6 ms·

> It correctly handles the strange array/map duality of lua tables in the most efficient way it can do safely (serializing both variants concurrently and only w

by orf 2y ago

> It correctly handles the strange array/map duality of lua tables in the most efficient way it can do safely (serializing both variants concurrently and only writing out the correct one at the end) The article doesn’t expand on this - what are they referring to? Are lua tables arrays? Serializing something common like tables 2x seems like a massive overhead.

copx 2y ago
A Lua table is data structure which contains both an array and a hash map part i.e. it accepts both indexed and keyed entries. E.g.: myTable[1] = "red" myTable.name = "Color Codes"
- Dylan16807 2y ago
  For the actual language, there are no "parts". Every table is a map, and the implementation could do several things behind the scenes. The issue is not knowing if the table can be encoded as an array, since that's more compact in many encodings.
MattJ100 2y ago
Lua doesn't have a separate "array" type, as arrays are just a special case of key->value where the key is always a positive integer. While this is nice (it simplifies the language yet Lua tables are incredibly versatile), it does indeed make it a little more work to translate structures to languages/serializations that distinguish between the two types, if the serializer needs to guess at runtime (e.g. if you don't have a predefined schema). I can't comment on the efficiency of whatever this implementation is doing, I haven't read the code. It does sound a little expensive. Also it's not always 100% clear which the correct mapping is, unless the developer explicitly picks one. For example, a serializer has no way to determine whether '{}' is intended to be an empty array or an empty hash. Another common gotcha, e.g. when translating to JSON, is that Lua does not restrict the types of keys (while JSON objects only support string keys), so boolean true/false are possible keys, for example, which cannot be translated to JSON directly.
- matheusmoreira 2y ago
  I ended up drawing the same conclusion while implementing my language. An insertion ordered hash table turned out to be just a normal array of values where the keys map to array indexes instead. Other than speed, I'm struggling to think of a good reason to keep the dedicated array type...
  - cmovq 2y ago
    Note that the lua VM still optimizes tables that look like arrays by storing values in the array separate from the hash table [1]. [1]: https://www.lua.org/gems/sample.pdf https://www.lua.org/gems/sample.pdf
    - matheusmoreira 2y ago
      This is really interesting. So it doesn't hash integer keys, it uses them directly as indexes in a separate array. How is order maintained between the two arrays though?
      - wruza 2y ago
        Badly. In addition to https://news.ycombinator.com/item?id=41146240 https://news.ycombinator.com/item?id=41146240 Lua has two iterators: for k, v in pairs(t) do … end for i, v in ipairs(t) do … end ipairs just counts from 1 to n until t[n] == nil. Pairs returns all keys (array’s too) in an order that is undefined. Merged dict and array looks neat on syntactic level but really is pita to deal with. It’s a questionable design in itself, and then you go outside and realize that you’re incompatible with everything else cause {} and [] are two different things.
        matheusmoreira 2y ago
        Yeah, I assumed as much... Looks like order just isn't maintained at all. Stopping at the first nil is pretty confusing and surprising to me, it implies a loop over an array full of nils would not iterate even once which makes no sense. Javascript does it right: array length is the greatest numerical index in the object plus one. Abstraction seemed neat at first but completely fell apart in the details. Many such cases. Looks like a true vector type is a good idea after all. > Merged dict and array looks neat on syntactic level but really is pita to deal with. It doesn't have to be that way. An insertion ordered hash table also contains an array part, it's just that it's completely internal to the implementation. It behaves just like a normal hash table, but internally the keys hash to indexes in the array part. The order of the hashes is undefined but the order of the key-value pairs in the array part is defined to be the order they were inserted into the table. It's really neat and it seems to work really well. It behaves exactly like an array if used like one. It definitely isn't an array though: integer keys are not offsets, they are hashed like every other key type. This doesn't seem like a huge problem to me. The lack of this property seems to be the root cause of the complexity of Lua's tables. It's tempting to think of these insertion ordered hash tables as some kind of superset of arrays. Just like it's tempting to think of hypergraphs as supersets of graphs, of graphs as supersets of trees, and of trees as supersets of linked lists. I haven't learned of any cracks in this abstraction, at least not yet. The reason to prefer less general data structures always seems to be performance, not correctness. Offsetting a pointer is faster than hashing some bytes, indexing two arrays, comparing keys for equality and then offsetting a pointer.
commodoreboxer 2y ago
In my Lua/cbor use, what I did was use a custom tag (I think the ID was 0x7AB1E, for "TABLE") with an array type composed of a sub array and map. The array contains the array elements of the table up to the first nil, and the map contains the rest. Worked well enough for my use.

by orf 2y ago

copx 2y ago

A Lua table is data structure which contains both an array and a hash map part i.e. it accepts both indexed and keyed entries. E.g.: myTable[1] = "red" myTable.name = "Color Codes"

Dylan16807 2y ago
For the actual language, there are no "parts". Every table is a map, and the implementation could do several things behind the scenes. The issue is not knowing if the table can be encoded as an array, since that's more compact in many encodings.

MattJ100 2y ago

Lua doesn't have a separate "array" type, as arrays are just a special case of key->value where the key is always a positive integer. While this is nice (it simplifies the language yet Lua tables are incredibly versatile), it does indeed make it a little more work to translate structures to languages/serializations that distinguish between the two types, if the serializer needs to guess at runtime (e.g. if you don't have a predefined schema). I can't comment on the efficiency of whatever this implementation is doing, I haven't read the code. It does sound a little expensive. Also it's not always 100% clear which the correct mapping is, unless the developer explicitly picks one. For example, a serializer has no way to determine whether '{}' is intended to be an empty array or an empty hash. Another common gotcha, e.g. when translating to JSON, is that Lua does not restrict the types of keys (while JSON objects only support string keys), so boolean true/false are possible keys, for example, which cannot be translated to JSON directly.

matheusmoreira 2y ago
I ended up drawing the same conclusion while implementing my language. An insertion ordered hash table turned out to be just a normal array of values where the keys map to array indexes instead. Other than speed, I'm struggling to think of a good reason to keep the dedicated array type...
- cmovq 2y ago
  Note that the lua VM still optimizes tables that look like arrays by storing values in the array separate from the hash table [1]. [1]: https://www.lua.org/gems/sample.pdf https://www.lua.org/gems/sample.pdf
  - matheusmoreira 2y ago
    This is really interesting. So it doesn't hash integer keys, it uses them directly as indexes in a separate array. How is order maintained between the two arrays though?
    - wruza 2y ago
      Badly. In addition to https://news.ycombinator.com/item?id=41146240 https://news.ycombinator.com/item?id=41146240 Lua has two iterators: for k, v in pairs(t) do … end for i, v in ipairs(t) do … end ipairs just counts from 1 to n until t[n] == nil. Pairs returns all keys (array’s too) in an order that is undefined. Merged dict and array looks neat on syntactic level but really is pita to deal with. It’s a questionable design in itself, and then you go outside and realize that you’re incompatible with everything else cause {} and [] are two different things.
      - matheusmoreira 2y ago
        Yeah, I assumed as much... Looks like order just isn't maintained at all. Stopping at the first nil is pretty confusing and surprising to me, it implies a loop over an array full of nils would not iterate even once which makes no sense. Javascript does it right: array length is the greatest numerical index in the object plus one. Abstraction seemed neat at first but completely fell apart in the details. Many such cases. Looks like a true vector type is a good idea after all. > Merged dict and array looks neat on syntactic level but really is pita to deal with. It doesn't have to be that way. An insertion ordered hash table also contains an array part, it's just that it's completely internal to the implementation. It behaves just like a normal hash table, but internally the keys hash to indexes in the array part. The order of the hashes is undefined but the order of the key-value pairs in the array part is defined to be the order they were inserted into the table. It's really neat and it seems to work really well. It behaves exactly like an array if used like one. It definitely isn't an array though: integer keys are not offsets, they are hashed like every other key type. This doesn't seem like a huge problem to me. The lack of this property seems to be the root cause of the complexity of Lua's tables. It's tempting to think of these insertion ordered hash tables as some kind of superset of arrays. Just like it's tempting to think of hypergraphs as supersets of graphs, of graphs as supersets of trees, and of trees as supersets of linked lists. I haven't learned of any cracks in this abstraction, at least not yet. The reason to prefer less general data structures always seems to be performance, not correctness. Offsetting a pointer is faster than hashing some bytes, indexing two arrays, comparing keys for equality and then offsetting a pointer.

commodoreboxer 2y ago

In my Lua/cbor use, what I did was use a custom tag (I think the ID was 0x7AB1E, for "TABLE") with an array type composed of a sub array and map. The array contains the array elements of the table up to the first nil, and the map contains the rest. Worked well enough for my use.