if/elseif/else vs tables

Posted by Shaun Biggs on Thu 24 May 2007 06:55 PM — 3 posts, 21,924 views.

Shaun Biggs USA Thu 24 May 2007 06:55 PM #0

I got bored today, so I decided to test something out. I've wondered about the efficiency of tables and cascading if statements. Just which one is better in which setting. I ran the following:


function testif( i )
  if i == 1 then
    return 2
  elseif i == 2 then
    return 3
  elseif i == 3 then
    return 4
  elseif i == 4 then
    return 5
  elseif i == 5 then
    return 6
  elseif i == 6 then
    return 7
  elseif i == 7 then
    return 8
  elseif i == 8 then
    return 9
  elseif i == 9 then
    return 10
  elseif i == 10 then
    return 11
  else
    return 1
  end
end

function testtable1( i )
tab = { [1]=2, [2]=3, [3]=4, [4]=5, [5]=6, [6]=7, [7]=8 , [8]=9, [9]=10, [10]=11, [11]=1}
  return tab[i]
end

tab2={}
for i = 1,10 do
  tab2[i] = i+1
end
tab2[#tab2+1]=1
function testtable2( i )
  return tab2[i]
end

function speedtest( count )
  start = os.time()
  test = 1
  for i = 1,count do
    test = testif( test )
  end
  print( "if:"..os.difftime( os.time(), start ) )
  start = os.time()
  for i = 1,count do
    test = testtable1( test )
  end
  print( "table1:"..os.difftime( os.time(), start ) )
  start = os.time()
  for i = 1,count do
    test = testtable2( test )
  end
  print( "table2:"..os.difftime( os.time(), start ) )
end

And got this out of it:

/speedtest(30000000)
if:15
table1:107
table2:11

Yes, that's a loop of 30 million tries. I started off with 100,000, but if and table2 were both less than a second... not a terribly good comparison. What I've learned today: Predefine your tables whenever possible. Also, if you're just running things through for one shot, you won't get terribly much better performance with a table. It just looks neater. Granted, even with the slowest table version, that's over a quarter of a million function calls per second on my machine.

David Haley USA Thu 24 May 2007 07:31 PM #1

If you have a very long series of if statements, the table is likely to be faster. If you have a very short series of if statements, the ifs are likely to be faster. And if your ifs are ordered such that the most probable cases are first, that will make the ifs faster.

In brief the issues are:

- it is faster to check equalities (in an if statement) than it is to index into a hash table.
- however, if you have to make a large number of equality tests before you find the right one, it might have been cheaper to take the hashing cost from the beginning.

If you were to make the numbers go up to, say, 100, you would probably start seeing the table outperforming the if checks.

And yes, it is a much better idea to create the table *outside* of the execution of the testtable function, either as a global variable or using a closure.

And incidentally I would argue that the cleanliness of the table solution outweighs the if checks, even if it were to be slightly slower. It depends on what you care about. If you're not hitting the table millions of times per second, it doesn't really matter. One of the most common "errors" for novice (and not-so-novice) programmers is what's called premature optimization: trying to optimize things, at the expense of clarity, because understanding what really matters in the end of the day with respect to the program speed.

Shaun Biggs USA Thu 24 May 2007 07:49 PM #2

I agree with every point you made. I should have been a bit more specific. I was testing small sets of matching items. I did try it at first with only boolean values, and here are the results:

/speedtest( 30000000 )
if:11
table:45
table:15

Creating the table each time takes up a LOT of time. Having the pre-created tables just increases relative speed exponentially the more elements I put in. I stopped at 11, since I just got sick of cut/pasting it all, and didn't want to set up a script to deal with it. With two elements, the slower table comparison takes 3 times as long as the faster table comparison. With 11 elements, it takes 9 times as long.

I also noted at the end the speed of the slowest test, creating the table each time, as being quite fast. If your speed requirements are higher than a quarter of a million tests per second in a mud client, you are doing something seriously wrong. Or making a mapper, which would have an already created set of tables. Also mentioned it looking better, and I should have mentioned that it is much easier to follow.