Could somebody explain "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined" in more detpth?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Could somebody explain "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined" in more detpth?

孙世龙 sunshilong
How to comprehend "due to the way that Lua implements tables, the
order that elements appear in a traversal is undefined".

Could somebody explain that in more depth?

Best regards
Sunshilong
Reply | Threaded
Open this post in threaded view
|

Re: Could somebody explain "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined" in more detpth?

Robert Burke
Hello,

"it's undefined" means "no guarantees are made about the order." The hope is that people will not rely on the order, then the implementation can be changed in the future without anyone's code breaking, because they did not rely on the order.


On Sun, Oct 11, 2020, 17:37 孙世龙 sunshilong <[hidden email]> wrote:
How to comprehend "due to the way that Lua implements tables, the
order that elements appear in a traversal is undefined".

Could somebody explain that in more depth?

Best regards
Sunshilong
Reply | Threaded
Open this post in threaded view
|

Re: Could somebody explain "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined" in more detpth?

孙世龙 sunshilong
>>How to comprehend "due to the way that Lua implements tables, the
>>order that elements appear in a traversal is undefined".
>>Could somebody explain that in more depth?
>"it's undefined" means "no guarantees are made about the order."
>The hope is that people will not rely on the order, then the
>implementation can be changed in the future without anyone's code
>breaking, because they did not rely on the order.
Thank you for your clarification.
Sorry, maybe I mislead you.

The sentence aforementioned is quoted from <<Programming in Lua>>(Page 38).
Here is the sentence followed [emphasise mine]:
The same program can **produce different orders each time it runs**.
The only certainty is that each element will appear once during
the traversal.

Why the same program may produce different orders each time it runs?

On Sun, Oct 11, 2020 at 6:12 PM Robert Burke <[hidden email]> wrote:

>
> Hello,
>
> "it's undefined" means "no guarantees are made about the order." The hope is that people will not rely on the order, then the implementation can be changed in the future without anyone's code breaking, because they did not rely on the order.
>
>
> On Sun, Oct 11, 2020, 17:37 孙世龙 sunshilong <[hidden email]> wrote:
>>
>> How to comprehend "due to the way that Lua implements tables, the
>> order that elements appear in a traversal is undefined".
>>
>> Could somebody explain that in more depth?
>>
>> Best regards
>> Sunshilong
Reply | Threaded
Open this post in threaded view
|

Re: Could somebody explain "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined" in more detpth?

Philippe Verdy-2
Because the way a table is built may depend on other factors like the allocation of other objects and the actions performed by the garbage collector, which may compact the internal representation separately (This would not invalidate the currently open iterators, but may affect the way a new iterator on the same table could operate, as it may start iterating on another item, or could traverse the internal tree in different branches structured differently; notably because a tree-like representation may contain pages randomly ordered by hashes, the iterators keeping only a "snapshot" of the current pages being traversed).
Lua does not formally define how tables are structured, and even the existing implementation does not document the two parts of the table (indexed by integer, or hashed), and these two parts may be restructured at any time by the garbage collector moving some items from one part to another (and it can do that safely when the table has no iterator currently open on it).
You may also have background threads or coroutines adding and removing temporary items in the table: if the thread/coroutine is yielded to another, they can change the backing store, the total number of nodes could increase or be reduced only in free nodes, while not changing the number of used nodes. As well a compactor may change the internal hashing functions depending on the fill rate or total size allocated, it could rebuild the collision lists.
There's already been multiple implementations of tables in Lua, and the specs allow for new implementations. The only contract is that no items should be iterated twice in the same traversal, and that all items in the table should be iterated (as long as the set of items is not extended or reduced, i.e. the set of distinct keys; note that this last set is unordered, this is just a set).
The same could apply to other languages using hash tables for their collections (Java, PHP, standard C++ libraries, Javascript, C#, Python, PostScript, Forth, etc., ... or filesystems for files or subdirectories in a directory). It is important to know how iterators are implemented and what they keep in their current state to respect the contract.



Le dim. 11 oct. 2020 à 13:41, 孙世龙 sunshilong <[hidden email]> a écrit :
>>How to comprehend "due to the way that Lua implements tables, the
>>order that elements appear in a traversal is undefined".
>>Could somebody explain that in more depth?
>"it's undefined" means "no guarantees are made about the order."
>The hope is that people will not rely on the order, then the
>implementation can be changed in the future without anyone's code
>breaking, because they did not rely on the order.
Thank you for your clarification.
Sorry, maybe I mislead you.

The sentence aforementioned is quoted from <<Programming in Lua>>(Page 38).
Here is the sentence followed [emphasise mine]:
The same program can **produce different orders each time it runs**.
The only certainty is that each element will appear once during
the traversal.

Why the same program may produce different orders each time it runs?

On Sun, Oct 11, 2020 at 6:12 PM Robert Burke <[hidden email]> wrote:
>
> Hello,
>
> "it's undefined" means "no guarantees are made about the order." The hope is that people will not rely on the order, then the implementation can be changed in the future without anyone's code breaking, because they did not rely on the order.
>
>
> On Sun, Oct 11, 2020, 17:37 孙世龙 sunshilong <[hidden email]> wrote:
>>
>> How to comprehend "due to the way that Lua implements tables, the
>> order that elements appear in a traversal is undefined".
>>
>> Could somebody explain that in more depth?
>>
>> Best regards
>> Sunshilong
Reply | Threaded
Open this post in threaded view
|

Re: Could somebody explain "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined" in more detpth?

Ką Mykolas
In reply to this post by 孙世龙 sunshilong
Well, with different Lua version it MAY change the order, as far as I read this. Do not remember the implementation details at the moment thought.

On Sun, Oct 11, 2020, 13:41 孙世龙 sunshilong <[hidden email]> wrote:
>>How to comprehend "due to the way that Lua implements tables, the
>>order that elements appear in a traversal is undefined".
>>Could somebody explain that in more depth?
>"it's undefined" means "no guarantees are made about the order."
>The hope is that people will not rely on the order, then the
>implementation can be changed in the future without anyone's code
>breaking, because they did not rely on the order.
Thank you for your clarification.
Sorry, maybe I mislead you.

The sentence aforementioned is quoted from <<Programming in Lua>>(Page 38).
Here is the sentence followed [emphasise mine]:
The same program can **produce different orders each time it runs**.
The only certainty is that each element will appear once during
the traversal.

Why the same program may produce different orders each time it runs?

On Sun, Oct 11, 2020 at 6:12 PM Robert Burke <[hidden email]> wrote:
>
> Hello,
>
> "it's undefined" means "no guarantees are made about the order." The hope is that people will not rely on the order, then the implementation can be changed in the future without anyone's code breaking, because they did not rely on the order.
>
>
> On Sun, Oct 11, 2020, 17:37 孙世龙 sunshilong <[hidden email]> wrote:
>>
>> How to comprehend "due to the way that Lua implements tables, the
>> order that elements appear in a traversal is undefined".
>>
>> Could somebody explain that in more depth?
>>
>> Best regards
>> Sunshilong
Reply | Threaded
Open this post in threaded view
|

Re: Could somebody explain "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined" in more detpth?

Francisco Olarte
In reply to this post by 孙世龙 sunshilong
Sunshilong.

On Sun, Oct 11, 2020 at 1:41 PM 孙世龙 sunshilong <[hidden email]> wrote:
> The sentence aforementioned is quoted from <<Programming in Lua>>(Page 38).
> Here is the sentence followed [emphasise mine]:
> The same program can **produce different orders each time it runs**.
> The only certainty is that each element will appear once during
> the traversal.
>
> Why the same program may produce different orders each time it runs?

I do not have the whole program handy, so I do not know the exact
answer. But if all the program does is fill a table and then traverse
it it may be due, typically, by randomization of hashes ( you generate
a random value at program/lua state start and use it in the generation
of hash values, a classical mitigation of denial of service attacks
similar to salting passwords ).

It may be due to other reasons. In general this hints you on not
relying on table enumeration order.

Francisco Olarte.
Reply | Threaded
Open this post in threaded view
|

Re: Could somebody explain "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined" in more detpth?

Luiz Henrique de Figueiredo
In reply to this post by 孙世龙 sunshilong
> How to comprehend "due to the way that Lua implements tables, the
> order that elements appear in a traversal is undefined".

Abstractly, a Lua table is a *set* of key-value pairs and the elements
of a set have no intrinsic order.

Concretely, a Lua table is implemented (at least in part) as a hash
table and the entries in a hash table might not have a fixed order
(for instance, an implementation might move the most recent accessed
entry in a collision list to the front of the list).
Reply | Threaded
Open this post in threaded view
|

Re: Could somebody explain "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined" in more detpth?

Philippe Verdy-2
Reordering collision lists must however not impact the traversal of currently open iterators (but it is legal to reorder iterators that have still not reached a hash slot or have already processed it).
This means that the iterator just needs to keep a local copy of the hash chain, or that the garbage collector can duplicate the existing chain in the background, allowing existing iterators to continue working on their shadow copy (this copy left referenced by existing open iterators will be garbage-collected later, one the existing iterators will no longer need it, as it will no longer be accessed by new iterators using the new chains).
This can even occur in a single threaded program without any coroutine (in fact there will still be a system-level coroutine for the garbage collector itself, that the single-threaded app will use launch at any time during a blocling call, including in the "next()" operation of its iterator, which is not forbidden to change the memory layout and invoke the allocator or collector).
So nothing prevents two successive iterators traversing the *same* table, that has not even changed its set of used keys, to return key/value pairs in a different order of keys.
As well nothing prevents integer keys to be moved between the indexed array part and the hashed part (in both directions), notably to fill gaps left in the indexed part or truncate the indexed part that has too many holes by moving some items to the hashed part, possibly resizing both parts.

Le dim. 11 oct. 2020 à 22:14, Luiz Henrique de Figueiredo <[hidden email]> a écrit :
> How to comprehend "due to the way that Lua implements tables, the
> order that elements appear in a traversal is undefined".

Abstractly, a Lua table is a *set* of key-value pairs and the elements
of a set have no intrinsic order.

Concretely, a Lua table is implemented (at least in part) as a hash
table and the entries in a hash table might not have a fixed order
(for instance, an implementation might move the most recent accessed
entry in a collision list to the front of the list).