Развертывание вложенного цикла в C

Я не уверен, в чем ошибка вашего текущего кода, но вот еще один подход.

void transpose(int dim, int *src, int *dst) {
    int i, j;

    for (i = 0; i <= dim-8; i += 8)
    {
        for (j = 0; j < dim; j++)
        {
                dst[j * dim + (i+0)] = src[(i+0) * dim + j];
                dst[j * dim + (i+1)] = src[(i+1) * dim + j];
                dst[j * dim + (i+2)] = src[(i+2) * dim + j];
                dst[j * dim + (i+3)] = src[(i+3) * dim + j];
                dst[j * dim + (i+4)] = src[(i+4) * dim + j];
                dst[j * dim + (i+5)] = src[(i+5) * dim + j];
                dst[j * dim + (i+6)] = src[(i+6) * dim + j];
                dst[j * dim + (i+7)] = src[(i+7) * dim + j];
        }
    }

    // Use the normal loop for any remaining elements   
    for (; i < dim; i++)
        for (j = 0; j < dim; j++)
            dst[j * dim + i] = src[i * dim + j];
}

Примечание. Количество умножений можно уменьшить, введя переменную, например:

int jdim = j * dim + i;
dst[jdim + 0] = ...
dst[jdim + 1] = ...
...
dst[jdim + 7] = ...

и так же для RHS.

Вся цель развертывания циклов состоит в том, чтобы удалить тесты. Вы не делаете никаких предположений о значении dim, поэтому вам нужно сохранить все тесты. Я сомневаюсь, что вы увидите какие-либо улучшения с развернутым кодом, но только тщательный бенчмаркинг может сказать вам для данного компилятора и архитектуры, если это имеет значение.

Одно можно сказать наверняка: это сделало код намного труднее для чтения и его было намного легче испортить.

Если вы знаете наиболее распространенные значения dim, вы можете попытаться оптимизировать их. Например, если вы знаете, что наиболее распространенным случаем являются матрицы 3x3, вы можете написать это:

void transpose(int dim, const int *src, int *dst) {
    if (dim == 3) {
        dst[0 * 3 + 0] = src[0 * 3 + 0];
        dst[0 * 3 + 1] = src[1 * 3 + 0];
        dst[0 * 3 + 2] = src[2 * 3 + 0];
        dst[1 * 3 + 0] = src[0 * 3 + 1];
        dst[1 * 3 + 1] = src[1 * 3 + 1];
        dst[1 * 3 + 2] = src[2 * 3 + 1];
        dst[2 * 3 + 0] = src[0 * 3 + 2];
        dst[2 * 3 + 1] = src[1 * 3 + 2];
        dst[2 * 3 + 2] = src[2 * 3 + 2];
    } else {
        for (int i = 0; i < dim; i++) {
            for (int j = 0; j < dim; j++) {
                dst[j * dim + i] = src[i * dim + j];
            }
        }
    }
}

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

Вот пример развернутого цикла. Обратите внимание, что цель состоит в том, чтобы удалить условные операторы и зависимости от переменных. Кроме того, этот код не был протестирован.

void transpose(int dim, int *src, int *dst) {
    // represent where the data is being read and where it is going
    int dstIndex = 0;
    int srcIndex = 0;

    // precalculate constants used within the loop
    int total = dim*dim;
    int unrolled = dim / 4;

    int dimx0 = dim*0;
    int dimx1 = dim*1;
    int dimx2 = dim*2;
    int dimx3 = dim*3;
    int dimx4 = dim*4;

    int i = 0;
    int j = 0;

    // since the matrix is being transposed i,j order doesn't matter as much
    // because one of the matrices will be accessed by column and the other
    // will be accessed by row (more effecient)
    for (j = 0; j < dim; j++) {
        for (i = 0; i < unrolled; i++) {
            // here the loop is being unrolled
            // notice that each statement does not rely on previous statements
            // and there is no conditional code
            dst[dstIndex + 0] = src[srcIndex + dimx0];
            dst[dstIndex + 1] = src[srcIndex + dimx1];
            dst[dstIndex + 2] = src[srcIndex + dimx2];
            dst[dstIndex + 3] = src[srcIndex + dimx3];
            dstIndex += 4;
            srcIndex += dimx4;
        }

        // the transpose was previously completed in larger blocks of 4
        // here whtever indices that were not transposed will be taken care of
        // e.g. if the matrix was 13x13, the above loop would run 3 times per row
        // and this loop would run once per row
        for (i = unrolled; i < dim; i++) {
            dst[dstIndex] = src[srcIndex];
            dstIndex += 1;
            srcIndex += dim;
        }

        // increment the source index
        srcIndex %= total;
        srcIndex += 1;
    }
}