Wondering about FACE_CACHE_BUCKETS_SIZE

Wondering about FACE_CACHE_BUCKETS_SIZE

[Win Treese]

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). 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. 

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.

 - Win

Re: Wondering about FACE_CACHE_BUCKETS_SIZE

[tomas]

[-- Attachment #1: Type: text/plain, Size: 1533 bytes --]

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

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: Wondering about FACE_CACHE_BUCKETS_SIZE

[Eli Zaretskii]

> From: Win Treese <treese@acm.org>
> Date: Tue, 9 Feb 2021 21:53:34 -0500
> 
> 
> 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). 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. 
> 
> 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.

Thanks, I changed that to 1009.