1.000.000.000 phép tính trên mỗi micro giây?

Question

OK, tôi đã nói chuyện với một người bạn về các trình biên dịch và tối ưu hóa các chương trình, và ông đề nghị rằng n * 0.5 nhanh hơn n/2. Tôi đã nói rằng trình biên dịch thực hiện điều đó loại tối ưu hóa tự động, vì vậy tôi đã viết một chương trình nhỏ để xem nếu có một sự khác biệt giữa n/2 và n * 0.5:

Division:

#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; 
} 

Nhân:

#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; 
} 

Và cho cả hai phiên bản, tôi nhận được 0.000002s avg. khi được biên soạn với clang main.c -O1. Và anh ta nói phải có điều gì đó sai trái với phép đo thời gian. Vì vậy, sau đó ông đã viết một chương trình:

#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; 
} 

Và cho rằng ông đã ...

1.869570s 
1.868254s 
25.674016s 
3.497555s 

... theo thứ tự đó.

Vì vậy, tôi đã chạy chương trình trên máy của mình được biên dịch với clang++ main.cpp -O1 và tôi nhận được kết quả tương tự như trước: 0.000002 to 0.000011.

Tuy nhiên, khi tôi biên soạn chương trình mà không tối ưu hóa, tôi nhận được kết quả tương tự cho anh ta trong bài kiểm tra đầu tiên của mình. Vì vậy, câu hỏi của tôi là, làm thế nào có thể bất kỳ số lượng tối ưu hóa làm cho chương trình rằng nhanh hơn nhiều?

Answer 1

Vì mã không thực hiện bất kỳ điều gì khác nhau trong mỗi vòng lặp, trình biên dịch được tự do di chuyển mã trong vòng lặp bên ngoài (kết quả sẽ giống hệt nhau) và loại bỏ toàn bộ vòng lặp, để lại cho bạn với gần như 0 thời gian chạy, như bạn đã thấy.

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; 
} 

là một vòng lặp mà không tham khảo i hoặc m và không chứa tham chiếu vòng tròn nên nó là tầm thường cho trình biên dịch để loại bỏ các tuyên bố lặp

Answer 3

Đây là một ví dụ tốt về cách điểm chuẩn một ngôn ngữ cấp cao thậm chí còn khó hơn so với lắp ráp điểm chuẩn (điều này đủ khó để có được quyền). Trình biên dịch có thể, và thường xuyên, sẽ can thiệp vào điểm chuẩn của bạn.

Bạn của bạn có một điểm, một bộ phận (phân chia thực tế, không chỉ viết / trong C) chậm hơn phép nhân. Đối với tăng gấp đôi, tỷ lệ là khoảng 4 cho độ trễ, và phân chia không pipelined trong khi nhân là, vì vậy tỷ lệ thông lượng là tồi tệ hơn nhiều: khoảng 20. (những con số này cho Haswell, nhưng là điển hình)

Integer division chậm hơn so với phân chia dấu chấm động, nhưng việc sử dụng phép nhân dấu phẩy động trên số nguyên gây ra hai chuyển đổi. Các chuyển đổi không quá tệ, vì vậy tổng cộng, phép nhân dấu phẩy động vẫn còn nhanh hơn.

Nhưng bất kỳ trình biên dịch thích hợp nào cũng sẽ biến phân chia số nguyên thành hằng số thành phép nhân số nguyên và thay đổi, và có thể một số công cụ sửa lỗi bổ sung (tùy thuộc vào số chia và loại). Phân chia bởi sức mạnh của hai thậm chí còn đơn giản hơn. Để biết chi tiết, hãy xem Division by Invariant Integers using Multiplication.Như một ví dụ, hãy xem xét

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

GCC biến này vào

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

nào tùy thuộc vào μarch, sẽ mất 3 hoặc 4 chu kỳ (trừ dòng điều khiển).

Mặt khác,

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

là biến thành

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

Trong đó sẽ mất khoảng 4 + 5 + 4 = 13 chu kỳ.

Một trình biên dịch cũng được phép rẽ f/2.0 vào f * 0.5 thậm chí không có bất kỳ "tối ưu hóa không an toàn", phân chia bởi một cường quốc hai là tương đương với phép nhân bởi nghịch đảo của nó. Điều đó không giữ cho những con số không phải là sức mạnh của hai.

Vì vậy, ngay cả với điểm chuẩn ít nhất được đo một cái gì đó, nó có thể sẽ không đo được điều đúng. Để đo phân dấu chấm động độ trễ vs nhân, bạn có thể viết một cái gì đó như:

.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 

Gọi cả một ngàn, được bọc trong rdtsc để có được thời gian. Dành thời gian thấp nhất cho cả hai. Nhân thời gian bằng tỷ lệ giữa đồng hồ cơ bản và đồng hồ turbo. Sau đó, bạn nên có (xấp xỉ) số chu kỳ của cả hai vòng lặp, chia cho 20000000 để lấy số chu kỳ trên mulpd hoặc divpd. Việc phân chia thời gian phụ thuộc vào các giá trị được chia, vì vậy nó không đưa ra kết quả chung nhất.

Bạn cũng có thể quan tâm đến số list of instruction latencies and throughputs.