Re: [boost] [parallel_sort] Proposal

Subject: Re: [boost] [parallel_sort] Proposal
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-02-03 05:20:32

Edouard A." wrote:

>> That's a lot of extra copying.
> [Edouard A.] 
>
> I don't do in place merge. I don't know if this would be faster. 

My point is that you're doing extra copying compared even to a standard 
out-of-place mergesort.  You're copying all the data on the way down, 
and then copying it all again during the merge on the way back up.  
Using in-place merge can avoid some of the copying on the way back up.  
I think you should get rid of the copying on the way down.

>> What do you mean by "hidden system locks"?
> [Edouard A.] 
>
> If you have two or more CPUs trying to access the same cache line, locking
> will occur.

Right.  But do you think this effect is more significant than copying 
all of your data O(log n) times?  Surely not.  But even if it were a 
problem you could easily fix it by aligning your split points to cache lines.

I encourage you to investigate parallel sorting algorithms in the 
literature - doesn't Knuth have a whole book of them? - rather than 
inventing your own.  And base your improvements on benchmark results.

Regards,  Phil.