Re: Wondering about FACE_CACHE_BUCKETS_SIZE

[tomas]

On Tue, Feb 09, 2021 at 09:53:34PM -0500, Win Treese wrote:
> 
> I happened to be looking at some code in src/xfaces.c on the trunk, and I
> noticed this at lines 289-292:
> 
> /* Size of hash table of realized faces in face caches (should be a
>    prime number).  */
> 
> #define FACE_CACHE_BUCKETS_SIZE 1001
> 
> 1001 isn’t prime (it’s 7*11*13).

No, it isn't :-)

>                                   A quick look at the hash table code
> suggest that the main effect of it is to slow things down a little bit
> because some hash buckets would get used more often than they
> would be with a prime. 

Still, this is pretty improbable. This would mean that whatever is hashed
in that table shows some statistical correlation with one of the linear
sequences m + n*i for n in {7, 11, 13}. Would be surprising, at least.

For some even (possibly power-of-two) numbers, I'd be more willing to
bet on it. Say you're hashing pointers: for alignment reasons they are
all divisible by 4, or 8.

I'd venture to say "prime enough", although 7 is uncomfortably small a
divisor ;-)

> From the git log, it’s been this way since the code was first committed
> in 1999.
> 
> There’s probably no real problem here, except that the comment and
> code don’t match. On the other hand, 997 and 1009 are nice nearby
> primes if it really matters.

But yes, to be in the camp "there will be no clustering, even if an
enemy choses the keys", perhaps 991, 997 or 1009 are better choices.

Cheers
 - t

signature.asc
Description: Digital signature