[r6rs-discuss] Hash function return value constraints
kumoyuki at gmail.com
Sat Apr 4 04:33:41 EDT 2009
2009/4/4 Lynn Winebarger <owinebar at gmail.com>:
> The problem is that the situation is actually reversed. The user may be
> writing the hash table implementation, but wants to use the Scheme
> implementation's hash functions to get hashes on arbitrary Scheme objects
> for efficiency. Obviously the tables the implementation provides can do
> whatever they want under the hood, but the hash functions provided by the
> implementation to the public should conform to the user's expectations.
And *that* is the clear reason for the R6RS restriction. It makes user
written hash table code more portable.
And you *do* have to write your own hash-tables if you want good
performance. Many moons ago, I did some serious side-by-side
benchmarking, and found that under identical test runs, variation in
any of the variables (underlying vector size, rehashing algorithm,
growth increments, hash-function, collision resolution algorithms...)
involved in a real hash-table implementation correlates chaotically
with the bench-mark run-times.
Hash tables are not O(1)! They need to be carefully tuned.
GPG Public key at http://cyber-rush.org/drr/gpg-public-key.txt
More information about the r6rs-discuss