Câu hỏi Thay thế bộ đếm vòng lặp 32 bit với 64 bit giới thiệu độ lệch hiệu suất điên


Tôi đang tìm cách nhanh nhất để popcount mảng dữ liệu lớn. Tôi gặp phải rất kì lạ hiệu ứng: Thay đổi biến vòng lặp từ unsigned đến uint64_t đã giảm 50% hiệu năng trên PC của tôi.

Điểm chính xác

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

    using namespace std;
    if (argc != 2) {
       cerr << "usage: array_size in MB" << endl;
       return -1;
    }

    uint64_t size = atol(argv[1])<<20;
    uint64_t* buffer = new uint64_t[size/8];
    char* charbuffer = reinterpret_cast<char*>(buffer);
    for (unsigned i=0; i<size; ++i)
        charbuffer[i] = rand()%256;

    uint64_t count,duration;
    chrono::time_point<chrono::system_clock> startP,endP;
    {
        startP = chrono::system_clock::now();
        count = 0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with unsigned
            for (unsigned i=0; i<size/8; i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "unsigned\t" << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }
    {
        startP = chrono::system_clock::now();
        count=0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with uint64_t
            for (uint64_t i=0;i<size/8;i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }

    free(charbuffer);
}

Như bạn thấy, chúng ta tạo một bộ đệm dữ liệu ngẫu nhiên, với kích thước đang được x megabyte ở đâu x được đọc từ dòng lệnh. Sau đó, chúng tôi lặp qua bộ đệm và sử dụng phiên bản chưa được kiểm soát của x86 popcount nội tại để thực hiện số lượng popcount. Để có được kết quả chính xác hơn, chúng tôi thực hiện số lần tải xuống 10.000 lần. Chúng tôi đo lường thời gian cho số lượng popcount. Trong trường hợp trên, biến vòng lặp bên trong là unsigned, trong trường hợp thấp hơn, biến vòng lặp bên trong là uint64_t. Tôi nghĩ rằng điều này sẽ không tạo ra sự khác biệt, nhưng ngược lại là trường hợp.

Kết quả (hoàn toàn điên rồ)

Tôi biên dịch nó như thế này (phiên bản g ++: Ubuntu 4.8.2-19ubuntu1):

g++ -O3 -march=native -std=c++11 test.cpp -o test

Đây là kết quả trên Haswell  Core i7-4770K CPU @ 3,50 GHz, đang chạy test 1 (dữ liệu ngẫu nhiên 1 MB):

  • chưa ký 41959360000 0.401554 giây 26,113 GB / giây
  • uint64_t 41959360000 0,759822 giây 13,8003 GB / giây

Như bạn thấy, thông lượng của uint64_t phiên bản mới là chỉ một nửa một trong những unsigned phiên bản! Vấn đề dường như là lắp ráp khác nhau được tạo ra, nhưng tại sao? Đầu tiên, tôi nghĩ về một lỗi trình biên dịch, vì vậy tôi đã thử clang++ (Ubuntu Kêu vang phiên bản 3.4-1ubuntu3):

clang++ -O3 -march=native -std=c++11 teest.cpp -o test

Kết quả: test 1

  • chưa ký 41959360000 0.398293 giây 26,3267 GB / giây
  • uint64_t 41959360000 0.680954 giây 15,3986 GB / giây

Vì vậy, nó gần như là kết quả tương tự và vẫn còn xa lạ. Nhưng bây giờ nó siêu lạ. Tôi thay thế kích thước bộ đệm đã được đọc từ đầu vào với một hằng số 1, vì vậy tôi thay đổi:

uint64_t size = atol(argv[1]) << 20;

đến

uint64_t size = 1 << 20;

Vì vậy, trình biên dịch bây giờ biết kích thước bộ đệm tại thời gian biên dịch. Có lẽ nó có thể thêm một số tối ưu hóa! Đây là những con số cho g++:

  • chưa ký 41959360000 0,509156 giây 20,5944 GB / giây
  • uint64_t 41959360000 0,508673 giây 20,6139 GB / giây

Bây giờ, cả hai phiên bản đều nhanh như nhau. Tuy nhiên, unsigned  thậm chí còn chậm hơn! Nó giảm từ 26 đến 20 GB/s, do đó thay thế một hằng số bằng một giá trị không đổi dẫn đến -sự khử sắc tố. Nghiêm túc, tôi không có đầu mối gì đang xảy ra ở đây! Nhưng bây giờ để clang++ với phiên bản mới:

  • chưa ký 41959360000 0.677009 giây 15,4884 GB / giây
  • uint64_t 41959360000 0,676909 giây 15,4906 GB / giây

Đợi đã, cái gì? Bây giờ, cả hai phiên bản đều giảm xuống chậm chạp số lượng 15 GB / s. Do đó, thay thế một hằng số bằng một giá trị không đổi thậm chí dẫn đến mã chậm trong cả hai trường hợp cho Clang!

Tôi hỏi một đồng nghiệp với một Ivy Bridge CPU để biên dịch điểm chuẩn của tôi. Ông có kết quả tương tự, vì vậy nó không có vẻ là Haswell. Bởi vì hai trình biên dịch tạo ra kết quả lạ ở đây, nó cũng không có vẻ là một lỗi trình biên dịch. Chúng tôi không có một CPU AMD ở đây, vì vậy chúng tôi chỉ có thể thử nghiệm với Intel.

Thêm điên khùng, làm ơn!

Lấy ví dụ đầu tiên (ví dụ atol(argv[1])) và đặt static trước biến, tức là:

static uint64_t size=atol(argv[1])<<20;

Đây là kết quả của tôi trong g ++:

  • chưa ký 41959360000 0,396728 giây 26,4306 GB / giây
  • uint64_t 41959360000 0,509484 giây 20,5811 GB / giây

Yay, một lựa chọn khác. Chúng tôi vẫn có 26 GB / giây với u32nhưng chúng tôi đã đạt được u64 ít nhất là từ 13 GB / s đến phiên bản 20 GB / s! Trên PC của đồng nghiệp, u64 phiên bản thậm chí còn nhanh hơn u32 phiên bản, cho kết quả nhanh nhất của tất cả. Đáng buồn thay, điều này chỉ hoạt động cho g++, clang++ dường như không quan tâm static.

Câu hỏi của tôi

Bạn có thể giải thích những kết quả này không? Đặc biệt:

  • Làm thế nào có thể có sự khác biệt như vậy giữa u32 và u64?
  • Làm thế nào có thể thay thế một không liên tục bằng một kích hoạt kích thước bộ đệm liên tục mã ít tối ưu?
  • Làm thế nào có thể chèn static từ khóa làm cho u64 vòng lặp nhanh hơn? Thậm chí nhanh hơn mã gốc trên máy tính của đồng nghiệp của tôi!

Tôi biết rằng tối ưu hóa là một lãnh thổ khó khăn, tuy nhiên, tôi chưa bao giờ nghĩ rằng những thay đổi nhỏ như vậy có thể dẫn đến 100% chênh lệch trong thời gian thực hiện và các yếu tố nhỏ như kích thước bộ đệm không đổi có thể kết hợp lại toàn bộ kết quả. Tất nhiên, tôi luôn muốn có phiên bản có khả năng xuất hiện 26 GB / s. Cách đáng tin cậy duy nhất tôi có thể nghĩ là sao chép dán lắp ráp cho trường hợp này và sử dụng lắp ráp nội tuyến. Đây là cách duy nhất tôi có thể loại bỏ các trình biên dịch dường như phát điên vì những thay đổi nhỏ. Bạn nghĩ sao? Có cách nào khác để nhận được mã có hiệu suất cao nhất không?

Việc tháo gỡ

Đây là việc tháo gỡ cho các kết quả khác nhau:

Phiên bản 26 GB / s từ g ++ / u32 / non-const bufsize:

0x400af8:
lea 0x1(%rdx),%eax
popcnt (%rbx,%rax,8),%r9
lea 0x2(%rdx),%edi
popcnt (%rbx,%rcx,8),%rax
lea 0x3(%rdx),%esi
add %r9,%rax
popcnt (%rbx,%rdi,8),%rcx
add $0x4,%edx
add %rcx,%rax
popcnt (%rbx,%rsi,8),%rcx
add %rcx,%rax
mov %edx,%ecx
add %rax,%r14
cmp %rbp,%rcx
jb 0x400af8

Phiên bản 13 GB / giây từ g ++ / u64 / non-const bufsize:

0x400c00:
popcnt 0x8(%rbx,%rdx,8),%rcx
popcnt (%rbx,%rdx,8),%rax
add %rcx,%rax
popcnt 0x10(%rbx,%rdx,8),%rcx
add %rcx,%rax
popcnt 0x18(%rbx,%rdx,8),%rcx
add $0x4,%rdx
add %rcx,%rax
add %rax,%r12
cmp %rbp,%rdx
jb 0x400c00

Phiên bản 15 GB / s từ clang ++ / u64 / non-const bufsize:

0x400e50:
popcnt (%r15,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r15,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r15,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r15,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp %rbp,%rcx
jb 0x400e50

Phiên bản 20 GB / giây từ g ++ / u32 & u64 / const bufsize:

0x400a68:
popcnt (%rbx,%rdx,1),%rax
popcnt 0x8(%rbx,%rdx,1),%rcx
add %rax,%rcx
popcnt 0x10(%rbx,%rdx,1),%rax
add %rax,%rcx
popcnt 0x18(%rbx,%rdx,1),%rsi
add $0x20,%rdx
add %rsi,%rcx
add %rcx,%rbp
cmp $0x100000,%rdx
jne 0x400a68

Phiên bản 15 GB / s từ clang ++ / u32 & u64 / const bufsize:

0x400dd0:
popcnt (%r14,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r14,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r14,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r14,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp $0x20000,%rcx
jb 0x400dd0

Thật thú vị, phiên bản nhanh nhất (26 GB / s) cũng là phiên bản dài nhất! Nó có vẻ là giải pháp duy nhất sử dụng lea. Một số phiên bản sử dụng jb để nhảy, những người khác sử dụng jne. Nhưng ngoài ra, tất cả các phiên bản dường như có thể so sánh được. Tôi không thấy khoảng cách hiệu suất 100% có thể bắt nguồn từ đâu, nhưng tôi không quá thành thạo trong việc lắp ráp giải mã. Phiên bản chậm nhất (13 GB / giây) trông rất ngắn và tốt. Bất cứ ai có thể giải thích điều này?

Bài học kinh nghiệm

Không có vấn đề gì câu trả lời cho câu hỏi này sẽ được; Tôi đã học được rằng trong các vòng thực sự nóng mỗi chi tiết có thể quan trọng, thậm chí các chi tiết dường như không có bất kỳ liên kết nào với mã nóng. Tôi chưa bao giờ nghĩ về loại sử dụng cho một biến vòng lặp, nhưng khi bạn thấy một thay đổi nhỏ như vậy có thể tạo ra 100% Sự khác biệt! Ngay cả kiểu lưu trữ của bộ đệm cũng có thể tạo ra sự khác biệt lớn, như chúng ta đã thấy với việc chèn statictừ khóa ở phía trước biến kích thước! Trong tương lai, tôi sẽ luôn kiểm tra các giải pháp thay thế khác nhau trên các trình biên dịch khác nhau khi viết các vòng thực sự chặt chẽ và nóng mà rất quan trọng cho hiệu năng hệ thống.

Điều thú vị cũng là sự khác biệt hiệu suất vẫn còn rất cao mặc dù tôi đã unrolled vòng lặp bốn lần. Vì vậy, ngay cả khi bạn hủy đăng ký, bạn vẫn có thể bị ảnh hưởng bởi độ lệch hiệu suất lớn. Khá thú vị.


1150
2017-08-01 10:33


gốc


NHIỀU NHẬN XÉT! Bạn có thể xem chúng trong trò chuyện và thậm chí để lại của riêng bạn có nếu bạn muốn, nhưng xin vui lòng không thêm bất kỳ chi tiết ở đây! - Shog9♦
Cũng thấy GCC Số phát hành 62011, Phụ thuộc dữ liệu sai trong hướng dẫn popcnt. Một người khác đã cung cấp nó, nhưng có vẻ như nó đã bị mất trong quá trình dọn dẹp. - jww


Các câu trả lời:


Thủ phạm: Phụ thuộc dữ liệu sai (và trình biên dịch thậm chí không nhận thức được nó)

Trên bộ xử lý Sandy / Ivy Bridge và Haswell, hướng dẫn:

popcnt  src, dest

dường như có sự phụ thuộc sai trên thanh ghi đích dest. Mặc dù hướng dẫn chỉ ghi vào nó, hướng dẫn sẽ đợi cho đến khi dest đã sẵn sàng trước khi thực hiện.

Sự phụ thuộc này không chỉ giữ được 4 popcnts từ một vòng lặp đơn. Nó có thể thực hiện trên các vòng lặp lặp lại làm cho nó không thể cho bộ vi xử lý song song các vòng lặp lặp lại khác nhau.

Các unsigned so với uint64_t và các chỉnh sửa khác không ảnh hưởng trực tiếp đến vấn đề. Nhưng chúng ảnh hưởng đến phân bổ đăng ký mà gán thanh ghi cho các biến.

Trong trường hợp của bạn, tốc độ là một kết quả trực tiếp của những gì bị mắc kẹt vào chuỗi phụ thuộc (sai) phụ thuộc vào những gì mà người cấp phát đăng ký quyết định làm.

  • 13 GB / s có một chuỗi: popcnt- -add- -popcnt- -popcnt → lần lặp tiếp theo
  • 15 GB / s có một chuỗi: popcnt- -add- -popcnt- -add → lần lặp tiếp theo
  • 20 GB / s có một chuỗi: popcnt- -popcnt → lần lặp tiếp theo
  • 26 GB / s có một chuỗi: popcnt- -popcnt → lần lặp tiếp theo

Sự khác biệt giữa 20 GB / s và 26 GB / s có vẻ là một phần nhỏ của việc giải quyết gián tiếp. Dù bằng cách nào, bộ vi xử lý bắt đầu nhấn nút cổ chai khác khi bạn đạt đến tốc độ này.


Để kiểm tra điều này, tôi sử dụng lắp ráp nội tuyến để vượt qua trình biên dịch và nhận được chính xác lắp ráp tôi muốn. Tôi cũng chia ra count biến để phá vỡ tất cả các phụ thuộc khác có thể gây rối với các điểm chuẩn.

Đây là kết quả:

Sandy Bridge Xeon @ 3,5 GHz: (có thể tìm thấy mã kiểm tra đầy đủ ở dưới cùng)

  • GCC 4.6.3: g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native
  • Ubuntu 12

Đăng ký khác nhau: 18,6195 GB / giây

.L4:
    movq    (%rbx,%rax,8), %r8
    movq    8(%rbx,%rax,8), %r9
    movq    16(%rbx,%rax,8), %r10
    movq    24(%rbx,%rax,8), %r11
    addq    $4, %rax

    popcnt %r8, %r8
    add    %r8, %rdx
    popcnt %r9, %r9
    add    %r9, %rcx
    popcnt %r10, %r10
    add    %r10, %rdi
    popcnt %r11, %r11
    add    %r11, %rsi

    cmpq    $131072, %rax
    jne .L4

Cùng đăng ký: 8,49272 GB / giây

.L9:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # This time reuse "rax" for all the popcnts.
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L9

Đăng ký tương tự với chuỗi bị hỏng: 17,8869 GB / giây

.L14:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # Reuse "rax" for all the popcnts.
    xor    %rax, %rax    # Break the cross-iteration dependency by zeroing "rax".
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L14

Vì vậy, những gì đã đi sai với trình biên dịch?

Dường như cả GCC lẫn Visual Studio đều không biết rằng popcnt có một sự phụ thuộc sai lầm như vậy. Tuy nhiên, những phụ thuộc sai này không phải là không phổ biến. Nó chỉ là vấn đề liệu trình biên dịch có nhận thức được nó hay không.

popcnt không chính xác là hướng dẫn được sử dụng nhiều nhất. Vì vậy, nó không thực sự là một bất ngờ mà một trình biên dịch chính có thể bỏ lỡ một cái gì đó như thế này. Dường như không có tài liệu nào ở bất kỳ nơi nào đề cập đến vấn đề này. Nếu Intel không tiết lộ nó, thì không ai bên ngoài sẽ biết cho đến khi có ai đó chạy vào nó một cách tình cờ.

(Cập nhật:  Kể từ phiên bản 4.9.2, GCC nhận thức được sự phụ thuộc sai này và tạo ra mã để bù đắp nó khi tối ưu hóa được kích hoạt. Các trình biên dịch chính từ các nhà cung cấp khác, bao gồm Clang, MSVC, và thậm chí cả ICC của Intel vẫn chưa nhận thức được lỗi này và sẽ không phát ra mã bù cho nó.)

Tại sao CPU lại có sự phụ thuộc sai như vậy?

Chúng tôi chỉ có thể suy đoán, nhưng có khả năng là Intel có cùng một cách xử lý cho nhiều lệnh hai toán hạng. Các hướng dẫn phổ biến như add, sub mất hai toán hạng cả hai đều là đầu vào. Vì vậy, Intel có thể bị đẩy popcnt vào cùng một danh mục để giữ thiết kế bộ vi xử lý đơn giản.

Bộ vi xử lý AMD dường như không có sự phụ thuộc sai lệch này.


Mã kiểm tra đầy đủ dưới đây để tham khảo:

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

   using namespace std;
   uint64_t size=1<<20;

   uint64_t* buffer = new uint64_t[size/8];
   char* charbuffer=reinterpret_cast<char*>(buffer);
   for (unsigned i=0;i<size;++i) charbuffer[i]=rand()%256;

   uint64_t count,duration;
   chrono::time_point<chrono::system_clock> startP,endP;
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %4  \n\t"
                "add %4, %0     \n\t"
                "popcnt %5, %5  \n\t"
                "add %5, %1     \n\t"
                "popcnt %6, %6  \n\t"
                "add %6, %2     \n\t"
                "popcnt %7, %7  \n\t"
                "add %7, %3     \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "No Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Chain 4   \t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "xor %%rax, %%rax   \n\t"   // <--- Break the chain.
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Broken Chain\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }

   free(charbuffer);
}

Một điểm chuẩn thú vị không kém có thể được tìm thấy ở đây: http://pastebin.com/kbzgL8si
Điểm chuẩn này thay đổi số lượng popcnts nằm trong chuỗi phụ thuộc (sai).

False Chain 0:  41959360000 0.57748 sec     18.1578 GB/s
False Chain 1:  41959360000 0.585398 sec    17.9122 GB/s
False Chain 2:  41959360000 0.645483 sec    16.2448 GB/s
False Chain 3:  41959360000 0.929718 sec    11.2784 GB/s
False Chain 4:  41959360000 1.23572 sec     8.48557 GB/s

1311
2017-08-01 22:41



Chào các bạn! Rất nhiều bình luận trong quá khứ ở đây; trước khi để một cái mới, làm ơn xem lại lưu trữ. - Shog9♦
Điều này vẫn tái tạo trong tiếng kêu đầu. Tôi đã gửi một lỗi: bugs.llvm.org/show_bug.cgi?id=34936. - Justin L.


Tôi đã mã hóa một chương trình C tương đương để thử nghiệm và tôi có thể xác nhận hành vi kỳ lạ này. Hơn nữa, gcc tin rằng số nguyên 64 bit (có thể là một số nguyên size_t anyway ...) tốt hơn, như sử dụng uint_fast32_t khiến gcc sử dụng uint 64 bit.

Tôi đã làm một chút mucking xung quanh với hội đồng:
Chỉ cần lấy phiên bản 32 bit, thay thế tất cả các lệnh / thanh ghi 32 bit bằng phiên bản 64 bit trong vòng lặp popcount-in của chương trình. Quan sát: mã là nhanh như phiên bản 32 bit!

Đây rõ ràng là một hack, vì kích thước của biến không thực sự là 64 bit, vì các phần khác của chương trình vẫn sử dụng phiên bản 32 bit, nhưng miễn là vòng lặp bên trong chiếm ưu thế hiệu suất, đây là một khởi đầu tốt .

Sau đó tôi đã sao chép mã vòng lặp bên trong từ phiên bản 32 bit của chương trình, đã tấn công nó lên đến 64 bit, không được đăng ký để làm cho nó thay thế cho vòng lặp bên trong của phiên bản 64 bit. Mã này cũng chạy nhanh như phiên bản 32 bit.

Kết luận của tôi là đây là lịch trình hướng dẫn không tốt bởi trình biên dịch, không phải là tốc độ thực tế / độ trễ của các lệnh 32-bit.

 (Caveat: Tôi đã tấn công hội đồng, có thể đã phá vỡ một cái gì đó mà không nhận thấy. Tôi không nghĩ vậy.)


47
2017-08-01 22:55





Đây không phải là câu trả lời, nhưng thật khó để đọc nếu tôi đưa kết quả vào bình luận.

Tôi nhận được những kết quả này với Mac Pro (Westmere 6-Lõi Xeon 3,33 GHz). Tôi đã biên dịch nó với clang -O3 -msse4 -lstdc++ a.cpp -o a (-O2 nhận được kết quả tương tự).

kêu vang uint64_t size=atol(argv[1])<<20;

unsigned    41950110000 0.811198 sec    12.9263 GB/s
uint64_t    41950110000 0.622884 sec    16.8342 GB/s

kêu vang uint64_t size=1<<20;

unsigned    41950110000 0.623406 sec    16.8201 GB/s
uint64_t    41950110000 0.623685 sec    16.8126 GB/s

Tôi cũng đã cố gắng:

  1. Đảo ngược thứ tự kiểm tra, kết quả là như nhau vì vậy nó quy tắc ra các yếu tố bộ nhớ cache.
  2. for tuyên bố ngược lại: for (uint64_t i=size/8;i>0;i-=4). Điều này cho kết quả tương tự và chứng minh việc biên dịch đủ thông minh để không chia kích thước cho 8 lần lặp (như mong đợi).

Đây là dự đoán hoang dã của tôi:

Hệ số tốc độ có ba phần:

  • bộ nhớ cache mã: uint64_t phiên bản có kích thước mã lớn hơn, nhưng điều này không ảnh hưởng đến CPU Xeon của tôi. Điều này làm cho phiên bản 64 bit chậm hơn.

  • Hướng dẫn sử dụng. Lưu ý không chỉ số vòng lặp, mà bộ đệm được truy cập với chỉ mục 32 bit và 64 bit trên hai phiên bản. Việc truy cập một con trỏ có độ lệch 64 bit yêu cầu một thanh ghi 64 bit chuyên dụng và địa chỉ, trong khi bạn có thể sử dụng ngay lập tức cho một bù đắp 32 bit. Điều này có thể làm cho phiên bản 32 bit nhanh hơn.

  • Hướng dẫn chỉ được phát ra trên bản biên dịch 64 bit (có nghĩa là, tìm nạp trước). Điều này làm cho nhanh hơn 64-bit.

Ba yếu tố này kết hợp với các kết quả có vẻ trái ngược nhau.


24
2017-08-01 11:04



Thú vị, bạn có thể thêm phiên bản trình biên dịch và cờ biên dịch không? Điều tốt nhất là trên máy tính của bạn, kết quả được quay lại, tức là, sử dụng u64 nhanh hơn. Cho đến bây giờ, tôi chưa bao giờ nghĩ về loại biến vòng lặp nào của tôi, nhưng có vẻ như tôi phải suy nghĩ hai lần lần sau :). - gexicide
@gexicide: Tôi sẽ không gọi nhảy từ 16.8201 đến 16.8126 khiến nó "nhanh hơn". - Mehrdad
@Mehrdad: Bước nhảy tôi muốn nói là 12.9 và 16.8, vì thế unsigned nhanh hơn ở đây. Trong tiêu chuẩn của tôi, ngược lại là trường hợp, tức là 26 cho unsigned, 15 cho uint64_t - gexicide
@gexicide Bạn có nhận thấy sự khác biệt trong bộ đệm địa chỉ [i] không? - Non-maskable Interrupt
@Calvin: Không, ý bạn là gì? - gexicide


Tôi không thể đưa ra câu trả lời có thẩm quyền, nhưng cung cấp tổng quan về nguyên nhân có thể xảy ra. Tham chiếu này cho thấy khá rõ ràng rằng đối với các hướng dẫn trong cơ thể của vòng lặp của bạn có tỷ lệ 3: 1 giữa độ trễ và thông lượng. Nó cũng cho thấy tác động của nhiều công văn. Vì có (cho-hoặc-lấy) ba đơn vị nguyên trong bộ vi xử lý x86 hiện đại, thường có thể gửi ba hướng dẫn trên mỗi chu kỳ.

Vì vậy, giữa đường ống cao điểm và hiệu suất nhiều công văn và thất bại của các cơ chế này, chúng tôi có một yếu tố sáu trong hiệu suất. Nó khá nổi tiếng rằng sự phức tạp của tập lệnh x86 làm cho nó khá dễ dàng cho sự vỡ vỡ kỳ quặc xảy ra. Tài liệu trên có ví dụ tuyệt vời:

Hiệu suất Pentium 4 cho các thay đổi đúng 64 bit thực sự kém. Dịch chuyển trái 64 bit cũng như tất cả các thay đổi 32 bit đều có hiệu suất chấp nhận được. Có vẻ như đường dẫn dữ liệu từ 32 bit trên tới 32 bit thấp hơn của ALU không được thiết kế tốt.

Cá nhân tôi chạy vào một trường hợp kỳ lạ, nơi một vòng lặp nóng chạy chậm hơn đáng kể trên một lõi cụ thể của một chip bốn lõi (AMD nếu tôi nhớ lại). Chúng tôi thực sự có hiệu suất tốt hơn trên tính toán giảm bản đồ bằng cách tắt lõi đó.

Ở đây đoán của tôi là ganh đua cho các đơn vị số nguyên: rằng popcnt, tính năng đếm vòng lặp và tính toán địa chỉ tất cả chỉ có thể chạy ở tốc độ tối đa với bộ đếm rộng 32 bit, nhưng bộ đếm 64 bit gây ra tranh chấp và các đường ống dẫn. Vì chỉ có khoảng 12 chu kỳ tổng cộng, có khả năng 4 chu kỳ với nhiều công văn, mỗi vòng lặp thực hiện thân, một gian hàng duy nhất có thể ảnh hưởng hợp lý đến thời gian chạy theo hệ số 2.

Sự thay đổi được tạo ra bằng cách sử dụng một biến tĩnh, mà tôi đoán chỉ gây ra một sự sắp xếp lại nhỏ của các lệnh, là một đầu mối khác rằng mã 32 bit đang ở một điểm nào đó để tranh chấp.

Tôi biết đây không phải là một phân tích nghiêm ngặt, nhưng nó  một lời giải thích hợp lý.


10
2017-08-01 20:12



Thật không may, kể từ đó (Core 2?), Hầu như không có sự khác biệt về hiệu suất giữa các hoạt động số nguyên 32 bit và 64 bit ngoại trừ nhân / chia - không có trong mã này. - Mysticial
@Gene: Lưu ý rằng tất cả các các phiên bản lưu trữ kích thước trong sổ đăng ký và không bao giờ đọc nó từ ngăn xếp trong vòng lặp. Do đó, tính toán địa chỉ không thể được trộn lẫn, ít nhất không phải trong vòng lặp. - gexicide
@ Gene: Thú vị giải thích thực sự! Nhưng nó không giải thích các điểm WTF chính: 64 bit đó là chậm hơn 32bit do các quầy hàng đường ống là một điều. Nhưng nếu đây là trường hợp, không nên phiên bản 64bit đáng tin cậy chậm hơn 32 bit? Thay vào đó, ba trình biên dịch khác nhau phát ra mã chậm ngay cả đối với phiên bản 32 bit khi sử dụng kích thước bộ đệm liên tục biên dịch; thay đổi kích thước bộ đệm thành tĩnh một lần nữa thay đổi mọi thứ hoàn toàn. Thậm chí còn có một trường hợp trên máy đồng nghiệp của tôi (và trong câu trả lời của Calvin), nơi phiên bản 64bit nhanh hơn đáng kể! Nó có vẻ là hoàn toàn không thể đoán trước .. - gexicide
@ Tâm lý Đó là quan điểm của tôi. Không có sự khác biệt về hiệu năng cao điểm khi không có tranh chấp cho IU, thời gian xe buýt, vv Tham chiếu rõ ràng cho thấy điều đó. Contention làm cho mọi thứ khác nhau. Dưới đây là một ví dụ từ các tài liệu của Intel Core: "Một công nghệ mới có trong thiết kế là Macro-Ops Fusion, kết hợp hai lệnh x86 vào một hoạt động vi mô. Ví dụ, một chuỗi mã phổ biến như so sánh với bước nhảy có điều kiện sẽ trở thành một micro-op đơn lẻ. Thật không may, công nghệ này không hoạt động ở chế độ 64-bit. " Vì vậy, chúng tôi có tỷ lệ 2: 1 trong tốc độ thực thi. - Gene
@gexicide Tôi thấy những gì bạn đang nói, nhưng bạn đang suy luận nhiều hơn tôi có nghĩa là. Tôi đang nói rằng mã đang chạy nhanh nhất là giữ cho các đường ống và gửi hàng đợi đầy đủ. Tình trạng này là mong manh. Thay đổi nhỏ như thêm 32 bit vào tổng lưu lượng dữ liệu và sắp xếp lại hướng dẫn là đủ để phá vỡ nó. Trong ngắn hạn, các OP khẳng định rằng fiddling và thử nghiệm là cách duy nhất về phía trước là chính xác. - Gene


Bạn đã thử vượt qua chưa -funroll-loops -fprefetch-loop-arrays tới GCC?

Tôi nhận được các kết quả sau với các tối ưu hóa bổ sung sau:

[1829] /tmp/so_25078285 $ cat /proc/cpuinfo |grep CPU|head -n1
model name      : Intel(R) Core(TM) i3-3225 CPU @ 3.30GHz
[1829] /tmp/so_25078285 $ g++ --version|head -n1
g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3

[1829] /tmp/so_25078285 $ g++ -O3 -march=native -std=c++11 test.cpp -o test_o3
[1829] /tmp/so_25078285 $ g++ -O3 -march=native -funroll-loops -fprefetch-loop-arrays -std=c++11     test.cpp -o test_o3_unroll_loops__and__prefetch_loop_arrays

[1829] /tmp/so_25078285 $ ./test_o3 1
unsigned        41959360000     0.595 sec       17.6231 GB/s
uint64_t        41959360000     0.898626 sec    11.6687 GB/s

[1829] /tmp/so_25078285 $ ./test_o3_unroll_loops__and__prefetch_loop_arrays 1
unsigned        41959360000     0.618222 sec    16.9612 GB/s
uint64_t        41959360000     0.407304 sec    25.7443 GB/s

9
2017-08-04 15:37



Nhưng vẫn còn, kết quả của bạn là hoàn toàn xa lạ (đầu tiên unsigned nhanh hơn, sau đó uint64_t nhanh hơn) như unrolling không sửa chữa vấn đề chính của sự phụ thuộc sai. - gexicide


Tôi đã thử với Visual Studio 2013 Express, bằng cách sử dụng một con trỏ thay vì một chỉ mục, mà tăng tốc quá trình một chút. Tôi nghi ngờ điều này là do địa chỉ được bù trừ + đăng ký, thay vì bù trừ + đăng ký + (đăng ký << 3). Mã C ++.

   uint64_t* bfrend = buffer+(size/8);
   uint64_t* bfrptr;

// ...

   {
      startP = chrono::system_clock::now();
      count = 0;
      for (unsigned k = 0; k < 10000; k++){
         // Tight unrolled loop with uint64_t
         for (bfrptr = buffer; bfrptr < bfrend;){
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
         }
      }
      endP = chrono::system_clock::now();
      duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
           << (10000.0*size)/(duration) << " GB/s" << endl;
   }

mã lắp ráp: r10 = bfrptr, r15 = bfrend, rsi = count, rdi = buffer, r13 = k:

$LL5@main:
        mov     r10, rdi
        cmp     rdi, r15
        jae     SHORT $LN4@main
        npad    4
$LL2@main:
        mov     rax, QWORD PTR [r10+24]
        mov     rcx, QWORD PTR [r10+16]
        mov     r8, QWORD PTR [r10+8]
        mov     r9, QWORD PTR [r10]
        popcnt  rdx, rax
        popcnt  rax, rcx
        add     rdx, rax
        popcnt  rax, r8
        add     r10, 32
        add     rdx, rax
        popcnt  rax, r9
        add     rsi, rax
        add     rsi, rdx
        cmp     r10, r15
        jb      SHORT $LL2@main
$LN4@main:
        dec     r13
        jne     SHORT $LL5@main

9
2017-08-02 03:48





Bạn đã thử di chuyển bước giảm bên ngoài vòng lặp chưa? Ngay bây giờ bạn có một sự phụ thuộc dữ liệu thực sự không cần thiết.

Thử:

  uint64_t subset_counts[4] = {};
  for( unsigned k = 0; k < 10000; k++){
     // Tight unrolled loop with unsigned
     unsigned i=0;
     while (i < size/8) {
        subset_counts[0] += _mm_popcnt_u64(buffer[i]);
        subset_counts[1] += _mm_popcnt_u64(buffer[i+1]);
        subset_counts[2] += _mm_popcnt_u64(buffer[i+2]);
        subset_counts[3] += _mm_popcnt_u64(buffer[i+3]);
        i += 4;
     }
  }
  count = subset_counts[0] + subset_counts[1] + subset_counts[2] + subset_counts[3];

Bạn cũng có một số bí ẩn kỳ lạ đang xảy ra, rằng tôi không chắc chắn là phù hợp với các quy tắc bí danh nghiêm ngặt.


7
2017-08-01 18:33



Đó là điều đầu tiên tôi đã làm sau khi tôi đã đọc câu hỏi. Phá vỡ chuỗi phụ thuộc. Khi nó bật ra sự khác biệt hiệu suất không thay đổi (trên máy tính của tôi ít nhất - Intel Haswell với GCC 4.7.3). - Nils Pipenbrinck
@BenVoigt: Nó phù hợp với việc đánh răng nghiêm ngặt. void* và char* là hai loại có thể được đặt bí danh, vì chúng được xem là "con trỏ vào một số bộ nhớ". Ý tưởng của bạn liên quan đến việc loại bỏ dữ liệu phụ thuộc là tốt đẹp cho tối ưu hóa, nhưng nó không trả lời câu hỏi. Và, như @NilsPipenbrinck nói, nó dường như không thay đổi bất cứ điều gì. - gexicide
@gexicide: Quy tắc bí danh nghiêm ngặt không đối xứng. Bạn có thể dùng char* để truy cập T[]. Bạn không thể sử dụng an toàn T* để truy cập char[]và mã của bạn xuất hiện để làm việc sau. - Ben Voigt
@BenVoigt: Sau đó, bạn không bao giờ có thể malloc một mảng của bất cứ điều gì, như malloc trả về void* và bạn giải thích nó như T[]. Và tôi khá chắc chắn rằng void* và char* có cùng ngữ nghĩa liên quan đến răng cưa nghiêm ngặt. Tuy nhiên, tôi đoán đây là khá offtopic ở đây :) - gexicide
Cá nhân tôi nghĩ đúng cách là uint64_t* buffer = new uint64_t[size/8]; /* type is clearly uint64_t[] */ char* charbuffer=reinterpret_cast<char*>(buffer); /* aliasing a uint64_t[] with char* is safe */ - Ben Voigt


TL; DR: Sử dụng __builtin thay vào đó.

Tôi đã có thể làm gcc 4.8.4 (và thậm chí 4.7.3 trên gcc.godbolt.org) tạo mã tối ưu cho việc này bằng cách sử dụng __builtin_popcountlltrong đó sử dụng cùng một hướng dẫn lắp ráp, nhưng không có lỗi phụ thuộc sai đó.

Tôi không chắc chắn 100% mã điểm chuẩn của mình, nhưng objdump đầu ra dường như chia sẻ quan điểm của tôi. Tôi sử dụng một số thủ thuật khác (++i so với i++) để làm cho vòng lặp biên dịch unroll cho tôi mà không cần bất kỳ movl hướng dẫn (hành vi lạ, tôi phải nói).

Các kết quả:

Count: 20318230000  Elapsed: 0.411156 seconds   Speed: 25.503118 GB/s

Mã điểm chuẩn:

#include <stdint.h>
#include <stddef.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

uint64_t builtin_popcnt(const uint64_t* buf, size_t len){
  uint64_t cnt = 0;
  for(size_t i = 0; i < len; ++i){
    cnt += __builtin_popcountll(buf[i]);
  }
  return cnt;
}

int main(int argc, char** argv){
  if(argc != 2){
    printf("Usage: %s <buffer size in MB>\n", argv[0]);
    return -1;
  }
  uint64_t size = atol(argv[1]) << 20;
  uint64_t* buffer = (uint64_t*)malloc((size/8)*sizeof(*buffer));

  // Spoil copy-on-write memory allocation on *nix
  for (size_t i = 0; i < (size / 8); i++) {
    buffer[i] = random();
  }
  uint64_t count = 0;
  clock_t tic = clock();
  for(size_t i = 0; i < 10000; ++i){
    count += builtin_popcnt(buffer, size/8);
  }
  clock_t toc = clock();
  printf("Count: %lu\tElapsed: %f seconds\tSpeed: %f GB/s\n", count, (double)(toc - tic) / CLOCKS_PER_SEC, ((10000.0*size)/(((double)(toc - tic)*1e+9) / CLOCKS_PER_SEC)));
  return 0;
}

Tùy chọn biên dịch:

gcc --std=gnu99 -mpopcnt -O3 -funroll-loops -march=native bench.c -o bench

Phiên bản GCC:

gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4

Phiên bản hạt nhân Linux:

3.19.0-58-generic

Thông tin CPU:

processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 70
model name  : Intel(R) Core(TM) i7-4870HQ CPU @ 2.50 GHz
stepping    : 1
microcode   : 0xf
cpu MHz     : 2494.226
cache size  : 6144 KB
physical id : 0
siblings    : 1
core id     : 0
cpu cores   : 1
apicid      : 0
initial apicid  : 0
fpu     : yes
fpu_exception   : yes
cpuid level : 13
wp      : yes
flags       : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx rdtscp lm constant_tsc nopl xtopology nonstop_tsc eagerfpu pni pclmulqdq ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand hypervisor lahf_lm abm arat pln pts dtherm fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 invpcid xsaveopt
bugs        :
bogomips    : 4988.45
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

5
2018-05-04 11:14



Thật may mắn là -funroll-loops xảy ra để tạo mã không bị nghẽn cổ chai trên chuỗi phụ thuộc mang vòng lặp được tạo bởi popcntDep của sai. Sử dụng một phiên bản trình biên dịch cũ mà không biết về sự phụ thuộc sai là một rủi ro. Không có -funroll-loops, gcc 4.8.5 của vòng lặp sẽ tắc nghẽn về độ trễ popcnt thay vì thông lượng, bởi vì nó được tính rdx. Cùng một mã, được biên soạn bởi gcc 4.9.3 thêm một xor edx,edx phá vỡ chuỗi phụ thuộc. - Peter Cordes
Với các trình biên dịch cũ, mã của bạn sẽ vẫn dễ bị tổn thương với chính xác cùng một biến thể hiệu suất mà OP gặp phải: các thay đổi dường như tầm thường có thể làm cho một cái gì đó bị chậm bởi vì nó không có ý tưởng nó sẽ gây ra vấn đề. Tìm một cái gì đó xảy ra để làm việc trong một trường hợp trên một trình biên dịch cũ là không phải câu hỏi. - Peter Cordes
Đối với hồ sơ, x86intrin.h'S _mm_popcnt_* chức năng trên GCC là các trình bao bọc nội tuyến được ép buộc xung quanh __builtin_popcount*; nội tuyến sẽ làm cho chính xác tương đương với nội dung khác. Tôi rất nghi ngờ bạn sẽ thấy bất kỳ sự khác biệt nào có thể xảy ra do chuyển đổi giữa chúng. - ShadowRanger