Dynamic arrays and offset caching

As you know, dynamic arrays in OpenInsight are internally represented as delimiter-separated strings commonly containing fields, values and sub-values. Traditionally, locating an element required scanning the string from the start to find the required delimiters at the specified index . This can be a performance issue on large arrays, so one of the new features we’ve added to OpenInsight 11 is index/offset caching.

This is a technique that involves caching the byte offsets of previously located field, value and sub-value indexes when you use the “<>” operators, and the Insert/Extract/Replace/Delete functions. This means that we don’t always have to start scanning from the beginning of the string each time an element is accessed.

For example, suppose field 67 is located at byte offset 234, and field 68 begins at offset 245.

  • Without caching, locating field 68 requires rescanning the dynamic array from the beginning to find all preceding field marks.
  • With caching, once field 67 has already been located, the search for field 68 can begin from offset 234 instead of offset 1.

This optimization is especially effective when forward-iterating through large dynamic arrays, where successive accesses are close together. In previous versions, repeatedly accessing successive fields could result in near O(n²) scanning behaviour for large arrays. Offset caching eliminates much of this repeated work.

Consider the following program which processes 10000 SYSOBJ keys:

compile function test_dyn_cache( void )
$insert rti_Struct_Equates
$insert logical
select @file_sysobj
eof = FALSE$
idList = ""
loop
readNext id else eof = TRUE$
until eof
idList := id : @fm
repeat
idList[-1,1] = ""
idList = field( idList, @fm, 1, 10000 )
ctr = fieldCount( idList, @fm )
pf = blank_Struct( "MSWIN_LARGE_INTEGER" )
pcStart = blank_Struct( "MSWIN_LARGE_INTEGER" )
pcEnd = blank_Struct( "MSWIN_LARGE_INTEGER" )
call msWin_QueryPerformanceFrequency( pf )
call msWin_QueryPerformanceCounter( pcStart )
for x = 1 to ctr
id = idList<x>
next
call msWin_QueryPerformanceCounter( pcEnd )
pcStart = struct_To_Var( pcStart, "MSWIN_LARGE_INTEGER" )
pcEnd = struct_To_Var( pcEnd, "MSWIN_LARGE_INTEGER" )
pf = struct_To_Var( pf, "MSWIN_LARGE_INTEGER" )
pcTime = ( ( pcEnd - pcStart ) * 1000 ) / pf
call send_Dyn( "TEST_DYN_CACHE processed " : ctr : " items -> " : pcTime : " ms" )
return ""

Running this benchmark on the same machine using v10.2.4 took approximately 360ms, while OpenInsight 11 completed the same test in around 1–2ms.

For small dynamic arrays the difference may not be noticeable, but performance improvements become increasingly significant as array sizes grow.

This means you can continue using the familiar “<>” syntax for sequential dynamic array processing without needing to rewrite code using LOOP/REMOVE or LOOP/[] parsing patterns.

2 thoughts on “Dynamic arrays and offset caching

  1. Matt's avatarMatt

    Nice! I assume this is irrespective of UTF8 mode..

    What about iterating backwards, or random access though.. How do the benchmarks compare between OI10 and OI11 for this:

    for x = ctr to 1 step -1
    i = rnd( x) + 1
    id = idList< i>
    idList = delete( idList, i,0,0)
    next

    If OI11 suffers here cf OI10 then is there a way to control this behaviour?

    BTW, my 10.2.4 doesn’t have msWin_QueryPerformanceFrequency()

    Cheers, M@

    Reply
    1. Captain C's avatarCaptain C Post author

      Hi M@,

      UTF8 is not a factor in this as we’re just searching for single byte delimiters that are the same in either mode. All my tests are actually done in UTF8 mode – I just left that bit out of the example for clarity.

      Forwards and backwards iteration is optimized – on my machine forwards is averaging ~1.2ms, with backwards averaging ~1.4ms. On v10 both directions took the same time (~360ms)

      Random is what you’d expect – iterating using an rnd() index on that array averaged ~230ms total in v11, and ~370ms on v10 – all depends on where you land to see how effective the cache is.

      For your test specifically, v11 averaged ~305ms, while v10 averaged ~490ms, so still an improvement.

      My 10.2.4+ does have msWin_QueryPerformanceFrequency() – let me know if you want an RDK 🙂

      Cheers, /c

      Reply

Leave a comment