Casualties in the great computer shootout
Contents
There’s an interesting shootout between various programming languages going on here. Rather than argue in general about the relative merits of programming languages, this site measures them up in terms of the resources they consume performing various simple tasks. I like the way they’ve side-stepped the language bigots using this practical, experimental approach; though of course we have to be careful when we analyse the results.
The headline figures and rankings are what the site concentrates on: the shootout is all about who’s got the fastest gun, rather than who’s the most accurate.
Same job, different languages
If we dig a little deeper, there’s a huge amount of interest here in comparing other facets of different languages. Getting the job done isn’t just about writing the program. What do you need to do to run it? How accurate is it? How robust? How extensible?
Accumulating integers using C
One of the simplest example tasks is to calculate the sum of the entries in a file containing a single column of signed integers. It’s the kind of job you might expect C to do well, and the C implementation does indeed rank very highly in terms of CPU use and memory consumption — the entry even compiles cleanly.
/* -*- mode: c -*- * $Id: sumcol-gcc.code,v 1.39 2006/10/31 00:00:33 igouy-guest Exp $ * */ #include <stdio.h> #include <stdlib.h> #define MAXLINELEN 128 int main() { int sum = 0; char line[MAXLINELEN]; while (fgets(line, MAXLINELEN, stdin)) { sum += atoi(line); } printf("%d\n", sum); return(0); }
Accumulating integers using C++
The highest ranking C++ program looks more like C than C++ and provides a fine example of the ugly code you get when you try and write C in C++.
// The Great Computer Language Shootout // // with help from Waldek Hebisch // modified by Rob Stewart #include <iostream> #include <fstream> #include <stdlib.h> #include <stdio.h> using namespace std; #define MAXLINELEN 128 int main(int argc, char * * argv) { ios_base::sync_with_stdio(false); char line[MAXLINELEN]; int sum = 0; char buff[4096]; cin.rdbuf()->pubsetbuf(buff, 4096); // enable buffering while (cin.getline(line, MAXLINELEN)) { sum += atoi(line); } cout << sum << '\n'; }
Here’s how you should do it in C++. It’s a fraction slower but far cleaner. I include the code as written. It’s hard to see why the author hasn’t included the extra few characters needed to make it compile cleanly — perhaps he wanted the smallest possible C++ solution?
// The Computer Language Shootout // // by Greg Buchholz #include<iostream> #include<iterator> #include<numeric> main() { std::ios_base::sync_with_stdio(false); std::istream_iterator<int> ii(std::cin), eos; std::cout << accumulate(ii,eos,0) << "\n"; }
The
std::ios_base::sync_with_stdio(false); function call was a new
one on me. It looks like a performance hack — the program is equally
correct without it, and on my implementation runs equally quickly
without it. So I’d prefer a smaller and more conformant variant.
.... int main() { std::istream_iterator<int> ii(std::cin), eos; std::cout << accumulate(ii,eos,0) << "\n"; return 0; }
To our C programmer, this expressive little program may seem obscure. Where’s the loop to sum the integers? In fact, where are the integers coming from anyway? It’s true, there’s a lot beneath the surface of this high-level code, and without some understanding of the primitive elements, writing such code can be difficult and risky.
High-level code, Low-level errors
How can it be difficult to write such simple code? Here’s an example:
the
eos parameter is a default constructed input stream integer
iterator. A C++ novice might have tried to indicate default
construction like this.
std::istream_iterator<int> ii(std::cin), eos();
It won’t compile, but the compilation error is hard to interpret.)'
Let me reformat that for you.)'
Sadly, this is fairly typical of the compile errors when you call templated code incorrectly. In fact, this message is relatively friendly. In the face of too many errors like the above, our C++ novice may well give up and revert to a C style implementation.
Accumulating integers using C style Python
C++ is one descendant of C. Python is another. Both languages support a number of higher level idioms — generic programming, object oriented programming, functional programming — while retaining some level of C compatibility. We can accumulate integers in Python like this.
import sys total = 0 for line in sys.stdin.readlines(): total += int(line) print total
What we gain in readability, and indeed ease of coding, we lose in efficiency. This code is an order of magnitude more wasteful than the C solution. The shootout also presents a more Pythonic solution.
import sys, itertools print sum(itertools.imap(int, sys.stdin))
Here,
sum is a built-in generic function to add up the elements of a
collection (where the collection can be, as in this case, an iterable
object), and
itertools.imap is what generates that collection by
applying
int to each element of
sys.stdin. Note that when a file,
such as
sys.stdin, appears in an iterable context, the lines of that
file are what will be iterated over.
We could do without
itertools and simply use the built-in
map.
import sys print sum(map(int, sys.stdin))
The difference is that this version will build the whole collection in memory before summing its elements (which, on the 6Kb input file, is actually fractionally faster on my Python implementation).
Unfortunately, despite this elegance, the Python solution remains an order of magnitude more wasteful than both the C and C++ solutions. Nonetheless, it’s better in other important respects.
Correctness
Computers are incredibly quick at accumulating integers. It’s not a tricky problem, in contrast to, say, mapping out a traveling salesman’s itinerary, or stacking crates in a warehouse.
If we really care about the speed of our integer
accumulator, it’s probably because we have a very long list of input
numbers. In C, which is often described as portable assembler, an
integer is actually just a word on the machine — and is therefore constrained
to fit in a fixed number of bytes (4, typically, possibly as few as
2), giving a large-ish but finite range of values. Assuming
sizeof(int) is 4, the maximum integer value is 2 31 - 1, which is
2147483647.
What will 2147483647 + 1 be? Not 2147483648 — that won’t fit in 4 bytes. The actual result will depend on your implementation, but it certainly won’t be right. Most likely, the program will run as usual and will politely offer a vaguely convincing but wrong result. This is dangerous behaviour.
C++ advocates believe static typing is there to protect them from programming errors, and even that the compiler traps bugs before a program can even be run. I’ve come to regard static typing as a way of strapping code more tightly to the machine: great for shootouts, but less useful for flexible and correct programs.
Python provides a higher-level model of integers. (Is the word “model” correct in this context? The model of an integer is just an integer, an unbounded one.) Python integers don’t overflow. So the Python program can accumulate any sum of any integers which will fit on the machine.
Robustness
So, both C++ programs only cope with bounded integers and sums. They aren’t much use when the input is malformed either, and their responses differ. For example, if our input file contains commas, like this:
276, 498, -981, 770, ...
then our C style C++ will ignore the commas and just sum the numbers,
whilst our idiomatic C++ stops when it hits the first comma and
produces the result
276. Neither C++ variant draws attention to the
unexpected input. Similarly, if the input file contained an unexpected
floating point number:
276 498 -98.1 770 ...
then the C++ implementations yield different answers. I’ll leave it to you to figure out how they process the unexpected value.
Politely producing an answer which is not obviously wrong is, as I’ve said, dangerous. The Python program doesn’t know what to do either, so, in both cases it fails safely by raising an error.
$ python -c \ "import sys; print sum(map(int, sys.stdin))" \ < sumcol-input-with-comma.txt Traceback (most recent call last): File "<string>", line 1, in <module> ValueError: invalid literal for int() with base 10: '276,\n' $ python -c \ "import sys; print sum(map(int, sys.stdin))" \ < sumcol-input-with-float.txt Traceback (most recent call last): File "<string>", line 1, in <module> ValueError: invalid literal for int() with base 10: '-98.1\n'
Last one standing
At first it seems Python bites the dust early in the programming language shootout. In the longer term, I wouldn’t be surprised if it’s amongst the last ones standing.
Feedback
"What do you need to do to run it? How accurate is it? How robust? How extensible?"
- And the worst thing about 100m track races is that they tell us nothing about how well the competitors can swim? :-)
-"It’s hard to see why the author hasn’t included the extra few characters needed to make it compile cleanly ... It looks like a performance hack ..."
- Instead of complaining about programs, as though they were writ in stone - contribute a better program.
"... on the 6Kb input file ..."
- The example input file is 6KB, with N=21,000 the test input file is ~124MB
"I’ve come to regard static typing as a way of strapping code more tightly to the machine ... Python provides a higher-level model of integers."
And statically type checked languages like Haskell also provide arbitrary-precision tagged-integers - that functionality isn't restricted to dynamically type checked languages.
And "the program will run as usual and will politely offer a vaguely convincing but wrong result" is really about the C and its brethren - Ada and Oberon-2 and ... would all show an error on overflow, even C# provides overflow checks.
Isaac, thanks for the feedback.
"And the worst thing about 100m track races is that they tell us nothing about how well the competitors can swim? :-)"
Fair point, but I'm not sure how well the analogy works. Of course the shootout is all about efficiency, but the sample programs I compare are idiomatic solutions to the problem of accumulating integers, and I'm interested in their other dimensions. In fact, the shootout refuses non-idiomatic solutions, otherwise we'd probably see performance hacks like loop-unrolling and embedded assembler instructions -- and of course the Python would simply call out to C (which would use loop-unrolling and embedded assembler ... ).
"Instead of complaining about programs, as though they were writ in stone - contribute a better program."
Good point. I should. And thanks for the correction on file sizes -- I'd missed that. Things make a little more sense now :-)
Re- Haskell. I know little about Haskell, but I have hopes that functional languages are going to move further into the mainstream with the increase of multi-core chips. Accumulating a huge collection of integers is a task well-suited to divide and conquer: spawn tasks to accumulate portions of the collection, then sum their individual results. What I really don't want to see is programmers hand-coding threads to do this: it leads to horrendous code and hideous defects. I'd like the language to quietly and correctly tune the code for me.
idiomatic solutions to the problem of accumulating integers
That's very much a matter of perspective - there's always a lot of criticism that the programs are not idiomatic.
interested in their other dimensions ...
I look forward to seeing your cross-language measurements on those other dimensions :-)
Python would simply call out to C
At which we might wonder how much Python (Ruby, Smalltalk, Lisp, Lua, ... ) goodness we'd given up.
functional languages ... move further into the mainstream
Note that programs written in 2 pure functional programming languages (Haskell, Clean) are shown faster than the C program you listed.
I look forward to seeing your cross-language measurements on those other dimensions :-)
It's true, not everything is as easy to measure as speed (and we all know how hard it is to get meaningful speed measurements); and it's also true that automatically generated metrics are valuable.
My favourite such metric would be: "how many tests does it pass?" The shootout already has this covered. I think the shootout also has some interesting things to tell us about: "how do I run it?" and: "what happens when the computer doesn't like it (e.g. what do the compile errors look like)?". These details are incidental to the shootout, and harder to quantify.
Similarly, it's hard to objectively measure: "how readable is it?" For example, I'm used to (e.g.) Java programmers claiming that a long list of imports, keywords, type declarations and getters and setters make a program easier to read. I disagree! For me, the lines-of-code metric would be more closely correlated to readability. Again, the shootout sort-of covers this.
Note that programs written in 2 pure functional programming languages (Haskell, Clean) are shown faster than the C program you listed.
Interesting indeed. The speedy Haskell variant looks very clunky compared to the slower and the slowest ones -- but I'm no Haskell expert. I see the winning Clean entry is your own. Congratulations!
hard to objectively measure: "how readable is it?"
Because we haven't yet said what we mean by "readable". We might imagine "readable" could be measured by asking many many programmers questions about the program, and measuring their response time and accuracy.
Java programmers ... imports, keywords, type declarations and ... make a program easier to read. I disagree!
My opinion is that both those responses are too simplistic - it depends. It depends how big the program is, it depends how complex the program is, it depends on the skill and experience of the readers (and writers), it depends what browse/explore tools are available in the programming environment ...
I see the winning Clean entry is your own
And see how naive the implementation is - a simple recursive function that takes a handle and sum as arguments, and loops until no more ints are read - in this case, congratulations to the language implementors.
... we haven't yet said what we mean by "readable". We might imagine "readable" could be measured by asking many many programmers questions about the program, and measuring their response time and accuracy.
Another reason why it's hard to measure readability: it depends on who's doing the reading.