This is the mail archive of the
binutils@sources.redhat.com
mailing list for the binutils project.
just a little nitpik in bfd
- From: Stuart Balfour <sbalfour at cisco dot com>
- To: binutils at sources dot redhat dot com
- Date: Sun, 12 May 2002 13:56:18 -0700 (PDT)
- Subject: just a little nitpik in bfd
In the core of bfd (binutils 2.11.92), in file hash.c in function
bfd_hash_lookup, I see:
> hash = 0;
> len = 0;
> s = (const unsigned char *) string;
> while ((c = *s++) != '\0')
> {
> hash += c + (c << 17);
> hash ^= hash >> 2;
> ++len;
> }
> hash += len + (len << 17);
> hash ^= hash >> 2;
Surely, we can eliminate ++len from the loop, because it is an induction
variable (and the compiler might do it for us, but we can and should
code carefully first, then hope the compiler can do better):
hash = 0;
s = (const unsigned char *) string;
while ((c = *s++) != '\0')
{
hash += c + (c << 17);
hash ^= hash >> 2;
}
len = s - string - 1;
hash += len + (len << 17);
hash ^= hash >> 2;
One more wrinkle: why do we need to hash len into the hash total? I could
see it if we were hashing on less than the whole string. But len is
implicitly encoded into the hash total because longer strings will have
higher hash totals generally. We're into theory and practice here, and
I have none to offer. But Knuth, in "Sorting and Searching", doesn't
mention length of string as of special importance. Because an obvious
induction variable was computed in a tight loop, either len was a careless
afterthought, or the whole thing was coded by someone a little lacking
in craft. Considering the central importance of this algorithm, I think
there could be comment annotation for inclusion of length in the hash total.
Stuart Balfour
Software Tools
Cisco Systems
sbalfour@cisco.com