Re: Pure Lua tables

> It'd seem that when the hash part is empty, it just returns luaO_nilobject. So it shouldn't really matter?

Oh, I suppose that's true. luaH_set() creates the key if luaH_get() returns luaO_nilobject.

Another problem I've realized with my code is that (t->sizenode == 0) doesn't imply that the table t is empty! sizenode contains the power of 2 of the size, so if (sizenode == 8) then the hash table has size 256. And so if (sizenode == 0), the hash table has size 1. So hash tables always have at least 1 element. If the table is empty, it contains the `dummynode_` that is defined in ltable.c.

So that else-if condition should be `else if (!isdummy(t)) {`. Which still is a really fast check to do. (isdummy(t) expands to (t->lastfree == NULL).)

(Sorry, this has been me trying to explain the Lua code before fully understanding it. I hope I'm not spreading too much misinformation...)

On Sun, Oct 15, 2017 at 12:35 PM, Soni L. <fakedme@gmail.com> wrote:

On 2017-10-15 04:29 PM, Jeremy Ruten wrote:

Disregard the last part about changing the luaH_getint() code. I just realized luaH_getint() is used by luaH_setint() to find the position in the hash table to set a value, so luaH_getint() does need to do a search in the hash part every time.

Even if the hash part is empty?

It'd seem that when the hash part is empty, it just returns luaO_nilobject. So it shouldn't really matter?

Have you tried changing it and then running the Lua tests?

On Sun, Oct 15, 2017 at 12:23 PM, Jeremy Ruten <jeremy.ruten@gmail.com <mailto: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
<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 <mailto: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
<mailto: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
<mailto: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.
>
>

--
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.