Re: stringtable and Table Hashing

[Wim Couwenberg <debosberg@...>]

>
http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pd/rpb013.pdf

Although Knuth gives this reference for "Brent's
variation" (in Sorting and Searching) it is not so
relevant for Lua's implementation, I think.  But
ltable.c is an excellent reference!  ;-)

About the special string hash table: Lua uses a string
object (TString) to represent strings and maps equal C
strings to the *same* TString.  To do this it uses the
special string hash table with ordinary C strings
(i.e. const char* + length) as keys and TString* as
values.  The "usual" hash table can not be used
because a C string is not a Lua type that can occur as
a key (or value) in such a table.

Testing two TStrings for equality now takes just a
simple pointer comparison and not a full memcmp call. 
This is a huge gain because strings are very common as
table keys (almost all identifiers in a Lua program
end up as keys in a table.)

--
Wim



	
		
__________________________________
Do you Yahoo!?
Friends.  Fun.  Try the all-new Yahoo! Messenger.
http://messenger.yahoo.com/