Google Summer of Code: A Better Mergesort for FreeBSD

README.md

Mergesort

Mergesort is a set of improvements to FreeBSD's standard C library mergesort function.

Features

• a pointer width agnostic implementation of Wikisort
• an expanded set of tests
• a C benchmarking program with Python driver script

Changes

Wikisort

• wiki.c: Main logic of the wikisort function ported from https://github.com/BonzaiThePenguin/WikiSort/blob/master/WikiSort.c to be general for any input type
• wikihelpers.c: Helper functions from BonzaiThePenguin's wikisort ported to be general, along with additional helper functions and macros required for generalization

Testing Suite

• mergesort_test.c: Added a battery of test cases, testing a variety of custom data types, sizes, and orderings.
• test-sort.h: Added necessary structures

Benchmarking

• mergesort_bench.c: Program used by the driver script to run a sorting algorithm with settings passed in by command line argument.
• bench.py: Driver script which runs mergesort_bench with multiple configurations and compares them using ministat in order to output confidence in one algorithms superiority of another.

Instructions

Wikisort

• To use wikisort, all you need to do is include the wiki.c file at the top of your code. Ideally this code will replace merge.c and you will only have to include stdlib.h

Testing Suite

• This is a standard ATF suite so the code can be run with Kyua during regular testing.

Benchmarking

• mergesort_bench.c:

  Usage:
    ./mergesort_bench: [alg] [test] [runs] [elt_power]
  
  Valid algs:
    heap merge quick
    
  Valid tests:
    rand sort part rev
        rand: Random element array
        sort: Increasing order array
        part: Partially ordered array
        rev: Decreasing order array
        
  Run the algorithm [runs] times with 2^[elt_power] elements
  

• bench.py:

   python bench.py
  

  Files will be output in a new folder called stats with separate files for each statistical comparison and the raw results in a subfolder called data.

Contribute

Wikisort

• The algorithm currently functions with O(N) additional memory but runs into memory errors when sorting with O(1) additional memory.

Testing Suite

• The mergesort testing code could easily be ported to improve the other stdlib sort tests in the lib/libc/tests/stdlib directory.

Benchmarking

• Improving ministat output comprehension

Support

If you are having issues, please let us know. We have a mailing list located at: freebsd-hackers@freebsd.org or you can email me personally at milesfertel@college.harvard.edu

License

The project is licensed under the BSD license and the Unlicense.