lua-users home
lua-l archive

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


I don't suppose sneaking in some kind of ridiculous key name that includes null characters and other things that are vastly improbable for a real Lua user to use (something like "__detail.do.\0.not.touch\xE2\x98\xA2.size") for when I push the table and then pop the table, and using that MAYBE as a shortcut if it's present, and otherwise falling back to iterating until I hit a `nil` might be worth it...?

On Thu, Aug 18, 2016 at 9:17 PM, Coda Highland <chighland@gmail.com> wrote:
On Thu, Aug 18, 2016 at 5:48 PM, ThePhD <jm3689@columbia.edu> wrote:
> Well, I looked into this deeper after everyone gave me the conventional
> wisdom to NOT depend on `lua_next`'s iteration order and pray for no
> breaking changes.
>
> It turns out that the correct wisdom -- iterate using an index value --
> seems to also be the most performant wisdom from the C++ or C side. [1]
> compares the performance of calling `lua_next()` in a while loop and
> assuming it iterates in the right order, pushing a table and calling
> `lua_geti` with the indices (and knowing the size and indices before hand),
> and the other measures the doing a lua_pushinteger + lua_gettable. Measured
> in a computer with an i7 Intel chip, lots of ram, Windows 10, Lua 5.3.3
> compiled as a DLL.
>
> Interestingly, the pushinteger + gettable method is about equal to the
> lua_next implementation. So, for Lua 5.2 and lower, since there's no
> lua_geti intrinsically built into the API, the correct way is equal in
> performance to the UB way.
>
> lua_geti was introduced in Lua 5.3 I believe, and it correctly adds a very
> heavy performance gain for the lookup (sorry LuaJIT and Lua 5.2 users,
> you're not gonna get the benefits here).
>
> My only problem is: how do I know how big the array part is? I could use
> `#t` or fight with its equivalent in the Lua 5.1/2/3 code, which is either
> lua_objlen or lua_rawlength (I can't remember which). Right now I have a
> fixed size at compile-time... I could just keep iterating integer keys from
> 1 to infinity until I hit a snag, but that seems less than useful (and
> doesn't allow me to pre-allocate the size to save performance).
>
> Any suggestions for getting the length, or is lua_objlen/rawlength (or
> whatever it is for each version of Lua) good enough?
>
> [1] - https://dl.dropboxusercontent.com/u/17644642/lua%20iteration.html
>
> On Thu, Aug 18, 2016 at 2:41 PM, nobody <nobody+lua-list@afra-berlin.de>
> wrote:
>>
>> On 2016-08-18 19:20, Ross Berteig wrote:
>> > Honestly, the cost of writing a loop over integers from 1 to #t is so
>> > low (even in C) that you should just do that rather than assume that an
>> > undocumented behavior will work under all conditions.
>>
>> That reminds me of the "dual" situation that I once found myself in:
>>
>> Question: How do you iterate just the "non-array part" (i.e. all entries
>> excluding those with integer keys 1,2,... up to the first 'nil')?
>> (Assume that the "array part" contains millions of values (already
>> traversed in order by numeric for loop), and the "non-array part"
>> contains optional metadata, i.e. 0 or just a few values, that you now
>> want to inspect.)
>>
>> Answer:  You don't.  You use two tables, one for the array-like part,
>> one for the metadata, and place one inside the other at a "well-known"
>> key (i.e. one that you can get without calling `next`).  The 56 byte
>> cost of the extra table is negligible.  (If the array part may be
>> smaller so that the memory matters, put the metadata in an optional
>> field in the array and check whether it exists or is nil.)
>>
>> Non-Answers:
>>
>>  *  Trying to jump over part of the next()-traversal by swapping the
>>     current key passed to next from 1 to #t.  Usually works, but can
>>     break horribly, for the same reasons previously mentioned in this
>>     thread.
>>
>>  *  Making the keys well-known by arithmetic coding tricks, e.g. store
>>     t[k]=v as t[i+0.25] = k, t[i+0.75] = v or just keep a list of keys
>>     at t[i+0.5] = k and store t[k] = v normally, for i=1,2,...
>>     Really cool but useless hack: costs 64 instead of 32 bytes per
>>     entry (=costs more starting at 2 entries), needs own iterator, ...
>>
>

The typical answer in Lua is to iterate until you hit nil, thus
signifying the end of the sequence. Using the length-acquisition
function is either O(n) or O(log n) (I forget which version switched
to O(log n)). If you need nil as a valid element in your array, heaven
help you, because this list will argue until eternity over what the
right way to handle that is.

/s/ Adam