When Haskell is Faster than C (2013)
paulspontifications.blogspot.com
paulspontifications.blogspot.com
If you just write readable, friendly C code it won't be all that much faster than normal code in a high-level language like Haskell—it might even be slower. I know, I've done that myself. But you never see that in benchmarks, do you? That's not what benchmarks are about.
Here's another illustration: we can compile high-level languages like Haskell and Scheme to C. Does this make them "as fast as C"? Yes—they're literally running as C. But also no. Hand-optimized C code is going to beat those compilers any day. It's not even close.
C is not magical performance sauce you can sprinkle over your code to make it fast. It's just a language that doesn't have much mandatory overhead (no GC, minimal runtime... etc) and gives you access to certain low-level knobs that you can twiddle to optimize your code. I mean, that's important and useful, but unless you're going to apply that level of effort to your whole codebase, most of your C code won't be all that fast. Some applications need this level of optimization; most don't.
[1]: I actually wrote a little article about this myself too: http://www.forbes.com/sites/quora/2014/01/09/can-a-high-leve...
1) Often the "performance critical parts" are actually 60-80% of your code. This is the problem with the "don't optimize prematurely" philosophy. Think of it in advance instead. Do you need the highest possible performance? Are you sure? How fast should it be then? Per request? At setup? Per data point calculated? Choose your tools accordingly.
2) For numerical code I'd actually choose Modern Fortran over C. Much less to do until it's fast.
That has not been my experience at all. But I suppose it depends on what kind of programs you're writing.
For example, people rely on how C lays things out in memory, so C compilers have to lay things out in memory in specific ways. Haskell doesn't have this constraint and so can do a bunch of tricks.
And then there are things where C cannot move a variable/optimise out a variable because it's unknown whether some unrelated bit of code my go poke at its memory.
Now one might say "well if you know what you're doing then you can get the compiler to do what you want." Everything's possible, since everything's turing complete. But I would consider "variables need to be somewhere in memory" to be mandatory overhead.
One can rely on C compilers laying out things in memory in a specific way only within a struct and when compiler-specific alignment/packing attributes are used. All other assumptions about variables being adjacent in memory are wrong and lead to undefined behavior.
This is not just a theoretical thing; at a certain point in the past, both LLVM and GCC had such an optimization, driven by PGO. I think it got removed because it just didn't trigger often enough and didn't give enough benefits to justify the complexity.
Scalar replacement of structs/arrays is of course routinely done by all major compilers and allows to completely optimize away non-escaping local objects.
Debuggability is also often overlooked. You can attach a debugger to a running image, and, provided you have symbol names, figure what's going on. Even if all you have is a core dump you can make a good guess of what has happened most of the time. Trying Haskell and doing some research on debugging it seems the only way other than debug prints is to instrument your program and even then you are not getting much.
Actually the languages that don't, aren't worth using in production environments, this isn't anything C special.
PS. And, again, even if such tools existed they were just for informational purposes since you don't have much control over the generated code so you cannot sensibly modify source to change the binary in expected way. For example, in C, if I see a high number of cache misses in some loop I can: a) change the data layout (e.g. align structure fields or move simultaneously accessed fields together) b) add a prefetch. What am I to do in Haskell?
You can also do layout changes in Haskell, for example use a ByteString instead of Text, or an Array instead of Lists and so on.
What you mean by doing prefetchin C? There isn't any ANSI C feature for that. Only compiler tricks and hope for the best.
And I am saying you cannot.
>What you mean by doing prefetchin C? There isn't any ANSI C feature for that.
Actually, there is, it's called inline assembly. But any decent compiler has an intrinsic anyways.
>You can also do layout changes in Haskell, for example use a ByteString instead of Text, or an Array instead of Lists and so on.
So, I have this type data Vector3 = Vector3 Float Float Float. Can I change its layout without having to change the rest of the code? The only way I know is compiler-specific unboxing and even that has little predictable effect, as we don't even know if this type is going to hold boxed values to begin with.
Which is a language extension and not a C feature.
Nothing prevents an Haskell compiler to provide similar extensions.
> So, I have this type data Vector3 = Vector3 Float Float Float. Can I change its layout without having to change the rest of the code? The only way I know is compiler-specific unboxing and even that has little predictable effect, as we don't even know if this type is going to hold boxed values to begin with.
Yeah, with my limited Haskell knowledge I would say you would need to make use of Data.Vector.Unboxed or use unboxed values as compiler extension like on JHC.
Still, there are ways to improve performance on Haskell applications, even if they require new ways of thinking.
Back in the day higher level languages (including C) were quite bad at generating code on home computers, and we had to use Assembly if we cared about performance.
So like C compiler quality and tooling has improved in these last decades due to high industry use, Haskell tools can also improve if its acceptance in the industry keeps increasing.
And then we can probably enjoy such tools for Haskell as well.
In line assembler has always been C feature. I also fail to see the point of mentioning intrinsics being extension. Do you have an example of a compiler, which does not support cache prefetch on a platform that supports them?
>I would say you would need to make use of Data.Vector.Unboxed
I believe you are missing my point. The run-time layout of this type is not known in the first place. Making it unboxed may or may not change its layout to another unknown one. If you need a specific change, and not a change for the sake of change - there is nothing you can do. In C, I might want this to be a 12 byte type if I access the values sequentially and a 16 byte if randomly. In Haskell you can either have it boxed (and you have an order of magnitude more cache misses) or have either 12 or 16 byte in unboxed, but you cannot tell which one and if you wanted another one - tough cookies.
>Haskell tools can also improve if its acceptance in the industry keeps increasing.
And if they do we will discuss them then.
The Haskell community is silent on getting rid of lazy-ness from it or at least making it completely and entirely optional for people. So let me repeat this even if Haskell is good to train your mind in the comfort of your home, it is miles far from being enterprise ready.
[1] http://anil.recoil.org/papers/2011-cufp-scribe-preprint.pdf
For people without an argument. Because then you would have to know what those firms actually do.
Read this: http://flyingfrogblog.blogspot.de/2010/05/why-is-haskell-use...
It's from 2010 so things may be different - but it illustrates that you can't just drop names, you have to do your research.
I at least bothered to provide a list of enterprises that bother to make use of Haskell, regardless how much of it they end up writing.
Anyone can easily search for videos of online talks where people describe their experiences in the finance industry with data modeling in Haskell.
Also if it would be so bad, the number of Haskell jobs outside academia wouldn't be increasing.
Sure, but you have to do your research too, into what kind of person Jon Harrop is and about how seriously you should take his critiques of Haskell.
Yeah, but that's because it targets a pre-existing strict runtime, not because of any problems with laziness.
The rationale behind their decision is simple: Laziness comes with its big problems, one of them is difficult to debug and predict runtime behavior.
Mu is strict because it was designed to target an existing strict runtime for which plenty of code was already written (in a language called Lambda, the letter before Mu in the Greek alphabet) and which was already deployed to many users through the corporation. The decision to be strict and not lazy has nothing to do with any downsides of laziness.
I've built fairly complex systems written in similar languages which were capable of crashing in the sense of an un-handleable OOM, but they didn't just trip over a bad pointer and die.
If this is more widely true of such languages, and not just an artefact of the implementation and problem domain I was working in, then perhaps the need to attach a debugger to running systems, or corefile-spelunk, is reduced. What do you think of that?
FWIW, I would still have liked a better debugger on the system I used. We had a small team and they were making hard choices about what was capable of being implemented in the time to hand. So I did a bunch of printf-debugging of my logic, and learned to right some log-file analysis tools. But it never crashed.
I can't say anything on debugging large-ish programs, though. Regarding profiling, GHC's runtime system includes a profiler that looks fairly competent from what I've seen. (For example, you can mark expressions that you want profiled, or you can just go with profiling per function.)
If performance is important, it is a good idea to use an optimizable language.
So there are a few decades of engineering time spent improving code generation of C compilers.
There are a few applications where every little bit of performance counts, like if you want to squeeze as many frame per second from a game. But I'd say for 95% of the code written, performance only matters if it is 10x or 50x faster. If you need to run a script and the script runs in 15s instead of 20s, it might be an impressive 25% performance gain but it's probably not worth the additional time spent optimising.
Surely C can't be that much faster than say .net?
It's my experience that people use the term "fast" and "faster" differently than I do.
Go get some data[1] and see how long it takes you to process 600 million rows of anything. For example, take the 100 most popular symbols and find their last bid price.
Once it's in memory, top open source SQL engines take 5-10 seconds, but writing it in C you can do it within 20msec.
I'd be really curious to see how fast .net actually is: I'm told Spark took 35 seconds to work that out, and it's referred to as "Lightning-fast".
I don't use magnitudes except when being illustrative because multiplying magnitudes like 10x and 50x become more exaggerated as the data gets bigger. When the cpu stalls, and waits for memory to come in, or the "runtime" takes a diversion to garbage collect some things, we're really talking about doing things that don't need to be doing.
When I say something is "fast", I usually mean it isn't doing anything that doesn't need to be done, or I mean I can justify everything that it is doing that doesn't need to be done (as, for example, waiting for other slower things, or making it easier for me to write).
.net may do fewer things that don't need doing than (say) perl, but programming in C we can actually make "fast" programs; we can simply choose to not do anything that doesn't need doing, and that means .net will never catch up.
[1]: ftp://ftp.nyxdata.com/Historical%20Data%20Samples/Daily%20TAQ/
Do those 5-10s vs 20ms actually matter for the data consumer in the overall use case scenario?
Sorry for the trick, but it actually wasn't C at all, but a simple, non-optimising interpreted language that beats the pants off all these fancy optimising compilers who can work around shit programmers making shit programs.
The <20msec solution written in K is as follows:
select last bid by sym from quote where date=d,sym in S
I'd love to talk about how to write programs that are fast, but by all means, let's talk about how we don't really need our programs to be fast in the first place.For example, Java and .NET can call C code (very easily in the .NET case) but require the computational overhead of a GC transition and the maintenance overhead of having to write wrappers around any calls in the reverse direction. It would be awesome if you could easily write code that intermixed statements dealing with things at a lower level (malloc, pointer arithmetic, etc.) and those that access high level abstractions (GC'ed objects, virtual dispatch, etc.). The CLR and to a lesser degree C# technically allow for this kind of thing, but it's still sub-optimal from both an ease of use standpoint (it's very tedious to write C# like this) and a performance standpoint (the CLR's JIT produces non-optimal code compared to a static C compiler).
.NET Native may solve the second one (though I am skeptical at this point that this will be Microsoft's focus with the technology, as opposed to easing deployment/lowering start up times) but I still feel we lack a language that makes this kind of thing easy.
Have you looked into C++/CLI?
https://blogs.msdn.microsoft.com/dotnet/2016/04/18/whats-new...
I think it was a very big mistake to have Java and .NET use a JIT by default instead of AOT compilers like Eiffel, Modula-3, Oberon(-2), Component Pascal had.
It created a bad perception of what memory safe programing languages compilers are capable of.
but the lack of a real ecosystem is really starting to hurt my progress.
What suggestions do you have for lisp-1 -> lisp-2? While I prefer lisp-1 + syntax-parse, I'd rather have.. quicklisp. quicklisp is life. the quicklisp must flow.
I personally would recommend clojure + cider + emacs for an excellent ecosystem and tooling.
Too true, that's my main complaint about ql since day 1. Give me a simple way to define a ql-repo hierarchy and I'll be fine with it. I did invest a few hours maybe 3 years ago but realized that it's too much work (research and patching) to allow for that. Recent developments (author pitching for money in ql context) make me even more worried :(.
Seems like this should just be filed under "right tool for the job".
One thing that slows down change is that new languages come with parallel universes called "runtimes". The D language (https://dlang.org/) is an honourable exception (it has a runtime, but not a parellel universe).
But D is only an incremental improvement on C++, and somehow never took off. Maybe Rust will be the Saviour.
Runtimes are a wonderful thing, they abstract the OS and make it almost irrelevant. Actually, I see POSIX as the unofficial C runtime that for political reasons wasn't made into ANSI C and turning into a separate standard instead.
I stop caring about POSIX, when I left the C++ world as full stack behind and started using it only to optimize specific code paths or OS integration.
Personally I think it is a side effect of the world going all VM/JIT, when the same languages could easily be AOT compiled to native code.
So many developers just kept using C and C++, because they thought they were the only ones giving them compiler toolchains to do AOT.
Lucky we now have Go, D, Swift, .NET Native, OCaml, Haskell, Ada, Rust to change that mentality.
THAT SAID, I have a relevant story. IMVU used this file format called "CFL" for its 3D content. It was basically a kind of zip file except it used LZMA for asset compression. The original CFL library was written in C++, and while it worked fine, it was getting annoying to maintain and compile it, as well as inefficient to pass data from Python file buffers into C++ and back out. So one day I decided to see if I could replace it with a bit of Python code and pylzma. After I made this change, parsing our content files was _twice_ as fast. Having the code in a couple hundred lines of simple Python allowed me to optimize the data flows, minimizing copying from the file buffers into the LZMA decoder and then to the consumer of the data.
Sometimes the best way to make something fast is to write it in a safe, expressive language that lets you directly express your intent. :)
Linked lists are slow...
The leap you're making here is about how distant the memory addresses should be in general.
This is entirely dependent on your problem and your data-set.
https://www.youtube.com/watch?v=fHNmRkzxHWs&list=PL8N1fQK8Lw...
2. The author talks about the importance of reducing cache misses due to pointer indirection and then proceeds by implementing a character buffer as a linked list of small buffers...
3. The C version reads and writes character one by one, this can be greatly improved by reading/writing bigger chunks at once. Actually, the author points out this optimisation but says "that would require significant changes to the code;". So the author spent time optimising the Haskell version, but spending time optimising the C version is too much work? And then arrives at the conclusion Haskell is faster?
4. Commenters on the author's blog cannot reproduce the results...
Haskell is still pretty well-defined in terms of execution, but freedom from how to manage memory is in itself a major liberator for the optimisers.
I've been programming in both for a while now, and I wouldn't use 'faster than C' as a selling point.
In my (limited) experience, what Haskell gives you is conciseness and abstraction. What C gives you is speed and 'close to the machine' programming for when you need it. I'm not sure this article provides any useful insights.
I want both the compiler from the year 2030 and the drugs this guy has.
I guess you can call self-delusion a drug..