Массив и автоматическая векторизация указателя в gcc

Question

Я пытаюсь использовать авто-векторизацию с g ++ 5.4 (-ftree-vectorize). Я заметил, что версия массива в коде ниже чего-то заставляет компилятор упустить возможность векторизации во внутреннем цикле, что приводит к значительной разнице в производительности по сравнению с версией указателя. Можно ли что-нибудь сделать, чтобы помочь компилятору в этом случае?

void floydwarshall(float* mat, size_t n) {
#if USE_POINTER
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            auto v = mat[i*n + k];
            for (int j = 0; j < n; ++j) {
                auto val = v + mat[k*n+j];
                if (mat[i*n + j] > val) {
                    mat[i*n + j] = val;
                }
            }
        }
    }
#else // USE_ARRAY
    typedef float (*array)[n];
    array m = reinterpret_cast<array>(mat);
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            auto v = m[i][k];
            for (int j = 0; j < n; ++j) {
                auto val = v + m[k][j];
                if (m[i][j] > val) {
                    m[i][j] = val;
                }
            }
        }
    }
#endif
}

Answer 1

Обе версии делают векторизацию, с g++5.4 -O3 -march=haswellиспользование vcmpltps/vmaskmovps во внутреннем цикле по причине, которую указывает Марк.

Если вы не позволите компилятору использовать инструкции AVX, это будет сложнее. Но я не вижу ни одну версию векторизации вообще, если я просто использую -O3 (так что доступен только SSE2, так как он является базовым для x86-64). Итак, ваш оригинальный вопрос основан на результате, который я не могу воспроизвести.

Изменение if() на троичный оператор (чтобы код всегда сохранялся в массиве) позволяет компилятору загружать / MINPS / безоговорочно сохранять. Это большой трафик памяти, если ваша матрица не помещается в кеш; Может быть, вы можете расположить петли по-другому? Или, может быть, нет, так как m[i][k] нужен, и я предполагаю, что имеет значение, в каком порядке все происходит.

Если обновления происходят очень редко, а обратная запись "грязных" данных является причиной узкого места в памяти, возможно, стоит даже разветвиться, чтобы избежать сохранения, если ни один из векторных элементов не был изменен.

---

Вот версия массива, которая хорошо векторизуется, даже с использованием только SSE2. Я добавил код, чтобы сообщить компилятору, что вход выровнен и размер кратен 8 (число с плавающей точкой на вектор AVX). Если ваш реальный код не может сделать эти предположения, то уберите эту часть. Это облегчает поиск векторизованной части, потому что она не скрыта в скалярном вводном / чистом коде. (С помощью -O2 -ftree-vectorize не полностью развернуть код очистки таким образом, но -O3 делает.)

Я заметил, что без AVX gcc по-прежнему использует невыровненные загрузки, но выровненные хранилища. Может быть, он не понимает, что размер, кратный 8, должен m[k][j] выровнен, если m[i][j] выровнен? Это может быть разница между версией указателя и версией массива.

код в проводнике компилятора Godbolt

void floydwarshall_array_unconditional(float* mat, size_t n) {

    // try to tell gcc that it doesn't need scalar intro/outro code
    // The vectorized inner loop isn't particularly different without these, but it means less wading through scalar cleanup code (and less bloat if you can use this in your real code).

    // works with gcc6, doesn't work with gcc5.4
    mat = (float*)__builtin_assume_aligned(mat, 32);
    n /= 8;
    n *= 8;         // code is simpler if matrix size is always a multiple of 8 (floats per AVX vector)

    typedef float (*array)[n];
    array m = reinterpret_cast<array>(mat);

    for (size_t k = 0; k < n; ++k) {
        for (size_t i = 0; i < n; ++i) {
            auto v = m[i][k];
            for (size_t j = 0; j < n; ++j) {
                auto val = v + m[k][j];
                m[i][j] = (m[i][j]>val) ? val : m[i][j];   // Marc's suggested change: enables vectorization with unconditional stores.
            }
        }
    }
}

gcc5.4 не удается избежать скалярного кода ввода / очистки вокруг векторизованной части, но gcc6.2 делает это. Векторизованная часть в основном одинакова для обеих версий компилятора.

## The inner-most loop (with gcc6.2 -march=haswell -O3)
.L5:
    vaddps  ymm0, ymm1, YMMWORD PTR [rsi+rax]
    vminps  ymm0, ymm0, YMMWORD PTR [rdx+rax]     #### Note use of minps and unconditional store, enabled by using the ternary operator instead of if().
    add     r14, 1
    vmovaps YMMWORD PTR [rdx+rax], ymm0
    add     rax, 32
    cmp     r14, r13
    jb      .L5

Следующий цикл снаружи, который выполняет некоторую проверку целочисленного счетчика (используя некоторые вещи setcc) и выполняетvmovss xmm1, DWORD PTR [rax+r10*4] и отдельный vbroadcastss ymm1, xmm1, Предположительно, скалярная очистка, к которой он подключается, не нуждается в трансляции, и gcc не знает, что в целом будет дешевле использовать VBROADCASTSS в качестве нагрузки, даже если часть трансляции не нужна.