Repeated calls to $order(^xxx("")) run faster

[nars1]

Final Release Note

Repeated calls to $order(^xxx("")) where xxx is a global name run faster. (YDB#12)

Description

Below is a test case that shows $order(^x("")) done in a loop takes .2487 microseconds on average. Whereas $order(^x(""),-1) takes .1652 microseconds on average. That is forward $order is 50% slower than reverse $order. In this case, the global ^x has 2 levels of index blocks. For globals that are taller, the slowdown is even more. Turns out this is because the clue (which is set on any traversal of the GVT) is not set for the forward $order case whereas it is for the reverse $order and that clue helps later calls to the reverse $order to run a lot faster (by avoiding linear scans of the index blocks and data blocks).

mumps -run orderperf
450,094 nodes created in 357,239 microseconds
Avg. time to access first node .2487 microseconds
Avg. time to access last node .1652 microseconds

cat orderperf.m
orderperf ; $order() performance statistics
do create
do order
do previous
quit
create ;
kill ^x
set time1=$zut
for i=1:1:1E5 do
. set j=$random(1E9),k=$random(10)
. for l=1:1:k if $increment(m) set ^x(j,l)=$random(1E6)
set time2=$zut
write $fnumber(m,",")," nodes created in ",$fnumber(time2-time1,",")," microseconds",!
quit
order ;
set time1=$zut
set o=0
for i=1:1:1E4 do
. set x=$order(^x(""))
set time2=$zut if $increment(o,time2-time1)
write "Avg. time to access first node ",$fnumber(o/i,",")," microseconds",!
quit
previous;
set time1=$zut
set x=$order(^x(""))
set time1=$zut
set o=0
for i=1:1:1E4 do
. set x=$order(^x(""),-1)
set time2=$zut if $increment(o,time2-time1)
write "Avg. time to access last node ",$fnumber(o/i,",")," microseconds",!
quit

Draft Release Note

Repeated calls to $order(^xxx("")) where xxx is a global name run faster.

[ksbhaskar]

Suggested alternate release note that omits implementation details:

Repeated calls to $order(^xxx("")) where xxx is a global name run faster.