libpmsort 0.2 review
Downloadlibpmsort provides a parallel merge-sort algorithm that is interface compatible with qsort(3)
|
|
libpmsort provides a parallel merge-sort algorithm that is interface compatible with qsort(3). If the compare function is thread-safe, you may easily swap qsort with pmsort.
Though merge-sort itself is slower then quicksort on average, utilizing multiple CPUs or waiting in parallel for I/O can speed up the sorting tremendously.
Parallel mergesort, interface-compatible with qsort(3);
The compare-function must be thread-safe!
Uses posix-threads, currently hard-coded number of threads (pmsort) or can be
given explicitely (pmsort_mt). The latter function call is of course not
entirely interface compatible with qsort as it needs an additional integer
argument.
The benchmark program pm_test will compare pmsort to your system's qsort(3)
and mergesort(3). Testing v0.2 on a 4x PPC970 system yields an advantage of
100% over qsort(3) when sorting pure integers (best-case for serial qsort).
So pmsort(3) takes roughly twice the CPU-time but scales very well with multiple
processors.
Remind that this was the worst-case for pmsort(3) - sorting with e. g. an
I/O bound compare function can put pmsort(3) much further in the lead, even on
single processor systems.
What's New in This Release:
This release fixes a silly compile error.
It adds a benchmark/test program.
The Benchmark compares qsort(3), mergesort(3), and pmsort(3) sorting arrays of integers, floats, and doubles.
The array size can be parametrized, as can be the number of threads used by pmsort(3).
Preliminary tests on a 4x PPC970 yield an edge of rougly 200% of pmsort over mergesort.
libpmsort 0.2 search tags