1 000 000 000 вычислений на микросекунду?

Question

ОК, я говорил с другом о компиляторах и оптимизации программ, и он предположил, что n * 0.5 быстрее, чем n/2. Я сказал, что компиляторы такого рода оптимизации автоматически, поэтому я написал небольшую программу, чтобы увидеть, есть ли разница между n/2 и n * 0.5:

Раздел:

#include <stdio.h> 
#include <time.h> 

int main(int argc, const char * argv[]) { 
    int i, m; 
    float n, s; 
    clock_t t; 

    m = 1000000000; 
    t = clock(); 
    for(i = 0; i < m; i++) { 
     n = i/2; 
    } 
    s = (float)(clock() - t)/CLOCKS_PER_SEC; 

    printf("n = i/2: %d calculations took %f seconds (last calculation = %f)\n", m, s, n); 

    return 0; 
} 

Умножение:

#include <stdio.h> 
#include <time.h> 

int main(int argc, const char * argv[]) { 
    int i, m; 
    float n, s; 
    clock_t t; 

    m = 1000000000; 
    t = clock(); 
    for(i = 0; i < m; i++) { 
     n = i * 0.5; 
    } 
    s = (float)(clock() - t)/CLOCKS_PER_SEC; 

    printf("n = i * 0.5: %d calculations took %f seconds (last calculation = %f)\n", m, s, n); 

    return 0; 
} 

И для обеих версий я получил 0.000002s avg. при компиляции с clang main.c -O1. И он сказал, что должно быть что-то не так с измерением времени. Таким образом, он тогда написал программу:

#include <cstdio> 
#include <iostream> 
#include <ctime> 

using namespace std; 

int main() 
{ 
    clock_t ts, te; 
    double dT; 

    int i, m; 
    double n, o, p, q, r, s; 
    m = 1000000000; 

    cout << "Independent calculations:\n"; 
    ts = clock(); 
    for (i = 0; i < m; i++) 
    { 
     // make it a trivial pure float calculation with no int casting to float 
     n = 11.1/2.3; 
     o = 22.2/2.3; 
     p = 33.3/2.3; 
     q = 44.4/2.3; 
     r = 55.5/2.3; 
     s = 66.6/2.3; 
    } 

    te = clock(); 
    dT = ((float)(te - ts))/CLOCKS_PER_SEC; // make initial call to get the elapsed time to run the loop 
    ts = clock(); 

    printf("Division: %d calculations took %f seconds\n", m, dT); 

    for (i = 0; i < m; i++) 
    { 
     // make it a trivial pure float calculation with no int casting to float 
     n = 11.1 * 0.53; 
     o = 22.2 * 0.53; 
     p = 33.3 * 0.53; 
     q = 44.4 * 0.53; 
     r = 55.5 * 0.53; 
     s = 66.6 * 0.53; 
    } 

    te = clock(); 
    dT = ((float)(te - ts))/CLOCKS_PER_SEC; // make initial call to get the elapsed time to run the loop 
    ts = clock(); 

    printf("Multiplication: %d calculations took %f seconds\n", m, dT); 

    cout << "\nDependent calculations:\n"; 
    for (i = 0; i < m; i++) 
    { 
     // make it a trivial pure float calculation with no int casting to float 
     n = 11.1/2.3; 
     o = n/2.3; 
     p = o/2.3; 
     q = p/2.3; 
     r = q/2.3; 
     s = r/2.3; 
    } 


    te = clock(); 
    dT = ((float)(te - ts))/CLOCKS_PER_SEC; // make initial call to get the elapsed time to run the loop 
    ts = clock(); 

    printf("Division: %d calculations took %f seconds\n", m, dT); 

    for (i = 0; i < m; i++) 
    { 
     // make it a trivial pure float calculation with no int casting to float 
     n = 11.1 * 0.53; 
     o = n * 0.53; 
     p = o * 0.53; 
     q = p * 0.53; 
     r = q * 0.53; 
     s = r * 0.53; 
    } 


    te = clock(); 
    dT = ((float)(te - ts))/CLOCKS_PER_SEC; // make initial call to get the elapsed time to run the loop 
    ts = clock(); 

    printf("Multiplication: %d calculations took %f seconds\n", m, dT); 

    return 0; 
} 

И для этого он получил ...

1.869570s 
1.868254s 
25.674016s 
3.497555s 

... в таком порядке.

Итак, я запустил программу на своей машине, составленную с помощью clang++ main.cpp -O1, и получил аналогичные результаты: 0.000002 to 0.000011.

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

Answer 1

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

Answer 2

for (i = 0; i < m; i++) 
{ 
    // make it a trivial pure float calculation with no int casting to float 
    n = 11.1 * 0.53; 
    o = n * 0.53; 
    p = o * 0.53; 
    q = p * 0.53; 
    r = q * 0.53; 
    s = r * 0.53; 
} 

есть цикл, который не ссылается на i или m и не содержит циклических ссылок, так что тривиально для компилятора, чтобы удалить оператор цикла

Answer 3

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

У вашего друга есть точка, деление (фактическое деление, а не только написание / в C) медленнее, чем умножение. Для удвоений отношение составляет около 4 для задержки, а деление не конвейерно, а умножение - так, поэтому коэффициент пропускной способности намного хуже: около 20. (эти цифры для Haswell, но являются типичными)

Целочисленное подразделение медленнее, чем деление с плавающей запятой, но использование умножения с плавающей запятой на целое число вызывает два преобразования. Конверсии не так уж плохи, поэтому в целом умножение с плавающей запятой все еще быстрее.

Но любой правильный компилятор превратит целочисленное деление на константу в целочисленное умножение и сдвиг, а может быть, и некоторые дополнительные исправления (в зависимости от делителя и типа). Разделение на две силы еще проще. Для получения дополнительной информации см. Division by Invariant Integers using Multiplication.В качестве примера рассмотрим

int div2(int i) 
{ 
    return i/2; 
} 

GCC превращает это в

mov eax, edi 
shr eax, 31 
add eax, edi 
sar eax 
ret 

который в зависимости от μarch, будет принимать 3 или 4 цикла (за исключением управления потоком).

С другой стороны,

int div2(int i) 
{ 
    return i * 0.5; 
} 

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

cvtsi2sd xmm0, edi 
    mulsd xmm0, QWORD PTR .LC0[rip] 
    cvttsd2si eax, xmm0 
    ret 
.LC0: 
    .long 0 
    .long 1071644672 

Что бы около 4 + 5 + 4 = 13 циклов.

Компилятор также позволил превратить f/2.0 в f * 0.5 даже без каких-либо «небезопасных оптимизаций», деление на мощности двух эквивалентно умножению на обратную. Это не относится к числам, которые не являются силой двух.

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

.section data 
align 16 
one: dq 1.0, 1.0 
.section text 
_bench1: 
    mov ecx, -10000000 
    movapd xmm0, [one] 
loopone: 
    mulpd xmm0, xmm0 
    mulpd xmm0, xmm0 
    add ecx, 1 
    jnz loopone 
    ret 
_bench2: 
    mov ecx, -10000000 
    movapd xmm0, [one] 
looptwo: 
    divpd xmm0, xmm0 
    divpd xmm0, xmm0 
    add ecx, 1 
    jnz looptwo 
    ret 

Позвоните и по тысяче, завернутые в rdtsc, чтобы получить время. Возьмите самое низкое время для обоих. Умножьте время на соотношение между базовыми тактами и турбо-часами. Затем у вас должно быть (приблизительно) количество циклов, на которые берутся оба цикла, делят на 20000000, чтобы получить количество циклов за mulpd или divpd. Временное деление зависит от деления значений, поэтому он не дает наиболее общего результата.

Вы также можете быть заинтересованы в list of instruction latencies and throughputs.