Оптимизировать вложенные циклы для заполнения массива шаблонами, чтобы помочь компилятору создать эффективную сборку ARM?

Question

Мне только что дали задание переписать следующую функцию C, чтобы помочь компилятору ARM создавать более эффективный код сборки. Кто-нибудь знает как это сделать?

void some_function(int *data)
{
    int  i, j;

    for (i = 0; i < 64; i++)
    {
        for (j = 0; j < 64; j++)
            data[j + 64*i] = (i + j)/2;
    }
}

Answer 1

Оптимизация кода C для генерации "более эффективного кода сборки" для указанного c компилятора / процессора - это то, что вы обычно не должны делать. Напишите ясный и простой для понимания код C и позвольте компилятору выполнить оптимизацию.

Даже если вы делаете все виды трюков с кодом C и в итоге получаете "более эффективный код сборки" для вашего Если указать c компилятор / процессор, может оказаться, что простое обновление компилятора может все испортить, и вам придется снова изменить код C.

Для чего-то столь же простого, как ваш код, напишите это в коде ассемблера с самого начала. Но имейте в виду, что вам нужно быть настоящим экспертом в этом языке процессора / ассемблера, чтобы победить достойный компилятор.

В любом случае ... Если мы хотим догадаться, это мое предположение:

void some_function(int *data)
{
    int  i, j, x;

    for (i = 0; i < 64; i++)
    {
        // Handle even i-values
        x = i/2;
        for (j = 0; j < 64; j += 2)
        {
            *data = x;
            ++data;
            *data = x;
            ++data;
            ++x;        // Increment after writing to data twice
        }

        ++i;

        // Handle odd i-values
        x = i/2;
        for (j = 0; j < 64; j += 2)
        {
            *data = x;
            ++data;
            ++x;        // Increment after writing to data once
            *data = x;
            ++data;
        }
    }
}

Идея состоит в том, чтобы 1) заменить индексирование массива приращениями указателя и 2) заменить (i+j)/2 целочисленными приращениями.

У меня нет сделано какое-либо измерение поэтому я не могу точно сказать, что это будет хорошим решением. Я оставлю это OP.

---

Та же идея, что и выше, но с еще несколькими настройками (предложено @ user3386109)

void some_function(int *data)
{
    for (int i = 0; i < 32; i++)
    {
        // when i is even, the output is in matched pairs
        int value = i;
        for (int j = 0; j < 32; j++)
        {
            *data++ = value;
            *data++ = value++;
        }

        // when i is odd, the output starts with a singleton
        // followed by matched pairs, and ending with a singleton
        value = i;
        *data++ = value++;
        for (int j = 0; j < 31; j++)
        {
            *data++ = value;
            *data++ = value++;
        }
        *data++ = value;
    }
}

Answer 2

Во-первых (как упоминал Джонатан Леффлер), компилятор, вероятно, уже делает такую ​​хорошую работу, что попытка оптимизации путем написания указанного c C кода обычно коммерчески сомнительна, то есть вы теряете больше денег за время разработки, чем вы может сделать код немного быстрее.
Но иногда это того стоит; давайте предположим, что это так.

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

Хорошо, после этого мудрого взлома приведен код, в котором я демонстрирую оптимизацию, предложенную в комментариях. из них Джонатаном Леффлером:

/* Jonathan Leffler */
void some_function(int *data)
{
    int  i, j;
    int  k = 0;

    for (i = 0; i < 64; i++)
    {
        for (j = 0; j < 64; j++)
        {
            data[k++] = (i + j)/2;
        }
    }
}

/* Yunnosch 1, loop unrolling by 2 */
void some_function(int *data)
{
    int  i, j;

    for (i = 0; i < 64; i++)
    {
        for (j = 0; j < 64; j+=2)
            data[j +     64*i] = (i + j  )/2;
            data[j + 1 + 64*i] = (i + j+1)/2;
    }
}

/* Yunnosch 1 and Jonathan Leffler */
void some_function(int *data)
{
    int  i, j;
    int k=0; /* Jonathan Leffler */

    for (i = 0; i < 64; i++)
    {
        for (j = 0; j < 64; j+=2) /* Yunnosch */
        {
            data[k++] = (i + j  )/2;
            data[k++] = (i + j+1)/2; /* Yunnosch */
        }
    }
}

/* Yunnosch 2, avoiding the /2, including Jonathan Leffler */
/* Well, duh. This is harder than I thought... 
   I admit that this is NOT tested, I want to demonstrate the idea.
   Everybody feel free to help the very grateful me with fixing errors. */
void some_function(int *data)
{
    int  i, j;
    int  k=0;

    for (i = 0; i < 32; i++) /* magic numbers I normally avoid, 32 is 64/2 */
    {
        for (j = 0; j < 32; j++)
        {
            data[k     ] = (i + j);
            data[k+1   ] = (i + j);
            data[k  +64] = (i + j);
            data[k+1+64] = (i + j +1);
            k+=2;
        }
        k+=64;
    }
}

Последняя версия основана на следующем наблюдаемом шаблоне групп 2x2 в желаемом результате, как видно из 2D-интерпретации:

00 11 ...
01 12 ...

11 22 ...
12 23 ...
.. ..
.. ..
.. ..
´´´´