LINUX.ORG.RU

[криокамера] Насколько хороши сегодняшние оптимизирующие компиляторы?

 


0

0

Когда-то в молодости я увлекался асмом и с тех пор был свято уверен, что на x86 для повтора некоторых действий N ра нет ничего лучше цикла, в котором счетчик уменьшается от N до 0. Сейчас ради прикола попробовал такой «код» скомпилировать:

#include <stdio.h>

int main()
{
  unsigned i;
  for (i=0; i<100; i++) printf("Hello, world!\n");
  return 0;
}

gcc -O4 -S test.c, а там (выравнивание поскипано)

        xorl    %ebx, %ebx
.L2:
        movl    $.LC0, %edi
        addl    $1, %ebx
        call    puts
        cmpl    $100, %ebx
        jne     .L2

Тогда я попробовал

#include <stdio.h>

int main()
{
  unsigned i = 100;
  do {
    printf ("Hello, world!\n");
  } while (--i);
}

Результат получился точно такой же. И только с -Os я получил свой decl %ebx; jne .L2

Собственно, вопрос: почему добавление единички у нас лучше, чем инкремент (это же как минимум длиннее)? И почему второй цикл был «перевернут»? Ведь декремент установит ZF и необходимость в сравнении просто отпадет сама собой.

P. S. Выставил -Os в make.conf, планирую пересобирать мир.

Ответ на: комментарий от tailgunner

>Интереснее, почему вместо printf стоит puts.

Это-то как раз нормально и ожидаемо: printf парсит строку перед выводом, но это было сделано за него компилятором на этапе компиляции.

linuxfan
() автор топика

Ну а теперь я вообзе ничего не понимаю.

#include <stdio.h>

int main()
{
	volatile unsigned i = 100;
	do {
		puts("Hello, world");
		--i;
	} while (i);
	return 0;
}

Превращается в

        movl    $100, 20(%rsp)
        .p2align 4,,10
        .p2align 3
.L2:
        movl    $.LC0, %edi
        call    puts
        movl    20(%rsp), %eax    // WTF??
        subl    $1, %eax 
        movl    %eax, 20(%rsp)    // WTF??
        movl    20(%rsp), %eax    // WTF??
        testl   %eax, %eax
        jne     .L2

linuxfan
() автор топика
Ответ на: комментарий от tailgunner

>А чего ты ждал от volatile?

decl variable jne .L2

Здесь меня даже -Os разочаровал дико:

        movl    $100, 20(%rsp)
.L2:
        movl    $.LC0, %edi
        call    puts
        movl    20(%rsp), %eax
        decl    %eax
        movl    %eax, 20(%rsp)
        movl    20(%rsp), %eax // !
        testl   %eax, %eax // !
        jne     .L2

Строки, отмеченные "!" не нужны.

Кажется, древний анекдот про char make_program_look_big[10000000] нашел свое воплощение в оптимизаторе gcc.

linuxfan
() автор топика
Ответ на: комментарий от linuxfan

An object that has volatile-qualified type may be modified in ways unknown to the implementation or have other unknown side effects. Therefore any expression referring to such an object shall be evaluated strictly according to the rules of the abstract machine, as described in $2.1.2.3.

2.1.2.3 Program execution

The semantic descriptions in this Standard describe the behavior of an abstract machine in which issues of optimization are irrelevant.

_Accessing_ a _volatile_ object, modifying an object, modifying a file, or calling a function that does any of those operations are all side effects ,which are changes in the state of the execution environment. Evaluation of an expression may produce side effects.

vga ★★
()
Ответ на: комментарий от tailgunner

>Подозреваю, что по скорости ты ничего не выиграешь.

И давно ли у нас появились операции, выполнение которых не требует памяти? Вместо mov-sub-mov-mov-test получается всего один dec. Я уже не говорю, насколько это короче.

Ну ок, я могу понять, откуда последний mov берется — типа между декрементом и проверкой значение volatile-переменной могло иземниться, ок. Но нахрена загружать значение в регистр, менять регистр, сохранять значение обратно, когда sub/dec могут принимать ячейку памяти в качестве операнда?

linuxfan
() автор топика
Ответ на: комментарий от linuxfan

> Вместо mov-sub-mov-mov-test получается всего один dec.

Который разворачивается в mov-sub-mov, а еще один mov объяснен парой постов выше.

P.S. считать себя умнее компилятора - обычно плохая посылка.

tailgunner ★★★★★
()
Ответ на: комментарий от vga

>An object that has volatile-qualified type may be modified in ways unknown to the implementation or have other unknown side effects

И это повод для создания дичайших race conditions в виде read-modify-write вместо modify-in-memory? Я удивлен, почему начальное значение volatile-переменной gcc присваивает напрямую, а не через какой-нибудь промежуточный регистр.

linuxfan
() автор топика
Ответ на: комментарий от linuxfan

Ты читать умеешь? Тебе сказали: dec разворачивается в mov-sub-mov. Так как mov sub mov выполняется на современных процах быстрее, чем dec.

AntonK
()
Ответ на: комментарий от tailgunner

>А еще можно попробовать собрать программу для i386.

И отказаться от дополнительных 16 регистров и аппаратных операций над 64-битными целыми? Ну уж нет!

linuxfan
() автор топика
Ответ на: комментарий от tailgunner

>P.S. считать себя умнее компилятора - обычно плохая посылка.

Глупо считать себя глупее его. Максимум, на что он способен — это более-менее устроить переупорядочивание инструкций для более оптимального параллельного выполнения, но даже грамотно распорядиться регистрами внутри одной функции он не сможет.

Ах, да, gcc еще может развернуть цикл, даже если в командной строке ему явно сказать -fno-unroll-loops.

linuxfan
() автор топика
Ответ на: комментарий от linuxfan

>> А еще можно попробовать собрать программу для i386.

И отказаться от дополнительных 16 регистров и аппаратных операций над 64-битными целыми?

Зато там может появиться твоя любимая decl <memaddr> :)

tailgunner ★★★★★
()
Ответ на: комментарий от AntonK

>http://www.linux.org.ru/jump-message.jsp?msgid=4528311&cid=4528510

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

linuxfan
() автор топика

Баг?

#include <stdio.h>

int main()
{
	volatile unsigned i = 100;
	do {
		puts("Hello, world");
	} while (--i);
	return 0;
}

получаем

        movl    $100, 20(%rsp)
        .p2align 4,,10
        .p2align 3
.L2:
        movl    $.LC0, %edi
        call    puts
        movl    20(%rsp), %eax
        subl    $1, %eax
        movl    %eax, 20(%rsp)
        movl    20(%rsp), %eax // это не результат декремента!
        testl   %eax, %eax
        jne     .L2

А это уже явно бажный код: я прошу сравнить с нулем результат выполнения декремента, а не текущее значение переменной, как это делает gcc.

icc, кстати, это обрабатывает правильно: load-dec-store-jne

linuxfan
() автор топика
Ответ на: комментарий от AntonK

>А я утверждаю. Можешь сам попробовать проверить.

Ха! Да на основании опытов на одном своем процессоре, я могу утверждать, что инлайнинг не нужен, а выполнение call не требует никаких затрат:

funcalls:            0.013174
loop:                0.013130

Первое — это декремент volatile-переменной в цикле с помощью вызова функции (в ассемблерном листинге присутствует call). Второе — операция декремента прямо в цикле. 5 млн итераций. Отклонение в пределах статистической погрешности.

linuxfan
() автор топика
Ответ на: комментарий от AntonK

>Ну, он же перед сравниванием отнял единичку. Очки может пора купить?

Ты давно пишешь на пыхе? Месяца два? Только слепой не может не видеть, что в сравнение идет НЕ результат выполнения декремента, а какое-то левое текущее значение переменной.

linuxfan
() автор топика
Ответ на: Баг? от linuxfan

icc, кстати, это обрабатывает правильно: load-dec-store-jne

What constitutes an access to an object that has volatile-qualified type is implementation-defined.

vga ★★
()
Ответ на: комментарий от vga

>What constitutes an access to an object that has volatile-qualified type is implementation-defined.

Давай по-другому: что означает конструкция while (--i) ?

linuxfan
() автор топика
Ответ на: комментарий от AntonK

>А я утверждаю. Можешь сам попробовать проверить.

#include <stdio.h>

int main()
{
	volatile unsigned i = 100;
	do {
		puts("Hello, world");
                --i;
	} while (i);
	return 0;
}

icc -O3 -S дает нам

        movl      $100, 4(%rsp)                                 #5.22
                                # LOE rbx r12 r13 r14 r15
..B1.2:                         # Preds ..B1.3 ..B1.7
        movl      $_2__STRING.0, %edi                           #7.3
        call      puts                                          #7.3
                                # LOE rbx r12 r13 r14 r15
..B1.3:                         # Preds ..B1.2
        decl      4(%rsp)                                       #8.5 << gcc SUCKS
        movl      4(%rsp), %eax                                 #9.11
        testl     %eax, %eax                                    #9.11
        jne       ..B1.2        # Prob 82%                      #9.11

И, кстати, если поставить while (--i), то код изменится, т. к. и icc совершенно правильно будет сравнивать с нулем результат операции декремента.

linuxfan
() автор топика
Ответ на: комментарий от AntonK

>Я тебя обзывал?

Ты призывал меня купить очки! Хотя это ты не увидел, что в eax загружается текущее значение переменной, а не то, что было получено после декремента.

linuxfan
() автор топика
Ответ на: комментарий от AntonK

>Ну так ты по скорости сравни с тем, что gcc нагенерил (mov sub mov), должно быть быстрее.

Ты в курсе, что такое icc? По его ассемблерному выводу вообще можно учиться, как правильно писать код для процессоров Intel.

linuxfan
() автор топика
Ответ на: комментарий от linuxfan

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

AntonK
()
Ответ на: комментарий от AntonK

>Я все хорошо увидел - в eax загружается все правильно, не текущее значение, а декрементированное.

http://www.linux.org.ru/jump-message.jsp?msgid=4528311&cid=4528613

        movl    20(%rsp), %eax  // eax = i
        subl    $1, %eax        // eax -= 1
        movl    %eax, 20(%rsp)  // i = eax
        movl    20(%rsp), %eax  // eax = i (i != результату предыдущей операции согласно стандарту)
        testl   %eax, %eax      // сравнение с нулем какой-то ереси, а не результата декремента
linuxfan
() автор топика
Ответ на: комментарий от linuxfan
include <stdio.h> 
 
int main() 
{ 
   volatile unsigned i = 10; 
   do { 
      printf("%u", i); 
   } while (--i); 
   return 0; 
}

Скомпиль gcc и icc, запусти, сравни результат выполнения и подчеркни различия.

AntonK
()
Ответ на: комментарий от linuxfan

Давай по-другому: что означает конструкция while (--i) ?

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

А как должно быть по-твоему?

vga ★★
()
Ответ на: комментарий от linuxfan
movl    20(%rsp), %eax  // eax = i [br]
subl    $1, %eax        // eax -= 1[br] 
movl    %eax, 20(%rsp)  // i = eax [br]
movl    20(%rsp), %eax  // i имеет квалификатор volatile, значение нужно перечитать: eax = i [br]
testl   %eax, %eax      // сравнение с нулем прочитанного значения, а не какой-то ереси[br]

Так вроде все вполне очевидно

m0rph ★★★★★
()
Ответ на: комментарий от vga

s/инкремент/декремент/ конечно же, спать мне похоже пора.

vga ★★
()
Ответ на: комментарий от linuxfan

> сделано за него компилятором на этапе компиляции.

железно %)

melkor217 ★★★★★
()
Ответ на: комментарий от vga

>Стандарт с гцц согласен.

Я пропустил то место в стандарте, где говорится, что do { --i; }while(i); эквивалентно do while(--i). Напротив, стандарт нам говорит, что значение volatile переменной может быть произвольным образом изменено в любое время, а значит в первом случае я получу новое значение i, а не уменьшенное на единицу, как я хочу.

Фактически, gcc интерпретирует while(--i) как while (i--, i), а это неправильно.

6.5.3.1 Prefix increment and decrement operators

The value of the operand of the prefix ++ operator is incremented. The result is the new value of the operand after incrementation. The expression ++E is equivalent to (E+=1).

Или new value after incrementation можно настолько вольно интерпретировать?

linuxfan
() автор топика
Ответ на: комментарий от AntonK

>Повторяю

Я настойчиво рекомендую тебе просветиться на тему «почему в этой конструкции не должно быть printf». А бенчмарки gcc vs icc я делал неоднократно и получал выигрыш на 30-200% при использовании icc. Естественно, это при идентичных результатах вычислений.

linuxfan
() автор топика
Ответ на: комментарий от linuxfan

> бенчмарки gcc vs icc я делал неоднократно и получал выигрыш на 30-200% при использовании icc

Выигрыш 200% - это как? Отрицательное время исполнения? %)

tailgunner ★★★★★
()
Ответ на: комментарий от linuxfan

> Но нахрена загружать значение в регистр, менять регистр, сохранять значение обратно, когда sub/dec могут принимать ячейку памяти в качестве операнда?

Сейчас какой год на дворе, а? По тактам такая операция намного дороже, чем несколько дешевых операций над регистрами.

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

anonymous
()
Ответ на: комментарий от tailgunner

>Выигрыш 200% - это как? Отрицательное время исполнения? %)

Относительно времени работы кода icc. Т. е. icc генерировал код, который выполнялся до трех раз быстрее.

linuxfan
() автор топика
Ответ на: комментарий от linuxfan

> Глупо считать себя глупее его. Максимум, на что он способен — это более-менее устроить переупорядочивание инструкций для более оптимального параллельного выполнения, но даже грамотно распорядиться регистрами внутри одной функции он не сможет.

Ты просто по определению намного глупее компилятора. Потому как задача instructions scheduling - NP-полная. У человечишки мозг сплавится, а компьютеру по фиг. То, что ты глупее компилятора, видно хотя бы по тому, что ты не можешь понять смысла сделанных им преобразований.

anonymous
()
Ответ на: комментарий от linuxfan

ты имеешь в виду, что после сохранения декрементированного значения i в память это значение в памяти может произвольно измениться (например, произойдет прерывание, которое изменяет ячейку памяти 20(%rsp))?

Harald ★★★★★
()
Ответ на: комментарий от anonymous

> Оптимизация по размеру кода давно уже потеряла смысл.

Ненене, Дэвид Блейн. Кэш не безразмерный, так что оптимизация по размеру имеет смысл.

tailgunner ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.