Cache align futex hash buckets
PATCH 1/1 Cache align futex hash buckets
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.
kernel/futex.c +3 -2
@@ -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;
Quoted 13 lines · Ravikiran G Thirumalai
Following change places each element of the
futex_queueshashtable 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
===================================================================
kernel/futex.c struct futex_q { · line 107
Quoted 10 lines
kernel/futex.c +3
-2@@ -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?
Quoted 21 lines · Andrew Morton
Quoted 19 lines · Ravikiran G Thirumalai
Following change places each element of the
futex_queueshashtable 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
===================================================================kernel/futex.c +1
-1@@ -100,9 +100,10 @@ struct futex_q {struct futex_hash_bucket {spinlock_t lock;struct list_head chain; -}; +}____cacheline_internodealigned_in_smp ;
Quoted 6 lines
kernel/futex.c struct futex_q { · line 107
Quoted 4 lines
kernel/futex.c +2
-1-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?
Quoted 9 lines · Andrew Morton
Quoted 8 lines · Andrew Morton
Quoted 8 lines
kernel/futex.c +1
-1@@ -100,9 +100,10 @@ struct futex_q {struct futex_hash_bucket {spinlock_t lock;struct list_head chain; -}; +}____cacheline_internodealigned_in_smp ;
Quoted 8 lines
Quoted 6 lines
kernel/futex.c struct futex_q { · line 107
Quoted 4 lines
kernel/futex.c +2
-1-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
Quoted 18 lines · Ravikiran G Thirumalai
Quoted 16 lines · Andrew Morton
Quoted 14 lines · Andrew Morton
kernel/futex.c struct futex_q { · line 107
Quoted 12 lines
kernel/futex.c +3
-2@@ -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?
Quoted 6 lines
Quoted 1 line
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.
Quoted 21 lines · Andrew Morton
Quoted 20 lines · Ravikiran G Thirumalai
Quoted 17 lines · Andrew Morton
Quoted 8 lines · Andrew Morton
Quoted 8 lines
kernel/futex.c +1
-1@@ -100,9 +100,10 @@ struct futex_q {struct futex_hash_bucket {spinlock_t lock;struct list_head chain; -}; +}____cacheline_internodealigned_in_smp ;Quoted 6 lines
kernel/futex.c struct futex_q { · line 107
Quoted 4 lines
kernel/futex.c +2
-1-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?
Quoted 7 lines
Quoted 4 lines
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_VSMPenables 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.
Quoted 28 lines · Ravikiran G Thirumalai
Quoted 26 lines · Andrew Morton
Quoted 24 lines · Ravikiran G Thirumalai
Quoted 9 lines · Andrew Morton
Quoted 8 lines · Andrew Morton
Quoted 8 lines
kernel/futex.c +1
-1@@ -100,9 +100,10 @@ struct futex_q {struct futex_hash_bucket {spinlock_t lock;struct list_head chain; -}; +}____cacheline_internodealigned_in_smp ;Quoted 8 lines
Quoted 6 lines
kernel/futex.c struct futex_q { · line 107
Quoted 4 lines
kernel/futex.c +2
-1-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?
Quoted 7 lines
Quoted 2 lines
CONFIG_X86_VSMPenables 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_queueswould 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.
Quoted 8 lines · Andrew Morton
Quoted 6 lines · Ravikiran G Thirumalai
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_queueswould be large only on our boxes.
Quoted 6 lines
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
Quoted 2 lines · Ravikiran G Thirumalai
Following change places each element of the
futex_queueshashtable 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.
Quoted 26 lines
Signed-off-by Ravikiran Thirumalai <[email protected]>Signed-off-by Shai Fultheim <[email protected]>Index:
linux-2.6.16-rc2/kernel/futex.c
===================================================================kernel/futex.c +3
-3@@ -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/
Signature · 2 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Quoted 4 lines · Andrew Morton
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
Quoted 8 lines · Nick Piggin
Quoted 4 lines · Ravikiran G Thirumalai
Following change places each element of the
futex_queueshashtable 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.
Quoted 8 lines · Nick Piggin
Quoted 4 lines · Ravikiran G Thirumalai
Following change places each element of the
futex_queueshashtable 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.
Quoted 4 lines
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
Quoted 3 lines · Christoph Lameter
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.
Quoted 7 lines · Ravikiran G Thirumalai
Quoted 5 lines · Nick Piggin
Quoted 2 lines · Ravikiran G Thirumalai
Following change places each element of the
futex_queueshashtable on a different cacheline. Spinlocks of adjacent hash buckets lie on the same cacheline otherwise.
Quoted 7 lines
Quoted 2 lines
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.)
Quoted 9 lines
Quoted 4 lines
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.
Quoted 6 lines
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.
Signature · 2 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Quoted 10 lines · Christoph Lameter
Quoted 7 lines · Nick Piggin
Quoted 4 lines · Ravikiran G Thirumalai
Following change places each element of the
futex_queueshashtable on a different cacheline. Spinlocks of adjacent hash buckets lie on the same cacheline otherwise.
Quoted 6 lines
Quoted 2 lines
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
Quoted 16 lines · Nick Piggin
Quoted 14 lines · Christoph Lameter
Quoted 9 lines · Nick Piggin
Quoted 4 lines · Ravikiran G Thirumalai
Following change places each element of the
futex_queueshashtable 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?
Quoted 8 lines
Quoted 4 lines
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...
Quoted 4 lines · Nick Piggin
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 ;)
Quoted 22 lines · Andrew Morton
Quoted 21 lines · Nick Piggin
Quoted 18 lines · Christoph Lameter
Quoted 9 lines · Nick Piggin
Quoted 4 lines · Ravikiran G Thirumalai
Following change places each element of the
futex_queueshashtable 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.
Quoted 7 lines
Quoted 3 lines
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
Quoted 11 lines · Andrew Morton
Quoted 3 lines · Nick Piggin
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.
Signature · 2 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Quoted 13 lines · Nick Piggin
Quoted 11 lines · Andrew Morton
Quoted 3 lines · Nick Piggin
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...
Quoted 7 lines
We chould probably also convert the
list_headover to anhlist_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
Quoted 4 lines · Ravikiran G Thirumalai
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?
Quoted 9 lines · Ravikiran G Thirumalai
Quoted 7 lines · Andrew Morton
Quoted 4 lines · Ravikiran G Thirumalai
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()tohash_long().
Quoted 8 lines
OK, I will try that.
Quoted 3 lines
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