CodeSample: rwdeq
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
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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
PATCH 2/2 CodeSamples: add read/write solution to the deq example
In reply to Dominik DingelFrom: 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
@@ -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
Paul E. McKenney
AppliedQuoted 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 exampleCodeSamples/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.cSignature · 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
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
@@ -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
@@ -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.
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
Signed-off-by Paul E. McKenney <[email protected]>SMPdesign/partexercises.tex +9
-0@@ -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@@ -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.
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
DominikQuoted 48 lines
Thanx, Paul
------------------------------------------------------------------------
Add Quick Quiz for Dominik Dingel's solution
Signed-off-by Paul E. McKenney <[email protected]>SMPdesign/partexercises.tex +9
-0@@ -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@@ -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.
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
DominikQuoted 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
DominikQuoted 48 lines
Thanx, Paul
------------------------------------------------------------------------
Add Quick Quiz for Dominik Dingel's solution
Signed-off-by Paul E. McKenney <[email protected]>SMPdesign/partexercises.tex +9
-0@@ -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@@ -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.
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
DominikQuoted 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
DominikQuoted 53 lines
Quoted 52 lines
Thanks
DominikQuoted 48 lines
Thanx, Paul
------------------------------------------------------------------------
Add Quick Quiz for Dominik Dingel's solution
Signed-off-by Paul E. McKenney <[email protected]>SMPdesign/partexercises.tex +9
-0@@ -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@@ -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.