Re: [patch] Cache align futex hash buckets

[Ravikiran G Thirumalai <kiran@scalex86.org>]

On Wed, Feb 22, 2006 at 01:37:10PM +1100, Nick Piggin wrote:
> Andrew Morton wrote:
> >Nick Piggin <nickpiggin@yahoo.com.au> wrote:
> 
> >>Instead of 1MB hash with 256 entries in it covering 256 cachelines, you
> >>have a 1MB hash with 65536(ish) entries covering 256 cachelines.
> >>
> >
> >
> >Good (if accidental point).  Kiran, if you're going to gobble a megabyte,
> >you might as well use all of it and make the hashtable larger, rather than
> >just leaving 99% of that memory unused...
> >
> 
> We chould probably also convert the list_head over to an hlist_head,
> for a modest saving in size (although that's more important from a
> cache footprint POV rather than improving cacheline bouncing).
> 
> Although speaking of cacheline footprint: making the hash table so
> large will increase the "real" CPU cacheline footprint on your VSMP
> systems, so perhaps it is not always such an easy decision.

We re-ran the threaded benchmark with FUTEX_HASHBITS set to 15 (32k hash
slots) and got the same performance as the padding approach.  So increasing
the hash helps.  We also tried 256, 512, and 1024 hash slots, but we
did not get good results with those. 
We also collected hash collision statistics for 1024 slots.  We found that
50% of the slots did not take any hit!!  So maybe we should revisit the
hashing function before settling on the optimal number of hash slots. 

Thanks,
Kiran