Thread: New saca and bwt library (libsais)

It's great to see an actual improvement in SACA performance after 10 years of stagnation in the field. Brilliant work!
This certainly seems like it will become a new standard.

I know sais isn't a new algorithm, but being able to execute a majority of it out-of-order is an impressive optimization nonetheless.

Also my experience after my submission to GDCC.

For inverse BWT, if you do it in parallel like in Lucas iBWT, the bottleneck is the Memory Level Parallelism of the cpu (that is the number of concurrent memory cache misses). Intel Skylake has around 10 and ZEN2 around 20. (I have not tested for ZEN but it is likely faster). Also you need Huge pages because then TLB misses will be the bottleneck.

But note my block sorting was not exactly BWT but something a bit strange that used the cache better (but also with a compression ratio penalty).

Will you be updating your BSC with this new library?

i7-7820X @ 4.5Ghz

Code:

> bwttest enwik9 enwik9bwt
divsufsort time = 100.422 speed = 9.497MB/s
libsais time = 60.677 speed = 15.717MB/s

AMD Ryzen 5 3600X, 4342 MHz (from AIDA64)

Code:

> bwttest enwik9 enwik9bwt
divsufsort time = 85.416 speed = 11.165MB/s
libsais time = 54.552 speed = 17.482MB/s

@schnaader: added source to https://encode.su/threads/3579-New-s...ll=1#post68977

To test out the latest and greatest BWT/SA library by Ilya Grebnov, please check out the brand new BCM v1.60:

https://compressme.net/#downloads

AMD Ryzen 5800x (Zen3)

Enwik8

Code:

filelength = 100000000
memory allocation (6N) complete.
data loading complete (100000000 bytes).
divsufsort time = 6.468 speed = 14.744MB/s
libsais time = 3.875 speed = 24.611MB/s
BWT storing complete. index = 22481309

CARE_SBI_Join.tar (some extracted excel)

Code:

filelength = 54346752
memory allocation (6N) complete.
data loading complete (54346752 bytes).
divsufsort time = 1.507 speed = 34.385MB/s
libsais time = 1.190 speed = 43.556MB/s
BWT storing complete. index = 51422568

Originally Posted by Gribok

I updated libsais to version 2.1 with additional OpenMP parallelization (no changes to single threaded performance).

I am also attaching updated bwtbench program and test result of "divsufsort vs libsais vs msufsort" on enwik9 on Azure DS14_v2 VM (Xeon 8171M 2.1 GHz)

Great work. I never added induced sorting to MSufSort 4 so it's no where near as fast as it should be. But your recent work has inspired me to finish up MSufSort 4.

I'm curious, however, as to why the numbers I get for multithreaded performance on enwik8 are very different from yours. I find it hard to believe that different platforms could possibly produce such a very different result. Here are my numbers using an AMD Ryzen 9 3900 with Ubuntu 20.04:

Code:

libsais$ for ((i=1; i <=12 ; i++)); do echo $i; ./build/bin/libsais_demo enwik8 $i; done
1
elasped time = 18.95 MB/sec
2
elasped time = 27.58 MB/sec
3
elasped time = 34.09 MB/sec
4
elasped time = 39.21 MB/sec
5
elasped time = 42.76 MB/sec
6
elasped time = 45.09 MB/sec
7
elasped time = 45.93 MB/sec
8
elasped time = 46.27 MB/sec
9
elasped time = 47.87 MB/sec
10
elasped time = 47.77 MB/sec
11
elasped time = 48.06 MB/sec
12
elasped time = 48.33 MB/sec

Code:

msufsort$ for ((i=1; i <=12; i++)); do echo $i; ./build/bin/msufsort_demo b enwik8 $i | grep "transform completed"; done
1
burrows wheeler transform completed - total elapsed time: 15.65 MB/sec
2
burrows wheeler transform completed - total elapsed time: 30.96 MB/sec
3
burrows wheeler transform completed - total elapsed time: 41.80 MB/sec
4
burrows wheeler transform completed - total elapsed time: 51.70 MB/sec
5
burrows wheeler transform completed - total elapsed time: 60.31 MB/sec
6
burrows wheeler transform completed - total elapsed time: 65.61 MB/sec
7
burrows wheeler transform completed - total elapsed time: 73.26 MB/sec
8
burrows wheeler transform completed - total elapsed time: 78.18 MB/sec
9
burrows wheeler transform completed - total elapsed time: 83.19 MB/sec
10
burrows wheeler transform completed - total elapsed time: 87.56 MB/sec
11
burrows wheeler transform completed - total elapsed time: 90.90 MB/sec
12
burrows wheeler transform completed - total elapsed time: 93.89 MB/sec

Originally Posted by Gribok

sais algorithm is very sensitive to memory speed. My RAM is also overclocked with tight sub-timings. So I am not actually that surprised to see this difference especially with AMD (which is know by having weaker memory controller prior to Zen3 compensated by larger L3 cache).

For best performance try compiling with Clang 11.0 with "-Ofast -fopenmp -march=znver2 -DNDEBUG" (this is what I am using for testing with exception to -march=skylake instead of -march=znver2).

I am also having trouble with MSufSort4 on very repetitive inputs like fib41, rs13 and tm29 from Pizza & Chilli Repetitive Corpus.

I'll measure again with the compiler flags you mentioned and report back. But I think that I'm probably getting results for libsais that roughly match your results. I think your result for msufsort is what is different from mine.

Yes, msufsort4 doesn't have the induced sort component yet so it will suffer on those types of input at the moment. I'm mostly curious about MT performance in this case. Is there a reason why libsais appears to max out at about 6ish cores?

Unfortunately, I have some issues using your great library under Linux:
The first version gives "Segmentation fault (core dumped)". I believe stack size is about 8 KB.
The latest version cannot be compiled at all...

this is so obviuos: #include <stddef.h>, #include <limits.h>:)

I'm testing the newest version - no issues of any kind! Well done!
One question - what is the purpose of a newly added function last parameter "fs"? It's an extra space, but for what? Is it okay to keep it 0 or with some added extra space the BWT construction will be faster?

BTW, tested your great library on ARM (aarch64) machine - it's more than 2 times slower than divsufsort...

No, it wasn't Apple M1. Can't say exact model because of a trade secret. But that was the one with a slow memory and weird behaviour indeed.
On Intel platform your library is always faster. I've tested it it on many Intel CPUs, even on ones with T suffix.

Originally Posted by michael maniscalco

... I find it hard to believe that different platforms could possibly produce such a very different result.

I can confirm that the performance of libsais could be vastly different depending on a platform.