Re: [PATCH 0/2] CodeSample: rwdeq

["Paul E. McKenney" <paulmck@linux.vnet.ibm.com>]

On Thu, Aug 13, 2015 at 09:43:01AM -0700, Paul E. McKenney wrote:
> On Wed, Aug 12, 2015 at 09:55:22AM +0200, Dominik Dingel wrote:
> > From: Dominik Dingel <dingel@linux.vnet.ibm.com>
> > 
> > Hi all,
> > 
> > here is a somehow naive implementation of a reader/writer lock based approch
> > for the parallel deq problem.
> > 
> > The next step would be to use it as an introduction example in the text, as due
> > its way of implementation (taking always a read lock, working always with an
> > atomic counter) it is a less efficient way of doing things, compared with the
> > tandem approch. Then the benefits of partitioning might be even more obvious.
> > 
> > Thanks
> > 	Dominik
> 
> Queued, thank you, Dominik!
> 
> A quick unscientific run leads me to believe that this is slightly faster
> than the hashed implementation (not bad!), but about twice as slow as
> the tandem version.  Of course, considerable variation is to be expected
> based on workload.

And, as discussed earlier, here the commit adding a Quick Quiz referring
to your algorithm.  Thoughts?

							Thanx, Paul

------------------------------------------------------------------------

    Add Quick Quiz for Dominik Dingel's solution
    
    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

diff --git a/SMPdesign/partexercises.tex b/SMPdesign/partexercises.tex
index a44c285ce134..5d46e70028aa 100644
--- a/SMPdesign/partexercises.tex
+++ b/SMPdesign/partexercises.tex
@@ -683,6 +683,15 @@ Michael~\cite{DBLP:conf/europar/Michael03}.\footnote{
 	Instead, the common compare-and-swap (e.g., x86 cmpxchg)
 	suffices.}

+\QuickQuiz{}
+	Why are there not one but two solutions to the double-ended queue
+	problem?
+\QuickQuizAnswer{
+	There are actually at least three.
+	The third, by Dominik Dingel, makes interesting use of
+	reader-writer locking, and may be found in \co{lockrwdeq.c}.
+} \QuickQuizEnd
+
 In fact, as noted by Dice et al.~\cite{DavidDice:2010:SCA:HTM:deque},
 an unsynchronized single-threaded double-ended queue significantly
 outperforms any of the parallel implementations they studied.
diff --git a/qqz.tex b/qqz.tex
index 57cdc43f63d1..cfd0356854b7 100644
--- a/qqz.tex
+++ b/qqz.tex
@@ -2561,6 +2561,14 @@ ret = ~ret & tmp;
 	it is worthwhile) is left as an exercise for the reader.

 \QuickQ{}
+	Why are there not one but two solutions to the double-ended queue
+	problem?
+\QuickA{}
+	There are actually at least three.
+	The third, by Dominik Dingel, makes interesting use of
+	reader-writer locking, and may be found in \co{lockrwdeq.c}.
+
+\QuickQ{}
 	The tandem double-ended queue runs about twice as fast as
 	the hashed double-ended queue, even when I increase the
 	size of the hash table to an insanely large number.