Re: #table is not O(1)
- From: Mike Pall <mike-1409@xxxxxxxxxx>
- To: luajit@xxxxxxxxxxxxx
- Date: Fri, 5 Sep 2014 18:00:17 +0200
Evan Wies wrote:
> Mike Pall wrote:
> > [Corollary: one should definitely separate the concepts of a map
> > and an array if one were to design a new computer language.]
>
> Given the various extensions to Lua included in LuaJIT, have you
> considered addressing this?
Well, you'd have to define the semantics of an array type first ...
Ok, let's assume you want to have JavaScript-style arrays with an
explicit length property: they have auto-grow, but not auto-shrink
semantics, i.e. stores can never shrink an array. OTOH composite
operations like pop() or explicit assignments to the length property
*do* change the array length. IMHO this is an acceptable compromise
for a generic-valued array type.
It's not hard to implement such an array type on top of a Lua table
as a user-defined type. The other option would be to have a separate
array type in the VM.
In either case, you'll get into deep trouble when exposing such a
new type to existing Lua libraries or to the Lua/C API -- this is
the real catch!
E.g. preventing the classic Lua table library operations from
messing up the length for a user-defined type will be difficult.
OTOH none of these would work out-of-the-box for a VM-defined type
either. I bet many people have written such an array type or even
released libraries for it. But none of them have been widely
adopted.
In practice, it's simply not that troublesome to use plain Lua
tables as arrays. The efficiency of the length operator doesn't
matter that much. And you can work around it, where it really
matters.
> For existing true array uses (where the table is never sparse),
> would there be significant benefits (besides the #length operator
> performance and accuracy)?
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.
A user-defined array type on top of Lua tables will be less
efficient than either one.
Given the significant downsides of introducing a separate array
type to the existing Lua ecosystem, I don't think it makes sense
to do so.
Or, to get back to my point: the trade-off would be quite different
for a newly designed language. The key considerations are still user
expectations and semantics, where IMHO a separate array type makes
more sense. Obviously, compiling operations for such a type is much
easier than the artistry required to make a map perform well when
used like an array.
All abstractions have a cost. Either the implementer pays for it or
the user. Or both.
--Mike
Other related posts:
