and yet another episode in the series of "look, what I did with Haskell"
Building a data compression utility in Haskell using Huffman codes
31–40 of 94 posts
Re: Building a data compression utility in Haskell using Huffman codes
#32Hey, 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 like Haskell performance for every-day backend/web and CLI stuff. But I drop down into Rust when I'm writing something performance-focused.
That said, Haskell's no slouch. Here's a small program to count the 1-bits in a file.
main :: IO ()
main = do
content >= \[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/massivRe: Building a data compression utility in Haskell using Huffman codes
#33How 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.
That wasn't really the spirit of the question as I read it. 'Performance' has a narrower definition than that.
Re: Building a data compression utility in Haskell using Huffman codes
#34How 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.
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?
Re: Building a data compression utility in Haskell using Huffman codes
#35I 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!
Aha, that makes sense, I was wracking my brain as to how 0110 was unambiguous.
Re: Building a data compression utility in Haskell using Huffman codes
#36Earlier quoted context omitted.
I was under the impression that arithmetic codes are guaranteed to be at least one bit less efficient than Huffman codes per input block. What makes you say they have better compression ratio? 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 fashi…
Huffman codes are conceptually isomorphic to arithmetic codes where all probabilities are 2^-k with k integer, so they have an obvious disadvantage due to more inaccurate symbol distribution.
Hopefully k is natural. ;)
Re: Building a data compression utility in Haskell using Huffman codes
#37I 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!
Fixed it. Well spotted!
Re: Building a data compression utility in Haskell using Huffman codes
#38Haskell is a really nice language. In general I don’t identify as an X programmer for any value of X: I tend to write in a half dozen languages daily and they all suck in their own special way. 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 exc…
How do you distinguish data shuffling from computation? What’s actual computation from this perspective?
Re: Building a data compression utility in Haskell using Huffman codes
#39Hey, 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's speed can be competitive with systems languages but keep in mind that its killer feature is ease of abstraction.
The 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.
Re: Building a data compression utility in Haskell using Huffman codes
#40How is the performance when compared to similar implementations in C/C++ or Rust?
[deleted]