Re: table library changes (was Re: table.new in 5.3?)

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.

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).

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!

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.

—Tim