Re: [boost] [threadpool] version 22 with default pool

Subject: Re: [boost] [threadpool] version 22 with default pool
From: Edouard A. (edouard_at_[hidden])
Date: 2009-03-08 14:48:11

I have implemented a parallel_sort that is a bit slower than tbb with
threadpool (see below for the code).

Benchmark results:

                    std::fill 0..1000000 ok : 1 elapsed: 0.01
       tbb::parallel_for fill 0..1000000 ok : 1 elapsed: 0.01
            std::sort reverse 0..1000000 ok : 1 elapsed: 0.11
   tbb::parallel_sort reverse 0..1000000 ok : 1 elapsed: 0.037
      boost::tp::sort reverse 0..1000000 ok : 1 elapsed: 0.048

Machine: Q6600 - 4 GiB Ram - Running Vista 64 - x64 release build with full
optimizations.

Some remarks:

 * shutdown() renders the thread pool unusable (marks it terminated). This
is not what I was looking for. Ideally, a wait() method that just waits for
the pool to have no tasks left to process would be better. I would find it
cumbersome to manually wait for the result of each task. My 2c.
 * It's difficult to properly benchmark the two on my development machine
that is probably using one core to do things background work
 * Instrumentation seems to show that the _entry method of the pool is
extremely slow. I have not investigated further.
 * boost::tp::sort benchmark includes thread destruction... Probably eats up
some micro secs
 * My code is probably sub-optimal

The code:

template <typename RandomIterator>
RandomIterator pivot_partition(RandomIterator first, RandomIterator last)
{
        typedef RandomIterator iterator_type;
        typedef typename iterator_type::difference_type difference_type;
        typedef typename iterator_type::value_type value_type;

        iterator_type pivot = first + std::distance(first, last) / 2;

        // we partition
        value_type pivot_value = *pivot;

        // we "save" the pivot in putting it to the first place
        std::iter_swap(first, pivot);

        // we skip the pivot otherwise the partitioning won't work as
expected
        iterator_type par_start = first + 1;

        std::less<value_type> pred;

        pivot = std::partition(par_start, last, std::bind2nd(pred,
pivot_value));

        // we restore the pivot
        std::iter_swap(--pivot, first);

        return pivot;
}

template <typename RandomIterator, typename Pool>
void rec_pivot_partition(RandomIterator first, RandomIterator last, Pool &
p)
{
        if (std::distance(first, last) > 1000)
        {
                RandomIterator pivot = pivot_partition(first, last);
                rec_pivot_partition(first, pivot, p);
                rec_pivot_partition(pivot, last, p);
        }
        else
        {
                p.submit(boost::bind(&std::sort<iterator_type>, first,
last));
        }
        
};

template <typename RandomIterator>
void parallel_tp(RandomIterator first, RandomIterator last)
{

        typedef RandomIterator iterator_type;
        typedef typename iterator_type::difference_type difference_type;
        typedef typename iterator_type::value_type value_type;

        difference_type n = std::distance(first, last);

        RandomIterator l = first;
        
        const difference_type block_size = 1000;

        // we partition until we have "atoms", ie block of size < block_size
        boost::tp::default_pool & p = boost::tp::get_default_pool();

        rec_pivot_partition(first, last, p);

        p.shutdown();

}