Fast LZMA2 library with radix matchfinder

**Conor** · 14th January 2018, 15:57

I've recently done more work on the buffered radix matchfinder I used in the experimental Radyx archiver (https://encode.su/threads/2134-Radyx-archiver). It's simpler and faster than the one in Radyx, and I doubt there's much more scope for improvement. The library is written in C. I used some performance tricks and portability code from Zstandard.

I posted a 2-thread Silesia comparison graph in the github project: https://github.com/conor42/fast-lzma2
The performance gap over 7-zip is even higher with 4 threads than 2.

It's work in progress and there's no DLL build yet, only a fuzzer and a benchmark. I've made a 7-zip fork which uses the library by default, which I'll upload with binaries once I sort out building all the components.

Regards,
Conor

**Gonzalo** · 14th January 2018, 19:18

It would be really nice to give it a try. I really loved the old Radyx. Unfortunately, I don't have a Windows box around, but I could test under WINE if someone were to provide a binary. Thanks in advance to anyone who help with this.

**redrabbit** · 15th January 2018, 16:24

I compiled the code with visual studio 2015 i got a .exe (bench.exe) and one dll (libflzma2.dll) don't know how to use
I attach de binaries

**Jyrki Alakuijala** · 15th January 2018, 17:09

Originally Posted by Conor

I've recently done more work on the buffered radix matchfinder ...

Would it make sense to implement it within brotli or zstandard?

**Gonzalo** · 15th January 2018, 17:52

Originally Posted by redrabbit

don't know how to use

It is not intended to use as a file compressor / archiver, instead it performs a benchmark using the file you provide as argument.

Code:

bench.exe file.bin

**Gonzalo** · 15th January 2018, 18:04

@Conor: I get an error on several files. The only thing I found in common between them is that they are already compressed (pdfs, mp3, xz, etc). They are of different sizes but there is always the same error:

Code:

FL2_decompressDCtx() failed on size 4294967286 : Corrupted block detected

**Conor** · 15th January 2018, 23:46

It actually failed on compression but wasn't checked. The benchmark code is a little rougher than the rest. I halved the output buffer size to save memory, but never changed it back, so it's too small for incompressible data.
Fixed now. Thanks for finding it.

The 7-zip mod is nearly done so I'll upload binaries here and people can try archiving with it.

**Bulat Ziganshin** · 16th January 2018, 05:30

Originally Posted by Jyrki Alakuijala

Would it make sense to implement it within brotli or zstandard?

i would say that it makes more sense to implement it with codecs faster than lzma because
1) it losts some compression due to its block-wise nature
2) sorting match finders have potential up to multi-GB/s processing speed

**Conor** · 16th January 2018, 09:21

Originally Posted by Jyrki Alakuijala

Would it make sense to implement it within brotli or zstandard?

I combined it with a zstd encoder a while back, and it works well for level 12 or 13 up. The problem with faster levels is they skip many positions without searching for matches, so an algorithm which searches all positions can't compete. It makes optimization cheaper so levels 4-12 of my lzma2 library use optimal parsing.

Integration with zstd is messy. The threading model is different and so is the interaction between the matchfinder and encoder.

**nemequ** · 16th January 2018, 11:08

In case anyone wants to try this out on Linux (or anything other than VS): https://github.com/conor42/fast-lzma2/pull/1 (includes rudimentary CMake support).

**Conor** · 16th January 2018, 14:52

Originally Posted by nemequ

In case anyone wants to try this out on Linux (or anything other than VS): https://github.com/conor42/fast-lzma2/pull/1 (includes rudimentary CMake support).

Merged. Thanks

**nemequ** · 16th January 2018, 19:55

Is this compatible with existing lzma2 decoders? AFAICT it isn't, but the name makes it sound like it is… If it isn't you should probably make that clear in the README and project summary on github, and/or consider a different name.

**Conor** · 17th January 2018, 02:30

Originally Posted by nemequ

Is this compatible with existing lzma2 decoders? AFAICT it isn't, but the name makes it sound like it is… If it isn't you should probably make that clear in the README and project summary on github, and/or consider a different name.

Yes but you need to drop the dict size property byte off the front of the stream and feed the rest into the decoder, or you can disable writing the prop byte. It's done in my 7-zip fork which uses the library.

**Conor** · 30th January 2018, 14:02

Heaps of testing done and DLLs for x86 and x64 are now beta-released on github: https://github.com/conor42/fast-lzma2/releases

7-Zip 18.01 fork is released also: https://github.com/conor42/7-Zip-FL2/releases
I found a way to add it as a new matchfinder by modifying the standard Lzma2Encoder object to redirect compression to the new library if HC or BT matchfinders are not specified. RMF is the default in this release.

**Conor** · 29th March 2019, 18:16

After a great deal of work to get the library into a mature state, I have released v1.0.0. It includes some optimizations, including some of Igor Pavlov's recent work. The speed is up by around 5% - 8%. I did a massive amount of fuzz testing, and also archiving random file selections both in Radyx and 7-Zip. I think my computer is nearly worn out

I've released only the command line tool from 7-Zip-FL2 19.00 with Fast LZMA2 as the default. All of the other 7-Zip components will be in the next 7-Zip-zstd release if Tino is happy with it.
Edit: there's a 7-Zip plugin too.

Finally, the XZ fork FXZ is working well. Reports of success building/testing it on non-x86 systems are most welcome

**Shelwien** · 29th March 2019, 18:38

Do you have any ideas about how to make a lzma matchfinder with explicit support for fuzzy matches?
http://nishi.dreamhosters.com/u/lzmapat_v0.rar

**Conor** · 29th March 2019, 19:01

Originally Posted by Shelwien

Do you have any ideas about how to make a lzma matchfinder with explicit support for fuzzy matches?
http://nishi.dreamhosters.com/u/lzmapat_v0.rar

I have no ideas about how to make it work well.

**Conor** · 30th March 2019, 02:33

Originally Posted by Shelwien

Do you have any ideas about how to make a lzma matchfinder with explicit support for fuzzy matches?
http://nishi.dreamhosters.com/u/lzmapat_v0.rar

Also, the LZMA optimizer has a related idea where it finds a combination of match, literal, rep match. The three together constitute a match containing 1 non-matching byte. The basic idea of rep matches can be seen as a workaround for doing fuzzy matching.

**Shelwien** · 30th March 2019, 02:51

Yes, that's why I asked. But lzma matchfinder only provides one match of each length, and rep-matches are later added during heuristic pattern check.
I'm pretty sure that explicit fuzzy matchfinder can find better matches and improve compression even with current lzma format.
But its also interesting to investigate different methods of fuzzy match coding.
For example, instead of current match-literal-rep_match patterns, we could encode one long match, then some patch codes.
Or there's the example of bsdiff, which actually also works with fuzzy matches, and handles them by separating literal and match streams -
LZ part of bsdiff actually never changes the length of literal stream, but subtracts the matches from it, so some parts turn to zeroes,
and some other parts (mostly offsets in executable code) turn to repeated deltas. Then later its processed with something like RLE to
remove zeroes, but that's less relevant.

Btw, with lzma2, there's another obvious option for compression improvement - lzma2 block headers can change lc/lp/pb options.
Somehow I've never seen an encoder which could optimize these, though.

**Conor** · 30th March 2019, 06:08

Yes the current lzma only loses a small amount if the match-lit-rep pattern is removed, probably because the matchfinder is not designed to search for it.

I've thought about optimizing lc/lp/pb for extreme compression. It would be best, but slow, to test all combinations. Maybe a statistical analysis could find the best numbers in advance.

**Shelwien** · 30th March 2019, 10:42

> Yes the current lzma only loses a small amount if the match-lit-rep pattern is removed,
> probably because the matchfinder is not designed to search for it.

I actually tested that: https://encode.su/threads/1288-LZMA-...ll=1#post25165
Apparently some data types rely on rep0 (=fuzzy matches) quite a lot even as is.

Btw, I found that unpacking the rep-tokens, then using a simple greedy parser to recreate them
actually improves compression a little.

> I've thought about optimizing lc/lp/pb for extreme compression. It would be best, but slow, to test all combinations.
> Maybe a statistical analysis could find the best numbers in advance.

No need to test all combinations.
Either test a few popular ones (8/0/0 for text, 0/2/2 for 32-bit data, 3/0/2 the default, maybe a few more).
Or test options separately (find best lp, then best lc, then pb up to lp).

**Conor** · 6th May 2019, 10:15

Version 1.0.1 release: https://github.com/conor42/fast-lzma2/releases

This is mostly to make a proper POSIX build system. The root makefile builds a shared library, which can be installed with `make install`. There will be no 7-Zip or fxz releases with this version.

**joerg** · 6th May 2019, 10:44

@Conor

i am now using https://github.com/conor42/7-Zip-FL2/releases
it performs very well .. faster

will you release a new version of radyx ?

https://github.com/conor42/Radyx/releases

Thank you very much for your wonderfull programs!

best regards

**Conor** · 6th May 2019, 15:38

Originally Posted by joerg

will you release a new version of radyx ?

https://github.com/conor42/Radyx/releases

I will at some point. When I get to it depends on how much work I have to do over the coming months.

**dado023** · 13th May 2019, 00:42

is it possible to use this with normal 7-zip file manager on windows?...i would like to test it.

**Conor** · 13th May 2019, 07:36

Originally Posted by dado023

is it possible to use this with normal 7-zip file manager on windows?...i would like to test it.

Yes, you can select it in the file manager compress dialog in 7-Zip-zstd: https://github.com/mcmilk/7-Zip-zstd/releases

**78372** · 27th May 2019, 19:08

Can you provide a pascal example for these dlls? I am not familiar with C++

**Conor** · 28th May 2019, 04:28

Originally Posted by 78372

Can you provide a pascal example for these dlls? I am not familiar with C++

I haven't used pascal for a long time so there are no pascal examples, but if you look in the dev branch, test/file_test.c has a C example which is simpler than the C++ in 7-Zip-zstd.

**Conor** · 22nd October 2019, 18:23

Released fxz 1.1.0alpha, including an Arch PKGBUILD. I think fxz is complete now if no issues emerge.

**Gonzalo** · 22nd October 2019, 21:58

Lil bug report... Very unable to build. System: Manjaro (up to date). Method: PKGBUILD

--------------------------

EDIT: Manual compilation OK. Testing now. Anything we should know about testing? For example, max RAM usage for each preset, or if this is compatible with all the 7-zip flzma2 options

Thread: Fast LZMA2 library with radix matchfinder

Thread Tools

Search Thread

Display

Fast LZMA2 library with radix matchfinder

Thanks (9):

Thanks:

Thanks:

Thanks:

Thanks (2):

Thanks (5):

Thanks:

Thanks:

Thanks:

Thanks:

Similar Threads

TarsaMatchFinder - complete match finder based on radix sort

lzma2 stream detector

Radix sort match finder

lzma's binary tree matchfinder

Nibble MMC matchfinder

Posting Permissions