[gcc] ключи, оптимизация

Последний случай называется разворачиванием цикла и делает код как раз-таки более быстрым: за раз окучивается 16 элементов без накладных расходов на проверку условий и переходы.

>Последний случай называется разворачиванием цикла и делает код как раз-таки более быстрым: за раз окучивается 16 элементов без накладных расходов на проверку условий и переходы.
Ерунда.

В случае
        movaps  %xmm0, bullshit(%eax)
за одну итерацию цикла записывает 16 байт

В последнем случае 
        movb    $15, bullshit+N(%eax)
загоняет 1(один) байт 16 раз за одну итерацию. Это можно было бы назвать оптимизацией, если б у нас была 8-битная машина.

И объясните мне, чем 0 принципиально отличается от 15(или любого другого числа), что генерируется настолько разный код. 
Про отличая float от char я даже не спрашиваю..

если у тебя есть char * то он не обязан быть выровненным

alignment

>>Последний случай называется разворачиванием цикла и делает код как раз-таки более быстрым: за раз окучивается 16 элементов без накладных расходов на проверку условий и переходы.

>Ерунда.

>В случае > movaps %xmm0, bullshit(%eax) >за одну итерацию цикла записывает 16 байт

А вы не задумывались над тем, какова стоимость операции "jne .L2" для современного процессора? Первые проходы цикла будут оооочень дорогими, на порядки дороже разницы между movaps и 16-тью movb-ами.

Да и компилятор все таки лишен AI, что-бы оптимизировать все на 100%, конечно совместив развертку цикла и двиганье по 16 байт можно сильно выйграть, но опять-же - компилер не бох, а если вам нужно быстро заполнить что-то нулями, изойте memset, его реализация всегда обычно хорошо оптимизирована вручную в libc-ах

В данном случае компилятор это знает заранее. Почему в случае записи в массив 0 он считает его выравненым, а 15 - нет? Да и в случае невыровненного массива напрашивается менее нелепый код.

Кстати, если компилять под pentium-m, то код получается как и вдругих случаях, без movb.

PS: gcc 4.2.2 ситуация на этом примере та же

> Опции -O2 и -O3 для всех примеров делают код более раздутым и тревожным, но едва-ли более быстрым.

gcc version 4.1.3

-O2 -march=pentium3 -mtune=pentium3 -mmmx -msse -ftree-vectorize

.L2: xorps %xmm0, %xmm0 movaps %xmm0, bullshit(%eax) addl $16, %eax cmpl $1024, %eax jne .L2

>А вы не задумывались над тем, какова стоимость операции "jne .L2" для современного процессора? Первые проходы цикла будут оооочень дорогими, на порядки дороже разницы между movaps и 16-тью movb-ами.

Это только в начале, потом будет предсказание перехода, цикл с movb в итоге будет значительно медленней и неоправдано раздут. К тому же число итераций в данном случае - константа, довольно большая.

>конечно совместив развертку цикла и двиганье по 16 байт можно сильно выйграть,

В случае -funroll-all-loops он так и должен сделать. Но представьте тот 16*movb еще более развернутый :)

>а если вам нужно быстро заполнить что-то нулями, изойте memset,

Я об этом знаю, просто привел простейший пример. На более сложных он еще больше обосрется.

>.L2: xorps %xmm0, %xmm0 movaps %xmm0, bullshit(%eax) addl $16, %eax cmpl $1024, %eax jne .L2

Там по идее еще должен был появиться что-то вроде xorps %xmm0, %xmm0/movaps %xmm0, bullshit перед циклом - сэкономили на одном условном переходе. Но xorps %xmm0, %xmm0 опять внутри.

А теперь покажите тоже самое, когда заполняется не нулем.

а слабо бенчмарк сделать? Чтобы споров не было кто умнее, ты или разработчики gcc.

Всё ясно тут. Скорее всего оптимизация заполнения массива нулём в цикле
реализована специально, так как такой код частый, и реализуется просто
операцией xor на регистрах mmx. Заполнение константой, отличной от нуля,
не оптимизируется, так как это встречается редко и реализация будет
посложнее: нужно все 16 байтов регистра mmx сначала заполнить значениями
0x0F, а это будет намного сложнее xor.

И ещё, предполагаю, что процессор может выполнить инструкции

movb    $15, ullshit+1(%eax)
movb    $15, bullshit+2(%eax)
...

одновременно за 1 такт, так что ничего здесь плохого нету.

> чем 0 принципиально отличается от 15(или любого другого числа), что генерируется настолько разный код

Ответ на этот вопрос ты можешь найти в исходниках gcc. Там же можно заставить компилятор генерить более эффективный код.

> И ещё, предполагаю, что процессор может выполнить инструкции

> movb $15, ullshit+1(%eax)
> movb $15, bullshit+2(%eax)
> ...

> одновременно за 1 такт, так что ничего здесь плохого нету.

Умеет. Только другой командой, rep stosb

> Только другой командой, rep stosb

За 1 такт?

А ещё неплохо было бы, чтобы вместо вот этого

        addl    $16, %eax
        cmpl    $1024, %eax

выполнялся

        subl $16, %eax

с предварительным 

        movl    $1024-16, %eax

и выходом из цикла по eax overflow. Тупые компиляторы, тупые...

>а слабо бенчмарк сделать? Чтобы споров не было кто умнее, ты или разработчики gcc.

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

А бенчмарк есть искаропки - time называется

> За 1 такт? 

На двухядерном процессоре:

processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 15
model name      : Intel(R) Xeon(R) CPU            5110  @ 1.60GHz
stepping        : 6
cpu MHz         : 1595.989
cache size      : 4096 KB

Заполнение нулями циклом for без оптимизации (-O0): 7200-7900 тактов
Заполнение нулями циклом for с дикой оптимизацией автора поста: 1500-2000 тактов
Заполнение нулями функцией memset: 4500-4700 тактов
Заполнение нулями командой stosl: 320-370 тактов

Исходничек:
#include <string.h>
#include <stdio.h>

static inline unsigned long long get_cycles()
{
        unsigned long long ret;
        asm volatile("rdtsc" : "=A" (ret));
        return ret;
}

char bullshit[1024];
int main(int argc, char** argv){
	int i;
	unsigned long long ret = get_cycles();
//	memset(bullshit, 0xaa, 1024);
	for (i=0;i<1024;i++) bullshit[i]=0;
	printf("memset: %d\n", get_cycles() - ret);
	asm volatile(
		"rdtsc\n\t"
		"xchgl %%eax, %%ebx\n\t"
		"cld\n\t"
		"rep\n\t"
		"stosl\n\t"
		"rdtsc\n\t"
		"subl %%ebx, %%eax"
		: "=A" (ret)
		: "c" (1024/4), "b" (0), "D" (bullshit)
		);

	for (i = 0; i < 1024; ++i)
		if (bullshit[i] != 0) {
			printf("error\n");
			return 1;
		}
	printf("%d\n", ret);
	return 0;
}

Блин, memset'ом делал poison, не нулями memset заполняет. Да и ладно :)

rep movsb хорошо работает на п4, на счет п3 не уверен

> addl $16, %eax, cmpl $1024, %eax, переход

Тут тоже вопрос спорный - 2 команды из них точно выполнятся параллельно, даже на первопне, такчто накладных расходов это не дает. Плюс eax тут одновременно указатель, а у интелей вроде кешь наперед старается хватать дальше, а не по уменьшению.

Цикл очень маленький, сбрасывать кеш в случае промаха не надо.

> Всё ясно тут. Скорее всего оптимизация заполнения массива нулём в цикле реализована специально,

Называется функция memset в сишной библиотеке, которая (функция) оптимально реализована под данный процессор.

> так как такой код частый, и реализуется просто операцией xor на регистрах mmx.

xor'ом регистр(ы) нужно обнулить один раз. После сохранения значения регистра в память содержимое регистра не меняется, зачем его каждый раз обнулять?

> Заполнение константой, отличной от нуля, не оптимизируется,

Чем это так радикально отличается занесение значения в регистр от его обнуления xor'ом?

> так как это встречается редко и реализация будет посложнее: нужно все 16 байтов регистра mmx сначала заполнить значениями 0x0F, а это будет намного сложнее xor.

Заполнение mmx-регистра значениями 0x0f производится одной командой. Выводы неверные, мат.часть хромает.

Заменил цикл на такой:
for (i=0;i<1024;i++) bullshit[i]=0xf0 | bullshit[i];

для pentium-mmx - pentium3 получаем:
.L2:
        orb     $-16, bullshit(%eax)
        incl    %eax
        cmpl    $1024, %eax
        jne     .L2

а вот уже для pentium-4 считается кашерным использовать mmx:
.L2:
        movdqa  bullshit(%eax), %xmm0
        por     %xmm1, %xmm0
        movdqa  %xmm0, bullshit(%eax)
        addl    $16, %eax
        cmpl    $1024, %eax
        jne     .L2

Что за дискриминация?

movdqa - это sse2 (p-4+)

Знаток мат.части mv, я не говорил про алгоритмы, а говорил, как это скорее всего реализовано в gcc.

> Называется функция memset в сишной библиотеке, которая (функция) оптимально реализована под данный процессор.

Какая свзяь между компиляцией цикла for и функцией memset?

> xor'ом регистр(ы) нужно обнулить один раз. После сохранения значения регистра в память содержимое регистра не меняется, зачем его каждый раз обнулять?

Повторяю для знатоков мат.части: где у меня написано, что регистр нужно обнулить в цикле? Я только писал про обнуление командой xor.

> Чем это так радикально отличается занесение значения в регистр от его обнуления xor'ом?

Тем, что в приведённом коде на языке C нету инструкции заполнить нулём или другой константой значение переменной. Есть цикл for, заполняющий массив из char константой 0. Про заполнение 16-байтового регистра нулём компилятор додумывается сам, а про другую константу не додумывается.

> Заполнение mmx-регистра значениями 0x0f производится одной командой. Выводы неверные, мат.часть хромает.

Это знатокам мат.части легко присвоить 0x0F0F... регистру, а компилятор не может сообразить, что можно из 0x0F сделать 0x0f0f...

> Знаток мат.части mv, я не говорил про алгоритмы, а говорил, как это скорее всего реализовано в gcc.

С комментариями, что xor можно соптимизировать, и поэтому он засунут в цикл?

> Повторяю для знатоков мат.части: где у меня написано, что регистр нужно обнулить в цикле? Я только писал про обнуление командой xor.

Тогда объясните, что вы имели в виду этим:

"Всё ясно тут. Скорее всего оптимизация заполнения массива нулём в цикле реализована специально, так как такой код частый, и реализуется просто операцией xor на регистрах mmx"

> Какая свзяь между компиляцией цикла for и функцией memset?

Это общее замечание. Базовые функции в libc для частных случаев оптимизированы вручную.

> Тем, что в приведённом коде на языке C нету инструкции заполнить нулём или другой константой значение переменной. Есть цикл for, заполняющий массив из char константой 0. Про заполнение 16-байтового регистра нулём компилятор додумывается сам, а про другую константу не додумывается.

Потому что компилятор тупой. Заполнение массива одним ненулевым значением ничем алгоритмически не отличается заполнения нулём. For you information: movl something, %%register "ест" столько же тактов (1), сколько и xor %%register, %%register со времён царя Гороха (p-1 или даже i486, лень смотреть). Конечно, это может быть неверно для многих процессоров, которые поддерживает gcc, но раз уж gcc указали под какой процессор код оптимизировать, то пусть будет добр, оптимизирует под процессор, а не под абстрактную машину Тьюринга.

> Это знатокам мат.части легко присвоить 0x0F0F... регистру, а компилятор не может сообразить, что можно из 0x0F сделать 0x0f0f...

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

Кризис у gcc. icc и даже cl.exe генерируют куда более качественный код.

>movdqa - это sse2 (p-4+)

Да, не заметил. Непонятно, кто ему мешает это с помощью ммх сделать.

>Это знатокам мат.части легко присвоить 0x0F0F... регистру, а компилятор не может сообразить, что можно из 0x0F сделать 0x0f0f...

Это он прекрасно соображает, посмотрите другие примеры.