Engineering a Cache-Oblivious Sorting Algorithm

JEA 2006 by Gerth Stølting Brodal, Rolf Fagerberg, and Kristoffer Vinther

License

All source is released here under the GNU General Public License.

Source

The source can be downloaded here. Please check out the funnelsort project's home page for latest version of the funnelsort implementation. The source is located in directories with the following structure:

• funnelsort

  The four C++ header files containing the funnelsort implementation.

• minxp

  A minimalist cross platform class library. Contains useful classes for measuring wall clock time, memory mapping files, and miscellaneous other utilities. Used extensively by the benchmarking programs.

• benchmarking

  Various benchmarking programs. This section is mainly interesting for those who wish to investigate or reproduce the results presented in the article.

  • ChkSort: A program that verifies that the contents of a file is sorted.
  • FillMem: A program that attempts to flush any cache on the system (L1 through RAM) by allocating a large chunk of virual memory and filling it with random garbage.
  • SortGen: A program that generates files containing data of various types and in various distributions to be sorted in.
  • Sorters implement main entry points for various sorting algorithms:
    • dinkumsort: Dinkumware implementation of std::sort. Called "Dink" in the article.
    • funnelsort: Our funnelsort implementation. Called "funnelsort2" and "funnelsort4" in the article.
    • introsort: Custom implementation of std::sort using fast, fat partitioning. Called "Mix" in the article.
    • m-sortc: Multi-way merge sort optimized for L2 cache. Called "m-sortc" in the article.
    • m-sortm: Multi-way merge sort optimized for L2 cache. Called "m-sortm" in the article.
    • qsort: The C standard library qsort function. Not in the article.
    • rmerge: The register merge sort. Called "Rmerge" in the article.
    • sedsort: An implementation of quicksort by Robert Sedgewick available from his homepage. Called "Sedge" in the article.
    • sgisort: The SGI implementation of std::sort. Called "GCC" in the article.
    • spfunnelsort: The funnelsort implementation of my master's thesis. Not complete and not in the article.
    • stdsort: The std::sort provided with the compiler. Not in the article.
    • tpie: The TPIE external memory merge sort. Called "TPIE" in the article. Requires that TPIE be installed.

Please note that the code is written in ISO98 C++ using concepts such as partial template specialization. Not all compilers support these concepts, though most recent ones do. Using either of the following is recommended:

• GCC, version at least 3.2.
• Microsoft Visual C++, version at least 13.1.
• Intel C++ Compiler, version at least 7.0.
• MIPSPro C++ Compiler, version at least 7.3.

Quick Start

This section provides a brief introduction to using the source code once downloaded and extracted.

Using the funnelsort implementation

Start by including the merger and sort headers:

		#include <funnel.h>
		#include <sort.h>
		

Pick a merger to be used by the sort function, say a funnel (denoted a merge_tree) using four-way basic mergers merging arrays of ints:

		typedef typename iosort::merge_tree<int*,4> merger;
		

Use iosort::merge_sort to sort the int array:

		#include <vector>
		
		void sort_2k()
		{
			std::vector<int> array(2000);
			// TODO: populate array with input.
			std::vector<int> output(2000);

			iosort::merge_sort<merger,iosort:default_splitter<2> >
				(array.begin(), array.end(), output.begin());

			// output now contains copies of the elements in array in sorted order
		}
		

or if you prefer

		// C-style:
		#include <stdlib.h>
		
		void sort_2k()
		{
			int* array = (int*)malloc(2000*sizeof(int));
			// TODO: populate array with input.
			int* output = (int*)malloc(2000*sizeof(int));

			iosort::merge_sort<merger,iosort:default_splitter<2> >
				(array, array+2000, output);

			// output now poitns to copies of the elements in array in sorted order

			free(output);
			free(array);
		}
		

The iosort:default_splitter class template defines parameters used to decide the order of the merger to use for a given problem size and similar issues.

Using benchmarking programs

cd your way through the benchmarking/bin/ directory locating an architecture and compiler appropiate for you. Once there type make depend followed by make all. The directory will now contain the benchmarking programs and executables for each of the sorting algorithms.

Each of the sorters can be used in two ways: sorting files on disk and sorting arrays in memory. Sorting files is done by first creating a file using sortgen (if benchmarking this should be followed by fillmem to make sure the generated input is not cached) and sorting it using the sorter. Both sortgen and the sorters expect a parameter, -e, specifying the type of elements to generate and sort (i for ints, p for pairs of ints and void*s, and r for 100 byte records). sortgen also needs a -d parameter specifying the type of distribution. Sorting arrays in memory is similar, except instead of providing file names, one provides distribution type and size directly.

All sorters writes identical XML fragments to stdout containing benchmarking data.

Contact

E-mail:

Last updated: April 13th, 2005.
See here for latest revision.