[Synfig-devl] Faster Sorting Algorithm (and an update)

[<d....@fr...>]

>From the synfig forum....

----------
http://www.synfig.org/forums/viewtopic.php?f=22&t=10031

CodeMouse92 » 25 Mar 2016 22:42
Hey gang,

As you might know, my company and I have been working on a game animation studio, but we want to stay involved with Synfig and contribute where we can. This is one such case. At the heart of our game engine is an original, MIT-licensed C++ library called PawLIB, and one piece of that is Pawsort, an adaptive, unstable sorting algorithm. In benchmarks, this is proving to be faster than std::sort by a longshot in many scenarios.

Pawsort is a modification of the introsort (introspective sorting) algorithm. The traditional introsort combines quicksort, heapsort, and insertion sort. My algorithm combines Yaroslavskiy's dual-pivot quicksort, heapsort, and the Knuth shell sort. I'm not certain of the exact speed (in big-O notation), but figuring that out will be one of my back-burner goals this year. I know comparatively that it is at least O(n log n), since that is introsort's worst case performance.

Pawsort uses an original algorithm to determine the two pivot points for the dual-pivot quicksort, using a modification of the median-of-three that is traditionally used. The modified algorithm has thus far demonstrated that it is resistant to median-of-three killer arrays. I also leveraged the concept of depth in introsort to make an initial pass through the array and check if it is already sorted.

I've attached the C++ header file for Pawsort. The functions are all templated, so the sorting algorithm will work with arrays of any sortable type. I am still looking for ways I can further improve the speed and stability of the algorithm and its implementation. In addition, I will be working on implementing Timsort as the stable sorting algorithm in the library. Any feedback you might have is more than welcome.

I've also attached the output from our benchmarker, and the Callgrind output thereof. "pawsort_benchmark_" and the Callgrind data was on the Debug64 target, compiled with --std=c++14 -g -Wall -fexceptions.

"pawsort_benchmark_round2" was on the Release64 target, compiled with --std=c++14 -O3 -fexpensive-optimizations.

Finally, I included the main.cpp, which executes the benchmarker. main.cpp will not run for you, as it relies on the rest of PawLIB, but the file does show the various test scenarios referred to in the "pawsort_benchmark" files.

Before the month is out, the final code should be landing on our Github mirrors. I can include the link if anyone asks - otherwise, the link is on the PawLIB library page on our website.

I wanted to send this to ya'll early on, in case it might be helpful to Synfig Studio's continued optimization efforts. I'll keep you updated as the code is improved and expanded.

--