Notes

I just spent a day tracking down a nasty MPI bug in some fluids code, and the cause is amusing enough to record. A process was interleaving message receives from two of its neighbors, one above and one to the right. Each message contained a band of data one grid cell thick. Both messages were sending into the same array, so the two regions intersected at the corner of the domain.

This worked fine under LAM/MPI, but broke when we switched to OpenMPI. Presumably LAM was receiving one message at a time and returning control to the calling code, and OpenMPI decided to receive both messages at once. Since the message destinations overlapped in memory, the second message trounced the value of the first at the single overlapping corner cell.

For a while I thought the problem was a compiler bug, since switching to debug mode or adding print statements in the relevant area of code caused it to vanish. Fun.

Edit: (30may2009) I need more practice making figures, so I added one.

Something just occurred to me about the gcc implementation of std::vector in C++. Internally, an instance of vector needs to store (1) a pointer to the start of the memory, (2) the current vector size, and (3) the current buffer size. However, (2) and (3) can be represented either as integers relative to the start pointer or as absolute pointers past the end of the active and buffer spaces. Specifically, the two representations are

    template <class T>
    struct relative {
        T* start;
        size_t size, buffer_size;
    };

and

    template <class T>
    struct absolute {
        T* start;
        T* end; // = start + size
        T* buffer_end; // = start + buffer_size
    };

The relative integer representation seemed more natural, so it’s always struck me as odd that gnu stdc++’s vector class used the absolute representation.

What just occurred to me is that the absolute representation is better from a strict aliasing standpoint, since arrays of pointers are much less common than arrays of integers. This potentially gives the compiler more knowledge with which to optimize. For example, consider the following implementation of copy:

    void copy(vector<size_t>& dest, const vector<size_t>& src)
    {
        for(size_t i=0;i<src.size();i++)
            dest[i] = src[i];
    }

If the compiler is allowed to assume strict aliasing and vector<size_t> uses the absolute representation, it knows that the write to dest can’t change the value of src.size(), which allows the loop bound to be computed at the start of the loop. However, if the relative representation is used, nothing tells the compiler that dest.start != &src.size. If a write to dest[i] might change the value of size, the compiler has to repeat the memory lookup during every iteration of the loop, which prevents all interesting loop optimizations.

P.S. Someone pointed out that I forgot to define “strict aliasing”. Strict aliasing means that it is invalid in C++ to access the same memory through pointers of different types, and in particular that the compiler is allowed to make this assumption when optimizing. See the Wikipedia page for more details.