Hey, since this is likely to attract Haskell programmers: how fast is Haskell these days for a programmer intent on writing optimized code? I am particularly interested in its performance for numerical crunching like matrix operations and other stuff that benefit from SIMD.
Building a data compression utility in Haskell using Huffman codes
21–30 of 94 posts
Re: Building a data compression utility in Haskell using Huffman codes
#22Hey, since this is likely to attract Haskell programmers: how fast is Haskell these days for a programmer intent on writing optimized code? I am particularly interested in its performance for numerical crunching like matrix operations and other stuff that benefit from SIMD.
I’m not the best person to answer this question, but AFAIK it’s very very fast (in the rough vicinity of C). But also memory-hungry.
Re: Building a data compression utility in Haskell using Huffman codes
#23> To make it unambiguous we must make sure that no code word is a prefix of another code word. 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 While the code for a is a prefix of the code o…
[deleted]
Re: Building a data compression utility in Haskell using Huffman codes
#24Hey, since this is likely to attract Haskell programmers: how fast is Haskell these days for a programmer intent on writing optimized code? I am particularly interested in its performance for numerical crunching like matrix operations and other stuff that benefit from SIMD.
I met Sam Derbyshire at ZuriHac who told me all the difficult architectural work had been done for SIMD support.
+ 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:
Re: Building a data compression utility in Haskell using Huffman codes
#25How is the performance when compared to similar implementations in C/C++ or Rust?
Re: Building a data compression utility in Haskell using Huffman codes
#26For all readers, arithmetic codes are better in nearly all ways. They can be implemented in less RAM and code, they compress and decompress to a better ratio, and the probabilities of different symbols appearing can be dynamically updated during the stream far more easily. 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 u…
There is one way in which Huffman codes are better: they are easier to explain and simpler to implement. 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.
> easier to explain
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.
Re: Building a data compression utility in Haskell using Huffman codes
#27Very nice read, thanks for sharing!
What's nice ?
Re: Building a data compression utility in Haskell using Huffman codes
#28I think there is a typo in the table of the "Creating prefix-free codes" section. D should be '0010' (not '0110').
Otherwise a great read, thanks!
Re: Building a data compression utility in Haskell using Huffman codes
#29This is great! Are there any other similar tutorials going through writing a Haskell program, but with some more advanced features (monad transformers, lenses, etc)
I would recommend the book Haskell in Depth, which covers both of those topics (monad transformers by chapter 6, lenses in chapter 3 and chapter 14). It also covers some other advanced features, like Template Haskell and concurrency, and has a chapter dedicated to working with SQL databases in Haskell.
Re: Building a data compression utility in Haskell using Huffman codes
#30How is the performance when compared to similar implementations in C/C++ or Rust?
I’d say unbeatable!
The goal was simplicity of implementation and code clarity. For this kind of thing I say Haskell performs the best.