lua-users home
lua-l archive

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


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 <sunshilong369@gmail.com> 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 <sharpobject@gmail.com> 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 <sunshilong369@gmail.com> 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