On Wed, 19 Aug 2015 14:22:03 -0700
"Paul E. McKenney" <paulmck@xxxxxxxxxxxxxxxxxx> wrote:
> On Wed, Aug 19, 2015 at 09:06:04PM +0200, Dominik Dingel wrote:
> > On Sun, 16 Aug 2015 23:22:19 -0700
> > "Paul E. McKenney" <paulmck@xxxxxxxxxxxxxxxxxx> wrote:
> >
> > > 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@xxxxxxxxxxxxxxxxxx>
> > > > >
> > > > > 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.
> >
> > 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. ;-)
>
> > > 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?
>
> 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?
> 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
> > Thanks
> > Dominik
> >
> > > Thanx, Paul
> > >
> > > ------------------------------------------------------------------------
> > >
> > > Add Quick Quiz for Dominik Dingel's solution
> > >
> > > Signed-off-by: Paul E. McKenney <paulmck@xxxxxxxxxxxxxxxxxx>
> > >
> > > 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.
> > >
> >
>
--
To unsubscribe from this list: send the line "unsubscribe perfbook" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
