[Haskell-cafe] Byte Histogram

[Andrew Coppin]

There now follows a small grab-bag of miscelaneous but related thoughts. 
(Which probably means that this post will spawn a 2000 message thread 
discussing one tiny side-issue, rather than the main thrust of the 
message...)



First of all, benchmarking. We have The Great Language Shootout, which 
tests how fast solutions implemented in various programming languages 
can be, given unbounded amounts of time, energy, expertise, and compiler 
modifications. Which is interesting, from a certain point of view.

In another sense, it's less interesting. For example, a C program can be 
as fast as any Haskell program, since compiling Haskell entails 
transforming it *into* C. (Unless you're seriously going to suggest that 
GHC's native code generator is any match for the might of a half-decent 
C compiler...)

That got me thinking about a more interesting question: Not *how fast* 
can it go, but *how easily* can it go fast? People have written fast C 
programs and fast Haskell programs, but how easy is it to write a 
"typical" program and have it go fast, without spending years optimising it?

With that in mind, I set of with a plan to do some small-scale 
benchmarking. Pick a problem, solve it in both Haskell and C++, in the 
"simplest, most obvious way", and then apply "the simplest, most obvious 
optimisations". Measure performance and compare.

There are benchmarks that just output some data. ("Find all the prime 
numbers less than 1000...") I dislike these for a couple of reasons, not 
least because you can precompute the correct answer and just write a 
program which outputs that. (!) So I decided that all my benchmark 
programs should take a variable-sized data file as input, and save the 
results as output.

There's an old maxim of running benchmarks multiple times, to ensure 
that whatever time you got wasn't just a fluke. But then, maybe the 
first run pulls the input file into the file cache, and subsequent runs 
go faster. If your input data was randomly generated, perhaps you chose 
a particularly optimal or pessimal data set by accident. So I decided 
that each test run should use a different input file of approximately 
the same characteristics (size, random distribution, etc.)

So I ended up picking benchmarks like "sort the lines of this file into 
ascending order", "count the number of unique words in this file", 
"produce a histogram of byte values", "compute some statistics of this 
list of numbers", etc. The tasks are all extremely simple, so that there 
is some hope of it being possible to also implement them in C++.



One benchmark turned out to be particularly interesting: I call it "byte 
histogram". The task is simple:
- Open a binary input file.
- Read a stream of bytes from it.
- Count how many times each of the 256 possible byte values appears.
The test inputs are binary files of various sizes, some with a uniform 
distribution, some with variously skewed distributions (so that some 
bytes have a vastly higher count than others).

Assuming we have some suitable import statements, it's quite easy to do 
this:

   bytes <- BS.readFile "Input.bin"
   let out = BS.foldl' (\ map byte -> MAP.insertWith (+) byte 1 map) 
MAP.empty bytes
   writeFile "Output.csv" (unlines $ map (\(k,v) -> show k ++ "," ++ 
show v) $ MAP.toAscList out)

(There is some slight trickiness if you want bytes with zero frequency 
to still be listed.)

All of this *works* perfectly - i.e., it produces the correct answers. 
It's also astronomically slow, and it's very easy to make it eat many 
gigabytes of RAM while it runs. (If the program starts actually 
swapping, then you will truly know what "slow" is!)

OK, so what happens if we replace Data.Map with Data.IntMap? Well, it 
goes slightly faster, and consumes slightly less RAM. Inputs which 
didn't quite complete before will run to completion now. But performance 
is still abysmal.

Enough with this tree sillyness. What happens if you use an array? Given 
that the entire program (apart from the last 0.02% of it) spends its 
time notionally mutating the data, a mutable array would be the logical 
choise. Dial up an IOArray Word8 Int and the structure of the program 
changes slightly, but it's still only a handful of lines of code. And 
the performance? Still glacial.

In particular, suppose we have

   inc :: IOArray Word8 Int -> Word8 -> IO ()
   inc array byte = do
     count <- readArray array byte
     let count' = count + 1
     writeArray array byte count'

in the main loop. The program is giving us the right answer, but using 
absurd amounts of time and space to get it. Now watch this:

   inc :: IOArray Word8 Int -> Word8 -> IO ()
   inc array byte = do
     count <- readArray array byte
     let count' = count + 1
     count' `seq` writeArray array byte count'

And now, suddenly, memory usage becomes constant, regardless of input 
size, and run-time is slashed. The program goes from taking 50 seconds 
to process a certain file to taking only 0.02 seconds. And from taking 
400 MB of RAM to taking... less RAM than I can actually measure properly.

If we now replace the IOArray with an IOUArray then the seq call becomes 
superfluous, and there's a small performance increase, but nothing major.



None of this should be any surprise to anybody who actually knows how 
Haskell works. For anybody not yet expert enough to see the problem: The 
"inc" function doesn't read the array, see that a given byte has a count 
of 5, and overwrite that with a 6. It sees a 5 and overwrites it with a 
5+1. By the end of the main loop, every single array cell contains 
1+(1+(1+(1+(1+(1+....)))), which takes a stackload of RAM to hold.

That explains why RAM usage is so absurd. On top of all that, creating 
all this data takes time, and the spiralling RAM usage makes the GC go 
crazy trying to find garbage to get rid of (when of course there is 
none). And finally, at the end, you have to unwind all these 
expressions. (Curiously, I haven't seen a stack overflow yet...)

Adding the seq call forces 5+1 to actually turn into 6, not eventualy 
but *right now*, and so each array cell ends up actually containing a 
fully-evaluated integer. (No doubt this change in strictness also 
triggers an avalanche of optimisation opportunities, but the basic thing 
of importants is that we're not uselessly delaying evaluation now.)

As I say, none of this is a surprise to anybody who actually knows how 
to get performance out of Haskell. The strict version is actually faster 
than the C++ version. (I imagine I'm doing something horribly wrong with 
C++, of course...) Not drastically faster, but faster. Which probably 
just means that ByteString is doing nicer buffering than whatever the 
C++ standard library is called.

The important obsevation is this: One tiny, almost insignificant change 
can transform a program from taking 50 seconds and 400 MB of RAM into 
one that takes 0.02 seconds and 0.1 MB of RAM. And, at least in this 
case, the simpler version is the slow one.

To say that Haskell is "slow" is both a little bit vague, and not really 
backed up by facts. In about 5 minutes flat, I managed to write a 
Haskell program that's very simple, and yet faster than a comparably 
simple C++ program (and C++ is supposed to be "fast"). So it's not that 
Haskell is "slow". It's that Haskell is *tricky*. Tiny, tiny little 
changes that look innocuous can have vast effects on performance. And 
this is a nice little example of that effect.

As we (probably?) all know, strictness is a subtle and fickle thing. 
Consider:

   or :: Bool -> Bool -> Bool
   or True  True  = True
   or True  False = True
   or False True  = True
   or False False = False

Overlooking the obvious name clash, this seems like a perfectly 
legitimate definition for the logical-OR function. But now try this:

   xs `contains` x = foldr or False $ map (x ==) xs

A nice, pretty Haskell definition. But oh dears - this does not have the 
performance you would expect at all! But if you change the definition 
above to the apparently equivilent

   or True  _ = True
   or False x = x

then "contains" becomes much faster. If you saw these two functions side 
by side, you might well wonder what the hell the difference is. You 
might even wonder if the compiler would transform one to the other 
(although I'm not sure in which direction). But there is, in fact, a 
very, very big difference: one is lazier than the other.

For counting bytes, lazy = bad. For searching for matches, lazy = good. 
Similarly, if you take the byte histogram program and replace the lazy 
ByteString with a strict one, RAM usage spikes sharply.

In all, laziness is a tricky, tricky little hobbitses. I wrote a C++ 
program, in the obvious way, and it was very, very fast. I wrote a 
Haskell program in several comparably obvious ways, and they were all 
cripplingly slow. Until I added the magic "seq", and suddenly got 
blinding speed. So while it is not correct to say "Haskell is slow", one 
could justifyably say "C++ is fast more reliably than Haskell".



Consider for a moment the original implementation with Data.Map. Adding 
a seq or two here will do no good at all; seq reduces to WHNF. What we 
are wanting is NF, and I can see no way at all of doing that. (Other 
than doing something very expensive like looking up every possible key, 
which is far more operations than actually necessary.)

I wrote my own little BST algorithm, customised to the fact that there 
are always exactly 256 keys of type Word8. It was also nausiatingly 
slow. And then I did something: I inserted a few strictness annotations 
on the constructor fields. And (as you already worked out), performance 
increased drastically.

I can do that if *I* define the data structure. But if it's in a 
library, I am powerless to make it more strict (or less, if that were 
what I wanted).

That got me thinking... What would happen if, instead of "Integer", we 
had two types, "evaluated Integer" and "possibly unevaluated Integer"? 
What if the strictness or otherwise of a data structure were exposed at 
the type level?

The general idea here is that anything declared has having type 
"evaluated Integer" can never contain an unevaluated expression. It must 
always contain an actual integer. This of course implies that you might 
be able to unbox it or do other interesting things with it, but it also 
says something about evaluation.

The principle question is "what happens if you assign an unevaluated 
Integer to an evaluated Integer?" Is that legal? Do you have to 
explicitly evaluate it first? Or does that happen implicitly? Presumably 
"evaluated Integer" means evaluated to WHNF only - which for an integer 
is the same thing as NF, but for some more complex structure it might 
not be.

If the type system worked like this, I could do "Data.Map with evaluated 
integer keys and possibly evaluated integer values", and it would hold 
its values lazily. Or I could say "Data.Map with evaluated integer keys 
and evaluated integer values", and the structure would now magically be 
strict. Which is to say, the type system would ensure that any data 
passed into the structure was evaluated first, and the compiler could do 
any applicable optimisations based on the assumption of data being 
already evaluated. (For primitive types, that might be unboxing or 
passing in registors. For ADTs, it might just mean skipping an 
evaluation check.)

Currently, if you want a strict list, you have to implement one 
yourself. But is that strict in the spine, or the elements, or what? You 
have to implement every combination that you want. And, let us not 
forget, then go implement all the functions in Data.List over your new 
data structure. Not fun.

If, on the other hand, strictness where in the type system, data 
structures would be *parameterised* over the level of strictness required.

I have no idea what the syntax for that would look like, and backwards 
compatibility looks like a nightmare. You would need to answer questions 
like "what does it mean for a function to return an evaluated type?" and 
"is evaluation implicit or explicit?" But it seems like a rather 
interesting idea.

(Let us not forget: *Everything* is trivial for the person who doesn't 
have to write the implementation...)