2002.10.29 ~01 Bring back hashtable to q3asm-turbo?
Just now I bothered looking at the numbers related to q3asm-turbo's data
structures. For my mod, the hashtable q3asm-turbo had these numbers:
Symbol hash: 17819 nodes, longest chain = 45, mean non-empty = 9.320
Opcode hash: 95 nodes, longest chain = 3, mean non-empty = 1.484
The Bal.Bin.Tree implementation has these numbers:
Symbol tree: 17819 nodes, tree height = 19
Opcode tree: 95 nodes, tree height = 10
Export tree: 26515 nodes, tree height = 21
In the optimal case the symbol tree would have a height of 15 (log2 of
17819), and the opcode tree would have height of 7. The height of the
tree represents worst case time for searching.
In the hashtable implementation, the longest chain indicates worst-case
time for search, and the mean average roughly corresponds to mean
(average) search time. Within each chain in the hashtable, though,
sorting is done by linear-time insertion sort, and thus the major
portion of cost. The thing is that the opcode hash has a longest chain
of 3. This is next to squat (almost constant) for sorting and
searching. Meanwhile, the opcode tree has a height of 10, worst case
searching is visiting 10 nodes. In the tree, only 15 opcodes would be
reachable in 3 hops, while any opcode in the hashtable can be reached,
guaranteed, within 3 hops.
The question here is if I should resurrect the hashtable specifically
for the opcodes. Trees have major wins in the large-amount-of-data
department (due to reduced insertion costs), but hashing seems to win in
small-sets-of-data.