Todo for first verified sorting paper #1
Description
Joseph
A rough outline of what to do for our Haskell-oriented paper.
(Writing Tasks)
See this issue
(Verification)
- https://github.com/michaelborkowski/lh-array-sort/issues/11
- Linearize and linearcheck the remaining sorts:
- Disable all checks when enabling mutable arrays (may not be necessary)
- Verify correctness issue for Parallel Mergesort with multiple threads
- Verify correctness issue for Quicksort if we decide we want it
(Benchmarking)
- Change benchrunner to sort a shuffled array every iteration
- Rerun all benchmarks
- Redo all analysis
- Mergesort-parallel correctness issue: we get "not ordered" once in a while. With primitive-arrays it happens even with sequential version and more consistently.
- Investigate parallelization issues with parallel mergesort: it doesn't scale with growing number of threads at all. Possible directions: benchmark simpler algorithms like parallel merge, investigate the strictness in primitives (strictness may prevent GHC parallelization), use eventlog tracing to visualize the load of individual processors.
- Repair benchrunner on main if necessary.
- Cover all the sorts we care about on the benchrunner (quicksort, unrolled (4) mergesort, unrolled parallel mergesort and cilksort). Insertionsort is only reasonable on small array inputs.
- Automate setting up and running benchmarks for all languages that we want to compare against, and ensure our testing methodology is good across languages w.r.t. the way arrays are randomized, the way arrays are loaded into memory, etc.
- Run sequential benchmarks under RTS runtime
- Benchmark new quicksort?
- Restore PrimMutableArrays?
(Paper writing)
- Improve organization of the paper and coherency of the story
- Finalize introduction
- Finalize performance story
- Add in benchmarks
- Finalize verification story
- Finalize case studies
- Finalize benchmarks table
- Add and fix citations
Copied from: https://github.com/michaelborkowski/lh-array-sort/issues/6.