a

Câu hỏi Tại sao nó xử lý một mảng được sắp xếp nhanh hơn một mảng chưa được sắp xếp?


Đây là một đoạn mã C ++ có vẻ rất đặc biệt. Đối với một số lý do kỳ lạ, phân loại dữ liệu một cách kỳ diệu làm cho mã nhanh hơn gần gấp sáu lần.

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • Không có std::sort(data, data + arraySize);, mã chạy trong 11,54 giây.
  • Với dữ liệu được sắp xếp, mã sẽ chạy trong 1,93 giây.

Ban đầu, tôi nghĩ rằng điều này có thể chỉ là một ngôn ngữ hoặc trình biên dịch bất thường. Vì vậy, tôi đã thử nó trong Java.

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

Với một kết quả hơi tương tự nhưng ít khắc nghiệt hơn.


Suy nghĩ đầu tiên của tôi là việc phân loại sẽ đưa dữ liệu vào bộ nhớ cache, nhưng sau đó tôi nghĩ làm thế nào ngớ ngẩn đó là vì mảng vừa được tạo ra.

  • Chuyện gì vậy?
  • Tại sao nó xử lý một mảng được sắp xếp nhanh hơn một mảng chưa được sắp xếp?
  • Mã này tóm tắt một số thuật ngữ độc lập và thứ tự không quan trọng.

21674
2018-06-27 13:51


gốc


Chỉ để cho bản ghi âm thôi. Trên Windows / VS2017 / i7-6700K 4GHz, KHÔNG có sự khác biệt giữa hai phiên bản. Phải mất 0,6 cho cả hai trường hợp. Nếu số lần lặp trong vòng lặp ngoài được tăng gấp 10 lần thời gian thực hiện tăng gấp 10 lần đến 6 lần trong cả hai trường hợp. - mp31415
@ user194715: bất kỳ trình biên dịch nào sử dụng cmov hoặc triển khai không nhánh khác (như tự động vector hóa với pcmpgtd) sẽ có hiệu suất không phụ thuộc vào bất kỳ CPU nào. Nhưng nếu nó phân nhánh, nó sẽ phụ thuộc vào bất kỳ CPU nào với việc thực hiện đầu cơ không theo thứ tự. (Ngay cả các CPU có hiệu năng cao sử dụng dự đoán nhánh để tránh tìm nạp / giải mã bong bóng trên các nhánh đã chụp; hình phạt nhỡ nhỏ hơn). - Peter Cordes
Woops ... lại: Meltdown và Spectre - KyleMit
@ KyleMit hiện nó có cái gì để làm với cả hai? Tôi chưa đọc nhiều trên cả hai - mohitmun
@mohitmun, cả hai lỗ hổng bảo mật này đều phù hợp với nhiều loại lỗ hổng được phân loại là "Tấn công mục tiêu tiêm" - KyleMit


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


Bạn là nạn nhân của dự đoán nhánh Thất bại.


Dự đoán chi nhánh là gì?

Xem xét một ngã ba đường sắt:

Licensed Image Hình ảnh bởi Mecanismo, thông qua Wikimedia Commons. Được sử dụng theo CC-By-SA 3.0 giấy phép.

Bây giờ vì lợi ích của lập luận, giả sử đây là trở lại trong những năm 1800 - trước khi khoảng cách dài hoặc thông tin vô tuyến.

Bạn là người điều hành một ngã ba và bạn nghe thấy một chuyến tàu đến. Bạn không có ý tưởng mà cách nó được cho là phải đi. Bạn dừng xe lửa để hỏi người lái xe theo hướng họ muốn. Và sau đó bạn đặt công tắc thích hợp.

Xe lửa nặng và có nhiều quán tính. Vì vậy, họ mất mãi mãi để bắt đầu và làm chậm.

Có cách nào tốt hơn? Bạn đoán hướng tàu sẽ đi!

  • Nếu bạn đoán đúng, nó vẫn tiếp tục.
  • Nếu bạn đoán sai, thuyền trưởng sẽ dừng lại, quay lại và hét lên với bạn để lật công tắc. Sau đó, nó có thể khởi động lại xuống con đường khác.

Nếu bạn đoán đúng mỗi lần, tàu sẽ không bao giờ phải dừng lại.
Nếu bạn đoán sai quá thường xuyên, tàu sẽ dành rất nhiều thời gian dừng lại, sao lưu và khởi động lại.


Xem xét một tuyên bố nếu: Ở cấp độ bộ xử lý, nó là một hướng dẫn chi nhánh:

image2

Bạn là một bộ xử lý và bạn thấy một nhánh. Bạn không biết nó sẽ đi theo hướng nào. Bạn làm nghề gì? Bạn ngừng thực hiện và chờ cho đến khi các hướng dẫn trước đó hoàn tất. Sau đó, bạn tiếp tục xuống con đường chính xác.

Các bộ xử lý hiện đại phức tạp và có đường ống dài. Vì vậy, họ mất mãi mãi để "hâm nóng" và "làm chậm".

Có cách nào tốt hơn? Bạn đoán hướng nào nhánh sẽ đi!

  • Nếu bạn đoán đúng, bạn tiếp tục thực hiện.
  • Nếu bạn đoán sai, bạn cần phải tuôn ra đường ống và quay trở lại nhánh. Sau đó, bạn có thể khởi động lại đường dẫn khác.

Nếu bạn đoán đúng mỗi lần, việc thực hiện sẽ không bao giờ phải dừng lại.
Nếu bạn đoán sai quá thường xuyên, bạn dành rất nhiều thời gian trì hoãn, quay lại và khởi động lại.


Đây là dự đoán chi nhánh. Tôi thừa nhận nó không phải là sự tương tự tốt nhất kể từ khi tàu chỉ có thể báo hiệu hướng với một lá cờ. Nhưng trong các máy tính, bộ vi xử lý không biết hướng nào mà một chi nhánh sẽ đi cho đến giây phút cuối cùng.

Vì vậy, làm thế nào bạn sẽ chiến lược đoán để giảm thiểu số lần tàu phải trở lại và đi xuống con đường khác? Bạn nhìn vào lịch sử quá khứ! Nếu chuyến tàu đi qua 99% thời gian, thì bạn đoán còn lại. Nếu nó thay thế, sau đó bạn thay thế dự đoán của bạn. Nếu nó đi một cách 3 lần một lần, bạn đoán như vậy ...

Nói cách khác, bạn cố gắng xác định một mẫu và theo dõi nó. Đây là nhiều hơn hoặc ít hơn như thế nào dự đoán chi nhánh làm việc.

Hầu hết các ứng dụng đều có các nhánh được xử lý tốt. Vì vậy, các dự đoán chi nhánh hiện đại thường sẽ đạt được> 90% tỷ lệ truy cập. Nhưng khi phải đối mặt với các chi nhánh không thể đoán trước mà không có các mô hình dễ nhận biết, các dự báo chi nhánh hầu như vô dụng.

Đọc thêm: Bài viết "Dự báo chi nhánh" trên Wikipedia.


Như được gợi ý từ trên, thủ phạm là tuyên bố này nếu:

if (data[c] >= 128)
    sum += data[c];

Lưu ý rằng dữ liệu được phân bố đều giữa 0 và 255. Khi dữ liệu được sắp xếp, khoảng nửa đầu của các lần lặp lại sẽ không nhập câu lệnh if. Sau đó, tất cả họ sẽ nhập vào câu lệnh if.

Điều này rất thân thiện với các chi nhánh dự đoán từ các chi nhánh liên tục đi cùng một hướng nhiều lần. Ngay cả một bộ đếm bão hòa đơn giản sẽ dự đoán chính xác nhánh, ngoại trừ vài lần lặp sau khi nó chuyển hướng.

Hiển thị nhanh:

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

Tuy nhiên, khi dữ liệu là hoàn toàn ngẫu nhiên, các dự báo chi nhánh được trả lại vô ích bởi vì nó không thể dự đoán dữ liệu ngẫu nhiên. Do đó, có lẽ sẽ có khoảng 50% sai lầm. (không tốt hơn đoán ngẫu nhiên)

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

Vậy thì cái gì có thể làm được?

Nếu trình biên dịch không thể tối ưu hóa nhánh thành một bước di chuyển có điều kiện, bạn có thể thử một số hacks nếu bạn sẵn sàng hy sinh khả năng đọc cho hiệu suất.

Thay thế:

if (data[c] >= 128)
    sum += data[c];

với:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

Điều này loại bỏ các chi nhánh và thay thế nó bằng một số hoạt động bitwise.

(Lưu ý rằng hack này không hoàn toàn tương đương với if-statement ban đầu. Nhưng trong trường hợp này, nó hợp lệ cho tất cả các giá trị đầu vào của data[].)

Điểm chuẩn: Core i7 920 @ 3,5 GHz

C ++ - Visual Studio 2010 - bản phát hành x64

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - Netbeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

Quan sát:

  • Với Chi nhánh: Có sự khác biệt lớn giữa dữ liệu được sắp xếp và chưa được phân loại.
  • Với Hack: Không có sự khác biệt giữa dữ liệu được sắp xếp và chưa phân loại.
  • Trong trường hợp C ++, bản hack thực sự chậm hơn một chút so với nhánh khi dữ liệu được sắp xếp.

Nguyên tắc chung là tránh phân nhánh phụ thuộc vào dữ liệu trong các vòng quan trọng. (chẳng hạn như trong ví dụ này)


Cập nhật:

  • GCC 4.6.1 với -O3 hoặc là -ftree-vectorize trên x64 có thể tạo ra một động thái có điều kiện. Vì vậy, không có sự khác biệt giữa dữ liệu được sắp xếp và chưa phân loại - cả hai đều nhanh.

  • VC ++ 2010 không thể tạo các chuyển động có điều kiện cho chi nhánh này ngay cả dưới /Ox.

  • Intel Compiler 11 thực hiện điều gì đó kỳ diệu. Nó trao đổi hai vòng, do đó nâng nhánh nhánh không thể đoán trước lên vòng ngoài. Vì vậy, không chỉ là nó miễn dịch các mispredictions, nó cũng nhanh gấp đôi bất cứ điều gì VC + + và GCC có thể tạo ra! Nói cách khác, ICC đã lợi dụng vòng lặp kiểm tra để đánh bại điểm chuẩn ...

  • Nếu bạn cung cấp cho Intel Compiler mã không có nhánh, nó chỉ ra bên phải vector hóa nó ... và chỉ nhanh như với nhánh (với trao đổi vòng lặp).

Điều này cho thấy rằng ngay cả các trình biên dịch hiện đại trưởng thành cũng có thể thay đổi một cách dữ dội trong khả năng tối ưu hóa mã của chúng ...


28593
2018-06-27 13:56



@Mysticial Để tránh sự thay đổi hack bạn có thể viết một cái gì đó như int t=-((data[c]>=128)) để tạo mặt nạ. Điều này cũng sẽ nhanh hơn. Sẽ rất thú vị nếu biết trình biên dịch đủ thông minh để chèn một di chuyển có điều kiện hay không. - Mackie Messer
@phonetagger Hãy xem câu hỏi tiếp theo này: stackoverflow.com/questions/11276291/… Intel Compiler đến khá gần hoàn toàn thoát khỏi vòng lặp bên ngoài. - Mysticial
@Novelocrat Chỉ một nửa trong số đó là chính xác. Chuyển 1 vào bit dấu khi nó bằng 0 thực sự là UB. Đó là bởi vì nó tràn đầy số nguyên. Nhưng chuyển một bit ra khỏi bit dấu là IB. Phải dịch chuyển một số nguyên có dấu âm là IB. Bạn có thể đi vào đối số rằng C / C ++ không yêu cầu bit trên cùng là chỉ báo dấu hiệu. Nhưng chi tiết thực hiện là IB. - Mysticial
@Micicial Cảm ơn rất nhiều vì đã liên kết. Có vẻ đầy hứa hẹn. Tôi sẽ đi mặc dù nó. Một yêu cầu cuối cùng. Xin lỗi, nhưng xin đừng bận tâm, bạn có thể cho tôi biết làm thế nào bạn có thể làm điều này int t = (data[c] - 128) >> 31; sum += ~t & data[c]; thế nào để thay thế if-condition ban đầu ở trên? - Unheilig
Ngữ pháp trong tôi muốn tôi nghĩ rằng điều này nên đọc "... nạn nhân của dự đoán chi nhánh thất bạiure"thay vì chỉ" ... nạn nhân của dự đoán chi nhánh thất bại. " - jdero


Dự đoán chi nhánh.

Với một mảng được sắp xếp, điều kiện data[c] >= 128 Là đầu tiên false cho một chuỗi các giá trị, sau đó trở thành true cho tất cả các giá trị sau này. Đó là dễ dàng để dự đoán. Với mảng chưa được phân loại, bạn trả tiền cho chi phí phân nhánh.


3640
2018-06-27 13:54



Dự đoán nhánh có hoạt động tốt hơn trên các mảng được sắp xếp so với mảng có các mẫu khác nhau không? Ví dụ, đối với mảng -> {10, 5, 20, 10, 40, 20, ...} phần tử tiếp theo trong mảng từ mẫu là 80. Loại mảng này có được tăng tốc theo dự đoán nhánh trong mà phần tử tiếp theo là 80 ở đây nếu mẫu được theo sau? Hay nó thường chỉ giúp với các mảng được sắp xếp? - Adam Freeman
Vì vậy, về cơ bản tất cả mọi thứ tôi thường học về big-O là ra khỏi cửa sổ? Tốt hơn để phải trả chi phí phân loại so với chi phí phân nhánh? - Agrim Pathak
@AgrimPathak Điều đó phụ thuộc. Đối với đầu vào không quá lớn, thuật toán có độ phức tạp cao hơn nhanh hơn thuật toán có độ phức tạp thấp hơn khi hằng số nhỏ hơn cho thuật toán có độ phức tạp cao hơn. Trường hợp điểm hòa vốn có thể khó dự đoán. Cũng thế, so sánh điều này, địa phương là quan trọng. Big-O là quan trọng, nhưng nó không phải là tiêu chuẩn duy nhất cho hiệu suất. - Daniel Fischer
Khi nào dự đoán chi nhánh diễn ra? Khi nào ngôn ngữ sẽ biết mảng đó được sắp xếp? Tôi đang nghĩ về tình hình của mảng trông giống như: [1,2,3,4,5, ... 998,999,1000, 3, 10001, 10002]? điều này sẽ làm mờ đi 3 tăng thời gian chạy? Nó sẽ được miễn là mảng unsorted? - Filip Bartuzi
@FilipBartuzi Chi nhánh dự đoán diễn ra trong bộ vi xử lý, dưới mức độ ngôn ngữ (nhưng ngôn ngữ có thể cung cấp cách để nói cho trình biên dịch những gì có khả năng, do đó, trình biên dịch có thể phát ra mã phù hợp với điều đó). Trong ví dụ của bạn, thứ tự out-of-order 3 sẽ dẫn đến một misprediction chi nhánh (cho điều kiện thích hợp, trong đó 3 cho một kết quả khác nhau hơn 1000), và do đó xử lý mảng đó có khả năng sẽ mất một vài chục hoặc hàng trăm nano giây dài hơn sắp xếp mảng sẽ, hầu như không bao giờ đáng chú ý. Những gì chi phí thời gian là tôi tỷ lệ cao của mispredictions, một misprediction mỗi 1000 là không nhiều. - Daniel Fischer


Lý do tại sao hiệu suất cải thiện đáng kể khi dữ liệu được sắp xếp là hình phạt dự đoán nhánh bị xóa, như được giải thích rõ ràng trong Bí ẩncâu trả lời.

Bây giờ, nếu chúng ta nhìn vào mã

if (data[c] >= 128)
    sum += data[c];

chúng ta có thể thấy rằng ý nghĩa của điều này if... else... nhánh là thêm một cái gì đó khi một điều kiện được thỏa mãn. Loại chi nhánh này có thể dễ dàng chuyển thành di chuyển có điều kiện câu lệnh, sẽ được biên dịch thành một lệnh di chuyển có điều kiện: cmovl, trong một x86 hệ thống. Chi nhánh và do đó hình phạt dự đoán chi nhánh tiềm năng bị xóa.

Trong C, do đó C++, câu lệnh, sẽ biên dịch trực tiếp (không có bất kỳ tối ưu hóa nào) thành lệnh di chuyển có điều kiện trong x86, là toán tử bậc ba ... ? ... : .... Vì vậy, chúng tôi viết lại câu lệnh trên vào một câu lệnh tương đương:

sum += data[c] >=128 ? data[c] : 0;

Trong khi duy trì khả năng đọc, chúng tôi có thể kiểm tra yếu tố tăng tốc.

Trên Intel Core i7-2600K @ 3.4 GHz và Visual Studio 2010 Release Mode, điểm chuẩn là (định dạng được sao chép từ Mysticial):

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

Kết quả là mạnh mẽ trong nhiều thử nghiệm. Chúng tôi nhận được một tốc độ tuyệt vời khi kết quả chi nhánh là không thể đoán trước, nhưng chúng tôi phải chịu một chút khi nó có thể dự đoán được. Trong thực tế, khi sử dụng một di chuyển có điều kiện, hiệu suất là như nhau bất kể mẫu dữ liệu.

Bây giờ hãy xem xét kỹ hơn bằng cách điều tra x86 lắp ráp chúng tạo ra. Để đơn giản, chúng tôi sử dụng hai chức năng max1 và max2.

max1 sử dụng nhánh có điều kiện if... else ...:

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2 sử dụng toán tử bậc ba ... ? ... : ...:

int max2(int a, int b) {
    return a > b ? a : b;
}

Trên máy x86-64, GCC -S tạo ra các hội đồng dưới đây.

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2 sử dụng ít mã hơn nhiều do việc sử dụng lệnh cmovge. Nhưng lợi ích thực sự là max2 không liên quan đến nhảy nhánh, jmp, sẽ có một hình phạt hiệu suất đáng kể nếu kết quả dự đoán là không đúng.

Vậy tại sao một động thái có điều kiện lại hoạt động tốt hơn?

Trong một điển hình x86 bộ vi xử lý, việc thực hiện một lệnh được chia thành nhiều giai đoạn. Nói chung, chúng tôi có phần cứng khác nhau để đối phó với các giai đoạn khác nhau. Vì vậy, chúng tôi không phải đợi một hướng dẫn để hoàn thành để bắt đầu một hướng dẫn mới. Cái này được gọi là đường ống.

Trong trường hợp nhánh, lệnh sau được xác định bởi lệnh trước, vì vậy chúng ta không thể thực hiện pipelining. Chúng ta phải đợi hoặc dự đoán.

Trong trường hợp di chuyển có điều kiện, lệnh di chuyển có điều kiện thực hiện được chia thành nhiều giai đoạn, nhưng các giai đoạn trước đó như Fetch và Decode không phụ thuộc vào kết quả của lệnh trước; chỉ những giai đoạn sau mới cần kết quả. Do đó, chúng ta đợi một phần thời gian thực hiện của một lệnh. Đây là lý do tại sao phiên bản di chuyển có điều kiện chậm hơn so với nhánh khi dự đoán dễ dàng.

Quyển sách Hệ thống máy tính: Phối cảnh của một lập trình viên, ấn bản thứ hai giải thích chi tiết điều này. Bạn có thể kiểm tra Mục 3.6.6 cho Hướng dẫn di chuyển có điều kiện, toàn bộ Chương 4 cho Kiến trúc bộ vi xử lývà Mục 5.11.2 để điều trị đặc biệt cho Chi nhánh dự đoán và hình phạt sai.

Đôi khi, một số trình biên dịch hiện đại có thể tối ưu hóa mã của chúng tôi để lắp ráp với hiệu suất tốt hơn, đôi khi một số trình biên dịch không thể (mã được đề cập là sử dụng trình biên dịch gốc của Visual Studio). Biết được sự khác biệt về hiệu năng giữa nhánh và di chuyển có điều kiện khi không thể đoán trước có thể giúp chúng ta viết mã với hiệu năng tốt hơn khi kịch bản trở nên phức tạp đến nỗi trình biên dịch không thể tối ưu hóa chúng một cách tự động.


2961
2018-06-28 02:14



Không có mức tối ưu hóa mặc định trừ khi bạn thêm -O vào các dòng lệnh GCC của mình. (Và bạn không thể có một tiếng Anh tồi tệ nhất so với tôi;) - Yann Droneaud
Tôi cảm thấy khó tin rằng trình biên dịch có thể tối ưu hóa toán tử bậc ba tốt hơn nó có thể là câu lệnh if tương đương. Bạn đã chỉ ra rằng GCC tối ưu hóa toán tử bậc ba với một chuyển động có điều kiện; bạn không cho thấy rằng nó không làm chính xác điều tương tự cho câu lệnh if. Thực tế, theo Mystical ở trên, GCC làm tối ưu hóa câu lệnh if thành một di chuyển có điều kiện, điều này sẽ làm cho câu trả lời này hoàn toàn không chính xác. - BlueRaja - Danny Pflughoeft
@WiSaGaN Mã trình diễn không có gì, bởi vì hai đoạn mã của bạn biên dịch thành cùng một mã máy. Điều quan trọng là mọi người không hiểu ý tưởng rằng bằng cách nào đó câu lệnh if trong ví dụ của bạn khác với câu chuyện trong ví dụ của bạn. Đúng là bạn sở hữu sự giống nhau trong đoạn cuối của bạn, nhưng điều đó không xóa đi sự thật rằng phần còn lại của ví dụ này là có hại. - Justin L.
@ WiSaGaN Lưu ý của tôi chắc chắn sẽ biến thành một upvote nếu bạn sửa đổi câu trả lời của bạn để loại bỏ các sai lầm -O0 ví dụ và cho thấy sự khác biệt trong được tối ưu hóa asm trên hai testcases của bạn. - Justin L.
@UpAndAdam Tại thời điểm thử nghiệm, VS2010 không thể tối ưu hóa nhánh ban đầu thành di chuyển có điều kiện ngay cả khi chỉ định mức tối ưu hóa cao, trong khi gcc có thể. - WiSaGaN


Nếu bạn tò mò về việc tối ưu hơn nữa có thể được thực hiện cho mã này, hãy xem xét điều này:

Bắt đầu với vòng lặp gốc:

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Với nút trao đổi vòng lặp, chúng ta có thể thay đổi vòng lặp này một cách an toàn thành:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Sau đó, bạn có thể thấy rằng if có điều kiện là không đổi trong suốt quá trình thực hiện i vòng lặp, vì vậy bạn có thể nâng if ngoài:

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

Sau đó, bạn thấy rằng vòng lặp bên trong có thể được thu gọn thành một biểu thức duy nhất, giả sử mô hình dấu chấm động cho phép nó (/ fp: nhanh được ném, ví dụ)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

Con số đó nhanh hơn 100.000 lần so với trước đây


2026
2017-07-03 02:25



Nếu bạn muốn lừa, bạn cũng có thể lấy phép nhân bên ngoài vòng lặp và thực hiện tổng hợp * = 100000 sau vòng lặp. - Jyaif
@Michael - Tôi tin rằng ví dụ này thực sự là một ví dụ về -khớp cẩu bất biến vòng lặp (LIH) tối ưu hóa và KHÔNG hoán đổi vòng lặp. Trong trường hợp này, toàn bộ vòng lặp bên trong là độc lập với vòng lặp bên ngoài và do đó có thể được treo ra khỏi vòng lặp bên ngoài, trong đó kết quả chỉ đơn giản là nhân với một tổng i của một đơn vị = 1e5. Nó làm cho không có sự khác biệt cho kết quả cuối cùng, nhưng tôi chỉ muốn thiết lập kỷ lục thẳng vì đây là một trang thường xuyên như vậy. - Yair Altman
Mặc dù không có tinh thần đơn giản của các vòng lặp trao đổi, bên trong if tại thời điểm này có thể được chuyển thành: sum += (data[j] >= 128) ? data[j] * 100000 : 0; trình biên dịch có thể giảm xuống cmovge hoặc tương đương. - Alex North-Keys
Vòng lặp ngoài là để làm cho thời gian được thực hiện bởi vòng lặp bên trong đủ lớn để cấu hình. Vậy tại sao bạn lặp lại trao đổi. Cuối cùng, vòng lặp đó sẽ bị xóa. - saurabheights
@saurabheights: Câu hỏi sai: tại sao trình biên dịch KHÔNG lặp lại trao đổi. Microbenchmarks là khó;) - Matthieu M.


Không nghi ngờ gì, một số người trong chúng ta sẽ quan tâm đến cách xác định mã có vấn đề đối với bộ dự đoán nhánh của CPU. Công cụ Valgrind cachegrind có trình mô phỏng dự đoán nhánh, được bật bằng cách sử dụng --branch-sim=yes cờ. Chạy nó qua các ví dụ trong câu hỏi này, với số vòng lặp bên ngoài giảm xuống còn 10000 và được biên dịch với g++, cung cấp những kết quả này:

Đã sắp xếp:

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

Chưa phân loại:

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

Khoan xuống đầu ra theo từng dòng được sản xuất bởi cg_annotate chúng ta thấy cho vòng lặp được đề cập:

Đã sắp xếp:

          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

Chưa phân loại:

          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

Điều này cho phép bạn dễ dàng xác định dòng có vấn đề - trong phiên bản chưa được phân loại if (data[c] >= 128) đường dây gây ra 164.050.007 chi nhánh có điều kiện bị cáo buộc sai (Bcm) theo mô hình dự báo nhánh của cachegrind, trong khi nó chỉ gây ra 10,006 trong phiên bản được sắp xếp.


Ngoài ra, trên Linux, bạn có thể sử dụng hệ thống con của bộ đếm hiệu suất để thực hiện cùng một tác vụ, nhưng với hiệu năng gốc sử dụng bộ đếm CPU.

perf stat ./sumtest_sorted

Đã sắp xếp:

 Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

Chưa phân loại:

 Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

Nó cũng có thể làm chú thích mã nguồn bằng cách tháo gỡ.

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq   
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...

Xem hướng dẫn hiệu suất để biết thêm chi tiết.


1690
2017-10-12 05:53



Điều này là đáng sợ, trong danh sách chưa được phân loại, sẽ có 50% cơ hội nhấn thêm. Bằng cách nào đó dự đoán chi nhánh chỉ có tỷ lệ bỏ lỡ 25%, làm thế nào nó có thể làm tốt hơn 50% bỏ lỡ? - TallBrianL
@ tall.b.lo: 25% là tất cả các chi nhánh - có hai các nhánh trong vòng lặp, một cho data[c] >= 128 (trong đó có tỷ lệ bỏ lỡ 50% như bạn đề xuất) và một cho điều kiện vòng lặp c < arraySize có tỷ lệ bỏ lỡ ~ 0%. - caf


Tôi chỉ đọc về câu hỏi này và câu trả lời của nó, và tôi cảm thấy một câu trả lời là mất tích.

Một cách phổ biến để loại bỏ dự đoán nhánh mà tôi thấy là hoạt động tốt trong ngôn ngữ được quản lý là tra cứu bảng thay vì sử dụng nhánh (mặc dù tôi chưa thử nghiệm trong trường hợp này).

Cách tiếp cận này hoạt động nói chung nếu:

  1. Đó là một bảng nhỏ và có khả năng được lưu trữ trong bộ xử lý
  2. Bạn đang chạy mọi thứ trong một vòng lặp khá chặt chẽ và / hoặc bộ xử lý có thể tải trước dữ liệu

Bối cảnh và lý do

Rất tiếc, vậy nghĩa là gì?

Từ góc độ bộ xử lý, bộ nhớ của bạn chậm. Để bù đắp cho sự khác biệt về tốc độ, chúng xây dựng trong một vài cache trong bộ xử lý của bạn (cache L1 / L2) để bù đắp cho điều đó. Vì vậy, hãy tưởng tượng rằng bạn đang thực hiện các phép tính tốt đẹp của mình và tìm ra rằng bạn cần một bộ nhớ. Bộ xử lý sẽ nhận được hoạt động 'tải' của nó và tải bộ nhớ vào bộ nhớ cache - và sau đó sử dụng bộ nhớ cache để thực hiện phần còn lại của các phép tính. Bởi vì bộ nhớ là tương đối chậm, 'tải' này sẽ làm chậm chương trình của bạn.

Giống như dự đoán nhánh, điều này đã được tối ưu hóa trong bộ vi xử lý Pentium: bộ vi xử lý dự đoán rằng nó cần tải một mẩu dữ liệu và cố gắng tải dữ liệu đó vào bộ đệm trước khi thao tác thực sự truy cập bộ nhớ cache. Như chúng ta đã thấy, dự đoán nhánh đôi khi đi sai lầm khủng khiếp - trong trường hợp xấu nhất bạn cần quay trở lại và thực sự chờ đợi một lần tải bộ nhớ, sẽ mất mãi mãi (nói cách khác: dự đoán chi nhánh thất bại là xấu, tải bộ nhớ sau khi dự đoán chi nhánh thất bại chỉ là khủng khiếp!).

May mắn cho chúng ta, nếu mô hình truy cập bộ nhớ có thể dự đoán được, bộ vi xử lý sẽ tải nó trong bộ đệm nhanh của nó và tất cả đều tốt.

Điều đầu tiên chúng ta cần biết là nhỏ bé? Mặc dù nhỏ hơn nói chung là tốt hơn, quy tắc chung là gắn vào bảng tra cứu có kích thước <= 4096 byte. Như một giới hạn trên: nếu bảng tra cứu của bạn lớn hơn 64K, nó có thể đáng xem xét lại.

Xây dựng một bảng

Vì vậy, chúng tôi đã tìm ra rằng chúng tôi có thể tạo ra một bảng nhỏ. Điều tiếp theo cần làm là lấy một hàm tra cứu tại chỗ. Hàm tra cứu thường là các hàm nhỏ sử dụng một vài phép toán số nguyên cơ bản (và, hoặc, xor, shift, add, remove và có thể nhân). Bạn muốn có đầu vào của bạn được dịch bởi chức năng tra cứu thành một loại 'khóa duy nhất' trong bảng của bạn, mà sau đó chỉ đơn giản là cung cấp cho bạn câu trả lời của tất cả công việc bạn muốn nó làm.

Trong trường hợp này:> = 128 có nghĩa là chúng ta có thể giữ giá trị, <128 có nghĩa là chúng ta loại bỏ nó. Cách dễ nhất để làm điều đó là sử dụng 'AND': nếu chúng ta giữ nó, chúng ta VÀ nó với 7FFFFFFF; nếu chúng ta muốn loại bỏ nó, chúng ta VÀ nó bằng 0. Lưu ý rằng 128 là một lũy thừa của 2 - vì vậy chúng ta có thể tiếp tục và tạo một bảng gồm 32768/128 số nguyên và điền nó với một số không và rất nhiều 7FFFFFFFF.

Ngôn ngữ được quản lý

Bạn có thể tự hỏi tại sao điều này hoạt động tốt trong các ngôn ngữ được quản lý. Sau khi tất cả, ngôn ngữ quản lý kiểm tra ranh giới của các mảng với một chi nhánh để đảm bảo bạn không mess lên ...

Không hẳn là chính xác lắm... :-)

Đã có khá nhiều công việc loại bỏ nhánh này cho các ngôn ngữ được quản lý. Ví dụ:

for (int i=0; i<array.Length; ++i)
   // Use array[i]

Trong trường hợp này, rõ ràng với trình biên dịch rằng điều kiện biên sẽ không bao giờ bị trúng. Ít nhất là trình biên dịch JIT của Microsoft (nhưng tôi hy vọng Java làm những việc tương tự) sẽ nhận thấy điều này và loại bỏ hoàn toàn việc kiểm tra. WOW - điều đó có nghĩa là không có chi nhánh. Tương tự như vậy, nó sẽ đối phó với các trường hợp rõ ràng khác.

Nếu bạn gặp rắc rối với tra cứu trên các ngôn ngữ được quản lý - điều quan trọng là thêm & 0x[something]FFFđể chức năng tra cứu của bạn để làm cho kiểm tra ranh giới có thể dự đoán được - và xem nó đi nhanh hơn.

Kết quả của trường hợp này

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random rnd = new Random(0);
for (int c = 0; c < arraySize; ++c)
    data[c] = rnd.Next(256);

//To keep the spirit of the code in-tact I'll make a separate lookup table
// (I assume we cannot modify 'data' or the number of loops)
int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
    lookup[c] = (c >= 128) ? c : 0;

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        // Here you basically want to use simple operations - so no
        // random branches, but things like &, |, *, -, +, etc. are fine.
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);

Console.ReadLine();

1160
2018-04-24 06:26



Bạn muốn bỏ qua nhánh dự báo, tại sao? Đó là một tối ưu hóa. - Dustin Oprea
Bởi vì không có chi nhánh nào tốt hơn một nhánh :-) Trong nhiều trường hợp, điều này đơn giản hơn rất nhiều ... nếu bạn đang tối ưu hóa, nó chắc chắn đáng để thử. Họ cũng sử dụng nó một chút trong f.ex. graphics.stanford.edu/~seander/bithacks.html - atlaste
Trong các bảng tra cứu tổng quát có thể nhanh, nhưng bạn đã chạy thử nghiệm cho điều kiện cụ thể này chưa? Bạn vẫn sẽ có một điều kiện chi nhánh trong mã của bạn, chỉ bây giờ nó được chuyển đến phần tìm kiếm bảng. Bạn vẫn sẽ không nhận được sự thăng tiến của bạn - Zain Rizvi
@Zain nếu bạn thực sự muốn biết ... Có: 15 giây với chi nhánh và 10 với phiên bản của tôi. Bất kể, đó là một kỹ thuật hữu ích để biết một trong hai cách. - atlaste
Tại sao không sum += lookup[data[j]] Ở đâu lookup là một mảng với 256 mục, số đầu tiên là 0 và số cuối cùng bằng với chỉ mục? - Kris Vandermotten


Vì dữ liệu được phân phối từ 0 đến 255 khi mảng được sắp xếp, xung quanh nửa đầu của các lần lặp sẽ không nhập if-statement ( if tuyên bố được chia sẻ bên dưới).

if (data[c] >= 128)
    sum += data[c];

Câu hỏi đặt ra là: Điều gì làm cho câu lệnh trên không được thực thi trong một số trường hợp nhất định như trong trường hợp dữ liệu được sắp xếp? Ở đây có "dự báo chi nhánh". Một yếu tố dự báo chi nhánh là một mạch kỹ thuật số cố gắng đoán một nhánh nào (ví dụ: if-then-else cấu trúc) sẽ đi trước khi điều này được biết chắc chắn. Mục đích của dự báo chi nhánh là cải thiện dòng chảy trong đường ống dẫn. Chi nhánh dự đoán đóng một vai trò quan trọng trong việc đạt được hiệu suất cao hiệu quả!

Hãy làm một số đánh dấu băng ghế dự bị để hiểu nó tốt hơn

Hiệu suất của một if-statement phụ thuộc vào điều kiện của nó có một mô hình dự đoán được. Nếu điều kiện luôn đúng hoặc luôn sai, logic dự đoán nhánh trong bộ xử lý sẽ lấy mẫu. Mặt khác, nếu mô hình là không thể đoán trước, if-statement sẽ đắt hơn nhiều.

Hãy đo lường hiệu suất của vòng lặp này với các điều kiện khác nhau:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Dưới đây là thời gian của vòng lặp với các mẫu true-false khác nhau:

Condition            Pattern                 Time (ms)

(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0            TF alternating    760

(i & 3) == 0            TFFFTFFF…          513

(i & 2) == 0            TTFFTTFF…          1675

(i & 4) == 0            TTTTFFFFTTTTFFFF… 1275

(i & 8) == 0            8T 8F 8T 8F …     752

(i & 16) == 0            16T 16F 16T 16F … 490

Một “xấu"Mô hình đúng-sai có thể tạo ra if-statement lên đến sáu lần chậm hơn so với một “tốt" mẫu! Tất nhiên, đó là mô hình tốt và đó là xấu phụ thuộc vào các hướng dẫn chính xác được tạo ra bởi trình biên dịch và trên bộ vi xử lý cụ thể.

Vì vậy, không có nghi ngờ về tác động của dự báo chi nhánh về hiệu suất!


1035
2018-02-15 07:24



Bạn không hiển thị thời gian của mẫu TF "ngẫu nhiên". - Mooing Duck
@MooingDuck Vì nó sẽ không tạo ra sự khác biệt - giá trị đó có thể là bất cứ điều gì, nhưng nó vẫn sẽ nằm trong giới hạn của các ngưỡng này. Vậy tại sao lại hiển thị một giá trị ngẫu nhiên khi bạn đã biết giới hạn? Mặc dù tôi đồng ý rằng bạn có thể hiển thị một mục đích vì mục đích hoàn thành, và 'chỉ vì nó'. - cst1992
@ cst1992: Ngay bây giờ thời gian chậm nhất của ông là TTFFTTFFTTFF, có vẻ như, với con mắt của tôi, khá có thể dự đoán được. Ngẫu nhiên vốn dĩ không thể đoán trước được, vì vậy hoàn toàn có thể nó sẽ chậm hơn, và do đó nằm ngoài giới hạn được hiển thị ở đây. OTOH, nó có thể là TTFFTTFF hoàn toàn chạm vào trường hợp bệnh lý. Không thể nói, vì anh ta không hiển thị thời gian cho ngẫu nhiên. - Mooing Duck
@MooingDuck Đối với mắt người, "TTFFTTFFTTFF" là một chuỗi có thể dự đoán được, nhưng những gì chúng ta đang nói đến ở đây là hành vi của bộ dự đoán nhánh được xây dựng thành một CPU. Dự báo nhánh không phải là nhận dạng mẫu AI; nó rất đơn giản. Khi bạn chỉ thay thế các nhánh, nó không dự đoán tốt. Trong hầu hết các mã, các nhánh đi theo cùng một cách hầu như mọi lúc; xem xét một vòng lặp thực thi hàng nghìn lần. Nhánh ở cuối vòng lặp quay trở lại điểm bắt đầu của vòng lặp 999 lần, và sau đó lần thứ nghìn làm điều gì đó khác. Một dự báo chi nhánh rất đơn giản hoạt động tốt, thông thường. - steveha
@steveha: Tôi nghĩ rằng bạn đang đưa ra các giả định về cách dự đoán chi nhánh CPU hoạt động, và tôi không đồng ý với phương pháp đó. Tôi không biết dự đoán chi nhánh tiên tiến như thế nào, nhưng tôi có vẻ nghĩ nó tiên tiến hơn bạn nhiều. Bạn có lẽ đúng, nhưng các phép đo chắc chắn sẽ tốt. - Mooing Duck


Một cách để tránh lỗi dự đoán nhánh là xây dựng bảng tra cứu và lập chỉ mục bằng cách sử dụng dữ liệu. Stefan de Bruijn thảo luận rằng trong câu trả lời của mình.

Nhưng trong trường hợp này, chúng ta biết các giá trị nằm trong khoảng [0, 255] và chúng ta chỉ quan tâm đến các giá trị> = 128. Điều đó có nghĩa là chúng ta có thể dễ dàng trích xuất một bit sẽ cho chúng ta biết liệu chúng ta có muốn giá trị hay không: dữ liệu đến đúng 7 bit, chúng tôi được để lại với bit 0 hoặc 1 bit và chúng tôi chỉ muốn thêm giá trị khi chúng tôi có 1 bit. Hãy gọi bit này là "bit quyết định".

Bằng cách sử dụng giá trị 0/1 của bit quyết định làm chỉ mục thành một mảng, chúng tôi có thể tạo mã sẽ nhanh như nhau dù dữ liệu được sắp xếp hay chưa được sắp xếp. Mã của chúng tôi sẽ luôn thêm giá trị, nhưng khi bit quyết định bằng 0, chúng tôi sẽ thêm giá trị ở đâu đó mà chúng tôi không quan tâm. Đây là mã:

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

Mã này lãng phí một nửa số cộng nhưng không bao giờ có lỗi dự đoán nhánh. Nó nhanh hơn rất nhiều trên dữ liệu ngẫu nhiên so với phiên bản với câu lệnh if thực tế.

Nhưng trong thử nghiệm của tôi, một bảng tra cứu rõ ràng là hơi nhanh hơn này, có lẽ bởi vì lập chỉ mục vào một bảng tra cứu là hơi nhanh hơn bit chuyển. Điều này cho thấy cách mã của tôi thiết lập và sử dụng bảng tra cứu (không được gọi là lut cho "Bảng tra cứu" trong mã). Đây là mã C ++:

// declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

Trong trường hợp này, bảng tra cứu chỉ có 256 byte, vì vậy nó phù hợp với bộ nhớ cache và tất cả đều nhanh. Kỹ thuật này sẽ không hoạt động tốt nếu dữ liệu là giá trị 24 bit và chúng tôi chỉ muốn một nửa trong số đó ... bảng tra cứu sẽ quá lớn để thực tế. Mặt khác, chúng ta có thể kết hợp hai kỹ thuật được hiển thị ở trên: đầu tiên thay đổi các bit trên, sau đó chỉ mục một bảng tra cứu. Đối với một giá trị 24-bit mà chúng tôi chỉ muốn giá trị nửa trên, chúng tôi có khả năng chuyển dữ liệu ngay bằng 12 bit và được để lại với giá trị 12 bit cho chỉ mục bảng. Chỉ mục bảng 12 bit ngụ ý một bảng giá trị 4096, có thể là thực tế.

EDIT: Một điều tôi quên để đưa vào.

Kỹ thuật lập chỉ mục thành mảng, thay vì sử dụng if tuyên bố, có thể được sử dụng để quyết định con trỏ để sử dụng. Tôi thấy một thư viện đã triển khai cây nhị phân và thay vì có hai con trỏ được đặt tên (pLeft và pRight hoặc bất kỳ thứ gì) có một chuỗi các con trỏ có độ dài-2 và sử dụng kỹ thuật "quyết định bit" để quyết định cái nào cần làm theo. Ví dụ: thay vì:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

thư viện này sẽ làm một cái gì đó như:

i = (x < node->value);
node = node->link[i];

Đây là liên kết đến mã này: Cây đỏ đen, Eternally Confuzzled


963
2017-07-22 08:29



Phải, bạn cũng có thể sử dụng bit trực tiếp và nhân (data[c]>>7 - cũng được thảo luận ở đâu đó ở đây); Tôi cố tình để lại giải pháp này, nhưng tất nhiên bạn là chính xác. Chỉ cần một lưu ý nhỏ: Quy tắc chung của bảng tra cứu là nếu nó phù hợp với 4KB (vì bộ đệm ẩn), nó sẽ hoạt động - tốt nhất là làm cho bảng càng nhỏ càng tốt. Đối với các ngôn ngữ được quản lý, tôi sẽ đẩy nó lên 64KB, đối với các ngôn ngữ cấp thấp như C ++ và C, tôi có thể cân nhắc lại (đó chỉ là trải nghiệm của tôi). Vì typeof(int) = 4, Tôi muốn cố gắng tối đa 10 bit. - atlaste
Tôi nghĩ rằng lập chỉ mục với giá trị 0/1 có thể sẽ nhanh hơn số nguyên nhân, nhưng tôi đoán nếu hiệu suất thực sự quan trọng bạn nên cấu hình nó. Tôi đồng ý rằng các bảng tra cứu nhỏ là cần thiết để tránh áp lực bộ nhớ cache, nhưng rõ ràng nếu bạn có bộ nhớ cache lớn hơn, bạn có thể lấy đi một bảng tra cứu lớn hơn, vì vậy 4KB là nguyên tắc nhỏ hơn một quy tắc cứng. Tôi nghĩ bạn có nghĩa là sizeof(int) == 4? Điều đó đúng với 32-bit. Điện thoại di động hai tuổi của tôi có bộ nhớ cache 32KB L1, vì vậy ngay cả bảng tra cứu 4K cũng có thể hoạt động, đặc biệt nếu các giá trị tra cứu là một byte thay vì một int. - steveha
Có thể tôi đang thiếu cái gì đó nhưng trong j bằng 0 hoặc 1 phương pháp tại sao bạn không chỉ nhân giá trị của bạn bằng j trước khi thêm nó thay vì sử dụng chỉ mục mảng (có thể sẽ được nhân với 1-j thay vì j) - Richard Tingle
@steveha Phép nhân nên nhanh hơn, tôi đã thử tìm kiếm nó trong sách Intel, nhưng không thể tìm thấy nó ... dù bằng cách nào, điểm chuẩn cũng mang lại cho tôi kết quả ở đây. - atlaste
@steveha P.S .: một câu trả lời khác có thể là int c = data[j]; sum += c & -(c >> 7); không đòi hỏi phép nhân nào cả. - atlaste


Trong trường hợp được sắp xếp, bạn có thể làm tốt hơn là dựa vào dự đoán nhánh thành công hoặc bất kỳ mẹo so sánh nhánh nào: hoàn toàn loại bỏ nhánh.

Thật vậy, mảng được phân vùng trong một vùng liền kề với data < 128 và một với data >= 128. Vì vậy, bạn nên tìm các điểm phân vùng với một tìm kiếm dichotomic (sử dụng Lg(arraySize) = 15 so sánh), sau đó thực hiện tích lũy thẳng từ thời điểm đó.

Một cái gì đó như (bỏ chọn)

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

hoặc, bị quấy rầy hơn một chút

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

Một cách tiếp cận nhanh hơn, mang lại gần đúng giải pháp cho cả hai được sắp xếp hoặc unsorted là: sum= 3137536; (giả định một phân bố thực sự thống nhất, 16384 mẫu với giá trị dự kiến ​​là 191,5) :-)


883
2017-07-24 07:57



sum= 3137536 - tài giỏi. Đó là kinda rõ ràng không phải là điểm của câu hỏi. Câu hỏi rõ ràng là giải thích các đặc tính hiệu suất đáng ngạc nhiên. Tôi có khuynh hướng nói rằng việc bổ sung std::partition thay vì std::sort có giá trị. Mặc dù câu hỏi thực tế mở rộng đến nhiều hơn chỉ là điểm chuẩn tổng hợp được đưa ra. - sehe
@ DeadMG: đây thực sự không phải là tìm kiếm nhị phân chuẩn cho một khóa đã cho, mà là tìm kiếm chỉ mục phân vùng; nó đòi hỏi một so sánh duy nhất cho mỗi lần lặp lại. Nhưng đừng dựa vào mã này, tôi chưa kiểm tra nó. Nếu bạn quan tâm đến việc triển khai chính xác được bảo đảm, hãy cho tôi biết. - Yves Daoust


Hành vi trên đang xảy ra do dự đoán chi nhánh.

Để hiểu dự đoán chi nhánh, trước hết phải hiểu Hướng dẫn đường ống:

Bất kỳ lệnh nào được chia thành một chuỗi các bước để các bước khác nhau có thể được thực thi đồng thời song song. Kỹ thuật này được gọi là đường dẫn hướng dẫn và điều này được sử dụng để tăng thông lượng trong các bộ vi xử lý hiện đại. Để hiểu điều này tốt hơn, hãy xem ví dụ trên Wikipedia.

Nói chung, các bộ vi xử lý hiện đại có đường ống khá dài, nhưng để dễ dàng, hãy xem xét 4 bước này.

  1. IF - Lấy lệnh từ bộ nhớ   
  2. ID - Giải mã lệnh   
  3. EX - Thực thi lệnh   
  4. WB - Ghi lại đăng ký CPU

Đường dẫn 4 giai đoạn nói chung cho 2 hướng dẫn. 4-stage pipeline in general

Quay lại câu hỏi trên, hãy xem xét các hướng dẫn sau:

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

Nếu không có dự đoán chi nhánh, những điều sau sẽ xảy ra:

Để thực hiện lệnh B hoặc lệnh C, bộ xử lý sẽ phải chờ cho đến khi lệnh A không đạt tới giai đoạn EX trong đường ống, vì quyết định đi đến lệnh B hoặc lệnh C phụ thuộc vào kết quả của lệnh A. Vậy là đường ống sẽ trông như thế này

khi điều kiện trả về đúng: enter image description here

Khi điều kiện trả về false: enter image description here

Như là kết quả của việc chờ kết quả của lệnh A, tổng số chu kỳ CPU đã sử dụng trong trường hợp trên (không có dự đoán nhánh; cho cả true và false) là 7.

Vậy dự đoán nhánh là gì?

Chi nhánh dự đoán sẽ cố gắng đoán theo cách mà một chi nhánh (một cấu trúc nếu-thì-khác) sẽ đi trước khi điều này được biết chắc chắn. Nó sẽ không đợi lệnh A đạt tới giai đoạn EX của đường ống, nhưng nó sẽ đoán quyết định và đi đến lệnh đó (B hoặc C trong trường hợp ví dụ của chúng ta).

Trong trường hợp đoán đúng, đường ống trông giống như sau: enter image description here

Nếu sau này nó phát hiện ra rằng dự đoán là sai thì các lệnh được thực hiện một phần sẽ bị loại bỏ và đường ống bắt đầu lại với nhánh chính xác, phát sinh chậm trễ. Thời gian bị lãng phí trong trường hợp sai lệch chi nhánh bằng số giai đoạn trong đường ống từ giai đoạn tìm nạp đến giai đoạn thực thi. Các bộ vi xử lý hiện đại có xu hướng có đường ống khá dài để độ trễ sai lệch giữa chu kỳ xung nhịp từ 10 đến 20. Đường ống càng dài thì nhu cầu tốt hơn dự báo chi nhánh.

Trong mã OP, lần đầu tiên khi có điều kiện, dự báo chi nhánh không có bất kỳ thông tin nào để dự đoán cơ sở, do đó, lần đầu tiên nó sẽ ngẫu nhiên chọn lệnh tiếp theo. Sau đó trong vòng lặp for, nó có thể đưa ra dự đoán về lịch sử. Đối với một mảng được sắp xếp theo thứ tự tăng dần, có ba khả năng:

  1.  Tất cả các phần tử nhỏ hơn 128
  2.  Tất cả các phần tử lớn hơn 128
  3.  Một số phần tử mới bắt đầu nhỏ hơn 128 và sau đó nó trở nên lớn hơn 128

Giả sử rằng người dự đoán sẽ luôn luôn giả định nhánh thực sự trong lần chạy đầu tiên.

Vì vậy, trong trường hợp đầu tiên, nó sẽ luôn luôn lấy các chi nhánh thực sự từ lịch sử tất cả các dự đoán của nó là chính xác. Trong trường hợp thứ 2, ban đầu nó sẽ dự đoán sai, nhưng sau một vài lần lặp lại, nó sẽ dự đoán chính xác. Trong trường hợp thứ 3, nó ban đầu sẽ dự đoán chính xác cho đến khi các phần tử nhỏ hơn 128. Sau đó, nó sẽ thất bại trong một thời gian và chính nó khi nó thấy thất bại dự đoán nhánh trong lịch sử.

Trong tất cả các trường hợp này, lỗi sẽ ít hơn số lượng và kết quả là chỉ một vài lần nó sẽ cần loại bỏ các lệnh được thực thi một phần và bắt đầu lại với nhánh chính xác, dẫn đến ít chu kỳ CPU hơn.

Nhưng trong trường hợp một mảng không được phân loại ngẫu nhiên, dự đoán sẽ cần loại bỏ các lệnh được thực hiện một phần và bắt đầu lại với nhánh chính xác phần lớn thời gian và dẫn đến nhiều chu kỳ CPU hơn so với mảng được sắp xếp.


697
2017-07-03 15:35



hai lệnh được thực hiện cùng nhau như thế nào? này được thực hiện với lõi CPU riêng biệt hoặc là hướng dẫn đường ống được tích hợp trong lõi cpu đơn? - M.kazem Akhgary
@ M.kazemAkhgary Đó là tất cả bên trong một lõi logic. Nếu bạn quan tâm, điều này được mô tả độc đáo ví dụ như Hướng dẫn dành cho nhà phát triển phần mềm Intel - Sergey.quixoticaxis.Ivanov


Một câu trả lời chính thức sẽ là từ

  1. Intel - Tránh Chi phí của Chi nhánh
  2. Intel - Chi nhánh và tổ chức lại vòng lặp để ngăn chặn Mispredicts
  3. Các bài báo khoa học - kiến ​​trúc máy tính dự đoán nhánh
  4. Sách: J.L. Hennessy, D.A. Patterson: Kiến trúc máy tính: một phương pháp định lượng
  5. Các bài viết trong các ấn phẩm khoa học: T.Y. Yeh, Y.N. Patt thực hiện rất nhiều trong số này trên dự đoán chi nhánh.

Bạn cũng có thể thấy từ này đáng yêu sơ đồ tại sao các chi nhánh dự đoán bị lẫn lộn.

2-bit state diagram

Mỗi phần tử trong mã ban đầu là một giá trị ngẫu nhiên

data[c] = std::rand() % 256;

do đó, người dự đoán sẽ thay đổi các bên là std::rand() thổi.

Mặt khác, một khi nó được sắp xếp, trước tiên, người dự đoán sẽ chuyển sang trạng thái không mạnh và khi giá trị thay đổi thành giá trị cao, người dự đoán sẽ trong ba lần chạy qua thay đổi tất cả các cách từ mạnh không được thực hiện mạnh.



612
2017-10-11 21:05