* [RFC][PATCH RT 1/2] futex_requeue-optimize
@ 2006-05-10 9:27 Sébastien Dugué
2006-05-11 16:15 ` Andrew Morton
0 siblings, 1 reply; 9+ messages in thread
From: Sébastien Dugué @ 2006-05-10 9:27 UTC (permalink / raw)
To: LKML; +Cc: Ingo Molnar, Thomas Gleixner, Andrew Morton
In futex_requeue(), when the 2 futexes keys hash to the same bucket, there
is no need to move the futex_q to the end of the bucket list.
futex.c | 13 ++++++++-----
1 files changed, 8 insertions(+), 5 deletions(-)
Signed-off-by: Sébastien Dugué <sebastien.dugue@bull.net>
Index: linux-2.6.16-rt20/kernel/futex.c
===================================================================
--- linux-2.6.16-rt20.orig/kernel/futex.c 2006-05-04 10:58:38.000000000 +0200
+++ linux-2.6.16-rt20/kernel/futex.c 2006-05-04 10:58:55.000000000 +0200
@@ -835,17 +835,20 @@ static int futex_requeue(u32 __user *uad
if (++ret <= nr_wake) {
wake_futex(this);
} else {
- list_move_tail(&this->list, &hb2->chain);
- this->lock_ptr = &hb2->lock;
+ /*
+ * If key1 and key2 hash to the same bucket, no
+ * need to requeue.
+ */
+ if (likely(head1 != &hb2->chain)) {
+ list_move_tail(&this->list, &hb2->chain);
+ this->lock_ptr = &hb2->lock;
+ }
this->key = key2;
get_key_refs(&key2);
drop_count++;
if (ret - nr_wake >= nr_requeue)
break;
- /* Make sure to stop if key1 == key2: */
- if (head1 == &hb2->chain && head1 != &next->list)
- head1 = &this->list;
}
}
^ permalink raw reply [flat|nested] 9+ messages in thread* Re: [RFC][PATCH RT 1/2] futex_requeue-optimize
2006-05-10 9:27 [RFC][PATCH RT 1/2] futex_requeue-optimize Sébastien Dugué
@ 2006-05-11 16:15 ` Andrew Morton
2006-05-12 6:32 ` Ingo Molnar
2006-05-12 8:09 ` Sébastien Dugué
0 siblings, 2 replies; 9+ messages in thread
From: Andrew Morton @ 2006-05-11 16:15 UTC (permalink / raw)
To: Sébastien Dugué; +Cc: linux-kernel, mingo, tglx
Sébastien Dugué <sebastien.dugue@bull.net> wrote:
>
>
>
> In futex_requeue(), when the 2 futexes keys hash to the same bucket, there
> is no need to move the futex_q to the end of the bucket list.
>
> ...
>
> Index: linux-2.6.16-rt20/kernel/futex.c
> ===================================================================
> --- linux-2.6.16-rt20.orig/kernel/futex.c 2006-05-04 10:58:38.000000000 +0200
> +++ linux-2.6.16-rt20/kernel/futex.c 2006-05-04 10:58:55.000000000 +0200
> @@ -835,17 +835,20 @@ static int futex_requeue(u32 __user *uad
> if (++ret <= nr_wake) {
> wake_futex(this);
> } else {
> - list_move_tail(&this->list, &hb2->chain);
> - this->lock_ptr = &hb2->lock;
> + /*
> + * If key1 and key2 hash to the same bucket, no
> + * need to requeue.
> + */
> + if (likely(head1 != &hb2->chain)) {
> + list_move_tail(&this->list, &hb2->chain);
> + this->lock_ptr = &hb2->lock;
> + }
> this->key = key2;
> get_key_refs(&key2);
> drop_count++;
>
> if (ret - nr_wake >= nr_requeue)
> break;
> - /* Make sure to stop if key1 == key2: */
> - if (head1 == &hb2->chain && head1 != &next->list)
> - head1 = &this->list;
> }
> }
For some reason I get a reject when applying this. Which is odd, because I
see no differences in there. Oh well - please try to work out what went
wrong and double-check that the patch which I applied still makes sense.
Should the futex code be using hlist_heads for that hashtable?
^ permalink raw reply [flat|nested] 9+ messages in thread* Re: [RFC][PATCH RT 1/2] futex_requeue-optimize
2006-05-11 16:15 ` Andrew Morton
@ 2006-05-12 6:32 ` Ingo Molnar
2006-05-12 8:10 ` Sébastien Dugué
2006-05-12 8:09 ` Sébastien Dugué
1 sibling, 1 reply; 9+ messages in thread
From: Ingo Molnar @ 2006-05-12 6:32 UTC (permalink / raw)
To: Andrew Morton; +Cc: Sébastien Dugué, linux-kernel, tglx
* Andrew Morton <akpm@osdl.org> wrote:
> Should the futex code be using hlist_heads for that hashtable?
yeah. That would save 1K of .data on 32-bit platforms, 2K on 64-bit
platforms.
Ingo
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [RFC][PATCH RT 1/2] futex_requeue-optimize
2006-05-12 6:32 ` Ingo Molnar
@ 2006-05-12 8:10 ` Sébastien Dugué
2006-05-12 11:13 ` Sébastien Dugué
0 siblings, 1 reply; 9+ messages in thread
From: Sébastien Dugué @ 2006-05-12 8:10 UTC (permalink / raw)
To: Ingo Molnar; +Cc: Andrew Morton, linux-kernel, tglx
On Fri, 2006-05-12 at 08:32 +0200, Ingo Molnar wrote:
> * Andrew Morton <akpm@osdl.org> wrote:
>
> > Should the futex code be using hlist_heads for that hashtable?
>
> yeah. That would save 1K of .data on 32-bit platforms, 2K on 64-bit
> platforms.
I'll try to look into this.
Sébastien.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [RFC][PATCH RT 1/2] futex_requeue-optimize
2006-05-12 8:10 ` Sébastien Dugué
@ 2006-05-12 11:13 ` Sébastien Dugué
2006-05-12 11:12 ` Ingo Molnar
0 siblings, 1 reply; 9+ messages in thread
From: Sébastien Dugué @ 2006-05-12 11:13 UTC (permalink / raw)
To: Ingo Molnar; +Cc: Andrew Morton, linux-kernel, tglx
On Fri, 2006-05-12 at 10:10 +0200, Sébastien Dugué wrote:
> On Fri, 2006-05-12 at 08:32 +0200, Ingo Molnar wrote:
> > * Andrew Morton <akpm@osdl.org> wrote:
> >
> > > Should the futex code be using hlist_heads for that hashtable?
> >
> > yeah. That would save 1K of .data on 32-bit platforms, 2K on 64-bit
> > platforms.
>
> I'll try to look into this.
>
Well, moving the hash bucket list to an hlist may save a few bytes on
.data, but all the insertions are done at the tail on this list which
would not be easily done using hlists.
Any thoughts?
Sébastien.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [RFC][PATCH RT 1/2] futex_requeue-optimize
2006-05-12 11:13 ` Sébastien Dugué
@ 2006-05-12 11:12 ` Ingo Molnar
2006-05-12 13:16 ` Sébastien Dugué
0 siblings, 1 reply; 9+ messages in thread
From: Ingo Molnar @ 2006-05-12 11:12 UTC (permalink / raw)
To: Sébastien Dugué; +Cc: Andrew Morton, linux-kernel, tglx
* Sébastien Dugué <sebastien.dugue@bull.net> wrote:
> On Fri, 2006-05-12 at 10:10 +0200, Sébastien Dugué wrote:
> > On Fri, 2006-05-12 at 08:32 +0200, Ingo Molnar wrote:
> > > * Andrew Morton <akpm@osdl.org> wrote:
> > >
> > > > Should the futex code be using hlist_heads for that hashtable?
> > >
> > > yeah. That would save 1K of .data on 32-bit platforms, 2K on 64-bit
> > > platforms.
> >
> > I'll try to look into this.
> >
>
> Well, moving the hash bucket list to an hlist may save a few bytes
> on .data, but all the insertions are done at the tail on this list
> which would not be easily done using hlists.
>
> Any thoughts?
just queue to the head. This is a hash-list, ordering has only
performance effects.
Ingo
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [RFC][PATCH RT 1/2] futex_requeue-optimize
2006-05-12 11:12 ` Ingo Molnar
@ 2006-05-12 13:16 ` Sébastien Dugué
2006-05-12 13:40 ` Ingo Molnar
0 siblings, 1 reply; 9+ messages in thread
From: Sébastien Dugué @ 2006-05-12 13:16 UTC (permalink / raw)
To: Ingo Molnar; +Cc: Andrew Morton, linux-kernel, tglx
On Fri, 2006-05-12 at 13:12 +0200, Ingo Molnar wrote:
> * Sébastien Dugué <sebastien.dugue@bull.net> wrote:
>
> > On Fri, 2006-05-12 at 10:10 +0200, Sébastien Dugué wrote:
> > > On Fri, 2006-05-12 at 08:32 +0200, Ingo Molnar wrote:
> > > > * Andrew Morton <akpm@osdl.org> wrote:
> > > >
> > > > > Should the futex code be using hlist_heads for that hashtable?
> > > >
> > > > yeah. That would save 1K of .data on 32-bit platforms, 2K on 64-bit
> > > > platforms.
> > >
> > > I'll try to look into this.
> > >
> >
> > Well, moving the hash bucket list to an hlist may save a few bytes
> > on .data, but all the insertions are done at the tail on this list
> > which would not be easily done using hlists.
> >
> > Any thoughts?
>
> just queue to the head. This is a hash-list, ordering has only
> performance effects.
>
Queuing to the head would mean that tasks are woken up in LIFO order
(i.e. the last task put to sleep will be the first to be woken up).
I'm not sure that's what people would expect, or am I missing
something here?
Sébastien.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [RFC][PATCH RT 1/2] futex_requeue-optimize
2006-05-12 13:16 ` Sébastien Dugué
@ 2006-05-12 13:40 ` Ingo Molnar
0 siblings, 0 replies; 9+ messages in thread
From: Ingo Molnar @ 2006-05-12 13:40 UTC (permalink / raw)
To: Sébastien Dugué; +Cc: Andrew Morton, linux-kernel, tglx
* Sébastien Dugué <sebastien.dugue@bull.net> wrote:
> Queuing to the head would mean that tasks are woken up in LIFO order
> (i.e. the last task put to sleep will be the first to be woken up).
> I'm not sure that's what people would expect, or am I missing
> something here?
hm, indeed, you are right. So a double-linked list head it has to be.
Ingo
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [RFC][PATCH RT 1/2] futex_requeue-optimize
2006-05-11 16:15 ` Andrew Morton
2006-05-12 6:32 ` Ingo Molnar
@ 2006-05-12 8:09 ` Sébastien Dugué
1 sibling, 0 replies; 9+ messages in thread
From: Sébastien Dugué @ 2006-05-12 8:09 UTC (permalink / raw)
To: Andrew Morton; +Cc: linux-kernel, mingo, tglx
On Thu, 2006-05-11 at 09:15 -0700, Andrew Morton wrote:
> Sébastien Dugué <sebastien.dugue@bull.net> wrote:
> >
> >
> >
> > In futex_requeue(), when the 2 futexes keys hash to the same bucket, there
> > is no need to move the futex_q to the end of the bucket list.
> >
> > ...
> >
> For some reason I get a reject when applying this. Which is odd, because I
> see no differences in there. Oh well - please try to work out what went
> wrong and double-check that the patch which I applied still makes sense.
Yep, it's due to the futex_hash_bucket renaming from ->bh to ->hb that
went into pi-futex-futex-code-cleanups.patch from the PI-futex
patchset - no harm.
Sébastien.
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2006-05-12 13:40 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2006-05-10 9:27 [RFC][PATCH RT 1/2] futex_requeue-optimize Sébastien Dugué
2006-05-11 16:15 ` Andrew Morton
2006-05-12 6:32 ` Ingo Molnar
2006-05-12 8:10 ` Sébastien Dugué
2006-05-12 11:13 ` Sébastien Dugué
2006-05-12 11:12 ` Ingo Molnar
2006-05-12 13:16 ` Sébastien Dugué
2006-05-12 13:40 ` Ingo Molnar
2006-05-12 8:09 ` Sébastien Dugué
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).