Generalising tail call optimised C++

This series: Lightning talk, Explanation, Performance, Generalisation.

In previous posts I discussed the construction of some C++ that does the same job that the tail call optimisation does in some other languages. The example code given showed the case where we know that every function in the recursion will take two long integer parameters, and return a long as well.

In fact, it is perfectly possible to generalise this code to cover more complex cases. Fortunately, the trampoline function doesn’t need to know the arguments taken by the functions being called, only the return value. It looks like this:

template<typename RetT>
const RetT trampoline_templ(
    std::auto_ptr< IAnswer<RetT> > answer )
{
    while( !answer->finished() )
    {
        answer = answer->tail_call()();
    }
    return answer->value();
}

So we can call this with the type of the return value as our template parameter, and supply an object which satisfies the IAnswer<RetT> interface:

template<typename RetT>
class IAnswer
{
public:
    virtual const bool             finished()  const = 0;
    virtual const ICallable<RetT>& tail_call() const = 0;
    virtual const RetT             value()     const = 0;
};

where ICallable looks like this:

template<typename RetT>
class ICallable
{
public:
    typedef std::auto_ptr< IAnswer<RetT> > AnswerPtr;
    virtual AnswerPtr operator()() const = 0;
};

The concrete classes that implement these interfaces need to know the types (and number) of the arguments, but that’s ok because they only get instantiated by code that would otherwise (in the standard, non-tail-call recursion case) call the functions themselves. In the toy case we are using of repeatedly adding up numbers to multiply by two, the outer function looks like this:

const long times_two_tail_call_templ( const long n )
{
    typedef Answer2<long, long, long> AnswerType;

    return trampoline_templ(
        AnswerType::newFn(
            times_two_tail_call_impl, 0, n, 0 )
    );
}

and the inner one looks like this:

std::auto_ptr< IAnswer<long> > times_two_tail_call_impl(
    const long acc, const long i )
{
    typedef Answer2<long, long, long> AnswerType;

    if( i == 0 )
    {
        return return AnswerType::newAns( acc );
    }
    else
    {
        return AnswerType::newFn(
            times_two_tail_call_impl,
            acc + 2, i - 1, 0 );
    }
}

Both of the above use static convenience methods newFn and newAns that I have defined on Answer2 to create smart pointers to newly-allocated Answer2 objects. newAns creates an Answer2 that contains a final answer, and newFn creates an Answer2 specifying another function (with arguments) to call.

Answer2 looks like this:

template<typename RetT, typename Arg1T, typename Arg2T>
class Answer2 : public IAnswer<RetT>
{
private:
    typedef FnPlusArgs2<RetT, Arg1T, Arg2T> FnArgs;
    typedef std::auto_ptr< IAnswer<RetT> > AnswerPtr;

    const bool finished_;
    const FnArgs tail_call_;
    const RetT value_;

private:
    Answer2( const bool finished, const FnArgs tail_call, const RetT value )
    : finished_( finished )
    , tail_call_( tail_call )
    , value_( value )
    {
    }

    static AnswerPtr newPtr(
        const bool finished, const FnArgs tail_call, const RetT value )
    {
        return AnswerPtr( new Answer2<RetT, Arg1T, Arg2T>(
            finished, tail_call, value ) );
    }
public:
    static AnswerPtr newFn(
        const typename FnArgs::fn_type fn,
        const Arg1T arg1,
        const Arg2T arg2,
        const RetT zero_val )
    {
        return newPtr( false, FnArgs( fn, arg1, arg2 ), zero_val );
    }

    static AnswerPtr newAns( const RetT value )
    {
        return newPtr( true, FnArgs::null(), value );
    }

    virtual const bool    finished()  const { return finished_; };
    virtual const FnArgs& tail_call() const { return tail_call_; };
    virtual const RetT    value()     const { return value_; };
};

and uses FnPlusArgs2, which looks like this:

template<typename RetT, typename Arg1T, typename Arg2T>
class FnPlusArgs2 : public ICallable<RetT>
{
private:
    typedef typename ICallable<RetT>::AnswerPtr AnswerPtr;
public:
    typedef AnswerPtr (*fn_type)( const Arg1T, const Arg2T );
private:
    const fn_type fn_;
    const Arg1T arg1_;
    const Arg2T arg2_;

public:
    FnPlusArgs2( const fn_type fn, const Arg1T arg1, const Arg2T arg2 )
    : fn_( fn )
    , arg1_( arg1 )
    , arg2_( arg2 )
    {
    }

    virtual AnswerPtr operator()() const
    {
        return fn_( arg1_, arg2_ );
    }

    static FnPlusArgs2<RetT, Arg1T, Arg2T> null()
    {
        return FnPlusArgs2<RetT, Arg1T, Arg2T>( NULL, 0, 0 );
    }
};

I have continued with the 2 long arguments, and long return value example here, but with the above code it is possible to construct recursive code using more than one function, and the functions can have different numbers of arguments, and different argument types, so long as they all co-operate to produce an answer of the required type. The Source code for this article includes an example, in the file tail_call_templ_2fns.cpp, of two different functions that call each other recursively, and take different arguments, using the trampoline function and interfaces listed above, and Answer3 and FnPlusArgs3 class templates similar to Answer2 and FnPlusArgs2 shown above. Implementing the N-args case using variadic templates (C++11) or template meta-programming is left as an exercise for the reader.

This more realistic case where the number and types of arguments are not known beforehand forces us to use dynamic memory to store our AnswerN objects, and causes more pointer dereferences and virtual function calls, and these do hurt performance. In tests on my machine, this code ran approximately 10 times slower than the version using only stack memory. Perhaps we C++ programmers should comfort ourselves that many languages supporting tail-call optimisation require dynamic memory, virtual functions and pointer indirection to do absolutely everything.

JavaScript WTFs Videos

I recorded some videos of my JavaScript WTFs presentations:

You can get the JavaScript WTFs slides.

Update: all six episodes:

Find them all on PeerTube:

Closures in Scheme

Update: watch the video

In this series on Scheme: Intro, Basics, Closures.

Here’s a presentation I did recently, on Closures in the Scheme programming language. Closures are the way the environment in which a function was created hangs around with it as long as the function itself exists. They allow many flexible programming styles, and in this presentation I demonstrate how a simple object-oriented class structure can be implemented using closures.

Closures in Scheme

Performance of tail call optimised C++

This series: Lightning talk, Explanation, Performance, Generalisation.

After I wrote a version of tail-call optimised code in C++ I became interested in its performance relative to normal recursion. The tail call version can process arbitrarily large input, but how much do you pay for that in terms of performance?

Recap: there are 4 different versions of our function, called times_two. The first, “hardware”, uses the “*” operator to multiply by 2. The second, “loop” uses a for loop to add up lots of 2s until we get the answer. The third, “recursive”, uses a recursive function to add up 2s. The fourth, “tail_call” is a reimplementation of “recursive”, with a manual version of the tail call optimisation – see the original article for details.

Let’s look first at memory usage. Here is the stack memory usage over time as reported by Massif of calling the four functions for a relatively small input value of 100000:

Stack usage by the four functions.  recursive uses loads, and the others are constant.

The recursive function uses way more memory than the others (note the logarithmic scale), because it keeps all those stack frames, and the tail_call version takes much longer than the others (possibly because it puts more strain on Massif?), but keeps its memory usage low. Let’s look at how that affects its performance, for different sizes of input:

Time taken by each function for different input values.  When recursive starts using more memory than is available on the machine, its execution time grows rapidly

For these much larger input values, the recursive and tail_call functions take similar amounts of time, until the recursive version starts using all the physical memory on my computer. At this point, its execution times become huge, and erratic, whereas the tail_call function plods on, working fine.

So the overhead of the infrastructure of the tail call doesn’t have much impact on execution time for large input values, but it’s clear from the barely-visible green line at the bottom that using a for-loop with a mutable loop variable instead of function calls is way, way faster, with my compiler, on my computer, in C++. About 18 times faster, in fact.

And, just in case you were wondering: yes those pesky hardware engineers with their new-fangled “*” operator managed to defeat all comers with their unreasonable execution times of 0 seconds every time (to the nearest 10ms). I suppose that shows you something.

Tail call optimisation in C++

This series: Lightning talk, Explanation, Performance, Generalisation.

Some programming languages make recursive programming more practical by providing the tail call optimisation. For a tiny talk at the recent ACCU conference I looked at how we might do something similar in C++.

Update: Source code for this article is available.

Multiplying by two

Here’s a toy problem we will use as our example.

Imagine for a second that you want to write a function that multiplies a number by two. OK, we can do that:

long times_two_hardware( long value )
{
    return value * 2;
}

Now imagine that you don’t have the “*” operator. We’re going have to use “+”:

long times_two_loop( long value )
{
    long ret = 0;
    for ( long i = 0; i < value; ++i )
    {
        ret += 2;
    }
    return ret;
}

(Obviously, this is just a silly example designed to be easy to follow.)

Now imagine that you read somewhere that state was bad, and you could always replace a loop with recursion. Then you might get something like this:

long times_two_naive_recursive( long value )
{
    if ( value == 0 )
    {
        return 0;
    }
    else
    {
        return 2 + times_two_naive_recursive( value - 1 );
    }
}

This is fine, but what happens when you run it for a large input?

$ ulimit -S -s 16
$ ./times_two naive_recursive 100000
Segmentation fault

Note that I set my stack size to be very small (16K) to make the point - actually, this will run successfully for very large arguments, but it will eat all your memory and take a long time to finish.

Why does this fail? Because every time you call a function, the state of the current function is saved, and new information is pushed onto the stack about the new function. When you call a function from within a function multiple times, the stack grows and grows, remembering the state all the way down to the place where you started.

So is programming like this useless in practice?

Tail call optimisation

No, because in several programming languages, the compiler or interpreter performs the "tail call optimisation".

When you call a function from within some other code, you normally need the state of the current code to be preserved. There is a special case where you don't need it, though, and this is called a tail call. A tail call is just the situation where you call a function and immediately return its return value as your return value. In this case, we don't need any of the state of the current code any more - we are just about to throw it away and return.

The tail call optimisation throws away this unneeded state before calling the new function, instead of after.

[In practice, in compiled code, this involves popping all the local variables off the stack, pushing the new function parameters on, and jmping to the new function, instead of calling it. This means that when we hit the ret at the end of the new function, we return to the original caller, instead of the location of the tail call.]

Many recursive functions can be re-cast as tail-call versions (sometimes called iterative versions). The one we're looking at is one of those. Here is the tail-call version:

long times_two_recursive_impl( long total, long counter )
{
    if ( counter == 0 )
    {
        return total;
    }
    else
    {
        return times_two_recursive_impl(
            total + 2, counter - 1 );
    }
}

long times_two_recursive( long value )
{
    return times_two_recursive_impl( 0, value );
}

It consists of an outer function times_two_recursive which just hands off control to the inner function times_two_recursive_impl. The inner function uses a counter variable and calls itself recursively, reducing that counter by one each time, until it reaches zero, when it returns the total, which is increased by 2 each time.

The key feature of this implementation is that the recursive function times_two_recursive_impl uses a tail call to do the recursion: the value of calling itself is immediately returned, without reference to anything else in the function, even temporary variables.

So, let's see what happens when we compile and run this:

$ ulimit -S -s 16
$ ./times_two recursive 100000
Segmentation fault

Did I mention that C++ doesn't do the tail call optimisation?*

* Tail call optimisation isn't in the C++ standard. Apparently, some compilers, including MS Visual Studio and GCC, do provide tail call optimisation under certain circumstances (when optimisations are enabled, obviously). It is difficult to implement for all cases, especially in C++ since destruction of objects can cause code to be executed where you might not have expected it, and it doesn't appear to be easy to tell when a compiler will or will not do it without examining the generated assembly language. Languages which have this feature by design, like Scheme (and D?) can do it more predictably.

So how would we write code that is tail call optimised in C++? Possibly of more interest to me personally: if we were generating C++ as the output format for some other language, what code might we generate for tail call optimised functions?

Tail call optimised C++

Let's imagine for a second we have some classes, which I'll define later. FnPlusArgs holds a function pointer, and some arguments to be passed to it. Answer holds on to one of 2 things: either a FnPlusArgs to call later, or an actual answer (return value) for our function.

Now we can write our function like this:

Answer times_two_tail_call_impl( long acc, long i )
{
    if ( i == 0 )
    {
        return Answer( true, null_fn_plus_args, acc );
    }
    else
    {
        return Answer(
            false,
            FnPlusArgs(
                times_two_tail_call_impl,
                acc + 2,
                i - 1
            ),
            0
        );
    }
}

long times_two_tail_call( long n )
{
    return trampoline( Answer(
        false,
        FnPlusArgs( times_two_tail_call_impl, 0, n ),
        0 ) );
}

This has the same structure as times_two_recursive, if a little more verbose. The important point to note, though, is that times_two_tail_call_impl doesn't call itself recursively. Instead, it returns an Answer object, which is a delegate saying that we have more work to do: calling the provided function with the supplied arguments.

The Trampoline

All we need now is some infrastructure to call this function, and deal with its return value, calling functions repeatedly until we have an answer. This function is called a "trampoline", and you can sort of see why:

long trampoline( Answer answer )
{
    while ( !answer.finished_ )
    {
        answer = answer.tail_call_();
    }
    return answer.value_;
}

While the answer we get back tells us we have more work to do, we call functions, and when we're finished we return the answer.

Now all we need to get this working is the definition of Answer and FnPlusArgs:

struct Answer;
typedef Answer (*impl_fn_type)( long, long );

struct FnPlusArgs
{
    impl_fn_type fn_;
    long arg1_;
    long arg2_;

    FnPlusArgs(
        impl_fn_type fn,
        long arg1,
        long arg2
    );

    Answer operator()();
};

impl_fn_type null_fn = NULL;
FnPlusArgs null_fn_plus_args( null_fn, 0, 0 );

struct Answer
{
    bool finished_;
    FnPlusArgs tail_call_;
    long value_;

    Answer( bool finished, FnPlusArgs tail_call, long value );
};


FnPlusArgs::FnPlusArgs(
    impl_fn_type fn,
    long arg1,
    long arg2
)
: fn_( fn )
, arg1_( arg1 )
, arg2_( arg2 )
{
}

Answer FnPlusArgs::operator()()
{
    return fn_( arg1_, arg2_ );
}


Answer::Answer( bool finished, FnPlusArgs tail_call, long value )
: finished_( finished )
, tail_call_( tail_call )
, value_( value )
{
}

The only notable thing about this is that we use operator() on FnPlusArgs to call the function it holds.

Results

Now, when we run this code, we get what we wanted:

$ ulimit -S -s 16
$ ./times_two tail_call 100000
200000

(I.e. it doesn't crash.)

So, it turns out that the tail call optimisation is just a while loop. Sort of.