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