On Wed, Aug 4, 2010 at 5:01 AM, David Tweed <david.tw...@gmail.com> wrote: > On Wed, Aug 4, 2010 at 2:53 AM, Jacob Todd <jaketodd...@gmail.com> wrote: > It's also worth remembering that K & R was written at a time many > decades ago when performance aspects of computer architecture were a > lot, lot simpler. Apparently they have > > #define HASHSIZE 101 > > which given that there's no really efficient way of computing % for > arbitrary numbers is going to be quite slow (particularly if the > strings are short), which is why hashes for modern machines use table > sizes that avoid needing a mod. (There are other things that are slow > on modern architectures that modern hash functions avoid.) I'd use K&R > for the C syntax and some of the higher level ideas of programming, > but not try to understand good hashing technology from there.
A minor clarification: looking at the gcc assembly if you've hardcoded the table size it figures out some magic constants so that it takes around 8 bit-twiddling and subtraction instructions to do the mod operation, which is slow but not that slow. If you pass the table size as a variable, which you would in "serious" code you get integer division based code, which is going to be "quite slow". But the point about K & R being basically a syntax and high-level strategy book these days stands. -- cheers, dave tweed__________________________ computer vision reasearcher: david.tw...@gmail.com "while having code so boring anyone can maintain it, use Python." -- attempted insult seen on slashdot
