A Better MergeSort for FreeBSD
- Student: Miles Fertel (miles@)
- Mentor: Brooks Davis (brooks@)
The current libc implementation for mergesort is fundamentally flawed in that it does not allow sorting data which has an element size less than sizeof(void *) / 2. I will develop a pointer width agnostic Mergesort remove this constraint which limits FreeBSD’s Mergesort on machines with larger pointer sizes. Moreover, I aim to improve the speed of Mergesort and ideally decrease the space requirements for its use.
The core problem of this GSoC project is dissecting the implementation in
to determine the critical sections that depend on the size of the elements being greater than sizeof(void *) / 2 in order to discover the purpose of this restriction. This is likely a trade off in exchange for some optimization. I plan to use the Community Bonding period to do more extensive code reading and tests, as well as ask the opinion of more experienced contributors, in order ensure I’m prepared for the start of the coding period.
I aim to improve the practical runtime and space complexity of mergesort based on the papers:
Fast Stable Merging and Sorting in Constant Extra Space (1989-92)
which implement an in-place block Mergesort using O(1) additional memory. I will either port a working block Mergesort from https://github.com/Mrrl/GrailSort or https://github.com/BonzaiThePenguin/WikiSort and tinker with them to optimize and style the implementation for FreeBSD, or write my own implementation from the algorithm pseudocode laid out in the paper if the code cannot be ported. The challenge here for me is my lack of knowledge of open-source software licensing. I need to learn what software can be copied and what software must be implemented myself.
A pointer width agnostic Mergesort
I will either change FreeBSD’s mergesort to support any element size or replace it with a comparable or better mergesort that does.
A Mergesort benchmark suite
I will write a set of benchmark scripts which demonstrate the speed improvement the new Mergesort has on different data sets compared to the previous Mergesort. These will likely be bash or python scripts that call to gprof and pmcstat.
My plan during the community bonding period is to communicate with contributors over the mailing list and do a deep reading of the mergesort implementation in order to determine the purpose of the restriction on element width. Furthermore, I will use this time to learn BSD style and licensing rules, as well as look over my labs copy of The Design and Implementation of the FreeBSD Operating System.
Weeks 1-2 (May 30 - June 11)
Task: Write a battery of tests to support the correctness of my implementation.
Approach: Write C unit tests which use the mergesort function in as many different ways as I can conceive. Aim to have tests which emulate likely mergesort workloads, as well as test for corner cases. This will be done early such that the implementation that is written can be tested immediately.
Deliverables: test/mergesort_tests.c: A rigorous correctness testing suite
Week 3 (June 12 - June 18)
Task: Decide on an algorithm and demonstrate that it can be implemented as pointer width agnostic.
Approach: Use the information gathered over community bonding period in order to decide if the current implementation can be restructured to be pointer width agnostic. If not, compare the pros and cons of the two block sorting algorithms in the referenced papers in order to determine which is preferable.
Deliverables: A plan of action which notates the algorithm chosen as our mergesort replacement and why it is believed to be superior.
Plan of Action
To modify WikiSort over the coming weeks to fit the freebsd mergesort specifications. Including the following tasks:
- Change the code to fit the mergesort prototype
- Modify the implementation to take in arrays of any type
- Find out to what extent mergesort_b needs to sustained and act accordingly
- Simplify by removing extraneous functions from the codebase
- Ensure the code provided contains no memory leaks or bugs
- Assess any licensing concerns of the code
- Optimize where possible
Weeks 4-7 (June 19 - July 16)
Task: Implement the chosen algorithm.
Approach: See Plan of Action above.
Deliverables: lib/libc/stdlib/merge.c: A backwards compatible, pointer width agnostic, mergesort implementation.
Weeks 8-10 (July 17 - August 6)
Task: Write benchmarking scripts in order to support the time and space usage superiority of my implementation.
Approach: Write a C program which tests merge.c against different data sizes and data patterns for runtime. Use a hardware performance utility to profile the memory usage of each implementation as well.
Deliverables: test/mergesort_benchmark.c: A comprehensive benchmarking suite which exhibits the improved mergesort’s runtime and memory usage.
Weeks 11-13 (August 7 - 29)
Task: Documentation, style audit, and merge to production.
Approach: Latex a pdf (or whatever format of documentation is preferable) containing all the design decisions and optimizations that went into the new mergesort. Display the improvement that the new mergesort provides, with before and after data visualization. Edit the man page for mergesort, removing the restriction on element sizes. Look through merge.c and the C unit tests and ensure that they conform with the style guide in the FreeBSD man pages. Lastly, share the changes with the mailing list, requesting comments and concerns before requesting the files be merged into stdlib.
- Name: Miles Fertel
- Country of Residence: USA
- University: Harvard University
- Major: Computer Science
- Year of Study: Rising Junior
- Github: github.com/milesfertel
- Resume: milesfertel.com
Results and Documentation
The final deliverables of this project are:
- a pointer width agnostic implementation of Wikisort, which can be improved to eventually replace the current mergesort implementation.
- an expanded set of tests which can support the correctness of the new implementation.
- a C benchmarking program with Python driver script which can verify the efficacy of the new implementation.
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
- 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 for testing custom types
- mergesort_bench.c: Benchmarking 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.
- To use wikisort, all you need to do is include the wiki.c file. Ideally this code will replace merge.c and you will only have to include stdlib.h
- This is a standard ATF suite so the code can be run with Kyua during regular testing.
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
Usage: python bench.py [elts]
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. Bench will optionally run 2 elts elements as the dataset size when provided. Otherwise it will run 2 20 elements.
- The algorithm currently functions with O(N) additional memory but runs into memory errors when sorting with O(1) additional memory.
- We will want to update lib/libc/stdlib/qsort.1.
- Add a wikisort_b variant for block support. (See mergesort(3))
- The mergesort testing code could easily be ported to improve the other stdlib sort tests in the lib/libc/tests/stdlib directory.
- Improve the bigstruct_mergesort_test in mergesort_tests.c by varying the value of the canary in the bigstruct in order to ensure it is actually copied over.
Implement a better design for random data testing as started in https://github.com/milesfertel/freebsd/tree/randtests. The goal would be to have the necessary data stored on failure such that the failure case could be replicated.I think you can just print it to stderr. It might make more sense to have a separate program in src/tools/tools that can store the bad outputs to files and load them again for debugging.
- Improving ministat output comprehension
If you are having issues, please let us know. We have a mailing list located at: email@example.com or you can email me personally at firstname.lastname@example.org
The project is licensed under the BSD license and the Unlicense.