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

71–80 of 94 posts

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

#71

Post by CyberDildonics »

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.

If you want to write fast stuff that takes advantage of SIMD, you want to use ISPC, which is made for high performance SIMD. Using haskell for this would be like doing surgery with a dull rock, you will never get what you want.

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

#74

Post by tkz1312 »

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.

Haskell really shines when you want to write high level, declarative code. Performance when using this style is generally fine for CLI / web backend style stuff. It has the tools to write pretty fast low level code, but they’re fairly clunky and if that’s all you want to write it’s probably not going to be the best tool for the job. They’re pretty nice if you have a few focused hotspots you need to optimize.

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

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

#76

Post by wredue »

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.

If you’re writing idiomatic Haskell. Its performance is terrible.

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

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

#77

Post by 082349872349872 »

tossandthrow wrote: post #42
random3 wrote: post #38

Earlier quoted context omitted.

How do you distinguish data shuffling from computation? What’s actual computation from this perspective?

Philosophically speaking there is no difference. 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.

Philosophically speaking there's a great difference.

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.

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

#78

Post by wyager »

GrantMoyer wrote: post #68
wyager wrote: post #65

Earlier quoted context omitted.

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

You're doing extremely simple constant arithmetic here. GHC can optimize this type of thing away to nothing as well. Are we talking about contrived examples or real numerical bottlenecks?

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

#79

Post by a1369209993 »

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 [not gratuitously inefficient] uniquely decodable code that is neither a prefix code nor one in reverse.

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}
This is trivially uniquely decodable by uniquely decoding 0->A/etc backward, then uniquely decoding A->a/etc foreward. It's equivalent in lengths to the optimal prefix code {a=0,b=110,c=1110,d=1111,e=10} so it's a (one of several) optimal code for the same probability distributions.

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.

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

#80

Post by Twisol »

wyager wrote: post #78
GrantMoyer wrote: post #68

Earlier quoted context omitted.

> 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

You're doing extremely simple constant arithmetic here. GHC can optimize this type of thing away to nothing as well. Are we talking about contrived examples or real numerical bottlenecks?

I think it was a joke about compilers removing code by reasoning about undefined behavior.
Post reply on HN