Re: C++: Why do we nreverse CLASSTYPE_TAGS

[Mike Stump <mrs at apple dot com>]

On Monday, March 24, 2003, at 12:17 PM, Matt Austern wrote:
> 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.

While wild ass guesses are fairly common, they can be dangerous.  I put 
in a hash of an often used data structure and noticed a massive 
slowdown.  The slowdown was caused in part by the bzero cost in 
clearing the hash table itself.

The right answer is to perfect your ability to measure (use the time 
stamp register on x86 to drive timevar or some such), and then just 
measure the tradeoff on a `normal' processor and use it.  This is far 
better than just using the answer of 10.  You may have to create a 
synthetic testcase to measure it.  If you plot 0, 1, 2, 3, 5, 7, 9, 10, 
15, 20, 25, 35, 50, 75, 100 and see where things come out, you can then 
be a little more confident that the choice was the right one.