hash functions should not be required to accept two arguments William D Clinger (09 Nov 2015 17:42 UTC)
Re: hash functions should not be required to accept two arguments William D Clinger (10 Nov 2015 12:02 UTC)
Re: hash functions should not be required to accept two arguments taylanbayirli@xxxxxx (10 Nov 2015 13:00 UTC)
Re: hash functions should not be required to accept two arguments William D Clinger (10 Nov 2015 13:50 UTC)
Re: hash functions should not be required to accept two arguments taylanbayirli@xxxxxx (10 Nov 2015 14:27 UTC)
Hash salt John Cowan (10 Nov 2015 06:37 UTC)
Re: Hash salt taylanbayirli@xxxxxx (10 Nov 2015 10:00 UTC)
Re: Hash salt John Cowan (11 Nov 2015 05:21 UTC)
Re: Hash salt Shiro Kawai (11 Nov 2015 05:59 UTC)
Re: Hash salt John Cowan (11 Nov 2015 06:22 UTC)
Re: Hash salt taylanbayirli@xxxxxx (11 Nov 2015 07:54 UTC)
Re: hash functions should not be required to accept two arguments taylanbayirli@xxxxxx (10 Nov 2015 09:58 UTC)

Re: hash functions should not be required to accept two arguments William D Clinger 10 Nov 2015 12:02 UTC

Alex Shinn wrote:

> Did you see my computation on the SRFI 125 mailing list which
> gave the 1/4 available memory?

No.

> First, with 3-bit tags the max fixnum is 2^28-1 = 268435455,
> half your value... and half the memory, which already means
> we have more than enough remaining memory to implement
> something like memcached.

I said "the largest positive fixnum is likely to be 536870911."
If you survey implementations that use 3-bit tags, you'll find
that most devote two tags to fixnums, doubling the fixnum range.
If your reasoning applies only to systems that don't do that,
then your argument applies only to systems whose performance is
likely to be unsatisfactory on other grounds.

> The keys could be fixnums.  Since we can use negative fixnums
> we already have more possible keys than the maximum number
> of buckets.

That's a consequence of SRFI 126's arbitrary restriction of hash
values to non-negative integers.  If that were a real problem
(which it isn't, as explained above), the solution would be to
allow negative hash values.

> I haven't run any benchmarks, but I think a simple lookup in a
> hash table should not cons.

I've run the benchmarks.  In Larceny, a simple hash table lookup
costs about 100 times as much as allocating a bignum whose lifetime
is limited to the duration of the lookup.

You're repeating an ancient mantra that became obsolete with the
advent of generational garbage collection.

You may say your reasoning still applies to systems that don't
use generational garbage collection, but why would someone who
needs extreme performance (approaching 100% of the address space)
be using a low-performance system?

Will