Re: Pure Lua tables

On Sun, Oct 15, 2017 at 12:23 PM, Jeremy Ruten <jeremy.ruten@gmail.com> wrote:

> Only if it is not in there does control flow reach a
hash computation.

I think Soni's question is how to prevent it from doing that hash computation.

From the C API, you can call lua_createtable(L, 256, 0) to create a table with an array part of 256 elements and an empty hash part. Then any calls to luaH_get() with an int in the range 1-256 would be handled by the array part only.

Unfortunately you can't use lua_createtable() or anything like it from Lua code. There are some ugly workarounds described here: http://lua-users.org/wiki/TablePreallocation

As for why Lua does it that way, I guess it's because searching for an integer key in an empty hash table isn't very expensive. And usually tables will be filled with values.

So what you're proposing is changing the 'else' in luaH_getint() to maybe 'else if (t->sizenode > 0)'? That doesn't seem like a bad idea, if I understand the code correctly. (I'm still learning the Lua internals myself.)

const TValue *luaH_getint (Table *t, lua_Integer key) {
/* array part */
if (l_castS2U(key) - 1 < t->sizearray)
return &t->array[key - 1];
/* hash part */
else if (t->sizenode > 0) {
/* ...snip... */
}
return luaO_nilobject;
}

On Sun, Oct 15, 2017 at 12:00 PM, Dirk Laurie <dirk.laurie@gmail.com> wrote:
I suppose you mean luaH_getint which is where the switch sends you for
an integer key.

Read carefully.

There are two lines that check whether the index is in the range of
the array part. Only if it is not in there does control flow reach a
hash computation.

2017-10-15 19:05 GMT+02:00 Soni L. <fakedme@gmail.com>:
>
>
> On 2017-10-15 02:58 PM, Dirk Laurie wrote:
>>
>> 2017-10-15 17:43 GMT+02:00 Soni L. <fakedme@gmail.com>:
>>>
>>> I'm reading the Lua code, and it seems that Lua always checks the hash
>>> part,
>>> even for tables that don't use it. Why is this?
>>
>> That's not how I read the code. Here are the comments and return
>> statements of luaH_next.
>>
>> /* find original element */
>> /* try first array part */
>> /* a non-nil value? */
>> ...
>> return 1;
>> }
>> /* hash part */
>> /* a non-nil value? */
>> ...
>> return 1;
>> ...
>> return 0; /* no more elements */
>>
>> It's quite possible to return without reaching the code dealing with
>> the hash part.
>>
>
> Look at luaH_get. e.g. t[1] always checks hash part which does have a cost.
> the only way to avoid that cost is to fill the array part: if you have 256
> possible values, you need to fill t[1] to t[256]. and ofc t[0] always goes
> to the hash part so you also need to shift by one if 0 is a valid index.
>
>
> --
> Disclaimer: these emails may be made public at any given time, with or
> without reason. If you don't agree with this, DO NOT REPLY.
>
>