hash functions should not be required to accept two arguments William D Clinger 09 Nov 2015 17:25 UTC
Re: hash functions should not be required to accept two arguments John Cowan 09 Nov 2015 22:35 UTC
Re: hash functions should not be required to accept two arguments Alex Shinn 10 Nov 2015 02:44 UTC
Re: hash functions should not be required to accept two arguments John Cowan 10 Nov 2015 05:43 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 John Cowan 10 Nov 2015 13:58 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 Alex Shinn 10 Nov 2015 14:15 UTC
Re: hash functions should not be required to accept two arguments taylanbayirli@xxxxxx 10 Nov 2015 14:26 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 John Cowan 11 Nov 2015 05:53 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