James Dow Allen said:
(BTW, The only reason I had glibc source on my laptop
is that I wanted to inspect their hsearch() and see
if they ever fixed its *very* egregious performance
bug.
[off-topic] I could not find your bug report, so I filed one.
When I mentioned the bug some years ago, someone
directed me to a Usenet group for reporting gnu
bugs, but that group seemed to be defunct!
I saw no reason to pursue it; no one has come forward
who admits to actually *using* hsearch().
... learners might like to look at
hsearch_r.c at the link above to see how easily one
can make an error ...
I noticed its buggy reprobe behavior doing a "black
box" test some years ago, and didn't more than glance
at the source code until you posted. Now I see things
are much worse than I realized. Indeed, as you suggest,
hsearch()'s only utility may be as a how-not-to example.
The hsearch code includes a "frilly" feature (perhaps
added hurriedly to an already-working routine?) with
at least five flaws. The feature expanded a table
entry from (normally) 8 bytes to 12 bytes with the
extra field ("used") used (redundantly) in tests for
empty slots and key equality. (I say "redundant", because
if (hp->key == 0)
was already available to test for empty slots, and
if (!strcmp(hp->key, item.key))
is a necessary and sufficient test for key equality.)
(1) If one chooses to spend 4 (or sizeof(unsigned int))
bytes in this fashion, one should "get one's money
worth!" The field will be compared with "hval" (or
"ohval"!) which is derived via:
unsigned int hval;
hval = ... /* hashfunction(item.key) */ ;
/* ohval = hval + 1 */
hval %= htab->size;
if (hval == 0) ++hval; /* get rid of this */
...
if (...->used != hval) /* bypass strcmp() */
The value of hval *before* the "%= htab->size" should
have been preserved for the short-circuiting key equality
test. I've shown a way to do this with the commented-out
ohval assignment. (Note that as is, false equalities
(where the strcmp() ends up not being bypassed) will be
quite common.
(2) It's not very wrong to pack an empty-slot indicator
into the extra field (though one wonders why they bothered),
but they found a bad solution to an easy problem. Note,
for example, the "+ 1" in my "ohval = " fix. That's it!
You're done! This allows the inequality short-circuit
*and* the empty-slot test, with *no* further worry
about any issues of the "+ 1".
Instead, the coder chose to inject the "+ 1" into
code more intimately associated with the table indexing,
and this leads to the next two bugs. (To avoid a zero
index, he also uses a "+ 1" in the calloc() to allocate
the hash table, but let's not quibble over 12 wasted
bytes.)
(3) As implied in the above code and discussion, a
table of size p will have entries (1,2,3,...,p);
however no hash output maps to (p), while *two* hash
outputs map to 1! (see "if (hval == 0) ++hval;" above).
A nit, perhaps, but why deliberately degrade one's
hash function? The "if (hval == 0)" can be simply
snipped, I think, with no ill effect, but as
explained in (1) and (2), the whole concept is hardly
worth salvage.
(4) Also building on flaw (2), coder managed
to distort the "based-on-Knuth reprobing" and wastes
almost every initial reprobe. Had the coder bothered
to print *any* statistic about reprobes during his
testing, this bug would have become blindingly obvious,
(5) Finally, the whole "used" concept is unnecessary
and may hurt rather than help performance. It increases
the table size by 50% and *increases* instructions
executed (at least if strcmp is wholly or partly in-lined).
It *does* avoid cache-misses (on unequal
key strings) during reprobing, but if this were a goal,
why didn't they switch to quadratic reprobing, whose
virtues include good cache utilization?
I think this hsearch() teaches three useful lessons,
in order of increasing importance:
(1) Be careful when "squeezing" in special-values.
hsearch() bugs #2 and #3 stem from the
++hval; /* make room for special indicator */
Try to avoid such things, or find a way to make them
transparent to most of the code.
(2) Exercise special caution when implementing
tricky or poorly-understood code.
(3) Test your code.
When the only purpose of a method is improved performance,
test the performance! (A "hash table" implemented as
sequential search will pass functional tests.)
printf() is your debugging friend! (We've all needed to
set breakpoints or pore over coredumps back in the day,
but judicious use of "if (TEST) printf()" is the
straightforward way to address most testing and debugging.)
Developing and printing *any* statistic about reprobe
counts during hsearch() evaluation would have made its bug
blindingly obvious. That this code was placed in glibc
without any such test is a black mark indeed on someone.
Don't be afraid to do simple tests. Perhaps the
programmer didn't bother to print probing statistics
because he didn't know how to interpret them, but if he
*had* printed them *anyway*, very little expertise would
have been needed to see that something was wrong.
A few months ago, in a thread about gets(), I mentioned
the original Hubbell Telescope flaw as an example
where a cheap simple test was overlooked amid a debate
about whether to run an expensive thorough test.
In that thread, the self-appointed Deprecator-in-Chief
utterly failed to grasp this simple point, suggesting that
this blind spot affects even average-plus programmers.
James Dow Allen
