Word Aligned

Casualties in the great computer shootout

2007-02-01 • C++, Python • 1 Comment

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 $
 * http://www.bagley.org/~doug/shootout/
 */

#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
// http://shootout.alioth.debian.org/
// 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
// http://shootout.alioth.debian.org/
// 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.

sumcol3.cpp: In function 'int main()':
sumcol3.cpp:8: error: no matching function for call to 'accumulate(std::istream_iterator<int, char, std::char_traits<char>, ptrdiff_t>&, std::istream_iterator<int, char, std::char_traits<char>, ptrdiff_t> (&)(), int)'

Let me reformat that for you.

sumcol3.cpp: In function 'int main()':

sumcol3.cpp:8: error: no matching function for call to
'accumulate(
std::istream_iterator<int, char, std::char_traits<char>, ptrdiff_t>&,
std::istream_iterator<int, char, std::char_traits<char>, ptrdiff_t> (&)(),
int)'

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.