2.6.4 vs 2.6.4-mm1
These are some benchmarks on a 16-way (4x4) NUMAQ. Basically measures the scheduler patches with a couple of meaningless but very scheduler intensive benchmarks.
hackbench:
The number in () is a projection for the time 1000 would take, assuming a linear scaling. It is probably better shown on a graph, but you can see a non linear element in 2.6.4 that is basically absent in 2.6.4-mm1.
2.6.4 2.6.4-mm1 50 19.4 (388) 15.5 (310) 100 39.0 (390) 34.5 (345) 150 59.0 (393) 48.3 (322) 200 82.9 (414) 68.9 (344) 250 114.8 (459) 90.2 (360) 300 145.4 (484) 106.3 (354) 350 178.1 (508) 122.1 (348) 400 218.8 (547) 135.0 (337) 450 237.8 (528) 163.9 (364) 500 262.0 (524) 181.7 (363)
volanomark (MPS):
This one starts getting huge mmap_sem contention at 150+ coming from futexes. Don't know what is taking the mmap_sem for writing. Maybe just brk or mmap.
2.6.4 2.6.4-mm1 15 5850 6221 30 5682 5852 45 4736 5700 60 2857 5622 75 1024 4840 90 1832 5191 105 491 5036 120 1591 4228 135 393 4986 150 1056 1586
Quoted 4 lines · Nick Piggin
volanomark (MPS):
This one starts getting hugemmap_semcontention at 150+ coming from futexes. Don't know what is taking themmap_semfor writing. Maybe just brk or mmap.
are you sure it's down_write() contention? down_read() can create contention just as much, simply due to the fact that hundreds of threads and a dozen CPUs are pounding in on the same poor lock.
i do think there should be a rw-semaphore variant that is per-cpu for the read path. (This would also fix the 4:4 threading overhead.)
Ingo
Quoted 9 lines · Ingo Molnar
Quoted 5 lines · Nick Piggin
volanomark (MPS):
This one starts getting hugemmap_semcontention at 150+ coming from futexes. Don't know what is taking themmap_semfor writing. Maybe just brk or mmap.
Quoted 5 lines
are you sure it's
down_write()contention?down_read()can create contention just as much, simply due to the fact that hundreds of threads and a dozen CPUs are pounding in on the same poor lock.
No I'm not sure actually, it could be just read lock contention. IIRC it was all coming from the semaphore's spinlock, in up_read...
Quoted 4 lines
i do think there should be a rw-semaphore variant that is per-cpu for the read path. (This would also fix the 4:4 threading overhead.)
That would be interesting, yes. I have (somewhere) a patch that wakes up the semaphore's waiters outside its spinlock. I think that only gave about 5% or so improvement though.
Quoted 6 lines · Nick Piggin
That would be interesting, yes. I have (somewhere) a patch that wakes up the semaphore's waiters outside its spinlock. I think that only gave about 5% or so improvement though.
Here is a cleaned up patch for comments. It is untested at the moment because I don't have access to the 16-way NUMAQ now. It moves waking of the waiters outside the spinlock.
I think it gave about 5-10% improvement when the rwsem gets really contended. Not as much as I had hoped, but every bit helps.
The rwsem-spinlock.c code could use the same optimisation too.
Move rwsem's up_read wakeups out of the semaphore's wait_lock
linux-2.6-npiggin/lib/rwsem.c | 49 +++++++++++++++++++----------------------- 1 files changed, 23 insertions(+), 26 deletions(-)
lib/rwsem.c renamed from lib/rwsem.c~rwsem-scale +23 -26
@@ -35,13 +35,15 @@ void rwsemtrace(struct rw_semaphore *sem* - the spinlock must be held by the caller * - woken process blocks are discarded from the list after having flags zeroised * - writers are only woken if wakewrite is non-zero +* +* The spinlock will be dropped by this function */ static inline struct rw_semaphore *__rwsem_do_wake (struct rw_semaphore *sem,int wakewrite) { +LIST_HEAD (wake_list);struct rwsem_waiter *waiter; -struct list_head *next;signed long oldcount; -int woken, loop; +int woken;rwsemtrace (sem,"Entering __rwsem_do_wake" );
@@ -63,9 +65,8 @@ static inline struct rw_semaphore *__rwsif (!(waiter->flags &RWSEM_WAITING_FOR_WRITE )) goto readers_only; -list_del (&waiter->list); +list_move_tail (&waiter->list, &wake_list); waiter->flags =0 ; -wake_up_process (waiter->task); goto out;/* don't want to wake any writers */
@@ -74,13 +75,16 @@ static inline struct rw_semaphore *__rwsif (waiter->flags &RWSEM_WAITING_FOR_WRITE ) goto out; -/* grant an infinite number of read locks to the readers at the front of the queue -* - note we increment the 'active part' of the count by the number of readers (less one -* for the activity decrement we've already done) before waking any processes up +/* grant an infinite number of read locks to the readers at the front +* of the queue - note we increment the 'active part' of the count by +* the number of readers (less one for the activity decrement we've +* already done) before waking any processes up */ readers_only: woken =0 ; do { + list_move_tail(&waiter->list, &wake_list); + waiter->flags = 0; woken++; if (waiter->list.next==&sem->wait_list)
@@ -90,23 +94,17 @@ static inline struct rw_semaphore *__rws }while (waiter->flags &RWSEM_WAITING_FOR_READ ); - loop = woken; woken *=RWSEM_ACTIVE_BIAS -RWSEM_WAITING_BIAS ; woken -=RWSEM_ACTIVE_BIAS ;rwsem_atomic_add (woken,sem); - next = sem->wait_list.next; -for (; loop>0 ; loop--) { - waiter = list_entry(next,struct rwsem_waiter,list); - next = waiter->list.next; - waiter->flags =0 ; + out: +spin_unlock (&sem->wait_lock); +while (!list_empty (&wake_list)) { + waiter = list_entry(wake_list.next,struct rwsem_waiter,list); +list_del (&waiter->list);wake_up_process (waiter->task); } - - sem->wait_list.next = next; - next->prev = &sem->wait_list; - - out:rwsemtrace (sem,"Leaving __rwsem_do_wake" );return sem;
@@ -130,9 +128,8 @@ static inline struct rw_semaphore *rwsemset_task_state (tsk,TASK_UNINTERRUPTIBLE );/* set up my own style of waitqueue */ -spin_lock (&sem->wait_lock); waiter->task = tsk; - +spin_lock (&sem->wait_lock);list_add_tail (&waiter->list,&sem->wait_list);/* note that we're now waiting on the lock, but no longer actively read-locking */
@@ -143,8 +140,8 @@ static inline struct rw_semaphore *rwsem*/ if (!(count &RWSEM_ACTIVE_MASK )) sem =__rwsem_do_wake (sem,1 ); - -spin_unlock (&sem->wait_lock); +else +spin_unlock (&sem->wait_lock);/* wait to be given the lock */ for (;;) {
@@ -204,8 +201,8 @@ struct rw_semaphore fastcall *rwsem_wake/* do nothing if list empty */ if (!list_empty (&sem->wait_list)) sem =__rwsem_do_wake (sem,1 ); - -spin_unlock (&sem->wait_lock); +else +spin_unlock (&sem->wait_lock);rwsemtrace (sem,"Leaving rwsem_wake" );
@@ -226,8 +223,8 @@ struct rw_semaphore fastcall *rwsem_down/* do nothing if list empty */ if (!list_empty (&sem->wait_list)) sem =__rwsem_do_wake (sem,0 ); - -spin_unlock (&sem->wait_lock); +else +spin_unlock (&sem->wait_lock);rwsemtrace (sem,"Leaving rwsem_downgrade_wake" );return sem;
_
your patch looks interesting.
wrt. making a fully scalable MM read side:
perphaps RCU could be used to make lookup access to the vma tree and lookup of the pagetables lockless. This would make futexes (and pagefaults) fundamentally scalable.
another option would be to introduce a rwsem which is read-scalable, but this would pessimise writes quite as bad as brlocks did. I'm not sure how acceptable that is.
Ingo
Quoted 21 lines · Nick Piggin
Quoted 6 lines · Nick Piggin
That would be interesting, yes. I have (somewhere) a patch that wakes up the semaphore's waiters outside its spinlock. I think that only gave about 5% or so improvement though.
Here is a cleaned up patch for comments. It is untested at the moment because I don't have access to the 16-way NUMAQ now. It moves waking of the waiters outside the spinlock.
I think it gave about 5-10% improvement when the rwsem gets really contended. Not as much as I had hoped, but every bit helps.
The
rwsem-spinlock.ccode could use the same optimisation too.
Quoted 3 lines · Ingo Molnar
your patch looks interesting.
I'll see if I can get some numbers for it soon.
Quoted 11 lines
wrt. making a fully scalable MM read side:
perphaps RCU could be used to make lookup access to the vma tree and lookup of the pagetables lockless. This would make futexes (and pagefaults) fundamentally scalable.
another option would be to introduce a rwsem which is read-scalable, but this would pessimise writes quite as bad as brlocks did. I'm not sure how acceptable that is.
It is a pretty silly benchmark. But I guess one day someone is going to complain about mm scalability.