Nonportable code in C++ support

[Esben Mose Hansen]

On Friday 15 February 2008 20:14:15 Matthew Woehlke wrote:
> Esben Mose Hansen wrote:
> > It wouldn't break. It's a hash function, it's going to get moduloed with
> > some smallish number anyway. The hash function just need a reasonable
> > chance to get different results for different pointers, fast. The latter
> > is the reason why I wouldn't bitshift it with size_t, even though those
> > bits would likely nearly always be zero.
>
> Isn't this a *really* good reason to strip the last couple bits? I.e.
> because otherwise with a small table you will *always* get collisions
> due to the last 2-4 bits always being 0?

Most hashtable implementations uses a modulo by some number of the form 2^N-1 
or similar, you would not get increased collisions. This why e.g. the 
upcoming implementation of the hash table in the C++ std library just uses a 
straight reinterpret_cast.

>
> Seriously, how long does a bit-shift operation take? It's measured in
> single-digit /cycles/ after all... It's measurable compared to the cost
> of calling the hash function, but not compared to much else.

A hash function can be called very often. Just the other day, a 70s 
optimisation program managed to call hash<T*> 250 million times. If the 
result is improved, it might be worth it using the 250 million cycles (I 
mean, what is that these days?), but in this case it is not. It just means 
more complicated code with worse performance for no real gain.

-- 
regards, Esben

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.