Re: worst case time using hash-tables in Lua

Le ven. 15 mai 2020 à 21:18, Francisco Olarte <folarte@peoplecall.com> a écrit :

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.

Consider this code (which defines a single lexical scope:

local x = create_collectable_thing(1);

local y = create_collectable_thing(2);

local z = create_collectable_thing(3);

//...

return y

end

What is the "scope" of x and z ? they each start from their declaration to the "return", and would survive (would not be collectable while creating the second object, which also survices during the creation of the third object, and the first and second object would not be collected except at the return point where only objects referenced by x and z will be collected.

But the compiler CAN know that this "x" is not used after the line of its declaration, and CAN mark it immediately as collectable: the compiler KNOWS that x is not used after. It does the same for z; only y is not marked as collectable because the referenced object is returned and passed back to the caller....

I make then a difference between the lexical/syntaxic scope where a variable *may* be used by additional code (but the compiler knows the whole code of the block and can mark the effective scope of each varaible which is smaller than the lexical scope (this is exactly what Java does and most C/C++ compilers).

As well Java will reuse the storage location of variable x (no longer needed) for the variable z, so for the 3 local varaibles in lexical scope, it allocates only 2 places on the stack. A C/C++ will do the same for allocating registers by reusing registers no longer needed by any further reference.

What this means is that the compiler can consider the former sample as if it was:

local x = create_collectable_thing(1);

x = nil;

local y = create_collectable_thing(2);

local z = create_collectable_thing(3);

z = nil;

//...

return y

end

The compiler does not necessarily need to perform nil assignment in code, it can mark (including for the debugger) that the lifetime scope of varaibles x and z is terminated after their declaration line which is the only place where they occur. In fact, given that x and z are never reused, it can also remove the storage instruction and not allocate any local varaible for x and z as if it was:

create_collectable_thing(1);

local y = create_collectable_thing(2);

create_collectable_thing(3);

//...

return y

end

(i.e. discarding the return value of the created 1st and 3rd objects, which will still be created in the indicated order by performing the 3 function calls, because it may have other side effects even if their return value is ignored).

In this case, the 1st and 3rd object are immediately collectable after their creation and return of their creation function call, without having to first reach and starting to run the code of the return statement. So this is even more generic than just local variables as in this case above there's no local variable at all for the 1st and 3rd returned object which can still be collected earlier

Everything is know by the compiler which sees ALL the code inside the same lexical scope (there's no need to find any "end" or "return", jsut the need to determine that there's no other use before them). The compiler never compiles a partial scope line by line: this only occurs in an interactive interpreter (including in a debugger where one could modify the existing variables in scope during a debugger breakpoint) which would execute isolated statement using a permanent scope keeping all variables as it never knows if that variable will be used by a later intereactive statement.

If a debugger is used, it could load the Lua program as a script that it will compile without this optimization so that no local variables will be removed, their values will be kept; or the debugger can still load the optimized code, but will allow tracing inside the function by putting a break just after the instruction but before crossing the boundary where the scope of the varaible is lost and the object will be collected: the debugger can still inspect the returned value from the 1st call, even if it's not stored in any varaible by the traced code, but only if the breakpoint is between the 1st creation and the 2nd.

The debugger can no longer access the value of "x" later in the same block, as it is no longer accessible and its value may have been garbage collected: the local variable x for example is visible by the debugger, even if it is allocated nowhere and nothig is stored by any instruction in the bytecode. to do that, the debugger creates an internal reference of the return value at the position of the breakpoint, so the garbage collector will not collect it (as the garbage collector will see that the value is still referenced, may be not inside the traced code, but in some object of the debugger).

Typically, the debugger will control the garbage collector to instruct it to not collect any object that the debugger is bookkeeping (under instruction by the user of the debugger).