Haskell is very competitive with C, and on some benchmarks, it isfaster. How is that possible? With all that Haskell does on top of theraw C code, how can it possibly be faster? In this episode, I talk abouttwo advantages of Haskell that can make it faster than C.
Transcript
Eric Normand: How is Haskell faster than C? I've two explanations,which I'll get to in a moment. My name is Eric Normand, and I helppeople thrive with functional programming.
Usually, languages are compared to C. It's the standard benchmarklanguage to say like, "Oh, this language is only a factor of two slowerthan C." Most languages are slower than C. Especially when you get intothe more higher-level languages, you have this idea, "Well, we lost alot of speed."
You don't have to deal with all these problems that C has. You don'thave memory leaks because we have a garbage collector. You don't haveto deal with when to free the memory, just all these niceties add up,but it's at the cost of the speed.
Then, you have something like Haskell that is often faster than C in thebenchmarks. It's very close to C when it's not faster. It's not like,"Oh, it's twice as slow." No, it's right there, it's within a fewpercentage of C, and very often it's on the other side, it's fasterthan C. What's going on?
There's actually two things, at least. These are the two things I knowof that are going on. The first is optimization. Haskell has a lot ofknowledge. The Haskell compiler is given a lot of knowledge about theprogram and the form of types, usually. Those types are richer than whatthe types in C are.
Not only is it the types, but there's a lot of the semantics of Haskellthat give the compiler a lot of leeway, let's call it, a lot of wiggleroom for optimization.
One of those is lazy evaluation. In C, it's strict evaluation, you puta function there, it executes one line at the time. It's how you shouldthink of C executing. It's going to call this line. Everything on thisline is going to finish before we get to the next line.
In Haskell, that's not the case. You can call something, give it aname, and it doesn't actually do anything yet. The compiler canactually analyze it and a lot of times figure out, "Hey, you've neverused this and this branch." I'm not going to do it yet until I knowthat you're in this branch, and then I'll do it.
Or, it might never do it. The analysis gets so complex. It mightremember how to do it and in case you need it, it will be there, but itwon't do it. There's a lot of stuff that you could in theory hand-tuneif you're very good at optimizing.
As a programmer, you could hand-tune and say, "Oh, there's a certaincase where I won't need this value, so I'm just not gonna calculate ituntil I really, really need it." In practice, it gets so hard. It getsso complicated that you're just not going to do it. Haskell can dothat. Haskell just does it and the programmer doesn't have to thinkabout it.
It can do some analysis, it can figure out when something is going to beneeded anyway, it might as well just calculate it now. It can do someanalysis and say, "Oh, it's only needed sometimes, so I probablywon't do it yet." Sometimes it just puns and says, "Well, I don'tknow how to analyze this." The net effect is that that it's faster.
Another thing is it can do a lot of, because everything is pure, it cando a lot more optimizations like moving code around, inlining, and doingmore stuff at compile time that can't be done in C. Those are typicallythought of like inlining, people optimization, that kind of stuff.
Haskell has a broader range of maneuvers that it can do that let thecode get optimized really well. That's nice. It's like you're gettingthe benefits of the high level. You can code how it should be read. I'mcoding for another programmer, I'm just making it very readable, butthen the compiler can transform it into something that's better to beexecuted on the machine.
That's number one, that's optimization. Number two is potentially evenbigger. That is that Haskell lets you use better data and algorithms. Ineed to explain because, yes, they're both true and complete. Let'stake that argument, I agree, but let's take it off the table.
Bryan Cantrill actually made this argument, and that's where I got theidea for this episode from. He was talking about Rust but it appliesequally to Haskell. He has been doing a lot of system programming in hiscareer and a lot of it is done in C because it needs to be low level.
His argument goes like this, "Well, if you need a data structure, in Cit's just hard to do anything more complex than a linked list." Or,maybe you could get a little bit more complicated, but you write linkedlist all day long because it's something that you know you're notgoing to mess up and it does the job, and it's fine.
Haskell, because it's higher level, it can actually manage much morecomplex data structures and do so in a correct way. It gives you toolsto write data structures that are known to be more efficient for certainaccess patterns. Linked lists are very linear.
Not every access, if you access the first thing, it's constant. Ingeneral, you're accessing things inside the list randomly. Let's saythat's what your algorithm is. You're accessing stuff randomly.That's linear. If you do that in a loop, wow, you're quadraticalready.
In Haskell, you can replace that linked list with something else, likelet's say a tree. Now, your access is logarithmic, and you've alreadysaved a bunch of time in terms of time complexity.
That is another way that Haskell benefits over C. That if the problem iscomplicated enough or big enough where a linked list...The differencebetween in-access complexity and Big O notation complexity, between alinked list and a tree, boom, it's a big enough difference. Haskell'sgoing to win.
It's simply a matter of how much complexity can you handle. Of course,if someone wrote a tree in C and you imported that library and youincluded it in your C code, you would start competing again withHaskell. You could do that, sure. Do you do that? Is that a possibility?
In these benchmarks, it might not be a possibility. Whereas, in Haskell,you could do that, you could write it yourself. I find that this is thecase, a lot of times, in higher-level languages. It's a spectrum. C isa very low level, Java's higher level than C, but then Scala's higherlevel than Java, Clojure is higher level than Java.
It's a spectrum. What happens is as you tackle these benchmarks, sure,C is going to win because it's very small problems. It's likecalculating something with a known algorithm. People have beenoptimizing the C algorithm for that for years, so they know exactly howto make it the fastest.
When you're dealing with more real-world problems, bigger problems,very often, you do need garbage collection and a better concept of datatype and data structure than C will give you. That's what happens. Itis not just about data structures, there are other facilities of thelanguage.
As a little anecdote, I heard a story once where there was a competitionto see who could write the fastest program, and it was C versus Java. Itsurprised everyone, especially the C programmers, but the Javaimplementation won.
It won by a lot. The C people were like, "No, that's not possible.It's..." "How can this big monstrous VM beat our highly-tuned tinylittle C program?" They started reading the Java code. You couldimagine them huddled there with their printouts like, "Huh!" They allwere like, "No, look. They cheated."
What they were pointing at was, in Java, they had used threads. Theyused multiple threads to solve the problem, whereas, in C they didn't.They considered that cheating. In C, you can see the problem here. Youcould see why they consider it cheating.
Because they're used to benchmarks where it's just one thread, purelysequential code. It is really hard to write threads in C compared toJava. In Java, it's very easy to write threads and to start newthreads. What do you do? What do you do? Who won?
I say that Java people won. That's the whole point of Java, is that itmakes those kind of things easy. It makes threads on cross-platformreally easy. It makes garbage collection cross-platform really easy. Ithink that the same thing is true of Haskell.
If it makes writing a data structure that gives you an advantage over alinked list, let's say, easy. That's what you get. That's why it'sfaster.
All right. If you have some ideas about why Haskell is faster, aboutthese high-level languages, how they could be faster than a low-levellanguage where you get to control everything and highly tune the codedown to individual instructions if that's the thing you like doing. Howis that even possible? Do you agree with me, disagree? I'd love toknow.
You can go to lispcast.com/podcast. You can find ways to contact me,email, Twitter, LinkedIn. You can also find all the past episodes. Theyhave audio, video, and text transcripts of all the past episodes. Youcan find subscribe links if you want to subscribe. Thank you so much.Check you later.
