[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: table library changes (was Re: table.new in 5.3?)
- From: Philipp Janda <siffiejoe@...>
- Date: Thu, 28 Nov 2013 11:02:24 +0100
Am 28.11.2013 07:12 schröbte Tim Hill:
On Nov 27, 2013, at 7:57 PM, Philipp Janda <firstname.lastname@example.org> wrote:
what if the table implementation changes to use (say) a red/black
tree, which has vastly different performance characteristics?
If you change the implementation of tables, both the Lua version and the C version of `table.insert` and `table.remove` will show a similar new performance characteristic, because both version use the same operations (`#`, `rawset`, and `rawget`). Unless you change Lua's C API and don't expose those new operations to Lua, but in that case you need a new table library anyway.
No, I think we’re talking about different things here. At the moment, tables are (kind of) dynamic arrays (the array part, that is), where most (but not all) of the integer keys are implied within a dynamically sized array. In such an implementation, any insert operation inevitably involves some form of “shifting up” of items to make room for the new item. Such an algorithm, expressed in C or Lua, has similar performance .. approx. O(n) for an n item table. At root, this is because “insert” is a “compound” operation for this particular implementation, which simply involves an algorithm wrapped around one or more lower-level “primitive” operations such as rawget/rawset.
Yes. The current C API determines how an insert function has to look like.
BUT, if you change the internals of tables to use (say) a red/black tree, then insert is a totally different operation .. in fact it is now a “primitive" operation in it’s own right, and is no longer just a standard algorithm wrapped around rawget/rawset (in fact, these primitives are no longer used for insert).
The good news is that this would be compatible with the current table
implementation (tables being key-value-mappings). The bad news is that
you still would have a loop of rawget/rawsets because you need to
increment the keys in the nodes to the right of the insertion point, but
I see what you mean. I can imagine using a deque or an array that is
re-allocated on both ends for the array part, so that you could save
rawget/rawset operations by shifting the smaller portion of the array
part. But the point is that you want to hide the table internals behind
a Lua API while it already is hidden behind the C API. The current table
library already could use `memmove` on the array part to speed up
´table.insert` operations if it were willing to break the encapsulation
of the public C API. If/when it does (and the change is worth the
effort), then by all means `table.insert` has earned it's place in the
core library (although you still wouldn't be able to use it with proxy
tables/userdata, or for multiple elements at once).
Now, if you have Lua code that “knows” inserts can be done with rawget/rawset, they will continue to work, but with O(n) performance. The red/black tree will bring no benefit because the code has been designed around the characteristics of a particular implementation .. which is bad. If, otoh, you had used table.insert(), then code will suddenly get a free performance boost from O(n) to O(1), without a re-write .. which is good.
So, the algorithm change makes Lua code run in O(n) time while C code can run in O(1) time. Of course, the Lua code can be changed if the new low-level insert primitive is exposed to Lua, but (a) that is expensive to do and (b) that nice new API is … what? .. the table.insert() API that people are discussing deleting!
I doubt that `insert` would be a good primitive -- maybe `shift` or
This all comes down to API abstraction .. it’s bad to design an API that exposes the idiosyncrasies of a particular implementation … you are far better having an API that can apply to many DIFFERENT implementations. The existing Lua API, imho, is rather good at this, and I for one don’t want to see that clean abstraction abandoned.
Yes. The current API abstraction for tables is at the C API level, and
it doesn't permit a significantly better `table.insert` implementation
in C than in Lua because Lua has access to all operations that C has
access to. I'm not overly concerned about `table.insert` being in Lua's
standard library -- that's still a lot less fat than in any other
language, and apparently there *are* people out there using it. I'm just
saying that at the moment it doesn't have any properties (other than
compatibility) that justify its existence in the core table library more
than any other remotely useful function that works on tables.