Indexed dictionary search vs table.find benchmark

Help and Feedback Scripting Support
, ,
#1

Derived from this topic, the question arose about the difference in performance between searching for a key within a dictionary by indexed access, or by using table.find.

I created a benchmark:

local dic = {}
local tab = {}
local elements = 30000
local keyToFind = "k" .. elements

print("table and dictionary with " .. elements .. " elements")
print("key to find in both: ", keyToFind)
print()

-- create test dictionary and table
for i = 1, elements do
	key = "k" .. i
	dic[key] = 0 -- create dictionaty
	table.insert(tab, key) -- create table
end

-- benchmark
local time = tick()
for i = 1, elements do
	if dic[keyToFind] then end
end
local timeD = tick() - time
print("seconds to find a key in dictionary:\t", timeD)

local time = tick()
for i = 1, elements do
	if table.find(tab, keyToFind) then end
end
local timeT = tick() - time
print("seconds to find a key in array (table.find):\t", timeT)
print()

print("dictionary indexing was " .. timeT / timeD .. " x faster than table.find")

Here the results:

  table and dictionary with 30000 elements
  key to find in both:  k30000
  
  seconds to find a key in dictionary:	         0.00047421455383301
  seconds to find a key in array (table.find):	 2.804699420929
  
  dictionary indexing was 5914.4102564103 x faster than table.find
6 Likes
Is there a way to have a dictionary only with keys?
#2

You’ve done a little mistake, when using table.find you don’t need to loop through the table, just use it with no loop, instead of

for i = 1, elements do
	if table.find(tab, keyToFind) then end
end

just do

if table.find(tab, keyToFind) then end

Rerunning your benchmark fixed gave me these results:

table and dictionary with 30000 elements
key to find in both:  k30000

seconds to find a key in dictionary:	 0.00062441825866699
seconds to find a key in array (table.find):	 0.00012683868408203

dictionary indexing was 0.20313096601756 x faster than table.find

I’m not sure why does the “x faster” line say incorrect numbers but it should be something around x5 times faster not x5914 times

2 Likes
How do i keep these variables local?
#3

Not my mistake. It’s simulating 30,000 searchings for each instruction, to have the same balanced result of the benchmark.

3 Likes
#4

If you are not running that much times per frame then you could use it in RenderStepped and get no performance impact

#5

Wrong. If I have to search for a key in a dictionary with 10,000 elements once per frame at 40 fps, make the math…

1 Like
#6

Just to be fair, in the original test I purposely sent table.find to look for the last item in the table, so it had to loop internally 30000 times until it found the result.
So, I changed the item to be searched: instead of the last, the first; in this way table.find will immediately find the first item.
Even so, table.find proved to be 5 times slower than searching for an index in a dictionary:

  table and dictionary with 30000 elements
  key to find in both:  k1
  
  seconds to find a key in dictionary:	 0.00042033195495605
  seconds to find a key in array (table.find):	 0.0022177696228027
  
  dictionary indexing was 5.2762336925695 x faster than table.find
9 Likes
Some Benchmarking