Test SA-IC creation suffix array algorithm

[AndrzejB]

https://gitlab.com/compress-data/sa-is

can be seen inversely proportional efficency when cicles exists.Naive takes long tiome when long cycles, but algorithm SA-IS especially.

Next, I want do similar test of Karkkainen-Sanders, but I think it is slower than SA-IS

[xezz]

Do you know openbwt?

[AndrzejB]

Sa-Is is not quite linear. I tested for 150 kB block and was above 4x better than naive, but for large block like 10 MB was only 1.1 x better. Method Karkkainen-Sanders was above 2x worse on large blocks. Worse cooperation with processor cache?

[dnd]

The best and widely used SA construction library for CPUs is libdivsufsort. 2 times faster than SAIS (incl. in openbwt) from the same author.
You might also have a look at: msufsort parallel suffix array construction algorithm & msufsort 4 update