Path: utzoo!utgpu!attcan!uunet!seismo!sundc!pitstop!sun!decwrl!megatest!djones
From: djones@megatest.UUCP (Dave Jones)
Newsgroups: comp.lang.c
Subject: Re: Efficient coding considered harmful?
Message-ID: <959@goofy.megatest.UUCP>
Date: 3 Nov 88 03:31:09 GMT
References: <8819@smoke.BRL.MIL>
Organization: Megatest Corporation, San Jose, Ca
Lines: 48

Okay, I'll wade into the fray.  But only up to my, er, toenails this time.
Last time I ventured into a religious war, I was burned at the
metaphorical stake,  but I never converted by gum!  No doubt this 
will have the same outcome.


From article <8819@smoke.BRL.MIL>, by gwyn@smoke.BRL.MIL (Doug Gwyn ):
> In article <137@twwells.uucp> bill@twwells.UUCP (T. William Wells) writes:
>>#define HASHSIZE 4              /* A power of two, or else! */
> 
> To continue my complaint against using bitwise operators where arithmetic
> is called for, let me point out that most reasonable hashing schemes work
> best of the hash table size is NOT a power of two.

Perhaps most, but certainly not all.  My favorite *requires* a power
of two.  One exception disproves the rule.  But aren't we straying away
from the subject?  The subject is whether it is EVER okay to use >> to
implement division by a power of two, not whether or not it is best, in some 
hypothetical case, to divide by a power of two or a by a prime number.

> ...

> Again, this is a case that any decent compiler would have been able to
> handle just as well if you had used division and remainder operators.

True enough.  But what if you are programming for the new Banana 8000,
and you don't have access to a "decent compiler", because there aren't
any?  Or, more to the point,  what if the power of two you are dividing
by is not a constant?  

I've got a hash-table package that has been working just fine, 
thankyewverymuch -- and fast as blazes -- in lots of applications written
by lots of programmers, for about three years now.  I expect it
to live on indefinately. It uses a quick rehashing scheme, not chaining. 
It automatically doubles the size of the table when things get crowded.
And yet entries can be efficiently removed on demand. It is the fastest
hashing algorithm I know of. 

The speed of the division makes a difference.

The table size is not a constant, but it's always a power of two.  
Has to be.  I used a shift to divide by the power of two, and I'm not 
about to make it slower because of religious dogma.

> The trickery is not only unnecessary, but (as I said previously) it gets
> in the way of code reliability and maintainance.

What trickery?