rwsem performance optimizations

For version 8 of the patchset, we included the patch from Waiman to streamline wakeup operations and also optimize the MCS lock used in rwsem and mutex.

Tim got the following improvement for exim mail server workload on 40 core system:

Alex+Tim's patchset: +4.8%
Alex+Tim+Waiman's patchset: +5.3%

Quoted 3 lines · Tim Chen

For version 8 of the patchset, we included the patch from Waiman to streamline wakeup operations and also optimize the MCS lock used in rwsem and mutex.

I'd be feeling a lot easier about this patch series if you also had performance figures that show how mmap_sem is affected.

These:

Quoted 5 lines

Tim got the following improvement for exim mail server workload on 40 core system:

Alex+Tim's patchset: +4.8%
Alex+Tim+Waiman's patchset: +5.3%

appear to be mostly related to the anon_vma->rwsem. But once that lock is changed to an rwlock_t, this measurement falls away.

Peter Zijlstra suggested the following testcase:

===============================>
In fact, try something like this from userspace:

n-threads:

  pthread_mutex_lock(&mutex);
  foo = mmap();
  pthread_mutex_lock(&mutex);

/* work */

  pthread_mutex_unlock(&mutex);
  munma(foo);
  pthread_mutex_unlock(&mutex);

vs

n-threads:

  foo = mmap();
  /* work */
  munmap(foo);

I've had reports that the former was significantly faster than the latter.
<===============================

this could be put into a standalone testcase, or you could add it as a new subcommand of 'perf bench', which already has some pthread code, see for example in tools/perf/bench/sched-messaging.c. Adding:

perf bench mm threads

or so would be a natural thing to have.

Thanks,

Ingo
--
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/

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Reviewed-by Ingo Molnar <[email protected]>

Reviewed-by Peter Zijlstra <[email protected]>

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcs_spinlock.h |   64 ++++++++++++++++++++++++++++++++++++++++++
 include/linux/mutex.h        |    5 ++-
 kernel/mutex.c               |   60 ++++----------------------------------
 3 files changed, 74 insertions(+), 55 deletions(-)
 create mode 100644 include/linux/mcs_spinlock.h

include/linux/mcs_spinlock.h new file +1 -0

new file mode 100644
index 0000000..b5de3b0
@@ -0,0 +1,64 @@
+/*

include/linux/mcs_spinlock.h new file +53 -0

+#ifndef __LINUX_MCS_SPINLOCK_H
+#define __LINUX_MCS_SPINLOCK_H
+
+struct mcs_spinlock {
+	struct mcs_spinlock *next;
+	int locked; /* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
+{
+	struct mcs_spinlock *prev;
+
+	/* Init node */
+	node->locked = 0;
+	node->next   = NULL;
+
+	prev = xchg(lock, node);
+	if (likely(prev == NULL)) {
+		/* Lock acquired */
+		node->locked = 1;
+		return;
+	}
+	ACCESS_ONCE(prev->next) = node;
+	smp_wmb();
+	/* Wait until the lock holder passes the lock down */
+	while (!ACCESS_ONCE(node->locked))
+		arch_mutex_cpu_relax();
+}
+
+static void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
+{
+	struct mcs_spinlock *next = ACCESS_ONCE(node->next);
+
+	if (likely(!next)) {
+		/*
+		 * Release the lock by setting it to NULL
+		 */
+		if (cmpxchg(lock, node, NULL) == node)
+			return;
+		/* Wait until the next pointer is set */
+		while (!(next = ACCESS_ONCE(node->next)))
+			arch_mutex_cpu_relax();
+	}
+	ACCESS_ONCE(next->locked) = 1;
+	smp_wmb();
+}
+
+#endif /* __LINUX_MCS_SPINLOCK_H */

include/linux/mutex.h +3 -2

index ccd4260..e6eaeea 100644
@@ -46,6 +46,7 @@
  * - detects multi-task circular deadlocks and prints out all affected
  *   locks and tasks (and only those tasks)
  */
+struct mcs_spinlock;
 struct mutex {
 	/* 1: unlocked, 0: locked, negative: locked, possible waiters */
 	atomic_t		count;

@@ -55,7 +56,7 @@ struct mutex {
 	struct task_struct	*owner;
 #endif
 #ifdef CONFIG_MUTEX_SPIN_ON_OWNER
-	void			*spin_mlock;	/* Spinner MCS lock */
+	struct mcs_spinlock	*mcs_lock;	/* Spinner MCS lock */
 #endif
 #ifdef CONFIG_DEBUG_MUTEXES
 	const char 		*name;

@@ -179,4 +180,4 @@ extern int atomic_dec_and_mutex_lock(atomic_t *cnt, struct mutex *lock);
 #define arch_mutex_cpu_relax()	cpu_relax()
 #endif
 
-#endif
+#endif /* __LINUX_MUTEX_H */

kernel/mutex.c +7 -53

index 6d647ae..4640731 100644
@@ -25,6 +25,7 @@
 #include <linux/spinlock.h>
 #include <linux/interrupt.h>
 #include <linux/debug_locks.h>
+#include <linux/mcs_spinlock.h>
 
 /*
  * In the DEBUG case we are using the "NULL fastpath" for mutexes,

@@ -52,7 +53,7 @@ __mutex_init(struct mutex *lock, const char *name, struct lock_class_key *key)
 	INIT_LIST_HEAD(&lock->wait_list);
 	mutex_clear_owner(lock);
 #ifdef CONFIG_MUTEX_SPIN_ON_OWNER
-	lock->spin_mlock = NULL;
+	lock->mcs_lock = NULL;
 #endif
 
 	debug_mutex_init(lock, name, key);

@@ -111,54 +112,7 @@ EXPORT_SYMBOL(mutex_lock);
  * more or less simultaneously, the spinners need to acquire a MCS lock
  * first before spinning on the owner field.
  *
- * We don't inline mspin_lock() so that perf can correctly account for the
- * time spent in this lock function.
  */
-struct mspin_node {
-	struct mspin_node *next ;
-	int		  locked;	/* 1 if lock acquired */
-};
-#define	MLOCK(mutex)	((struct mspin_node **)&((mutex)->spin_mlock))
-
-static noinline
-void mspin_lock(struct mspin_node **lock, struct mspin_node *node)
-{
-	struct mspin_node *prev;
-
-	/* Init node */
-	node->locked = 0;
-	node->next   = NULL;
-
-	prev = xchg(lock, node);
-	if (likely(prev == NULL)) {
-		/* Lock acquired */
-		node->locked = 1;
-		return;
-	}
-	ACCESS_ONCE(prev->next) = node;
-	smp_wmb();
-	/* Wait until the lock holder passes the lock down */
-	while (!ACCESS_ONCE(node->locked))
-		arch_mutex_cpu_relax();
-}
-
-static void mspin_unlock(struct mspin_node **lock, struct mspin_node *node)
-{
-	struct mspin_node *next = ACCESS_ONCE(node->next);
-
-	if (likely(!next)) {
-		/*
-		 * Release the lock by setting it to NULL
-		 */
-		if (cmpxchg(lock, node, NULL) == node)
-			return;
-		/* Wait until the next pointer is set */
-		while (!(next = ACCESS_ONCE(node->next)))
-			arch_mutex_cpu_relax();
-	}
-	ACCESS_ONCE(next->locked) = 1;
-	smp_wmb();
-}
 
 /*
  * Mutex spinning code migrated from kernel/sched/core.c

@@ -448,7 +402,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 
 	for (;;) {
 		struct task_struct *owner;
-		struct mspin_node  node;
+		struct mcs_spinlock  node;
 
 		if (!__builtin_constant_p(ww_ctx == NULL) && ww_ctx->acquired > 0) {
 			struct ww_mutex *ww;

@@ -470,10 +424,10 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 		 * If there's an owner, wait for it to either
 		 * release the lock or go to sleep.
 		 */
-		mspin_lock(MLOCK(lock), &node);
+		mcs_spin_lock(&lock->mcs_lock, &node);
 		owner = ACCESS_ONCE(lock->owner);
 		if (owner && !mutex_spin_on_owner(lock, owner)) {
-			mspin_unlock(MLOCK(lock), &node);
+			mcs_spin_unlock(&lock->mcs_lock, &node);
 			goto slowpath;
 		}
 

@@ -488,11 +442,11 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 			}
 
 			mutex_set_owner(lock);
-			mspin_unlock(MLOCK(lock), &node);
+			mcs_spin_unlock(&lock->mcs_lock, &node);
 			preempt_enable();
 			return 0;
 		}
-		mspin_unlock(MLOCK(lock), &node);
+		mcs_spin_unlock(&lock->mcs_lock, &node);
 
 		/*
 		 * When there's no owner, we might have preempted between the

Signature · 9 lines

1.7.4.4



--
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/

Quoted 22 lines · Tim Chen

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Reviewed-by Ingo Molnar <[email protected]>

Reviewed-by Peter Zijlstra <[email protected]>

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcs_spinlock.h |   64 ++++++++++++++++++++++++++++++++++++++++++
 include/linux/mutex.h        |    5 ++-
 kernel/mutex.c               |   60 ++++----------------------------------
 3 files changed, 74 insertions(+), 55 deletions(-)
 create mode 100644 include/linux/mcs_spinlock.h

include/linux/mcs_spinlock.h new file +1 -0

new file mode 100644
index 0000000..b5de3b0
@@ -0,0 +1,64 @@
+/*

include/linux/mcs_spinlock.h line 11

Quoted 10 lines

include/linux/mcs_spinlock.h new file +10 -0

+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ *
+ * The MCS lock (proposed by Mellor-Crummey and Scott) is a simple spin-lock
+ * with the desirable properties of being fair, and with each cpu trying
+ * to acquire the lock spinning on a local variable.
+ * It avoids expensive cache bouncings that common test-and-set spin-lock
+ * implementations incur.
+ */

nitpick:

I believe you need

+#include <asm/processor.h>

here, to avoid breaking the build when arch_mutex_cpu_relax() is not defined (arch/s390 is one case)

Quoted 36 lines · Rafael Aquini

Quoted 22 lines · Tim Chen

We will need the MCS lock code for doing optimistic spinning for rwsem. Extracting the MCS code from mutex.c and put into its own file allow us to reuse this code easily for rwsem.

Reviewed-by Ingo Molnar <[email protected]>

Reviewed-by Peter Zijlstra <[email protected]>

Signed-off-by Tim Chen <[email protected]>

Signed-off-by Davidlohr Bueso <[email protected]>

---
 include/linux/mcs_spinlock.h |   64 ++++++++++++++++++++++++++++++++++++++++++
 include/linux/mutex.h        |    5 ++-
 kernel/mutex.c               |   60 ++++----------------------------------
 3 files changed, 74 insertions(+), 55 deletions(-)
 create mode 100644 include/linux/mcs_spinlock.h

include/linux/mcs_spinlock.h new file +1 -0

new file mode 100644
index 0000000..b5de3b0
@@ -0,0 +1,64 @@
+/*

include/linux/mcs_spinlock.h line 11

Quoted 10 lines

include/linux/mcs_spinlock.h new file +10 -0

+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ *
+ * The MCS lock (proposed by Mellor-Crummey and Scott) is a simple spin-lock
+ * with the desirable properties of being fair, and with each cpu trying
+ * to acquire the lock spinning on a local variable.
+ * It avoids expensive cache bouncings that common test-and-set spin-lock
+ * implementations incur.
+ */

nitpick:

Quoted 6 lines

I believe you need

+#include <asm/processor.h>

here, to avoid breaking the build when arch_mutex_cpu_relax() is not defined (arch/s390 is one case)

Probably

+#include <linux/mutex.h>

should be added instead?
It defines arch_mutex_cpu_relax when there's no
architecture specific version.

Thanks.
Tim

Ingo,

I ran the vanilla kernel, the kernel with all rwsem patches and the kernel with all patches except the optimistic spin one. I am listing two presentations of the data. Please note that there is about 5% run-run variation.

% change in performance vs vanilla kernel
#threads all without optspin
mmap only
1 1.9% 1.6%
5 43.8% 2.6%
10 22.7% -3.0%
20 -12.0% -4.5%
40 -26.9% -2.0%
mmap with mutex acquisition
1 -2.1% -3.0%
5 -1.9% 1.0%
10 4.2% 12.5%
20 -4.1% 0.6%
40 -2.8% -1.9%

So I'd expect this to be a rather sensitive workload and you'd have to actively engineer it to hit the effect PeterZ mentioned. I could imagine MPI workloads to run into such patterns - but not deterministically.

Quoted 7 lines · Tim Chen

Ingo,

I ran the vanilla kernel, the kernel with all rwsem patches and the kernel with all patches except the optimistic spin one. I am listing two presentations of the data. Please note that there is about 5% run-run variation.

Quoted 14 lines

% change in performance vs vanilla kernel
#threads all without optspin
mmap only
1 1.9% 1.6%
5 43.8% 2.6%
10 22.7% -3.0%
20 -12.0% -4.5%
40 -26.9% -2.0%
mmap with mutex acquisition
1 -2.1% -3.0%
5 -1.9% 1.0%
10 4.2% 12.5%
20 -4.1% 0.6%
40 -2.8% -1.9%

Silly question: how do the two methods of starting N threads compare to each other?

Do they have identical runtimes?

I think PeterZ's point was
that the pthread_mutex case, despite adding extra serialization, actually runs faster in some circumstances.

Also, mind posting the testcase? What 'work' do the threads do - clear some memory area?

How big is the memory area?

I'd expect this to be about large enough mmap()s showing page fault processing to be mmap_sem bound and the serialization via pthread_mutex() sets up a 'train' of threads in one case, while the parallel startup would run into the mmap_sem in the regular case.

So I'd expect this to be a rather sensitive workload and you'd have to actively engineer it to hit the effect PeterZ mentioned. I could imagine MPI workloads to run into such patterns - but not deterministically.

Only once you've convinced yourself that you are hitting that kind of effect reliably on the vanilla kernel, could/should the effects of an improved rwsem implementation be measured.

Thanks,

Ingo
--
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/

The workload that I got the report from was a virus scanner, it would spawn nr_cpus threads and {mmap file, scan content, munmap} through your filesystem.

Quoted 4 lines · Peter Zijlstra

The workload that I got the report from was a virus scanner, it would spawn nr_cpus threads and {mmap file, scan content, munmap} through your filesystem.

So I suspect we could make the mmap_sem write area *much* smaller for the normal cases.

Look at do_mmap_pgoff(), for example: it is run entirely under mmap_sem, but 99% of what it does doesn't actually need the lock.

The part that really needs the lock is

        addr = get_unmapped_area(file, addr, len, pgoff, flags);
        addr = mmap_region(file, addr, len, vm_flags, pgoff);

but we hold it over all the other stuff too.

In fact, even if we moved the mmap_sem down into do_mmap(), and moved code around a bit to only hold it over those functions, it would still cover unnecessarily much. For example, while merging is common, not merging is pretty common too, and we do that

        vma = kmem_cache_zalloc(vm_area_cachep, GFP_KERNEL);

allocation under the lock. We could easily do things like preallocate it outside the lock.

The throughput of pure mmap with mutex is below vs pure mmap is below:

% change in performance of the mmap with pthread-mutex vs pure mmap
#threads vanilla all rwsem without optspin
patches

1               3.0%    	-1.0%   	-1.7%
5               7.2%    	-26.8%  	5.5%
10              5.2%    	-10.6%  	22.1%
20              6.8%    	16.4%   	12.5%
40              -0.2%   	32.7%   	0.0%

So with mutex, the vanilla kernel and the one without optspin both run faster. This is consistent with what Peter reported. With optspin, the picture is more mixed, with lower throughput at low to moderate number of threads and higher throughput with high number of threads.

% change in performance of the mmap with pthread-mutex vs pure mmap

#threads        vanilla all     without optspin
1               3.0%    -1.0%   -1.7%
5               7.2%    -26.8%  5.5%
10              5.2%    -10.6%  22.1%
20              6.8%    16.4%   12.5%
40              -0.2%   32.7%   0.0%

In general, vanilla and no-optspin case perform better with pthread-mutex. For the case with optspin, mmap with pthread-mutex is worse at low to moderate contention and better at high contention.

Quoted 11 lines · Tim Chen

The throughput of pure mmap with mutex is below vs pure mmap is below:

% change in performance of the mmap with pthread-mutex vs pure mmap
#threads vanilla all rwsem without optspin
patches

1               3.0%    	-1.0%   	-1.7%
5               7.2%    	-26.8%  	5.5%
10              5.2%    	-10.6%  	22.1%
20              6.8%    	16.4%   	12.5%
40              -0.2%   	32.7%   	0.0%

Quoted 4 lines

So with mutex, the vanilla kernel and the one without optspin both run faster. This is consistent with what Peter reported. With optspin, the picture is more mixed, with lower throughput at low to moderate number of threads and higher throughput with high number of threads.

So, going back to your orignal table:

Quoted 11 lines

% change in performance of the mmap with pthread-mutex vs pure mmap

#threads        vanilla all     without optspin
1               3.0%    -1.0%   -1.7%
5               7.2%    -26.8%  5.5%
10              5.2%    -10.6%  22.1%
20              6.8%    16.4%   12.5%
40              -0.2%   32.7%   0.0%

In general, vanilla and no-optspin case perform better with pthread-mutex. For the case with optspin, mmap with pthread-mutex is worse at low to moderate contention and better at high contention.

it appears that 'without optspin' appears to be a pretty good choice - if it wasn't for that '1 thread' number, which, if I correctly assume is the uncontended case, is one of the most common usecases ...

How can the single-threaded case get slower? None of the patches should really cause noticeable overhead in the non-contended case. That looks weird.

It would also be nice to see the 2, 3, 4 thread numbers - those are the most common contention scenarios in practice - where do we see the first improvement in performance?

Also, it would be nice to include a noise/sttdev figure, it's really hard to tell whether -1.7% is statistically significant.

Quoted 40 lines · Ingo Molnar

Quoted 11 lines · Tim Chen

The throughput of pure mmap with mutex is below vs pure mmap is below:

% change in performance of the mmap with pthread-mutex vs pure mmap
#threads vanilla all rwsem without optspin
patches

1               3.0%    	-1.0%   	-1.7%
5               7.2%    	-26.8%  	5.5%
10              5.2%    	-10.6%  	22.1%
20              6.8%    	16.4%   	12.5%
40              -0.2%   	32.7%   	0.0%

Quoted 4 lines

So with mutex, the vanilla kernel and the one without optspin both run faster. This is consistent with what Peter reported. With optspin, the picture is more mixed, with lower throughput at low to moderate number of threads and higher throughput with high number of threads.

So, going back to your orignal table:

Quoted 11 lines

% change in performance of the mmap with pthread-mutex vs pure mmap

#threads        vanilla all     without optspin
1               3.0%    -1.0%   -1.7%
5               7.2%    -26.8%  5.5%
10              5.2%    -10.6%  22.1%
20              6.8%    16.4%   12.5%
40              -0.2%   32.7%   0.0%

In general, vanilla and no-optspin case perform better with pthread-mutex. For the case with optspin, mmap with pthread-mutex is worse at low to moderate contention and better at high contention.

it appears that 'without optspin' appears to be a pretty good choice - if it wasn't for that '1 thread' number, which, if I correctly assume is the uncontended case, is one of the most common usecases ...

How can the single-threaded case get slower? None of the patches should really cause noticeable overhead in the non-contended case. That looks weird.

Quoted 6 lines

It would also be nice to see the 2, 3, 4 thread numbers - those are the most common contention scenarios in practice - where do we see the first improvement in performance?

Also, it would be nice to include a noise/sttdev figure, it's really hard to tell whether -1.7% is statistically significant.

Ingo,

I think that the optimistic spin changes to rwsem should enhance performance to real workloads after all.

In my previous tests, I was doing mmap followed immediately by munmap without doing anything to the memory. No real workload will behave that way and it is not the scenario that we should optimize for. A much better approximation of real usages will be doing mmap, then touching
the memories being mmaped, followed by munmap.

This changes the dynamics of the rwsem as we are now dominated by read acquisitions of mmap sem due to the page faults, instead of having only write acquisitions from mmap. [...]

[...] In this case, any delay in write acquisitions will be costly as we will be blocking a lot of readers. This is where optimistic spinning on write acquisitions of mmap sem can provide a very significant boost to the throughput.

I change the test case to the following with writes to the mmaped memory:

#define MEMSIZE (1 * 1024 * 1024)

char *testcase_description = "Anonymous memory mmap/munmap of 1MB";

void testcase(unsigned long long *iterations)

{
        int i;

        while (1) {
                char *c = mmap(NULL, MEMSIZE, PROT_READ|PROT_WRITE,
                               MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
                assert(c != MAP_FAILED);
                for (i=0; i<MEMSIZE; i+=8) {
                        c[i] = 0xa;
                }
                munmap(c, MEMSIZE);

                (*iterations)++;
        }
}

I compare the throughput where I have the complete rwsem patchset against vanilla and the case where I take out the optimistic spin patch. I have increased the run time by 10x from my pervious experiments and do 10 runs for each case. The standard deviation is ~1.5% so any changes under 1.5% is statistically significant.

% change in throughput vs the vanilla kernel.
Threads all No-optspin
1 +0.4% -0.1%
2 +2.0% +0.2%
3 +1.1% +1.5%
4 -0.5% -1.4%
5 -0.1% -0.1%
10 +2.2% -1.2%
20 +237.3% -2.3%
40 +548.1% +0.3%

Now when I test the case where we acquire mutex in the user space before mmap, I got the following data versus vanilla kernel. There's little contention on mmap sem acquisition in this case.

n all No-optspin
1 +0.8% -1.2%
2 +1.0% -0.5%
3 +1.8% +0.2%
4 +1.5% -0.4%
5 +1.1% +0.4%
10 +1.5% -0.3%
20 +1.4% -0.2%
40 +1.3% +0.4%

Thanks.

Quoted 53 lines · Tim Chen

Quoted 40 lines · Ingo Molnar

Quoted 11 lines · Tim Chen

The throughput of pure mmap with mutex is below vs pure mmap is below:

% change in performance of the mmap with pthread-mutex vs pure mmap
#threads vanilla all rwsem without optspin
patches

1               3.0%    	-1.0%   	-1.7%
5               7.2%    	-26.8%  	5.5%
10              5.2%    	-10.6%  	22.1%
20              6.8%    	16.4%   	12.5%
40              -0.2%   	32.7%   	0.0%

Quoted 4 lines

So with mutex, the vanilla kernel and the one without optspin both run faster. This is consistent with what Peter reported. With optspin, the picture is more mixed, with lower throughput at low to moderate number of threads and higher throughput with high number of threads.

So, going back to your orignal table:

Quoted 11 lines

% change in performance of the mmap with pthread-mutex vs pure mmap

#threads        vanilla all     without optspin
1               3.0%    -1.0%   -1.7%
5               7.2%    -26.8%  5.5%
10              5.2%    -10.6%  22.1%
20              6.8%    16.4%   12.5%
40              -0.2%   32.7%   0.0%

In general, vanilla and no-optspin case perform better with pthread-mutex. For the case with optspin, mmap with pthread-mutex is worse at low to moderate contention and better at high contention.

it appears that 'without optspin' appears to be a pretty good choice - if it wasn't for that '1 thread' number, which, if I correctly assume is the uncontended case, is one of the most common usecases ...

How can the single-threaded case get slower? None of the patches should really cause noticeable overhead in the non-contended case. That looks weird.

Quoted 6 lines

It would also be nice to see the 2, 3, 4 thread numbers - those are the most common contention scenarios in practice - where do we see the first improvement in performance?

Also, it would be nice to include a noise/sttdev figure, it's really hard to tell whether -1.7% is statistically significant.

Ingo,

I think that the optimistic spin changes to rwsem should enhance performance to real workloads after all.

Quoted 6 lines

In my previous tests, I was doing mmap followed immediately by munmap without doing anything to the memory. No real workload will behave that way and it is not the scenario that we should optimize for. A much better approximation of real usages will be doing mmap, then touching
the memories being mmaped, followed by munmap.

That's why I asked for a working testcase to be posted ;-) Not just pseudocode - send the real .c thing please.

Quoted 4 lines

This changes the dynamics of the rwsem as we are now dominated by read acquisitions of mmap sem due to the page faults, instead of having only write acquisitions from mmap. [...]

Absolutely, the page fault read case is the #1 optimization target of rwsems.

Quoted 13 lines

[...] In this case, any delay in write acquisitions will be costly as we will be blocking a lot of readers. This is where optimistic spinning on write acquisitions of mmap sem can provide a very significant boost to the throughput.

I change the test case to the following with writes to the mmaped memory:

#define MEMSIZE (1 * 1024 * 1024)

char *testcase_description = "Anonymous memory mmap/munmap of 1MB";

void testcase(unsigned long long *iterations)

Quoted 15 lines

{
        int i;

        while (1) {
                char *c = mmap(NULL, MEMSIZE, PROT_READ|PROT_WRITE,
                               MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
                assert(c != MAP_FAILED);
                for (i=0; i<MEMSIZE; i+=8) {
                        c[i] = 0xa;
                }
                munmap(c, MEMSIZE);

                (*iterations)++;
        }
}

It would be _really_ nice to stick this into tools/perf/bench/ as:

perf bench mem pagefaults

or so, with a number of parallelism and workload patterns. See tools/perf/bench/numa.c for a couple of workload generators - although those are not page fault intense.

So that future generations can run all these tests too and such.

Quoted 7 lines

I compare the throughput where I have the complete rwsem patchset against vanilla and the case where I take out the optimistic spin patch. I have increased the run time by 10x from my pervious experiments and do 10 runs for each case. The standard deviation is ~1.5% so any changes under 1.5% is statistically significant.

Quoted 10 lines

% change in throughput vs the vanilla kernel.
Threads all No-optspin
1 +0.4% -0.1%
2 +2.0% +0.2%
3 +1.1% +1.5%
4 -0.5% -1.4%
5 -0.1% -0.1%
10 +2.2% -1.2%
20 +237.3% -2.3%
40 +548.1% +0.3%

The tail is impressive. The early parts are important as well, but it's really hard to tell the significance of the early portion without having an sttdev column.

( "perf stat --repeat N" will give you sttdev output, in handy percentage
form. )

Quoted 14 lines

Now when I test the case where we acquire mutex in the user space before mmap, I got the following data versus vanilla kernel. There's little contention on mmap sem acquisition in this case.

n all No-optspin
1 +0.8% -1.2%
2 +1.0% -0.5%
3 +1.8% +0.2%
4 +1.5% -0.4%
5 +1.1% +0.4%
10 +1.5% -0.3%
20 +1.4% -0.2%
40 +1.3% +0.4%

Quoted 2 lines

Thanks.

A bit hard to see as there's no comparison _between_ the pthread_mutex and plain-parallel versions. No contention isn't a great result if performance suffers because it's all serialized.

It would be _really_ nice to stick this into tools/perf/bench/ as:

perf bench mem pagefaults

or so, with a number of parallelism and workload patterns. See tools/perf/bench/numa.c for a couple of workload generators - although those are not page fault intense.

So that future generations can run all these tests too and such.

Quoted 6 lines

I compare the throughput where I have the complete rwsem patchset against vanilla and the case where I take out the optimistic spin patch. I have increased the run time by 10x from my pervious experiments and do 10 runs for each case. The standard deviation is ~1.5% so any changes under 1.5% is statistically significant.

Quoted 10 lines

% change in throughput vs the vanilla kernel.
Threads all No-optspin
1 +0.4% -0.1%
2 +2.0% +0.2%
3 +1.1% +1.5%
4 -0.5% -1.4%
5 -0.1% -0.1%
10 +2.2% -1.2%
20 +237.3% -2.3%
40 +548.1% +0.3%

The tail is impressive. The early parts are important as well, but it's really hard to tell the significance of the early portion without having an sttdev column.

( "perf stat --repeat N" will give you sttdev output, in handy percentage
form. )

Quoted 29 lines

It would be _really_ nice to stick this into tools/perf/bench/ as:

perf bench mem pagefaults

or so, with a number of parallelism and workload patterns. See tools/perf/bench/numa.c for a couple of workload generators - although those are not page fault intense.

So that future generations can run all these tests too and such.

Quoted 16 lines

I compare the throughput where I have the complete rwsem patchset against vanilla and the case where I take out the optimistic spin patch. I have increased the run time by 10x from my pervious experiments and do 10 runs for each case. The standard deviation is ~1.5% so any changes under 1.5% is statistically significant.

% change in throughput vs the vanilla kernel.
Threads all No-optspin
1 +0.4% -0.1%
2 +2.0% +0.2%
3 +1.1% +1.5%
4 -0.5% -1.4%
5 -0.1% -0.1%
10 +2.2% -1.2%
20 +237.3% -2.3%
40 +548.1% +0.3%

Quoted 6 lines

The tail is impressive. The early parts are important as well, but it's really hard to tell the significance of the early portion without having an sttdev column.

( "perf stat --repeat N" will give you sttdev output, in handy percentage
form. )

Quick naive question as I haven't hacked perf bench before.

Now perf stat gives the statistics of the performance counter or events. How do I get it to compute the stats of
the throughput reported by perf bench?

Something like

perf stat -r 10 -- perf bench mm memset --iterations 10

doesn't quite give what I need.