[botan-devel] Threaded Filters/Operation Parallelisation

Joel Low joel at joelsplace.sg
Sun Feb 3 19:41:19 EST 2013


Hi Jack,

Sorry about not being able to work on this. It's on my to-do list but time
has been rather unforgiving recently. I'll work on it when time permits and
post again to the list.

Thanks!
Joel

-----Original Message-----
From: botan-devel [mailto:botan-devel-bounces at randombit.net] On Behalf Of
Jack Lloyd
Sent: Sunday, 3 February 2013 7:12 AM
To: Botan development list
Subject: Re: [botan-devel] Threaded Filters/Operation Parallelisation

Hi Joel,

I have not had a chance to test this as carefully as I would like from a
performance or correctness standpoint, but as it is isolated and completely
opt-in for the user it seems safe enough to include for further testing, so
I've checked this in to mainline and it will be in 1.11.2.

Unfortunately the patch as it currently is designed can't work for 1.10, as
it makes Filter::send virtual which is a (quite major) ABI change. I
designed and implemented the pipe/filter system over a decade ago
(terrifying...) and it was not really designed for extension in this (or any
other) way, so I'm actually surprised it only took one ABI change to make
this work.

Thanks again for your work on this. For the right application this could
make a huge difference, so having it available out of the box is a real
plus.

-Jack

On Thu, Jan 10, 2013 at 01:13:09AM +0000, Joel Low wrote:
> 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
> 





> _______________________________________________
> 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: smime.p7s
Type: application/pkcs7-signature
Size: 6053 bytes
Desc: not available
URL: <http://lists.randombit.net/pipermail/botan-devel/attachments/20130204/8b1227a1/attachment.p7s>


More information about the botan-devel mailing list