Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Matt Austern <austern at apple dot com>]

On Monday, March 24, 2003, at 12:04 PM, Gabriel Dos Reis wrote:
> | How expensive is the hash function?  Unless it's pretty extreme, I'd
> | be surprised if you needed to get all the way to 10 to get a win.
>
> Actually, we have the hash function for free for the following reason:
>
>    by caching the hash value, as suggested in a previous patch, we
>    don't need to recompute it when we map a name to the associated
>    type.  That hash is already computed as a result of calling
>    get_identifier().

If the hash function is free, then it's hard to imagine that a hash
table would ever be substantially more expensive than a list.  The
costs of a hash table are one mod or the moral equivalent (to get from
the hash function to a bucket index) and one extra pointer indirection
(to get to the head of the bucket).  How many linked list nodes to you
have to chase through to make up for a single integer division?  Not
very many, I'd think.

			--Matt