[botan-devel] Threaded Filters/Operation Parallelisation

Joel Low joel at joelsplace.sg
Wed Jan 9 20:13:09 EST 2013


Thanks Jack for writing that test.

My program is pretty similar to that, just that mine deals directly with files 
and not a memory buffer, so your loop is much tighter than mine (no file I/O), 
exposing the race condition. I forgot to lock the mutex before notifying the 
workers, so it could have signalled while the workers were still busy.

I've attached the patch to apply *relative to the previous patch* so you'll 
have to apply that patch first, then this one to make v2 of the patch.

Regards,
Joel

-----Original Message-----
From: botan-devel [mailto:botan-devel-bounces at randombit.net] On Behalf Of Jack 
Lloyd
Sent: Thursday, 10 January 2013 6:49 AM
To: Botan development list
Subject: Re: [botan-devel] Threaded Filters/Operation Parallelisation

Hi Joel,

Can you take a look at the attached test and see if you notice anything wrong 
with it? It seems to deadlock on a Linux machine with 4 cores with your patch 
applied to mainline and compiled with gcc 4.7.0.

-Jack

On Mon, Jan 07, 2013 at 02:18:13PM +0000, Joel Low wrote:
> Hi Jack,
>
> Yes, it's to cache the size of m_threads. That's my practice when I
> know that the value is invariant, I think it's to help the compiler
> see that m_threads doesn't change its size throughout the execution of
> the loop, which hopefully allows it to produce better code. I think
> the inlining bit is secondary since IIRC the C++ standard does dictate
> the behaviour of the STL types.
>
> I've not tested it, and it could just be me being overly cautious (or
> pessimistic about my compiler). If your version fits the rest of the
> library better, then I think we should go with your style.
>
> Regards,
> Joel
>
> -----Original Message-----
> From: botan-devel [mailto:botan-devel-bounces at randombit.net] On Behalf
> Of Jack Lloyd
> Sent: Monday, 7 January 2013 8:10 PM
> To: Botan development list
> Subject: Re: [botan-devel] Threaded Filters/Operation Parallelisation
>
> Hi Joel,
>
> I'm curious about this loop in basefilt.cpp
>
>    for(size_t i = 0, j = m_threads.size(); i != j; ++i)
>       {
>       m_threads[i]->join();
>       }
>
> Is the intent here for j to simply cache m_threads.size()? Why not
> simply
>
>    for(size_t i = 0; i != m_threads.size(); ++i)
>
> as vector.size should be inlined and very fast.
>
> -Jack
>
>
> On Wed, Jan 02, 2013 at 11:01:12PM +0000, Joel Low wrote:
> > Thanks for the review, Jack.
> >
> > I've included the updated patch. Let me know if that works.
> >
> > Regards,
> > Joel
> >
> > -----Original Message-----
> > From: botan-devel [mailto:botan-devel-bounces at randombit.net] On
> > Behalf Of Jack Lloyd
> > Sent: Wednesday, 2 January 2013 11:49 PM
> > To: Botan development list
> > Subject: Re: [botan-devel] Threaded Filters/Operation
> > Parallelisation
> >
> > Hi Joel,
> >
> > I've only had time to very briefly review the patch but it looks good.
> >
> > A few minor comments:
> >
> > - Can you use an m_ prefix on all class members? I know a lot of the
> >   code doesn't use a prefix or suffix at all, but I am trying to
> >   ensure that all new or heavily touched code adopts m_ (rather than
> >   suffix _ as you use in Semaphore or no prefix).
> >
> > - Semaphore seems generally useful, move it to
> > src/util/semaphore.{cpp,h}
> >
> > - Add your name to the copyright headers of each modified file. (And
> >   make sure all new sources have one)
> >
> > - For some reason, despite all your work on Windows support and other
> >   patches, your name is not already included in the list of copyright
> >   owners in the license, so please also update license.rst
> >
> > Can you make those changes and send the updated patch as an
> > attachment to the list (so it can be archived by mailman)?
> >
> > Thanks,
> >   Jack
> >
> > On Wed, Jan 02, 2013 at 06:51:10AM +0000, Joel Low wrote:
> > > Hello all,
> > >
> > > So I've finally managed to sit down and write this patch. The
> > > design seems quite different from what I had in mind, since this
> > > round I wanted it to be a drop-in replacement for Fork.
> > >
> > > There's a bit of code taken from a blog post to emulate a semaphore:
> > > The link is there, and if someone knows of a better class (or
> > > better still, one within Botan itself), let me know and I'll use
> > > that class
> > instead.
> > >
> > > Let me know what you think.
> > >
> > > Patch: http://pastebin.com/kgF0b7Yp (1 month visibility)
> > >
> > > Regards,
> > > Joel
> > >
> > > -----Original Message-----
> > > From: botan-devel-bounces at randombit.net
> > > [mailto:botan-devel-bounces at randombit.net] On Behalf Of Joel Low
> > > Sent: Tuesday, 24 April 2012 5:07 PM
> > > To: botan-devel at randombit.net
> > > Subject: [botan-devel] Threaded Filters/Operation Parallelisation
> > >
> > > Hello all,
> > >
> > > Recently I've been playing with the idea of having a threaded Fork
> > > filter to be used together with Pipe: processing for each
> > > subsequent filter downstream of the threaded Fork filter is done
> > > in a separate thread of its own. This could potentially bring
> > > performance benefits (in theory) especially with a move on to
> > > having an increasing number of
> > computing cores per CPU.
> > >
> > > So I've emailed Jack separate to the list to get some of his opinions.
> > > The main points he raised were that:
> > >
> > >  - The approach used for Fork would be most promising in terms of
> > > working with the current design and not forcing a full rewrite of
> > > the
> > filter system.
> > >  - He proposed defining a new Filter subclass Threaded_Filter
> > > which itself takes a Filter* as an argument which will spawn a
> > > thread and uses two message queues for I/O with the filter it manages.
> > >  - When write() is called on the Threaded_Filter, it pushes it to
> > > the input queue, which the worker thread pulls off and write()s to
> > > the underlying filter.
> > >  - With this approach the application can control concurrency very
> > > finely (perhaps too finely), since the application can specify
> > > which filters run on the main thread, and what runs on a secondary 
> > > thread.
> > >
> > > I was leaning to a slightly different approach: with the knowledge
> > > that Fork operations parallelise the easiest, I should adapt the
> > > Fork class to let each downstream filter run in a separate thread.
> > > This shares much commonality in its design with Jack's idea
> > > (especially in terms of thread sync and friends), provides a
> > > little less control over what runs in a separate thread, but comes
> > > with a slightly easier
> > implementation.
> > >
> > > Jack stated that I probably should email the devel list and
> > > solicit ideas, since everyone may have different expectations.
> > > I'll be implementing this in my spare time so I'd like to accept
> > > as many ideas and combine them before acting on it. I think that
> > > the pipe/filter design Botan has is intuitive, and I'd like to
> > > keep that as much as possible, without compromising on potential
> > > performance
> gains.
> > > Intuitively, both seem to run contrary to each other, but I think
> > > we can work something out here to an API that is both powerful yet
> > > easily
> > mastered.
> > >
> > > Any thoughts?
> > >
> > > Regards,
> > > Joel
> > >
> >
> >
> >
> > > _______________________________________________
> > > botan-devel mailing list
> > > botan-devel at randombit.net
> > > http://lists.randombit.net/mailman/listinfo/botan-devel
> >
> > _______________________________________________
> > botan-devel mailing list
> > botan-devel at randombit.net
> > http://lists.randombit.net/mailman/listinfo/botan-devel
>
>
>
>
>
> > _______________________________________________
> > botan-devel mailing list
> > botan-devel at randombit.net
> > http://lists.randombit.net/mailman/listinfo/botan-devel
>
> _______________________________________________
> botan-devel mailing list
> botan-devel at randombit.net
> http://lists.randombit.net/mailman/listinfo/botan-devel



> _______________________________________________
> botan-devel mailing list
> botan-devel at randombit.net
> http://lists.randombit.net/mailman/listinfo/botan-devel

-------------- next part --------------
A non-text attachment was scrubbed...
Name: Hash v2.patch
Type: application/octet-stream
Size: 597 bytes
Desc: not available
URL: <http://lists.randombit.net/pipermail/botan-devel/attachments/20130110/61c8e268/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 6053 bytes
Desc: not available
URL: <http://lists.randombit.net/pipermail/botan-devel/attachments/20130110/61c8e268/attachment.p7s>


More information about the botan-devel mailing list