Может ли этот альтернативный способ зацикливаться быть более эффективным?

Question

В один дождливый день мне было скучно, и я придумала:

int ia_array[5][5][5]; //interger array called array

{
        int i = 0, j = 0, k = 0;//counters
        while( i < 5 )//loop conditions
        {
            ia_array[i][j][k] = 0;//do something
            __asm inc k;//++k;

            if( k > 4)
            {
                __asm inc j;  //++j;
                __asm mov k,0;///k = 0;
            }
            if( j > 4)
            {
                __asm inc i;  //++i;
                __asm mov j,0;//j = 0;
            }
        }//end of while
    }//i,j,k fall out of scope

это функционально эквивалентно трем вложенным циклам. Однако в цикле for нельзя использовать операторы __asm. Также у вас есть возможность не помещать счетчики в область видимости, чтобы вы могли использовать их для других циклов. Я посмотрел на разборку для обоих, и у моей альтернативы есть 15 кодов операций, а для вложенных циклов - 24. Поэтому потенциально ли это быстрее? предположим, я действительно спрашиваю __asm ​​inc i; быстрее, чем ++ я;?

примечание: я не собираюсь использовать этот код в каких-либо проектах, просто из любопытства. спасибо за ваше время.

Answer 1

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

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

В этом случае, например,Вы можете, по крайней мере, иметь шанс, заметив, что iarray[5][5][5] может (с точки зрения языка ассемблера) рассматриваться как один плоский массив из 5 * 5 * 5 = 125 элементов и кодировать большую часть того, что по сути является memset, вединственная инструкция:

mov ecx, 125    // 125 elements
xor eax, eax    // set them to zero
mov di, offset ia_array // where we're going to store them
rep stosd       // and fill that memory.

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

Следующим шагом будет рассмотрение вопроса о том, чтобы использовать временные хранилища вместо простого stosd.Это на самом деле не ускорит этот цикл (во всяком случае, сильно), но в целом он может набрать некоторую скорость, избегая того, чтобы это хранилище загрязняло кеш, если возможно, что другой код, уже находящийся в кеше, сразу важнее.Вы также можете использовать некоторые другие инструкции SSE, чтобы набрать небольшую скорость, но даже в лучшем случае вы не можете ожидать намного лучше, чем пара процентов из этого.Суть в том, что для обнуления некоторой памяти скорость ограничивается, прежде всего, скоростью шины, а не инструкциями, которые вы используете, поэтому ничто из того, что вы делаете, скорее всего, не очень поможет.

Answer 2

Несколько вещей:

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

2. Помещая в ваш код операторы __asm, вы, вероятно, исключаете любые оптимизации, которые компилятор может выполнить в цикле. Поэтому, если вы скомпилируете это с помощью чего-то очень быстрого, например, скажем, компиляторов Intel, то, скорее всего, производительность вашего кода будет хуже, чем с компилятором. Это особенно верно для чего-то столь же простого, как ваш код здесь, где размеры массива известны статически, а границы цикла постоянны.

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

Существует множество ядер и кодов обработки чисел, в которых компиляторы все еще не могут работать лучше, чем знающие люди, но без большого опыта работы с деталями архитектуры вы не добьетесь гораздо большего успеха, чем icc -fast или xlC -O5.

Answer 3

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

Answer 4

Во-первых, ваш компилятор, скорее всего, будет хранить значения i, j и k в регистрах.

Более эффективно делать for (i = 4; i <=0; i--), чем for(i = 0; i < 5; i++), поскольку процессор может определить, был ли результат последней выполненной операции нулевым бесплатно - ему не нужно явно сравнивать с 4 (см. cmovz инструкция).

В x86 дело не в том, что выполнение меньшего количества команд приведет к более быстрому коду. Существуют всевозможные проблемы, связанные с конвейерной обработкой команд, которые программисту приходится слишком много писать вручную. Предоставьте это компилятору, в наши дни они достаточно эффективны (хотя определенно не оптимальны ... но кто хочет часами ждать, пока их код скомпилируется).

Вы можете проверить это самостоятельно, запустив свою функцию несколько сотен тысяч раз с каждой реализацией и проверив, что быстрее. Проверьте, можете ли вы написать asm-инструкции для циклов с

__asm {
    inc j;
    mov k, 0;
}

(прошло уже много времени с тех пор, как я это сделал)

P.S. Весело экспериментируйте с asm, это может быть очень интересно и полезно!

Answer 5

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