Skip to contentSkip to conversation

CodeSample: rwdeq

PATCH Applied Dominik Dingel 2 participants 9 messages Aug 12, 2015 – Aug 21, 2015

lore
Share & tools
lore
#0 lore raw

cover CodeSample: rwdeq

From: Dominik Dingel <[email protected]>

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

Dominik Dingel (2):
CodeSamples: Fix compiler warnings
CodeSamples: add read/write solution to the deq example

 CodeSamples/SMPdesign/Makefile       |   5 +-
 CodeSamples/SMPdesign/deqtorture.h   |   2 +-
 CodeSamples/SMPdesign/lockrwdeq.c    | 154 +++++++++++++++++++++++++++++++++++
 CodeSamples/SMPdesign/locktdeq.c     |   4 -
 CodeSamples/SMPdesign/matmul.c       |   3 +-
 CodeSamples/SMPdesign/matmul_block.c |   3 +-
 CodeSamples/SMPdesign/smpalloc.c     |   1 -
 7 files changed, 163 insertions(+), 9 deletions(-)
 create mode 100644 CodeSamples/SMPdesign/lockrwdeq.c
Signature · 1 line
1.9.1
#1 lore raw

PATCH 1/2 CodeSamples: Fix compiler warnings

From: Dominik Dingel <[email protected]>

Remove unreferenced variables, add necessary returns, make compiler happy.

---
 CodeSamples/SMPdesign/deqtorture.h   | 2 +-
 CodeSamples/SMPdesign/locktdeq.c     | 4 ----
 CodeSamples/SMPdesign/matmul.c       | 3 ++-
 CodeSamples/SMPdesign/matmul_block.c | 3 ++-
 CodeSamples/SMPdesign/smpalloc.c     | 1 -
 5 files changed, 5 insertions(+), 8 deletions(-)
CodeSamples/SMPdesign/deqtorture.h +1 -1
index 4def9d7..61ea70a 100644
@@ -482,7 +482,6 @@ int main(int argc, char *argv[])
 	int d1, d2, d3, d4;
 	struct deq_elem e1, e2, e3;
 	int i;
-	struct cds_list_head *p;
 	struct pdeq deq;
 
 	init_pdeq(&deq);
@@ -546,4 +545,5 @@ int main(int argc, char *argv[])
 	for (i = 0; i < 10; i++) {
 		pdeq_perf();
 	}
+	return 0;
 }
CodeSamples/SMPdesign/locktdeq.c +0 -4
index 20bdb85..0375902 100644
@@ -140,8 +140,6 @@ struct cds_list_head *pdeq_pop_r(struct pdeq *d)
 
 void pdeq_push_l(struct cds_list_head *e, struct pdeq *d)
 {
-	int i;
-
 	spin_lock(&d->llock);
 	deq_push_l(e, &d->ldeq);
 	spin_unlock(&d->llock);
@@ -149,8 +147,6 @@ void pdeq_push_l(struct cds_list_head *e, struct pdeq *d)
 
 void pdeq_push_r(struct cds_list_head *e, struct pdeq *d)
 {
-	int i;
-
 	spin_lock(&d->rlock);
 	deq_push_r(e, &d->rdeq);
 	spin_unlock(&d->rlock);
CodeSamples/SMPdesign/matmul.c +2 -1
index 13a7d46..96ed9ef 100644
@@ -53,11 +53,12 @@ void *matmul_thread(void *me_in)
 		}
 
 	atomic_inc(&ndone);
+	return NULL;
 }
 
 int main(int argc, char *argv[])
 {
-	int i, j, k;
+	int i, j;
 	long long startcreatetime;
 	long long starttime;
 	long long endtime;
CodeSamples/SMPdesign/matmul_block.c +2 -1
index 7ed0d52..2ed38ca 100644
@@ -58,11 +58,12 @@ void *matmul_thread(void *band_in)
 		}
 
 	atomic_inc(&ndone);
+	return NULL;
 }
 
 int main(int argc, char *argv[])
 {
-	int i, j, k;
+	int i, j;
 	struct band *bands;
 	int bandsize;
 	long long startcreatetime;
CodeSamples/SMPdesign/smpalloc.c +0 -1
index f6250ef..5b1f5b6 100644
@@ -156,7 +156,6 @@ void usage(char *progname)
 int main(int argc, char *argv[])
 {
 	int i;
-	struct memblock *p[2 * TARGET_POOL_SIZE] = { 0 };
 	long long nc;
 	long long nf;
 	int nkids = 1;
Signature · 1 line
1.9.1
#2 lore raw

PATCH 2/2 CodeSamples: add read/write solution to the deq example

In reply to Dominik Dingel

From: Dominik Dingel <[email protected]>

In addition to the split deque and the hashed deque there is now a solution working with an atomic counter and a read writer lock.

---
 CodeSamples/SMPdesign/Makefile    |   5 +-
 CodeSamples/SMPdesign/lockrwdeq.c | 154 ++++++++++++++++++++++++++++++++++++++
 2 files changed, 158 insertions(+), 1 deletion(-)
 create mode 100644 CodeSamples/SMPdesign/lockrwdeq.c
CodeSamples/SMPdesign/Makefile +4 -1
index fd042b9..80da412 100644
@@ -14,7 +14,7 @@
 #
 # Copyright (c) 2008 Paul E. McKenney, IBM Corporation.
 
-PROGS = smpalloc lockdeq lockhdeq locktdeq matmul matmul_block
+PROGS = smpalloc lockdeq lockhdeq locktdeq lockrwdeq matmul matmul_block
 
 all: $(PROGS)
 
@@ -37,6 +37,9 @@ lockhdeq: lockhdeq.c deqtorture.h ../api.h
 locktdeq: locktdeq.c deqtorture.h ../api.h
 	cc $(GCC_ARGS) -g -o locktdeq -DTEST locktdeq.c -lpthread
 
+lockrwdeq: lockrwdeq.c deqtorture.h ../api.h
+	cc $(GCC_ARGS) -g -o lockrwdeq -DTEST lockrwdeq.c -lpthread
+
 matmul: matmul.c ../api.h
 	cc $(GCC_ARGS) -g -o matmul -DTEST matmul.c -lpthread
 
CodeSamples/SMPdesign/lockrwdeq.c new file +154 -0

154 lines not on this page · raw message

Signature · 1 line
1.9.1
#3 lore raw
In reply to Dominik Dingel
Quoted 7 lines · Dominik Dingel

From: Dominik Dingel <[email protected]>

Hi all,

here is a somehow naive implementation of a reader/writer lock based approch for the parallel deq problem.

Quoted 7 lines

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.

Thanx, Paul

Quoted 22 lines

Dominik Dingel (2):
CodeSamples: Fix compiler warnings
CodeSamples: add read/write solution to the deq example

 CodeSamples/SMPdesign/Makefile       |   5 +-
 CodeSamples/SMPdesign/deqtorture.h   |   2 +-
 CodeSamples/SMPdesign/lockrwdeq.c    | 154 +++++++++++++++++++++++++++++++++++
 CodeSamples/SMPdesign/locktdeq.c     |   4 -
 CodeSamples/SMPdesign/matmul.c       |   3 +-
 CodeSamples/SMPdesign/matmul_block.c |   3 +-
 CodeSamples/SMPdesign/smpalloc.c     |   1 -
 7 files changed, 163 insertions(+), 9 deletions(-)
 create mode 100644 CodeSamples/SMPdesign/lockrwdeq.c
Signature · 6 lines
1.9.1

--
To unsubscribe from this list: send the line "unsubscribe perfbook" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
#4 lore raw
Quoted 16 lines · Paul E. McKenney
Quoted 7 lines · Dominik Dingel

From: Dominik Dingel <[email protected]>

Hi all,

here is a somehow naive implementation of a reader/writer lock based approch for the parallel deq problem.

Quoted 7 lines

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

Quoted 6 lines

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

SMPdesign/partexercises.tex +9 -0
index a44c285ce134..5d46e70028aa 100644
@@ -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.
qqz.tex +8 -0
index 57cdc43f63d1..cfd0356854b7 100644
@@ -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.
#5 lore raw
Quoted 17 lines · On Sun, 16 Aug 2015 23:22:19 -0700 "Paul E. McKenney"…
Quoted 16 lines · Paul E. McKenney
Quoted 14 lines · Dominik Dingel

From: Dominik Dingel <[email protected]>

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

Quoted 6 lines
Quoted 6 lines

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.

Sounds good, during sniff tests I saw even slightly less performance than your hashed implementation.

Quoted 2 lines

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

Looks good! Thanks for putting it in.
My plan, as soon as I get to:
- Rework the section to start with my solution
- Show the disadvantages of my solution
-> Atomic and read/writer lock (resulting in bouncing cache lines)
- Show your tandem solution which will avoid that overhead and will only in the worst case really do synchronization of the complete data structure.

What do you think?

Thanks
Dominik

Quoted 48 lines

Thanx, Paul

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

Add Quick Quiz for Dominik Dingel's solution

SMPdesign/partexercises.tex +9 -0
index a44c285ce134..5d46e70028aa 100644
@@ -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.
qqz.tex +8 -0
index 57cdc43f63d1..cfd0356854b7 100644
@@ -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.
#6 lore raw
Quoted 20 lines · Dominik Dingel
Quoted 17 lines · On Sun, 16 Aug 2015 23:22:19 -0700 "Paul E. McKenney"…
Quoted 16 lines · Paul E. McKenney
Quoted 14 lines · Dominik Dingel

From: Dominik Dingel <[email protected]>

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

Quoted 8 lines
Quoted 6 lines
Quoted 6 lines

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.

Sounds good, during sniff tests I saw even slightly less performance than your hashed implementation.

It is probably possible to construct a workload that makes either look good or bad. ;-)

Quoted 11 lines
Quoted 2 lines

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

Looks good! Thanks for putting it in.
My plan, as soon as I get to:
- Rework the section to start with my solution
- Show the disadvantages of my solution
-> Atomic and read/writer lock (resulting in bouncing cache lines)
- Show your tandem solution which will avoid that overhead and will only in the worst case really do synchronization of the complete data structure.

Quoted 1 line

What do you think?

I was actually planning to push the hashed version to either a quick quiz or an appendix in order to make room for other sections to expand. One approach would be to put both your implementation and the hashed implementation in the "Important Questions" section for the second edition.

Later on, I am thinking in terms of a supplement of some sort, so that the main book stays at roughly 500 pages, but so that people can go look at additional material if they want. Thoughts?

Thanx, Paul

Quoted 52 lines

Thanks
Dominik

Quoted 48 lines

Thanx, Paul

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

Add Quick Quiz for Dominik Dingel's solution

SMPdesign/partexercises.tex +9 -0
index a44c285ce134..5d46e70028aa 100644
@@ -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.
qqz.tex +8 -0
index 57cdc43f63d1..cfd0356854b7 100644
@@ -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.
#7 lore raw
Quoted 44 lines · On Wed, 19 Aug 2015 14:22:03 -0700 "Paul E. McKenney"…
Quoted 20 lines · Dominik Dingel
Quoted 17 lines · On Sun, 16 Aug 2015 23:22:19 -0700 "Paul E. McKenney"…
Quoted 16 lines · Paul E. McKenney
Quoted 14 lines · Dominik Dingel

From: Dominik Dingel <[email protected]>

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

Quoted 8 lines
Quoted 6 lines
Quoted 6 lines

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.

Sounds good, during sniff tests I saw even slightly less performance than your hashed implementation.

It is probably possible to construct a workload that makes either look good or bad. ;-)

Quoted 11 lines
Quoted 2 lines

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

Looks good! Thanks for putting it in.
My plan, as soon as I get to:
- Rework the section to start with my solution
- Show the disadvantages of my solution
-> Atomic and read/writer lock (resulting in bouncing cache lines)
- Show your tandem solution which will avoid that overhead and will only in the worst case really do synchronization of the complete data structure.

Quoted 7 lines
Quoted 1 line

What do you think?

I was actually planning to push the hashed version to either a quick quiz or an appendix in order to make room for other sections to expand. One approach would be to put both your implementation and the hashed implementation in the "Important Questions" section for the second edition.

Sounds reasonable. You have any time for releasing in mind?

Quoted 5 lines

Later on, I am thinking in terms of a supplement of some sort, so that the main book stays at roughly 500 pages, but so that people can go look at additional material if they want. Thoughts?

Thanx, Paul

I encourage to go that way, so people really want to dive deep can do so, while at the same time you do not scare potential readers, right?

Thanks
Dominik

Quoted 53 lines
Quoted 52 lines

Thanks
Dominik

Quoted 48 lines

Thanx, Paul

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

Add Quick Quiz for Dominik Dingel's solution

SMPdesign/partexercises.tex +9 -0
index a44c285ce134..5d46e70028aa 100644
@@ -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.
qqz.tex +8 -0
index 57cdc43f63d1..cfd0356854b7 100644
@@ -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.
#8 lore raw
Quoted 49 lines · Dominik Dingel
Quoted 46 lines · On Wed, 19 Aug 2015 14:22:03 -0700 "Paul E. McKenney"…
Quoted 20 lines · Dominik Dingel
Quoted 17 lines · On Sun, 16 Aug 2015 23:22:19 -0700 "Paul E. McKenney"…
Quoted 16 lines · Paul E. McKenney
Quoted 14 lines · Dominik Dingel

From: Dominik Dingel <[email protected]>

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

Quoted 8 lines
Quoted 6 lines
Quoted 6 lines

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.

Sounds good, during sniff tests I saw even slightly less performance than your hashed implementation.

It is probably possible to construct a workload that makes either look good or bad. ;-)

Quoted 12 lines
Quoted 2 lines

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

Looks good! Thanks for putting it in.
My plan, as soon as I get to:
- Rework the section to start with my solution
- Show the disadvantages of my solution
-> Atomic and read/writer lock (resulting in bouncing cache lines)
- Show your tandem solution which will avoid that overhead and will only in the worst case really do synchronization of the complete data structure.

What do you think?

Quoted 7 lines
Quoted 5 lines

I was actually planning to push the hashed version to either a quick quiz or an appendix in order to make room for other sections to expand. One approach would be to put both your implementation and the hashed implementation in the "Important Questions" section for the second edition.

Sounds reasonable. You have any time for releasing in mind?

Well, there is a public git tree, so as soon as I get to make the changes. I don't yet have a firm date for the second edition, but probably a small number of years rather than months, depending on how some work leading up to it goes.

Quoted 6 lines
Quoted 4 lines

Later on, I am thinking in terms of a supplement of some sort, so that the main book stays at roughly 500 pages, but so that people can go look at additional material if they want. Thoughts?

I encourage to go that way, so people really want to dive deep can do so, while at the same time you do not scare potential readers, right?

Yep! Also, some people like a printed copy, and keeping the book under 500 pages keeps the printing costs reasonable.

Thanx, Paul

Quoted 57 lines

Thanks
Dominik

Quoted 53 lines
Quoted 52 lines

Thanks
Dominik

Quoted 48 lines

Thanx, Paul

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

Add Quick Quiz for Dominik Dingel's solution

SMPdesign/partexercises.tex +9 -0
index a44c285ce134..5d46e70028aa 100644
@@ -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.
qqz.tex +8 -0
index 57cdc43f63d1..cfd0356854b7 100644
@@ -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.