NNCP: Lossless Data Compression with Neural Networks (2019)
bellard.org
bellard.org
"The lossless data compressor employs the traditional predictive approach: at each time t, the encoder uses the neural network model to compute the probability vector p of the next symbol values t knowing all the preceding symbols s0 up to st−1. The actual symbol value st is encoded using an arithmetic encoder with approximately −log2 ( pst ) bits. Then the model is updated knowing the symbol st. The decoder works symmetrically so there is no need to transmit the model parameters. It implies both encoder and decoder update their model identically.
When no preprocessing is done, st represents the byte at position t. Hence there are Ns= 256 different symbol values from 0 to Ns−1."
For those usually familiar with Huffman coding this is using an Arithmetic coding https://en.wikipedia.org/wiki/Arithmetic_coding
It allows adaptive coding (i.e. changing the probabilities of symbols dynamically). Here these probabilities are modelled dynamically using a neural network.
The magic is that the neural network parameters are defined implicitly : You don't need to transmit the neural network parameters, therefore you can use as big as you want neural network.
During the decoding the from scratch network is continuously trained using the freshly decoded data, in the same way that it was during the encoding. The more data you compress, the more you train the internal neural network parameters, and the better the prediction for next character gets.
You decode 20 bytes, you update the model with this new data, you decode 20 new bytes with the new model, you update the model,... , every 1000000 bytes you can even update your model multiple times using all currently available data to make the network converge faster.
Of course this only works if everything is exactly deterministic, which Fabrice Bellard took great effort in guaranteeing, which is no small engineering feat.
As described, arithmetic coding does a 1:1 mapping of input-output, while NN deterministically generates probability distribution for the arithmetic coding. Conceptually, it would work with any deterministic / reproducible function, even a PRF or a running hash, though the point of NN is to give good distribution estimates for interesting inputs, thus short output from the arithmetic encoder.
Presumably, there are some limited choices during coding, which then need to be encoded as well.
Because of training is deterministic and the same data is presented during encoding and decoding, the weights of encoder and decoder are always kept in sync, such that the network used when encoding the nth byte is exactly the same as the network used when decoding the nth byte.
The weights of the network are the internal state.
The figure is given in nncp_v2.1.pdf. This is 1000x slower than xz, which in turn is 1000x slower than gzip.
I have always wondered if a compression service could be a viable commercial offering and with NNCP rates and its compression speed, it looks like it could! That's for cases when you need to really compress the heck out of something, e.g. prior to distributing a large static piece of data to a very large number of recipients. I think there was a service like this, used by AAA game developers for distributing patches, but it didn't take because it had a very slow decompression... and, now reading further through the paper, it looks like an issue with NNCP too -
The NNCP v2 decompression speed is similar to its compression speed.
I know shipping speeds are important, but it seems game developers could try harder with delta compressing their updates, because it's hard to believe a tens-of-GBs download is the best they could do when you already have a BluRay disk or something (unless it's new content, of course)
I wonder how much their bandwidth costs are and how quickly a reduction would pay itself.
I'm not sure how viable this is today, or ever was: Many residential connections are heavily asymmetric. Players presumably aren't too excited either by the idea of continuing to seed while they already play online, with shitty ISP-provided routers suffering hundreds of milliseconds of bufferbloat whenever the uplink is saturated.
Yes, WoW used to have bit-torrent based update.
>Many residential connections are heavily asymmetric.
this is a US centric-view, though. For instance I have 300Mb up/down. At least for most of the Europe (and I suppose Asia), it's pretty common not to be restricted in any way.
I could leave a bit-torrent client non-stop and won't feel it. Like I've said: alas. There is some stigma associated with p2p/torrents.
While asymmetric connections make sense for many residential use cases, P2P is not one of them.
I live in Europe and I have a 1000/0.5 Mbit/s connection.
I've seen 20:1 offers on cable providers, but it's mostly marketing BS, as you're unlikely to get full download speed in most circumstances due to upload limitations.
I do reach the full downlink speed though due to (presumably) ACK compression in the modem and ACK synthesis/reexpansion in the CMTS. You are right that otherwise such a high ratio would not be feasible with TCP.
IME, the line starts to choke when you actually want to send requests and they compete with ACKs and your internet stutters and crawls in both direction. Though that was with a slower connection - it's harder to fill a bigger pipe.
BTW, is the ACK compression counted for consumers benefit?
No more ACKs? No more DL!
In the Philippines, 15 Mbps down / 3 Mbps up ADSL with a static public IP is not something that a foreigner could easily buy. Globe Telecom in Cebu asked for evidence that I have sufficient income to pay for this (2600 PHP per month), and their rules only allow documents from the Philippines, so my bank statement was rejected. I had to talk to their higher-level manager to negotiate an exception. And their default router has 2 seconds of bufferbloat, so I bought a TP-Link Archer C7 and installed OpenWRT to compensate.
Given the layers of encryption and obfuscation, and leaving aside the merits or otherwise of DRM in the first place, I can imagine it could be hard to do delta patching. At least, without making it easier to crack the DRM - e.g. you’d presumably have to decrypt the asset that needed patching, apply the delta, and re-encrypt/re-sign it all client side.
In a place with ubiquitous fast broadband, a compromise with regard to decompression speed might be ok.
If you're sending something to mars... 2 kb/sec might make sense.
Keep in mind that 2KB/s is on something like 3090... Massively power hungry even on the decompression.
You might be interested: Zstandard has an adaptive mode that attempts to do this.
Apologies if this is a noob question, but could you improve it with training?
Considering all other things like GPU, code quality etc. equal, the speed here mainly depends on the size of the network. Larger networks result in better performance (logarithmic), but also slower speeds (linear). There are some tricks like pruning to create significantly smaller networks with similar-ish performance, but good models are often large.
Unrelated to your question, what nobody mentions is that the decompression side also needs to complete network. With 57M and 187M parameters, those files are going to be quite large, > 100MB for sure. That completely annihilates the performance wins for 1 time transfers.
https://news.ycombinator.com/item?id=27244810
it's a very clever use of symmetry.
LZ78 used it "just" to build a dictionary, but the general idea of using symmetry is there.
(A fascinating variant on this is Semantic Dictionary Encoding, by Dr Michael Franz in his doctoral dissertation (1994), that used this symmetry to compress partial ASTs to cache partially generated code for runtime code generation)
As I understand it, when starting up (beginning of stream) - the network does not compress, then guesses the next byte at every turn determininstically from input so far.
Decoding can "read" the fist byte, then proceed to learn and guess the second byte and so on.
Each file is really its own special theoretical multivariate space to find the best theoretical compression ratio. Usually finding the optimal or near-optimal compression is the hardest computationally.
And it's basically a perfectly cacheable computation if you have some sort of database mapping algorith + parameters to apply to a given file.
Decompression usually isn't as big a deal for performance.
Anyway an online database for a service that has actively tried to take a known common file (match on filesize, hash, etc) down to its best compressed representation so 1) we don't have to do it every time.
Cloud providers would presumably love these, since S3 probably has millions copies of many files and would 1) get to compress the file and 2) get to share its representation across all instances.
LZ4HC is LZ4 compressed with the slow compressor to achieve better compression. It is decompressed using regular LZ4 decompressor.
They also compare with zstd and lzma, which are the open source competition.
I don't know what "specs" you think are missing. They do say which architectures are supported, what the memory use is, whether multi-threading is supported, etc.
No public price, true.
You can read the blogs of the people who work on this code to get a feel for the caliber:
https://cbloomrants.blogspot.com/
https://fgiesen.wordpress.com/
These are known people with known reputation. The product itself is well known in the industry.
So what is it that causes this big gulf in productivity? I know that as a programmer I have all sorts of internal and external obstacles to just sitting down and churning out entire projects, let alone something useful with clever and high-quality code. Is a 10x rockstar just somebody who's been able to eliminate most of their obstacles, and has some amount of talent left over to solve problems with?
'Hero Worship' is about elevating someone to a categorically higher level. This can lead to thinking you could never be as good, taking everything they say as gospel, defending even their poor opinions, etc.
If we -worship- 10x developers, you can maybe better see how with the emphasis on that word things can get pretty toxic pretty quick. For example, I think many would agree HR disputes should not take talent level as an input, but if one of those people isn't even a mortal...
---
None of this is necessary to have a role model, or precludes celebrating someone for doing excellent work as is this case.
would anyone look at Usain Bolt and say that he's mortal and just like everyone else? Why is it so difficult to imagine that there are people who are just so much better than you, that you (an average person) can never catch up?
Most people have no trouble understanding that they cannot reach the level of Usain Bolt. Why should programming be any different from sprinting in this case?
I would argue that innate talent is strongly linked to genetics. In the case of coding, I think intelligence plays a large role.
I do not believe there is much of a spread in intelligence based on genetics. Short of disability, and given the same consistency, training, and opportunities I seriously doubt that anything even remotely close to a 10x gap would be seen.
I am certainly not keen on the science of the topic though, biology is certainly my worst subject. But I have heard of no research showing such a divide.
If you put Manchester City up against a team consisting of average people who are fit and know how to play soccer it's pretty easy to see Manchester City scoring 10x the goals - at least.
2) If quantified the performance gap between me (unfit, untrained) and Bolt will be smaller than the gap between me (practised programmer) and Bellard.
This is quite the assumption. Bolt is the fastest man we've ever seen. You actually think you're more closely competitive to him than Bellard???
Obviously that’s silly because the physical result is approached asymptotically. World class athletes train and compete their whole lives of a fractional difference in result. Clearly the output by the human brain is not constrained by something asymptotic as what the human body can physically be trained to accomplish.
Something unusual about Bellard is the breadth of his knowledge. There are probably a fair few who can write a fast deterministic low level code optimized neural network library. A decent number who can write an autodiff library but few who can do both. Once that's done, I daresay that's the hard part.
Given such a library, implementing an LSTM or transformer model and combining it with Adaptive Modeling/incremental learning of data statistics using a neural network to feed an Arithmetic Coder is something that is within the reach of many more.
In summary, a 10x developer is not 10x smarter or 10x more skilled, they just waste less time investigating unproductive paths and are maybe 1% less likely to take wrong turns. This ends up making a huge difference for large complex tasks.
One thing I’ve noticed is that he chooses to apply himself to many different subfields of development, but always using the same technologies e.g. all his work seems to be in either C or JavaScript.
I’ve only worked in a couple of subfields but have seriously used at least 7 different languages, plus countless libraries. Compared to Bellard I’ve probably spent (wasted?) a large amount of time trying to choose, and then learn, the “best” tool for each job.
Surely his intellectual life is diverse
There are other programmers at his level, or with the potential to be at his level, splattered all over the industry.
Unfortunately, they ‘waste’ their time on their day job stuff, often having to do things badly because technical approaches are prescribed by others etc.
Many of us meet truly great programmers, but so few of them actually demonstrate and express it. They just grin when asked to implement micro services and add some banal features to the website etc.
gzip = 17 MB/s
xz = 1 MB/s
CMIX = 1.6 kB/s
NNCP = 2~3 kB/s
Not only this is unacceptable for hot/warm data, also it's still impractical for cold data. It takes 10~16 years to compress or decompress 1 TB data.
For example, let's say you've decoded a stream that so far contained:
123456
a clever algorithm can make a guess that "7890" will be next (compression is all about making good guesses about the future data). LZ77 just can't — it has no way to express such prediction. This is general problem for LZ77 with data that has a predictable structure, but isn't a literal repetition of previous data.
NNCP is such an algorithm on top of that general idea.
All compression is prediction + entropy coding. The entropy coding part is a solved problem. Inserting LZ77 between your predictor and the entropy coder just makes it harder to communicate the exact symbols and probabilities you have predicted.
If you're building a rocket: you can strap a rocket engine to a car, and it will still go faster than the car itself, but it's easier not to build it on top of a car.
Demonstrating a novel compression scheme with a high compression ratio is worthwhile. It might inspire something else.
So he does not beat the SoTA “by a substantial margin”. Your comment is overstating the case.
Aside from the compression efficiency, I'd like to see other metrics too, like the work it takes to compute the compression (in units of energy, time, or whatever), to get more of a sense on what kind of workloads using something like that would make sense. These super-efficient compressors often only make sense in long term archival and compress-once-transmit-often scenarios.
It appears http://www.mattmahoney.net/dc/text.html (that Bellard links to on the NNCP page) has some information:
- NNCP (w/GPU) used 161812 nanoseconds/byte to compress, 158982 nanoseconds/byte to decompress, on an Intel Xeon E3-1230 v6, 3.5 GHz, RTX 3090 GPU, using about 6GB of RAM, to compress enwik9 down to 110,034,293 bytes
- CMIX used 602867 nanoseconds/byte to compress, 601569 nanoseconds/byte to decompress, on an Intel Core i7-7700K, 32 GB DDR4 using about 25GB of RAM, to compress enwik9 down to 115,714,367 bytes
- gzip -9 used 101 nanoseconds/byte to compress, 17 nanoseconds/byte to decompress, on an... Athlon-64 3500+ in 32-bit mode running XP, to compress enwik9 down to 322,591,995 bytes
- 7zip 9.20 used 1031 nanoseconds/byte to compress, 42 nanoseconds/byte to decompress, on a Gateway M-7301U laptop with 2.0 GHz dual core Pentium T3200 (1MB L2 cache), 3 GB RAM, Vista SP1, 32 bit, to compress enwik9 down to 227,905,645 bytes
These benchmarks are not directly comparable, as vastly different machines were used, but it still gives a trend at the very least.
As expected, these super-efficient algorithms are slow, really slow. Honestly, I'd think at least today too slow to make sense even for long term archival, and far too slow for compress-once-transmit-often scenarios, as the decompression rate is almost as slow as the compression rate.
Still, it's impressive work, don't get me wrong.
1. The compressors he is comparing to *are* neural networks themselves (PAQ)
2. He is using a rather small corpus enwik8 (100,000,000 bytes), instead of the common enwik9
3. He is not publishing the amount of RAM or hardware he used
https://web.archive.org/web/20210216231934/http://mattmahone...
It seems Bellard is starting to play with these. I bet he will find interesting things and I would love to see him interact in the Russian compression webforum (please don't link). Big names in compression like Yann Collet, Matt Mahoney, and Jarek Duda used to hang out there.
Remove wasting time on HN/reddit/watercooling and then compensating by working more hours, and cut the "cord" for all/most entertainment. Instead, read technical stuff. Even if you do it for just a couple of hours a day you'll leave most people behind. Same with programming. Ideally do it in the morning before work. So go to sleep very early.
The serendipity of HN, Reddit and Twitter have exposed me to a lot of ideas and information I would have otherwise never known about.
Reddit and Twitter are mostly a waste of time nowadays due to the signal to noise ratio. I dropped my reddit addiction and I'm working on eliminating Twitter.
I wish there were a social network system where people pool and share what they are expected to be doing and help each other. Or at least encourage each other to focus. But this goes against the advertisement paradigm where they want us to be impulsive and stupid. Sad, sad, sad.
Not directly, but by giving me new perspectives and ideas that bounce off my current perspective and ideas to create new ways of thinking about things.
My perspective now is that too much focus is a bad thing because it comes at the expense of broadening your perspective.
Reddit I agree is low signal, but I think Twitter is high signal depending on who you're following.
The signal might be good but is it the signal you should be focusing on? There is an amazing amount of interesting stuff being discovered all the time. But is it helping you achieve concrete goals?
With Twitter I see a trap. Say you work on implementing/using <Knowledge Domain X> and follow exclusively people doing similar work. They will also share things outside this domain. Since 2016 almost all science twitter users became highly political. And there is no way to filter this out.
This is a feature for Twitter and the like. They profit by making you emotional and going a rabbit hole of impulsiveness.
My point is that putting everything through the filter of "does this directly help me achieve my goals?" isn't the best way to pursue your goals, assuming we're talking about big goals where the path to achieving them isn't clear.
I recommend checking out this podcast episode called "Why Greatness Cannot be Planned". It really changed my perspective on achieving my long term goals: https://www.youtube.com/watch?v=lhYGXYeMq_E
Also on Twitter, yeah some people don't only tweet things in their domain. But I've found that some people do reliably stick to a single domain. Though I don't really follow science people on Twitter.
But can someone please explain to me how this guy finds the time to build all those amazing things? It's so much non trivial stuff in his list. I wonder... Does he have kids? A family? Is he rich? Does he get millions to build quantum computers? I really wanna know :-)
Thanks
Here's the code if anyone's interested: https://github.com/trsigg/lm-compression . I haven't looked at it in a while except for updating it today to work with more recent versions of the transformers library, but I think it should still function and is pretty easy to try out with different models. I thought about using something like a hidden Markov model instead which would be much faster (even more so because it would enable using tabled rather than range-based ANS), but I haven't gotten around to it.
Edit: I thought the model in the above paper was pre-trained, but apparently it's only trained on the data as it arrives! That's indeed a very interesting approach, I wouldn't have expected that neural network models would converge quickly enough for it to be useful.
I would guess that's down to neural networks poor performance with small training sets.
When I asked what that was, why did he have to dive into my C files, he admitted he doesn’t care to remember C syntax, and just had to look it up quickly to write his function.
It turned out he was mostly writing all of his code in x86 assembly, and a pretty complex code. His main project in assembly was a compressor that was faster and more efficient than RAR, which at that time was at the top. I tried it and that was true.
Many year later, the guys went on to win Hutter prize, and kept improving his own record year after year. I admire his grit and persistence, and how he keeps discovering new ways to improve his algorithms. And I wouldn’t be surprised if he maintains them in pure assembly (he did originally).
I did hire the guy, and enjoyed working with him.
https://encode.su/threads/3094-NNCP-Lossless-Data-Compressio...
The LibNC library is free to use as a binary shared library.
Contact the author if access to its source code is required.
Program or model size: bytes rato: bpb speed: KB/s
xz -9 24 865 244 1.99 1020
LSTM (small) 20 500 039 1.64 41.7
Transformer 18 126 936 1.45 1.79 (!)
LSTM (large2) 16 791 077 1.34 2.38
In reality, the Weissman score does not exist.
I highly recommend this serie if you haven't seen it :)
This is false, it uses both - hence the 'middle out' was suitable for video chat and all kind of enterprise software (incl. a custom appliance box). Overall - a be it all compression.
The score is so popular, it has its own wikipedia page[0]. It compares both required time and compression ratio of measured applications, with those of a de facto standard according to the data type.