On Thu, Jan 1, 2015 at 11:55 AM, Piaget Modeler via AGI <[email protected]> wrote: > So, my question is, are there any known optimizations to this problem of > resolving > function names with packages?
Normally you would look up identifiers in a hash table. On older hardware, the most expensive step would be computing a hash of the string, something like (hash = (hash + next_letter) * C) for some large odd constant C. In newer hardware, the most expensive step is random memory access. To speed lookup, I align the hash table on a cache line boundary (usually 64 bytes) and test hash, hash^1, hash^2, hash^3... using XOR rather than addition to stay within the cache line as long as possible. Some compilers use "perfect" hash functions for reserved words, where C is adjusted experimentally in advance to find a table with no collisions. -- -- Matt Mahoney, [email protected] ------------------------------------------- AGI Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/21088071-f452e424 Modify Your Subscription: https://www.listbox.com/member/?member_id=21088071&id_secret=21088071-58d57657 Powered by Listbox: http://www.listbox.com
