This is the mail archive of the binutils@sources.redhat.com mailing list for the binutils project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]