Re: worst case time using hash-tables in Lua

[Francisco Olarte <folarte@...>]

Philipe:

On Fri, May 15, 2020 at 7:25 PM Philippe Verdy <verdyp@gmail.com> wrote:
>>  This is interesting. Can you be more specific? How can a local variable be collected if it is still in the scope?
> It could be garbage collected if the scope of the variable was more precisely analyzed (not just "lexically" where you may want to reuse its value by adding code within that scope, but by effective area of use in that lexical scope).

The problem with this approach is that in lua garbage collection may
USE the variable in the __gc. I'm fine with Lua optimizing this for
things which can be proven side effect free, but this cannot be done
by the compiler, unless it has all the code in scope.

> Unfortunately, there's no tracking of the last use in the Lua compiler, scopes are only lexical and local variables reside in the table of local variables until the full table for the lexical scope is removed.

Which, IMO, is a good things. If I want finer scopes I'll code it,
do/end are just 5 chars plus overhead. Having easy reasoning about my
resources lifetimes is a great advantage.

> One way to avoid this is to unset the variable value explicitly in the Lua code (i.e. setting these variables explicitly to nil where we no longer need their value), but this is error prone, and a programmer should not have to manage that explicitly in the source code.

Its a much used idiom in other language, like storing the pointer to a
dynamically allocated C++ value in a smart pointer and explicitly
deleting it when you are done and have something to do which could
benefit from it, but having the safety net of not having to it in
every code path because it will be freed on scoper.


> This automatic unsetting of unused variable could be made in the compiler itself (like what Java does for its class compiler: local varaibles are represented in an integer indexed array, and positions that are no longer needed can be reused for other local variables, as you can see if you look at the Java bytecode; this analysis also occurs in C/C++ compilers, still not in Lua).

I'm not too sure Java goes that trigger happy on unsetting variables,
given how tightly defined the memory model is. Especially on
references to variables with finalizers, which are not guaranteed to
be run, but I think are guaranteed to NOT be run before scope end.
Bear in mind Java and C++ have typed variables, so their compilers can
easily trace which ones are observable effect free.

> And the Lua compiler could even eliminate "dead code" trying to assign a value to a variable that is never reused later.

That's a slippery slope. You could say it can eliminate the call to
the creation functions. In lua letting a variable get collected is not
side effect free, so not a trivial operation. If it can prove it is,
let it do it, but given the flexibility of the language it can be
problematic. Not all programs use trivial content of the "just a
memory chunk" type on their variables.

Francisco Olarte.
_______________________________________________
lua-l mailing list -- lua-l@lists.lua.org
To unsubscribe send an email to lua-l-leave@lists.lua.org