Word Aligned

Knuth visited, Brains Limited

tag@wordaligned.org (Thomas Guest) — 2011-02-03

Lucky me, I did get a ticket to see Professor Donald Knuth deliver the 2011 Turing Lecture at Cardiff University. He started out by saying he’d been wanting to come here ever since seeing Yellow Submarine in the 60s because of some dialogue which goes something like:

“What do you call a big school of whales?”

“A University of Wales.”

What a fine country Wales is for a computer scientist, he continued, you have a place called Login. A village in Pembrokeshire, someone in the audience chipped in, it’s very beautiful. Wonderful, all the more reason to visit!

Openings over, the lecture turned into a question and answer session. If I’m honest, I’d have preferred something more formal, but having just completed TAOCP4A, all 900 pages of it, and Volume 8 of his collected papers, the “dessert” edition of the series on fun and games, Professor Knuth was in a holiday mood, and it was a delight to hear him field questions on the future of computer science, P = NP, literate programming, analog computers, brute force vs. elegance, and whether the increase in computing power diminishes the art of programming.

Yes, computers grow exponentially more powerful — but human appetites grow yet more quickly. And even if you have all of that power, can you be sure the computers are getting the right answers? This afternoon, Professor Knuth said, while strolling through Cardiff, he’d seen the famous brewery Brains & Co. Ltd. and thought, yes, that’s about right. Brains limited.

My thanks to Arkadyevna for permission to use her wonderful photo.

Set.insert or set.add?

tag@wordaligned.org (Thomas Guest) — 2010-11-17

Get set, go!

Suppose you have an element e to put in a set S.

Should you:

S.add(e)

or:

S.insert(e)

It depends on which language you’re using. I use C++ and Python and I usually get it wrong.

>>> S.insert(e)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'set' object has no attribute 'insert'

Try again!

error: 'class std::set<int, std::less<int>, std::allocator<int> >' 
has no member named 'add'

Maybe my IDE should auto-complete the correct member function but it doesn’t, or at least I haven’t configured it to, so instead I’ve worked out how to remember.

Now, neither C++ nor Python pins down how a set should be implemented — read the language standard and reference manual respectively and all you’ll get is an interface and some hints. Read between the lines of these references, though, or study the implementations, and you’ll soon realise a Python set is an unordered container designed for fast membership, union, intersection, and differencing operations — much like the mathematical sets I learned about at school — whereas a C++ set is an ordered container, featuring logarithmic access times and persistent iterators.

Think: C++ set ≈ binary tree; Python set ≈ hashed array.

It’s apparent which method is correct for which language now. To put something into a binary tree you must recurse down the tree and find where to insert it. Hence std::set::insert() is correct C++. To put something into a hashed array you hash it and add it right there. Hence set.add() is proper Python.

How long is a string?

I’m suggesting programmers should know at least some of what goes on in their standard language library implementations. Appreciating an API isn’t always enough. You insert into trees and add to hashes: so if your set is a tree, call S.insert(), and if it’s a hash, S.add().

Such logical arguments don’t always deliver.

Question: Suppose now that S is a string and you’re after its length. Should you use S.length() or S.size()?

Answer: Neither or both.

In Python a string is a standard sequence and as for all other sequences len(S) does the trick. In C++ a string is a standard container and as for all other containers S.size() returns the number of elements; but, being std::string, S.length() does too.

Oh, and the next revision of C++ features an unordered_set (available now as std::tr1::unordered_set) which is a hashed container. I think unordered_set is a poor name for something which models a set better than std::set does but that’s the price it pays for coming late to the party. And you don’t std::unordered_set::add elements to it, you std::unordered_set::insert them.

My thanks to the|G|™ for permission to use his string.

Define pedantic

tag@wordaligned.org (Thomas Guest) — 2010-11-02

My dictionary defines a pedant as:

pedant n. 1. A person who relies too much on academic learning or who is concerned chiefly with academic detail.

Apparently the word derives from the Italian, pedante, meaning teacher. During my career as a computer programmer a number of my colleagues have been surprisingly pedantic about the proper use of English.

“I refuse to join a supermarket queue marked 10 items or less.”

“I do wish people would stop using target as a verb. You aim at a target, you don’t target it.”

“I am an exceptionally skilled grammarian in English … Take that rule and shove it!”

Some of this fussiness may well be a reaction against corporate double-speak. Still, I wouldn’t have expected programmers to be 1) so particular and 2) so certain they’re right. Maybe this attitude comes from all those years of writing code. Programming languages are strict about what they’ll accept: after all, they have standards!

Some programming languages are more pedantic than others. Paul Graham memorably characterises C++ as a pernickety aunt^[1]. By contrast, Perl won’t pick nits. Designed by Larry Wall to be his software butler, Perl interprets your ill-expressed wishes with discretion and assurance. Hence you can end up with a Perl program which gets on with its job but which no-one fully understands.

Pedants, by definition, take things too far, but pedantry in programming isn’t all bad. GCC has a useful -pedantic flag. It helps you write portable programs. Perl has a use strict pragma which recasts the butler as a personal trainer.

When it comes to correctness, attention to detail matters. What if this input parameter goes negative? Will that file be closed when an exception is thrown? Can your algorithm handle an empty container?

I recently fixed a defect in some (of my own) code which assumed conformant input. When faced with garbage-in this code failed even to generate garbage-out, instead getting caught in an infinite loop. Should a pedantic program insist on correct inputs or should it consider how to handle all possible inputs? Define pedantic.

[1]: It turns out my memory is at fault here. When I checked the reference I discovered Paul Graham makes no explicit mention of C++.

We need a language that lets us scribble and smudge and smear, not a language where you have to sit with a teacup of types balanced on your knee and make polite conversation with a strict old aunt of a compiler. — Paul Graham, Hackers and Painters

You might have guessed which language he’s promoting for scribbling but there’s no mention of Lisp either in this particular essay. In fact only one programming language earns a name-check. I’ll let you find out which one for yourselves.

Hiding iterator boilerplate behind a Boost facade

tag@wordaligned.org (Thomas Guest) — 2010-07-07

Filling in missing methods. Python

Here’s another wholesome recipe served up by Raymond Hettinger.

Total ordering class decorator

def total_ordering(cls):
    'Class decorator that fills-in missing ordering methods'    
    convert = {
        '__lt__': [('__gt__', lambda self, other: other < self),
                   ('__le__', lambda self, other: not other < self),
                   ('__ge__', lambda self, other: not self < other)],
        '__le__': [('__ge__', lambda self, other: other <= self),
                   ('__lt__', lambda self, other: not other <= self),
                   ('__gt__', lambda self, other: not self <= other)],
        '__gt__': [('__lt__', lambda self, other: other > self),
                   ('__ge__', lambda self, other: not other > self),
                   ('__le__', lambda self, other: not self > other)],
        '__ge__': [('__le__', lambda self, other: other >= self),
                   ('__gt__', lambda self, other: not other >= self),
                   ('__lt__', lambda self, other: not self >= other)]
    }
    roots = set(dir(cls)) & set(convert)
    assert roots, 'must define at least one ordering operation: < > <= >='
    root = max(roots)       # prefer __lt__ to __le__ to __gt__ to __ge__
    for opname, opfunc in convert[root]:
        if opname not in roots:
            opfunc.__name__ = opname
            opfunc.__doc__ = getattr(int, opname).__doc__
            setattr(cls, opname, opfunc)
    return cls

If you have a class, X, which implements one or more of the ordering operators, <, <=, >, >= then total_ordering(X) adapts and returns the class with the missing operators filled-in. Alternatively, use standard decorator syntax to adapt a class. If we apply @total_ordering to a Point class

@total_ordering
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __lt__(self, other):
        return (self.x, self.y) < (other.x, other.y)

then we can compare points however we like

>>> p = Point(1,2)
>>> q = Point(1,3)
>>> p < q, p > q, p >= q, p <= q
(True, False, False, True)

Here’s a nice touch: the freshly-baked methods even have documentation!

>>> help(Point)
Help on class Point in module __main__:

class Point
 |  Methods defined here:
 |  
 |  __ge__(self, other)
 |      x.__ge__(y) <==> x>=y
 |  
 |  __gt__(self, other)
 |      x.__gt__(y) <==> x>y
 |  
 |  __init__(self, x, y)
 |  
 |  __le__(self, other)
 |      x.__le__(y) <==> x<=y
 |  
 |  __lt__(self, other)

Writing class decorators may not be the first thing a new Python programmer attempts, but once you’ve discovered the relationship between Python’s special method names and the more familiar operator symbols, I think this recipe is remarkably straightforward.

convert = {
    '__lt__': [('__gt__', lambda self, other: other < self),
               ('__le__', lambda self, other: not other < self),
               ('__ge__', lambda self, other: not self < other)],
    '__le__': [('__ge__', lambda self, other: other <= self),
               ('__lt__', lambda self, other: not other <= self),
               ('__gt__', lambda self, other: not self <= other)],
    '__gt__': [('__lt__', lambda self, other: other > self),
               ('__ge__', lambda self, other: not other > self),
               ('__le__', lambda self, other: not self > other)],
    '__ge__': [('__le__', lambda self, other: other >= self),
               ('__gt__', lambda self, other: not other >= self),
               ('__lt__', lambda self, other: not self >= other)]
}

Before moving on to something more challenging, look again at one of the recipe’s key ingredients, the convert dict, which helps create the missing ordering functions from existing ones. As you can see, there’s much repetition here, and plenty of opportunities for cut-and-paste errors.

This block of code is an example of what programmers term boilerplate. By using the total ordering decorator, we can avoid boilerplating our own code.^[1]

Filling in missing methods. C++

Python is dynamic and self-aware, happy to expose its internals for this kind of tinkering. It takes real wizardry to achieve similar results with a less flexible language, such as C++ — but it can be done.

In a previous article we developed a random access file iterator in C++. At its heart, this iterator simply repositioned itself using file-seeks and dereferenced itself using file-reads. There wasn’t much to it.

Unfortunately we had to fill-out the iterator with the various members required to make it comply with the standard random access iterator requirements (which was the whole point, since we wanted something we could use with standard binary search algorithms).

We had to expose standard typedefs:

typedef std::random_access_iterator_tag iterator_category;
typedef item value_type;
typedef std::streamoff difference_type;
typedef item * pointer;
typedef item & reference;

Worse, we had to implement a full set of comparison, iteration, step and access functions. Please, page down past the following code block! I only include it here so you can see how long it goes on for.

Iterator boilerplate

public: // Comparison
    bool operator<(iter const & other) const
    {
        return pos < other.pos;
    }
    
    bool operator>(iter const & other) const
    {
        return pos > other.pos;
    }
    
    bool operator==(iter const & other) const
    {
        return pos == other.pos;
    }
    
    bool operator!=(iter const & other) const
    {
        return pos != other.pos;
    }
    
public: // Iteration
    iter & operator++()
    {
        return *this += 1;
    }
    
    iter & operator--()
    {
        return *this -= 1;
    }
    
    iter operator++(int)
    {
        iter tmp(*this);
        ++(*this);
        return tmp;
    }
    
    iter operator--(int)
    {
        iter tmp(*this);
        --(*this);
        return tmp;
    }
    
public: // Step
    iter & operator+=(difference_type n)
    {
        advance(n);
        return *this;
    }
    
    iter & operator-=(difference_type n)
    {
        advance(-n);
        return *this;
    }
    
    iter operator+(difference_type n)
    {
        iter result(*this);
        return result += n;
    }
    
    iter operator-(difference_type n)
    {
        iter result(*this);
        return result -= n;
    }
    
public: // Distance
    difference_type operator-(iter & other)
    {
        return pos - other.pos;
    }
    
public: // Access
    value_type operator*()
    {
        return (*this)[0];
    }

value_type operator[](difference_type n)
    {
        std::streampos restore = getpos();
        advance(n);
        value_type const result = read();
        setpos(restore);
        return result;
    }
    ....

How tiresome! Most of these member functions are directly and unsurprisingly implemented in a standard way. It would be nice if we could write (and test!) what we actually needed to and have a decorator fill in the rest.

Enter Boost iterators

Actually, we can! I’m grateful to proggitor dzorz for telling me how.

A nicer solution would use boost::iterator_facade and just implement dereference, equal, increment, decrement, advance and distance_to.

Like many programmers I have mixed feelings about C++ — when it’s good it’s very very good, but when it’s bad it’s horrid — and these feelings are only amplified by the Boost library. Boost is superb, so long as you stick to the good parts.

So which parts are good? It depends. On you, who you work with, and the platforms you’re working on.

In my previous article I used an ingenious iterator adaptor from the Boost.Spirit parser library to disastrous effect. If only I’d looked a little more carefully I’d have discovered something more useful in a more obvious place. Boost.Iterator could have helped.

As dzorz points out, boost::iterator_facade can work with any C++ iterable. Implement whatever subset of

dereference
equal
increment
decrement
advance
distance_to

is appropriate and iterator_facade will fill in the boilerplate required to standardise your iterator.

In our case, we’ll need the full set. That’s because we’re after a random access iterator. Other iterators need rather less. Here’s a table showing the relationship between core operations and iterator concepts.

Using boost::iterator_facade

The Boost.Iterator documentation is well-written but daunting. Read it from top-to bottom and you’ll get:

rationale and theory
plans for standardisation (which don’t seem correct ^[2])
usage notes
some subtle points on the implementation and its predecessor
a namecheck for the curiously recurring template pattern
a fat reference section detailing the boilerplate which this library allows you to forget
a tutorial

If you’re tempted to skip to the end of the page, you’ll see this code block.

#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>
  
  ....
  
private:
  struct enabler {};
  
public:
  template <class OtherValue>
  node_iter(
      node_iter<OtherValue> const& other
    , typename boost::enable_if<
          boost::is_convertible<OtherValue*,Value*>
        , enabler
      >::type = enabler()
  )
    : m_node(other.m_node) {}

According to the surrounding documentation this is “magic”. I find it scary.

Luckily it turns out the library is straightforward to use. What you really want, as a newcomer, are the usage notes and the tutorial example.

The tutorial walks through the process of skinning a singly-linked list with a forwards iterator facade. This is a different use case to ours: the tutorial shows a basic class which implements what it should, and the facade allows it to be treated as a forwards iterator. In our case we’ve already created a full-blown random access iterator. We can retrospectively apply iterator_facade to strip our class back to basics.

Templates and Traits

Where we had:

template <typename item>
class text_file_iter
{
public: // Traits typedefs, which make this class usable with
        // algorithms which need a random access iterator.
    typedef std::random_access_iterator_tag iterator_category;
    typedef item value_type;
    typedef std::streamoff difference_type;
    typedef item * pointer;
    typedef item & reference;
....
};

We now need (my thanks here to Giuseppe for correcting the code I originally posted here):

template <typename value>
class text_file_iter
    : public boost::iterator_facade<
      text_file_iter<value>
    , value
    , std::random_access_iterator_tag
    , value
    , std::streamoff
    >
....
};

(Yes, the class accepts itself as a template parameter. That’s the curious recursion.)

Constructors, destructors and operators

We still need iterator constructors and destructors — these are unchanged — but we can eliminate every single operator shown in the “Iterator boilerplate” code block above.

Here’s what we need instead, to ensure iterator_facade can do its job. The read() member function we had before doesn’t need changing.

    ....
private: // Everything Boost's iterator facade needs
    friend class boost::iterator_core_access;
    
    value dereference() const
    {
        return read();
    }
    
    bool equal(iter const & other) const
    {
        return pos == other.pos;
    }
    
    void increment()
    {
        advance(1);
    }
    
    void decrement()
    {
        advance(-1);
    }
    
    void advance(std::streamoff n)
    {
        in.seekg(n, std::ios_base::cur);
        pos = in.tellg();
    }
    
    std::streamoff distance_to(iter const & other) const
    {
        return other.pos - pos;
    }

And that really is all there is to it. I’m impressed.

Notice, by the way, that friend is used to expose the primitive, private member functions for use by the boost::iterator_core_access class. This follows the example set by the tutorial. I’ve written enough C and Python to question C++’s sophisticated access rules — you have public, protected and private, but that’s still not enough, so you need friend declaration to cut through it all — which tempts me to simply make dereference(), equal() etc. public, but then the facade wouldn’t be a proper facade. Users should treat the final class exactly as they would any other random access iterator, and designating these members as private means they’ll have to.

Wrinkles

You’ll notice the dereference() member function has a const signature. However, the read() member function is non-const.

    // Return the item at the current position
    value_type read()
    {
        value_type n = 0;
        
        // Reverse till we hit whitespace or the start of the file
        while (in && !isspace(in.peek()))
        {
            in.unget();
        }
        in.clear();
        
        in >> n;
        return n;
    }

Here, in is a data member of type std::ifstream, and clearly the read call modifies it. That’s what this alarming compiler error is trying to tell us.

boost_binary_search_text_file.cpp: In member function 'value text_file_iter<value>::read() const [with value = long long int]':
boost_binary_search_text_file.cpp:90:   instantiated from 'value text_file_iter<value>::dereference() const [with value = long long int]'
/opt/local/include/boost/iterator/iterator_facade.hpp:516:   instantiated from 'static typename Facade::reference boost::iterator_core_access::dereference(const Facade&) [with Facade = text_file_iter<long long int>]'
/opt/local/include/boost/iterator/iterator_facade.hpp:634:   instantiated from 'Reference boost::iterator_facade<I, V, TC, R, D>::operator*() const [with Derived = text_file_iter<long long int>, Value = long long int, CategoryOrTraversal = boost::random_access_traversal_tag, Reference = long long int, Difference = long long int]'
/usr/include/c++/4.2.1/bits/stl_algo.h:4240:   instantiated from 'bool std::binary_search(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = text_file_iter<long long int>, _Tp = main::number]'
boost_binary_search_text_file.cpp:203:   instantiated from here
boost_binary_search_text_file.cpp:174: error: passing 'const std::basic_ifstream<char, std::char_traits<char> >' as 'this' argument of 'typename std::basic_istream<_CharT, _Traits>::int_type std::basic_istream<_CharT, _Traits>::peek() [with _CharT = char, _Traits = std::char_traits<char>]' discards qualifiers
boost_binary_search_text_file.cpp:176: error: passing 'const std::basic_ifstream<char, std::char_traits<char> >' as 'this' argument of 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::unget() [with _CharT = char, _Traits = std::char_traits<char>]' discards qualifiers
boost_binary_search_text_file.cpp:178: error: passing 'const std::basic_ifstream<char, std::char_traits<char> >' as 'this' argument of 'void std::basic_ios<_CharT, _Traits>::clear(std::_Ios_Iostate) [with _CharT = char, _Traits = std::char_traits<char>]' discards qualifiers
boost_binary_search_text_file.cpp:180: error: passing 'const std::basic_ifstream<char, std::char_traits<char> >' as 'this' argument of 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(long long int&) [with _CharT = char, _Traits = std::char_traits<char>]' discards qualifiers

Related to this, the Reference template parameter (shown in bold in the listing below) is actually a value, rather than the (default) value &. As we originally implemented it, our file iterator reads values lazily, only when clients request them. We have no reference to return.

template <typename value>
class text_file_iter
    : public boost::iterator_facade<
      text_file_iter<value>
    , value
    , std::random_access_iterator_tag
    , value
    , std::streamoff
    >
};

I faced a dilemma here. Either I could modify my original file iterator, including a current value data member, which I would take care to update every time we repositioned the file read position. Then our references could be real references and read() would naturally be const, simply returning a reference to this member. Or, I could make the in input stream data member mutable.

Mutable makes me uneasy for the same reason that friend does — if you can shake off the rigours of const-correctness so easily, then why bother with it? — and for this reason the first option appealed. However, a read-only file is an unusual container: we do not change it, but we cannot supply const references to its elements without reading them in, and that will mean changes to the file input stream. The easier option, involving the smallest code change, was to make in mutable. So that’s what I did.

Less code, more software

By employing two of my least favourite C++ keywords I now had a class which provided the functions it should, and, thanks to the magic worked by Boost’s iterator facade, I also had a class which I could use as a standard random access iterator. Most of the code changes were the deletion of boilerplate — very satisfying. I added code too, since I decided to invest a little more effort in tests. I didn’t have any doubts about the Boost library’s correctness but I thought I might not have been using it correctly. Happily these tests all passed.

Performance

Let’s not forget why we originally wanted a random access file iterator: we had a large sorted file, too large to read into memory, and we wanted to test for the presence of the number in this file.

For test purposes I created a file just over 4GB in size. A simple linear search through this file took around 180 seconds on my (aging laptop) computer, and was light on memory use. By creating a random access file iterator, boilerplate and all, we took advantage of the standard binary search algorithm and reduced the time to around 4 milliseconds.

How would our version using Boost iterator facade do? I wasn’t expecting it to be faster than the original, but I wouldn’t have been surprised if it gave it a close run: using Boost doesn’t usually involve compromise. In fact, over repeated runs of my performance tests there was no significant difference between the two iterator versions — or at least there wasn’t once a helpful reader had discovered and fixed a bug in my program, which was causing it to run correctly but slowly.

To trust a facade I guess you need some knowledge of what lies behind it.

Note: During my original performance tests, reported in the first version of this article, the Boost iterator performed woefully, far slower even than a linear search. By this time I’d lost patience, and it was left up to a reader, Giuseppe, to point out my mistake. I’d been using a boost::random_access_traversal_tag template parameter, with the result that std::distance() was using repeated increments rather than calling distance_to() to get an immediate result, and consequently ran very slowly. I should have used std::random_access_iterator_tag. I modified my code accordingly and confirmed that the Boost version does indeed perform on a par with the original version.

My thanks to Chris P for permission to use his photograph of the Library of Celsus at Ephesus, or at rather its beautiful facade. Ephesus is famous for the Temple of Artemis, one of the seven wonders of the ancient world, of which only fragments remain. Thanks too to Dave Hamster for the boilerplate photo — actually a detail from the hull of the SS Great Britain.

If you’d like to continue this experiment the code and the tests I used are available via anonymous SVN access from http://svn.wordaligned.org/svn/etc/search_text_file.

[1]: As of Python 2.7 and 3.2, the standard library will include a version of this recipe. It’s in the functools module. For some reason, your class “should supply an __eq__()” method.

[2]: According to the Boost.Iterator documentation:

Both iterator_facade and iterator_adaptor as well as many of the specialized adaptors mentioned below have been proposed for standardization, and accepted into the first C++ technical report; see our [Standard Proposal For Iterator Facade and Adaptor (PDF)][tr1proposal] for more details.

I assumed this meant there’d be tr1::iterator_(facade|adaptor) classes, but I don’t think that’s the case. Unlike other (good) bits of Boost, the Iterator library doesn’t seem likely to be part of the next C++ release.

Equality and Equivalence

tag@wordaligned.org (Thomas Guest) — 2010-06-09

If A <= B and B <= A then A and B must be equal, right?

Wrong, actually.

We could rank actors according to their Bacon number, for example. Hugh Grant and Daniel Day-Lewis both have a Bacon number of 2, but that doesn’t make them equal!

I think most programmers get the distinction between ordering and equality, but it’s easy to forget.

Part of the problem is the less-than-or-equal-to and greater-than-or-equal-to operators both mention equal. The standard programming representation of these operators includes a single equals symbol, whil the representation of equality has two equals symbols. Symbolically we might assume:

<= ∧ >= ⇒ ==

Wrong!

☠

Another part of the problem is that we tend to think of numbers as archetypal objects: when in doubt, do as the ints do. For integers, it’s true, equality and equivalence are the same. The same is true of real numbers, but what about their floating point representations? A NaN doesn’t even equal itself. Complex numbers have no standard comparison operators.

>>> 3+4j == 4j+3
True
>>> 3+4j <= 4j+3
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: no ordering relation is defined for complex numbers

To avoid trouble, remember that the equal in less-than-or-equal-to should really be equivalent.

Oh, and please don’t confuse equality with assignment.

Binary search revisited

tag@wordaligned.org (Thomas Guest) — 2010-05-26

Recap

Recently I wrote about C++’s standard binary search algorithms (yes, four of them!) which do such a fine job of:

specifying exactly what kind of range a binary search requires
separating the core algorithm from the details of the range it’s working on
delivering precise results

To support these claims I included an implementation of a file iterator, suitable for use with std::binary_search() etc. to efficiently locate values in very large files.

Now, there are a couple of issues with this approach:

we had to write a lot of code to make a file iterator suitable for use with standard algorithms
this file iterator only works on highly structured files, where each value occupies a fixed number of bytes

In this follow up article we’ll consider each of these issues in a little more depth by working through two very different solutions to a related problem.

The Problem

Suppose, once again, that we have a large file, a few gigabytes, say. The file contains numbers, in order, and we’re interested in testing if this file contains a given number. This time, though, the file is a text file, where the numbers are represented in the usual way as sequences of digits separated by whitespace.

$ less lots-of-numbers
...
10346  11467 11469 11472  11501 
  11662    12204 12290
...

Note that a number in this file does not occupy a fixed number of bytes. If we jump to a new position in the file using a seek operation, we cannot expect to land exactly where a number starts. Thus the random access file iterator we developed last time won’t work.

Input iterators

In C++ an input file is an example of an input stream, and the standard library gives us istream_iterators which perform formatted input. In our case, an istream_iterator<int> effectively converts the file into a stream of numbers.

Istream iterators are input iterators. They progress through the input stream, item by item, with no repeating or rewinding allowed. Despite their limitations, the C++ standard library provides some algorithms which require nothing more than basic input iterators. For example, to count up even numbers in the file whose name is supplied on the command line we might use std::count_if.

#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>

bool is_even(int x)
{
    return x % 2 == 0;
}

int main(int argc, char * argv[])
{
    typedef std::istream_iterator<int> i_iter;
    typedef std::ostream_iterator<int> o_iter;
    std::ifstream in(argv[1]);
    
    std::cout << std::count_if(i_iter(in), i_iter(), is_even) << '\n';
    
    return 0;
}

The next version of C++ supports lambda functions, so you’ll be able to put is_even right where it’s used, in the count_if() function call. Or, with the current version of C++, you could write:

Ouch!

    ....
    std::count_if(i_iter(in), i_iter(),
                 std::not1(std::bind2nd(std::modulus<int>(), 2)))

Maybe not!

Find

The very simplest search algorithm, std::find, needs nothing more than an input iterator. To determine if a number is in a file, we could just invoke std::find.

typedef std::istream_iterator<int> i_iter;

bool 
is_number_in_file(char const * filename, int n)
{
    std::ifstream in(filename);
    i_iter begin(in);
    i_iter end;
    return std::find(begin, end, n) != end;
}

Here, the find algorithm advances through the numbers in the file, from start to finish, stopping as soon as it hits one equal to the supplied value, n. We can expect this function to be light on memory use — there will be some buffering at the lower levels of the file access, but nothing more — and the function is evidently correct.

It would be correct even if our file was unsorted, however. Is there any way we can do better?

Rewrite the file!

In the previous article we developed a random access iterator for accessing binary files, and usable for efficient binary searches of sorted binary files. Now would be a good time to question the problem specification. Is this a one off? Or are we going to be testing the presence of more numbers in the file in future? And if so, can we convert the file to binary to save time in the long run?

Although I’m not going to pursue this option here, it may well be the best approach. For now, though, let’s assume we have a one-off problem to solve, and that we aren’t allowed to tinker with the input.

Adapting iterators

If we want to use std::binary_search we need, as a minimum, forward iterators. Like input iterators, forward iterators advance, one step at a time. Unlike input iterators, you can copy a forward iterator and dereference or advance that copy in future, independently of the original.

Forward iterators are suitable for multipass algorithms, such as std::search, which looks for the first occurrence of a sequence within a sequence (a generalised strstr, if you like), or std::adjacent_find and std::search_n which look for repeated elements; and of course std::binary_search, which is our immediate interest.

Wouldn’t it be nice if we could convert our istream iterators into forwards iterators? Then we could plug them directly into all these algorithms.

Other languages allow this. You can replicate streams in the Unix shell with tee. And you can do something similar in Python, thanks to one of the standard iterator tools. Independent iterators over the same sequence needed? Itertools.tee is your friend. The example below codes up adjacent find in Python.

from itertools import tee
import sys

def adjacent_find(xs):
    '''Does the supplied iterable contain any adjacent repeats?
    
    Returns True if xs contains two consecutive, equal items,
    False otherwise. 
    '''
    try:
        curr, next_ = tee(xs)
        next(next_)
        return any(c == n for c, n in zip(curr, next_))
    except StopIteration:
        return False

Why, even Java has an iterator adaptors, courtesy of Jez Higgins’ Mango library.

What about C++? I couldn’t find any such iterator adaptors in the standard library, but I turned up something in the standard library research and development unit, also known as Boost.

Multipass iterator

Boost.Spirit is a remarkable C++ parser framework, which uses operator overloading to represent parsers directly as EBNF grammars in C++. Somewhere in its depths it tracks back, and hence must adapt input iterators into forward iterators — or multipass iterators, to use its own term.

The multi_pass iterator will convert any input iterator into a forward iterator suitable for use with Spirit.Qi. multi_pass will buffer data when needed and will discard the buffer when its contents is not needed anymore. This happens either if only one copy of the iterator exists or if no backtracking can occur.

What’s good enough for parsing is more than good enough for searching. Here’s a function which detects whether a number is in a file. Most of the code here just includes the right headers and defines some typedefs. By leaning on high quality support libraries we’ve overcome our first issue: we no longer have to write loads of code just to call binary search!

Boost spirit multipass iterators

#include <fstream>
#include <iterator>
#include <algorithm>

#include <boost/spirit/include/support_multi_pass.hpp>

namespace spirit = boost::spirit;

typedef long long number;
typedef std::istream_iterator<number> in_it;
typedef spirit::multi_pass<in_it> fwd_it;

/*
  Returns true if the input number can be found in the named 
  file, false otherwise. The file must contain ordered, 
  whitespace separated numbers.
*/
bool
is_number_in_file(number n, char const * filename)
{
    std::ifstream in(filename);
    
    fwd_it begin = spirit::make_default_multi_pass(in_it(in));
    fwd_it end = spirit::make_default_multi_pass(in_it());
    
    return std::binary_search(begin, end, n);
}

Not so fast

If this library-based solution looks too good to be true, that’s because it is! As we noted before, the standard binary search algorithm may indeed work with forward iterators, but it works far better with random access iterators. There’s no point reducing the number of integer comparisons to O(log(N)) if we’re going to advance our iterators O(N) times.

What’s worse, these multipass iterators aren’t magic. Did you read the smallprint concerning Python’s tee iterator?

This itertool may require significant auxiliary storage (depending on how much temporary data needs to be stored).

If teed iterators diverge, intervening values have to be stored somewhere, and the same appears to be true of our inscrutable multipass iterators. Huge chunks of our large input file are buffered into memory. When I ran this function to confirm the presence of a single number somewhere near the middle of a 4.4GB input file, it took over 19 minutes.

real	19m13.675s
user	5m19.219s
sys	1m26.278s

Much of this time was spent paging.

As a comparison, testing for the same value using find took just under 3 minutes.

real	2m48.139s
user	2m21.336s
sys	0m7.252s

You’ll have noticed that we used default multipass iterators. These iterators permit multi-dimensional customisation. I wasn’t feeling brave enough to attempt a template storage policy class, and I very much doubt I could have beaten a simple linear find anyway; anything built on a generic input iterator is unlikely to solve our problem efficiently.

Better than find

We can beat std::find with a bit of ingenuity. Standard istream iterators are useful but, in this case, not a good starting point. A better idea is to create a novel iterator which uses file seek operations to advance through the file, then fine-tunes the file position to point at a number.

Consider an imagine an iterator which can be positioned at any seekable position in the file, and which we dereference to be the first number in the file which ends at or after that position. The graphic below shows a file with 11 seekable positions, 0 through 10 inclusive.

positions 0 and 1 dereference to the number 42
positions 2, 3, 4 and 5 dereference to the number 57
positions 6, 7, 8 and 9 dereference to the number 133
it is an error to try and dereference position 10, at the end of the file

Now, this is a rather unusual iterator. It iterates over the numbers in the file, but each number gets repeated for every byte in the file it occupies. Despite this duality it’s perfectly usable — so long as we keep a clear head. Binary searches are fine.

How does this version perform?

Recall, a linear search for a single value in the middle of a 4.4GB took nearly 3 minutes. Running 10 binary searches through the same file took just 40 milliseconds — that’s a rate of 25 searches a second!

Implementation

Here’s our weird new iterator. It should be usable on files containing whitespace separated items of any type for which the stream read operator>>() has been defined.

There’s quite a lot of code here, but much of it is random access iterator scaffolding. The interesting functions are the private implementation details towards the end of the class.

#include <fstream>
#include <ios>
#include <iterator>
#include <stdexcept>

#include <ctype.h>

// File read error, thrown when low level file access fails.
class file_read_error : public std::runtime_error
{
public:
    file_read_error(std::string const & what)
        : std::runtime_error(what)
    {
    }
};

/*
  Here's an unusual iterator which can be used to binary search
  for whitespace-separated items in a text file.
  
  It masquerades as a random access iterator but a file
  is not usually a random access device. Nonetheless, file seek
  operations are quicker than stepping through the file item by
  item.
  
  The unusual thing is that the iterators correspond to 
  file offsets rather than items within the file.
  
  Here's a short example where the items are numbers.
  
  +---+---+---+---+---+---+---+---+---+---+
  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
  +---+---+---+---+---+---+---+---+---+---+
  |'4'|'2'|   |   |'5'|'7'|   |'1'|'3'|'3'|
  +---+---+---+---+---+---+---+---+---+---+
  
  The graphic shows a text file which contains 3 numbers,
  42, 57, 133, separated by whitespace.
  
  The file itself is 10 bytes long, and hence there are 11
  iterators over the file, corresponding to actual file positions
  (including the one-past-the end position). To dereference an
  iterator, we step back through the file until we reach either
  whitespace or the start of the file. Then we look forwards 
  again and read in the next item.
  
  In the graphic above:
  
   - Iterators 0 and 1 point to number 42
   - Iterators 2, 3, 4 and 5 point to number 57
   - Iterators 6, 7, 8, 9 point to number 133
   - Iterator 10 is the end, and must not be dereferenced
  
  Dereferencing an iterator always returns an item which is in
  the file, and all items in the file have iterators pointing to
  them, so std::binary_search based on these iterators is valid.
  
  The iterators also expose their underlying file positions
  directory (via the getpos() member function), and with a
  little thought we can make use of std::lower_bound() and
  std::upper_bound().
*/
template <typename item>
class text_file_item_iter
{
    typedef text_file_item_iter<item> iter;
    
private: // Sanity
    
    // Check things are OK, throwing an error on failure.
    void check(bool ok, std::string const & what)
    {
        if (!ok)
        {
            throw file_read_error(what);          
        }
    }
    
public: // Traits typedefs, which make this class usable with
        // algorithms which need a random access iterator.
    typedef std::random_access_iterator_tag iterator_category;
    typedef item value_type;
    typedef std::streamoff difference_type;
    typedef item * pointer;
    typedef item & reference;
    
    enum start_pos { begin, end };
    
public: // Lifecycle
    text_file_item_iter(iter const & other)
        : fname(other.fname)
    {
        open();
        setpos(other.pos);
    }
    
    text_file_item_iter()
        : pos(-1)
    {
    }
    
    text_file_item_iter(std::string const & fname,
                        start_pos where = begin)
        : fname(fname)
        , pos(-1)
    {
        open();
        if (where == end)
        {
            seek_end();
        }
    }
    
    ~text_file_item_iter()
    {
        close();
    }
    
    iter & operator=(iter const & other)
    {
        close();
        fname = other.fname;
        open();
        setpos(other.pos);
        return *this;
    } 
    
public: // Comparison
        // Note: it's an error to compare iterators over different files.
    bool operator<(iter const & other) const
    {
        return pos < other.pos;
    }
    
    bool operator>(iter const & other) const
    {
        return pos > other.pos;
    }
    
    bool operator==(iter const & other) const
    {
        return pos == other.pos;
    }
    
    bool operator!=(iter const & other) const
    {
        return pos != other.pos;
    }
    
public: // Iteration
    iter & operator++()
    {
        return *this += 1;
    }
    
    iter & operator--()
    {
        return *this -= 1;
    }
    
    iter operator++(int)
    {
        iter tmp(*this);
        ++(*this);
        return tmp;
    }
    
    iter operator--(int)
    {
        iter tmp(*this);
        --(*this);
        return tmp;
    }
    
public: // Step
    iter & operator+=(difference_type n)
    {
        advance(n);
        return *this;
    }
    
    iter & operator-=(difference_type n)
    {
        advance(-n);
        return *this;
    }
    
    iter operator+(difference_type n)
    {
        iter result(*this);
        return result += n;
    }
    
    iter operator-(difference_type n)
    {
        iter result(*this);
        return result -= n;
    }
    
public: // Distance
    difference_type operator-(iter & other)
    {
        return pos - other.pos;
    }
    
public: // Access
    value_type operator*()
    {
        return (*this)[0];
    }
    
    value_type operator[](difference_type n)
    {
        std::streampos restore = getpos();
        advance(n);
        value_type const result = read();
        setpos(restore);
        return result;
    }
    
    // Allow direct access to the underlying stream position
    std::streampos getpos()
    {
        std::streampos pos_ = in.tellg();
        check(in, "getpos failed");
        return pos_;
    }
    
private: // Implementation details
    void open()
    {
        in.open(fname.c_str(), std::ios::binary);
        check(in, "open failed");
        pos = getpos();
    }
    
    void close()
    {
        if (in.is_open())
        {
            in.close();
            check(in, "close failed");
        }
    }
    
    void advance(difference_type n)
    {
        check(in.seekg(n, std::ios_base::cur), "advance failed");
        pos = getpos();
    }
    
    void seek_end()
    {
        check(in.seekg(0, std::ios_base::end), "seek_end failed");
        chop_whitespace();
        pos = getpos();
    }
    
    void chop_whitespace()
    {
        do
        {
            in.unget();
        } while (isspace(in.peek()));
        in.get();
        in.clear();
    }
    
    void setpos(std::streampos newpos)
    {
        check(in.seekg(newpos), "setpos failed");
        pos = newpos;
    }
    
    // Return the item at the current position
    value_type read()
    {
        item n = 0;
        // Reverse till we hit whitespace or the start of the file
        while (in && !isspace(in.peek()))
        {
            in.unget();
        }
        in.clear();
        check(in >> n, "read failed");
        return n;
    }
    
private: // State
    std::string fname;
    std::ifstream in;
    std::streampos pos;
};

Hardware used

  Model Name:	            MacBook
  Model Identifier:	    MacBook1,1
  Processor Name:           Intel Core Duo
  Processor Speed:          2 GHz
  Number Of Processors:	    1
  Total Number Of Cores:    2
  L2 Cache (per processor): 2 MB
  Memory:                   2 GB
  Bus Speed:                667 MHz

Conclusions

Initially the Boost.Spirit solution looked promising but we pushed it too hard. Suitable abstractions can remove complexity; but they can also hide it. When efficiency matters, we need a handle on what’s going on.

After this false start we did find a way to create a file iterator suitable for use with the standard binary search algorithms. Use it with care, though!

Man or man(1)?

tag@wordaligned.org (Thomas Guest) — 2010-05-19

How careless, we’d forgotten to configure log rotation. So our application had gone with a default designed for a less verbose age, rotating files as soon as they exceeded a megabyte in size, and never throwing any of them away. Oh, and it was putting these log files at the root of the file system where they’d somehow gone unnoticed for some time. As a consequence, the file system had become clogged up with squillions of files.

$ cd /
$ ls
...
server.log.736624
server.log.736625
server.log.736626
server.log.736627
...

How many files, exactly?

$ ls | wc -l
^C

No time to wait. Too many! We had to act fast.

We changed the log rotate configuration to something more appropriate, restarted the application, and set about cleaning up. Now, this is when you don’t want to open a file browser and drag files into trash can, not unless you like watching egg-timers. The desktop metaphor fails when you have squillions of files on your desk. Alarmingly, the shell complains too.

$ rm server.log.*
-bash: /bin/rm: Argument list too long

At this point, a clear head and a steady hand is needed. I use pathname expansion and rm all the time and I’m confident the commands I type will have the right effect. But in my current situation — as root user, in the root directory, on a machine running an unfamiliar flavour of Unix, about to combine find with xargs and rm — I grow nervous.

How to stop find from descending? -Maxdepth, I think, but level 0 or 1? Is -print required? Should I create a scratch directory and practise.

Enough questions already! Are you a man or a man(1) reader?

$ find / -maxdepth 1 -name 'server.log.*' | xargs rm -f

Done!

Binary search returns … ?

tag@wordaligned.org (Thomas Guest) — 2010-05-12

In an article inspired by Jon Bentley’s classic book, Programming Pearls, Mike Taylor invites his readers to implement the binary search algorithm. To spice things up, he requests we work:

without reference to any existing implementation
without calling any library routine, such as bsearch
without writing tests.

Mike Taylor doesn’t formally specify the problem. He’s confident his readers will know what a binary search is, and if not, the description he quotes from Programming Pearls should suffice:

Binary search solves the problem [of searching within a pre-sorted array] by keeping track of a range within the array in which T [i.e. the sought value] must be if it is anywhere in the array. Initially, the range is the entire array. The range is shrunk by comparing its middle element to T and discarding half the range. The process continues until T is discovered in the array, or until the range in which it must lie is known to be empty.

So could our binary search implementation simply return a binary result, true if T is in the array, false otherwise? Well, Yes. And No. A binary search can provide more information, as Mike Taylor hints when he mentions bsearch.

Jon Bentley and Mike Taylor are primarily interested in how often programmers make a mess of what appears to be a simple assignment and in how to avoid this mess. In this article, I’d like to point out that the problem specification needs attention too.

Bsearch in C

The C library’s bsearch function returns the location of T, if found, or a sentinel value otherwise. We might use the array index of T or -1 as location and sentinel. Standard C uses pointers:

NAME
    bsearch -- binary search of a sorted table
    
SYNOPSIS
    #include <stdlib.h>
    
    void *
    bsearch(const void *key, const void *base, size_t nel, 
        size_t width,
        int (*compar) (const void *, const void *));
    
DESCRIPTION 
    The bsearch() function searches an array of `nel` objects, 
    the initial member of which is pointed to by `base`, for a member
    that matches the  object pointed to by `key`.  The size (in bytes)
    of each member of the array is specified by `width`.
    
    The contents of the array should be in ascending sorted order 
    according to the comparison function referenced by `compar`.  The 
    `compar` routine is expected to have two arguments which point to
    the `key` object and to an array member, in that order.  It should 
    return an integer which is less than, equal to, or greater than
    zero if the `key` object is found, respectively, to be less than,
    to match, or be greater than the array member.

RETURN VALUES
    The bsearch() function returns a pointer to a matching member
    of the array, or a null pointer if no match is found.  If two members
    compare as equal, which member is matched is unspecified.

Void pointers, function pointers, raw memory — generic functions in C aren’t pretty. How would this function look in a language with better support for generic programming?

Binary search in C++

C++ programmers can of course use bsearch directly since C++ includes the standard C library. The C++ counterpart would seem to be std::binary_search.

At first glance std::binary_search appears to be a weakened version of bsearch. Like bsearch, it searches for a value. Unlike bsearch, it simply returns a boolean result: true if the value is found, false otherwise. Nonetheless, it can tell us more than bsearch in some circumstances.

Let’s return to Mike Taylor’s second constraint, the one about implementing functions which already exist in standard libraries. In a follow up article he explains:

… sometimes you do need to write a binary search, and the library routines won’t get the job done. Or if they will, they’re grotesquely inefficient. For example, suppose you have a 64-bit integer, and you need to find out whether it’s among the nine billion 64-bit integers that are stored in ascending order in a 72 Gb file. The naive solution is to read the file into memory, making an array (or, heaven help us, an Array) of nine billion elements, then invoke the library search function. And of course that just plain won’t work — the array won’t fit in memory.

Agreed! We should know how our wheels work and be ready to reinvent them when necessary: but C++’s std::binary_search will solve this problem efficiently. All we need is a suitable iterator over the file, in this case one which:

increments in 8 byte steps
uses file seeks for larger steps
is dereferenced by reading 8 byte values from the file
stores file position, for use in ordering and distance operations

I include an implementation of just such an iterator towards the end of this article. My aging laptop didn’t have enough disk space for a 72GB data file but I found room for a 5GB one. Std::binary_search() took milliseconds to test the presence of values in this file, and the times improved dramatically on repeat runs; using a linear search, the time extended to minutes, and repeat runs showed no such improvements.

Std::binary_search() requirements

It’s fair to suggest that creating a custom iterator just so we could use std::binary_search merely moves the problem. The iterator’s implementation is longer and arguably more fiddly than any custom binary search function would be. Why couldn’t we use a standard input stream iterator with the standard binary search algorithm?

The reason is that std::istream_iterators are input iterators, suitable only for single pass algorithms. Binary search doesn’t need to take any backwards steps but it does need to be able copy its iterators and advance them repeatedly. As a minimum, then, it requires forwards iterators.

Note the algorithm’s complexity!

The number of comparisons is logarithmic: at most log(last - first) + 2. If ForwardIterator is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to last - first.

In the case of our large file of numbers, comparisons are cheap; there’s little point minimising them if we’re going to take billions of short steps through the file. This is why we created a random access file iterator^[1].

A more subtle point is that binary search deals with equivalence rather than equality: it only requires a less-than operator (or a comparison function), and returns true if it can find an element x which satisfies !(x < t) && !(t < x).

The point I’m making is that C++ does a nice job of separating algorithms and containers, which is why the same algorithm can be used on vectors, files, arrays etc. It also carefully defines minimum requirements on the types used by algorithms^[2].

Std::binary_search() limitations

We noted earlier that std::binary_search delivers nothing more than a binary result. Is the element there or not? From the SGI STL documentation:

Note that this is not necessarily the information you are interested in!

Even bsearch tells us where it found the match; or rather, where it found a match, since there could be several. This imprecision is one of bsearch’s failings — but it really lets us down when it can’t find the element: in this case, it subdivides the range until it finds where the element would be if it were there, realises there is no match, then throws all positional information away and returns a null pointer.

Suppose our large file represents a set of numbers and we want to know where our test number should go in this file, if it isn’t already present? A C++ binary search algorithm can do this, but it isn’t std::binary_search.

Locating missing elements

Here’s another problem binary search can solve. Suppose we want to know how many runners finished the 2010 London marathon in a time between 3 and 4 hours. Let’s suppose we’ve already loaded the ordered finishing times into an array.

We might try using bsearch to find the position of the runners who finished with a time of exactly 3 hours and with a time of exactly 4 hours. Then the answer would be the difference between these two positions.

There are two problems with this approach:

what if no one finished with a time of exactly 3 or 4 hours?
what if more than one runner finished with a time of exactly 3 or 4 hours?

In the first case bsearch returns a null pointer and we can’t complete our calculation. In the second case, bsearch makes no guarantees about which of the equally-placed runners it will find, and even if we can make our calculation, we cannot be sure it is correct.

Bsearch is not much use, then, but a binary search can give us our answer.

Imagine we had a late result for the race, a runner who recorded a time of exactly 3 hours. What’s the first position in the array at which we could place this runner, whilst maintaining the array ordering? Similarly, where’s the first position at which we could insert a runner with a time of 4 hours, maintaining the array ordering. Both these positions are well defined and precise — even if everyone finished the race in less than 3 hours, or even if no one ran the race — and the correct answer is their difference.

Lower_bound

C++ supplies just such an algorithm. It goes by the name of std::lower_bound, but really it’s good old binary search. We want to find the first place our target element could go, whilst maintaining the ordering, which we do by repeatedly splitting the range.

while the range is non-empty
look at the element in the middle of the range
is its value less than the target value?
if so, continue looking in the top half of the range
if not, continue looking in the bottom half of the range

The while loop exits when the range has been reduced to a single point and this point is what we return. On my platform, the code itself reads a bit like:

template<typename fwd_it, typename t>
fwd_it
lower_bound(fwd_it first, fwd_it last, const t & val)
{
    typedef typename iterator_traits<fwd_it>::difference_type distance;
    
    distance len = std::distance(first, last);
    distance half;
    fwd_it middle;
    
    while (len > 0)
    {
        half = len >> 1;
        middle = first;
        std::advance(middle, half);
        if (*middle < val)
        {
            first = middle;
            ++first;
            len = len - half - 1;
        }
        else
            len = half;
    }
    return first;
}

I think this version of binary search is yet another gem from the C++ standard library. As Jon Bentley and Mike Taylor eloquently point out, the implementation is subtle — in particular, if (*middle < val) we must eliminate middle or risk an infinite loop — but by tightening the problem specification and paring back the requirements we’ve created a function which is far more useful than bsearch and arguably simpler to code.

For comparison, here’s the bsearch implemented by glibc, version 2.11.

/* Perform a binary search for KEY in BASE which has NMEMB elements
   of SIZE bytes each.  The comparisons are done by (*COMPAR)().  */
void *
bsearch (const void *key, const void *base, size_t nmemb, size_t size,
         int (*compar) (const void *, const void *))
{
  size_t l, u, idx;
  const void *p;
  int comparison;
  
  l = 0;
  u = nmemb;
  while (l < u)
    {
      idx = (l + u) / 2;
      p = (void *) (((const char *) base) + (idx * size));
      comparison = (*compar) (key, p);
      if (comparison < 0)
        u = idx;
      else if (comparison > 0)
        l = idx + 1;
      else
        return (void *) p;
    }

return NULL;
}

Binary search variants

On my platform, std::binary_search is built directly on std::lower_bound. Here’s the code.

template<typename fwd_it, typename t>
fwd_it
lower_bound(fwd_it first, fwd_it last, const t & val)
{
    fwd_it i = std::lower_bound(first, last, val);
    return i != last && !(val < *i);
}

Std::upper_bound searches a sorted range to find the last position an item could be inserted without changing the ordering.

Std::equal_range returns a pair of iterators, logically equal to make_pair(lower_bound(...), upper_bound(...)).

Iterating over numbers in a file

The iterator class I created to use std::binary_search on an file containing fixed width binary formatted numbers appears below. To determine whether the file numbers.bin contains the target value 288230376151711744, we would write something like:

#include <algorithm>

....
    
    typedef binary_file_number_iter<long long, 8> iter;
    long long target = 288230376151711744LL;
    
    bool found = std::binary_search(iter("numbers.bin", iter::begin),
                                    iter("numbers.bin", iter::end),
                                    target);

To test the performance of these iterators I created a 5GB binary file packed with 8 byte numbers. These numbers were multiples of 3:

0, 3, 6, 9, ..., 2015231997

I then timed how long it took to search this file for 10 interesting numbers (and to confirm the returned results were as expected).

-1, 0, 1, 2, 1007616000, 1007616001, 1007616002, 1007616003, 2015231997, 2015232000

Binary_search() recorded a time of 0.308 seconds on a rather old MacBook^[3]. Using a hand-coded linear search the run time was just over 38 minutes. That is, the binary search ran 7000 times faster on this sample.

Interestingly, repeated runs of the binary search test using the same input file and the same targets ran in an average time of just 0.030 seconds, a 10-fold times speed up over the first run. Similarly repeating the linear search showed no such improvement. I’m attributing this to operating system file caching, but I don’t pretend to know exactly what’s going on here. (My thanks to Michal Mocny for his explanation in the comments below).

Binary file number iterator

#ifndef BINARY_FILE_NUMBER_ITERATOR_HPP_INCLUDED
#define BINARY_FILE_NUMBER_ITERATOR_HPP_INCLUDED

#include <fstream>
#include <ios>
#include <iostream>
#include <iterator>
#include <stdexcept>

// File read error, thrown when low level file access fails.
class file_read_error : public std::runtime_error
{
public:
    file_read_error(std::string const & what)
        : std::runtime_error(what)
    {
    }
};

// This iterator class is used for numbers packed into a file
// using a fixed width binary format. Numbers must be packed
// most significant byte first.
//
// The file is not read into memory. Iterators are moved by
// file seeking and dereferenced by reading from the file.
//
// These iterators declare themselves to be random access
// iterators but a file is not usually a random access device.
// For example, advancing an iterator a large distance may well
// take longer than advancing a small distance.
template <typename number, int number_size>
class binary_file_number_iter
{
    typedef binary_file_number_iter<number, number_size> iter;
    
private: // Sanity
    // Check things are OK, closing the stream and throwing an error on failure.
    void check(bool ok, std::string const & what)
    {
        if (!ok)
        {
            close();
            throw file_read_error(what);          
        }
    }
    
public: // Traits typedefs, which make this class usable with
        // algorithms which need a random access iterator.
    typedef std::random_access_iterator_tag iterator_category;
    typedef number value_type;
    typedef std::streamoff difference_type;
    typedef number * pointer;
    typedef number & reference;
    
public:
    static int const number_width = number_size;
    
public: // Enum used to construct begin, end iterators
    enum start_pos { begin, end };
    
public: // Lifecycle
    binary_file_number_iter(std::string const & filename,
                            start_pos where = begin)
        : filename(filename)
        , pos(-1)
    {
        open();
        if (where == end)
        {
            seek_end();
        }
    }
    
    binary_file_number_iter()
        : pos(-1)
    {
    }
    
    binary_file_number_iter(iter const & other)
        : filename(other.filename)
    {
        open();
        setpos(other.pos);
    }
    
    ~binary_file_number_iter()
    {
        close();
    }
    
    iter & operator=(iter const & other)
    {
        close();
        filename = other.filename;
        open();
        setpos(other.pos);
        return *this;
    } 
    
public: // Comparison
        // Note: it is an error to compare iterators into different files.
    bool operator<(iter const & other) const
    {
        return pos < other.pos;
    }
    
    bool operator>(iter const & other) const
    {
        return pos > other.pos;
    }
    
    bool operator==(iter const & other) const
    {
        return pos == other.pos;
    }
    
    bool operator!=(iter const & other) const
    {
        return pos != other.pos;
    }
    
public: // Iteration
    iter & operator++()
    {
        return *this += 1;
    }
    
    iter & operator--()
    {
        return *this -= 1;
    }
    
    iter operator++(int)
    {
        iter tmp(*this);
        ++(*this);
        return tmp;
    }
    
    iter operator--(int)
    {
        iter tmp(*this);
        --(*this);
        return tmp;
    }
    
public: // Step
    iter & operator+=(difference_type n)
    {
        advance(n);
        return *this;
    }
    
    iter & operator-=(difference_type n)
    {
        advance(-n);
        return *this;
    }
    
    iter operator+(difference_type n)
    {
        iter result(*this);
        return result += n;
    }
    
    iter operator-(difference_type n)
    {
        iter result(*this);
        return result -= n;
    }
    
public: // Distance
    difference_type operator-(iter & other)
    {
        return (pos - other.pos) / number_size;
    }
    
public: // Access
    value_type operator*()
    {
        return (*this)[0];
    }
    
    value_type operator[](difference_type n)
    {
        std::streampos restore = getpos();
        advance(n);
        value_type const result = read();
        setpos(restore);
        return result;
    }
    
    // Allow access to the underlying stream position
    std::streampos getpos()
    {
        std::streampos s = in.tellg();
        check(in, "getpos failed");
        return s;
    }
private: // Implementation details
    void open()
    {
        in.open(filename.c_str(), std::ios::binary);
        check(in, "open failed");
        pos = getpos();
    }
    
    void close()
    {
        if (in.is_open())
        {
            in.close();
        }
    }
    
    void advance(difference_type n)
    {
        check(in.seekg(n * number_size, std::ios_base::cur), "advance failed");
        pos = getpos();
    }
    
    void seek_end()
    {
        check(in.seekg(0, std::ios_base::end), "seek_end failed");
        pos = getpos();
    }
    
    void setpos(std::streampos newpos)
    {
        check(in.seekg(newpos), "setpos failed");
        pos = newpos;
    }
    
    value_type read()
    {
        number n = 0;
        unsigned char buf[number_size];
        check(in.read((char *)buf, number_size), "read failed");
        
        for (int i = 0; i != number_size; ++i)
        {
            n <<= 8;
            n |= buf[i];
        }
        return n;
    }
    
private: // State
    std::string filename;
    std::ifstream in;
    std::streampos pos;
};

#endif // BINARY_FILE_NUMBER_ITERATOR_HPP_INCLUDED

Here are some basic tests for the binary file number iterator.

Test binary file number iterator

#include <assert.h>
#include <fstream>
#include <algorithm>
#include <ext/algorithm> // For Gnu's non-standard is_sorted
#include <iostream>

#include "binary_file_number_iterator.hpp"

typedef binary_file_number_iter<long long, 8> iter8;
typedef binary_file_number_iter<int, 4> iter4;
typedef binary_file_number_iter<short, 2> iter2;
typedef binary_file_number_iter<char, 1> iter1;

template <typename fwd_it>
bool is_sorted(fwd_it beg, fwd_it end)
{
    return __gnu_cxx::is_sorted(beg, end);
}

char const * empty_test_file(char const * name)
{
    std::ofstream ofile;
    ofile.open(name);
    ofile.close();
    return name;
}

/*
  Create a small test file containing numbers, in ascending order,
  for number sizes 1, 2, 4 and 8 bytes.
  
  A hex view of the file looks like:
  
  0000 0000 0000 0000 0303 0303 0303 0303
  0606 0606 0606 0606 0909 0909 0909 0909
  0c0c 0c0c 0c0c 0c0c 0f0f 0f0f 0f0f 0f0f
*/
char const * basic_test_file(char const * name)
{
    std::ofstream ofile;
    ofile.open(name);
    for (unsigned char i = 0; i != 18; i += 3)
        for (unsigned j = 0; j != 8; ++j)
            ofile << i;            
    ofile.close();
    return name;
}

void empty_file_tests()
{
    char const * empty_file = empty_test_file("empty_test_file");
    iter1 beg(empty_file, iter1::begin);
    iter1 end(empty_file, iter1::end);
    assert(beg == end);
    assert(std::lower_bound(beg, end, -1) == end);
    assert(std::upper_bound(beg, end, -1) == end);
    assert(!std::binary_search(beg, end, 0));
    assert(std::equal_range(beg, end, -1) == std::make_pair(beg, beg));
}

template <typename value_type>
value_type repeat(int v, int w)
{
    value_type result = 0;
    while (w-- != 0)
    {
        result <<= 8;
        result |= v;
    }
    return result;
}

template <typename iter>
void basic_file_tests()
{
    char const * basic_file = basic_test_file("basic_test_file");
    
    typedef typename iter::value_type value_t;
    typedef typename std::pair<iter, iter> range;
    int const w = iter::number_width;
    
    iter beg(basic_file, iter::begin);
    iter end(basic_file, iter::end);
    assert(beg < end);
    assert(!(beg > end));
    assert(!(beg == end));
    assert(beg != end);
    assert(end - beg == 48 / w);
    
    iter mid = beg;
    assert(mid[0] == 0);
    assert(mid[8/w] == repeat<value_t>(3, w));
    assert(*mid == 0);
    assert(*mid++ == 0);
    assert(*--mid == 0);
    assert(*(mid += 16/w) == repeat<value_t>(6, w));
    assert(mid < end);
    assert(mid > beg);
    
    assert(is_sorted(beg, end));
    assert(std::lower_bound(beg, mid, -1) == beg);
    assert(std::lower_bound(beg, mid, 0) == beg);
    assert(std::upper_bound(beg, mid, 0) == beg + 8/w);
    assert(std::upper_bound(beg, mid, 1) == beg + 8/w);
    assert(std::binary_search(beg, end, 0));
    assert(std::binary_search(beg, end, repeat<value_t>(0xf, w)));
    
    mid = beg + 8/w;
    assert(std::equal_range(beg, end, 0) == std::make_pair(beg, mid));
    assert(std::equal_range(beg, end, 1) == std::make_pair(mid, mid));
}

int main()
{
    empty_file_tests();
    basic_file_tests<iter1>();
    basic_file_tests<iter2>();
    basic_file_tests<iter4>();
    basic_file_tests<iter8>();
    return 0;
}

Triple fail

In this article we’ve discussed binary search:

referring to existing implementations
calling library routines, such as std::binary_search
and written some tests.

Despite this indiscipline, we never even bothered to roll our own binary search: we’ve tackled the exact opposite of the problem which Mike Taylor set. Programming tasks rarely start with a clear specification, and even if they do, the specification needs questioning.

Thanks

My thanks to pinprick for the cheese photos, and for this delicious description.

morbier is a soft-ripened, washed rind cheese. the tradition of bathing the rinds in salty water (or strong ale) goes back to trappist monks, who perfected the art. washing the rind makes it tougher, protecting the cheese and making it last longer. washing the rind also makes it a place where a certain bacteria, b. linens, love to hang out. while they work their magic, making the cheese inside smooth and creamy and silky, they also make the outside stinky. there isn’t any good way to put it. however, most stinky cheese taste amazing, and once you realize that, you find that you love the smell of stinky cheese. stink on the outside means gold on the inside! — pinprick

How long before flickr implements scratch and sniff?

[1]: Well, something which masquerades as a random access iterator. Files are not usually random access devices, and the time taken by a seek operation may well vary with the seek offset. By supplying random access scaffolding, we at least ensure that a single, efficient, seek operation is used each time we advance the file position.

[2]: The C++ standard describes the requirements on types in some detail. Unfortunately C++ implementations provide little support for enforcing these requirements. Violations are likely to be punished by grotesque compiler warnings.

[3]: The laptop specification:

Hardware Overview:
  Model Name:	            MacBook
  Model Identifier:	    MacBook1,1
  Processor Name:	    Intel Core Duo
  Processor Speed:	    2 GHz
  Number Of Processors:	    1
  Total Number Of Cores:    2
  L2 Cache (per processor): 2 MB
  Memory:                   2 GB
  Bus Speed:                667 MHz

Think, quote, escape

tag@wordaligned.org (Thomas Guest) — 2010-03-30

Evidently Jamie had got in before me. Somehow he’d unpacked the new 2U server and balanced it on the side of his desk. He looked hassled. I didn’t ask. The server’s fans whirred noisily. On Jamie’s second monitor I could see the familiar chatter of Linux installing itself. I stepped over the cardboard and polystyrene, sat, woke my machine.

Moments later I heard the install disk eject. Jamie typed something, cursed. The disk clattered into the bin. The room grew quiet as the server shut down.

We were a small, new team. Nonetheless, we’d put something substantial together. It built on a Java framework and ran on Linux. We’d tweaked the framework, meaning we had to build it from source before building our own stuff, so a clean build took almost half an hour. Just over half an hour later, Jamie had burned a new install disk. He placed it in the server’s DVD drive. The fans roared up again. Ten minutes later, more cursing, another disk in the bin.

I walked across. Jamie was glaring at some code. A Perl list? His cursor was poised over an item in this list, a single-quoted string, inside which was a sed command, whose arguments themselves needed quoting, which was evidently meant to edit the contents of a double-quoted string in some configuration file. Think: quote and escape. I could see there were four DVDs in the bin. Jamie must have been in for some time. No wonder he looked hassled.

So, what’s up?

A trade show in the States. The salesman was out there. A bare machine had already been delivered and he needed the software, so Jamie had to cut a DVD which would directly install the operating system together with our application. Please don’t expect a salesman to download an ISO image and set up enough of a network to boot from it. A courier was booked for midday to collect the DVD. That’s what’s up. So leave me alone and let me get on with it.

He didn’t actually say that last bit. It’s true, though, he was the Linux expert. I stubbornly watched as he changed some double quotes for single ones, added a couple more backslashes, checked in the file, kicked off another build.

Back at my desk, I reviewed the version control change logs. Evidently Jamie was working on a post-install script which took the form of a list of actions which would be evaluated and executed in Perl. Looking at the file diffs, the sticking point seemed to be a sed command to edit the X display settings. Embedding sed within Perl was proving tricky.

Jamie’s edit-build-burn-install-check cycle seemed crazy to me. Why not recreate the broken post-install step as a standalone operation? Soon enough I’d found a way to reproduce the problem. After reading documentation and experimenting I figured out how to nest and escape the various strings. I admit, it took me longer than I expected. By this time Jamie solved the problem by trial and error anyway — and as proof he had an install disk which he knew worked. He may well have spent less time actually concentrating on the issue than I had; the build-burn-install phases of his process all ran as background activities.

In the event we needed to revise the software anyway. So the salesman had to download a new build at the last minute. Jamie stayed late the next day to talk him through the installation.

Beware the March of IDEs!

tag@wordaligned.org (Thomas Guest) — 2010-03-15

The March of IDEs

Visual Studio can be one of the programmer’s best friends, but over the years it has become increasingly pushy, domineering, and suffering from unsettling control issues. Should we just surrender to Visual Studio’s insistence on writing our code for us? Or is Visual Studio sapping our programming intelligence rather than augmenting it?

— Charles Petzold, Does Visual Studio Rot the Mind?

March the 15th is a good day to revisit a talk Charles Petzold gave to at the NYC .NET Developer’s Group some four and half years ago. The speaker is probably best known as the author of Programming Windows, now in its fifth edition, and during his talk he confesses to a love/hate relationship with the software most people use for Windows programming — Microsoft Visual Studio (VS).

If you haven’t read the talk, read it now; and if you have, give it another look. Charles Petzold frets about the addictive nature of VS: if you become hooked on intellisense will you become dependent and mentally flabby? And what about the code VS generates in directories which it chooses?

Beware! Your IDE is taking over: you’ll end up working for it.

The story has a happy ending. Charles Petzold finds an antidote, working on programs to solve a series of maths puzzles set by New Scientist.

I decided to use plain old ANSI C, and to edit the source code in Notepad — which has no IntelliSense and no sense of any other kind — and to compile on the command line using both the Microsoft C compiler and the Gnu C compiler.

Me and my IDE

I rarely use Visual Studio these days, mainly because I’m primarily developing on Unix platforms. I have used VS in the past, though: but I still turned to Emacs to edit files. For debugging, I’ll admit VS is peerless. VS project files aren’t portable. It took someone far more expert than me a considerable amount of time to create a cross-platform build system capable of keeping everyone happy. Similarly, a few years ago I spent a short while doing Java development on Linux. Again, I tended to fall back on Emacs for editing, while using Eclipse to enforce style rules, tidy imports, debug, that kind of thing. I would have used Eclipse more but it kept on crashing. When I first started developing on a Mac I tried out XCode. It opened far too many windows and GDB didn’t seem to want to play with it. I abandoned it.

I suppose I do use Emacs as an IDE for code development, and for everything else, but it’s set up the way I want and it never tries to smooth over the details of what it’s up to. I frequently drop into the shell (even if it’s a shell running within Emacs).

My biggest problem with the traditional IDE is the view it imposes on a software project. The IDE makes you feel like you’re an airplane pilot sitting in front of a bank of controls, steering great swathes of code on a demanding course. The I in IDE emphasises integration; it’s in danger of creating Interdependencies, of coupling everything. I prefer something more focused.

Learning to Say “Hello, World”

It took me a while to reach this view. Charles Petzold’s epiphany is almost identical to one I had myself, many years ago.

Towards the end of last year, O’Reilly books posed the question: What 97 things should every programmer programmer know? In answer, I wrote about the moment I decided to shut down my IDE and get back to basics.

You can find the story, Learn to Say “Hello, World” on the wiki which was used for developing the book. Alternatively, the submission was accepted for publication, so you can buy the book itself.

The Ides of March

This [silver denarius] was struck in honour of Marcus Junius Brutus, one of the assassins of Julius Caesar. The reverse shows the cap of liberty given to freed slaves flanked by two daggers. This indicates Brutus’ intention of freeing Rome from Caesar’s imperial ambitions and the murder weapons employed to do so. Below is the day of the deed; EID.MAR, the ides of March.

— From the British Museum collection

Credits

My thanks to Kevlin Henney for editing my contribution to 97 Things Every Programmer Should Know, and indeed to everyone at O’Reilly involved with putting the book together.

I wish I could claim the title of this blog post was my own invention. I’m also struggling to remember where I first heard it. I think it might have been Matt Bowers, who also invented build ASBOs. Anyone?

Pi seconds is a nanocentury

tag@wordaligned.org (Thomas Guest) — 2010-03-14

π seconds is a nanocentury

— Jon Bentley, quoting Tom Duff, Programming Pearls

No, this isn’t a mysterious and fundamental connection between circles and the solar system. Actually, it’s incorrect:

nanocentury ~3.15576 seconds
ratio of a circle’s circumference to its diameter ~3.14159

Rather, Tom Duff’s rule of thumb is a useful mnemonic. One year is roundabout 3.14×10⁷ seconds. The accuracy of this figure is more than good enough for back of an envelope calculations. (Such calculations would be easier if we adopted a decimal time system — 100 seconds in a minute, 100 minutes in an hour, say — but time is one of the few currencies with internationally agreed denominations. I can’t see it changing, and 100 days in a year doesn’t make sense anyway.)

Bike charts by Google

tag@wordaligned.org (Thomas Guest) — 2010-02-18

I’ve liked the Google chart API ever since I first discovered it. Pack a text definition of an image into a URL http://chart.apis.google.com/chart?YOUR-IMAGE-HERE and you’ll be served up a freshly cooked PNG. It’s free. There’s not even a watermark.

http://chart.apis.google.com/chart?  # A chart, please
    &chs=320x160                     # sized 320x160 pixels
    &cht=gom                         # of type swingometer
    &chd=t:70                        # with 70% swing
    &chl=Nice!                       # labeled "Nice!"

Gone are the days when the documentation fitted on a single web-page. The API has fattened up and filled out. Every time I visit something new has been added: mathematical formulae written in TeX; a playground where you can sketch a chart directly; a validation option which tells you where you went wrong — much more helpful than a bare 404.

New to me: dynamic icons, which let you create “a variety of interesting callouts, pins, or bubbles that mix text and images”.

Mercurial manxman Mark Cavendish won an incredible 6 stages of last year’s Tour. Here he is, becoming the first Briton ever to win the final showdown on the Champs-Élysées, and winning it by an immense margin. For me, it was a bitter-sweet moment: that sprint should have put Cav in the green jersey, but he’d thrown away his chance in the points competition earlier in the race with an act of petulance which I still struggle to understand.

The Champs-Élysées may have a cobbled surface but it’s level and straight — definitely one for the sprinters. How about something twisted and mountainous? This second tableau recreates Fabian Cancellara’s dare-devil descent during stage 7 of last year’s tour. Defending the maillot jaune, Cancellara got dropped by the peleton following a wheel change. Watch him weave between team cars and camera bikes at top speed to regain his place. Awesome!

Now for a real classic — when Stephen Roche dug deep during an epic mountain stage in the 1987 Tour. Pedro Delgado, wearing yellow, had built a substantial lead over his rival on the climb up La Plagne. Yet somehow Roche clawed his way back into contention, appearing at the finish line just 5 seconds down on Delgado. He surprised everyone. He collapsed, exhausted, and had to be given oxygen, but he’d done enough. Roche went on to win the Tour. Formidable!

When you comment on a comment

tag@wordaligned.org (Thomas Guest) — 2010-02-10

@ianbicking these days, I very rarely bother reading anything where I cannot comment. — @drjtwit

You’ll notice there are no comments here. I hate discussing things via blog comments. If you’d like to talk, drop me a line. If you’d like to discuss things in public, post on your blog.

— Coda Hale

When you leave a comment on a comment, how often do you wonder what your rights are? Not too often, I’d guess. Over the years, it has become an accepted fact that content contributed to a website simply belongs to that website. If the website, or blog for today’s web, goes away then all of your contributions disappear along with it. A real world analogy would be sending in letters or artwork to a magazine. There’s usually that disclaimer which says the publication can do whatever with your submission. And, of course, they can’t return anything to you. It belongs to the magazine now.

— Daniel Ha, A commenter’s rights

In a recent blog post Dan Twining writes about blog comments and asks what I think of Disqus, the commenting service used here at Word Aligned. The question comes at an interesting time.

Unlike Blogger, Wordpress, Typepad etc. Disqus isn’t a blogging platform. Disqus do comments, and their central idea is integration. You don’t need yet another online id to leave a disqus comment. Sign in using your OpenID or Yahoo! account, for example. You can have your comments tweeted or posted on Facebook. Disqus works with whatever blogging system you use and it works across different systems: if a blog uses disqus and you post a comment on that blog, then that comment remains yours — the blog owner can’t edit it, and other readers can click through to see comments you’ve posted on other sites. Well, other comments posted using disqus that is. Clearly these connections extend as more sites adopt disqus, and this seems to be happening.
I used to use Haloscan for comments. I switched to Disqus about this time last year. I had no particular complaints with Haloscan; installation was simple, I didn’t get any spam comments, and the service proved reliable enough. It just seemed Haloscan wasn’t going anywhere. As it turns out, Haloscan will soon be gone. They’re shutting down the service this week.
It so happens Dan’s question comes when the action on this site is happening in the comments section. Which makes me think.

Back to Daniel Ha, the Disqus CEO, who has clearly thought harder about comments than I ever will. Towards the top of this note is a quote from his article “A Commenter’s Rights”. Daniel Ha goes on to point out that times have changed, and that online publishers are able to involve their readers and include their input in more sophisticated ways. It’s better for both commenters and publishers, he suggests, if commenters retain rights over their original material.

So what are a commenter’s rights? I’m going to make an initial attempt to materialize what some rights should be.

The ability to edit and remove their comments

Access to all of their comments, even if it has been deleted on a blog

The right to use their own comments as blog posts. After all, a commenter is just a publisher not writing on his own website.

A life for the comment beyond a single blog. I want to take my comments with me, even if the blog shuts down.

This may seem threatening to the publisher, but it really isn’t. A commenter should have rights to what they post, but bloggers should still have control over content that appear on their blogs. Bloggers should still control:

Whether or not someone is allowed to comment on his blog

The deletion of a comment

The modification of a comment, as long as the original copy is still accessible and the edit is transparent
— Daniel Ha, A commenter’s rights

Why bother with site-hosted comments at all? If people want to comment they can do so on specially designed community sites like Proggit or Hacker News. This is the internet: we go where we please, we find what we like.

Well, I guess I included comments on this site because that’s what other blogs did, and because I thought it was a way to engage readers and persuade them to return. The truth is, most readers arrive here via proggit; if I did away with comments here I might get more comments on reddit, and consequently more visits.

Look again at Daniel Ha’s words

When you leave a comment on a comment …

I’m guessing this is a typo, and that he meant “When you leave a comment on a website …”. If so, it’s an interesting slip. Modern comment systems are designed for comments on comments as much as for comments on the original article. Why bother with the original if the comments are more interesting? Jump straight into the discussion!

[…] It’s not that I don’t like sites with comments on, but when you read a site with comments it automatically puts you, the reader, in a defensive mode where you’re saying, “what’s good in this comment thread? What can I skim?”

These are John Gruber’s words but you won’t find them on his Daring Fireball website (the quotation has been transcribed by Shawn Blanc from an interview), and you won’t find comments there either. Have a look at an article on Daring Fireball. Here’s a recent one about Adobe Flash. Now try to imagine how the article would look with comments.

I’ve exported any Haloscan comments left on this site and imported them into Disqus using the disqus developer API. My thanks to Roberto Alsina for his helpful pointers on how to do this. Links to comments will have broken, but everything else should be fine. I’m sticking with comments and I’m sticking with Disqus, which gets better all the time. Please let me know if you spot any problems.

I’ll shut up now.

Power programming

tag@wordaligned.org (Thomas Guest) — 2010-01-26

Powerful or dangerous?

Recently I wrote about one of the Google Code Jam challenges, where, perhaps surprisingly, the best answer — the most elegant and obviously correct answer, requiring the fewest lines of code, with virtually zero space overhead, and running the quickest — the very best answer was coded in C++.

Why should this be surprising? C++ is a powerful language.

In my experience there is almost no limit to the damage that a sufficiently ingenious fool can do with C++. But there is also almost no limit to the degree of complexity that a skillful library designer can hide behind a simple, safe, and elegant C++ interface.

— Greg Colvin, “In the Spirit of C”

Yes. And yes! But in this article I wanted to discuss something C++ can’t do. Let’s start with another challenge from the same round of the 2009 Google Code Jam.

Decision trees

Decision trees — in particular, a type called classification trees — are data structures that are used to classify items into categories using features of those items. For example, each animal is either “cute” or not. For any given animal, we can decide whether it is cute by looking at the animal’s features and using the following decision tree.
(0.2 furry
  (0.81 fast
    (0.3)
    (0.2)
  )
  (0.1 fishy
    (0.3 freshwater
      (0.01)
      (0.01)
    )
    (0.1)
  )
)
— Decision Trees, Google Code Jam 2009

The challenge goes on to describe the structure more formally, then steps through an example calculation. What is the probability, p, that a beaver is cute?

For example, a beaver is an animal that has two features: furry and freshwater. We start at the root with p equal to 1. We multiply p by 0.2, the weight of the root and move into the first sub-tree because the beaver has the furry feature. There, we multiply p by 0.81, which makes p equal to 0.162. From there we move further down into the second sub-tree because the beaver does not have the fast feature. Finally, we multiply p by 0.2 and end up with 0.0324 — the probability that the beaver is cute.

The challenge itself involves processing input comprising a number of test cases. Each test case consists of a decision tree followed by a number of animals. A solution should parse the input and output the calculated cuteness probabilities.

Cuteness calculator

def cuteness(decision_tree, features):
    """Return the probability an animal is cute.
    
    - decision_tree, the decision tree
    - features, the animal's features,
    """
    p = 1.0
    dt = decision_tree
    has_feature = features.__contains__
    while dt:
        weight, *dt = dt
        p *= weight
        if dt:
            feat, lt, rt = dt
            dt = lt if has_feature(feat) else rt
    return p

Calculating an animal’s cuteness given a decision tree and the animal’s features isn’t hard. In Python we don’t need to code up a specialised decision tree class — a nested tuple does just fine. The cuteness() function shown above descends the decision tree, switching left or right according to each feature’s presence or absence. The efficiency of this algorithm is proportional to the depth of the tree multiplied by the length of the feature list; as far as the code jam challenge goes, it’s not a concern.

>>> decision_tree = (
...     0.2, 'furry',
...         (0.81, 'fast',
...             (0.3,),
...             (0.2,),
...         ),
...         (0.1, 'fishy',
...             (0.3, 'freshwater',
...                  (0.01,),
...                  (0.01,),
...             ),
...             (0.1,),
...         ),
...     )
>>> beaver = ('furry', 'freshwater')
>>> cuteness(decision_tree, beaver)
0.032400000000000005

No, the real problem here is how to parse the input data to create the decision trees and feature sets. As you can see, though, the textual specification of a decision tree closely resembles a Python representation of that decision tree. Just add punctuation.

Specification	Python
(0.2 furry (0.81 fast (0.3) (0.2) ) (0.1 fishy (0.3 freshwater (0.01) (0.01) ) (0.1) ) )	(0.2, 'furry', (0.81, 'fast', (0.3,), (0.2,), ), (0.1, 'fishy', (0.3, 'freshwater', (0.01,), (0.01,), ), (0.1,), ), )

Specification

Python

(0.2 furry
  (0.81 fast
    (0.3)
    (0.2)
  )
  (0.1 fishy
    (0.3 freshwater
      (0.01)
      (0.01)
    )
    (0.1)
  )
)

(0.2, 'furry',
  (0.81, 'fast',
    (0.3,),
    (0.2,),
  ),
  (0.1, 'fishy',
    (0.3, 'freshwater',
      (0.01,),
      (0.01,),
      ),
      (0.1,),
  ),
)

Rather than parse the decision tree definition by hand, why not tweak it so that it is a valid Python nested tuple? Then we can just let the Python interpreter eval the tuple and use it directly.

Eval

A program’s ability to read and execute source code at run-time is one of the things which makes dynamic languages dynamic. You can’t do it in C and C++ — no, sneaking instructions past the end of a buffer doesn’t count. Should you do it in Python? Well, it won’t hurt to give it a try.

spec = '''\
(0.2 furry
  (0.81 fast
    (0.3)
    (0.2)
  )
  (0.1 fishy
    (0.3 freshwater
      (0.01)
      (0.01)
    )
    (0.1)
  )
)
'''

tuple_rep = re.sub(r'([\.\d]+|\))', r'\1,', spec)
tuple_rep = re.sub(r'([a-z]+)', r'"\1",', tuple_rep)
decision_tree = eval(tuple_rep)[0]

Here, we start with the input specification of the decision tree (imagine this has been read directly from standard input). The first regex substitution inserts commas after numbers, and right parentheses. The second substitution quotes and inserts a comma after feature strings. This turns the decision tree’s specification into a textual representation of a nested Python tuple. We then eval that tuple and assign the result to decision_tree — a Python decision tree we can go on and use in the rest of our program. And that’s the code jam challenge cracked, pretty much.

>>> from pprint import pprint
>>> pprint(decision_tree)
(0.2,
 'furry',
 (0.81, 'fast', (0.3,), (0.2,)),
 (0.1, 'fishy', (0.3, 'freshwater', (0.01,), (0.01,)), (0.1,)))

(Minor wrinkle: you’ll have spotted the final decision tree is the first element of the evaluated tuple. That’s because the regex substitution puts a trailing comma after the right parenthesis which closes the decision tree specification, which turns tuple_rep into a one-tuple. The single element contained in this one-tuple is what we need.)

Dynamic or hacky?

As you can see, it doesn’t take much code to pull the decision tree in ready for use. Python allows us to convert between text and code and to execute code within the current environment: you just need to keep a clear head and remember where you are. Regular expressions may not have the first class language support they enjoy in Perl and Ruby, but they are well supported, and the raw string syntax makes them more readable.

Certainly, this code snippet is easier to put together than a full blown parser, but I think it will take more than this to convince a C++ programmer that Python is a powerful language, rather than a dangerous tool for ingenious fools. It fails to convince me. I can’t remember ever using eval or exec in production code, where keeping a separation between layers is more important than speed of coding.

Jam to golf

That said, Python is a fine language for scripting, and speed of coding is what matters in this particular challenge. Just for fun, what if there were a prize for brevity? Then of course Perl would win!

Code Jam golf, by gnibbler, Stack Overflow

say("Case #$_:"),
$_=eval"''".'.<>'x<>,
s:[a-z]+:*(/ $&\\s/?:g,s/\)\s*\(/):/g,
eval"\$_=<>;say$_;"x<>for 1..<>

Note that this does more than simply parse a decision tree — it’s a complete solution to the code jam challenge, reading trees, features, calculating cutenesses, and producing output in the required format. Sadly that’s all I can say about it because the details of its operation are beyond me.

Code vs data

Using Python to dynamically execute code may not generally be needed or welcomed in Python production code, and over-reliance on the same trick risks reinforcing Perl’s “write only” reputation, but Python and Perl aren’t the only contenders. The equivalence of code and data marks Lisp’s apotheosis. Take a look at a Lisp solution to the challenge. This one is coded up in Arc.

(def r () (read))
(for i 1 (r)
  (prn "Case #" i ":")
  (r)
  (= z (r))
  (repeat (r)
    (r)
    (loop (= g (n-of (r) (r))
             c z
             p 1)
       c
       (= p (* (pop c) p)
          c (if (pos (pop c) g)
                (c 0)
                (cadr c))))
    (prn p)))

Which challenge does this solve?

I meant the code golf challenge, of solving the decision tree problem using the fewest keystrokes. At 154 characters this Arc program is nearly half as long again as the winning Perl entry, but it’s hardly flabby. What really impresses me, though, is that the code is (almost) as readable as it is succinct. It’s elegant code. The only real scars left by the battle for brevity are the one character variable names. Here’s the same code with improved variable names and some comments added. It’s the (read) calls which evaluate expressions on standard input. The (for ...) and (repeat ...) expressions operate as you might expect. The third looping construct, (loop ...) initialises, tests and proceeds, much like a C for loop.

(for i 1 (read)               ; Read N, # test cases, and loop
  (prn "Case #" i ":")
  
  (read)                      ; Skip L, # lines taken by decision tree
  (= dtree (read))            ; and read the tree in directly
  
  (repeat (read)              ; Repeat over A, # animals
    (read)                    ; Skip animal name
    ; Read in the animal's features and walk down the 
    ; decision tree calculating p, the cuteness probability
    (loop (= features (n-of (read) (read)) 
             dt dtree
             p 1)
       dt
       (= p (* (pop dt) p)
          dt (if (pos (pop dt) features)
                (car dt)
                (cadr dt))))
    (prn p)))

You could argue the elegance of this solution is due to the fact the input comprises a sequence of tokens and S-expressions. If commas had been used to separate input elements and the text fields had been enclosed in quotes, then maybe a Python solution would have been equally clean. Or if the input had been in XML, then we’d be looking to a library rather than eval for parsing the input.

It’s a fair point, but the equivalence of code and data counts as Lisp’s biggest idea. Where Python’s eval is workable but rarely needed, Lisp’s (read) is fundamental.

Powerful language vs power user?

So, the most elegant answer to the code jam decision tree challenge would also be the quickest to write, and it would be written in Lisp. Did code jam champion, ACRush, submit a Lisp solution?

Absolutely not!

Another fundamental thing about Lisp is that it’s straightforward to parse. A C++ expert can knock up an input parser for decision trees and features to order. ACRush brushed this round aside with a perfect score, taking just 45 minutes to code up working C++ solutions to this question and two others. I’ve reproduced his solution to the decision tree challenge at the end of this article. It’s plain and direct. Given the time constraints, I think it exhibits astonishing fluency — the work of someone who can think in C++.

In this article we’ve encountered four programming languages:

Python
Perl
Lisp
C++

These languages are very different but they share features too. They are all mature, popular and well-supported^[1]. Each is a powerful general purpose programming language. But ultimately, the power of the programmer is what matters.

Appendix A: First impressions of Arc

Here’s another revision of the Arc solution, this time decomposed into subfunctions. I found no complete formal documentation of Arc. You’ll have to read the source and follow the forum, and to actually run any code you’ll have to download a an old version of MzScheme. The official line is: by all means have a play, but expect things to change. That said, the language looks delightful, practical, and quite onion free. The tutorial made me smile. Recommended reading.

; The input is a sequence of valid Arc expressions.
; Create some read aliases to execute these.
(= skip read
   decision-tree read
   n-features read 
   n-tests read
   n-animals read)

(def animal-features ()
     ; Get an animal's features
     (skip) ; animal name
     (n-of (n-features) (read)))

(def cuteness (dtree features)
     ; Calculate cuteness from a decision tree and feature set
     (= dt dtree
        p 1.0)
     (while dt
          (= p (* (pop dt) p)
             dt (if (pos (pop dt) features)
                (car dt)
                (cadr dt))))
     p)

; Loop through the tests, printing results
(for i 1 (n-tests)
     (prn "Case #" i ":")
     (skip) ; # lines the tree specification takes
     (= dtree (decision-tree))
     (repeat 
         (n-animals)
         (prn (cuteness dtree (animal-features)))))

Appendix B: C++ solution

Here’s champion ACRush’s C++ solution. I’ve removed some general purpose macros from the top of the file. You can download the original here.

#include <set>
#include <string>
#include <vector>
#include <sstream>
#include <cstdio>
#include <cstdlib>

using namespace std;

vector<string> A;
vector<int> P;
set<string> M;

#define SIZE(X) ((int)(X.size()))

double solve(int H,int T)
{
    H++;T--;
    double p=atof(A[H].c_str());
    if (H==T) return p;
    if (M.find(A[H+1])!=M.end())
        return p*solve(H+2,P[H+2]);
    else
        return p*solve(P[T],T);
}
int main()
{
    freopen("A-large.in","r",stdin);freopen("A-large.out","w",stdout);
    int testcase;
    scanf("%d",&testcase);
    for (int caseId=1;caseId<=testcase;caseId++)
    {
        int nline;
        scanf("%d",&nline);
        A.clear();
        char str[1024];
        gets(str);
        for (int i=0;i<nline;i++)
        {
            gets(str);
            string s="";
            for (int k=0;str[k];k++)
                if (str[k]=='(' || str[k]==')')
                    s+=" "+string(1,str[k])+" ";
                else
                    s+=str[k];
            istringstream sin(s);
            for (;sin>>s;A.push_back(s));
        }
        P.resize(SIZE(A),-1);
        vector<int> stack;
        for (int i=0;i<SIZE(A);i++)
            if (A[i]=="(")
                stack.push_back(i);
            else if (A[i]==")")
            {
                int p=stack[SIZE(stack)-1];
                P[i]=p;
                P[p]=i;
                stack.pop_back();
            }
        int cnt;
        printf("Case #%d:\n",caseId);
        for (scanf("%d",&cnt);cnt>0;cnt--)
        {
            scanf("%s",str);
            M.clear();
            int length;
            for (scanf("%d",&length);length>0;length--)
            {
                scanf("%s",str);
                M.insert(str);
            }
            double r=solve(0,SIZE(A)-1);
            printf("%.12lf\n",r);
        }
    }
    return 0;
}

Appendix C: A Python Solution

import re
from itertools import islice

def cuteness(decision_tree, features):
    p = decision_tree[0]
    if len(decision_tree) > 1:
        _, feat, lt, rt = decision_tree
        p *= cuteness(lt if feat in features else rt, features)
    return p

def read_decision_tree(spec):
    tuple_rep = re.sub(r'([\.\d]+|\))', r'\1,', spec)
    tuple_rep = re.sub(r'([a-z]+)', r'"\1",', tuple_rep)
    return eval(tuple_rep)[0]

def take_lines(lines, n):
    return ''.join(islice(lines, n))

def main(fp):
    lines = iter(fp)
    n_tests = int(next(lines))
    for tc in range(1, n_tests + 1):
        print("Case #%d:" % tc)
        tree_spec = take_lines(lines, int(next(lines)))
        dtree = read_decision_tree(tree_spec)
        n_animals = int(next(lines))
        for line in islice(lines, n_animals):
            features = set(line.split()[2:])
            print(cuteness(dtree, features))

import sys
main(sys.stdin)

Notes

[1] (Arc may not be mature, popular or well-supported; but Lisp certainly is.)

Python, Surprise me!

tag@wordaligned.org (Thomas Guest) — 2009-12-15

A Simple Function

Here’s a simple function which converts the third item of a list into an integer and returns it, returning -1 if the list has fewer than three entries or if the third entry fails to convert.

def third_int(xs):
    '''Convert the third item of xs into an int and return it.
        
    Returns -1 on failure.
    '''    
    try:
        return int(xs[2])
    except IndexError, ValueError:
        return -1

Unfortunately this simple function is simply wrong. Evidently some exceptions aren’t being caught.

>>> third_int([1, 2, 3, 4])
3
>>> third_int([1])
-1
>>> third_int(('1', '2', '3', '4',))
3
>>> third_int(['one', 'two', 'three', 'four'])
Traceback (most recent call last):
    ....
ValueError: invalid literal for int() with base 10: 'three'

How ever did a ValueError sneak past the except clause?

The Real Surprise

There’s nothing mysterious or surprising going on here, but I’ll delay answering this question for a moment. For me, the real surprise about Python is that, generally, I get it right first time. Python similarly caught Eric S. Raymond by surprise. His first surprise was that it took him just 20 minutes to get used to syntactically significant whitespace. And just 100 minutes later …

My second [surprise] came a couple of hours into the project, when I noticed (allowing for pauses needed to look up new features in Programming Python) I was generating working code nearly as fast as I could type. When I realized this, I was quite startled. An important measure of effort in coding is the frequency with which you write something that doesn’t actually match your mental representation of the problem, and have to backtrack on realizing that what you just typed won’t actually tell the language to do what you’re thinking. An important measure of good language design is how rapidly the percentage of missteps of this kind falls as you gain experience with the language.

— Eric S. Raymond, Why Python?

I certainly don’t generate working code as fast as I can type, and I’m not even a particularly quick typist, but I rarely make syntactic errors when writing Python — and I don’t often need to consult the documentation on such matters. As Chuck Allison memorably puts it: “the syntax is so clean it squeaks”.

Parentheses Required(?)

There are some oddities and gotchas though. I don’t object to the explicit self in methods, but I do sometimes forget to write it — especially if I’ve just switched over from C++.

A side-effect of the whitespace thing is that you can’t just wrap a long line. The line ending needs to be escaped.

if 1900 < year < 2100 and 1 <= month <= 12 \
    and 1 <= day <= 31 and 0 <= hour < 24 \
    and 0 <= minute < 60 and 0 <= second < 60: # Looks like a valid date
    return 1

Alternatively, parenthesize.

if (1900 < year < 2100 and 1 <= month <= 12
    and 1 <= day <= 31 and 0 <= hour < 24
    and 0 <= minute < 60 and 0 <= second < 60): # Looks like a valid date
    return 1

In the above, the parentheses aren’t required to group terms, but instead serve to implicitly continue the line of code past a couple of newline characters.

Parentheses serve more than one role in Python’s syntax. As in all C-family languages, they can group expressions. They also get involved building tuples, (1, 2, 3) or ('red', 0xff0000) for example. Beware the special case: a one-tuple needs a trailing comma, ("singleton",). This isn’t something I forget or accidentally omit, but it can make things fiddly. Here’s a tuple-tised tree, where we represent a tree as a tuple whose first element is a node value, and any subsequent elements are sub-trees. Careful with those commas!

tree = (2, (7, (2,), (6, (5,), (11,))), (5, (9, (4,))))

Actually, tuples are just comma-separated lists of expressions — no parentheses required — so we might equally well have written.

tree = 2, (7, (2,), (6, (5,), (11,))), (5, (9, (4,)))

Here, the superfluous outermost parentheses have been omitted; the inner ones are still required for grouping.

How about we always append a trailing comma to our tuples so the one-tuple no longer looks different?

tree = 2, (7, (2,), (6, (5,), (11,))), (5, (9, (4,))),

That’s allowed and fine. Unless we need an empty tuple, that is, in which case the parentheses are required. And a comma would be wrong.

>>> ()
()
>>> (),
((),)
>>> ,
   ....
SyntaxError: invalid syntax
>>> (,)
   ....
SyntaxError: invalid syntax
>>> tuple()
()

Python 3 introduces a nice new syntax for set literals, reusing the braces which traditionally enclose dicts.

>>> ls = { 1, 11, 21, 1211, 111221, 312211 }

Again, beware the edge case: {} is an empty dict, not an empty set.

>>> zs = {}
>>> type(zs)
<class 'dict'>
>>> zs = set()
>>> type(zs)
<class 'set'>

Python 3 allows non-ascii characters in identifiers, but not any old character, so we cannot get away with

>>> ∅ = set()
      ^
SyntaxError: invalid character in identifier

Parentheses are used for function calls too, and also for generator expressions. Here’s a lazy list of squares of numbers less than a million.

>>> sqs = (x * x for x in range(1000000))

Here’s the sum of these numbers.

>>> sum((x * x for x in range(1000000)))
333332833333500000

Actually, we can omit the generator-expression parentheses in the sum. The function call parentheses magically turn the enclosed x * x for x in range(1000000) into a generator expression. As usual, Python does what we want.

>>> sum(x * x for x in range(1000000))
333332833333500000

Serious about Syntax

If you’ve read this far you may well be thinking: “So what?” I haven’t shown any gotchas, merely a few quirks and corner cases. As already mentioned, the real surprise is that Python fails to surprise. Part of this, as I hope I’ve shown here, can be attributed to the interpreter, which positively invites you to experiment; but mainly Python’s clean and transparent design takes the credit. Repeating Eric S. Raymond: you don’t have to “actually tell the language to do what you’re thinking”.

Since I first started using Python the syntax has grown considerably, yet the extensions and additions seem almost as if they’d been planned from the start^[1]. Generator expressions complement list comprehensions. The yield statement fits nicely with iteration.

Even more remarkably, Python 3 has chosen to break backwards compatibility, so it can undo those few early choices which now seem mistakes. Which brings us back to the broken function at the top of this article. Here it is again, docstring omitted for brevity.

def third_int(xs):
    try:
        return int(xs[2])
    except IndexError, ValueError:
        return -1

I really did write a function like this, and I really did get it wrong in just this way. The code is syntactically valid, but I should have written

def third_int(xs):
    try:
        return int(xs[2])
    except (IndexError, ValueError):
        return -1

The parentheses in the except clause are crucial. The formal syntax of this form of try statement is

try1_stmt ::=  "try" ":" suite
               ("except" [expression [("as" | ",") target]] ":" suite)+
               ["else" ":" suite]
               ["finally" ":" suite]

In the corrected version of third_int(), the parentheses group IndexError, ValueError into a single expression, a tuple, and the except clause matches any object with class (or base class) IndexError or ValueError. The broken version is very different, as becomes clear if we use the alternative "as" form.

def third_int(xs):
    try:
        return int(xs[2])
    except IndexError as ValueError:
        return -1

Here, the except clause will match an object with class or base class IndexError, and assigns that object to the target, which is called ValueError (and which shadows the “real” ValueError in the rest of the function definition). If int() raises a ValueError, it will not be matched.

Won’t Get Fooled Again

Oh, I get it, now. It is a bit subtle, but I won’t make that mistake again.

Wait, there’s more! In Python 3k, my broken implementation is properly broken — a syntax error.

Python 3.1
>>> def third_int(xs):
...     try:
...         return int(xs[2])
...     except IndexError, ValueError:
  File "<stdin>", line 4
    except IndexError, ValueError:
                     ^
SyntaxError: invalid syntax

The Python 3k syntax of this form of try statement reads.

try1_stmt ::=  "try" ":" suite
               ("except" [expression "as" target]] ":" suite)+
               ["else" ":" suite]
               ["finally" ":" suite]

You can’t use a comma to capture the target any more. It’s an advance and a simplification. Why am I not surprised?

[1]: With the possible exception of conditional expressions, that is.

Next permutation: When C++ gets it right

tag@wordaligned.org (Thomas Guest) — 2009-11-19

The Next Number Problem

Suppose you have a fixed list of digits chosen from the range 1..9. What numbers can you make with them? You’re allowed as many zeros as you want. Write the numbers in increasing order.

Exactly this puzzle came up in the recent Google Code Jam programming contest:

You are writing out a list of numbers. Your list contains all numbers with exactly D_i digits in its decimal representation which are equal to i, for each i between 1 and 9, inclusive. You are writing them out in ascending order.
For example, you might be writing every number with two ‘1’s and one ‘5’. Your list would begin 115, 151, 511, 1015, 1051.
Given N, the last number you wrote, compute what the next number in the list will be.

The competition has closed now, but if you’d like to give it a go sample input files can be found on the website, where you can also upload your results and have them checked.

Here’s a short section from a trial I ran on my computer. Input numbers are in the left-hand column: the corresponding output numbers are in the right-hand column.

50110812884911623516 → 50110812884911623561
82454322474161687049 → 82454322474161687094
82040229261723155710 → 82040229261723157015
43888989554234187388 → 43888989554234187838
76080994872481480636 → 76080994872481480663
31000989133449480678 → 31000989133449480687
20347716554681051891 → 20347716554681051918

Choice of Algorithm

Like many of the code jam challenges, you’ll need to write a program which runs fast enough; but choosing the right algorithm is more important than choosing the right language. Typically a high-level interpreted language like Python allows me to code and test a solution far more quickly than using a low-level language like C or C++.

In this particular case, though, like most successful candidates, I used C++. Here’s why.

Next_permutation transforms the range of elements [first, last) into the lexicographically next greater permutation of the elements. […] If such a permutation exists, next_permutation transforms [first, last) into that permutation and returns true. Otherwise it transforms [first, last) into the lexicographically smallest permutation and returns false.

Although the next number problem appears to be about numbers and lexicographical ordering appears to be about words, std::next_permutation is exactly what’s needed here.

Lexicographical Ordering

A dictionary provides the canonical example of lexicographical ordering. Words are built from characters, which can be alphabetically ordered A, B, C, … , so in the dictionary words which begin with A appear before words which begin with B, which themselves come in front of words beginning with C, etc. If two words start with the same letter, pop that letter from the head of the word and compare their tails, which puts AARDVARK before ANIMAL, and — applying this rule recursively — after AARDMAN. Imagine there’s an empty word marking position zero, before A, right at the front of the dictionary, and our recursive definition is complete.

Next permutation in action

Here’s a simple program which shows next_permutation() in action.

#include <algorithm>
#include <cstdio>

int main()
{
    char xs[] = "123";
    do
    {
        std::puts(xs);
    }
    while (std::next_permutation(xs, xs + sizeof(xs) - 1));
    return 0;
}

This program outputs lexicographically ordered permutations of 1, 2 and 3. When the main function returns, the array xs will have cycled round to hold the lexicographically smallest arrangement of its elements, which is "123". Note that we never convert the characters '1', '2', '3' into the numbers 1, 2, 3. The values of both sets of data types appear in the same order, so all works as expected.

If we tweak and rerun the same program with xs initialised to "AAADKRRV" we get rather more output.

AAADKRRV
AAADKRVR
AAADKVRR
...
AARDVARK
...
VRRKAADA
VRRKADAA
VRRKDAAA

The sequence doesn’t start by repeating "AAADKRRV" 6 times, once for every permutation of the 3 A’s. Only strictly increasing permutations are included. And although the repeated calls to next_permutation generate a series of permutations, the algorithm holds no state. Each function call works on its input range afresh.

This second run of the program yields 3360 lines of output, even though there are 8! = 40320 possible permutations of 8 characters. Each unique permutation corresponds to 3! × 2! = 12 actual permutations of the 8 characters (because there are 3 A’s and 2 R’s), and 40320 ÷ 12 is 3360.

Snail sort’s revenge

As you can see, next_permutation sorts an input range, one step at a time. When next_permutation eventually returns false, the range will be perfectly ordered. Hence we have snail_sort(), hailed by the SGI STL documentation as the worst known deterministic sorting algorithm.

template <class Iter> 
void snail_sort(Iter first, Iter last)
{
    while (next_permutation(first, last)) {}
}

Very witty, and evidence that code can be both elegant and inefficient.

In two important edge cases, though, snail_sort performs on a par with super-charged quicksort!

I snail sorted an array filled with 100000000 zeros in 0.502 seconds. Running quicksort on the same array took 5.504 seconds.
Starting with an array of the same size filled with the values 99999999, 99999998, 99999997, … 1, 0 snail sort’s 0.500 seconds trounced quicksort’s 4.08 seconds.

The Next Number, Solved

Here’s an outline solution to the next number problem. (I’ve glossed over the exact input and output file formats for clarity.) It reads numbers from standard input and writes next numbers to standard output. Next_permutation does the hard work, and there’s a bit of fiddling when we have to increase the number of digits by adding a zero.^[1]

#include <algorithm>
#include <iostream>

/*
 Given a string of digits, shift any leading '0's
 past the first non-zero digit and insert an extra zero.
 
 Examples:
  
 123 -> 1023
 008 -> 8000
 034 -> 3004
*/
void insert_a_zero(std::string & number)
{
    size_t nzeros = number.find_first_not_of('0');
    number = number.substr(nzeros);
    number.insert(1, nzeros + 1, '0');
}

/*
 Outline solution to the 2009 code jam Next Number problem.
 
 Given a string representing a decimal number, find the next
 number which can be formed from the same set of digits. Add
 another zero if necessary. Repeat for all such strings read
 from standard input.
*/
int main()
{
    std::string number;
    while (std::cin >> number)
    {
        if (!next_permutation(number.begin(), number.end()))
        {
            insert_a_zero(number);
        }
        std::cout << number << '\n';
    }
    return 0;
}

Implementation

Having used the C++ standard library to solve the puzzle, let’s take a look at how it works. Next permutation is a clever algorithm which shuffles a collection in place. My system implements it like this^[2].

template<typename Iter>
bool next_permutation(Iter first, Iter last)
{
    if (first == last)
        return false;
    Iter i = first;
    ++i;
    if (i == last)
        return false;
    i = last;
    --i;
        
    for(;;)
    {
        Iter ii = i;
        --i;
        if (*i < *ii)
        {
            Iter j = last;
            while (!(*i < *--j))
            {}
            std::iter_swap(i, j);
            std::reverse(ii, last);
            return true;
        }
        if (i == first)
        {
            std::reverse(first, last);
            return false;
        }
    }
}

We start with a range delimited by a pair of bi-directional iterators, [first, last). If the range contains one item or fewer, there can be no next permutation, so leave the range as is and return false. Otherwise, enter the for loop with an iterator i pointing at the final item in the range.

At each pass through the body of this for loop we decrement i by one, stepping towards the first item in the range. We are looking for one of two conditions:

the value pointed to by i is smaller than the one it pointed to previously
i reaches into the first item in the range

Put another way, we divide the range into a head and tail, where the tail is the longest possible decreasing tail of the range.

If this tail is the whole range (the second condition listed above) then the whole range is in reverse order, and we have the lexicographical maximum formed from its elements. Reversing the range returns it to its lexicographical minimum, and we can return false.

If this tail is not the whole range, then the final item in the head of the range, the item i points to, this item is smaller than at least one of the items in the tail of the range, and we can certainly generate a greater permutation by moving the item towards the end of the range. To find the next permutation, we reverse iterate from the end of the range until we find an item *j bigger than *i — that’s what the while loop does. Swapping the items pointed to by i and j ensures the head of the range is bigger than it was, and the tail of the range remains in reverse order. Finally, we reverse the tail of the range, leaving us with a permutation exactly one beyond the input permutation, and we return true.

What’s happening here?

It’s clear from this paper analysis that the algorithm is of linear complexity. Essentially, it walks up and down the tail of the list, comparing and swapping. But why does it work?

Let xs be the range (first, last). As described above, divide this range into prefix and suffix subranges, head and tail, where tail is the longest monotonically decreasing tail of the range.

If the head of the range is empty, then the range xs is clearly at its lexicographical maximum.

Otherwise, tail is a lexicographical maximum of the elements it contains, and xs is therefore the largest permutation which starts with the subrange head. What will the head of the next permutation be? We have to swap the final item in head with the smallest item of tail which exceeds it: the definition of tail guarantees at least one such item exists. Now we want to permute the new tail to be at a its lexicographical minimum, which is a matter of sorting it from low to high.

Since tail is in reverse order, finding the smallest item larger than head[-1] is a matter of walking back from the end of the range to find the first such items; and once we’ve swapped these items, tail remains in reverse order, so a simple reversed will sort it.

As an example consider finding the next permutation of:

8342666411

The longest monotonically decreasing tail is 666411, and the corresponding head is 8342.

8342 666411

666411 is, by definition, reverse-ordered, and cannot be increased by permuting its elements. To find the next permutation, we must increase the head; a matter of finding the smallest tail element larger than the head’s final 2.

8342 666411

Walking back from the end of tail, the first element greater than 2 is 4.

8342  666411

Swap the 2 and the 4

8344 666211

Since head has increased, we now have a greater permutation. To reduce to the next permutation, we reverse tail, putting it into increasing order.

8344 112666

Join the head and tail back together. The permutation one greater than 8342666411 is 8344112666.

Beautiful C++?

C++ has its detractors, who characterise it as subtle, complex, and dangerous; but sometimes it excels. Look once more at the C++ implementation of this algorithm.

template<typename Iter>
bool next_permutation(Iter first, Iter last)
{
    if (first == last)
        return false;
    Iter i = first;
    ++i;
    if (i == last)
        return false;
    i = last;
    --i;
    
    for(;;)
    {
        Iter ii = i;
        --i;
        if (*i < *ii)
        {
            Iter j = last;
            while (!(*i < *--j))
            {}
            std::iter_swap(i, j);
            std::reverse(ii, last);
            return true;
        }
        if (i == first)
        {
            std::reverse(first, last);
            return false;
        }
    }
}

With its special cases, boolean literals, multiple returns (4, count them!), disembodied and infinite loops, this code fails to exhibit conventional beauty. Yet it is beautiful. All the next permutation algorithm needs are iterators which can advance forwards or backwards, step by step. And that’s all this implementation uses.

I’m as excited as anyone by the mathematical rigour of functional programming, but sometimes computer science is about algorithms with virtually no space overhead, algorithms which loop rather than recurse. Sometimes it’s about shuffling, nudging and swapping — operations which map directly to the machine’s most primitive operations. In such cases, C++ gets it right.

Permutations in Python

For the code jam, though, as mentioned earlier, having a super-fast program rarely matters. More often, it’s about developing a fast enough program super-quickly.

I find Python a far quicker language for developing code than C++. (Indeed, sometimes when it’s obvious from the outset that a final program will need implementing in C++, I put together a working prototype using Python, which I then translate.) Could we solve the next number problem using code from the standard Python library?

At a first glance, itertools.permutations looks promising.

itertools.permutations(iterable, r=None)
Return successive r length permutations of elements in the iterable.
If r is not specified or is None, then r defaults to the length of the iterable and all possible full-length permutations are generated.
Permutations are emitted in lexicographic sort order. So, if the input iterable is sorted, the permutation tuples will be produced in sorted order.
Elements are treated as unique based on their position, not on their value. So if the input elements are unique, there will be no repeat values in each permutation.

However, this algorithm doesn’t care about the values of the items in the iterable, and the lexicographic sort order applies to the indices of these items. So although the ordering of the generated items is well-defined:

we get repeats, and
it’s not the ordering we want (in this case)

>>> from itertools import permutations
>>> concat = ''.join
>>> list(map(concat, permutations('AAA')))
['AAA', 'AAA', 'AAA', 'AAA', 'AAA', 'AAA']
>>> list(map(concat, permutations('231')))
['231', '213', '321', '312', '123', '132']

It is possible to code up next_permutation using nothing more than the standard itertools, but it isn’t advisable.

Snail permute

from itertools import permutations, groupby

def next_permutation(xs):
    """Calculate the next permutation of the sequence xs.
    
    Returns a pair (yn, xs'), where yn is a boolean and xs' is the 
    next permutation. If yn is True, xs' will be the lexicographic 
    next permutation of xs, otherwise xs' is the lexicographic 
    smallest permutation of xs.
    """
    xs = tuple(xs)
    if not xs:
        return False, xs
    else:
        ps = [p for p, gp in groupby(sorted(permutations(xs)))]
        np = len(ps)
        ix = ps.index(xs) + 1
        if ix == len(ps):
            return False, ps[0]
        else:
            return True, ps[ix]

As it happens, a solution based on this exhaustive search would score points in the code jam since it copes with the small input set. For the large input set its factorial complexity rules it out, and we’d need to implement the next permutation algorithm from scratch.

[1]: A more cunning solution avoids the special case by pushing the extra zero to head of the string before applying next_permutation, then popping it if it hasn’t been moved.

[2]: I’ve tweaked the layout and parameter names for use on this site.

Python on Ice

tag@wordaligned.org (Thomas Guest) — 2009-10-28

A moratorium on Python changes is probably a good thing—the last edition of my book nearly made my head explode. — @dabeaz

Python?

“Python?”

“Yes, Python. It’s a high-level language, we used it for the prototype. We can use it for parts of the system where performance isn’t critical. Connecting components together. The web server.”

“But what will we do when Python changes? It’s a developing language, right? How can we maintain our system.”

Not an issue, I explained. Python takes backwards compatibility very seriously. Besides, we choose which version of Python to deploy with, we choose when we migrate — maybe never. Look, you can download the source for every version of Python ever released. All you need is a C compiler. C is the porting layer, if you like, and C isn’t going anywhere in a hurry.

In all honesty, I expected more maintenance issues with the C++ parts of our product, where the language may not have changed in a decade but compilers are only just catching up with it; and in fact I didn’t have to argue for long to persuade senior management, not on this issue at least. They’d already seen how quickly I could get things up and running using Python. Even though the company had more experience with C, C++, Java, and even .Net, I convinced them Python had a role on the server-based system we were developing.

Nonetheless, I didn’t think it the right time to mention Python 3. Why confuse things?

Twisted 8.1 on Python 2.5

I won’t go into detail about the product. Data flowed through it, redirected dynamically using tees and filters, and robots were attached to the resulting streams to monitor them. A web UI presented controls and a view of the system. We used C and C++ for managing the bulk of the flow. The robots we coded in both Python and C++. We connected and coordinated everything using Twisted, a Python networking engine. Our initial deployment used Python 2.5 and Twisted 8.1. We’ve since upgraded to Python 2.6 and Twisted 8.2.

Python 3 on Word Aligned

At work there was no question of using Python 3 even though it became available when we started development. Twisted hadn’t been released against Python 3 (it still hasn’t) and even if it had been, we wouldn’t have trusted it immediately. Here at Word Aligned, though, I switched to Python 3 pretty much as soon as it was officially released. Since the start of 2009, any Python code published on this site has been written in Python 3.

Since then I’ve come to question my decision. I want people to visit my site and I want them to stay long enough to read any code here. Python is perfect because it’s readable and accessible. Anyone who’s ever written a program, whatever the language, can understand Python. But many times I’ve felt the need to explain my Python 3 code, not to Java, C#, C++ and C users, not even to Perl and Ruby users, but to Python users!

Note that in Python 3 … whereas in Python 2 … available in Python 3.1 only … you’d need to write … from __future__ import print_function

I wouldn’t have felt the need to say any of this if I’d stuck with Python 2.

Python 3 absent from Europython

At Europython 2009 I was struck by the absence of Python 3 from the agenda. None of the sessions covered Python 3, used Python 3, or even mentioned Python 3 (unless you count David Jones’ talk on Loving Old Versions of Python). The only Python 3 code I saw appeared on the conference bag; a lightly obfuscated script which printed out the conference destination. Note that print is being used in a way which works with both 2.x and 3.x — that is, with parentheses and taking a single parameter. Very few systems resolve /usr/bin/env python as Python 3, though^[1], which is lucky since even this simple function raises an exception under Python 3 (and transforming the code using 2to3 makes it worse).

This Python 3 silence was at last broken during the question and answer session which followed the final keynote on the final day of the conference. An audibly nervous member of the audience asks Python Software Foundation supremo Steve Holden a question:

Audience member: A source of confusion is the Python 2 Python 3 thing. How are you going about getting people to move from Python 2 to Python 3?

Steve Holden: I’m not trying to get people to move to Python 3. [Audience applauds].

Steve Holden went on to round out this answer, saying that 2.6 is the recommended production version of Python. Anyone who took Python 3.0 into production, he said, would have been “kicked in the teeth by the fact that the IO subsystem performed execrably slowly, it was really dreadful” — a fact the 3.0 release notes failed to mention, but which has been fixed in Python 3.1. For teaching purposes, or for greenfield development which doesn’t need to reuse other people’s code, by all means try Python 3, he said. Python 3 is the future of Python. There’s a migration strategy in place.

And what about the overhead on the core Python development team, who now have two versions to maintain? Well, Steve Holden said, there are tools to automate patching and merging, but yes, there’s an overhead.

(To hear the question and full response, there’s a video at blip.tv. Fast forward to 52 minutes and 40 seconds.)

Python 3 Literature

How have book authors reacted to Python 3? Mark Pilgrim has dived in with aplomb. His introductory book, Dive into Python 3, uses Python 3 as Python 3 was intended. For example, you won’t find % characters used in string formatting; {up to date braces are used exclusively}. It’s an engaging, painstakingly-written book, and (bonus!) the online version is an object lesson in how to craft HTML.

David Beazley attacks the problem in a different way, but then his subject is different. His comprehensive Python Essential Reference aims to cover the core language and its standard library in its entirety: think of it as the reference any serious Python programmer would like to have within reach. David Beazley’s approach is to concentrate on the common subset of Python 2 and 3, omitting features of 2 which aren’t in 3 and avoiding features of 3 which haven’t been backported to 2. His book succeeds but it does raise some awkward questions. Will Pythonistas find themselves maintaining parallel code-bases, and end up twisting their code until it fits into the intersection of two flavours of the language?

Or will they simply avoid Python 3?

David Beazley eventually covers new Python 3 features in an appendix, by which time the strain has started to show:

Finally, even though Python 3.0 is described as the latest and greatest, it suffers from numerous performance and behavioral problems […] in the opinion of this author, Python 3.0 is really only suitable for experimental use by seasoned Python veterans.

The Cost of Python 3

David Beazley may have ended up feeling like a Python 3 beta tester, but, as discussed at the start of this article, most Python users have a free choice. We can live a little longer with Python 2 warts in exchange for a proven platform and an excellent set of supporting libraries. We can try and write to a language subset. We can use Python 2 and import much of the future. Or we can dive into Python 3.

The people who must find the language fork tough are the Python suppliers. Our choice, as consumers, means work for them: we’ve mentioned the core Python team, who must surely spend more time patching and testing; think of Python library writers (such as the wizards behind Twisted).

There’s another important class of supplier: the people working on alternative Python implementations, the ones which work on Java, or .Net, the ones which have no global interpreter lock, the ones which can run deeply recursive functions. Pythonistas are understandably excited about Unladen Swallow, a development branch of CPython 2.6. Just look at the project goals!

We want to make Python faster, but we also want to make it easy for large, well-established applications to switch to Unladen Swallow.

Produce a version of Python at least 5x faster than CPython.

Python application performance should be stable.

Maintain source-level compatibility with CPython applications.

Maintain source-level compatibility with CPython extension modules.

We do not want to maintain a Python implementation forever; we view our work as a branch, not a fork.

In summary, if Unladen Swallow touches down safely, it will become CPython, and anyone using CPython will benefit from a high-level language capable of performing at native speeds.

I’d like to highlight the final goal, the one about maintaining, branching and forking. Unladen Swallow is a branch taken from CPython 2.6^[2]. If it succeeds, much hard and unglamorous work will be needed to merge it to the latest CPython 2, and patch it across to CPython 3. Python implementers must pay a high price, in terms of increased workload, for the Python 2, Python 3 fork.

Could Python have evolved in a more linear way, by deprecating then removing features, while adding in new ones? I guess not, a mature language wouldn’t dare break backwards compatibility.

Would it?

Evolution of Python

My employers were right to characterise Python as a developing language. On the subject of incremental change, I wanted to highlight again the evolution of the multiset in Python, from Python 1.4, released in 2001, through to Python 3.1, just 4 months old.

Evolution of the Multiset in Python

def multiset_14(xs):
    multiset = {}
    for x in xs:
        if multiset.has_key(x):
            multiset[x] = multiset[x] + 1
        else:
            multiset[x] = 1
    return multiset

def multiset_15(xs):
    multiset = {}        
    for x in xs:
        multiset[x] = multiset.get(x, 0) + 1
    return multiset

import collections

def multiset_25(xs):
    multiset = collections.defaultdict(int)
    for x in xs:
        multiset[x] += 1
    return multiset

def multiset_31(xs):
    return collections.Counter(xs)

Lovely!

multiset_14() won’t work in Python 3, and multiset_31() won’t work in Python 2 (not yet, anyway).

Accepting Python 3

The main goal of the Python development community at this point should be to get widespread acceptance of Python 3000. — Guido van Rossum, 2009-10-21

Unlike Steve Holden, Guido van Rossum is trying to get people to move to Python 3, or at least to accept it. Here’s how:

I propose a moratorium on language changes. This would be a period of several years during which no changes to Python’s grammar or language semantics will be accepted. The reason is that frequent changes to the language cause pain for implementers of alternate implementations (Jython, IronPython, PyPy, and others probably already in the wings) at little or no benefit to the average user (who won’t see the changes for years to come and might not be in a position to upgrade to the latest version for years after).

Wow!

I’m not close enough to Python development to know exactly what’s involved here, but a scan of the email thread suggests this proposal has been widely accepted. I think it’s clear from the rest of this article that I sympathise with the motivation behind it. Yet I can’t help feeling uneasy about putting Python on ice. Yes, there have been changes to the language grammar over the past fifteen years. I wouldn’t say they’ve been frequent, and there aren’t many I’d want to do without, even if I only get to use them (in production) a year or two after they’ve been released. Yes, these changes cause pain to implementers^[3], but that’s not the whole story. Who said implementing a language would be easy? Perhaps much of the pain comes from implementing the changes twice, once for 2 and once for 3.

Soon there’ll be a PEP stating more formally what exactly a moratorium on language changes will mean. That is,

A Python Enhancement Proposal which Proposes: Stop Enhancing Python!

[1] I wonder if anyone can guess why this code fails, just by looking at it? As a hint, highlight the rest of this paragraph. Some Python 2 codecs are byte rather than text oriented, and Python 3 prohibits this kind of confusion.

[2] More details of the Unladen Swallow branch approach.

In order to achieve our combination of performance and compatibility goals, we opt to modify CPython, rather than start our own implementation from scratch. In particular, we opt to start working on CPython 2.6.1: Python 2.6 nestles nicely between 2.4/2.5 (which most interesting applications are using) and 3.x (which is the eventual future). Starting from a CPython release allows us to avoid reimplementing a wealth of built-in functions, objects and standard library modules, and allows us to reuse the existing, well-used CPython C extension API. Starting from a 2.x CPython release allows us to more easily migrate existing applications; if we were to start with 3.x, and ask large application maintainers to first port their application, we feel this would be a non-starter for our intended audience.

[3]: C++ compiler writers, gear up for C++0x!

Steady on Subversion

tag@wordaligned.org (Thomas Guest) — 2009-10-13

My secret shame

In a world of distributed version control systems I’m ashamed to confess I still use Subversion. We use it at work, exclusively. I use it at home, by default. Worse still, in a small way, I help promote and perpetuate this antiquated version control system: if you want to mirror a Subversion repository or set up a Subversion pre-commit hook, you may well find some faded notes I wrote on these subjects.

Whisper the words. I still like Subversion.

What do I like most? The command to revert a change. Merge it backwards.

$ svn merge --change -666

Branches and tags are one and the same. For someone who grew up with CVS, that’s quite a relief. Anyone can grasp the versioned file tree model. No one wants their version control system to surprise them. My boss, who doesn’t get to program as much as he’d like, has discovered a shiny Subversion client — and he doesn’t even use Windows. The sales team, who do use Windows, can use Subversion to collaborate on their office documents. TortoiseSVN interfaces to the Word diff tool, a nice touch. And software developers can surely find stable Subversion plug-ins for whatever tools they use.

The Subversion documentation is solid and has been for some while. I’m surprised anyone ever arrives at my website seeking tips, but arrive they do, and in ever-increasing numbers.

Subversion does enough. The hard parts of my job are deciding what software to write, writing it, and working as a team. Version control should be frictionless, the easy bit. Which it is.

Of course Subversion has weak points. It should be faster (whee, see how git flies!) and merging can be irksome (improving on CVS wasn’t much of a target). But the biggest annoyance I’ve had with Subversion is caused by its ubiquity and its continuing upgrade trajectory. Somehow I’ve ended up accessing 1.4 and 1.5 format repositories on a machine which hosts 1.4, 1.5 and 1.6 clients in /usr/local/bin, /usr/bin and /opt/local/bin, not necessarily in that order. Silly me, I’m sorted now, I think, but I’d happily see Subversion go into maintenance mode. For managing change, give me stable software.

Do it the same, but better!

As mentioned at the start of this post, though, the world of version control has itself changed. Subversion represents evolution: by being a better CVS, it aimed to supplant its ancestor and become the VCS of choice for open source projects. CVS has indeed been supplanted, but true progress has come from the distributed version control revolution.

We’ve been talking about a single, central source tree which develops in discrete steps. Everyone has a local working copy of the files in this tree, which they keep up to date, routinely merging changes back to base. Check out, check in. It is an easy model to understand, but in practice there can be problems. What happens when you can’t access the tree? Or when it gets pulled in different directions? Or when you lose track of who merged what where when? Now consider the distributed version control world, where the model extends to multiple trees. Everyone copies the entire repository as needed. Clone, merge.

In this distributed world a project needn’t have a single, central repository^[1]. What’s more, there is no single leading distributed version control system. As a result, open source projects are spoiled for choice.

The rise of the DVCS is a fascinating history, though one I’ve yet to directly engage with — unless you count the growing collection of DVCSes taking root on my hard disk (none of which shipped with my operating system). I like the feel of git. Python will migrate to mercurial. For now, I’m staying put.

Definitive commentary

Ben Collins-Sussman is one of the original designers and developers of Subversion, and co-author of Version Control with Subversion. His essays on the changing field of version control make fine reading. A couple of years ago he wrote:

Today, Subversion has now gone from “cool subversive product” to “the default safe choice” for both 80% and 20% audiences. The 80% companies who were once using crappy version control (or no version control at all) are now blogging to one another — web developers giving “hot tips” to each other about using version control (and Subversion in particular) to manage their web sites at their small web-development shops. What was once new and hot to 20% people has finally trickled down to everyday-tool status among the 80%.

The great irony here … is that Subversion was originally intended to subvert the open source world. It’s done that to a reasonable degree, but it’s proven far more subversive in the corporate world!

— Ben Collins-Sussman, Version Control and “the 80%”, October 2007

In April last year he followed up with:

[…] we think that [Subversion] will probably be the “final” centralized system that gets written in the open source world — it represents the end-of-the-line for this model of code collaboration.

It will continue to be used for many years, but specifically it will gain huge mindshare in the corporate world, while (eventually) losing mindshare to distributed systems in the open-source arena … Subversion isn’t anywhere near “fading away”. Quite the opposite: its adoption is still growing quadratically in the corporate world, with no sign of slowing down. This is happening independently of open source trailblazers losing interest in it. It may end up becoming a mainly “corporate” open source project (that is, all development funded by corporations that depend on it), but that’s a fine way for a piece of mature software to settle down.

— Ben Collins-Sussman, Subversion’s Future, April 2008

Long live Subversion

Ben Collins-Sussman backs up his essay with a graph showing the increasing numbers of Apache Subversion servers discoverable on the internet. His claims square with my personal experience. I’m a corporate Subversion user and I don’t see my employer switching version control systems any time soon (it’s my decision as much as anyone’s). What’s more, Subversion is used in most of the companies I know of, where it has supplanted both legacy and proprietary systems. As stated already, version control isn’t the hard part of my job, but should I ever need to change jobs, Subversion won’t stand in my way.

[1]: A project may well choose to nominate a single central repository as the “master” repository. The functionality offered by distributed version control systems is effectively a superset of that offered by centralised ones.

Favicon

tag@wordaligned.org (Thomas Guest) — 2009-09-16

On the subject of this site, I wanted to mention the recent addition of a favicon . Per pixel, it’s cost me more effort than any other feature; but then it’s accessed more than any other asset. It’s meant to be a piece from a jigsaw puzzle. I got the idea when re-reading Life A User’s Manual. I like puzzles and piecing things together.

Perec’s great masterpiece is packed with interwoven stories and trickery, but at its heart is the epic battle between the millionaire, Bartlebooth, and the puzzle-maker Gaspard Winckler. Bartlebooth begins his campaign by learning how to paint, which takes him 10 years. For the next 20 years he travels the world, painting a water colour picture of a different port every couple of weeks. He sends the paintings back home to Paris. On receipt, Winckler glues each picture to a board which he then cuts, making a series of jigsaw puzzles for Bartlebooth to solve on his return. Once Bartlebooth completes each puzzle, an ingenious process is used to glue its pieces together and re-join the cut fibres of the paper; then the picture itself is lifted from the board, returned to the port it depicts, and washed clean in the sea; and finally the paper is returned in something close to its original state to Bartlebooth.

Thus, after 50 years of work, there will be nothing to show.

In the book’s preamble Perec describes familiar die-cut jigsaws, classifying the best known pieces of such puzzles as “little chaps”, “double crosses” and “crossbars”. Such diversions are eschewed by the true puzzler:

The art of jigsaw puzzling begins with wooden puzzles cut by hand, whose maker undertakes to ask himself all the questions the player will have to solve, and, instead of allowing chance to cover his tracks, aims to replace it with cunning, trickery and subterfuge. All the elements occurring in the image to be reassembled — this armchair covered in gold brocade, that three-pointed black hat with its rather ruined black plume, or that silver-braided bright yellow livery — serve by design as points of departure for trails that lead to false information.

My thanks to Tim Beard for scanning a couple of pages from his edition of La Vie, Mode d’Emploi. I wanted to know what the “little chaps” etc. were before they got translated into English. I realise my favicon could be improved but I don’t know how to go about it. Anyone?

Code Rot

tag@wordaligned.org (Thomas Guest) — 2009-09-03

Those of us who have to tiptoe around non-standard or ancient compilers will know that template template parameters are off limits.

— Hubert Matthews (PDF)

Dvbcodec Fail

Long ago, way back in 2004, I wrote an article for Overload describing how to use the Boost Spirit parser framework to generate C++ code which could convert structured binary data to text. I went on to republish this article on my own website, where I also included a source distribution.

Much has changed since then. The C++ language may not have, but compiler and platform support for it has improved considerably. Boost survives — indeed, many of its libraries will feed into the next version of C++. Overload thrives, adapting to an age when printed magazines about programming are all but extinct. My old website proved less durable: I’ve changed domain name and shuffled things around more than once. But you can still find the article online if you look hard enough, and recently someone did indeed find it. He, let’s call him Rick, downloaded the source code archive, dvbcodec-1.0.zip, extracted it, scanned the README, typed:

$ make

… and discovered the code didn’t even build.

At this point many of us would assume (correctly) the code had not been maintained. We’d delete it and write off the few minutes it took to evaluate it. Rick decided instead to contact me and let me know my code was broken. He even offered a fix for one problem.

Code Rot

Sad to say, I wasn’t entirely surprised. I no longer use this code. Unused code stops working. It decays.

I’m not talking about a compiled executable, which the compiler has tied to a particular platform, and which therefore progressively degrades as the platform advances. (I’ve heard stories about device drivers for which the source code has long been lost, and which require ever more elaborate emulation shims to keep them alive.) I’m talking about source code. And the decay isn’t usually literal, though I suppose you might have a source listing on a mouldy printout, or an unreadable floppy disk.

No, the code itself is usually a pristine copy of the original. Publishers often attach checksums to source distributions so readers can verify their download is correct. I hadn’t taken this precaution with my dvbcodec-1.0.zip but I’m certain the version Rick downloaded was exactly the same as the one I created 5 years ago. Yet in that time it had stopped working. Why?

Standard C++

As already mentioned, this was C++ code. C++ is backed by an ISO standard, ratified in 1998, with corrigenda published in 2003. You might expect C++ code to improve with age, compiling and running more quickly, less likely to run out of resources.

Not so. My favourite counter-example comes from a nice paper “CheckedInt: A policy-based range-checked integer” (PDF) published by Hubert Matthews in 2004 which discusses how to use C++ templates to implement a range-checked integer. The paper includes a source code listing together with some notes to help readers forced to “tiptoe around non-standard or ancient compilers” (think: MSVC6). Yet when I experimented with this code in 2005 I found myself tripped up by a strict and up-to-date compiler.

$ g++ -Wall -c checked_int.cpp
checked_int.cpp: In constructor `CheckedInt<low, high, ValueChecker>::CheckedInt(int)':
checked_int.cpp:45: error: there are no arguments to `RangeCheck' that
depend on a template parameter, so a declaration of `RangeCheck' must
be available
checked_int.cpp:45: error: (if you use `-fpermissive', G++ will accept
your code, but allowing the use of an undeclared name is deprecated)

I emailed Hubert Matthews using the address included at the top of his paper. He swiftly and kindly put me straight on how to fix the problem.

What’s interesting here is that this code is pure C++, just over a page of it. It has no dependencies on third party libraries. Hubert Matthews is a C++ expert and he acknowledges the help of two more experts, Andrei Alexandrescu and Kevlin Henney, in his paper. Yet the code fails to build using both ancient and modern compilers. In its published form it has the briefest of shelf-lives.

Support Rot

Code alone is of limited use. What really matters for its ongoing health is that someone cares about it — someone exercises, maintains and supports it. Hubert Matthews included an email address in his paper and I was able to contact him using that address.

How well would my code shape up on this front? Putting myself in Rick’s position, I unzipped the source distribution I’d archived 5 years ago. I was pleased to find a README which, at the very top, provides a URL for updates, http://homepage.ntlworld.com/thomas.guest. I was less pleased to find this URL gave me a 404 Not Found error. Similarly, when I tried emailling the project maintainer mentioned in the README, I got a 550 Invalid recipient error: the attempted delivery to thomas.guest@ntlworld.com had failed permanently.

Cool URIs don’t change but my old NTL homepage was anything but cool; it came for free with a dial-up connection I’ve happily since abandoned. Looking back, maybe I should have found a more stable location for my code. If I’d set up (e.g.) a Sourceforge project then my dvbcodec project might still be alive and supported, possibly even by a new maintainer.

How did this ever compile?

Wise hindsights wouldn’t resurrect my code. If I wanted to continue I’d have to go it alone. Here’s what the README had to say about platform requirements.

REQUIREMENTS and PLATFORMS

To build the dvbcodec you will need Version 1.31.0 of Boost, or later.

You will also need a good C++ compiler. The dvbcodec has been built and tested on the Windows operating system using: GCC 3.3.1, MSVC 7.1

A “good C++ compiler”, eh? As we’ve already seen, GCC 3.3.1 may be good but my platform has GCC 4.0.1 installed, which is better. If my records can be believed, this upperCase() function compiled cleanly using both GCC 3.3.1 and MSVC 7.1.

std::string
upperCase(std::string const & lower)
{
    std::string upper = lower;
    
    for (std::string<char>::iterator cc = upper.begin();
         cc != upper.end(); ++cc)
    {
        * cc = std::toupper(* cc);
    }
    
    return upper;
}

Huh? Std::string is a typedef for std::basic_string<char> and there’s no such thing as a std::basic_string<char><char>::iterator, which is what GCC 4.0.1 says:

stringutils.cpp:58: error: 'std::string' is not a template

The simple fix is to write std::string::iterator instead of std::string<char>::iterator. A better fix, suggested by Rick, is to use std::transform(). I wonder why I missed this first time round?

std::string
upperCase(std::string const & lower)
{
    std::string upper = lower;
    std::transform(upper.begin(), upper.end(), upper.begin(), ::toupper);
    return upper;
}

Boost advances

GCC has become stricter about what it accepts even though the formal specification of what it should do (the C++ standard) has stayed put. The Boost C++ libraries have more freedom to evolve, and the next round of build problems I encountered relate to Boost.Spirit’s evolution. Whilst it would be possible to require dvbcodec users to build against Boost 1.31 (which can still be downloaded from the Boost website) it wouldn’t be reasonable. So I updated my machine (using Macports) to make sure I had an up to date version of Boost, 1.38 at the time of writing.

$ sudo port upgrade boost

Boost’s various dependencies triggered an upgrade of boost-jam, gperf, libiconv, ncursesw, ncurses, gettext, zlib, bzip2, and this single command took over an hour to complete.

I discovered that Boost.Spirit, the C++ parser framework on which dvbcodec is based, has gone through an overhaul. According to the change log the flavour of Spirit used by dvbcodec is now known respectfully as Spirit Classic. A clever use of namespaces and include path forwarding meant my “classic” client code would at least compile, at the expense of some deprecation warnings.

Computing dependencies for decodeout.cpp...
Compiling decodeout.cpp...
In file included from codectypedefs.hpp:11,
                 from decodecontext.hpp:10,
                 from decodeout.cpp:8:
/opt/local/include/boost/spirit/tree/ast.hpp:18:4: warning: #warning "This header is deprecated. Please use: boost/spirit/include/classic_ast.hpp"
In file included from codectypedefs.hpp:12,
                 from decodecontext.hpp:10,
                 from decodeout.cpp:8:

To suppress these warnings I included the preferred header. I then had to change namespace directives from boost::spirit to boost::spirit::classic. I fleetingly considered porting my code to Spirit V2, but decided against it: for even after this first round of changes, I still had a build problem.

Changing behaviour

Actually, this was a second level build problem. The dvbcodec build has multiple phases:

it builds a program to generate code. This generator can parse binary format syntax descriptions and emit C++ code which will convert data formatted according to these descriptions
it runs this generator with the available syntax descriptions as inputs
it compiles the emitted C++ code into a final dvbcodec executable

I ran into a problem during the second phase of this process. The dvbcodec generator no longer parsed all of the supplied syntax descriptions. Specifically, I was seeing this conditional test raise an exception when trying to parse section format syntax descriptions.

    if (!parse(section_format,
               section_grammar,
               space_p).full)
    {
        throw SectionFormatParseException(section_format);
    }

Here, parse is boost::spirit::classic::parse, which parses something — the section format syntax description, passed as a string in this case — according to the supplied grammar. The third parameter, boost::spirit::classic::space_p, is a skip parser which tells parse to skip whitespace between tokens. Parse returns a parse_info struct whose full field is a boolean which will be set to true if the input section format has been fully consumed.

I soon figured out that the parse call was failing to fully consume binary syntax descriptions with trailing spaces, such as the the one shown below.

" program_association_section() {"
"    table_id                   8"
"    section_syntax_indicator   1"
"    '0'                        1"
....
"    CRC_32                    32"
" }                              "

If I stripped the trailing whitespace after the closing brace before calling parse() all would be fine. I wasn’t fine about this fix though. The Spirit documentation is very good but it had been a while since I’d read it and, as already mentioned, my code used the “classic” version of Spirit, in danger of becoming the “legacy” then “deprecated” and eventually the “dead” version. Re-reading the documentation it wasn’t clear to me exactly what the correct behaviour of parse() should be in this case. Should it fully consume trailing space? Had my program ever worked?

I went back in time, downloading and building against Boost 1.31, and satisfied myself that my code used to work, though maybe it worked due to a bug in the old version of Spirit. Stripping trailing spaces before parsing allowed my code to work with Spirit past and present, so I curtailed my investigation and made the fix.

(Interestingly, Boost 1.31 found a way to warn me I was using a compiler it didn’t know about.

boost_1_31_0/boost/config/compiler/gcc.hpp:92:7: warning: 
#warning "Unknown compiler version - please run the configure tests and report the results"

I ignored this warning.)

Code inaction

Apologies for the lengthy explanation in the previous section. The point is, few software projects stand alone, and changes in any dependencies, including bug fixes, can have knock on effects. In this instance, I consider myself lucky; dvbcodec’s unusual three phase build enabled me to catch a runtime error before generating the final product. Of course, to actually catch that error, I needed to at least try building my code.

More simply: if you don’t use your code, it rots.

Rotten artefacts

It wasn’t just the code which had gone off. My source distribution included documentation — the plain text version of the article I’d written for Overload — and the Makefile had a build target to generate an HTML version of this documentation. This target depended on Quickbook, another Boost tool. Quickbook generates Docbook XML from plain text source, and Docbook is a good starting point for HTML, PDF and other standard output formats.

This is quite a sophisticated toolchain. It’s also one I no longer use. Most of what I write goes straight to the web and I don’t need such a fiddly process just to produce HTML. So I decided to freshen up dead links, leave the original documentation as a record, and simply cut the documentation target from the Makefile.

Stopping the rot

As we’ve seen, software, like other soft organic things, breaks down over time. How can we stop the rot?

Freezing software to a particular executable built against a fixed set of dependencies to run on a single platform is one way — and maybe some of us still have an aging Windows 95 machine, kept alive purely to run some such frozen program.

A better solution is to actively tend the software and ensure it stays in shape. Exercise it regularly on a build server. Record test results. Fix faults as and when they appear. Review the architecture. Upgrade the platform and dependencies. Prune unused features, splice in new ones. This is the path taken by the Boost project, though certainly the growth far outpaces any pruning (the Boost 1.39 download is 5 times bigger than its 1.31 ancestor). Boost takes forwards and backwards compatibility seriously, hence the ongoing support for Spirit classic and the compiler version certification headers. Maintaining compatibility can be at odds with simplicity.

There is another way too. Although the dvbcodec project has collapsed into disrepair the idea behind it certainly hasn’t. I’ve taken this same idea — of parsing formal syntax descriptions to generate code which handles binary formatted data — and enhanced it to work more flexibly and with a wider range of inputs. Whenever I come across a new binary data structure, I paste its syntax into a text file, regenerate the code, and I can work with this structure. Unfortunately I can’t show you any code (it’s proprietary) but I hope I’ve shown you the idea. Effectively, the old C++ code has been left to rot but the idea within it remains green, recoded in Python. Maybe I should find a way to humanely destroy the C++ and all links to it, but for now I’ll let it degrade, an illustration of its time.

Is it possible that software is not like anything else, that it is meant to be discarded: that the whole point is to see it as a soap bubble? — Alan J. Perlis

Thanks

I would like to thank to Rick Engelbrecht for reporting and helping to fix the bugs discussed in this article.

This article first appeared in Overload 92, and I would like to thank the team at Overload for their expert help.

Word Aligned

Knuth visited, Brains Limited

Set.insert or set.add?

Get set, go!

How long is a string?

Define pedantic

Hiding iterator boilerplate behind a Boost facade

Contents

Equality and Equivalence

Binary search revisited

Contents

Man or man(1)?

Binary search returns … ?

Contents

Think, quote, escape

Beware the March of IDEs!

The March of IDEs

Me and my IDE

Learning to Say “Hello, World”

The Ides of March

Credits

Pi seconds is a nanocentury

Bike charts by Google

When you comment on a comment

Power programming

Contents

Python, Surprise me!

A Simple Function

The Real Surprise

Parentheses Required(?)

Serious about Syntax

Won’t Get Fooled Again

Next permutation: When C++ gets it right

Contents

itertools.permutations(iterable, r=None)

Python on Ice

Contents

Steady on Subversion

My secret shame

Do it the same, but better!

Definitive commentary

Long live Subversion

Favicon

Code Rot

Contents

`itertools.permutations(iterable, r=None)`