libdivsufsort

[Alexander Rhatushnyak]

divsufsort and libdivsufsort are mentioned in 22 threads in this forum. BSC uses libdivsufsort-lite, and probably a few other compressors do. So I decided to take a closer look at it.

First, libdivsufsort-lite crashes on 32-bit systems if file size is 1Gb or bigger, because of this call:
SA = (int *)malloc((size_t)n * sizeof(int));
It actually allocates ((n*4)&((1<<32)-1)) bytes.

Also, I introduced some speed improvements, and now libdivsufsort-lite runs ~3% faster on average on large files... at least if you compile it with the latest MinGW 4.5.2 (and the set of options provided by Yuta in makefile) and run on a computer with Core i7:

97.46 => 94.01 seconds on Manzini's Large Corpus, see also http://code.google.com/p/libdivsufso...ACA_Benchmarks

Many functions were not modified, including construct_SA(), construct_BWT(), divsufsort() and divbwt().

Yuta Mori did not reply to the e-mail I sent four days ago. Is there another way to reach him except yuta.256 at gmail?

[biject.bwts]

That's the email I used. However he is a busy man and his interests change plus he does not know English. Just keep trying and if you know Japanese you might have better luck.

[encode]

That's the email I used. However he is a busy man and his interests change plus he does not know English. Just keep trying and if you know Japanese you might have better luck.

It's simply not true! He speaks English really well! I had a conversation with him via email some time ago. He even registered at this forum (zxcb)!

[biject.bwts]

Well I am pretty sure he told me he was not good at English. Then again many people can't understand my poor use of English especially if I type fast. But sadly its the only language I know. Actaully I have friends that don't think I can speak English.

[Matt Mahoney]

Unfortunately the new version runs a bit slower on my computer. zpaq uses libdivsufsort-lite for -m1 (default) and -m2 compression. I tested on enwik8 using 16 MB blocks (default, 2 threads) and 100 MB blocks (1 thread) on a 2.0 GHz T3200, 3 GB, under Vista. I compiled with MinGW g++ 4.6.1: "g++ -O3 zpaq.cpp libzpaq.cpp divsufsort.c". zpaq1 is the new version.

C:\tmp>timer .\zpaq -m1 c enwik8.zpaq \res\enwik8

Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
Overwriting archive enwik8.zpaq
[1] \res\enwik8 16000000 -> 3985845 (1.9929 bpc)
[2] \res\enwik8+16000000 16000000 -> 4001739 (2.0009 bpc)
[3] \res\enwik8+32000000 16000000 -> 3988989 (1.9945 bpc)
[4] \res\enwik8+48000000 16000000 -> 4007152 (2.0036 bpc)
[5] \res\enwik8+64000000 16000000 -> 3993157 (1.9966 bpc)
[6] \res\enwik8+80000000 16000000 -> 4025764 (2.0129 bpc)
[7] \res\enwik8+96000000 4000000 -> 1032769 (2.0655 bpc)
31 seconds

Kernel Time  =     0.951 = 00:00:00.951 =   3%
User Time    =    57.361 = 00:00:57.361 = 188%
Process Time =    58.313 = 00:00:58.313 = 191%
Global Time  =    30.498 = 00:00:30.498 = 100%

C:\tmp>timer .\zpaq1 -m1 c enwik8.zpaq \res\enwik8

Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
Overwriting archive enwik8.zpaq
[1] \res\enwik8 16000000 -> 3985845 (1.9929 bpc)
[2] \res\enwik8+16000000 16000000 -> 4001739 (2.0009 bpc)
[3] \res\enwik8+32000000 16000000 -> 3988989 (1.9945 bpc)
[4] \res\enwik8+48000000 16000000 -> 4007152 (2.0036 bpc)
[5] \res\enwik8+64000000 16000000 -> 3993157 (1.9966 bpc)
[6] \res\enwik8+80000000 16000000 -> 4025764 (2.0129 bpc)
[7] \res\enwik8+96000000 4000000 -> 1032769 (2.0655 bpc)
31 seconds

Kernel Time  =     0.936 = 00:00:00.936 =   3%
User Time    =    57.891 = 00:00:57.891 = 189%
Process Time =    58.827 = 00:00:58.827 = 192%
Global Time  =    30.529 = 00:00:30.529 = 100%

For the single threaded version (one 100 MB block) I tested each 3 times.

C:\tmp>timer .\zpaq -m1 -b100 c enwik8.zpaq \res\enwik8

Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
Overwriting archive enwik8.zpaq
[1] \res\enwik8 100000000 -> 22823444 (1.8259 bpc)
56 seconds

Kernel Time  =     0.686 = 00:00:00.686 =   1%
User Time    =    55.458 = 00:00:55.458 =  98%
Process Time =    56.144 = 00:00:56.144 =  99%
Global Time  =    56.488 = 00:00:56.488 = 100%

C:\tmp>timer .\zpaq1 -m1 -b100 c enwik8.zpaq \res\enwik8

Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
Overwriting archive enwik8.zpaq
[1] \res\enwik8 100000000 -> 22823444 (1.8259 bpc)
57 seconds

Kernel Time  =     0.546 = 00:00:00.546 =   0%
User Time    =    55.817 = 00:00:55.817 =  98%
Process Time =    56.363 = 00:00:56.363 =  99%
Global Time  =    56.582 = 00:00:56.582 = 100%

C:\tmp>timer .\zpaq -m1 -b100 c enwik8.zpaq \res\enwik8

Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
Overwriting archive enwik8.zpaq
[1] \res\enwik8 100000000 -> 22823444 (1.8259 bpc)
57 seconds

Kernel Time  =     0.733 = 00:00:00.733 =   1%
User Time    =    55.489 = 00:00:55.489 =  97%
Process Time =    56.222 = 00:00:56.222 =  99%
Global Time  =    56.644 = 00:00:56.644 = 100%

C:\tmp>timer .\zpaq1 -m1 -b100 c enwik8.zpaq \res\enwik8

Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
Overwriting archive enwik8.zpaq
[1] \res\enwik8 100000000 -> 22823444 (1.8259 bpc)
57 seconds

Kernel Time  =     0.639 = 00:00:00.639 =   1%
User Time    =    55.863 = 00:00:55.863 =  98%
Process Time =    56.503 = 00:00:56.503 =  99%
Global Time  =    56.800 = 00:00:56.800 = 100%

C:\tmp>timer .\zpaq -m1 -b100 c enwik8.zpaq \res\enwik8

Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
Overwriting archive enwik8.zpaq
[1] \res\enwik8 100000000 -> 22823444 (1.8259 bpc)
57 seconds

Kernel Time  =     0.592 = 00:00:00.592 =   1%
User Time    =    55.536 = 00:00:55.536 =  98%
Process Time =    56.129 = 00:00:56.129 =  99%
Global Time  =    56.473 = 00:00:56.473 = 100%

C:\tmp>timer .\zpaq1 -m1 -b100 c enwik8.zpaq \res\enwik8

Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
Overwriting archive enwik8.zpaq
[1] \res\enwik8 100000000 -> 22823444 (1.8259 bpc)
57 seconds

Kernel Time  =     0.717 = 00:00:00.717 =   1%
User Time    =    55.817 = 00:00:55.817 =  98%
Process Time =    56.534 = 00:00:56.534 =  99%
Global Time  =    56.894 = 00:00:56.894 = 100%

Edit: compiling in 64 bit Linux g++ 4.5.2 gives the following errors:

matt@matt-Latitude-E6510:~/t$ g++ -O3 zpaq.cpp libzpaq.cpp libdivsufsort-lite/divsufsort.c -fopenmp -o zpaq1 -DNDEBUG
libdivsufsort-lite/divsufsort.c: In function ?int* ss_median3(const unsigned char*, const int*, int*, int*, int*)?:
libdivsufsort-lite/divsufsort.c:358:35: error: cast from ?int*? to ?int? loses precision
libdivsufsort-lite/divsufsort.c:358:35: error: cast from ?int*? to ?int? loses precision
libdivsufsort-lite/divsufsort.c:358:35: error: cast from ?int*? to ?int? loses precision
libdivsufsort-lite/divsufsort.c:358:35: error: cast from ?int*? to ?int? loses precision
libdivsufsort-lite/divsufsort.c:358:35: error: cast from ?int*? to ?int? loses precision
libdivsufsort-lite/divsufsort.c:358:35: error: cast from ?int*? to ?int? loses precision
libdivsufsort-lite/divsufsort.c: In function ?int* tr_median3(const int*, int*, int*, int*)?:
libdivsufsort-lite/divsufsort.c:1136:31: error: cast from ?int*? to ?int? loses precision
libdivsufsort-lite/divsufsort.c:1136:31: error: cast from ?int*? to ?int? loses precision
libdivsufsort-lite/divsufsort.c:1136:31: error: cast from ?int*? to ?int? loses precision
libdivsufsort-lite/divsufsort.c:1136:31: error: cast from ?int*? to ?int? loses precision
libdivsufsort-lite/divsufsort.c:1136:31: error: cast from ?int*? to ?int? loses precision
libdivsufsort-lite/divsufsort.c:1136:31: error: cast from ?int*? to ?int? loses precision

[Gribok]

Unfortunately the new version runs a bit slower on my computer. zpaq uses libdivsufsort-lite for -m1 (default) and -m2 compression. I tested on enwik8 using 16 MB blocks (default, 2 threads) and 100 MB blocks (1 thread) on a 2.0 GHz T3200, 3 GB, under Vista. I compiled with MinGW g++ 4.6.1: "g++ -O3 zpaq.cpp libzpaq.cpp divsufsort.c". zpaq1 is the new version.

I have similar observation with bsc on Silesia corpus. I think this changes is more suitable for large tests like Gauntlet or Manzini's Large corpus. Profiler actually showing that main problem of modern block sorting algorithms is cache misses.

[Alexander Rhatushnyak]

Unfortunately the new version runs a bit slower on my computer. ... I compiled with MinGW g++ 4.6.1: "g++ -O3 zpaq.cpp libzpaq.cpp divsufsort.c". zpaq1 is the new version.

I guess it's more likely because of the difference between
gcc 4.5.2 -O3 -s -fomit-frame-pointer -DNDEBUG
and
g++ 4.6.1 -O3
than the difference between computers.
Among the two executables from my package, which one is faster?
If you have both 4.5.2 and 4.6.1, you can try investigating the reason. If you compile with -save-temps -fverbose-asm, the beginning of .s file will help to see the difference.

I have similar observation with bsc on Silesia corpus.

Maybe some of my proposed optimizations must be disabled. I don't think all of them are useless on Silesia corpus files. Don't you think so?

[Matt Mahoney]

I recompiled zpaq for the tests using the same compiler and options (without -DNDEBUG) and only changed divsusort.c.

[Matt Mahoney]

Here are tests under 64 bit Linux on a Core i7 M620 2.66 GHz, 4 GB. I compiled both zpaq with g++ 4.5.2 with -O3 -DNDEBUG -fopenmp. zpaq1 is compiled with the new divsufsort.c. I changed line 80 from "#if 1" to "#if 0" to fix the compile error. I tested on enwik8 with block sizes 100, 50, 25 MB to test 1, 2, and 4 threads and repeated each test 2 or 3 times. The processor has 2 cores and 2 hyperthreads per core, so zpaq uses 4 threads by default if it can. Well, I can't really say which version is faster from these results.

matt@matt-Latitude-E6510:~/t$ time ./zpaq -m1 -b100 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[1] enwik8 100000000 -> 22823439 (1.8259 bpc)
27 seconds

real	0m27.016s
user	0m33.370s
sys	0m0.290s
matt@matt-Latitude-E6510:~/t$ time ./zpaq1 -m1 -b100 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[1] enwik8 100000000 -> 22823439 (1.8259 bpc)
27 seconds

real	0m26.815s
user	0m33.440s
sys	0m0.270s
matt@matt-Latitude-E6510:~/t$ time ./zpaq -m1 -b100 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[1] enwik8 100000000 -> 22823439 (1.8259 bpc)
26 seconds

real	0m26.848s
user	0m33.510s
sys	0m0.280s
matt@matt-Latitude-E6510:~/t$ time ./zpaq1 -m1 -b100 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[1] enwik8 100000000 -> 22823439 (1.8259 bpc)
27 seconds

real	0m26.760s
user	0m33.430s
sys	0m0.230s
matt@matt-Latitude-E6510:~/t$ time ./zpaq -m1 -b100 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[1] enwik8 100000000 -> 22823439 (1.8259 bpc)
27 seconds

real	0m26.983s
user	0m32.790s
sys	0m0.260s
matt@matt-Latitude-E6510:~/t$ time ./zpaq1 -m1 -b100 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[1] enwik8 100000000 -> 22823439 (1.8259 bpc)
26 seconds

real	0m26.753s
user	0m33.470s
sys	0m0.190s
matt@matt-Latitude-E6510:~/t$ time ./zpaq -m1 -b50 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[2] enwik8+50000000 50000000 -> 11817686 (1.8908 bpc)
[1] enwik8 50000000 -> 11797504 (1.8876 bpc)
16 seconds

real	0m16.292s
user	0m35.390s
sys	0m0.290s
matt@matt-Latitude-E6510:~/t$ time ./zpaq1 -m1 -b50 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[2] enwik8+50000000 50000000 -> 11817686 (1.8908 bpc)
[1] enwik8 50000000 -> 11797504 (1.8876 bpc)
17 seconds

real	0m16.391s
user	0m35.720s
sys	0m0.410s
matt@matt-Latitude-E6510:~/t$ time ./zpaq -m1 -b50 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[2] enwik8+50000000 50000000 -> 11817686 (1.8908 bpc)
[1] enwik8 50000000 -> 11797504 (1.8876 bpc)
16 seconds

real	0m16.038s
user	0m35.690s
sys	0m0.250s
matt@matt-Latitude-E6510:~/t$ time ./zpaq1 -m1 -b50 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[2] enwik8+50000000 50000000 -> 11817686 (1.8908 bpc)
[1] enwik8 50000000 -> 11797504 (1.8876 bpc)
16 seconds

real	0m16.320s
user	0m35.830s
sys	0m0.250s
matt@matt-Latitude-E6510:~/t$ time ./zpaq -m1 -b25 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[1] enwik8 25000000 -> 6101549 (1.9525 bpc)
[2] enwik8+25000000 25000000 -> 6103079 (1.9530 bpc)
[4] enwik8+75000000 25000000 -> 6098279 (1.9514 bpc)
[3] enwik8+50000000 25000000 -> 6122307 (1.9591 bpc)
13 seconds

real	0m13.650s
user	0m48.450s
sys	0m0.540s
matt@matt-Latitude-E6510:~/t$ time ./zpaq1 -m1 -b25 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[3] enwik8+50000000 25000000 -> 6122307 (1.9591 bpc)
[4] enwik8+75000000 25000000 -> 6098279 (1.9514 bpc)
[1] enwik8 25000000 -> 6101549 (1.9525 bpc)
[2] enwik8+25000000 25000000 -> 6103079 (1.9530 bpc)
13 seconds

real	0m13.602s
user	0m50.060s
sys	0m0.560s
matt@matt-Latitude-E6510:~/t$ time ./zpaq -m1 -b25 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[4] enwik8+75000000 25000000 -> 6098279 (1.9514 bpc)
[3] enwik8+50000000 25000000 -> 6122307 (1.9591 bpc)
[2] enwik8+25000000 25000000 -> 6103079 (1.9530 bpc)
[1] enwik8 25000000 -> 6101549 (1.9525 bpc)
14 seconds

real	0m13.583s
user	0m52.050s
sys	0m0.390s
matt@matt-Latitude-E6510:~/t$ time ./zpaq1 -m1 -b25 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[3] enwik8+50000000 25000000 -> 6122307 (1.9591 bpc)
[2] enwik8+25000000 25000000 -> 6103079 (1.9530 bpc)
[4] enwik8+75000000 25000000 -> 6098279 (1.9514 bpc)
[1] enwik8 25000000 -> 6101549 (1.9525 bpc)
14 seconds

real	0m13.604s
user	0m50.180s
sys	0m0.390s

matt@matt-Latitude-E6510:~/t$ time ./zpaq -m1 -b25 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[2] enwik8+25000000 25000000 -> 6103079 (1.9530 bpc)
[3] enwik8+50000000 25000000 -> 6122307 (1.9591 bpc)
[4] enwik8+75000000 25000000 -> 6098279 (1.9514 bpc)
[1] enwik8 25000000 -> 6101549 (1.9525 bpc)
13 seconds

real	0m13.526s
user	0m52.030s
sys	0m0.450s
matt@matt-Latitude-E6510:~/t$ time ./zpaq1 -m1 -b25 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[1] enwik8 25000000 -> 6101549 (1.9525 bpc)
[3] enwik8+50000000 25000000 -> 6122307 (1.9591 bpc)
[4] enwik8+75000000 25000000 -> 6098279 (1.9514 bpc)
[2] enwik8+25000000 25000000 -> 6103079 (1.9530 bpc)
13 seconds

real	0m13.596s
user	0m51.960s
sys	0m0.470s
matt@matt-Latitude-E6510:~/t$ time ./zpaq -m1 -b25 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[2] enwik8+25000000 25000000 -> 6103079 (1.9530 bpc)
[1] enwik8 25000000 -> 6101549 (1.9525 bpc)
[4] enwik8+75000000 25000000 -> 6098279 (1.9514 bpc)
[3] enwik8+50000000 25000000 -> 6122307 (1.9591 bpc)
14 seconds

real	0m13.480s
user	0m52.220s
sys	0m0.470s
matt@matt-Latitude-E6510:~/t$ time ./zpaq1 -m1 -b25 c enwik8.zpaq enwik8
Overwriting archive enwik8.zpaq
[3] enwik8+50000000 25000000 -> 6122307 (1.9591 bpc)
[2] enwik8+25000000 25000000 -> 6103079 (1.9530 bpc)
[4] enwik8+75000000 25000000 -> 6098279 (1.9514 bpc)
[1] enwik8 25000000 -> 6101549 (1.9525 bpc)
14 seconds

real	0m13.599s
user	0m48.340s
sys	0m0.470s

[Alexander Rhatushnyak]

From http://mattmahoney.net/dc/zpaq301.zip => readme.txt :

The enclosed zpaq.exe was compiled with MinGW 4.5.0 and compressed
with upx 3.06w as follows:

g++ -O3 -s -fomit-frame-pointer -DNDEBUG zpaq.cpp libzpaq.cpp divsufsort.c -o zpaq.exe

from http://mattmahoney.net/dc/paq8l.zip => paq8l.cpp :

Recommended compiler commands and optimizations:
MINGW g++:
nasm paq7asm.asm -f win32 --prefix _
g++ paq8l.cpp -DWINDOWS -O2 -Os -s -march=pentiumpro -fomit-frame-pointer -o paq8l.exe paq7asm.obj
...
UNIX/Linux (PC):
nasm -f elf paq7asm.asm
g++ paq8l.cpp -DUNIX -O2 -Os -s -march=pentiumpro -fomit-frame-pointer -o paq8l paq7asm.o

from http://mattmahoney.net/dc/lpaq1.zip => lpaq1.cpp :

To compile (g++ 3.4.5, upx 3.00w):
g++ -Wall lpaq1.cpp -O2 -Os -march=pentiumpro -fomit-frame-pointer
-s -o lpaq1.exe
upx -qqq lpaq1.exe

I've also looked at http://mattmahoney.net/dc/paq9a.zip , http://mattmahoney.net/dc/bbb.zip and http://mattmahoney.net/dc/lpq1v2.zip - there's no clue how they were compiled.

From http://libdivsufsort.googlecode.com/...fsort-lite.zip => Makefile :

CFLAGS = -O3 -fomit-frame-pointer

Why did you decide to compile libdivsufsort-lite 2.1.0 with no -fomit-frame-pointer ?

[Matt Mahoney]

According to http://linux.die.net/man/1/g++ -O (and -O2, -O3) turn on -fomit-frame-pointer. This was not true in older versions.

[Alexander Rhatushnyak]

According to http://linux.die.net/man/1/g++ -O (and -O2, -O3) turn on -fomit-frame-pointer. This was not true in older versions.

MinGW 4.5.2 doesn't turn it on. What about g++ 4.5.2 under 64 bit Linux?

I compiled both zpaq with g++ 4.5.2 with -O3 -DNDEBUG -fopenmp.

[Matt Mahoney]

I don't think 64 bit code uses frame pointers. Parameters are passed in registers instead of on the stack. I didn't try with -m32.