Passing enums efficiently (string atoms)

[petrihakkinen]

I'm thinking about how to efficiently pass enums from Lua to C++. The best option seems to be string atoms:

1. At startup, generate unique atom for each possible enum string. Store the atoms in global string->atom hash map.
2. Register 'useratom' callback which looks up the atom from the string->atom hash map.
3. When passing an enum from Lua to C++, check the atom of the input string and map it back to native enum value.

I'm worried about step 2 as that will increase the cost of all string creations, which could negate most of the gains of this optimization, especially in apps that create (lots of) new strings at runtime.

It feels redundant that both Luau and the useratom callback compute a hash for new strings, so I'm wondering could the internal string hash be exposed as an argument to the callback instead? The host would have no way to use the hash for other purposes, so exposing the string hash should be safe I think.

Another option would be to expose string hashes fully to the host:

unsigned int lua_stringhash(const char* str, int len);  // computes the hash of given string
const char* lua_tostringhash(lua_State* L, int idx, unsigned int* hash); // returns the string and hash at given slot

This would be even faster: the useratom callback overhead would be gone completely and the host could just compute the hashes of all possible enum values upfront and use the incoming string hash as search key in step 3.

What do you think?

[zeux]

The atoms give you an opportunity to only compute the association between string and enum once though. Exposing the hash still requires a hash based lookup, whereas with atoms you can simply index into an enum vector using the atom index. I'd recommend using the atoms - the extra overhead is generally negligible in our experience. If it needs to be mitigated then for example atom callback can filter strings based on their length as min/max enum length is known apriori.

fwiw in Roblox we represent enums as userdata that's part of a global table, e.g. Enum.Foo.Bar; this is where imports are super useful because the cost of the lookup evaporates at runtime.

[petrihakkinen]

Sorry, I'm a bit swamped with other work but here are some quick comments:

It's true that later versions of Lua don't compute hash for very long strings. In this case though it would be ok to pass 0 as the hash to the useratom callback. The atom look up algorithm in the callback has to be resilient to hash collisions anyway, and truly long strings for enum values don't make sense... Note that removing the hash computation likely incurs other costs at runtime. Very long strings may be duplicated and string equality comparisons become more branchy.

Hash randomization: this has the downside of making benchmarking and debugging harder because they add noise, and many applications don't need protection against DoS, so I suggest adding a compile flag to luaconf for disabling that feature. In case of multiple VMs and hash randomization, a simple fix would be to add lua_State* argument to the useratom callback. This way the string->atom hashmap could be built per state using state specific hashes. Actually I recommend doing this in any case, because it would be much cleaner to store the hash map details to some per state context instead of some global variable shared by all VMs (in our case, some VMs have completely different set of enums/atoms). I noticed this when I was playing around with the atom API.

Note that lua_stringhash function would not be strictly needed (although convenient). After initial state creation I can push all enums as strings to the Lua stack which would trigger the atom callback, where I build the hash map using the provided hashes. Later at runtime when the hash map is already built, I can use the hashes provided to the callback to convert strings to atoms. That's the theory at least, I haven't tested this in practice yet.

I agree a proof of concept demoing the benefits would be the next logical step. I can probably work on it this week.

[petrihakkinen]

p.s. I don't want to sound pushy, but if you have some time at some point, could you check out these two small pull requests, please? The vec fastcall constructor would be a clear win for us and probably all other users of 4-wide vectors, and the missing state argument from userdata destructors is an issue I've not found a good workaround yet (other than adding the lua_State* param). I can take "no" as an answer, if you feel there's something dubious with the changes :)

#510
#511

[zeux]

Re: your hash comments - I'm bringing this up to highlight that some of these API changes are highly coupled with the internal implementation, not to suggest that we have specific plans to change this right now (we know of the downsides of hash randomization which is why we haven't pursued it yet). Which is a good reason to try to minimize the API changes here if any, as all of them may or may not be invalidated in the future. Eg yes, passing 0 may be reasonable if hash isn't computed only rarely, but what if it's not computed for short strings either? :) That would likely lead to a significant regression in performance for a caller that expects a well distributed hash most of the time.

Btw one downside of lua_State* arguments, which actually applies to your destructor change as well, is we're starting to gain uncertain semantics in parts of the API as to what you actually can do with the state argument. I'm not sure if there's a good way to clarify this; for example, any stack manipulation from the atom callback (and possibly GC callback, unsure) is likely incredibly unsafe; any allocation from either is a latent bug. Both can be used to get lookaside info via lua_getthreaddata() without issues. Registry access in the form of lua_unref works... lua_getref may or may not be fully safe in GC context, and is definitely unsafe in atom context as it mutates the stack.

And yeah the PRs will be looked at, I was on vacation last week and am currently recovering from cold, I've asked someone from the team to take a look or may get to them myself later this week depending.

[petrihakkinen]

You're right about the danger of adding the lua_State* argument. I didn't think of that.

In case the hash is entirely dropped at some point, the best option in that case would probably be to remove the hash argument too. In my opinion breaking changes should not be feared if they improve things in general and they help propel the project forward.

No rush with the PRs. Get well soon!

[petrihakkinen]

Finally had time to test this optimization in practice. You're right, the gains are pretty much insignificant. Creation of new strings is typically rare and rehashing is not that expensive because string data is probably already loaded into cache. I guess it could be possible to write a custom benchmark that shows some speed up in some specific case (e.g. generating new strings in a loop), but then again almost anything can be proven like that :)

[zeux]

Just a quick note that 0.536 changes useratom callback behavior (behind a flag for now) to be called when the atom is requested, instead of when the string is created. The atom is still cached, but this usually results in a significant reduction in useratom calls since only strings that are eventually used for reflection purposes by the host get the atom computed.

[petrihakkinen]

Ooh, this is very nice! Thanks!