Building a data compression utility in Haskell using Huffman codes
lazamar.github.io
lazamar.github.io
I mention this only because, when I learned the tree-based approach at uni, I simply wasn't aware that there was another way to do it, and I'm wondering how many of you that's true for as well.
While the tree approach is intuitive and illuminating, it probably makes more sense to work with in-place arrays, since the situations when you care most about compression are probably the situations when you have a lot of data and want to run fast.
In-Place Calculation of Minimum-Redundancy Codes
Moffat, Katajainen. 1995.
http://hjemmesider.diku.dk/~jyrki/Paper/WADS95.pdfOr in general, refer to "On the Implementation of Minimum Redundancy Prefix Codes" by Moffat and Turpin (1997), as strongly recommended and later explained by Charles Bloom [1].
[1] https://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffm...
The authors mention this technique in the second edition.
the phrasing sounds like a list comprehension
Technically, this is not quite correct. The class of so-called uniquely decodable codes is unambigous, and a superset of the prefix codes. One simple example of a uniquely decodable code is the reverse of a prefix code. For the example in the article that would be
a 1
b 00
c 10
Something like
`100000000000000001`
In this case, where to know whether the first code was an `a` or a `c` you have to read all the way to where the zeroes end.
a 1
b 101
It is neither prefix-free nor suffix-free. Yet every occurrence of 0 corresponds to an occurrence of b.
However, this is obviously inefficient. So I guess the question is whether there's an optimal code which is neither prefix-free nor suffix-free.
--------------
EDIT
I did some googling and found this webpage https://blog.plover.com/CS/udcodes.html where the author gives the following example of a uniquely decodable code:
a 0011
b 011
c 11
d 1110
More interesting than I thought. First the adversarial answer; sure (edit: ah, I see someone else posted exactly the same!):
a 101
b 1
The Kraft inequality gives the sets of code lengths that can be made uniquely decodable, and we can achieve any of those with Huffman coding. So there's never a reason to use a non-prefix code (assuming we are doing symbol coding, and not swapping to something else like ANS or arithmetic coding).
But hmmmm, I don't know if there exists a uniquely-decodable code with the same set of lengths as an optimal Huffman code that is neither a prefix code nor one in reverse (a suffix code).
If I was going to spend time on it, I'd look at https://en.wikipedia.org/wiki/Sardinas-Patterson_algorithm -- either to brute force a counter-example, or to see if a proof is inspired by how it works.
This can be done by composing a prefix code with a suffix code:
A 0
B 01
C 11
a A 0
b BA 010
c BB 0101
d BC 0111
e C 11
{a=0,b=010,c=0101,d=0111,e=11}
And it's neither prefix nor suffix itself, since a=0 and b=010. In fact, it can't in general be decoded incrementally at all, in either direction, since "cee...ee?" vs "bee...ee?" and "?cc...cca" vs "?cc...ccb" both depend on unbounded lookahead to distinguish a single symbol.
I'm not sure the optimality holds for any composition of a in-isolation-optimal prefix code with a in-isolation-optimal suffix code, but it did work for the most trivial cases (other than the degenerate 1-to-1 code) I could come up with.
https://www.coursera.org/learn/scala-functional-programming?...
Also, the microprogram had to deal with branch prediction because it was a non-superscalar pipelined processor model. Guess the wrong branch, and enjoy wasting cycles on a pipeline stall while the correct branch filters forward.
+ https://gitlab.haskell.org/ghc/ghc/-/issues/7741
It might make it for GHC 9.12 (for 128 bit vectors only, and mostly floating-point operations unless other people come in and contribute).
The patch is at:
That said, Haskell's no slouch. Here's a small program to count the 1-bits in a file.
main :: IO ()
main = do
content <- getArgs >>= \[a] -> unsafeMMapVector a Nothing
print (vectorPopCount content)
vectorPopCount :: V.Vector Word64 -> Int
vectorPopCount = V.foldl' (+) 0 . V.map popCount
I haven't tried crunching matrices, but I would start by checking out repa, accelerate, or massiv.
https://hackage.haskell.org/package/repa
https://hackage.haskell.org/package/accelerate
https://hackage.haskell.org/package/massivThe idea is that it is simple to assemble multiple parts into a coherent, well organised program. Which is important for the entirety of the program, no just the tight loop.
So, with the nice FFI Haskell has, you can always drop down to languages without a GC for inherently imperative optimisations. Then you wrap that into a library with nice types and you can now leverage that raw power anywhere in your Haskell code where the types will match.
I worked at Meta in a high performance Haskell application and that's what we did. Wrote beautiful, large, fast Haskell programs which in some specialised parts had C++ building blocks. 99% of the time was spent on Haskell land composing things into more and more useful applications.
To answer your question directly, The GHC compiler is very good. High level code will perform very well, and for most realistic applications, performance bottlenecks are architectural, not e.g. the use of single width versus SIMD, and the "architectural asymptotics" of haskell are very favorable. I think GHC has/is getting SIMD support but that's not what I would focus on when evaluating perf.
I wouldn't write a matrix multiplication algorithm in Haskell, but I also wouldn't write one in rust or C if I was serious about speed.
Many focus on number crunching as a performance metric, but almost no one is ever actually bottlenecked on that, and if they are it doesn't really matter what high level language they're using.
That's not strictly true; sometimes a C compiler can optimize away my whole program: https://godbolt.org/z/oG5nfGE6z
It has pretty nice CPU profiling tools, so finding and optimizing CPU hotspots is fairly pleasant. Tracking down rouge memory leaks (which lazy evaluation makes more likely) on the other hand can be extremely frustrating.
If you look at the benchmarks game results [1], the fastest haskell implementations are generally between 2 and 5 times slower than the fastest c versions, and will be written in a highly imperative style.
[1]: https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
If you’re choosing to fight with Haskell, why? Just use something else.
To understand why people claim Haskell is “fast”, you need to understand what they mean. What they mean is “if you opted to write C in such a way as you were performing similar amounts of copious and useless data copying, pointer following and stack blowing madness, Haskell will perform that fast”. They are not saying “Haskell is as fast as the fastest idiomatic C implementation”.
Another thing you’re going to see a lot of is extremely simple anecdotes, such as counting in a loop, or favourable measure points (they will measure the whole c program, but just the point in Haskell after they’ve flattened data, for example, stating “we just want to compare those parts”).
The explanation is that Haskell has terrible performance idioms like “copying shit for no reason all the time”.
There’s a reason that the prevailing opinion on language performance within the Haskell community is “thinking about performance of a language is a premature optimization”
This, of course, ignores that Haskells poor performance characteristics are actually technical debt, for which all people should be considering off the bat for their project. You cannot simultaneously say “premature” and not also add this to the techdebt column.
There comes a time in *all* scaling applications that Haskell will be such a burden, that it’ll be forced to be rewritten.
I mean. Fundamentally, reducing cache invalidation, reducing pointer following, and branch prediction are like 80% of your performance gains today. Haskell, being bad at all of these, fundamentally will never perform from a language standpoint.
You can make all the “I believe!!!” Arguments you like. Belief is not fact. Fact is that Haskell measurably performs badly, and Haskell idioms will never perform well.
If your organization is okay with accepting that huge performance tech debt, that’s a choice for your org.
In concrete terms, what are these Haskell idioms, what are their measured performance characteristics, and what are alternative idioms for each that perform better? Is there a write up that you could share about this?
I think it would be truly educational. Without that though, your statements appear equally as anecdotal.
While I do think this is often and perhaps even usually true, it’s irrelevant to anything I’ve said in this thread, and I wasn’t even thinking in these terms.
You’re hearing things.
Otherwise a great read, thanks!
Direct link: https://lazamar.github.io/images/data-compressor.svg
The only reason Huffman codes are used is they were invented first and arithmetic codes were patented. That patent has now expired, so we should use the better design.
* They usually self synchronize when some data is corrupted (but not guaranteed, does not apply where the Huffman table is dynamic)
* Neither Huffman nor arithmetic codes are easy to parallelize the decoding of, but Huffman is slightly easier.
Are you thinking of pre-defined Huffman tables that aren't adapted to the input? Because the latter ought to be as good as it gets.
(I agree with the other benefits. Since arithmetic coding tables are built in a streaming fashion rather than constructing the codebook up front, they are more memory-efficient while working.)
I went for simplicity of exposition in the post, but arithmetic coders can indeed get arbitrarily close to the entropy, which is not quite the case with Huffman.
I think Huffman is the one compression algorithm that compresses stuff significantly that can fit on the proverbial napkin, so it's a good start.
The others require the whole napkin stack at the table.
That is, LZ determines, dynamically as it goes, what are all the elements we want to encode and their probabilities. Then you need a coder, like Huffman, to actually encode it.
In the post I used a semi-static zero-order byte-based model. Which means I counted the byte occurrences first and just used that count for the probabilities throughout all of the encoding. Then I used Huffman codes to translate those probabilities into bits.
But I'm considering writing a follow-up changing this static model for an LZ77 one as I think that would be fun.
Comparing LZ to arithmetic encoding is a category error. LZ and Huffman are combined modeling+encoding methods, while arithmetic is just an encoding method, and it can be combined with any modeling technique. Arithmetic plus a suitable modeling technique will achieve compression as good as LZ, Huffman, or any other scheme. The PAQ8 compressors, and I believe its successors in the Hutter Prize ranking, use arithmetic plus a very advanced modeling scheme.
The goal was simplicity of implementation and code clarity. For this kind of thing I say Haskell performs the best.
If the Haskell implementation is 3x slower than C/C++/Rust implementation, it would be acceptable.
If it's 30x slower, I would rather choose C/C++/Rust even the implementation won't be simple.
If it is even possible to be 3x faster than C/C++/Rust, then why not the mainstream programmers adopt Haskell everywhere?
I am doing some inefficient things (like two pass encoding) on purpose to keep things simple and clear. So using this particular piece of code to judge a language's performance potential is not really the way to go here.
For extremely optimized Haskell you can get close to the speed of C, but there’s still a garbage collector.
There are also certain classes of problem where a naive Haskell implementation can beat other languages by mile, including C, if you use the same implementation in both languages. Laziness can be really great sometimes. This didn’t happen much in practice though because the kind of code that’s really efficient with lazy evaluation is very obviously not in a strict language so people don’t usually write code that way.
In the end I’d say Haskell is a good choice for performance sensitive but not performance critical program. In a larger Haskell application if you have a performance critical bit you can usually write Haskell code that will be fast enough if you know what your doing. For something stand alone that needs to be as fast as possible, or the most critically performance sensitive parts of a bigger application, I’d consider using C or C++.
My try of the 1 billion row challenge in Go and Haskell (and C) and comparison to other, fast implementations: https://github.com/Release-Candidate/1-billion-row-challenge...
But on two separate occasions I made important career decisions with opportunity cost to work with highly lethal GHC contributors: those people are just really good.
If Haskell sucks like all languages it’s because Haskell excels at using computers to compute something: Haskell considers data shuffling a strictly secondary concern compared to doing actual computations.
What parent commenter probably refers to is that you think in terms of computations and not in terms of data units.
And that is just tremendously elegant.
Data shuffling doesn't —in principle— lose information; computation does. ("evaluation is forgetting")
In https://news.ycombinator.com/item?id=32498382 "glue code" and "parsley code" are data shuffling, while "crunch code" is computation.
I guess we have to colive in a world where both views are true.
I'm guessing if all you do is this kind of db - screen - keyboard and back stuff, haskell is not very useful, if not actively a hindrance.
If you’re moving a lot of undifferentiated bytes the language you should use is historically C, more recently C++ (which is still the standard), or maybe soon Rust (which looks to become the standard).
If IO is a small part of your problem, performance needs to be good but not insane, and you’re mostly thinking about algorithms and mathematics?
Haskell is a very pragmatic choice there. OCaml is strong here too, and TypeScript is a very cool compromise between “mainstream” and “we do math here”.
I want to open a file, and I can't read it all at once, so I'll use a FileReader and it should be buffered, so I'll wrap it with a BufferedReader. I'll use try-with-resources and click into the classes because I can't remember if the contract of the outermost reader is that it will close the inner readers too.
Right, now I'll grab the next n bytes from the stream, and start thinking about the algorithm. Swear a bit when I think about crossing the buffer boundaries, and on-and-on...
The IO concerns are very much interwoven with the algorithm.
In Haskell I just start by writing one function from bytes to bytes. That's the computation. Then when that's done I expose that function as bytes to bytes.
Others can hook it up to files, webservers, pipe it through gzip, whatever!
6 languages per day? Are they the same six the next day?
> they all suck in their own special way.
Not surprising if you're writing 6 different languages per day.
> Haskell excels at using computers to compute something
Can you please explain how Haskell computes medians more elegantly than say C?