One size fits all

As an amateur chess player I occasionally watch videos on the subject on youtube. Just as it happens I watched one old video of GM Ben Finegold on isolated queen pawn positions the other day. He started with explaining that most people don't like such positions, because beginners tend to be dogmatic. They are taught a number of rules like ‘isolated pawns are bad’, ‘knights before bishops’ and so on, and they like to stick to the rules without regard to context. So that is when it struck me, we tend do the same in programming, especially true in the case of people with limited experience. That rigid thinking however doesn't do well neither in chess nor in C++.

My favorite object to rant about these days is the beloved by beginners and advanced alike “design patterns” pattern. This was all started by the famous book by the same name written by the so called “gang of four”^[1]. I, being pretty active the last year in the Qt forums, often encounter questions on the topic of design patterns from other users. So I decided to write this very post, where I hope the shed some light on the issue.

As programmers we often encounter similar problems as work progresses along which are solved pretty much the same way, and as humans we love to generalize. So that is the whole premise behind the aforementioned book, to show that a set of similar problems have a corresponding set of “good” solutions. This, of course, is generally true, but many people, especially the ones well conditioned to rigid thinking and/or those with limited experience, are ready to jump overboard and just apply it to every situation, always. So in reality this creates a very profound problem, not only are some patterns inapplicable to certain contexts, but people tend to bend over backwards in their wish to apply them, thus creating a vile mess in the process.

The original ideas were posed for Java, and while it pains me to say it constantly, C++ is not Java. Some of the proposed solutions are inappropriate to be applied directly to C++, or become much more complex if one tries to adapt them. This naturally stems from the fact that C++ is a lower-level language, albeit still object oriented, and as such has a lot of peculiarities that are not relevant to other languages.

A typical example of misunderstanding is the singleton pattern, where only one instance of an object is created, initialized and used. This pattern (or as I lovingly call it: “The singleton antipattern”) has gained widespread use for no good reason. The idea behind it is supposedly to restrict the programmer to using a single instance of a given class. There are a number of pitfalls with this, however:

1. Having a singleton class imposes that you have only one object of that class, conversely needing one object does not sum up to requiring the class to be singleton(ian). If you need one instance of something, just create one!
2. The singleton creates extremely tight coupling between the classes that use it. Think a C global variable. In fact the singleton is just that – a global variable dressed in shiny clothes (i.e. it has methods). The same results one can get by using a number of global functions that make use of a global variable.
3. As a consequence of 1 and 2, the singleton introduces an application global state, which might be hard to manage depending on the context.
4. A C++ specific problem is that most singleton implementations leak memory. Java has no such problem as the memory is managed by its virtual machine, in C++ this may be problematic.
5. A lazy initialization singleton implementation must be explicitly made thread-safe in case the initialization might be done concurrently.

So what the singleton has to show for in return – imposing a single instance.

Other patterns described in the book and on the internet also suffer similarly and the reason is: there is no one-size-fits-all in programming.
Don't be dogmatic, evaluate the context level-headedly and only then settle on a solution.

---

[1] Gamma, E., Helm, R., Johnson, R., Vlissides, J., Design Patterns - Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995.

OpenMPI and qmake

For a project I'm developing I want to use OpenMPI and the Qt toolkit. Naturally, this would mean that I'd like to use QtCreator with the qmake's build chain as well. OpenMPI recommends using their wrapper compiler/linker instead of the default one, so I needed to make aware the qmake system of this. It is possible to change the compiler on a per-project basis, but after reading a bit on qmake, I've decided to solve this a bit more elegantly.

qmake supports features that can be used in different projects by just adding a configuration entry. I've created such a feature and added it as a git repository here: https://bitbucket.org/nye/qmake-openmpi-feature.git. To make qmake aware of a feature one has only to put the .prf file in $QTDIR/mkspecs/features and it's ready to use. To use the OpenMPI compiler/linker just add the following configuration entry to your project file:

CONFIG += openmpi

Count your pluses

This text is a continuation of the “Bubblin' up” post regarding floating point operations, and more specifically here I will explore how to properly sum such numbers. The problem presented is, that because of the specific representation of floating point numbers, every operation done on them is inherently imprecise. Additionally, even if it is assumed that the operations carry no error at all, there is a problem with storing the number. If the number can't be exactly represented in the specified floating point format (as discussed in the previous post), naturally a truncation error will be imposed. What does that mean? Firstly, do not trust floating point numbers. Yes, the statement is a bit exaggerated, but it is a good practice to always keep in mind that floating point numbers are just an approximation. And secondly, special care should be taken when working with them.

Truncation, as unseemly as it may appear, is inevitable because of the discreteness of computer memory. Nothing can be done about it, there is no computer with an infinite amount of memory. Here the machine epsilon arises as a natural measurement of the least significant number (in sense of mantissa bits) representable in a specific architecture. Rounding errors are a consequence of truncation and occur because no number can be represented in computers with an infinite amount of significant digits, meaning all floating point operations are approximate and need be rounded, hence the name. By design the machine epsilon is the upper bound on the relative error associated with rounding in floating point arithmetic.

All that said, summation is a classical problem illustrating the accumulation of error. Every addition will carry an error into the result, and even if the error is not large, the accumulation might be significant when adding many terms. Furthermore, because computers normalize the numbers (see wikipedia), if the values' exponents differ much, the smaller numbers' contributions might not be reflected in the sum at all! Although the problem is known, the solution is not as obvious or trivial as it might seem. So lets consider and compare few approaches (error estimations will not be derived, but only presented):

1. The naïve approach consists of just adding up the numbers in an accumulator. The accumulated error will grow linearly on the number of terms – O(n). A snippet in C++ illustrating the method is presented:

double doNaiveSum(double * numbers, int size)
{
    double sum = 0;
    for (int i = 0; i < size; i++)
        sum += numbers[i];
    return sum;
}

2. The naïve approach with presorting in which the numbers are sorted by absolute value before summing them. This case is very similar to the previous one, so no code snippet will be provided. The idea is to sum smaller numbers first so their contribution is not lost. The performance is only marginally better than the former case and the benefit is not guaranteed but depends heavily on the magnitude of the numbers, which might vary to a large degree in different applications.

3. Pairwise summation is a divide and conquer algorithm which consists in dividing each range by half, summing recursively each half and then adding the results. The method offers significant improvement over the naïve approach. The error grows logarithmically O(log(n)) for a minute increase in arithmetic operations. A minor inconvenience is that the natural implementation is recursive. Consider the following example code:

double doPairwiseSum(double * numbers, int size)
{
    if (size < 4)  {  // For 3 numbers or less just perform the regular summation
        double sum = 0;
        for (int i = 0; i < size; i++)
            sum += numbers[i];
        return sum;
    }

    // Calculate the left part size as half the original size, and the right part size as the reminder
    int leftSize = (size >> 1), rightSize = size - leftSize;

    // Perform a recursive sum on each part and return the result
    return doPairwiseSum(numbers, leftSize) + doPairwiseSum(numbers + leftSize, rightSize);
}

4. Kahan summation is a compensated summation technique which uses a running compensation to reduce the numerical error. The idea is to keep an additional variable, where the low-order bits, which would be otherwise lost, can be stored. Although Kahan's algorithm achieves O(1) error growth (a constant not depending on the number of additions), additional operations are required which might not always be appropriate. In such a case pairwise summations is a viable alternative with its logarithmic error growth.

double doCompensatedSum(double * numbers, int size)
{  
    double sum = 0, compensation = 0;
    for (int i = 0; i < size; i++)  {
        // Adjust the input value with the stored compensation value (the low-order bits from previous operations)
        double x = numbers[i] - compensation;
        // Calculate the new value for the sum
        double tempSum = sum + x;
        // Recover the low-order bits lost in the last addition
        compensation = (tempSum - sum) - x;
        // Update the sum variable
        sum = tempSum;
    }
    return sum;
}

When using this algorithm beware of overly aggressive compilers, which could in principle recognize that arithmetically the compensation should always be zero and perform optimizations effectively removing its calculation.

5. Arbitrary precision arithmetic is a brute-force solution where no special care is (implicitly) taken to limit the error growth. For most intents and purposes one of the above (or similar) algorithms would be more appropriate, since arbitrary precision floating points are usually emulated in software (at least to my knowledge) and are carrying a lot of computational and memory overhead.