On Thu, Aug 20, 2015 at 07:36:14PM +0200, Dominik Dingel wrote:
> 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?
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.
> > 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
> 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
