[boost] [parallel_sort] Proposal

Subject: [boost] [parallel_sort] Proposal
From: Edouard A. (edouard_at_[hidden])
Date: 2009-02-01 12:49:02

Howdy,

 

I just finished the first working version of parallel_sort. It seems there
is a lot of interest for this function in the C++ community, and in the
boost community specifically, which is the motivation for this post. ;)

 

My implementation is somewhat very different in nature from the one present
in Intel's TBB. It's designed to take advantages of a multi-core user
machine, it's not designed to run on a grid for massive sorting operation. 

 

It only uses the STL and the boost library. It doesn't have any fancy
prerequisites, except having several cores to unleash its power!

 

Current benchmarks on my Q6600 vs2008-64-bit default allocator:

 

2 threads : 160 % faster

4 threads : 260 % faster

 

Keep in mind the Q6600 is not a real equivalent to a quad-cpu machine and
that the default memory allocator is not multithreading friendly.

 

It can be heavily customized. I already offer the possibility to choose
between quick sorting and merge sorting, and for quick sorting I offer two
pivot algorithms : fast or secure. Then you can of course specify a
predicate and a fallback sorting algorithm for when you run out of threads.

 

If you don't care to customize, no problem! Just write:

 

parallel_sort<2>(v.begin(), v.end()); // sort with 2 threads

 

There is still some work to be done, especially in the documentation area. 

 

Nevertheless, I think it's time to open up the code and start getting
feedback. J As an added bonus I also offer to add my implementation of the
smoothsort algorithm (with some hints from Steven). This algorithm is faster
on sorted input but slower on random input.

 

Cheers

 

-- 
 
EA