Why -Wconversion is ESSENTIAL

Wconversion, along side the equally critical -Werror is a constant life saver.


Hidden bugs which cause code to appear to work but occasionally give nasty, unexpected effects are a nightmare. They come in all shapes and sizes, but one of the most common in my experience, and the most likely to cause a failure late of a Friday afternoon just before a deadline, is automatic type conversion (type coercion to give it a more precise name).

template<typename C>
void assertEqual(C c,double a,double b)
{
    // Good enough for audio :)
    double epsilon=1.0e-10;
    bool ok(false);
    if(b==0)
    {
        // ok=abs(a)<epsilon; SILENT KILLER
        ok=fabs(a)<epsilon;
    }else{
        // ok=fabs(1.0-(a/b))<epsilon; SILENT KILLER
        ok=fabs(1.0-(a/b))<epsilon;
    }
    assertEqual(c,ok,true);
}

I will now have to admit I wrote the above code. This is a perfect example of the effects of rushing. Something at the time of writing it told me there was a problem, but I ignored my inner voice and pushed on. Then later I recompiled with the ever so necessary -Wconversion -Werror and all was revealed. abs() from stdlib.h takes integer arguments [ int abs(int) __pure2; ]. The C++ compiler, in default mode, silently converts the passed doubles into int. This is a devastating bug because many, many values will give a 'true' return for what should be a false. 1.1 and 1.0 are not 'close enough for audio' but would give a return of 'true'.

I have seen this happen all over the place in code, more often converting between signed and unsigned or different sizes of integer. 

Iterators Via CRTP

Iteration without end.
(wikicommons -see here)

My current (personal time) work is all about compile time optimisation via templates and constexpr, so here is an implementation of iterators using recursive templates to give compile time static polymorphic dispatch.


CRTP: Curiously Recursive Template Pattern (how about that for a terrible name) is a template based, i.e. compile time, form of polymorphism. It allows inheritance with semantically late binding without the cost of virtual dispatch. On Sonic-Cpp (the project on which I am working) there are generators which create samples; the samples when placed in sequence create digitised sounds (see here).

Generators are defined by what they implement, not via inheritance. They all have a get(size_t) method, but that is by convention. I wrote them this way so the get(size_t) method is fully inlineable, there is no virtual dispatch (see here). However, writing begin() and end() for accessing the object contents via iterators for each type of Generator would be a waste of time and effort. This is where CRTP comes in, we can delay the resolution of the get(size_t) method until instantiation of the template and hence have the appearance of inheritance so we only need to write the code for begin() and end() once; the complier then instantiates as many different implementations of begin() and end() as are necessary.

I guess I could have explained that better; at least it does kind of illustrate why the pattern gets called 'curious'. Code often speaks better than English so:

template<class G>
    class GeneratorIterator : public std::iterator<std::random_access_iterator_tag, double>
    {
      size_t m_pos;
      G const * m_gen;
    public:
      GeneratorIterator(size_t pos,G const * gen) :m_pos(pos),m_gen(gen) {}
      GeneratorIterator(const GeneratorIterator& mit) : m_pos(mit.m_pos),m_gen(mit.m_gen) {}
      GeneratorIterator& operator++() {++m_pos;return *this;}
      GeneratorIterator operator++(int) {GeneratorIterator tmp(*this); operator++(); return tmp;}
      GeneratorIterator& operator--() {--m_pos;return *this;}
      GeneratorIterator operator--(int) {GeneratorIterator tmp(*this); operator--(); return tmp;}
      bool operator==(const GeneratorIterator& rhs) {return m_pos==rhs.m_pos;}
      bool operator!=(const GeneratorIterator& rhs) {return m_pos!=rhs.m_pos;}
      double operator*() {return m_gen->get(m_pos);}
    };

    template<class G>
    class Generator
    {
    public:
        constexpr GeneratorIterator<G> begin()
        {
            return GeneratorIterator<G>(0,static_cast<G const *>(this));
        }
        constexpr GeneratorIterator<G> end()
        {
            return GeneratorIterator<G>(G::size(),static_cast<G const *>(this));
        }
    };

Here I have a very simple implementation of an iterator. It is not all that clean as it is technically a const iterator because it read sthe values by copy as they are doubles. However, it will do and nicely illustrates the CRTP. The Generator class is the recursive template. It provides the begin() and end() methods which are required for most iteration. These are the methods required to allow for(x:y) semantics in C++11 style iterator loops.

The trick is that as a programmer we know that when Generator is instantiated it is actually a child class of its self. When the template argument is that child we can statically cast to the child and therefore create the appropriate iterator over the child. The child is accessed from the iterator by the child having a pointer to the generator. This could be done slightly more cleanly with a reference, but it was easier to directly cast the this pointer.

Here is an example of the child class:

template<typename A,typename B>
    class MixGenerator : public Generator<MixGenerator<A,B>>
    {
        const A& m_a;
        const B& m_b;
    public:
        MixGenerator(const A& a,const B& b):m_a(a),m_b(b){}
        double get(size_t index) const
        {
            return m_a.get(index)+m_b.get(index);
        }

        static constexpr size_t size()
        {
            static_assert(A::size()==B::size(),"Size match in mix");
            return A::size();
        }
    };

Here are some tests to show this stuff works:

    void testIterator()
    {
        startGroup("Iterator");
        ArrayGenerator<12345> gen;
        double accumea(0);
        for(size_t i(0);i<gen.size();++i)
        {
            gen.set(i,i+0.1);
            accumea+=i+0.1;
        }
        auto it=gen.begin();
        assertEqual("Begin  :",(double)0.1,*it);
        auto end=gen.end();
        assertEqual("--End  :",(double)12344.1,*(--end));
        double accumeb(0);
        for(auto v:gen)
        {
            accumeb+=v;
        }
        assertEqual("Sum 1  :",accumea,accumeb);
        accumeb=0;
        for(auto it=gen.begin();it!=gen.end();++it)
        {
            accumeb+=*it;
        }
        assertEqual("Sum 2  :",accumea,accumeb);

        gen.set(0,-1);
        assertEqual("Begin++:",*(gen.begin())++,-1);

        gen.set(1,-2);
        assertEqual("++Begin:",*(++(gen.begin())),-2);

        gen.set(2,-3);
        auto it1=gen.begin();
        ++it1;
        ++it1;
        auto it2=it1--;

        assertEqual("++++--:",*it2,-3);
        assertEqual("++----:",*it1,-2);

    }

Functional C++ : Approaching Fibonacci From The Correct End

Wikicommons - see here

Writing an efficient computation for the Fibonacci is apparently a common interview question: Here I ruin this with a very, very simple constexpr.


How can the fibonacci numbers be anything but trivial to work out? I cannot remember when I first implemented a piece of code to do it; the reason being I was probably 10 or 11 years old at the time. Somehow, educating people in computer science ruins their ability to do things simply (not really, but it can sometimes...). For me, computing Fibonacci is mechanical, we take an number and add another number and so on. For those trained in the fine arts of comp'sci' it is a functional problem. As with all things functional, it has a habit of not mapping onto Von Neumann machines very well...

Functionally fibonacci is this:

Fn = Fn-1 + Fn-2
F0 = 1
F1 = 1

This is the root of the problem - IT IS BACKWARDS!

I am pretty sure Fibonacci himself did not use functional syntax to define his series, so why should we?

The easy way to compute fibonacci is to work up from 0 not down from n. It is really hard to code it in a simple way to count down as we are doing a double iteration. We recurse (a form of iteration) down over the definitions form n to 0 then we iterate back up them to compute the value. Why not just compute the value in one iteration?

Here is my solution (works on g++ 4.9):

#pragma once

namespace funcs
{
    constexpr size_t fibonacci_inner(size_t t1,size_t t2,size_t index,size_t n)
    {
        return n==index?t1+t2:fibonacci_inner(t2,t1+t2,index+1,n);
    }

    constexpr size_t fibonacci(size_t n)
    {
        return n<2?1:fibonacci_inner(0,1,1,n);
    }

    static_assert(fibonacci(0)==1,"fibonacci(0)");
    static_assert(fibonacci(1)==1,"fibonacci(1)");
    static_assert(fibonacci(2)==2,"fibonacci(2)");
    static_assert(fibonacci(3)==3,"fibonacci(3)");
    static_assert(fibonacci(4)==5,"fibonacci(4)");
    static_assert(fibonacci(5)==8,"fibonacci(5)");

}

The trick, if one wants to call it such, is not to conflate the concept of termination with the calculation its self. By simply passing index and n to each recursion of the series we make a tail call version of the a simple imperative loop starting at the 0 and ending at the required value for the calculation.