Re: Drawing the line between speed and simplicity/elegance

On Thu, May 7, 2015 at 12:34 PM, Parke <parke.nexus@gmail.com> wrote:

Actually, insert and remove appear to use a binary search, so the time
would be logarithmic, not linear.

http://www.lua.org/source/5.3/ltable.c.html#luaH_getn

Called from:

http://www.lua.org/source/5.3/lvm.c.html#luaV_objlen
http://www.lua.org/source/5.3/lapi.c.html#lua_len
http://www.lua.org/source/5.3/lauxlib.c.html#luaL_len
http://www.lua.org/source/5.3/ltablib.c.html#aux_getn
http://www.lua.org/source/5.3/ltablib.c.html#tinsert

...and...

On Thu, May 7, 2015 at 1:15 PM, Tim Hill <drtimhill@gmail.com> wrote:

I’m pretty sure insert/remove do NOT take linear time, though the time is complex to compute since Lua may or may not have migrated the array to the “array part” of the table. In either case your insert/remove time will be much closer to O(1) than O(n) since the table is based on hashing.

Well, O(n) complexity was indeed an assumption on my part. But it's certainly not O(1) in practice. The actual insertion or read itself should be constant time, but it still scans the table to find array bounds even if you supply the insertion point. And when basically every statement in my language is doing at least a few pushes and/or pops, on down the call chain, it adds up...

Contrived, totally non-scientific illustration:

> do local t, t0 = {}, os.clock()

>> for i=1,1000000 do t[i] = i end

>> print(os.clock() - t0, "seconds") end

0.035409 seconds

> do local insert, t, t0 = table.insert, {}, os.clock()

>> for i=1,1000000 do insert(t, i) end -- or: insert(t, i, i), with similar performance

>> print(os.clock() - t0, "seconds") end

0.231265 seconds

So you're right, it's not thousands of times slower. It is slower by an order of magnitude though, which could be non-trivial when the whole system and everything anyone might ever build on top of it depends on the stack for literally *everything*. I think insert/remove is less clear than array notation anyway, but that's maybe personal preference more than anything.

Brigham Toskin