Speed Analysis of pairs and ipairs

[haza55]

[highlight]If you don't know what pairs and ipairs is, do not bother reading this.[/highlight]

So which is actually faster?

Most say ipairs is, and for the real world part they are correct. But when you have tables nearing 15k keyvalues, pairs is the better option.

Although the speed difference between ipairs and pairs is negligible(really really small).

For example a table with 100 keyvalues the difference between pairs and ipairs was 3.41E-07seconds.
Meaning ipairs was faster than pairs by 0.0000000341seconds.

[b]1,000 keyvalues, ipairs wins in speed.[/b]
[b]If the purple line is in the positive, it means ipairs was faster.[/b]
[img]http://img707.imageshack.us/img707/4135/1000m.png[/img]

[b]100,000 keyvalues, pairs wins in speed.[/b]
[b]If the purple line is in the negative, it means pairs was faster.[/b]
[img]http://img204.imageshack.us/img204/7159/100000z.png[/img]

[b]100,000 keyvalues, pairs wins in speed.[/b]
[b]Since the line is almost always negative, pairs is faster.[/b]
[img]http://img689.imageshack.us/img689/1583/100000diff.png[/img]

All the data was collected just after a garbage collection.
All the timing values were recorded with C++ Functions QueryPerformanceCounter and QueryPerformanceFrequency in Windows, which is the most precise timing.

[highlight]Now people can shut up about how ipairs is so much faster.[/highlight]

[yakahughes]

Wow thank you. Fly away, ipairs people.

[Kogitsune]

[QUOTE=yakahughes;19501136]Wow thank you. Fly away, ipairs people.[/QUOTE]

I'll keep using ipairs when appropriate ( when the table consists entirely of numeric keys ), and pairs when appropriate ( any time else ). You know, like before I saw this thread.

----

Since you've got the tool there, is this any faster / better than pairs?

for k, v in next, t do

Saw that in PIL and never got around to testing it myself.

[haza55]

[QUOTE=Kogitsune;19501198]I'll keep using ipairs when appropriate ( when the table consists entirely of numeric keys ), and pairs when appropriate ( any time else ). You know, like before I saw this thread.

----

Since you've got the tool there, is this any faster / better than pairs?

for k, v in next, t do

Saw that in PIL and never got around to testing it myself.[/QUOTE]

I'll have a look later.
I will also look at while loops, for i=1,bla etc.

[NullPoint]

-snip-

[editline]09:45AM[/editline]

[QUOTE=Kogitsune;19501198]I'll keep using ipairs when appropriate ( when the table consists entirely of numeric keys ), and pairs when appropriate ( any time else ). You know, like before I saw this thread.[/QUOTE]

this.

[fishface60]

[QUOTE=Kogitsune;19501198]Since you've got the tool there, is this any faster / better than pairs?

for k, v in next, t do

Saw that in PIL and never got around to testing it myself.[/QUOTE]
It should do exactly the same as pairs, except with one less function call. pairs(t) returns next, t

[Kogitsune]

[QUOTE=fishface60;19502386]It should do exactly the same as pairs, except with one less function call. pairs(t) returns next, t[/QUOTE]

I know this. I'm asking if that function call is going to make a difference across the long term, not if it functions differently.

It appears to just be called once, so it shouldn't beyond the expense of a single function call, though.

[Lexic]

This is very interesting. So it actually doesn't matter?
Could you do a speed analysis for the 1 to 200 mark please? I suspect very few people will use a table with more than 200 elements in it in gmod.

[haza55]

[img]http://img80.imageshack.us/img80/691/10002.png[/img]

[lua]
for k, v in pairs(tableToTraverse) do

for k, v in ipairs(tableToTraverse) do

while(k <= #tableToTraverse) do
k = k + 1

for i=1,#tableToTraverse do

for k, v in next,tableToTraverse, nil do
[/lua]

for i=1,#tableToTraverse do
is definitely the best way, but you need keys that are sequential from 1 to n

In all honesty, pairs or ipairs is the best, pairs working on every table and ipairs only working on integer keyed tables.

[Deco Da Man]

[QUOTE=haza55;19504848]
[lua]
for k, v in pairs(tableToTraverse) do

for k, v in ipairs(tableToTraverse) do

while(k <= #tableToTraverse) do
k = k + 1

for i=1,#tableToTraverse do

for k, v in next,tableToTraverse, nil do
[/lua]

for i=1,#tableToTraverse do
is definitely the best way, but you need keys that are sequential from 1 to n

In all honesty, pairs or ipairs is the best, pairs working on every table and ipairs only working on integer keyed tables.[/QUOTE]

Wow, enlightening

Questions:

What's with the sudden bump in while? Was that due to something on your PC, or does it happen every time?
Does anyone know the reason?

Are you doing:
[lua]
for i=1,#tableToTraverse do
[/lua]
or
[lua]
for i=1,#tableToTraverse do
local value = tableToTraverse[i]
[/lua]
for the fori test?

([b]Edit:[/b] As with the while loop. Are you indexing the table?)

Thanks!

[Overv]

-snip-

[haza55]

Every test gets the value and multiples it by 10.
Just to simulate it doing something.

for i=1,#tableToTraverse do
local value = tableToTraverse[i] * 10
end

Is exactly what it does.

As for that spike I would have to run the test again, it doesn't appear to be cpu related otherwise all the other results of the same table size would be up.

[fishface60]

How many times are you running the algorithm to get the results, it would smooth out the bumps if you ran it more often and averaged the results.
The bumps would be caused by your computer's scheduler pre-empting the garrysmod process to do something else, this would add the delay.

[haza55]

[QUOTE=fishface60;19526763]How many times are you running the algorithm to get the results, it would smooth out the bumps if you ran it more often and averaged the results.
The bumps would be caused by your computer's scheduler pre-empting the garrysmod process to do something else, this would add the delay.[/QUOTE]

A sample every increment of 10 in table size.

It is probably the thread being suspended.

[Lexic]

[QUOTE=haza55;19526877]A sample every increment of 10 in table size.

It is probably the thread being suspended.[/QUOTE]
So once.
He's suggesting you run the tests 10 times and take an average, for a cleaner test. :3:

[aVoN]

[QUOTE=haza55;19504848][media]http://img80.imageshack.us/img80/691/10002.png[/media]

[lua]
for k, v in pairs(tableToTraverse) do

for k, v in ipairs(tableToTraverse) do

while(k <= #tableToTraverse) do
k = k + 1

for i=1,#tableToTraverse do

for k, v in next,tableToTraverse, nil do
[/lua]

for i=1,#tableToTraverse do
is definitely the best way, but you need keys that are sequential from 1 to n

In all honesty, pairs or ipairs is the best, pairs working on every table and ipairs only working on integer keyed tables.[/QUOTE]
while could be a bit faster if you won't do the table-size-check in the while-statement everytime. Try
[lua]local size = #tableToTraverse;
local k = 0;
while(k <= size) do k = k + 1;[/lua]

[haza55]

[QUOTE=aVoN;19529469]while could be a bit faster if you won't do the table-size-check in the while-statement everytime. Try
[lua]local size = #tableToTraverse;
local k = 0;
while(k <= size) do k = k + 1;[/lua][/QUOTE]

Ahh good point, let me adjust the test.

[aVoN]

Thanks!
Still the fori will definitely beat everything: Fixed loop-size and no "counting" in lua (but in C++) directly.

[haza55]

[QUOTE=aVoN;19541115]Thanks!
Still the fori will definitely beat everything: Fixed loop-size and no "counting" in lua (but in C++) directly.[/QUOTE]

Yes, you are right.

This is the moving average of the new test. 10 samples of each table size are averaged, so this is much better data.
[img]http://img207.imageshack.us/img207/4914/1000movavgnew.png[/img]

Same data, but this time a linear trendline, I have also shown the r^2 value to show how close it fits the data.
[img]http://img249.imageshack.us/img249/9748/1000linearnew.png[/img]

You can see clearly that pairs(table) is just an alias for next,table,nil

[DarkSpider]

In your fori and while are you actually accessing the table's variables at index "i"?

[haza55]

[QUOTE=DarkSpider;19541501]In your fori and while are you actually accessing the table's variables at index "i"?[/QUOTE]

Yes.

[Lexic]

Wait wait wait wait wait wait.
pairs is [b]always[/b] faster than ipairs?

[haza55]

[QUOTE=Lexic;19546475]Wait wait wait wait wait wait.
pairs is [b]always[/b] faster than ipairs?[/QUOTE]

Seems so, I really do wonder were the assumption that ipairs was faster than pairs came from.

[Lexic]

Could you do an in-depth (a test every 1 or 2 size increases) for 1-200 please? I'm fairly sure that none of us will be working on tables of 1,000 or more in general usage.

[editline]07:45AM[/editline]

[QUOTE=haza55;19546528]Seems so, I really do wonder were the assumption that ipairs was faster than pairs came from.[/QUOTE]
Hey! That was my automerge.
However, I'm fairly sure this comes from the Programming in Lua book.

[editline]07:48AM[/editline]

It might have come from the same place as the belief that ipairs is faster if you put local k,v infront of it.

[DEADBEEF]

Interesting results, but I have one suggestion.
Can you link your image urls properly, it's a pain having to copy/paste them every time.

[DarKSunrise]

Apparently the media-tags broke.

[Grea$eMonkey]

[QUOTE=haza55;19546528]Seems so, I really do wonder were the assumption that ipairs was faster than pairs came from.[/QUOTE]

It makes sense. I mean, ipairs needs to return an iterator function in addition to everything else.

[NullPoint]

[QUOTE=grea$emonkey;19611309]It makes sense. I mean, ipairs needs to return an iterator function in addition to everything else.[/QUOTE]

So does pairs, It just return next as the iterator function.

[Grea$eMonkey]

[QUOTE=NullPoint;19611376]So does pairs, It just return next as the iterator function.[/QUOTE]

My bad.

[LuaStoned]

[QUOTE=DarKSunrise;19610888]Apparently the media-tags broke.[/QUOTE]

Garry disabled media-tags for images.