Hardware prefetching in Pentium III §

The test §

The thing I want to test is whether or not Pentium III's prefetcher, if existent and effective, can handle accessing memory linearly with large variable strides. The first algorithm with such an access pattern that came to my mind was Shell sort. When used with the 3-smooth numbers (i.e. numbers of the form 2^p3^q, with natural p and q) as the gap sequence, its time complexity is O(nlog²n), which is practical even for large values of n.

As a comparison baseline the obvious choice is then heap sort, due to its infamy for being extremely cache-hostile and already being available in the C++ standard library. In fact, if comparisons and swaps are cheap, heap sort's cache hostility can and does make up for its theoretical complexity advantage, making it not much faster than 3-smooth Shell sort. On my Core i5-4590 (Haswell) the difference between the two algorithms is indeed less than a factor of two:

Shell (interactive)
$ g++ -O3 p3-prefetch-shell-sort.cc && time ./a.out # heap sort
./a.out  2,77s user 0,00s system 99% cpu 2,771 total
$ g++ -O3 -DUSE_SHELL_SORT p3-prefetch-shell-sort.cc && time ./a.out # Shell sort
./a.out  4,52s user 0,00s system 99% cpu 4,517 total

The implementation of Shell sort has been lifted from Wikipedia and C++-ified with no other significant changes:

C++
void shell_sort(std::uint32_t* array, std::size_t length)
{
    if(length <= 1) {
        return;
    }

    auto current_gap = std::find_if(std::begin(gaps), std::end(gaps),
        [&](std::size_t gap){return gap >= length;});
    do {
        --current_gap;
        const auto gap = *current_gap;
        for(std::size_t i = gap; i < length; ++i) {
            auto temp = std::move(array[i]);
            std::size_t j = i;
            for(; j >= gap && array[j - gap] > temp; j -= gap) {
                array[j] = std::move(array[j - gap]);
            }
            array[j] = std::move(temp);
        }
    } while(current_gap > std::begin(gaps));
}

The complete source of the benchmark program is available under the CC0 license.

With that code, a Coppermine Pentium III at 1 GHz (thanks to daemon32 for running the test!), a Tualatin Pentium III at 1.13 GHz, a Dothan Pentium M at 1.6 GHz for comparison purposes, GCC 8, Intel's performance event register reference, and the excellent Linux perf tool, let's go measuring.

The results §

There is a problem. The Intel performance monitoring event reference doesn't mention anything about prefetching in its P6 chapter! Prefetching events are mentioned in the Pentium M reference, however, and considering P6 family history, it's not unreasonable to believe the same events would be used in Pentium III. These events are, in syntax suitable for perf stat -e, cpu/event=0xf0,name=upward-prefetches/ and cpu/event=0xf8,name=downward-prefetches/. They count the number of prefetch requests, and therefore the number of prefetched cache lines. This will be important later on.

So first things first: these events don't report anything on Coppermine, always showing zeros. This adds credence to the idea that Coppermine and earlier P6 models didn't have hardware prefetching unit. On Tualatin, however, things are more interesting, so without further ado, let's dive into the performance counter stats!

The conclusion §

This test shows that the legends are true. Coppermine doesn't have automatic hardware prefetching, and thus presumably Katmai and older P6 processors don't either. It was introduced in a limited, but functional, form in Tualatin: hardware prefetching only works for ascending addresses, and is limited by slow memory interface, but can handle variable strides, and even the undocumented performance events appear to function correctly.