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 17:58:30

> 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.

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
 * 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.

Regards.

-- 
EA