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

Subject: Re: [boost] [threadpool] version 22 with default pool
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2009-03-09 03:16:08

Hi Edouard ,

----- Original Message ----- 
From: "Edouard A." <edouard_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Sunday, March 08, 2009 10:58 PM
Subject: Re: [boost] [threadpool] version 22 with default pool

>> Hi,
>> 
>> I don't see when the merge is done. Have you tested that the result is
>> ordered?
>> Could you attach the complete file?
> 
> There is no merge, this is a quicksort. I changed my mind. :D I have tested
> the input to be sorted but maybe some bug eluded me.

Ok, I see now how ot works.
 
> I could try something with a merge sort as well. You would divide your
> collection in blocks then merge them in parallel. Would have to be careful
> with false sharing, but concurrent_vector should protect us from most nasty
> cases.
> 
> Anyway as for parallel_quick_sort. First you traverse the collection,
> partitioning, until you reach a block size of 1000, at which point you
> create a task to sort this block in a separate thread. As you can see this
> is pretty straightforward with std::partition.
> 
> Limits : 
> 
> * I have no protection against quadratic behavior

What do you mean?
> * Block size may be suboptimal, I don't merge smaller blocks (ie if we have
> two blocks of 500, we will sort two blocks of 500 instead of one of 1000)
> 
> You will need to remove the calls to TBB and probably some useless includes
> referring to some work in progress on my side.

I have not installe TBB. There is a lot of change to make it compilable without TBB.

Instead of

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

I would do

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

so no need to store the futures in a list. Do you see any problem with this approach?

Best,
Vicente