Re: Pure Lua tables
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: Pure Lua tables
- From: "Soni L." <fakedme@...>
- Date: 2017年10月15日 16:35:55 -0200
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.