Click here to Skip to main content
15,943,477 members
Articles / Programming Languages / C#

Faster Sorting through Appropriate Threading on Multi-processor Machines

Rate me:
Please Sign up or sign in to vote.
4.20/5 (8 votes)
5 Mar 2009Apache4 min read 33.4K   386   22   10
Splitting a generics List of KeyValuePairs over the number of processors and then merging the result lists over half the processors and then half again, until only one list, the final list, is left.


The goal was to achieve improved sorting performance by spawning a limited number of threads to use as much of the available processing power on multi-core and/or multi-processor machines as possible. The result is an improvement of 40% on dual core and more than 100% on a 4 processor machine.


As part of a team involved in importing RDBMSs into an Associative Knowledge base, I recently inherited some code that hashed through a large amount of relational data, aggregating it before pushing it onto the server.

This article though, really has nothing to do with that. I was just looking for an excuse to generate heat. In fact I was quite embarrassed that the code was consuming a full 25% of the available processing on the quad core server, so I decided to do something about it.

After 2 months of cursing, I now have a new found respect for threaded architecture. There are pitfalls galore, even if you read all the documents. Nuances, such as code that runs on one machine and not on another. A lock that just doesn't seem to lock, and locks that make your code run like molasses.

The number one lesson I've learned is not to spawn threads unless there is a clear benefit to doing so. Even cheap threads are expensive when you have thousands of them around.

The number two lesson is to minimize contention or to avoid locking if you can.

Okay, so applying these lessons to sorting gives the following:

  1. Split your big unsorted list by the number of available processors.
  2. Spawn one thread per split that sorts them using your favourite sorting routine.
  3. Merge pairs of result lists using Mergesort until you have no more results to merge.

(You will find this logic applied in the ParallelSorter method of Jigger.Parallel<T>).

Perfectionist Disclaimer

I do NOT claim that the source code provided has much merit as far as programming style goes. The sorting logic was extracted from a working class and placed in a test and benchmarking solution for the sole purpose of proving that it was worth doing. Memory consumption was taken into consideration but not to the detriment of performance.


However, having said that, if you have anything (con/de)structive to say, I'm all ears.

Source and Contributing

The zip contains the source, unit test and benchmarking files. I hope you have Visual Studio 2008, otherwise you will have to do some copy-pasting.

You will also find a set of results from my tests on my Dual Core notebook and on a Dual core, Dual processor server. I would be interested to hear from those of you that have other configurations. To add to the list, just install Ntime.

Using the Code

You will find many examples in the Parallel.Sort.Test.ParallelTester class. I have extracted what's pertinent and put it below:

//Initialise the collection
List<KeyValuePair<int, string>> stringDupesList= 
     new List<KeyValuePair<int, string>>(); 

// Load up a List of KeyValuePairs
ManyStringAdder(ref stringDupesList, 20);

//Initialise the Parallel sorter
Parallel<KeyValuePair<int, string>> parallelDo = 
     new Parallel<KeyValuePair<int, string>>(new KeyValueComparer<int, string>()); 

// And now you can sort using one of the 3 supplied 
// Sort using MergeSort. This one is a stable sort
stringDupesList = parallelDo.MergeSort(stringDupesList));

// This is the sort provided by Microsoft. 
// I've assumed it to be a derivative of QuickSort
stringDupesList = parallelDo.MSQuickSort(stringDupesList));

// This is my attempt at using the Logic from FastQuickSort with MergeSort. Not so good.
stringDupesList = parallelDo.MergeInsertionSort(stringDupesList));        

Points of Interest

Building a solution that's worthy of being published as an article requires quite an effort. I had already benchmarked my sort with a console application, but when you need to show your results to others you have to be more formal and certain. For unit testing, I had already settled on Visual Studio 2008 but for micro benchmarking I had to do some research.


After a few days of rummaging around the interweb, wondering whether I should translate my own JavaScript profiler and checking to see if profiling tools could benchmark to the degree I require, I ended up with three 3rd party candidates.

  • Nperf is a neglected but cool tool that provides graphs. Maybe part of Gallio ?
  • Ntime provides an nUnit interface, is feature full and was easy to implement
  • Microbenchmarking by Jon Skeet is C# source that you compile in your class

I went with NTime because I had little time to figure out the other candidates. Jon Skeet's tool provides a subset of the functionality in NTime and NPerf was temperamental to say the least. I still think I should translate my JavaScript profiler because it outputs to XML, ready to graph. But that's for another day.


The magic here is in what to test. I knew that my sort was running in production but I had never tested some obvious combinations of data types, values and thread count because my application never went near them. But, if you want other people to run your software, you are going to have to think about more uses for your code and test it. In the end, I spent half a day on the sort class and more than a week writing the tests and benchmarking in the hopes that I'll be able to re-use some of it in the future.


In no particular order to:

  • NTime (by AdamSlosarski) for saving my time
  • Nick Taylor for being a sounding board
  • Kevin Fleming for inspiring usage of sound practices that I sometimes use
  • My wife for going with the flow
  • Ron Everett for not saying no when I said I wanted to write this article
  • Everyone else that I know


  • 2009-03-05
    • First release of Jigger.Parallel<T>.Sort


This article, along with any associated source code and files, is licensed under The Apache License, Version 2.0

Written By
Architect Relavance
Canada Canada
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

GeneralTried CCR -- Microsoft's Concurrency and Coordination Runtime Pin
jboarman9-Mar-09 11:02
jboarman9-Mar-09 11:02 
GeneralRe: Tried CCR -- Microsoft's Concurrency and Coordination Runtime Pin
Jason Rudland11-Mar-09 16:45
Jason Rudland11-Mar-09 16:45 
QuestionGuarantee of split to cores? Pin
zaf5-Mar-09 20:38
zaf5-Mar-09 20:38 
AnswerRe: Guarantee of split to cores? Pin
AWdrius5-Mar-09 23:07
AWdrius5-Mar-09 23:07 
GeneralRe: Guarantee of split to cores? Pin
zaf6-Mar-09 1:48
zaf6-Mar-09 1:48 
GeneralRe: Guarantee of split to cores? Pin
Jason Rudland6-Mar-09 3:24
Jason Rudland6-Mar-09 3:24 
GeneralRe: Guarantee of split to cores? Pin
zaf6-Mar-09 8:53
zaf6-Mar-09 8:53 
GeneralRe: Guarantee of split to cores? Pin
JasonShort9-Mar-09 11:07
JasonShort9-Mar-09 11:07 
Of course MS says that Dot Net 4 will include much more ability to run on multi core machines...

And I have read a few things that suggested you will finally be able to set processor affinity (tell it which core to run on ) in managed code without resorting to dll imports.

Threading is difficult, and I don't expect the Dot Net 4 libs to help it that much. Look at how poorly some of the locking mechanisms perform. You can usually gain serious performance only through domain knowledge. Any generic API will have a difficulty with knowing what you intended.

I expect that Array.Sort or some other synchronous objects may be able to take advantage of multicore in the next release. But for most operations you will still have to tune and tweak.

BTW, good job on the article.

Jason S Short, Ph.D.
VistaDB Software, Inc.

GeneralRe: Guarantee of split to cores? Pin
Jason Rudland11-Mar-09 16:59
Jason Rudland11-Mar-09 16:59 
GeneralRe: Guarantee of split to cores? Pin
JasonShort12-Mar-09 11:08
JasonShort12-Mar-09 11:08 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.