[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: A useful useless fact about Lua keywords
- From: Philippe Verdy <verdyp@...>
- Date: Tue, 14 Sep 2021 16:45:31 +0200
Hashing tables that have very few members is a waste of time, we can just store them in an array, avoiding also the extra indirection. Instead of hashing, you can perfectly keep a stable order with a very simple binary comparaison, when keys are also short, and even store thèse keys directly in the array. Keys in tables used for Lua reserved keywords are small in length and count of strings, and they are already internalized, leaning that you can just compare their internalized pointer as a simple integer, not needing any hash.
Even if that table is not sorted (by the bytes of each string, or by the internalized unique pointer for these few string constants), a simple full scan of the array (to search pointer equality)would be faster that using
For now Lua creates a hashtable for every table keyed by numbers not in integer sequence 1 to N or any other type, and an array for integers in sequence. That's arbitrary, and probably not the optimal choice. It could use one or two arrays for all small tables (with few keys, such as less than about 32).
As of Lua 5.4, there are no two keywords that share the same first and
last letter. There are some that start with the same two letters,
(else/elseif, repeat/return) but if we look at the first and last
letter they are unique. For example, the only keyword that starts with
"e" and ends with "f" is "elseif".
One application of this useless fact would be if one wants to build a
perfect hashing function for just Lua keywords. The hash function
wouldn't have to look at all the characters of the word; just the first
and last one should be enough.
and break do else elseif end
false for function goto if in
local nil not or repeat return
then true until while