Tại sao phân hạch lặp lại có ý nghĩa trong trường hợp này?

Question

Các mã mà không phân hạch trông như thế này:

int check(int * res, char * map, int n, int * keys){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     res[ret] = i; 
     ret += map[hash(keys[i])] 
    } 
    return ret; 
} 

Với phân hạch:

int check(int * res, char * map, int n, int * keys){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     tmp[i] = map[hash(keys[i])]; 
    } 
    for(int i = 0; i < n; ++i){ 
     res[ret] = i; 
     ret += tmp[i]; 
    } 
    return ret; 
} 

Ghi chú:

• Các nút cổ chai là map[hash(keys[i])] mà truy cập bộ nhớ một cách ngẫu nhiên.

• bình thường, nó sẽ là if(tmp[i]) res[ret++] = i; để tránh nếu, tôi đang sử dụng ret += tmp[i].

• map[..] luôn 0 hoặc 1

là Phiên bản phân hạch thường là đáng kể nhanh hơn và tôi đang cố gắng để giải thích lý do tại sao. Đoán tốt nhất của tôi là ret += map[..] vẫn giới thiệu một số phụ thuộc và ngăn chặn việc thực thi đầu cơ.

Tôi muốn biết liệu có ai có giải thích tốt hơn không.

Answer 1

Từ các thử nghiệm của tôi, tôi nhận được sự khác biệt về tốc độ khoảng 2 lần giữa các vòng hợp nhất và chia tách. Sự khác biệt về tốc độ này rất nhất quán bất kể cách tôi điều chỉnh vòng lặp.

Fused: 1.096258 seconds 
Split: 0.562272 seconds 

(Tham khảo chốt đối với các mã kiểm tra đầy đủ.)

---

Mặc dù tôi không chắc chắn 100%, tôi nghi ngờ rằng điều này là do sự kết hợp của hai yếu tố:

1. Độ bão hòa của bộ đệm tải cửa hàng cho memory disambigutation do bộ nhớ cache bị bỏ lỡ từ map[gethash(keys[i])].
2. Phụ thuộc bổ sung trong phiên bản vòng lặp được hợp nhất.

Rõ ràng là map[gethash(keys[i])] sẽ khiến bộ nhớ cache bị mất gần như mọi lần. Trong thực tế, nó có lẽ đủ để làm ướt toàn bộ bộ đệm lưu trữ.

Bây giờ, hãy xem xét sự phụ thuộc được thêm vào. Vấn đề là các ret biến:

int check_fused(int * res, char * map, int n, int * keys){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     res[ret] = i; 
     ret += map[gethash(keys[i])]; 
    } 
    return ret; 
} 

Biến ret là cần thiết cho độ phân giải địa chỉ của các cửa hàng res[ret] = i;.

• Trong vòng lặp hợp nhất, ret đến từ một lỗi bộ nhớ cache chắc chắn.
• Trong vòng lặp phân tách, ret đang đến tmp[i] - nhanh hơn nhiều.

Độ trễ địa chỉ này của trường hợp vòng lặp hợp nhất có thể gây ra res[ret] = i để lưu trữ để làm tắc nghẽn bộ đệm lưu trữ cùng với map[gethash(keys[i])].

Vì bộ đệm cửa hàng tải có kích thước cố định, nhưng bạn đã tăng gấp đôi rác trong đó:
Bạn chỉ có thể chồng lấp bộ đệm ẩn một nửa nhiều như trước đây. Như vậy 2x giảm tốc độ.

---

Giả sử nếu chúng ta thay đổi vòng lặp hợp nhất như sau:

int check_fused(int * res, char * map, int n, int * keys){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     res[i] = i; // Change "res" to "i" 
     ret += map[gethash(keys[i])]; 
    } 
    return ret; 
} 

này sẽ phá vỡ sự phụ thuộc độ phân giải địa chỉ.

^{(Lưu ý rằng nó không giống nhau nữa, nhưng nó chỉ là để chứng minh sự khác biệt hiệu suất.)}

Sau đó chúng ta có được timings tương tự:

Fused: 0.487477 seconds 
Split: 0.574585 seconds 

---

Đây là thử nghiệm hoàn chỉnh mã:

#define SIZE 67108864 

unsigned gethash(int key){ 
    return key & (SIZE - 1); 
} 

int check_fused(int * res, char * map, int n, int * keys){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     res[ret] = i; 
     ret += map[gethash(keys[i])]; 
    } 
    return ret; 
} 
int check_split(int * res, char * map, int n, int * keys, int *tmp){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     tmp[i] = map[gethash(keys[i])]; 
    } 
    for(int i = 0; i < n; ++i){ 
     res[ret] = i; 
     ret += tmp[i]; 
    } 
    return ret; 
} 


int main() 
{ 
    char *map = (char*)calloc(SIZE,sizeof(char)); 
    int *keys = (int*)calloc(SIZE,sizeof(int)); 
    int *res = (int*)calloc(SIZE,sizeof(int)); 
    int *tmp = (int*)calloc(SIZE,sizeof(int)); 
    if (map == NULL || keys == NULL || res == NULL || tmp == NULL){ 
     printf("Memory allocation failed.\n"); 
     system("pause"); 
     return 1; 
    } 

    // Generate Random Data 
    for (int i = 0; i < SIZE; i++){ 
     keys[i] = (rand() & 0xff) | ((rand() & 0xff) << 16); 
    } 

    printf("Start...\n"); 

    double start = omp_get_wtime(); 
    int ret; 

    ret = check_fused(res,map,SIZE,keys); 
// ret = check_split(res,map,SIZE,keys,tmp); 

    double end = omp_get_wtime(); 

    printf("ret = %d",ret); 
    printf("\n\nseconds = %f\n",end - start); 

    system("pause"); 
} 

Answer 2

Tôi không nghĩ rằng đó là chỉ mục mảng, nhưng cuộc gọi đến chức năng hash() có thể gây ra một gian hàng đường ống và ngăn chặn sắp xếp lại lệnh tối ưu.