09-13-12 - LZNib

LZNib is the straightforward/trivial way to do an LZ77 coder using EncodeMod for variable length numbers and 4-bit nibble aligned IO. That is, literals are always 8 bit; the control word is 4 bits and signals either a literal run len or a match length, using a range division value instead of a flag bit.

eg. if the nibble is < config_divider_lrl , it's a literal run len; if nibble is >= config_divider_lrl, it's a match.

The point of LZNib is to see how much compression is possible while keeping the decode speed close to the fastest of any reasonable compressor (LZ4,snappy,etc).

Testing different values of config_divider_lrl :

name	raw	config_divider_lrl=4	config_divider_lrl=5	config_divider_lrl=6	config_divider_lrl=7	config_divider_lrl=8	config_divider_lrl=9	config_divider_lrl=10	config_divider_lrl=11	config_divider_lrl=12	best
lzt00	16914	5639	5638	5632	5636	5654	5671	5696	5728	5771	5632
lzt01	200000	199360	199354	199348	199345	199339	199333	199324	199319	199314	199314
lzt02	755121	244328	243844	250836	255146	255177	255257	257754	260107	260597	243844
lzt03	3471552	1746220	1744630	1743728	1743043	1742718	1742728	1743191	1744496	1746915	1742718
lzt04	48649	13932	13939	13968	14015	14120	14184	14268	14319	14507	13932
lzt05	927796	422058	421115	420746	420592	418289	418200	418639	418854	418082	418082
lzt06	563160	414925	414080	412748	412223	409673	408884	408361	408435	407393	407393
lzt07	500000	237756	237318	237004	236910	236771	236949	237381	238091	239176	236771
lzt08	355400	309397	309490	308579	307706	307263	306418	305689	305495	305793	305495
lzt09	786488	302834	303018	303773	304350	305222	307405	308888	310649	314647	302834
lzt10	154624	11799	11785	11792	11800	11821	11843	11866	11885	11923	11785
lzt11	58524	22420	22341	22249	22288	22276	22322	22370	22561	22581	22249
lzt12	164423	28901	28974	28900	28957	29053	29122	29296	29381	29545	28900
lzt13	1041576	1072275	1068614	1058545	1047273	1025641	1025616	1025520	1025404	1024891	1024891
lzt14	102400	52010	51755	51595	51462	51379	51314	51298	51302	51341	51298
lzt15	34664	11846	11795	11767	11760	11740	11740	11756	11831	11837	11740
lzt16	21504	11056	11000	10961	10934	10911	10904	10893	10883	10892	10883
lzt17	53161	20122	20119	20152	20210	20288	20424	20601	20834	21091	20119
lzt18	102400	77317	77307	77274	77045	77037	77020	77006	76964	76976	76964
lzt19	768771	306499	307120	308138	309635	311801	314857	318983	323981	329683	306499
lzt20	1179702	975546	974447	973507	972326	971521	972060	971614	971569	985009	971521
lzt21	679936	99059	99182	99385	99673	100013	100492	101018	101652	102387	99059
lzt22	400000	334796	334533	334357	334027	333860	333733	333543	333501	337864	333501
lzt23	1048576	1029556	1026539	1023978	1021833	1019900	1018124	1016552	1015139	1013815	1013815
lzt24	3471552	1711694	1710524	1708577	1706969	1696663	1695663	1694205	1692996	1688324	1688324
lzt25	1029744	224428	224423	224306	229365	229362	229368	229603	227083	227546	224306
lzt26	262144	240106	239633	239200	238864	238538	238232	237960	237738	237571	237571
lzt27	857241	323147	323098	323274	323133	322050	322068	322799	322182	322573	322050
lzt28	1591760	343555	345586	348549	350601	352455	354077	356025	360583	364438	343555
lzt29	3953035	1445657	1442589	1440996	1440794	1437132	1437593	1440565	1442614	1442914	1437132
lzt30	100000	100668	100660	100656	100655	100653	100651	100651	100643	100643	100643
total	24700817	12338906	12324450	12314520	12308570	12268320	12272252	12283315	12296219	12326039	12212820

The divider at 8 is the same as using a flag bit + 3 bit payload in the nibble.

There does seem to be some win to be had by transmitting divider in the file (but it's not huge). Adaptive divider seems like an interesting thing to explore also, but it will make the decoder slower. Obviously it would be nice to be able to find the optimal divider for each file without just running the compressor N times.

---

Some comparison to other compressors. I tried to run all compressors with settings for max compression and max decode speed.

I'm having a bit of trouble finding anything to compare LZNib to. Obviously the LZ4+Large Window (LZ4P) that I talked about before is a fair challenger. I thought CRUSH would be the one, but it does very poorly on the big files, indicating that it has a small window (?). If anyone knows of a strong byte-aligned LZ that has large/unbounded window, let me know so I have something to compare against.

(ADDENDUM : tor -c1 can do byte-aligned IO and large windows, but it's a really bad byte-aligned coder)

(obviously things like LZ4 and snappy are not fair challengers because their small window makes them much worse; also note that zlib of course has a small window but is the only one with entropy coding; also several of these are not truly "byte aligned"; they have byte-aligned literals but do matches and control words bit by bit, which is "cheating" in this test (if you're allowed to do variable bit IO you can do much better; hell you may as well do huffman if you're doing variable bit IO) (though I'm also cheating because I believe I'm the only LZ here with a proper optimal parser) (I'm also cheating in a more subtle way, because I have this test set to tweak on and others don't)).

(aside : I don't understand why so many people are still writing small-window LZ's. Yes there is a certain use case for small-window LZ (eg. I did one for use on the SPU), but the most common use case for LZ these days is just "decompress the whole thing into a linear memory buffer", in which case you always have the entire buffer available for matches, so why not use it all?)

	raw	minilzo	snappy	quicklz 3	lz4 hc	lzopack -9	ULZ c6	crush cx	zlib	lz4p 332	lznib div8
lzt00	16914	7195	7254	6082	6473	5805	6472	5487	4896	6068	5654
lzt01	200000	198906	198222	200009	198900	198934	199680	222477	198199	198880	199339
lzt02	755121	567421	552599	334625	410695	426187	312889	258902	386203	292427	255177
lzt03	3471552	2456002	2399663	2036985	1820761	1854718	1835797	1938138	1789728	1795951	1742718
lzt04	48649	20602	21170	16894	16709	14858	17359	13869	11903	15584	14120
lzt05	927796	590072	554964	480848	460889	453608	464602	444945	422484	440742	418289
lzt06	563160	536084	516818	563169	493055	490308	428137	432989	446533	419768	409673
lzt07	500000	297306	298207	268255	265688	242029	268271	245662	229426	248500	236771
lzt08	355400	356248	351850	317102	331454	314918	337423	315688	277666	322959	307263
lzt09	786488	460896	472498	372682	344792	345561	329608	304048	325921	325124	305222
lzt10	154624	21355	25960	17249	15139	14013	16238	12540	12577	13299	11821
lzt11	58524	28153	29121	25626	25832	23717	26720	23279	21637	23870	22276
lzt12	164423	52725	53515	38745	33666	31574	36077	29601	27583	30864	29053
lzt13	1041576	1045665	1041684	1041585	1042749	1041633	1048598	1061423	969636	1040033	1025641
lzt14	102400	61394	63638	55124	56525	52102	58509	51491	48155	53395	51379
lzt15	34664	16026	15417	13626	14062	12663	14016	12470	11464	12723	11740
lzt16	21504	12858	13165	11646	12349	11203	12554	11119	10311	11392	10911
lzt17	53161	28075	29415	23478	23141	20979	23829	19877	18518	22028	20288
lzt18	102400	100499	97931	81100	85659	74268	89973	76858	68392	79138	77037
lzt19	768771	495312	524686	411916	363217	360558	333732	302006	312257	335912	311801
lzt20	1179702	1181855	1161896	1037098	1045179	1042190	1013392	952329	952365	993442	971521
lzt21	679936	240528	240244	188446	194075	174892	125322	103608	148267	113461	100013
lzt22	400000	401446	397959	338837	361733	354449	355978	321598	309569	348347	333860
lzt23	1048576	1052692	1048694	1048585	1040701	1030737	1047609	985814	777633	1035197	1019900
lzt24	3471552	2668424	2613405	2425865	2369885	2521469	2040395	2080506	2289316	1934129	1696663
lzt25	1029744	361885	425735	351577	324190	326180	477377	297974	210363	332747	229362
lzt26	262144	261152	259327	244555	246465	242343	252297	237162	222808	244990	238538
lzt27	857241	460703	466747	435522	430350	395926	392139	335655	333120	353497	322050
lzt28	1591760	578289	617498	453170	445806	421804	401166	349753	335243	388712	352455
lzt29	3953035	2570903	2535625	2259281	2235299	2052597	2227835	2013763	1805289	1519904	1437132
lzt30	100000	100397	100015	100009	100394	100033	100782	112373	100020	100393	100653
total	24700817	17231068	17134922	15199691	14815832	14652256	14294776	13573404	13077482	13053476	12268320

BTW I finally got most of these compressors linked into my own test bed for this post. Review of their API's (and some ranting) :

minilzo , quicklz, LZ4 : yes, good, easy. API is basically compress(char *,int len,char *), as it should be.

One minor niggle with these guys : I'm actually leaning towards compress API's taking "void *" now for buffers. It's annoying dealing with API's where somebody thinks "char *" is the way to take an array and someone else wants "const unsigned char *", etc. If it's just memory, take void *, I think. I'm not completely sure about that.

Oh, also "uncompress" ? Where did that come from? It's "decompress". Come on!

Oh, and about LZO : so minilzo is nice and clean, but it only gives you access to the most crappy compressor. To get the good LZO variants you have to use the full LZO sdk which is a nightmare. So I didn't bother and just ran lzopack -9.

miniz : I don't love the single file miniz.c thing; I'd like to have an implementation .c and a header with the externs. It makes it way harder to read the externs and see what is supposed to be public. I also don't like the custom types (mz_uLong and such), I like "int" (I guess "size_t" is okay). But not bad, way better than :

zlib : WTF WTF ridiculous clusterfuck. There's an MSVC make file that seems to make a lib that is not what you want. Then the contrib has some projects for two MSVC versions and not others; then you have to make sure that you get the DLL import and WINAPI defines in your import the same as the built lib. Much hair pulling due to "_deflate not found" link errors.

(BTW I don't entirely blame zlib for that; how many man hours have been wasted due to the linker being so damn unhelpful. Hey jerks who work on the linker, if I'm trying to import "__stdcall deflate" and you only have "__cdecl deflate" then perhaps you could figure out that just maybe I wanted those to hook up. We've only been having this damn problem for the last 20 years. It's the kind of thing where one decent human being on that team would go "hmm I bet we could do something better here". The linker is like the overly precise nerd; if you ask "can you pass the salt" he's like "no, I don't have any salt" , and you're like "fuck you, I can see the salt right next to you" and he's like "nope, no salt", and you're like wtf wtf so you walk around and grab it and you say "okay, what's this?" and he says "that's kosher salt").

Compressed sizes from zlib were slightly smaller than miniz, so I posted them.

lzma : this is a mixed bag; the C++ interface is a total disaster of COM insanity, but you can avoid that and the C interface (LzmaEnc/LzmaDec) is okay. A bit of a mess and you oddly have to handle the props transmission yourself, but so much better than the C++ interface that it looks great in comparison. Very bizarre to expose so many technical encoder settings in the basic API though.

snappy : WTF ? No MSVC build, it uses some crazy STL crap for no reason (iostreams? are you kidding me? using std::string for buffers? WTF), it's all overly complex and bad-C++y. Really gross. There's a mess of files and I can't tell which ones I actually need. Oh, and it generates warnings like crazy; so it's all bloated "clean style" but not actually clean, which is the worst way to be. And then after futzing around with it, I'm rewarded with a really crappy compressor.

I guess I see the point of snappy; it's LZRW1 for modern CPUs. Okay, that's fine. And it is reasonably fast even on incompressible data. So it has a certain use case, perhaps for disk compression, or I guess Google uses it for network data compression or some such. But people have been taking snappy and using it as just a utility data compressor and it is totally terrible for that.