lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index] 

Am 28.11.2013 07:12 schröbte Tim Hill:


On Nov 27, 2013, at 7:57 PM, Philipp Janda <siffiejoe@gmx.net> 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 something. 



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. 



—Tim



Philipp