Click here to Skip to main content
Click here to Skip to main content

Fast External Sort in C#

By , 14 Feb 2011
Rate this:
Please Sign up or sign in to vote.

Introduction

External sort of large data sets (and related algorithms like merge, join, group by, unique) are an important part of many data organization efforts such as database construction, search engine indexing and data-mining algorithms.

Background

What can you do when you have to sort 5,000,000,000 (5*10^9) integers (this is around 18GB of data when you store the integers in binary with 4 bytes per integer or 30GB if you store the data as text)?

  • Use a database. Boring!
  • Use a commercial product such as nsort from oridinal.com. Expensive!
  • Use an open source tool such as the unix sort command. Uncertain!
  • Roll your own and see how it performs. Fun!

I rolled my own external sort implementation in C# but only compared against the unix sort utility. Guess what, my implementation runs more than 6 times faster than unix sort. To be fair, there are research reports that show off fast sort implementations, but those implementations are tuned to particular hardware and in general cannot be found online.

Goals

  • Show a program that sorts a large number of integers (but only integers) using disk.
  • My program should be comparable to/or better than unix sort in terms of efficiency. It turns out mine is around 6 times faster which is a big gap when you measure your program's running time in hours.
  • My program is written in C#
  • Post my code
  • Keep it short

Non-goals

  • Write the fastest possible sort program
  • Write a complete solution, i.e. a program that works not only for integers but for any sort of input and supports multiple options
  • Evaluate and compare against most possible options to sort large datasets
  • Provide extensive discussion of mine or other approaches for external sorting

Experiment

After implementing my program, I ran one large scale experiment. I generated a text file of 5*10^9 integers. One needs approximately 18GB of space to store this much data given that one spends 4 bytes per integers. When the data is stored as text, with one number per line, it takes either 28GB or 33GB depending on whether you "\n" or "\r\n" to terminate the lines. I used two external USB hard drives with transfer-rate of 30-35MB per second from one to the other. The results when using one USB hard drive were similar. Given that the sorting algorithm requires two reads and two writes of the data-set, and assuming transfer rate between 30-35 MB per second, it should take, in the best case between 49 and 58 minutes to sort the data-set for this experiment. I used the following formula for this calculation:

 (   33.0 (*initial read*)
   + 18.0 (*sort chunks and write*) 
   + 18.0 (*read sorted chunks and merge*)
   + 33.0 (*write sorted file*)
 )* 1024.0 (*work in GB*) 
 /
 (   30.0 (*transfer rate MB/s*)
   * 60.0 (*convert to minutes*));;

I split the original file into chunks of 200MBs which lead to 96 files to merge. Overall, my program did not consume more than 1GB of memory. The timings of parts of my program are shown below:

ExternalSort.exe:
Time to sort intermediate files: 00:28:34.9422320
Number of files to merge: 96
Time to merge intermediate files: 00:24:50.6632475 
    (When '\n' for end of line is replaced by '\r\n' it took 00:27:43.6421148)
Total Sort Time: 00:53:25.9329689

I got the following timing for unix sort:

$ time sort -n --buffer-size=1000M --temporary-directory=/cygdrive/e/tmpSort/tmp/ 
--output=unixsort.output input.txt
real    422m35.296s (this is around 7 hours)
user    346m14.309s
sys     2m56.857s

I monitored unix sort through Windows Performance Monitor and noticed most of the time was spent in CPU. This is strange since external sorting should be mostly IO-bound. As another baseline, I ran the wc (word count command on the output file):

$ time wc -l output.txt
5000000000 output.txt
real    14m22.307s
user    1m40.386s
sys     0m27.424s

Word count spent most time doing IO, which is as expected.

One can observe from this experiment that reading took 14 minutes and reading + writing (both for the initial sort pass and the merge pass) took 28=2*14 minutes. It seems that one cannot sort faster than 4*14 (around 26 min.) that for my particular choice of hardware. If one used compressed files for input/output or multiple non-USB disks, one could do better.

Tricks

Everyone who implements an external sort program has a number of tricks. The most significant trick that I used was the way I performed the merge of multiple files. The literature accounts for using a priority queue. In my experience, the priority queue shows poor locality of reference and ends up slow. I used merging of streams where each stream is represented as array+rest. Rest contains code to generate a new "array+rest". For more than two streams, I built a binary tree of merges up front and allocated storage buffers. No allocation of memory happens after that. A drawback to this strategy is the larger amount of memory used. To merge n files where I use a buffer of k bytes for each file I need: log(n)*n*k bytes. Usually, n <= 1024, so log(n) is 10.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Stefan Savev 2

United States United States
No Biography provided

Comments and Discussions

 
GeneralSource ??? Pinmemberfwsouthern5-May-11 12:05 
GeneralMy vote of 4 PinmemberSledgeHammer0116-Feb-11 9:42 
I would have made a temp copy on the hard drive and then written it back at the end. Reading / writing from the usb drive will be much slower Smile | :) .
GeneralMy vote of 1 PinmemberPaulo Zemek15-Feb-11 1:58 
GeneralRe: My vote of 1 PinmemberSavev Stefan19-Mar-11 7:12 
GeneralMy vote of 4 PinmemberRavi Lodhiya31-Jan-11 20:54 
GeneralRe: My vote of 4 PinmemberStefan Savev 21-Feb-11 6:39 
GeneralRe: My vote of 4 PinmemberJohn Brett2-Feb-11 0:48 

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

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

| Advertise | Privacy | Mobile
Web03 | 2.8.140415.2 | Last Updated 14 Feb 2011
Article Copyright 2011 by Stefan Savev 2
Everything else Copyright © CodeProject, 1999-2014
Terms of Use
Layout: fixed | fluid