Is there a faster alternative to table.remove during time-critical code sections?

[jacques1]

I user table.remove several times to remove the first item from a table during my main game loop (which loops 30 times per second).

Recently I read in your documentation that table.remove may affect performance. So I am trying an alternative but its rather difficult to find out if it will affect performance less or more than table.remove.

Example:

itemTable = {1,2,3,4,5,6,7,8,9,0}

So instead of using table.remove( itemTable , 1) to remove the first item, is using below better/faster?

local tempTable = itemTable ; itemTable = {}

for i = 2 , #tempTable do

    itemTable[#itemTable+1] = tempTable[i]

end

So above basically creates a temporary table with the items of the original table, then clears the original table, then uses the temporary table to add all items back into the original table except for the 1st item.

In my case the table length is never really more then 10 items.

Any suggestions would be most helpful, as every millisecond I can save is critical due to numerous other calculations the main loop needs to go through,

cheers.

[anaqim]

if the table is only 10 items i doubt it matters whichever method you use but with larger tables, I often resort to rebuilding or setting flags instead of removing.

Never attempted to evaluate the difference in actual performance between the two methods though, just using the second one as it seems more logical.

[jacques1]

Okay, if anyone is interested, I decided to do up a quick test code, and looks like table.remove is actually at least 3 times faster then the replacement method. It appears the more items you have table.remove would be exponentially faster.

Not sure if this testing method is viable though as there is no other code running, but I assume if there was other code running both methods would slow down equally.

If the test method below is correct and table.remove is faster, that still does not solve the issue of performance when needing to remove an item. So I guess the only way to avoid performance issues is not to remove a table item nor replace it but as anaqim also suggested, to flag the table item. Of course this would require adjusting your actual game code to use flags instead of removing, and great care will be required to make sure you don’t forget the item is not removed.

local itemTable,tempTable,startTime -- table.remove method itemTable={1,2,3,4,5,6,7,8,9,10} startTime=system.getTimer() table.remove(itemTable,1) print("Table.remove method TIME:"..system.getTimer()-startTime..", #itemTable:"..tostring(#itemTable)) -- replacement method itemTable={1,2,3,4,5,6,7,8,9,10} startTime=system.getTimer() tempTable=itemTable;itemTable={} for j=2,#tempTable do itemTable[#itemTable+1]=tempTable[j] end print("Replacement method TIME:"..system.getTimer()-startTime..", #itemTable:"..tostring(#itemTable))

One last important thing to note, if you are removing more then 1 item from a table then it does appear the replacement method is faster exponentially. This can be tested by tweaking the above testing code to below:

local itemTable,tempTable,startTime -- table.remove method itemTable={1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0} startTime=system.getTimer() for j=1,10 do table.remove(itemTable,j) end print("Table.remove method TIME:"..system.getTimer()-startTime..", #itemTable:"..tostring(#itemTable)) -- replacement method itemTable={1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0} startTime=system.getTimer() tempTable=itemTable;itemTable={} for j=11,#tempTable do itemTable[#itemTable+1]=tempTable[j] end print("Replacement method TIME:"..system.getTimer()-startTime..", #itemTable:"..tostring(#itemTable))

Appreciate the feedback and hope this may help others. Cheers.

[anaqim]

Hi again,

Great info!

I work mostly with async network callbacks so very little of what I’ve done so far has been time critical, which is why I havent spent much time on the subject.

There was one game but there the underlying table didnt need real time modification as I used the flag method to control display objects based off the table instead.

I’ll keep your result in mind if/when I’ll need better precision.

[jacques1]

Thanks for your time Anaqim,

my game deals with 100s of objects that each have tables that need to constantly be modified due to physics collisions / pathfinding and other influences, so every milisecond saved is a very critical for me.

If you hadn’t replied I wouldn’t have bothered to do some timing test code and would have stuck with my new replacement method which actually ends up being slower than when i was using table.remove.

Will keep your flag approach in mind too to see if it can be of use.

Cheers!

[anaqim]

Likewise Jacques1,

One thing i love about lua is how easy it is to tag just about any array/table.

It is just so useful and a great way to “transport” additional info from function to function

Cheers!

[yvandotet]

I prefer to use “for-pairs loop”, there are less “mistake” about object’s removes, places in the table, etc…

And to remove object, I use myTable[index]=nil

when you have

local t={} t[1]="a" t[5]="z"

the line table.remove(t,5) don’t work, but t[5]=nil does  ( and #t will give 1 instead of 2 ).

[anaqim]

thanks for the tip yvandotet 

[Alan_PlantPot]

@yvandotet

I prefer to use “for-pairs loop”, there are less “mistake” about object’s removes, places in the table, etc…

And to remove object, I use myTable[index]=nil

when you have

local t={} t[1]="a" t[5]="z"

the line table.remove(t,5) don’t work, but t[5]=nil does  ( and #t will give 1 instead of 2 ).

#t would return 1 both before and after t[5] = nil . The # operator will return the highest value before nil is reached, and since t[2] is already nil in your example, #t will always return 1.

Likewise if you did this:

local t = {} for i = 2, 10000000 do t[i] = "aaaa" end print(#t)

the #t would print 0, because t[1] is nil.

[yvandotet]

yes thankx for the arguments i know it.

For the initial question, use that function to count the number of number-key element, it’s better than " #(table) "

local function hashtag(t) assert( t and type(t)=="table","not a good input for hashtag-function" ) local n=0 for ind in pairs(t) do if type(ind)=="number" then n=n+1 end end return n end local tab={} tab[1]="a" tab[5]="z" print(#tab) \>\>\> 1 print(hashtag(tab)) \>\>\> 2 (better :D)

for a global counting function, just remove the if-condition about the type of the key.

[nick_sherman]

@yvandotet

I prefer to use “for-pairs loop”, there are less “mistake” about object’s removes, places in the table, etc…

And to remove object, I use myTable[index]=nil

when you have

local t={} t[1]="a" t[5]="z"

the line table.remove(t,5) don’t work, but t[5]=nil does  ( and #t will give 1 instead of 2 ).

I have found for-pairs loops to be a lot slower in time-critical situations. If you know the fields that are in the table, it’s quicker to loop through using another table to lookup than k, v in pairs. If you extrapolate the below to hundreds or thousands of records with tens of fields, perhaps being processed many times a second, the first bit of code will be a lot quicker than the in pairs code, even if it is more long-winded.

[lua]

local fields = {“Name”, “Age”, “Address”}

local data = {

{Name = “Tony”, Age = 35 , Address = “Bolton”},

{Name = “Nigel”, Age = 56, Address = “Ipswich”}}

for a = 1, #data, 1 do

      for b = 1, #fields, 1 do

            local k = fields[b]

            local v = data[a][k]

           

            print (k, v)

      end

end

for k, v in pairs(data) do

      print (k, v)

end

[/lua]

[davebollinger]

…and if you take @nick_sherman’s approach and extrapolate it even further, perhaps to 10’s of thousands of records with dozens of fields, then don’t even hashtag your data fields, just imply them by position, and you’ll save both time and memory, fe:

-- field name forward lookup (ie, get name from index): local fieldNames = { "Name", "Age", "Address" } local data = { {"Tony", 35, "Bolton"}, {"Nigel", 56, "Ipswich"} } for recordNumber = 1, #data do for fieldNumber = 1, #fieldNames do -- "k" is NOT needed for RETRIEVAL at all -- provided only to have something for print() below local k = fieldNames[fieldNumber] local v = data[recordNumber][fieldNumber] print(k,v) end end

also fwiw, you might want a reverse lookup too:

-- field index reverse lookup (ie, get index from name): local fieldIndices = { Name=1, Age=2, Address=3 } for recordNumber = 1, #data do print(data[recordNumber][fieldIndices.Name] .. "'s age is " .. data[recordNumber][fieldIndices.Age]) end

if extending even further, perhaps 100 thousand records w hundred fields, then you might even want to break up the table into discrete indexed arrays of Name[n], Age[n], Address[n].  (bc each record takes 36 bytes, each hash take 40 bytes, while a numeric index just 16)  But… you would NOT want to do that if deletion (rather than storage/retrieval) is your primary concern!!

(also note that memory usage is heavier for a dynamically allocated table, compared to these static initialized examples)

[anaqim]

if the table is only 10 items i doubt it matters whichever method you use but with larger tables, I often resort to rebuilding or setting flags instead of removing.

Never attempted to evaluate the difference in actual performance between the two methods though, just using the second one as it seems more logical.

[jacques1]

Okay, if anyone is interested, I decided to do up a quick test code, and looks like table.remove is actually at least 3 times faster then the replacement method. It appears the more items you have table.remove would be exponentially faster.

Not sure if this testing method is viable though as there is no other code running, but I assume if there was other code running both methods would slow down equally.

If the test method below is correct and table.remove is faster, that still does not solve the issue of performance when needing to remove an item. So I guess the only way to avoid performance issues is not to remove a table item nor replace it but as anaqim also suggested, to flag the table item. Of course this would require adjusting your actual game code to use flags instead of removing, and great care will be required to make sure you don’t forget the item is not removed.

local itemTable,tempTable,startTime -- table.remove method itemTable={1,2,3,4,5,6,7,8,9,10} startTime=system.getTimer() table.remove(itemTable,1) print("Table.remove method TIME:"..system.getTimer()-startTime..", #itemTable:"..tostring(#itemTable)) -- replacement method itemTable={1,2,3,4,5,6,7,8,9,10} startTime=system.getTimer() tempTable=itemTable;itemTable={} for j=2,#tempTable do itemTable[#itemTable+1]=tempTable[j] end print("Replacement method TIME:"..system.getTimer()-startTime..", #itemTable:"..tostring(#itemTable))

One last important thing to note, if you are removing more then 1 item from a table then it does appear the replacement method is faster exponentially. This can be tested by tweaking the above testing code to below:

local itemTable,tempTable,startTime -- table.remove method itemTable={1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0} startTime=system.getTimer() for j=1,10 do table.remove(itemTable,j) end print("Table.remove method TIME:"..system.getTimer()-startTime..", #itemTable:"..tostring(#itemTable)) -- replacement method itemTable={1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0} startTime=system.getTimer() tempTable=itemTable;itemTable={} for j=11,#tempTable do itemTable[#itemTable+1]=tempTable[j] end print("Replacement method TIME:"..system.getTimer()-startTime..", #itemTable:"..tostring(#itemTable))

Appreciate the feedback and hope this may help others. Cheers.

[anaqim]

Hi again,

Great info!

I work mostly with async network callbacks so very little of what I’ve done so far has been time critical, which is why I havent spent much time on the subject.

There was one game but there the underlying table didnt need real time modification as I used the flag method to control display objects based off the table instead.

I’ll keep your result in mind if/when I’ll need better precision.

[jacques1]

Thanks for your time Anaqim,

my game deals with 100s of objects that each have tables that need to constantly be modified due to physics collisions / pathfinding and other influences, so every milisecond saved is a very critical for me.

If you hadn’t replied I wouldn’t have bothered to do some timing test code and would have stuck with my new replacement method which actually ends up being slower than when i was using table.remove.

Will keep your flag approach in mind too to see if it can be of use.

Cheers!

[anaqim]

Likewise Jacques1,

One thing i love about lua is how easy it is to tag just about any array/table.

It is just so useful and a great way to “transport” additional info from function to function

Cheers!

[yvandotet]

I prefer to use “for-pairs loop”, there are less “mistake” about object’s removes, places in the table, etc…

And to remove object, I use myTable[index]=nil

when you have

local t={} t[1]="a" t[5]="z"

the line table.remove(t,5) don’t work, but t[5]=nil does  ( and #t will give 1 instead of 2 ).

[anaqim]

thanks for the tip yvandotet 

[Alan_PlantPot]

@yvandotet

I prefer to use “for-pairs loop”, there are less “mistake” about object’s removes, places in the table, etc…

And to remove object, I use myTable[index]=nil

when you have

local t={} t[1]="a" t[5]="z"

the line table.remove(t,5) don’t work, but t[5]=nil does  ( and #t will give 1 instead of 2 ).

#t would return 1 both before and after t[5] = nil . The # operator will return the highest value before nil is reached, and since t[2] is already nil in your example, #t will always return 1.

Likewise if you did this:

local t = {} for i = 2, 10000000 do t[i] = "aaaa" end print(#t)

the #t would print 0, because t[1] is nil.