Even (somewhat) faster Suffix Sorting

[Christoph Diegelmann]

Hello,

I've played around a little and replaced libdivsufsort's trsort with basically radixSA
(I actually use boost's spreadsort, std::sort and insertion sort instead of radix sort).
Memory requirements should stay the same.

Runtimes reported by suftest on my machine (i7 4770K, 16 GB RAM):

File   | orginal    | modified
enwik8 |   8.1600 s |  7.8960 s
enwik9 | 105.0930 s | 95.5340 s

This is without OpenMP. OpenMP speeds up the unmodified sssort so the changes are a bit more significant:

File   | orginal    | modified
enwik8 |   6.1880 s |  5.9630 s
enwik9 |  83.1580 s | 74.6800 s

Source code can be found at https://github.com/akamiru/libdivsufsort
Main changes are in lib/spsort.cpp.

[michael maniscalco]

Hello,

I've played around a little and replaced libdivsufsort's trsort with basically radixSA
(I actually use boost's spreadsort, std::sort and insertion sort instead of radix sort).

The 'tr' sort is designed for detection and specialized sorting of tandem repeats. Yuta's implementation suffers performance wise due to his choice of substring sort as the primary sort routine. The best way to speed up tandem repeat sort is by placing it in the main sort by switching from substring sort to multikey quicksort.

Enwik8/9 are not good for testing tandem repeat sort in general because they don't really contain many tandem repeats

Try your changes against the files in the gauntlet test set. The corpus is designed to test for perfornance on heavy tandem repeats as well as other hard cases for SACAs.

http://www.michael-maniscalco.com/do...auntlet.tar.gz