Tips for Geeks, Part 1

So, tip number one: iterating over a byte array.

At first glance, what could be simpler? For example, summing all the bytes of an array in C++:

int summ(char * data, size_t length)
{
    int result = 0;
    for(size_t i=0;i<length;i++)
        result+=data[i];
    return result;
}

To any sane person I’d recommend leaving this code exactly as it is. It runs very fast on modern computers and is perfectly readable to boot.
But if you remember that we live in the age of 32-bit computing, with 64-bit already knocking on the door, operating on 8-bit numbers starts to feel a bit unserious and wasteful.
I’ll skip the long-winded reasoning and go straight to the final code:

int summ(char * data, size_t length)
{
    int result = 0;
    int nlength = length & ~3;

    size_t i = 0;
    for(; i < nlength; i += 4)
        for(size_t j=0; j < 4; j++)
            result += data[i + j];

    for(; i < length; i++)
        result += data[i];

    return result;
}

As you can see from the code, the array traversal is split into two big loops, and for instance when length = 18, the first loop runs from 0 to 15, and the second from 16 to 17. The inner loop over j will be unrolled into offset assignments by literally any compiler, so there’s no need to worry about it.
The code above is roughly one and a half times faster than a plain byte-by-byte scan, but it’s also a lot less readable. You’d get an even better result using a stride of 8 bytes instead of 4, though the gain becomes less noticeable at that point. And if the task isn’t just to compute a sum but to do some on-the-fly encryption (XOR with a constant or the element’s index, etc.), then performance will end up depending on the inner operations themselves rather than on how the traversal is organized. And the more complex the code gets, the more mistakes you can make in it.

So the moral of the story is:

Premature optimization is the root of all evil. (c) Knuth, Donald. 1974

I’d recommend an awful lot of people print out this axiom and hang it on the wall in the most visible spot they can find.