Following change places each element of the futex_queues hashtable on a
different cacheline. Spinlocks of adjacent hash buckets lie on the same
cacheline otherwise.
Signed-off-by: Ravikiran Thirumalai <[email protected]>
Signed-off-by: Shai Fultheim <[email protected]>
Index: linux-2.6.16-rc2/kernel/futex.c
===================================================================
--- linux-2.6.16-rc2.orig/kernel/futex.c 2006-02-07 23:14:04.000000000 -0800
+++ linux-2.6.16-rc2/kernel/futex.c 2006-02-09 14:04:22.000000000 -0800
@@ -100,9 +100,10 @@ struct futex_q {
struct futex_hash_bucket {
spinlock_t lock;
struct list_head chain;
-};
+} ____cacheline_internodealigned_in_smp;
-static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
+static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS]
+ __cacheline_aligned_in_smp;
/* Futex-fs vfsmount entry: */
static struct vfsmount *futex_mnt;
Ravikiran G Thirumalai <[email protected]> wrote:
>
> Following change places each element of the futex_queues hashtable on a
> different cacheline. Spinlocks of adjacent hash buckets lie on the same
> cacheline otherwise.
>
> Signed-off-by: Ravikiran Thirumalai <[email protected]>
> Signed-off-by: Shai Fultheim <[email protected]>
>
> Index: linux-2.6.16-rc2/kernel/futex.c
> ===================================================================
> --- linux-2.6.16-rc2.orig/kernel/futex.c 2006-02-07 23:14:04.000000000 -0800
> +++ linux-2.6.16-rc2/kernel/futex.c 2006-02-09 14:04:22.000000000 -0800
> @@ -100,9 +100,10 @@ struct futex_q {
> struct futex_hash_bucket {
> spinlock_t lock;
> struct list_head chain;
> -};
> +} ____cacheline_internodealigned_in_smp;
>
> -static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
> +static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS]
> + __cacheline_aligned_in_smp;
>
How much memory does that thing end up consuming?
Andrew Morton <[email protected]> wrote:
>
> Ravikiran G Thirumalai <[email protected]> wrote:
> >
> > Following change places each element of the futex_queues hashtable on a
> > different cacheline. Spinlocks of adjacent hash buckets lie on the same
> > cacheline otherwise.
> >
> > Signed-off-by: Ravikiran Thirumalai <[email protected]>
> > Signed-off-by: Shai Fultheim <[email protected]>
> >
> > Index: linux-2.6.16-rc2/kernel/futex.c
> > ===================================================================
> > --- linux-2.6.16-rc2.orig/kernel/futex.c 2006-02-07 23:14:04.000000000 -0800
> > +++ linux-2.6.16-rc2/kernel/futex.c 2006-02-09 14:04:22.000000000 -0800
> > @@ -100,9 +100,10 @@ struct futex_q {
> > struct futex_hash_bucket {
> > spinlock_t lock;
> > struct list_head chain;
> > -};
> > +} ____cacheline_internodealigned_in_smp;
> >
> > -static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
> > +static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS]
> > + __cacheline_aligned_in_smp;
> >
>
> How much memory does that thing end up consuming?
I think a megabyte?
On Mon, Feb 20, 2006 at 03:34:19PM -0800, Andrew Morton wrote:
> Andrew Morton <[email protected]> wrote:
> >
> > > @@ -100,9 +100,10 @@ struct futex_q {
> > > struct futex_hash_bucket {
> > > spinlock_t lock;
> > > struct list_head chain;
> > > -};
> > > +} ____cacheline_internodealigned_in_smp;
> > >
> > > -static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
> > > +static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS]
> > > + __cacheline_aligned_in_smp;
> > >
> >
> > How much memory does that thing end up consuming?
>
> I think a megabyte?
On most machines it would be 256 * 128 = 32k. or 16k on arches with 64B
cachelines. This looked like a simpler solution for spinlocks falling on
the same cacheline. So is 16/32k unreasonable?
Thanks,
Kiran
Ravikiran G Thirumalai <[email protected]> wrote:
>
> On Mon, Feb 20, 2006 at 03:34:19PM -0800, Andrew Morton wrote:
> > Andrew Morton <[email protected]> wrote:
> > >
> > > > @@ -100,9 +100,10 @@ struct futex_q {
> > > > struct futex_hash_bucket {
> > > > spinlock_t lock;
> > > > struct list_head chain;
> > > > -};
> > > > +} ____cacheline_internodealigned_in_smp;
> > > >
> > > > -static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
> > > > +static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS]
> > > > + __cacheline_aligned_in_smp;
> > > >
> > >
> > > How much memory does that thing end up consuming?
> >
> > I think a megabyte?
>
> On most machines it would be 256 * 128 = 32k. or 16k on arches with 64B
> cachelines. This looked like a simpler solution for spinlocks falling on
> the same cacheline. So is 16/32k unreasonable?
>
CONFIG_X86_VSMP enables 4096-byte padding for
____cacheline_internodealigned_in_smp. It's a megabyte.
On Mon, Feb 20, 2006 at 04:23:17PM -0800, Andrew Morton wrote:
> Ravikiran G Thirumalai <[email protected]> wrote:
> >
> > On Mon, Feb 20, 2006 at 03:34:19PM -0800, Andrew Morton wrote:
> > > Andrew Morton <[email protected]> wrote:
> > > >
> > > > > @@ -100,9 +100,10 @@ struct futex_q {
> > > > > struct futex_hash_bucket {
> > > > > spinlock_t lock;
> > > > > struct list_head chain;
> > > > > -};
> > > > > +} ____cacheline_internodealigned_in_smp;
> > > > >
> > > > > -static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
> > > > > +static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS]
> > > > > + __cacheline_aligned_in_smp;
> > > > >
> > > >
> > > > How much memory does that thing end up consuming?
> > >
> > > I think a megabyte?
> >
> > On most machines it would be 256 * 128 = 32k. or 16k on arches with 64B
> > cachelines. This looked like a simpler solution for spinlocks falling on
> > the same cacheline. So is 16/32k unreasonable?
> >
>
> CONFIG_X86_VSMP enables 4096-byte padding for
> ____cacheline_internodealigned_in_smp. It's a megabyte.
Yes, only on vSMPowered systems. Well, we have a large
internode cacheline, but these machines have lots of memory too. I
thought a simpler padding solution might be acceptable as futex_queues
would be large only on our boxes.
Maybe we can dynamically allocate spinlocks, but it would be difficult to
say which node the spinlock should come from as yet.
Ravikiran G Thirumalai <[email protected]> wrote:
>
> On Mon, Feb 20, 2006 at 04:23:17PM -0800, Andrew Morton wrote:
> > Ravikiran G Thirumalai <[email protected]> wrote:
> > >
> > > On Mon, Feb 20, 2006 at 03:34:19PM -0800, Andrew Morton wrote:
> > > > Andrew Morton <[email protected]> wrote:
> > > > >
> > > > > > @@ -100,9 +100,10 @@ struct futex_q {
> > > > > > struct futex_hash_bucket {
> > > > > > spinlock_t lock;
> > > > > > struct list_head chain;
> > > > > > -};
> > > > > > +} ____cacheline_internodealigned_in_smp;
> > > > > >
> > > > > > -static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
> > > > > > +static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS]
> > > > > > + __cacheline_aligned_in_smp;
> > > > > >
> > > > >
> > > > > How much memory does that thing end up consuming?
> > > >
> > > > I think a megabyte?
> > >
> > > On most machines it would be 256 * 128 = 32k. or 16k on arches with 64B
> > > cachelines. This looked like a simpler solution for spinlocks falling on
> > > the same cacheline. So is 16/32k unreasonable?
> > >
> >
> > CONFIG_X86_VSMP enables 4096-byte padding for
> > ____cacheline_internodealigned_in_smp. It's a megabyte.
>
> Yes, only on vSMPowered systems. Well, we have a large
> internode cacheline, but these machines have lots of memory too. I
> thought a simpler padding solution might be acceptable as futex_queues
> would be large only on our boxes.
Well it's your architecture... As long as you're finding this to be a
sufficiently large problem in testing to justify consuming a meg of memory
then fine, let's do it.
But your initial changelog was rather benchmark-free? It's always nice to
see numbers accompanying a purported optimisation patch.
On Mon, Feb 20, 2006 at 05:09:40PM -0800, Andrew Morton wrote:
> Ravikiran G Thirumalai <[email protected]> wrote:
> >
> >
> > Yes, only on vSMPowered systems. Well, we have a large
> > internode cacheline, but these machines have lots of memory too. I
> > thought a simpler padding solution might be acceptable as futex_queues
> > would be large only on our boxes.
>
> Well it's your architecture... As long as you're finding this to be a
> sufficiently large problem in testing to justify consuming a meg of memory
> then fine, let's do it.
>
> But your initial changelog was rather benchmark-free? It's always nice to
> see numbers accompanying a purported optimisation patch.
We saw 30% better elapsed time with a threaded benchmark on our systems, with
this patch. That said, we would like to avoid this bloat on our systems too,
and some work needs to be done to improve futex hashing on NUMA. But for now,
this patch should be good enough.
Thanks,
Kiran
Ravikiran G Thirumalai wrote:
> Following change places each element of the futex_queues hashtable on a
> different cacheline. Spinlocks of adjacent hash buckets lie on the same
> cacheline otherwise.
>
It does not make sense to add swaths of unused memory into a hashtable for
this purpose, does it?
For a minimal, naive solution you just increase the size of the hash table.
This will (given a decent hash function) provide the same reduction in
cacheline contention, while also reducing collisions.
A smarter solution might have a single lock per cacheline, and multiple hash
slots. This could make the indexing code a bit more awkward though.
> Signed-off-by: Ravikiran Thirumalai <[email protected]>
> Signed-off-by: Shai Fultheim <[email protected]>
>
> Index: linux-2.6.16-rc2/kernel/futex.c
> ===================================================================
> --- linux-2.6.16-rc2.orig/kernel/futex.c 2006-02-07 23:14:04.000000000 -0800
> +++ linux-2.6.16-rc2/kernel/futex.c 2006-02-09 14:04:22.000000000 -0800
> @@ -100,9 +100,10 @@ struct futex_q {
> struct futex_hash_bucket {
> spinlock_t lock;
> struct list_head chain;
> -};
> +} ____cacheline_internodealigned_in_smp;
>
> -static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
> +static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS]
> + __cacheline_aligned_in_smp;
>
> /* Futex-fs vfsmount entry: */
> static struct vfsmount *futex_mnt;
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/
>
--
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com
Andrew Morton <[email protected]> writes:
>
> Well it's your architecture... As long as you're finding this to be a
> sufficiently large problem in testing to justify consuming a meg of memory
> then fine, let's do it.
I think it's a waste of memory even with 128 byte cache lines.
If it's really a big problem. Some more clever solution would be
better. e.g. allocate a hash table per node and use a hierarchical
hash, trying to put stuff into the local node first.
-Andi
On Tue, 21 Feb 2006, Nick Piggin wrote:
> Ravikiran G Thirumalai wrote:
> > Following change places each element of the futex_queues hashtable on a
> > different cacheline. Spinlocks of adjacent hash buckets lie on the same
> > cacheline otherwise.
> >
>
> It does not make sense to add swaths of unused memory into a hashtable for
> this purpose, does it?
It does if you essentially have a 4k cacheline (because you are doing NUMA
in software with multiple PCs....) and transferring control of that
cacheline is comparatively expensive.
On Tue, Feb 21, 2006 at 02:30:00PM +1100, Nick Piggin wrote:
> Ravikiran G Thirumalai wrote:
> >Following change places each element of the futex_queues hashtable on a
> >different cacheline. Spinlocks of adjacent hash buckets lie on the same
> >cacheline otherwise.
> >
>
> It does not make sense to add swaths of unused memory into a hashtable for
> this purpose, does it?
I don't know if having two (or more) spinlocks on the same cacheline is a good
idea. Right now, on a 128 B cacheline we have 10 spinlocks on the
same cacheline here!! Things get worse if two futexes from different nodes
hash on to adjacent, or even nearly adjacent hash buckets.
>
> For a minimal, naive solution you just increase the size of the hash table.
> This will (given a decent hash function) provide the same reduction in
> cacheline contention, while also reducing collisions.
Given a decent hash function. I am not sure the hashing function is smart
enough as of now. Hashing is not a function of nodeid, and we have some
instrumentation results which show hashing on NUMA is not good as yet, and
there are collisions from other nodes onto the same hashbucket; Nearby
buckets have high hit rates too.
I think some sort of NUMA friendly hashing, where futexes from same nodes
hash onto a node local hash table, would be a decent solution here.
As I mentioned earlier, we are working on that, and we can probably allocate
the spinlock from nodelocal memory then and avoid this bloat.
We are hoping to have this as a stop gap fix until we get there.
Thanks,
Kiran
On Tue, 21 Feb 2006, Christoph Lameter wrote:
> It does if you essentially have a 4k cacheline (because you are doing NUMA
> in software with multiple PCs....) and transferring control of that
> cacheline is comparatively expensive.
Of course the above statement is a rather strong simplification of what is
actually happening .... but I hope it helps.
Ravikiran G Thirumalai wrote:
> On Tue, Feb 21, 2006 at 02:30:00PM +1100, Nick Piggin wrote:
>
>>Ravikiran G Thirumalai wrote:
>>
>>>Following change places each element of the futex_queues hashtable on a
>>>different cacheline. Spinlocks of adjacent hash buckets lie on the same
>>>cacheline otherwise.
>>>
>>
>>It does not make sense to add swaths of unused memory into a hashtable for
>>this purpose, does it?
>
>
> I don't know if having two (or more) spinlocks on the same cacheline is a good
> idea. Right now, on a 128 B cacheline we have 10 spinlocks on the
> same cacheline here!! Things get worse if two futexes from different nodes
> hash on to adjacent, or even nearly adjacent hash buckets.
>
It is no worse than having a hash collision and having to take the same lock.
(as I said, a really good solution might just use a single lock per cacheline,
but that would make hash indexing a bit more difficult.)
>
>>For a minimal, naive solution you just increase the size of the hash table.
>>This will (given a decent hash function) provide the same reduction in
>>cacheline contention, while also reducing collisions.
>
>
> Given a decent hash function. I am not sure the hashing function is smart
> enough as of now. Hashing is not a function of nodeid, and we have some
> instrumentation results which show hashing on NUMA is not good as yet, and
> there are collisions from other nodes onto the same hashbucket; Nearby
> buckets have high hit rates too.
>
But it is decent in that it is random. The probability of an address hashing
to the same cacheline as another should be more or less the same as with your
padded scheme.
> I think some sort of NUMA friendly hashing, where futexes from same nodes
> hash onto a node local hash table, would be a decent solution here.
> As I mentioned earlier, we are working on that, and we can probably allocate
> the spinlock from nodelocal memory then and avoid this bloat.
> We are hoping to have this as a stop gap fix until we get there.
>
But my point still stands that it never makes sense to add empty space into
a hash table. Add hash slots instead and you (for free) get shorter hash
chains.
--
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com
Christoph Lameter wrote:
> On Tue, 21 Feb 2006, Nick Piggin wrote:
>
>
>>Ravikiran G Thirumalai wrote:
>>
>>>Following change places each element of the futex_queues hashtable on a
>>>different cacheline. Spinlocks of adjacent hash buckets lie on the same
>>>cacheline otherwise.
>>>
>>
>>It does not make sense to add swaths of unused memory into a hashtable for
>>this purpose, does it?
>
>
> It does if you essentially have a 4k cacheline (because you are doing NUMA
> in software with multiple PCs....) and transferring control of that
> cacheline is comparatively expensive.
>
Instead of 1MB hash with 256 entries in it covering 256 cachelines, you
have a 1MB hash with 65536(ish) entries covering 256 cachelines.
-
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com
Nick Piggin <[email protected]> wrote:
>
> But my point still stands that it never makes sense to add empty space into
> a hash table. Add hash slots instead and you (for free) get shorter hash
> chains.
OK, not an accident ;)
Nick Piggin <[email protected]> wrote:
>
> Christoph Lameter wrote:
> > On Tue, 21 Feb 2006, Nick Piggin wrote:
> >
> >
> >>Ravikiran G Thirumalai wrote:
> >>
> >>>Following change places each element of the futex_queues hashtable on a
> >>>different cacheline. Spinlocks of adjacent hash buckets lie on the same
> >>>cacheline otherwise.
> >>>
> >>
> >>It does not make sense to add swaths of unused memory into a hashtable for
> >>this purpose, does it?
> >
> >
> > It does if you essentially have a 4k cacheline (because you are doing NUMA
> > in software with multiple PCs....) and transferring control of that
> > cacheline is comparatively expensive.
> >
>
> 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...
On Tue, Feb 21, 2006 at 06:08:45PM -0800, Andrew Morton wrote:
> Nick Piggin <[email protected]> wrote:
> >
> > Christoph Lameter wrote:
> > > On Tue, 21 Feb 2006, Nick Piggin wrote:
> > >
> > >
> > >>Ravikiran G Thirumalai wrote:
> > >>
> > >>>Following change places each element of the futex_queues hashtable on a
> > >>>different cacheline. Spinlocks of adjacent hash buckets lie on the same
> > >>>cacheline otherwise.
> > >>>
> > >>
> > >>It does not make sense to add swaths of unused memory into a hashtable for
> > >>this purpose, does it?
> > >
> > >
> > > It does if you essentially have a 4k cacheline (because you are doing NUMA
> > > in software with multiple PCs....) and transferring control of that
> > > cacheline is comparatively expensive.
> > >
> >
> > 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...
Yes, good (intentional :) ) point. I am rerunning my tests with a larger hash slot.
(As large as the padding takes away). If we get the same or better results, we
can just increase the hash slots.
Thanks,
Kiran
Andrew Morton wrote:
> Nick Piggin <[email protected]> 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.
Definitely for "normal" systems, we do not want to pad out to a
single entry per cacheline, so the current patch can not go upstream
as is.
--
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com
On Wed, Feb 22, 2006 at 01:37:10PM +1100, Nick Piggin wrote:
> Andrew Morton wrote:
> >Nick Piggin <[email protected]> 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
Ravikiran G Thirumalai <[email protected]> wrote:
>
> 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.
You could try switching from jhash2() to hash_long().
Was there any particular pattern to the unused slots? Not something silly
like every second one?
On Wed, Feb 22, 2006 at 05:51:44PM -0800, Ravikiran G Thirumalai wrote:
> On Wed, Feb 22, 2006 at 12:50:49PM -0800, Andrew Morton wrote:
> > Ravikiran G Thirumalai <[email protected]> wrote:
> > >
> > > 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.
> >
> > You could try switching from jhash2() to hash_long().
>
> OK, I will try that.
>
> >
> > Was there any particular pattern to the unused slots? Not something silly
> > like every second one?
>
> The distribution seems OK with 256 buckets, but with 1024 buckets, it goes
> bad. We see high hits every 4-6 buckets. Attaching the distribution
This pattern might not be bad as it avoids bouncing of spinlocks on the adjacent
hash buckets...but then there are high hits on adjacent buckets too.
(instrumentation done by Nippun)
Thanks,
Kiran