When adding to tables without table.create, Lua will often allocate more memory than needed (because it allocates in powers of two.) In most cases I just want to save a bit of memory.
This isn’t a bottleneck in the same way table searching is, but I’ll search my codebase and give a few examples:
- Creating nested tables of arbitrary size for use with
terrain:WriteVoxels()
- I have a list of parts, and now to build the object later I need to store a corresponding list of cframe offsets.
- I now want to make a clone of the parts above, so I need to create a table of identical length and move cloned parts into the table. (This seems to be my most common use-case)
There are quite a few other cases, but most of them are only used during my game’s compile process, so they never see the live game.
I found this implementation was fastest, especially for long lists:
return function(list, v, p)
-- v is the value we're searching for
-- p is where to start the search (generally the length of the table)
-- p is decremented as we search
if list[p] == v then -- Check the top of the list (most common case)
return p
end
p = p - 1 -- We just checked the top of the list, so we subtract 1
-- This code is auto-generated
while p>32 do
local b,c,d,e,f,g,h,i,j,k,l,m,n,o,q,r,s,t,u,w,x,y,z,a1,a2,a3,a4,a5,a6,a7,a8,a9 = unpack(list,p-31,p)--$const
if a9==v then return p elseif a8==v then return p-1 elseif a7==v then return p-2 elseif a6==v then return p-3
elseif a5==v then return p-4 elseif a4==v then return p-5 elseif a3==v then return p-6 elseif a2==v then return p-7
elseif a1==v then return p-8 elseif z==v then return p-9 elseif y==v then return p-10 elseif x==v then return p-11
elseif w==v then return p-12 elseif u==v then return p-13 elseif t==v then return p-14 elseif s==v then return p-15
elseif r==v then return p-16 elseif q==v then return p-17 elseif o==v then return p-18 elseif n==v then return p-19
elseif m==v then return p-20 elseif l==v then return p-21 elseif k==v then return p-22 elseif j==v then return p-23
elseif i==v then return p-24 elseif h==v then return p-25 elseif g==v then return p-26 elseif f==v then return p-27
elseif e==v then return p-28 elseif d==v then return p-29 elseif c==v then return p-30 elseif b==v then return p-31 end
p=p-32
end
if p>16 then
local b,c,d,e,f,g,h,i,j,k,l,m,n,o,q,r = unpack(list,p-15,p)--$const
if r==v then return p elseif q==v then return p-1 elseif o==v then return p-2 elseif n==v then return p-3
elseif m==v then return p-4 elseif l==v then return p-5 elseif k==v then return p-6 elseif j==v then return p-7
elseif i==v then return p-8 elseif h==v then return p-9 elseif g==v then return p-10 elseif f==v then return p-11
elseif e==v then return p-12 elseif d==v then return p-13 elseif c==v then return p-14 elseif b==v then return p-15 end
p=p-16
end
-- Check the remaining values
for i = p, 1, -1 do
if list[i] == v then
return i
end
end
-- Return false so the result can't be used with table.remove
return false
end
ipairs in the new VM is most likely fast enough to out-compete the unpack batches I’m doing here, but you can’t use ipairs to iterate backwards. I try to set everything up to modify the top of the list more than the bottom to reduce the need to shift everything. I also try to always disconnect things in the reverse order I connected them to reduce the need to search the whole list.
although there’s one big change that hasn’t happened yet and might only ship with v2 of new VM later this year, which will make Vector3 math much faster by making Vector3 a basic non-heap allocated type.