Re: #table is not O(1)
- From: Mike Pall <mike-1409@xxxxxxxxxx>
- To: luajit@xxxxxxxxxxxxx
- Date: Tue, 9 Sep 2014 00:18:27 +0200
Dibyendu Majumdar wrote:
> On 5 September 2014 17:00, Mike Pall <mike-1409@xxxxxxxxxx> wrote:
> > A VM-defined array type would be more or less on par with a plain
> > Lua table wrt. load/store performance. But this is only, because
> > this use case of Lua tables has been optimized to death in LuaJIT.
>
> Surely a VM defined dense array type will be more efficient than the
> existing table type? Assuming that there are special op codes for handling
> such a type?
Not really. For numeric keys, the first thing it does is to check
the hidden array part of a Lua table. The bounds check and the
loads/stores have the same overhead as for a VM-defined (generic)
array type.
> I was stepping through the Lua VM (can't step through Luajit code sadly) -
> to see what happens in a simple case like this:
> x = {1,2,3}
> x[4] = 4
>
> For the last operation it sees that the array part is not large enough - so
> then it does also searches the hash table to see if the key exists there.
The array part grows exponentially, so for stores to consecutive
indexes that happens only every log N operations. The extra check
in the hash part (or even a rehash) only changes a constant factor.
> I assume having a type that acts as array or hash table adds to the
> complexity of this simple operation.
It adds to the implementation complexity, but not the asymptotic
time complexity of consecutive stores.
If you're still worried about the overhead of array growth, have a
look at the table.new() function in the LuaJIT 2.1 docs. Or use
typed FFI arrays.
--Mike
Other related posts:
