lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

Lua has unique string type before 5.2.1 , all the strings is interning
for fast comparison .

Lua 5.2.1 add a new internal long string type because of hash DoS
attack , but short string is still interning. I guess the reason is
the performance of string comparison is very important to lua , string
interning can reduce the string comparison from O(n) to O(1).

I think if we can find another way to compare strings with O(1) , we
can use only one string type without interning.

We can add an unique 64bit id into TString struct , every time we push
a string into lua VM , allocate a new id to it . When we need compare
two strings, compare the id first. If id are the same, they are
equality, otherwise we compare the hash. If hash is also the same, use
memcmp.  And if the strings are equality, we can change the lower id
to the higher one.

For example, if we have two string A and B with the same value "Hello"
. At first , they have different id is 1 and is 2 . After
memcmp, we found A == B , so we can change = 2 . Next time, when
we need to compare A and B, we can just compare and , they
are the same, so we don't need memcmp .

I think it can simplify the implementation of lua, and we can share
the prototype of functions and const tables in multiple lua vm (with
minor modification).