Объяснение: log10 быстрее, чем log и log2, но только с O2 и более

Ответ 1

Я заметил некоторые вещи. Если я скомпилирую (GCC 4.5.3) ваш ассемблер, перечисляющий -O3 -S с помощью g++ logflt.S -lrt, я могу воспроизвести поведение. Мои тайминги:

ln=6:984160044
lb=6:950842852
lg=3:64288522

Затем я просмотрел вывод с помощью objdump -SC a.out. Я предпочитаю это смотреть в файлы .S, так как есть конструкции, которые я еще не понимаю. Код не очень легко читать, но я нахожу следующее:

Перед вызовом log или log2 аргумент преобразуется с помощью

400900:       f2 0f 2a c3             cvtsi2sd %ebx,%xmm0
400904:       66 0f 57 c9             xorpd  %xmm1,%xmm1
400908:       f2 0f 59 05 60 04 00    mulsd  0x460(%rip),%xmm0
40090f:       00 
400910:       66 0f 2e c8             ucomisd %xmm0,%xmm1

0x460(%rip) - относительный адрес, указывающий на шестнадцатеричное значение 0000 00000000 33333333 33332440. Это 16-байтная пара SSE double, из которой важна только одна двойная (код использует скалярный SSE). Этот двойной символ 10.1. Таким образом, mulsd выполняет умножение в строке С++ m = n * 10.1;.

log10 отличается:

400a40:       f2 0f 2a c3             cvtsi2sd %ebx,%xmm0
400a44:       66 0f 57 c9             xorpd  %xmm1,%xmm1
400a48:       66 0f 2e c8             ucomisd %xmm0,%xmm1

Я думаю, что для случая log10 вы забыли выполнить умножение! Итак, вы просто вызываете log10 с тем же значением снова и снова... Я бы не удивил меня если процессор достаточно умен, чтобы оптимизировать это.

EDIT: Я сейчас очень уверен, что это проблема, потому что в вашем другом листинге (-O0 -S) умножение выполняется правильно - поэтому отправьте свой код, и пусть другие докажут, что я ошибаюсь!

EDIT2: один способ, которым GCC мог избавиться от этого умножения, заключается в следующем:

log(n * 10.1) = log(n) + log(10.1)

Но в этом случае log(10.1) нужно было бы вычислить один раз, и я не вижу этого кода. Я также сомневаюсь, что GCC сделает это для log10, но не для log и log2.

Ответ 2

Это будет зависеть от реализации функций log() в библиотеке C, версии компилятора, аппаратной архитектуры и т.д. В любом случае, ниже я использую GCC 4.4 на x86-64 с glibc 2.11.

Изменение примера, чтобы добавить строку

cout << "sum=" << sum << endl;

который запрещает компилятору оптимизировать вызовы log(), как я упоминал в комментарии, я получаю следующие тайминги (только целые секунды, -O2):

• log: 98s
• log2: 105s
• log10: 120s

Эти тайминги кажутся примерно согласованными с таймингами -O0 и -O1 в исходном сообщении; при более высоких уровнях оптимизации оценки журналов оптимизируются, поэтому результаты -O2 и -O3 настолько различны.

Кроме того, глядя на пример журнала с профилиром "perf", топ-5 правонарушителей в отчете

# Samples: 3259205
#
# Overhead         Command              Shared Object  Symbol
# ........  ..............  .........................  ......
#
    87.96%             log  /lib/libm-2.11.1.so        [.] __ieee754_log
     5.51%             log  /lib/libm-2.11.1.so        [.] __log
     2.88%             log  ./log                      [.] main
     2.84%             log  /lib/libm-2.11.1.so        [.] __isnan
     0.69%             log  ./log                      [.] [email protected]

За исключением основного, все остальные символы связаны с вызовом log(). Подводя итог этим, мы можем заключить, что 97% общей продолжительности выполнения этого примера расходуется на log().

Реализация __ieee754_log можно найти здесь, в репозитории glibc git. Соответственно, другие реализации: log2, log10. Обратите внимание, что предыдущие ссылки относятся к версиям HEAD, для выпущенной версии см. Их соответствующие ветки

Ответ 3

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

В коде сборки OP связан (аннотации от меня):

.L10:
    cvtsi2sd %ebx, %xmm0         // convert i to double
    xorpd    %xmm1, %xmm1        // zero 
    mulsd    .LC0(%rip), %xmm0   // multiply i with 10.1
    ucomisd   %xmm0, %xmm1       // compare with zero
    jae       .L31               // always below, never jump

    addl    $1, %ebx             // i++
    cmpl    $2147483647, %ebx    // end of for loop
    jne     .L10
    ...
.L31:
    call    log10, log2, whatever...  // this point is never reached

Можно видеть, что вызов log никогда не выполняется, особенно если вы выполните его с помощью gdb. Весь код составляет 2 ³¹ умножения и сравнения двойника.

Это также объясняет ошеломляющее увеличение скорости выполнения функции журнала в 30 раз при компиляции с помощью -O2, если кто-то тоже нашел это странно.

Edit:

for (int n = 1; n < INT_MAX; ++n)
{
    m = n * 10.1;
    sum += log(m);
}

Компилятор не может полностью оптимизировать петли, потому что она не может доказать, что вызов log всегда будет успешным - он имеет побочные эффекты, если аргумент отрицательный. Таким образом, она заменяет цикл сравнением с нулем - выполняется log, если результат умножения меньше или меньше нуля. Это означает, что он никогда не выполняется:-)

То, что остается в цикле, - это умножение и тест, если результат может быть отрицательным.

Интересный результат возникает, если я добавляю -ffast-math к параметрам компилятора, что избавляет компилятор от строгого соответствия IEEE:

ln=0:000000944
lb=0:000000475
lg=0:000000357

Ответ 4

Вы неправильно подходите к проблеме и переходите к выводам.

Использование часов для профилирования недостаточно. Используйте приличный профилировщик вместо часов (gprof или AQTime7). Профилировщик должен иметь возможность предоставлять тайм-ауты в каждой строке. Ваша проблема заключается в том, что вы предполагаете, что узкое место лежит в функции журнала. Однако преобразование int-to-float не очень быстро и может быть узким местом. Другое дело, что gcc поставляется с исходным кодом, который вы можете прочитать.

Теперь , предполагая, что узкое место на самом деле лежит в функции журнала:

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

т.е. 10^(log10(2^32) + 10^-15) - 2^32 == 9.8895 * 10^-6, но 2^(log2(2^32) + 10^-15) - 2^32 == 2.977 * 10^-6 и 100^(log100(2^32) + 10^-15) - 2^32 == 0.00001977, также log2(INT_MAX) > log10(INT_MAX) Это означает, что с большей логарифмической базой, если функция логарифма пытается "искать" для правильный результат, он скорее ударит по ситуации, когда изменение прогнозируемого результата больше невозможно из-за округления ошибок. Однако это все еще просто предположение.

Существуют и другие способы вычисления логарифма. Например, log10(x) == ln(x)/ln(10), если функция логарифма вычисляла его таким образом, вы получали бы почти одинаковые тайминги.

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

Если ДЕЙСТВИТЕЛЬНО важно иметь более быструю функцию логарифма, а алгоритмическая оптимизация ДЕЙСТВИТЕЛЬНО невозможна (если логарифм действительно является узким местом, например, можно кэшировать результаты), вы можете попытаться найти более быструю реализацию алгоритма, но если я если бы вы в этом случае, я бы просто попытался бросить аппаратное обеспечение в проблему - например, распараллеливая задачу.