bzip3 compression support

[pete4abw]

@kspalaiologos has contributed a PR #85 which has been integrated into branch bzip3_poc. bzip3 is a "spiritual successor" to bzip2. bzip3 is very fast and outperforms bzip2. While my position continues to be leaning towards getting rid of inferior compression methods, if bzip3 proves both stable and effective, it may creep into the main branch after thorough vetting. While there are still bugs in decompressing, this poc is there for people to look at.

[pete4abw]

Here's the decompression bug: @kspalaiologos . It's a threading issue, obviously.

Fill_buffer stream 1 c_len 5,147,508 u_len 33,550,336 last_head 57,589,094
Starting thread 9 to decompress 5,147,508 bytes from stream 1
internal error: out of thread states.Fatal error - exiting

[pete4abw]

This bug has been squashed. See the bzip3_poc branch and check it out.

[pete4abw]

A comparison of a kernel 6.0 tar file which has been compiled. This includes kernel source, vmlinux and vmlinuz kernels, object, library, driver, and header files. lrzip-next+bz3 provides consistent compression levels and speeds throughout all levels, but greater speed than lrzip-next+lzma at higher levels. lrzip-next+bz3 decompression is slower for all levels.. The following charts illustrate. @kspalaiologos . More work needed to integrate fully and I'm reviewing thread locking that may not be needed...

[kspalaiologos]

Hello. I am somewhat confident that the block size setting code might not work correctly, however, I can't find the issue.

[pete4abw]

Need to look at open_stream_out() function in stream.c and block size defaults for bzip3. Many blocks are created where I think they should not be. This reduces compression potential as well as slows down decompression. open_stream_out will reduce block size based on a minimum thread count of 4. This means, for bz3, it cannot have a larger block size than 64MB. This is an arbitrary limit hard coded for now. However, running with -p3 or -p2 will override that limit. For a 16GB system that upper limit for bz3 will be bs=7 or 128MB. This is current output with -L9 where each block is 64MB. lzma2 and hence lzma uses a variable block size which give me a little flexibility in choosing the max possible block size. Larger systems may not have this limit.

$ lrzip-next -vvi kernel-6.0.tar.B9.lrz
Using configuration file /home/peter/.lrzip/lrzip.conf
Detected lrzip version 0.9 file.
Rzip chunk:       1
Chunk byte width: 4
Chunk size:       2,063,124,480
Stream: 0
Offset: 26
Block   Comp    Percent        Comp Size /     UComp Size            Offset :           Head
1       bzip3    50.5%         7,159,241 /     14,169,274       176,101,071 :              0
Stream: 1
Offset: 39
Block   Comp    Percent        Comp Size /     UComp Size            Offset :           Head
1       bzip3    23.4%        15,688,535 /     67,104,768                52 :     15,688,574
2       bzip3    20.9%        14,031,893 /     67,104,768        15,688,600 :     29,720,480
3       bzip3    15.8%        10,626,533 /     67,104,768        29,720,506 :     40,347,026
4       bzip3    18.1%        12,157,221 /     67,104,768        40,347,052 :     52,504,260
5       bzip3    15.6%        10,484,661 /     67,104,768        52,504,286 :     62,988,934
6       bzip3    15.1%        10,124,953 /     67,104,768        62,988,960 :     73,113,900
7       bzip3    15.1%        10,116,418 /     67,104,768        73,113,926 :     83,230,331
8       bzip3    13.8%         9,283,063 /     67,104,768        83,230,357 :     92,513,407
9       bzip3    14.8%         9,899,340 /     67,104,768        92,513,433 :    102,412,760
10      bzip3    15.4%        10,354,253 /     67,104,768       102,412,786 :    112,767,026
11      bzip3    13.4%         8,997,852 /     67,104,768       112,767,052 :    121,764,891
12      bzip3    11.1%         7,430,228 /     67,104,768       121,764,917 :    129,195,132
13      bzip3     2.2%         1,503,758 /     67,104,768       129,195,158 :    130,698,903
14      bzip3     2.6%         1,747,827 /     67,104,768       130,698,929 :    132,446,743
15      bzip3    13.7%         9,200,240 /     67,104,768       132,446,769 :    141,646,996
16      bzip3    12.5%         8,378,193 /     67,104,768       141,647,022 :    150,025,202
17      bzip3    25.7%        17,216,944 /     67,104,768       150,025,228 :    167,242,159
18      bzip3    13.2%         8,858,873 /     67,104,768       167,242,185 :    183,260,299
19      bzip3    14.1%         6,361,320 /     45,020,801       183,260,325 :              0

Summary
=======
File: ../kernel-6.0.tar.B9.lrz
lrzip-next version: 0.9 file
Compression Method: rzip + bzip3 -- Block Size: 67,108,864
Rzip Compression Level: 9, Lrzip-next Compressinn Level: 9

  Stats         Percent       Compressed /   Uncompressed
  -------------------------------------------------------
  Rzip:          61.4%     1,267,075,899 /  2,063,124,480
  Back end:      15.0%       189,621,346 /  1,267,075,899
  Overall:        9.2%       189,621,346 /  2,063,124,480

  Decompressed file size:  2,063,124,480
  Compressed file size:      189,621,674
  Compression ratio:              10.880x, bpb: 0.735

  MD5 Checksum: 64ccc490fb95cf9f80b1f2b1968d923d\

$ lrzip-next -vvi kernel-6.0.tar.L9.lrz
Using configuration file /home/peter/.lrzip/lrzip.conf
Detected lrzip version 0.9 file.
Rzip chunk:       1
Chunk byte width: 4
Chunk size:       2,063,124,480
Stream: 0
Offset: 26
Block   Comp    Percent        Comp Size /     UComp Size            Offset :           Head
1       lzma     52.1%         7,378,702 /     14,169,274       128,936,330 :              0
Stream: 1
Offset: 39
Block   Comp    Percent        Comp Size /     UComp Size            Offset :           Head
1       lzma     14.9%        76,859,833 /    515,784,704                52 :     76,859,872
2       lzma     10.1%        52,076,419 /    515,784,704        76,859,898 :    136,315,019
3       lzma     16.4%        36,269,486 /    221,337,217       136,315,045 :              0

Summary
=======
File: ../kernel-6.0.tar.L9.lrz
lrzip-next version: 0.9 file
Compression Method: rzip + lzma -- lc = 3, lp = 0, pb = 2, Dictionary Size = 100,663,296
Rzip Compression Level: 9, Lrzip-next Compressinn Level: 9

  Stats         Percent       Compressed /   Uncompressed
  -------------------------------------------------------
  Rzip:          61.4%     1,267,075,899 /  2,063,124,480
  Back end:      13.6%       172,584,440 /  1,267,075,899
  Overall:        8.4%       172,584,440 /  2,063,124,480

  Decompressed file size:  2,063,124,480
  Compressed file size:      172,584,560
  Compression ratio:              11.954x, bpb: 0.669

  MD5 Checksum: 64ccc490fb95cf9f80b1f2b1968d923d

[kspalaiologos]

Curiously, bzip3 alone beats lrzip-next+lzma on all levels:

 % bzip3 -feb511 -j3 linux-6.0.2.tar
bzip3 -feb511 -j3 linux-6.0.2.tar  114.36s user 2.90s system 231% cpu 5592M memory 50.581 total
 % wc -c linux-6.0.2.tar*
1340426240 linux-6.0.2.tar
 129296823 linux-6.0.2.tar.bz3
 135518689 linux-6.0.2.tar.lrz

[pete4abw]

Yes. For text only files, it performs excellently. My test file included all binaries in the kernel tree. But time-wise, it is far superior. This is a file containing several 5.x kernel sources. Of course, any file can yield different results. What I find interesting is how much better bzip3 performs with lrzip-next. I think bzip3 would perform even better with a larger block size (not just bzip3 block, but lrzip-next block). For example, the first compression thread was 689MB for lzma, but only 64MB for bzip3. I think a larger uncompressed input would yield better compression output. I'll look at open_stream_out() and check your contribution there.

lrzip-next command line: lrzip-next -L9|-BL9 file
bzip3 command line (-j3 option was invalid) bzip3 -eb511 file

Included files in kernel.5.x.tar

linux-5.4.209.tar
linux-5.10.135.tar
linux-5.15.59.tar
linux-5.18.16.tar
linux-5.19.tar

5,585,520,640  kernel.5.x.tar
 174,309,935  kernel.5.x.tar.B9.lrz 1:21
 170,183,377  kernel.5.x.tar.L9.lrz 5:29
 601,313,270  kernel.5.x.tar.bz3 6:07

[pete4abw]

After some more tweaking of the overhead values for bzip3 results for text only kernel 5.x files (as shown above), the results are impressive, @kspalaiologos . It should be made clear, these results are the integration of bz3 into lrzip-next, not standalone programs. For compression, at all levels except a small difference in L9, bzip3 has superior compression with better time performance at higher levels. For decompression lrzip+lzma performs better. With mixed value files, lrzip+lzma performs better in size, but bzip3 better in time for compression.

[pete4abw]

Updates pushed, but had to revert overhead computation to 6 * BS per spec. Will take a look at using the lzma2 style dictionary size methods to decrement block sizes for bzip3 in open_stream_out(). This would require some tweaks to the way block sizes are encoded. We would need more values for bzip3_bs to accommodate intermediate thread block size values. Stay tuned.

[pete4abw]

Since @kspalaiologos recommended 32MB as the floor and 511MB is the ceiling, block sizes may be evaluated as follows: Taking advantage of the lzma2-style dictionary size computation, we may use the following. Per thread memory overhead will be bs * 6 depending on ram. If sufficient ram is not available, threads and bs size will be decremented in open_stream_out(). Work is ongoing on this and will be pushed after testing.

bzip3 bs code	Block Size	lzma2-computation
0	32MB	( 2 * 2^24 )
1	48MB	( 3 * 2^24 )
2	64MB	( 2 * 2^25 )
3	96MB	( 3 * 2^25)
4	128MB	( 2 * 2^26 )
5	192MB	( 3 * 2^26 )
6	256MB	( 2 * 2^27 )
7	384MB	( 3 * 2^27 )
8	511MB	( 2 * 2^28 -1 )

[pete4abw]

Changes pushed. Test away.

[pete4abw]

The bzip3_poc branch has been merged into the Whats-Next branch and is stable for review and testing. Thanks to @kspalaiologos for the efforts. The bzip3_poc branch is terminated and will remain for legacy and review purposes.

[pete4abw]

Update in whats-next branch in computation of block size. Now, bs=compression_level-1.