Nonportable code in C++ support

[Matthew Woehlke]

Esben Mose Hansen wrote:
> On Friday 15 February 2008 20:14:15 Matthew Woehlke wrote:
>> 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.

Hmm, well... a particular algorithm I'm familiar with doesn't :-). And 
for good reason (keep reading...).

>> 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.

Ok... that would make a shift here *almost* a 0.2% performance hit on a 
typical recent machine. I can't say I'm terrifically worried about that.

However, you failed to take something into account. You don't just call 
hash(foo), because to get the hash table index you actually have to call 
reduce(hash(foo)). The reduce function matters... a *lot*.

In order for a no-op pointer hash function to not suck, you /must/ use 
the modulo-2**n-1 reduce() function you mentioned, but idivl is hugely 
more expensive than andl, even after the more complicated hash function 
needed by a modulo-2**n hash table. A modulo-2**n hash table (where 
reduce() == andl) with a shrl hash function should neatly outperform* a 
modulo-2**n-1 hash table (reduce() == movl+cltd+idivl) with a no-op hash 
function.

(* Did I say "outperform"? I meant "kick the pants off"... testing 2**30 
iterations of shrl+and vs movl+cltd+idivl in a loopl on a Xeon, the 
latter was around 20x slower. The times were 0m1.118s vs 0m27.393s. 
Sources attached.)

-- 
Matthew
A pool hall put up a sign in their front window that read: "Profound 
language prohibited within." I could just imagine some people discussing 
the meaning of life and being told to take it outside. -- Scott Adams
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: idiv.s
URL: <http://mail.kde.org/pipermail/kdevelop-devel/attachments/20080215/bbdd194b/attachment.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: shradd.s
URL: <http://mail.kde.org/pipermail/kdevelop-devel/attachments/20080215/bbdd194b/attachment-0001.ksh>