Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Building a data compression utility in Haskell using Huffman codes

lazamar.github.io

Post reply on HN
Print view View original

61–70 of 94 posts

Re: Building a data compression utility in Haskell using Huffman codes

#61

Post by imurray »

tromp wrote: post #18

> 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…

> It would be interesting to see a uniquely decodable code that is neither a prefix code nor one in reverse.

More interesting than I thought. First the adversarial answer; sure (edit: ah, I see someone else posted exactly the same!):

    a 101
    b 1
But it's a bad code, because we'd always be better with a=1 and b=0.

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.

Re: Building a data compression utility in Haskell using Huffman codes

#62

Post by imurray »

n4r9 wrote: post #56
tromp wrote: post #18

> 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…

It's a weird example, but what about 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 gi…

That code in the EDIT is suboptimal. It doesn't saturate the Kraft inequality. You could make every codeword two bits and still encode 4 symbols, so that would be strictly better.

Re: Building a data compression utility in Haskell using Huffman codes

#63

Post by n4r9 »

imurray wrote: post #62
n4r9 wrote: post #56

Earlier quoted context omitted.

It's a weird example, but what about 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 gi…

That code in the EDIT is suboptimal. It doesn't saturate the Kraft inequality. You could make every codeword two bits and still encode 4 symbols, so that would be strictly better.

Ah of course. Thanks for the insight. About 15 years since I studied this stuff!

Re: Building a data compression utility in Haskell using Huffman codes

#64

Post by rebeccaskinner »

freilanzer wrote: post #60
epgui wrote: post #22

Earlier quoted context omitted.

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.

I'm pretty sure highly optimised code won't be elegant Haskell code though.

Highly optimized code tends to be inelegant in any language. That said, you can get really good performance from very elegant looking “normal” Haskell too. The big challenge with performance in Haskell is that the differences between optimized and unoptimized code can be pretty subtle if you’re not used to thinking about Haskell performance.

Re: Building a data compression utility in Haskell using Huffman codes

#65

Post by wyager »

ykonstant wrote: post #21

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.

The reality is that for any language, including C, compiler optimized code will never be as fast as hand optimized code in libraries like BLAS. So at some level, the choice of host language doesn't matter very much, because you're going to be outsourcing all of the computation anyway if you're really serious about speed. This is the same reason all the AI stuff, possibly the single largest consumer of compute in the world, gets away with being written in python except for the low level compute libraries.

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.

Re: Building a data compression utility in Haskell using Huffman codes

#66

Post by mirpa »

atlintots wrote: post #16

This is great! Are there any other similar tutorials going through writing a Haskell program, but with some more advanced features (monad transformers, lenses, etc)

You might try: https://github.com/turion/rhine-koans it is tutorial for FRP library Rhine, well commented with tests

Re: Building a data compression utility in Haskell using Huffman codes

#67

Post by rebeccaskinner »

bdahz wrote: post #34
lazamar wrote: post #30

Earlier quoted context omitted.

I’d say unbeatable! The goal was simplicity of implementation and code clarity. For this kind of thing I say Haskell performs the best.

For the simplicity of implementation and code clarity, I need to know how much I need to pay for it. 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?

The general rule of thumb I’d give is that a performance aware but not micro-optimized Haskell program will typically run in about 2x to 5x the time of a comparable C program, and will take somewhere between 2x and 10x as much memory. For a naive Haskell program the range is much bigger- maybe 2x to 10x as much time and 10x to 1000x as much memory (it’s easy to do a lot of allocations in Haskell).

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++.

Re: Building a data compression utility in Haskell using Huffman codes

#68

Post by GrantMoyer »

wyager wrote: post #65
ykonstant wrote: post #21

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.

The reality is that for any language, including C, compiler optimized code will never be as fast as hand optimized code in libraries like BLAS. So at some level, the choice of host language doesn't matter very much, because you're going to be outsourcing all of the computation anyway if you're really serious about speed. This is the same reason all the AI stuff, possibly the single largest consumer of compute in the…

> The reality is that for any language, including C, compiler optimized code will never be as fast as hand optimized code

That's not strictly true; sometimes a C compiler can optimize away my whole program: https://godbolt.org/z/oG5nfGE6z

Re: Building a data compression utility in Haskell using Huffman codes

#69

Post by ReleaseCandidat »

ykonstant wrote: post #21

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.

It's doable but harder than in imperative languages and the resulting code is _really_ ugly. See the thread of the 1BRC https://discourse.haskell.org/t/one-billion-row-challenge-in... with example code at (I hope that's the right Gist) https://gist.github.com/AndrasKovacs/e156ae66b8c28b1b84abe6b...

Re: Building a data compression utility in Haskell using Huffman codes

#70

Post by ReleaseCandidat »

rebeccaskinner wrote: post #67
bdahz wrote: post #34

Earlier quoted context omitted.

For the simplicity of implementation and code clarity, I need to know how much I need to pay for it. 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?

The general rule of thumb I’d give is that a performance aware but not micro-optimized Haskell program will typically run in about 2x to 5x the time of a comparable C program, and will take somewhere between 2x and 10x as much memory. For a naive Haskell program the range is much bigger- maybe 2x to 10x as much time and 10x to 1000x as much memory (it’s easy to do a lot of allocations in Haskell). For extremely optim…

To rephrase using my experience: "performance aware" Haskell is about as "fast" as Go, but needs more memory, and both are slower than the same Java code - but both are way more fun to write ;). Optimising Go is easier for most people though, in Haskell you _really_ need to know Haskell internals (how to read core and write unboxed code) and understand laziness.

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...

Post reply on HN