Việc thay thế bộ đếm vòng lặp 32 bit bằng 64 bit tạo ra độ lệch hiệu suất điên rồ với _mm_popcnt_u64 trên CPU Intel

1461
gexicide 2014-08-02 00:33.

Tôi đang tìm cách nhanh nhất đến popcountcác mảng dữ liệu lớn. Tôi đã gặp phải một hiệu ứng rất kỳ lạ : Thay đổi biến vòng lặp từ unsignedthành uint64_tkhiến hiệu suất giảm 50% 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 tôi tạo một bộ đệm dữ liệu ngẫu nhiên, với kích thước là xmegabyte xđược đọc từ dòng lệnh. Sau đó, chúng tôi lặp lại bộ đệm và sử dụng phiên bản chưa được cuộn của popcountnội tại x86 để thực hiện popcount. Để có được kết quả chính xác hơn, chúng tôi thực hiện số lần bật lên 10.000 lần. Chúng tôi đo thời gian cho số lượng popcount. Trong trường hợp trên, biến vòng trong là unsigned, trong trường hợp dưới, biến lặp trong là uint64_t. Tôi nghĩ rằng điều này không có gì khác biệt, nhưng trường hợp ngược lại.

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 CPU Haswell Core i7-4770K @ 3,50 GHz của tôi, đang chạy test 1(vì vậy dữ liệu ngẫu nhiên 1 MB):

  • không dấu 41959360000 0,401554 giây 26,113 GB / s
  • uint64_t 41959360000 0,759822 giây 13,8003 GB / giây

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

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

Kết quả: test 1

  • không dấu 41959360000 0,398293 giây 26,3267 GB / s
  • uint64_t 41959360000 0,680954 giây 15,3986 GB / giây

Vì vậy, nó gần như là kết quả giống nhau và vẫn còn lạ. Nhưng bây giờ nó trở nên siêu lạ. Tôi thay thế kích thước bộ đệm được đọc từ đầu vào bằng 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 điểm 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++:

  • không dấu 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ừ 26xuống 20 GB/s, do đó thay thế một giá trị không đổi bằng một giá trị không đổi dẫn đến sự khử khoáng . Nghiêm túc mà nói, tôi không biết chuyện gì đang xảy ra ở đây! Nhưng bây giờ clang++với phiên bản mới:

  • không dấu 41959360000 0,677009 giây 15,4884 GB / giây
  • uint64_t 41959360000 0,676909 giây 15,4906 GB / giây

Chờ đã, cái gì? Bây giờ, cả hai phiên bản đều giảm xuống con số chậm là 15 GB / s. Do đó, việc thay thế một giá trị không phải 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 đối với Clang!

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

Làm ơn đi!

Lấy ví dụ đầu tiên (ví dụ có atol(argv[1])) và đặt một statictrướ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 ++:

  • không dấu 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 thay thế khác . Chúng tôi vẫn có tốc độ nhanh 26 GB / s u32, nhưng chúng tôi đã cố gắng tải u64ít nhất từ ​​13 GB / s lên phiên bản 20 GB / s! Trên PC của đồng nghiệp của tôi, u64phiên bản này thậm chí còn nhanh hơn u32phiên bản đó, mang lại kết quả nhanh nhất. Đáng buồn thay, điều này chỉ hoạt động cho g++, clang++dường như không quan tâm đến static.

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

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

  • Làm thế nào có thể có sự khác biệt như vậy giữa u32u64?
  • Làm thế nào để thay thế một không hằng số bằng một kích thước bộ đệm không đổi có thể kích hoạt mã kém tối ưu hơn ?
  • Làm thế nào để chèn statictừ khóa làm cho u64vòng lặp nhanh hơn? Thậm chí còn 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ổ phức tạp, 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 sự khác biệt 100% về thời gian thực hiện và các yếu tố nhỏ như kích thước bộ đệm không đổi lại có thể kết hợp hoàn toàn. Tất nhiên, tôi luôn muốn có phiên bản có thể tăng tốc 26 GB / s. Cách đáng tin cậy duy nhất tôi có thể nghĩ đến 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ới những thay đổi nhỏ. Bạn nghĩ sao? Có cách nào khác để lấy mã một cách đáng tin cậy với hiệu suất cao nhất không?

The Disassembly

Đây là cách 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 / s 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 / s 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

Điều thú vị là phiên bản nhanh nhất (26 GB / s) cũng là phiên bản dài nhất! Nó dường như 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 phiên bản khác sử dụng jne. Nhưng ngoài điều đó, tất cả các phiên bản dường như có thể so sánh được. Tôi không biết 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 giải mã lắp ráp. Phiên bản chậm nhất (13 GB / s) trông thậm chí còn 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ần biết câu trả lời cho câu hỏi này sẽ là gì; Tôi đã học được rằng trong các vòng lặp thực sự nóng, mọi chi tiết đều có thể quan trọng, ngay cả những chi tiết dường như không có bất kỳ liên quan nào đến mã nóng . Tôi chưa bao giờ nghĩ về loại nào sẽ sử dụng cho một biến vòng lặp, nhưng như bạn thấy một thay đổi nhỏ như vậy có thể tạo ra sự khác biệt 100% ! 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 khi chèn statictừ khóa vào trước biến kích thước! Trong tương lai, tôi sẽ luôn thử nghiệm các lựa chọn 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 lặp thực sự chặt chẽ và nóng hổi, ​​rất quan trọng đối với hiệu suất hệ thống.

Điều thú vị là sự khác biệt về hiệu suất vẫn rất cao mặc dù tôi đã mở 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 các sai lệch hiệu suất lớn. Khá thú vị.

8 answers

1575
Mysticial 2014-08-02 12:41.

Thủ phạm: Sự phụ thuộc dữ liệu sai (và trình biên dịch thậm chí không biết về điều đó)

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 vào thanh ghi đích dest. Mặc dù lệnh chỉ ghi vào nó, lệnh sẽ đợi cho đến khi destsẵn sàng trước khi thực thi. Sự phụ thuộc sai này (hiện tại) được Intel ghi lại là erratum HSD146 (Haswell)SKL029 (Skylake)

Skylake đã sửa lỗi này cho lzcnttzcnt .
Cannon Lake (và Ice Lake) đã sửa lỗi này cho popcnt.
bsf/ bsrcó phụ thuộc đầu ra đúng: đầu ra không được sửa đổi cho đầu vào = 0. (Nhưng không có cách nào để tận dụng điều đó với bản chất - chỉ AMD ghi lại nó và các trình biên dịch không để lộ nó.)

(Có, tất cả các hướng dẫn này đều chạy POPCNT được thực hiện như thế nào trong phần cứng? ).


Sự phụ thuộc này không chỉ giữ 4 popcnts từ một lần lặp vòng lặp duy nhất. Nó có thể thực hiện nhiều lần lặp vòng lặp khiến bộ xử lý không thể song song hóa các lần lặp vòng lặp khác nhau.

Các unsignedvs. uint64_tvà tinh chỉnh khác không trực tiếp ảnh hưởng đến vấn đề này. Nhưng chúng ảnh hưởng đến bộ cấp phát thanh ghi chỉ định các thanh ghi cho các biến.

Trong trường hợp của bạn, tốc độ là 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) tùy thuộc vào những gì trình cấp phát thanh ghi quyết định thực hiện.

  • 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 dường như là một yếu tố nhỏ của việc định địa chỉ gián tiếp. Dù bằng cách nào, bộ xử lý sẽ bắt đầu gặp phải những nút thắt 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 để bỏ qua trình biên dịch và nhận được chính xác lắp ráp mà tôi muốn. Tôi cũng chia nhỏ countbiế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 đủ ở phía dưới)

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

Các đăng ký khác nhau: 18,6195 GB / s

.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

Đăng ký cùng: 8.49272 GB / s

.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 / s

.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ậy điều gì đã xảy ra với trình biên dịch?

Có vẻ như cả GCC và Visual Studio đều không biết rằng popcntcó sự phụ thuộc sai như vậy. Tuy nhiên, những phụ thuộc sai này không phải là hiếm. Vấn đề chỉ là liệu trình biên dịch có biết về nó hay không.

popcntkhông chính xác là hướng dẫn được sử dụng nhiều nhất. Vì vậy, không thực sự ngạc nhiên khi một trình biên dịch lớn 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 đề 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 ai đó tình cờ tìm thấy nó.

( Cập nhật: Kể từ phiên bản 4.9.2 , GCC đã biết về sự phụ thuộc sai này và tạo mã để bù lại 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 chính Intel vẫn chưa biết về lỗi vi kiến ​​trúc 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 ta có thể suy đoán: nó chạy trên các đơn vị thực hiện tương tự như bsf/ bsrlàm có một sự phụ thuộc đầu ra. ( POPCNT được thực hiện như thế nào trong phần cứng? ). Đối với những hướng dẫn đó, Intel ghi kết quả số nguyên cho đầu vào = 0 là "không xác định" (với ZF = 1), nhưng phần cứng của Intel thực sự cung cấp một đảm bảo mạnh mẽ hơn để tránh phá vỡ phần mềm cũ: đầu ra không được sửa đổi. AMD ghi lại hành vi này.

Có lẽ bằng cách nào đó thật bất tiện khi tạo ra một số lỗi cho đơn vị thực thi này phụ thuộc vào đầu ra nhưng những đơn vị khác thì không.

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


Dưới đây là mã thử nghiệm đầ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 tại đây: http://pastebin.com/kbzgL8si
Điểm chuẩn này thay đổi số lượng popcnts 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
50
EOF 2014-08-02 12:55.

Tôi đã viết mã 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, gcctin rằng số nguyên 64 bit ( size_tdù sao cũng nên là ...) sẽ tốt hơn, vì việc sử dụng uint_fast32_tkhiến gcc sử dụng uint 64 bit.

Tôi đã làm một chút xung quanh với assembly:
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 số tiền bên trong của chương trình. Quan sát: mã nhanh như phiên bản 32-bit!

Đây rõ ràng là một vụ 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 số tiền bên trong chiếm ưu thế về 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, hack nó lên thành 64 bit, chỉnh sửa các thanh ghi để 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à trình biên dịch lập lịch lệnh không tốt, không phải là lợi thế về tốc độ / độ trễ thực tế của các lệnh 32-bit.

(Cảnh báo: Tôi đã hack lắp ráp, có thể đã làm hỏng thứ gì đó mà không để ý. Tôi không nghĩ vậy.)

28
Non-maskable Interrupt 2014-08-02 01:04.

Đâ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 bằng Mac Pro ( Westmere 6-Cores 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 với 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 với 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ả giống nhau nên nó loại trừ yếu tố bộ nhớ cache.
  2. fortuyê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 trình biên dịch đủ thông minh để không chia kích thước cho 8 mỗi lần lặp (như mong đợi).

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

Yếu tố tốc độ bao gồm ba phần:

  • bộ đệm mã: uint64_tphiê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 con trỏ có độ lệch 64 bit yêu cầu đăng ký và định địa chỉ 64 bit chuyên dụng, trong khi bạn có thể sử dụng ngay lập tức cho độ lệch 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 trình biên dịch 64-bit (nghĩa là, tìm nạp trước). Điều này làm cho 64-bit nhanh hơn.

Ba yếu tố cùng khớp với kết quả quan sát được dường như mâu thuẫn.

10
Gene 2014-08-02 10:12.

Tôi không thể đưa ra câu trả lời có thẩm quyền nhưng cung cấp một cái nhìn 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 phần thân 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-nhận) ba đơn vị số nguyên trong bộ xử lý x86 hiện đại, nên thường có thể gửi ba lệnh cho mỗi chu kỳ.

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

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

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

Đây là suy đoán của tôi đối với các đơn vị số nguyên: rằng các phép tính popcnt, bộ đếm vòng lặp và địa chỉ có thể hầu như không 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à ngừng đường ống. Vì chỉ có tổng cộng khoảng 12 chu kỳ, có khả năng là 4 chu kỳ với nhiều lần điều phối, mỗi lần thực thi nội dung vòng lặp, một lần dừng đơn 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 thứ tự nhỏ các hướng dẫn, là một manh mối khác cho thấy mã 32-bit đang ở một số điểm đến hạn để tranh cãi.

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

10
rcgldr 2014-08-02 17:48.

Tôi đã thử điều này với Visual Studio 2013 Express , sử dụng con trỏ thay vì chỉ mục, điều này đã đẩy nhanh quá trình một chút. Tôi nghi ngờ điều này là do địa chỉ là offset + đăng ký, thay vì offset + đă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:

[email protected]:
        mov     r10, rdi
        cmp     rdi, r15
        jae     SHORT [email protected]
        npad    4
[email protected]:
        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 [email protected]
[email protected]:
        dec     r13
        jne     SHORT [email protected]
9
Dangelov 2014-08-05 05:37.

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

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

[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
7
Ben Voigt 2014-08-02 08:33.

Bạn đã thử di chuyển bước giảm ra ngoài vòng lặp chưa? Ngay bây giờ bạn có một 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í danh kỳ lạ đang diễn ra, mà tôi không chắc là có tuân thủ các quy tắc về biệt hiệu nghiêm ngặt hay không.

6
assp1r1n3 2016-05-05 01:14.

TL; DR: Sử dụng __builtinnội dung thay thế; họ có thể tình cờ giúp đỡ.

Tôi đã có thể làm cho gcc4.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 mã này sử __builtin_popcountlldụng cùng một hướng dẫn lắp ráp, nhưng thật may mắn và tình cờ tạo ra mã không có bất ngờ phụ thuộc dài vòng lặp do lỗi phụ thuộc sai.

Tôi không chắc chắn 100% về 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 ( ++ivs i++) để làm cho trình biên dịch giải phóng vòng lặp cho tôi mà không cần bất kỳ movlhướng dẫn nào (hành vi kỳ 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;
}

Các 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 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:

Related questions

MORE COOL STUFF

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett đã bất chấp những lời khuyên hẹn hò điển hình khi cô gặp chồng mình.

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Michael Sheen là một diễn viên phi lợi nhuận nhưng chính xác thì điều đó có nghĩa là gì?

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Ngôi sao của Hallmark Colin Egglesfield chia sẻ về những cuộc gặp gỡ với người hâm mộ ly kỳ tại RomaDrama Live! cộng với chương trình INSPIRE của anh ấy tại đại hội.

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Bạn sẽ phải phủi sạch đầu đĩa Blu-ray hoặc DVD để xem tại sao Northern Exposure trở thành một trong những chương trình nổi tiếng nhất của thập niên 90.

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

8 công dụng tuyệt vời của Baking Soda và Giấm

8 công dụng tuyệt vời của Baking Soda và Giấm

Bạn biết đấy, hai sản phẩm này là nguồn điện để làm sạch, riêng chúng. Nhưng cùng với nhau, chúng có một loạt công dụng hoàn toàn khác.

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Thủy điện rất cần thiết cho lưới điện của Hoa Kỳ, nhưng nó chỉ tạo ra năng lượng khi có nước di chuyển. Bao nhiêu nhà máy thủy điện có thể gặp nguy hiểm khi các hồ và sông cạn kiệt?

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Tóc tỉa từ các tiệm và các khoản quyên góp cá nhân có thể được tái sử dụng như những tấm thảm thấm dầu và giúp bảo vệ môi trường.

Làm thế nào để xây dựng một quả địa cầu từ Scratch

Làm thế nào để xây dựng một quả địa cầu từ Scratch

Thời gian, sự kiên nhẫn, thời gian, sự cống hiến và thời gian chỉ là một vài trong số những thứ mà Peter Bellerby cần để thành lập và sau đó điều hành Bellerby & Co. Globemakers, một trong những công ty duy nhất trên Trái đất vẫn sản xuất các quả địa cầu bằng tay.

Năm giai đoạn đau buồn sau khi mất việc làm

Năm giai đoạn đau buồn sau khi mất việc làm

Đó là một ngày thứ Bảy, máy bay của tôi hạ cánh, và tôi đã sẵn sàng để thư giãn trong một kỳ nghỉ cuối tuần ngắn ngủi, khi một email đến trên điện thoại của tôi. Tôi đã mất việc.

Giữ an toàn cho danh tính của bạn với một cảnh báo đóng băng hoặc gian lận tín dụng

Giữ an toàn cho danh tính của bạn với một cảnh báo đóng băng hoặc gian lận tín dụng

Nếu bạn đã từng bị đánh cắp danh tính của mình, bạn biết đó là một trải nghiệm đáng sợ và căng thẳng. Một cách không phổ biến để ngăn chặn nó? Tín dụng bị đóng băng.

Buổi ra mắt phần 3 của The Good Place có một học sinh mới: Khán giả

Buổi ra mắt phần 3 của The Good Place có một học sinh mới: Khán giả

Eleanor (Kristen Bell) dường như đã tình nguyện cho chúng tôi làm vật tưởng nhớ. NBC's The Good Place là một chương trình thích thử thách tốt.

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Rothschild's luggage got lost, but luckily she has an incredible closet to shop: Sister Paris Hilton's!

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa. Từ Hollywood đến New York và mọi nơi ở giữa, hãy xem các ngôi sao yêu thích của bạn đang làm gì!

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

Các nhà điều tra đang xem xét liệu nhóm và nghi phạm có biết nhau trước vụ tấn công hay không

Thanh thiếu niên, Gia đình Florida Hội đồng quản trị trường học về Luật 'Không nói đồng tính': 'Buộc chúng tôi tự kiểm duyệt'

Thanh thiếu niên, Gia đình Florida Hội đồng quản trị trường học về Luật 'Không nói đồng tính': 'Buộc chúng tôi tự kiểm duyệt'

Vụ kiện, nêu tên một số học khu, lập luận rằng dự luật "Không nói đồng tính" được ban hành gần đây của Florida "có hiệu quả im lặng và xóa bỏ học sinh và gia đình LGBTQ +"

Đường băng hạ cánh

Đường băng hạ cánh

Cuối hè đầu thu là mùa hoài niệm. Những chiếc đèn đường chiếu ánh sáng của chúng qua những con đường đẫm mưa, và những chiếc lá dưới chân - màu đỏ cam tắt trong bóng chạng vạng - là lời nhắc nhở về những ngày đã qua.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Vào năm 2021, tôi khuyến khích bạn suy nghĩ lại mọi thứ bạn biết về khách hàng mà bạn phục vụ và những câu chuyện bạn kể cho họ. Lùi lại.

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Vào ngày sinh nhật thứ 9 của Felix The Cat, tôi nhớ về một trong những mất mát lớn nhất trong cuộc đời trưởng thành của tôi - Sophie của tôi vào năm 2013. Tôi đã viết bài luận này và chia sẻ nó trên nền tảng này một thời gian ngắn vào năm 2013.

Khi bạn không thể trở thành người mà Internet muốn bạn trở thành

Khi bạn không thể trở thành người mà Internet muốn bạn trở thành

Tôi ghét từ "tàu đắm". Mọi người cảm thấy thoải mái trong la bàn đạo đức của riêng mình, và khi làm như vậy, họ thấy mình vượt qua sự phán xét.

Language