So i did some experimenting today (on a #4200) to see for what dictionary sizes does B/S behave reasonably - and compare to another as a baseline. Sizes tested were consecutive powers of 2, and B/S flew off the handle so fast that to fit all points i had to use a chart with logarithmic scales:
Horizontal axis is size of the AA. Vertical is the time in microseconds to index a value (i.e. AA), averaged over 2^16 sample block. So we see how past 500-1000 it turns linear (or super-linear?), doubling individual time with each doubling of .count(). That is, it starts behaving O(N) - where a hash dictionary should stay O(1). In a way i sugar-coated it here by using log-log chart: the "hockey stick" looks much worse/steeper if scale was linear.
Conclusion: use roAssociativeArray preferably with <300 elements. Past 1000, roAA turns into molasses/tarpit.
Let's zoom in at the lower values, where roAA is usable, here is a linear (lin-lin) graph:
For small dictionaries, B/S is usable - but it would be a stretch to say it was "optimized" for small sizes, since Lua does dictionary access 7x faster even when B/S is at its best. Not sure why such big difference. It can't be the case-insensitivity, since it could just always hash based on lower-cased key and then resolve the collisions based on case-sensitivity.
I am including the code i used to test, so someone can check for flaws in my approach - as well as the data, so that one can draw their own charts and conclusions:
[spoiler=gory details:39dt7gim]Brightscript code and output:
Lua code and output:
Horizontal axis is size of the AA. Vertical is the time in microseconds to index a value (i.e. AA), averaged over 2^16 sample block. So we see how past 500-1000 it turns linear (or super-linear?), doubling individual time with each doubling of .count(). That is, it starts behaving O(N) - where a hash dictionary should stay O(1). In a way i sugar-coated it here by using log-log chart: the "hockey stick" looks much worse/steeper if scale was linear.
Conclusion: use roAssociativeArray preferably with <300 elements. Past 1000, roAA turns into molasses/tarpit.
Let's zoom in at the lower values, where roAA is usable, here is a linear (lin-lin) graph:
For small dictionaries, B/S is usable - but it would be a stretch to say it was "optimized" for small sizes, since Lua does dictionary access 7x faster even when B/S is at its best. Not sure why such big difference. It can't be the case-insensitivity, since it could just always hash based on lower-cased key and then resolve the collisions based on case-sensitivity.
I am including the code i used to test, so someone can check for flaws in my approach - as well as the data, so that one can draw their own charts and conclusions:
[spoiler=gory details:39dt7gim]Brightscript code and output:
for k = 1 to 16:
N = 2^k
n_loops = 2^16
dict = {}
for i = 0 to N-1:
dict[i.toStr()] = 7
next
keys = []
for i = 1 to n_loops:
keys.push((i mod N).toStr())
next
ti = createObject("roTimeSpan")
sum = 0
RunGarbageCollector()
ti.mark()
for each key in keys:
sum += dict[key]
next
time = 1e3 * ti.totalMilliSeconds() / n_loops
RunGarbageCollector()
ti.mark()
for each key in keys:
sum += 7
next
ref_time = 1e3 * ti.totalMilliSeconds() / n_loops
print N, time, time - ref_time
next
2 1.40381 0.640869
4 1.34277 0.564575
8 1.34277 0.579834
16 1.38855 0.62561
32 1.46484 0.686646
64 1.4801 0.701904
128 1.5564 0.778198
256 1.75476 0.976562
512 2.13623 1.32751
1024 2.91443 2.15149
2048 4.98962 4.22668
4096 10.6049 9.82666
8192 22.7814 22.0184
16384 53.5126 52.7496
32768 127.472 126.694
65536 327.148 326.385
Lua code and output:
for k = 1, 16 do
local N = 2^k
local n_loops = 2^16
local dict = {}
for i = 0, N-1 do
dict[tostring(i)] = 7
end
local keys = {}
for i = 1, n_loops do
keys[i] = tostring(i % N)
end
local sum = 0
collectgarbage('stop') -- just in case, to avoid GC peaks
local start = socket.gettime()
for _, key in pairs(keys) do
sum = sum + dict[key]
end
local time = 1e6 * (socket.gettime() - start) / n_loops
start = socket.gettime()
for _, key in pairs(keys) do
sum = sum + 7
end
local ref_time = 1e6 * (socket.gettime() - start) / n_loops
collectgarbage('restart')
print(N, time, time - ref_time)
end
[/spoiler:39dt7gim]
2 0.640869985 0.076295692
4 0.656127668 0.106811058
8 0.640869985 0.076295692
16 0.656127668 0.106811058
32 0.671388989 0.122076017
64 0.640869985 0.091553375
128 0.656127668 0.091549737
256 0.701904355 0.152587745
512 0.717165676 0.183110387
1024 0.717165676 0.167849066
2048 0.762942364 0.213625754
4096 0.808715413 0.198364432
8192 0.930784154 0.381467544
16384 0.991822162 0.442505552
32768 1.068114216 0.503539923
65536 1.15966759 0.579831976
