lua-users home
lua-l archive

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


Hello Philippe !

Can you point out an implementation of the btree you describe preferably as a C library ?

Cheers !

On 24/7/20 6:53, Philippe Verdy wrote:
Anyway, in other applications outside Lua, I've completely zapped the use of hashtables with a static large number of BUCKETS in the root page, replacing it by b-trees using much smaller pages with fixed size. You get the benefit of more compaction, a natural ordering for sequential access, fast random access, no longer any worst case of long collision lists, and much more efficient memory management. And you don't need to tweak into separating an array part and an hashed part, you get both simultaneously with pages that are small sorted arrays, and still the support for hashes when necessary. And data in the btree can also be compressed by not relegating the common prefixes in every node of the page.

That's what all modern databases do for their storage on indexed tables. B-trees are not so complicate, and they still maintain very good data locality. They are excellent for performance, and very economic in terms of storage space which is autoadaptative.

I' m convinced that all Lua tables could be implemented using a single b-tree, whose pages can also be stored in a single array, resizable on demand if more pages are needed. 

Le ven. 24 juil. 2020 à 06:41, Philippe Verdy <verdyp@gmail.com> a écrit :
If that code is scrappy, then why the Lua documentation fully specifies the syntax of table constructors using keys that can be arbitrary expressions? For now the syntax is fully documented, since long, but it has NEVER worked reliably, never been portable, and extremely sensitive to the implementation of tables, that has changed multiple times.

It's caused by the fact that the existing implementation, while trying to optimize the storage by segregating an array part and an hashed part, has NEVER specified its own invariants. And not determining the assignment order is still a flaw, even if the table has only a single hashed part for everything.

This is a clear incoherence between what is fully documented (the syntax of table constructors can have arbitrary key _expression_ with arbitrary non-nil datatype) but the implementation has NEVER supported it correctly. 

Le jeu. 23 juil. 2020 à 22:46, Andrew Starks <andrew@starksfam.org> a écrit :


> On Jul 23, 2020, at 12:56, Philippe Verdy <verdyp@gmail.com> wrote:
>
> Beside obviously funny code like {1, [1]=2}, the issue is more serious with this code, not created just for fun by hackers:
>
> { [k(1)] = v(1), [k(2)] = v(2) }

I can’t tell your tone through email but this seems like a lot of arm waving about the crappy code that programmers can write. If someone showed me this code in production, without tons of comments or proof of prior sanity checks, I would throw up into my mouth a little. It’s just crappy code.

Lua is a scripting language, but it’s unique because it’s so tiny and simple. It has well documented undefined behavior where other languages give you guarantees about order and errors when it thinks you’re doing something stupid.

It’s fine. Just because you can do breathtakingly dumb things with it, doesn’t mean you can’t write correct code and be productive with it.

You can keep waving your arms around but there isn’t any evidence of this being a real problem.

-Andrew Starks