Влияние параметров оптимизации GCC на итог сборки

> но вся эта гибкость оптимизации ничто, относительно, вашего кода.

Слишком, много, лишних, запятых.

>но вся эта гибкость оптимизации ничто, относительно, вашего кода.

Если вы и программы так же пишете, то удивительно, как они вообще компилируются.

боян. acovea и ее тесты поприкольнее будут.

> но вся эта гибкость оптимизации ничто, относительно, вашего кода

Литературный превед.

Такие маленькие промежутки времени с помощью time мерить?! Ф топку такие тесты!!!

Вы статью читали?

Ну а толку то? там асемблер показывали, он ничем не отличался ;)

да, сначала лабают быдлокодеры алгоритмы с асимптотикой O(exp(N)), когда можно O(Pn(N)), а потом начинают суетиться с компиляторами.

и получив прирост в 2-6% после многих месяцев шаманских плясок с опциями с полным удовлетворением и осознанием собственной важности забивают на все это дело.

поздавательная статейка.

Ну я хотел написать, что Кнута еще никто не отменял. Но подумал что слишком жестоко.

Что касается качества выборов алгоритмов - то его просто нету. Хорошо если авторы библиотеки языка не дураки, и всунули туда быстрые алгоритмы, но, не все алгоритмы одинаково хороши на разных данных. Иногда и пузырьковая сортировка может оказаться хорошей ;)

> Хорошо если авторы библиотеки языка не дураки, и всунули туда быстрые алгоритмы, но, не все алгоритмы одинаково хороши на разных данных.

/me споткнулся, на запятых, и ударился, лицом, об клавиатуру.

> бинарик

Бинарики-шминарики

>Ну я хотел написать, что Кнута еще никто не отменял. Но подумал что слишком жестоко.

ты думаешь, что лоровцы не могут осилить Кнута? =)

>Иногда и пузырьковая сортировка может оказаться хорошей ;)

Бывает и не редко. Поэтому и важно умение вычислять ресрсозатратность алгоритма на ожидаемых данных.

>ресрсозатратность

Что означает данный термин?

> ты думаешь, что лоровцы не могут осилить Кнута? =)

там слишком много запятых

Не думаю, вот и не стал так писать. А что касается последнего, это и подразумевалось.

> Бинарики-шминарики

- Мам, ты мне поесть что-нибудь приготовила?
- Конечно, приготовила. Я твою приправу в суп бросила!
- К-какую приправу?
- Ну, как какую? Которая в коробке была! Хе-хе! В коробке-моробке! Ха-ха-ха! Приправа-миправа в коробке-моробке!

Ага. :( Влияние лунного света на коррозию контактного рельса на перегоне "Автово" - "Кировкий завод".

Главный параметр оптимизации в голове программера. Если этот накосячит, тут уж оптимизируй, не оптимизируй... пофиг веники.

> но вся эта гибкость оптимизации ничто, относительно, вашего кода.

Автор очередной статьи о параметрах оптимизации в компиляторе в очередной раз отбаянился с выводами.

просто доверься виртуально машине, гыгы

Спасибо, проб^Dузнал много нового. Статья полезная.

Даешь java virtual machine на все программы. Да здраствует потребление ram!

1) статья говно

2) статья ниочем

3) только под интел и только под 32 бита.

4) не написано как провести анализ стоимости алгоритма.

Да доверьтесь же уже виртуальной машине наконец, она все в рантайме заоптимизирует и заинлайнит, как надо

> - Ну, как какую? Которая в коробке была! Хе-хе! В коробке-моробке! Ха-ха-ха! Приправа-миправа в коробке-моробке!

это с какого посева трава такая у тебя?

К. Касперски и то написал больше/лучше по теме.

Млин, очередной Агнер Фог выискался, только много тупее...

Ну а апотлогетов пузырьковой сортировки попросим описание случаев её эффективного (по сравнению с другими алгоритмами сортировки) применения.

Не зря, имхо про Билла поговорка ходила (или прям на книжках Кнута написано :) - что те кто книжекку прочитают, и хоть шото в ней поймут - милости просим в корпорацию.

А так, надоели эти "горе-оптимизаторы"...

Перерыв кучу кода опенсурсного, почему-то сильно понравился лишь postgres и tta. Видимо тем, что "кишат" те проекты нашими людьми.

> However, do not depend entirely on them: you should pay more attention to writing efficient and well-structured code.

Кхммм... позволю себе не (совсем) согласиться с автором. Well-structured --- да! Efficient --- не надо.

Не мешайте компилятору работать. Хорошо структурированный код в подавляющем большинстве случаев оптимизируется компилятором гораздо лучше, чем спагетти-код типомодели "здесь вместо умножения будет логический сдвиг и сложение, а вместо обмена через временную переменную три XOR'а". Не надо заниматься "ручной" оптимизацией кода. Не мешайте компилятору работать.

Главный IMHO признак хорошего кода --- human readability. Забавно, но именно максимально human readable в большинстве случаев лучше всего оптимизируется.

P.S. Стоит еще отметить, что оптимизация в целом есть глупость. В целом:)

Все просто, на не больших объемах данных, и опредленных данных, сортировка пузьрком оказывается наиболее быстрой :)

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

>Ну а апотлогетов пузырьковой сортировки попросим описание случаев её эффективного (по сравнению с другими алгоритмами сортировки) применения.

Частично-упорядоченная очередь элементов. Часто полная сортировка бывает ненужна. УЖЕ упорядоченные элемены можно найти в одном из хвостов этой очереди.

>Даешь java virtual machine на все программы. Да здраствует потребление ram!

Товарищ не знает, что такое отображение файлов на память. ;)

> Ну а апотлогетов пузырьковой сортировки попросим описание случаев её эффективного (по сравнению с другими алгоритмами сортировки) применения.

Не знаю, что означает термин "апотлогет", но по поводу пузырьковой сортировки могу дать подсказку: попробуйте посмотреть скорость сортировки массива скажем из 10 элементов пузырьковой и той же quicksort. Еще рекомедную почитаю внимательней какие-нибудь умные книжки по алгоритмам.

>Не мешайте компилятору работать. Хорошо структурированный код в подавляющем большинстве случаев оптимизируется компилятором гораздо лучше, чем спагетти-код типомодели "здесь вместо умножения будет логический сдвиг и сложение, а вместо обмена через временную переменную три XOR'а". Не надо заниматься "ручной" оптимизацией кода. Не мешайте компилятору работать.

Не нужно говорить глупости - компилятор сам заменит список на бинарное дерево?

Дело в том, что умные книжки предлагают в качестве метода сортировки "для массивов из 10 элементов" сортировку вставками.

Вот почему я и спрашивал про случаи где пузырьковая сортировка может эффективно выплыть :)

> вместо обмена через временную переменную три XOR'а

Об этом, если можно, поподробнее

> Не нужно говорить глупости - компилятор сам заменит список на бинарное дерево?

Согласен. Не нужно:)

Эта... в общем, если вместо
int tmp = b ; b = a ; a = tmp ;
написать где-нибудь во внутреннем цикле
b ^= a ^= b ^= a ;
(смотрите пацаны как я могу!:D) то, например, на ix86 архитектуре получится AFAIR офигительный то-о-о-о-о-о-о-о-о-о-ормоз.
На какой-нибудь может и получится ускорение, но ить это дело компилятора код оптимизировать. Дело программиста --- применять правильные алгоритмы для решения задач. И писать human readable и supportable код. А компилировать/оптимизировать должен компилятор.

Если я по субботнему пиву мозги еще ампутировал, то если взять отсортированный массив, переставить последний элемент в начало (например --- 9, 0, 1, 2, 3, 4, 5, 6, 7, 8), пузырьком быстрей отсортируется чем вставками.

P.S. Единица измерения скорости --- кол-во обменов.

P.P.S. Проверить! Мог ошибиться случайно :shuffle:

P.P.P.S. Но в подавляющем большинстве случаев оптимальный вариант --- быстрая сортировка с трехмедианным разбиением до размера подмассивов 10 или 11 (подзабыл точное число, давно ерундой не страдал --- использую STL'ный sort и все), а потом вставками. Insertion sort хорошо работают, когда любой элемент массива стоит на предсказуемом расстоянии от своего места.

>Эта... в общем, если вместо
int tmp = b ; b = a ; a = tmp ;
написать где-нибудь во внутреннем цикле
b ^= a ^= b ^= a ;
(смотрите пацаны как я могу!:D) то, например, на ix86 архитектуре получится AFAIR офигительный то-о-о-о-о-о-о-о-о-о-ормоз. 

Вы неправильно читали:

1 вариант:
	movl	-12(%ebp), %eax
	movl	%eax, -8(%ebp)
	movl	-16(%ebp), %eax
	movl	%eax, -12(%ebp)
	movl	-8(%ebp), %eax
	movl	%eax, -16(%ebp)
	movl	-12(%ebp), %eax
	movl	%eax, 8(%esp)
	movl	-16(%ebp), %eax
	movl	%eax, 4(%esp)
	movl	$.LC0, (%esp)

2 вариант:
	movl	-16(%ebp), %eax
	xorl	%eax, -12(%ebp)
	movl	-12(%ebp), %eax
	xorl	%eax, -16(%ebp)
	movl	-16(%ebp), %eax
	xorl	%eax, -12(%ebp)
	movl	-12(%ebp), %eax
	movl	%eax, 8(%esp)
	movl	-16(%ebp), %eax
	movl	%eax, 4(%esp)
	movl	$.LC0, (%esp)

Получается _абсолютно_ одинаково.

А где Вы тут одинаковость увидели:spy: Да еще и абсолютную? 11 инструкций? Дык вроде бы xor и mov --- это совсем разные инструкции.

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

>А где Вы тут одинаковость увидели:spy: Да еще и абсолютную? 11 инструкций? Дык вроде бы xor и mov --- это совсем разные инструкции.

За один такт выполняются обе (если чтение/запись в регистры). На более старых xor даже был быстрее (классический пример обнуления регистра: xor %reg,%reg быстрее чем movl $0, %reg).

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

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

> ... именно здесь должен включать моск программист и максимально оптимизировать свой код.

Включать мозг --- должен. Выбирать правильные алгоритмы --- да. Но оптимизировать код --- нет. Это задача компилятора.

Задача программиста --- оптимизировать алгоритм и закодировать его в human readable и supportable виде и форме, соблюдая все корпоративные/принятые в данном проекте правила кодирования.

За шедевры вроде

float cReciprocal = 1.f / c ;

for( ... ) { data[j] *= cRecoprocal ; // умножение вместо деления!!! }

частенько отрывают кхм... не только руки. Ну, отрывать не отрывают, но на этапе code review отклоняют изменения.

А про 3xXOR vs. temporary variable... сейчас сделаю бенчмарк:)

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

#include <cstdio>
#include <cstdlib>
inline void swap1( int& a, int& b )
{ int tmp = b ; b = a ; a = tmp ; }
inline void swap2( int& a, int& b )
{ a ^= b ^= a ^= b ; }
#define BUBLE_SORT(SWAP,a,l,r) \
do { \
for( int j = l ; j < r ; ++j ) \
for( int k = l + 1 ; k <= r ; ++k ) \
if( a[j] > a[k] ) SWAP( a[j], a[k] ) ; \
} while(0)
const int g_N = 100000 ;
int main( int argc, char *argv[] )
{ std::srand( 100 ) ;
int *a = new int [g_N] ;
for( int j = 0 ; j < g_N ; ++j ) a[j] = rand() ;
if( argc > 1 )
BUBLE_SORT( swap2, a, 0, g_N - 1 ) ;
else
BUBLE_SORT( swap1, a, 0, g_N - 1 ) ;
std::printf( "%d\n", a[rand()] ) ;
return 0 ;
}

На моем iP-M 7xx Dothan 1.6GHz (модель точно не помню). Компиляция с ключом -O2, первый вариант (временная переменная) 0:27.02user, второй --- 0:42.04user. System time и там и там ожидаемо ноль.

Так что не надо таких шедевров. Если 3XOR работает быстрей, то компилятор это знает;)

P.S. Я с Вами не спорю насчет "проблем алгоритма". Вопрос терминологии просто. Я в понятия "код" и "оптимизация кода" не вкладываю алгоритмы.

P.P.S. Если мне кто из девелоперов на code review такой код отдаст... порву на стельки:) Это не код, это просто бенчмарк "сделал и забыл".

$ gcc ./test.c
$ ./a.out 1000000000
res: -296517632, num: 1000000000, diff: 2105164
res: -296517632, num: 1000000000, diff: 2132119
$ ./a.out 1000000000
res: -296517632, num: 1000000000, diff: 2012834
res: -296517632, num: 1000000000, diff: 1971511

$ cat test.c
#include <sys/time.h>
#include <time.h>
#include <stdio.h>

int main(int argc, char *argv[])
{
        int a = 1000000;
        int b = 3000000;
        int tmp, res, num = 100000, i;
        struct timeval tm1, tm2;
        long diff;

        if (argc > 1)
                num = atoi(argv[1]);

        res = 0;
        gettimeofday(&tm1, NULL);
        for (i=0; i<num; ++i) {
                asm volatile ("movl $0, %%eax\n" :: "Ir"(b));
                res += b;
        }
        gettimeofday(&tm2, NULL);

        diff = (tm2.tv_sec - tm1.tv_sec)*1000000 + (tm2.tv_usec - tm1.tv_usec);

        printf("res: %d, num: %d, diff: %ld\n", res, num, diff);

        res = 0;
        gettimeofday(&tm1, NULL);
        for (i=0; i<num; ++i) {
                asm volatile ("xorl $0, %%eax\n" :: "Ir"(b));
                res += b;
        }
        gettimeofday(&tm2, NULL);

        diff = (tm2.tv_sec - tm1.tv_sec)*1000000 + (tm2.tv_usec - tm1.tv_usec);

        printf("res: %d, num: %d, diff: %ld\n", res, num, diff);
}

Сами операции одинаковы по времени (в пределах погрешности измерений времени).

Но такой же тест, проведенный для набора b ^= a; a ^= b; b ^= a; 
и tmp = b; b = a ; a = tmp;, показывает, что через xor медленее. 

Связано с доступом к памяти - либо просто movl в память, либо
xor, а затем результат положить в память.

>За один такт выполняются обе (если чтение/запись в регистры). На более старых xor даже был быстрее (классический пример обнуления регистра: xor %reg,%reg быстрее чем movl $0, %reg).

Как хорошо было на спектруме (процессор Z80). Что xor, что mov (на большинстве диалектов назывался ld) работали одинаково 4 такта. Правда в xor регистр назначения всегда аккумулятор, но это уже мелочи.

А по поводу обнуления через xor - большой плюс, что константу 0 хранить в памяти не надо (и соответственно читать из памяти ее не надо).

На том же спектруме при использовании xor экономия кода - 1 байт, экономия времени выполнения - 3 такта. Правда обнулять таким образом можно было только аккумулятор.

Доверься Виртуальной Машине, Люк!

Современные процессоры очень сильно отличаются от Z80. Поэтому экстраполировать ископаемые результаты на них будет некорректно.