[botan-devel] Threaded Filters/Operation Parallelisation

Jack Lloyd lloyd at randombit.net
Wed Jan 9 17:48:40 EST 2013


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 --------------
/*
* (C) 2009,2013 Jack Lloyd
*
* Distributed under the terms of the Botan license
*/

#include <fstream>
#include <iostream>
#include <string>
#include <botan/botan.h>

int main(int argc, char* argv[])
   {
   Botan::LibraryInitializer init;

   const std::vector<std::string> hashes = { "SHA-512", "Keccak-1600", "Skein-512" };

   std::vector<Botan::Filter*> filters;

   for(auto hash : hashes)
      {
      filters.push_back(new Botan::Chain(
                           new Botan::Hash_Filter(hash),
                           new Botan::Hex_Encoder));
      }

#if 0
   typedef Botan::Fork ForkImpl;
#else
   typedef Botan::Threaded_Fork ForkImpl;
#endif

   Botan::Pipe pipe(new ForkImpl(&filters[0], filters.size()));

   pipe.start_msg();

   Botan::AutoSeeded_RNG rng;
   auto buf = rng.random_vec(1024);

   const size_t desired_bytes = 100 * 1024 * 1024;
   size_t bytes = 0;

   while(bytes < desired_bytes)
      {
      pipe.write(&buf[0], buf.size());
      bytes += buf.size();
      }

   pipe.end_msg();

   return 0;
   }


More information about the botan-devel mailing list