Re: Could metatables easily be faster?

[Lars Müller <appgurulars@...>]

No, you are wrong. You're misunderstanding the semantics of the length operator. Just because the length operator returns some value doesn't mean all indices up to that value are in the array part; in fact Lua sometimes searches the hash part to find a "boundary", which is responsible for the length operator being so slow (as opposed to constant time in other languages).

The only case in which you're pretty much guaranteed that Lua uses the list part is if you manually set keys from 1 to n, in that order, as Lua can simply write to the list part and extend it if necessary (each operation is just appending to the list part).

This breaking change is particularly delicate as it would require breaking all current uses of metatables and using your arbitrary numeric constants, which would have to pollute the global environment. As others have pointed out, using sequences as metatables would fail. And in terms of code quality, this would be rather dirty: Suddenly metatables - "class" tables sometimes used as method tables - would have a "length", determined by the metamethods they set!?

The benefit of this is merely replacing one hash lookup, which is pretty fast if the table only contains the metatable fields (i.e., meta- and methodtable are separated) and if the string is interned (which it is as a constant string in the loaded Lua sources), by an array lookup. The burden of proof that this would yield any measurable improvement lies on you.

On 18.05.22 20:04, Mason Bogue wrote:

Sean:

> But if I only use __index and __tostring, that is no longer a Lua sequence (since index 2 is missing) and thus, goes into the hash portion.

This is wrong:
masonbogue@masons-MacBook-Air ersa % lua
Lua 5.4.3  Copyright (C) 1994-2021 Lua.org, PUC-Rio
> t = {1, nil, 3}
> #t
3

> Right now, to declare the metatable you use the type luaL_Reg, which has strings for keys

This is a feature designed specifically to assist creating metatables under the current semantics. If the semantics were altered, a new struct could easily replace it. I'm not denying that making this change would require modifying the API, but historically Lua has been willing to make breaking changes that improve the language.

>This also assumes that other functions won't be part of the metatable.

No, it doesn't. Of course, they won't be sped up, but I am also not suggesting that this change will lower your tax bill or make your knees stop hurting, either.

> out of order setting of the table won't result in the use of the array portion.

Oh, really? I believe a well-designed C API would be capable of sorting an array, but regardless:

masonbogue@masons-MacBook-Air ersa % lua
Lua 5.4.3  Copyright (C) 1994-2021 Lua.org, PUC-Rio
> t = {}
> t[4] = 4
> t[3] = 3
> t[2] = 2
> t[1] = 1
> #t
4

At worst, you regress to the old behavior, which is apparently acceptable. You can also simply place dummy functions to force array behavior, if desired (and I suspect it would be), such as __newindex = rawset.

Oliver:

> Please keep in mind that the array part of the table may not exist at all

Naturally, I am only interested in the case where the integer indices are treated as an array. Since it is already common in Lua to manage table creation to ensure that the array acts like an array when you want it to, I don't see why this would be a problem.

> Did you make a benchmark testing access times for integers and short strings?
Such a benchmark would require a substantial time investment, while someone familiar with Lua's implementation may highlight a problem which is not performance-dependent. It didn't seem reasonable to spend time putting together a patchset if it might be useless anyway, but if no other problems are identified in this thread, I might do so.

Best,

Mason

On Wed, May 18, 2022 at 1:19 PM Oliver Kroth <oliver.kroth@nec-i.de> wrote:

Hi Mason,

looking onto the source code
http://www.lua.org/source/5.4/ltable.c.html#luaH_getint ,
I am not that sure that it would save much time.
Please keep in mind that the array part of the table may not exist at all, and all integer indexes are actually in the has table part

Did you make a benchmark testing access times for integers and short strings?

Regards,

Oliver

Am 18.05.22 um 17:15 schrieb Mason Bogue:

Hi,

Currently, as I understand it, the metatable of a Lua value is a Lua table with string keys "__index", "__add", "__tostring", etc. These string keys are stored in a hash table and incur a hash-table lookup whenever accessing a metatable, i.e., if I write something like

t = {}

setmetatable(t, {__index = {a = function() return "b" end}})

then upon calling t:a(), Lua will perform three hash-table lookups: one check for 'a' in 't', one check for __index in t's metatable, and finally a check for 'a' in the method table.

But accessing __index by a string lookup in a hash table seems unnecessarily complicated, when for metatables we are always interested in the same 20 or so keys. Instead, Lua could simply define global values:

__index = 1

__newindex = 2

__tostring = 3

-- and so on

and then we write the metatables like this:

t = {}

setmetatable(t, {[__index] = {a = function() return "b" end}})

Now we have exchanged a hash-table lookup for an array lookup. The code is not really more complicated; you have to type only two more characters. Plus, many people will use an OOP library that abstracts away the whole metatable creation, so they wouldn't notice any difference. Practically everything using metatables immediately gets faster. Other than backwards compatibility, I'm having trouble thinking of a downside.

In fact, if I understand correctly, Lua already stores a list of metatable keys, looks up the key by an index, and then does a hash lookup for that key in the metatable:

const TValue *luaT_gettmbyobj (lua_State *L, const TValue *o, TMS event) {
  Table *mt;
  /* define mt (omitted for brevity) */
  return (mt ? luaH_getshortstr(mt, G(L)->tmname[event]) : luaO_nilobject);
}

Obviously the last line should be faster if it were just:

  return (mt ? luaH_getint(mt, event) : luaO_nilobject);

...right?

Best,

Mason