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.