Re: Could metatables easily be faster?

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