it-swarm-vi.com

Tại sao nhanh hơn để xử lý một mảng được sắp xếp 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. Vì một số lý do kỳ lạ, việc sắp xếp dữ liệu một cách kỳ diệu làm cho mã nhanh hơn gần 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ã sẽ chạy trong 11,54 giây.
  • Với dữ liệu được sắp xếp, mã chạy trong 1,93 giây.

Ban đầu, tôi nghĩ rằng đây có thể chỉ là một ngôn ngữ hoặc trình biên dịch dị 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ả tương tự nhưng ít cực đoan hơn.


Suy nghĩ đầu tiên của tôi là sắp xếp đưa dữ liệu vào bộ đệm, nhưng sau đó tôi nghĩ điều đó thật ngớ ngẩn vì mảng vừa được tạo.

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

Bạn là nạn nhân của dự đoán nhánh fail.


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

Hãy xem xét một ngã ba đường sắt:

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

Bây giờ để tranh luận, giả sử điều này trở lại vào những năm 1800 - trước khi liên lạc đường dài hoặc 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 đang đến. Bạn không biết nên đi theo hướng nào. Bạn dừng tàu để hỏi tài xế họ muốn hướng nào. Và sau đó bạn thiết lập công tắc một cách thích hợp.

Xe lửa nặng và có nhiều quán tính. Vì vậy, chúng mất mãi mãi để khởi động và chậm lại.

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ó tiếp tục.
  • Nếu bạn đoán sai, thuyền trưởng sẽ dừng lại, sao lưu và la mắng bạn để lật công tắc. Sau đó, nó có thể khởi động lại 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.
[.___.] Nếu bạn đoán sai quá thường xuyên , tàu sẽ mất rất nhiều thời gian để dừng lại, sao lưu và khởi động lại.


Hãy xem xét một câu lệnh if: Ở cấp độ bộ xử lý, đó là một lệnh rẽ nhánh:

Screenshot of compiled code containing an if statement

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

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

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

  • 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 xả đường ống và quay trở lại nhánh. Sau đó, bạn có thể khởi động lại con đường khác.

Nếu bạn đoán đúng mỗi lần , việc thực thi 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 mất rất nhiều thời gian để trì hoãn, quay trở lại và khởi động lại.


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

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

Nói cách khác, bạn cố gắng xác định một mẫu và làm theo mẫu đó.Đây ít nhiều là cách các công cụ dự đoán nhánh hoạt động.

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

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


Như được gợi ý từ phía trên, thủ phạm chính là câu lệnh if này:

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

Lưu ý rằng dữ liệu được phân phối đồng đều trong khoảng từ 0 đến 255. Khi dữ liệu được sắp xếp, khoảng nửa đầu của các lần lặp sẽ không nhập câu lệnh if. Sau đó, tất cả chúng sẽ nhập câu lệnh if.

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

Trực quan 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 hoàn toàn ngẫu nhiên, bộ dự báo nhánh sẽ vô dụng vì nó không thể dự đoán dữ liệu ngẫu nhiên. Do đó, có thể sẽ có khoảng 50% hiểu sai. (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 có thể làm gì?

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

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 giúp loại bỏ nhánh và thay thế nó bằng một số thao tác bitwise.

(Lưu ý rằng bản hack này không hoàn toàn tương đương với câu lệnh if gốc. 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: Lõi i7 920 @ 3,5 GHz

C++ - Visual Studio 2010 - 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 rất lớn giữa dữ liệu được sắp xếp và chưa được sắp xếp.
  • Với Hack: Không có sự khác biệt giữa dữ liệu được sắp xếp và chưa được sắp xếp.
  • Trong trường hợp C++, 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.

Một nguyên tắc chung là tránh phân nhánh phụ thuộc dữ liệu vào 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 -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 được sắp xếp - cả hai đều nhanh.

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

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

  • Nếu bạn cung cấp cho Trình biên dịch Intel mã không phân nhánh, nó sẽ hoàn toàn hợp lý hóa nó ... và 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ạnh mẽ về khả năng tối ưu hóa mã ...

30104
Mysticial

Dự đoán chi nhánh.

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

3879
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 chi nhánh được loại bỏ, như được giải thích rất hay trong câu trả lời Bí ẩn '.

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 nhánh if... else... cụ thể này là thêm một cái gì đó khi một điều kiện được thỏa mãn. Loại nhánh này có thể dễ dàng chuyển đổi thành di chuyển có điều kiện câu lệnh, sẽ được biên dịch thành một hướng dẫn di chuyển có điều kiện: cmovl, trong hệ thống x86. Chi nhánh và do đó hình phạt dự đoán chi nhánh tiềm năng được loại bỏ.

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 hướng dẫn di chuyển có điều kiện trong x86, là toán tử ternary ... ? ... : .... Vì vậy, chúng tôi viết lại tuyên bố trên thành một tương đương:

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

Trong khi duy trì khả năng đọc, chúng ta có thể kiểm tra hệ số tăng tốc.

Trên Intel Core i7 - 2600K @ 3,4 GHz và Chế độ phát hành Visual Studio 2010, đ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 bài kiểm tra. Chúng tôi nhận được một sự tăng tốc tuyệt vời khi kết quả chi nhánh là không thể dự đoán được, nhưng chúng tôi chịu đựng một chút khi dự đoán được. Trong thực tế, khi sử dụng một động thái 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 hội mà họ tạo ra. Để đơn giản, chúng tôi sử dụng hai hàm max1max2.

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ử ternary ... ? ... : ...:

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

Trên máy x86-64, GCC -S tạo hội bên dưới.

: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 mã ít hơn nhiều do sử dụng hướng dẫn cmovge. Nhưng lợi ích thực sự là max2 không liên quan đến các bước 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 thực hiện tốt hơn?

Trong bộ xử lý x86 thông thường, việc thực hiện một lệnh được chia thành nhiều giai đoạn. Roughly, 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 ta không phải đợi một hướng dẫn kết thúc để bắt đầu một hướng dẫn mới. Điều này được gọi làpipelining.

Trong trường hợp nhánh, hướng dẫn sau được xác định bởi lệnh trước, vì vậy chúng ta không thể thực hiện đường ống. Chúng ta phải chờ đợ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ư FetchDecode không phụ thuộc vào kết quả của hướng dẫn trước đó; chỉ giai đoạn sau mới cần kết quả. Vì vậy, chúng tôi chờ 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 chi nhánh khi dự đoán dễ dàng.

Cuốn sách Hệ thống máy tính: Quan điểm của lập trình viên, ấn bản thứ hai giải thích điều này một cách chi tiết. 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ộ xử lý và Mục 5.11.2 để biết cách xử lý đặc biệt đối với Dự đoán chi nhánh 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 để hội có hiệu năng tốt hơn, đôi khi một số trình biên dịch không thể (mã được đề cập đang 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 di chuyển và điều kiện di chuyển khi không thể đoán trước có thể giúp chúng ta viết mã với hiệu suất tốt hơn khi kịch bản trở nên phức tạp đến mức trình biên dịch không thể tự động tối ưu hóa chúng.

3125
WiSaGaN

Nếu bạn tò mò về việc tối ưu hóa nhiề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 ban đầu:

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

Với trao đổi vòng lặp, chúng ta có thể thay đổi vòng lặp này 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 điều kiện không đổi trong suốt quá trình thực thi vòng lặp i, do đó bạn có thể kéo if ra:

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 phẩy động cho phép nó (ví dụ:/fp: fast được ném)

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

Cái đó nhanh hơn 100.000 lần so với trước đây

2143
vulcan raven

Chắc chắn một số người trong chúng ta sẽ quan tâm đến các 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 giả lập dự báo nhánh, được bật bằng cách sử dụng cờ --branch-sim=yes. 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++, cho các kết quả sau:

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 được sắp xếp:

==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%   )

Đi sâu vào đầu ra từng dòng được tạo bởi cg_annotate chúng ta thấy cho vòng lặp đang đượ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 được 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,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 sắp xếp, dòng if (data[c] >= 128) đang gây ra 164.050.007 nhánh điều kiện dự đoán sai (Bcm) trong mô hình dự báo nhánh của bộ nhớ cache, 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 bộ đếm hiệu suất để thực hiện cùng một tác vụ, nhưng với hiệu suất 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 được sắp xếp:

 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ể thực hiện chú thích mã nguồn với sự phân tách.

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.

1784
caf

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

Một cách phổ biến để loại bỏ dự đoán chi nhánh mà tôi thấy hoạt động đặc biệt tốt trong các ngôn ngữ được quản lý là tra cứu bảng thay vì sử dụng một nhánh (mặc dù tôi đã không kiểm tra nó 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 trong bộ xử lý và
  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à tại sao

Từ góc độ bộ xử lý, bộ nhớ của bạn chậm. Để bù cho sự khác biệt về tốc độ, một vài bộ nhớ cache được tích hợp vào bộ xử lý của bạn (bộ đệm L1/L2). Vì vậy, hãy tưởng tượng rằng bạn đang thực hiện các tính toán Nice của bạn và nhận ra rằng bạn cần một phần bộ nhớ. Bộ xử lý sẽ có được hoạt động 'tải' của nó và tải phần bộ nhớ vào bộ đệm - và sau đó sử dụng bộ đệm để thực hiện phần còn lại của các phép tính. Vì bộ nhớ 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ộ xử lý Pentium: bộ xử lý dự đoán rằng nó cần tải một phần 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ự chạm vào bộ đệm. Như chúng ta đã thấy, dự đoán chi nhánh đôi khi sai lầm khủng khiếp - trong trường hợp xấu nhất bạn cần quay lại và thực sự chờ tải bộ nhớ, sẽ mất mãi mãi ( nói cách khác: thất bại dự đoán chi nhánh là xấu, tải bộ nhớ sau khi dự đoán nhánh thất bại chỉ là khủng khiếp! ).

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

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

Xây dựng 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à có được một chức năng tra cứu tại chỗ. Các hàm tra cứu thường là các hàm nhỏ sử dụng một vài thao tác số nguyên cơ bản (và, hoặc, xor, shift, add, remove và có lẽ là nhân). Bạn muốn dịch đầu vào của mình đượ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, sau đó chỉ cần 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ó thực hiện.

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 thoát khỏi nó. Cách dễ nhất để làm điều đó là sử dụng 'VÀ': nếu chúng tôi giữ nó, chúng tôi VÀ nó với 7FFFFFFF; nếu chúng ta muốn loại bỏ nó, chúng ta VÀ nó với 0. Cũng lưu ý rằng 128 là 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 vào đó một số 0 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ý. Rốt cuộc, các ngôn ngữ được quản lý kiểm tra ranh giới của các mảng với một nhánh để đảm bảo bạn không làm phiền ...

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

Đã có khá nhiều công việc loại bỏ chi 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ị ảnh hưởng. Ít nhất là trình biên dịch Microsoft JIT (nhưng tôi hy vọng Java cũng làm những điều tương tự) sẽ chú ý đ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ự, 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 việc tra cứu bằng các ngôn ngữ được quản lý - điều quan trọng là thêm & 0x[something]FFF vào chức năng tra cứu của bạn để kiểm tra ranh giới có thể dự đoán được - và xem nó sẽ 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 random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
    data[c] = random.Next(256);
}

/*To keep the spirit of the code intact, 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();
1247
atlaste

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

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

Câu hỏi 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ự đoán chi nhánh". Công cụ dự đoán nhánh là một mạch kỹ thuật số cố gắng đoán xem nhánh nào (ví dụ: cấu trúc if-then-else) sẽ đi trước khi điều này được biết chắc chắn. Mục đích của bộ dự báo 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!

Hãy thực hiện một số đánh dấu băng ghế để hiểu rõ hơn

Hiệu suất của câu lệnh if- phụ thuộc vào việc điều kiện của nó có mẫu dự đoán hay không. Nếu điều kiện luôn luôn đúng hoặc luôn luôn sai, logic dự đoán nhánh trong bộ xử lý sẽ chọn mẫu. Mặt khác, nếu mô hình không thể đoán trước, câu lệnh if- 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 đúng-sai 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 mẫu xấu Mô hình đúng-sai có thể tạo ra một câu lệnh if- chậm hơn đến sáu lần so với một mẫu tốt mô hình! Tất nhiên, mẫu nào tốt và xấu phụ thuộc vào các hướng dẫn chính xác được tạo bởi trình biên dịch và trên bộ xử lý cụ thể.

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

1118
Saqlain

Một cách để tránh các lỗi dự đoán nhánh là xây dựng bảng tra cứu và lập chỉ mục cho nó 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 tôi biết các giá trị nằm trong phạm vi [0, 255] và chúng tôi chỉ quan tâm đến các giá trị> = 128. Điều đó có nghĩa là chúng tôi có thể dễ dàng trích xuất một bit sẽ cho chúng tôi biết liệu chúng tôi có muốn giá trị hay không: bằng cách thay đổi dữ liệu ở bên phải 7 bit, chúng tôi chỉ còn lại 0 bit 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 ta có thể tạo mã sẽ nhanh như nhau cho dù dữ liệu được sắp xếp hay không được sắp xếp. Mã của chúng tôi sẽ luôn thêm một 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ố bổ sung nhưng không bao giờ có lỗi dự đoán chi 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 nhanh hơn một chút so với điều này, có lẽ vì việc lập chỉ mục vào bảng tra cứu nhanh hơn một chút so với dịch chuyển bit. Đ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 (được gọi một cách đơn giản 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, do đó, nó phù hợp độc đáo trong bộ đệm 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à các giá trị 24 bit và chúng tôi chỉ muốn một nửa trong số chúng ... bảng tra cứu sẽ quá lớn để trở nê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 dịch chuyển các bit qua, sau đó lập chỉ mục một bảng tra cứu. Đối với giá trị 24 bit mà chúng tôi chỉ muốn giá trị nửa trên cùng, chúng tôi có thể có khả năng dịch chuyển dữ liệu sang phải 12 bit và được để lại giá trị 12 bit cho chỉ mục bảng. Một chỉ mục bảng 12 bit ngụ ý một bảng gồm 4096 giá trị, có thể là thực tế.

Kỹ thuật lập chỉ mục thành một mảng, thay vì sử dụng câu lệnh if, có thể được sử dụng để quyết định sử dụng con trỏ nào. 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 (pLeftpRight hoặc bất cứ thứ gì) có một mảng dài 2 con trỏ và sử dụng kỹ thuật "bit quyết định" để quyết định nên theo dõi cái nào. 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à một liên kết đến mã này: Cây đen đỏ , Được xác nhận bên trong

1039
steveha

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ỳ thủ thuật so sánh không phân nhánh nào: loại bỏ hoàn toàn 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 mảng khác có data >= 128. Vì vậy, bạn nên tìm điểm phân vùng với tìm kiếm nhị phân (sử dụng so sánh Lg(arraySize) = 15), sau đó thực hiện tích lũy thẳng từ điểm đó.

Một cái gì đó như (không được kiểm tra)

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, hơi khó hiểu hơn

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

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

942
Yves Daoust

Các hành vi trên đang xảy ra vì dự đoán chi nhánh.

Để hiểu dự đoán chi nhánh, trước tiên người ta phải hiểu Đường ống chỉ dẫn :

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 hiện đồng thời song song. Kỹ thuật này được gọi là đường ống dẫn và điều này được sử dụng để tăng thông lượng trong các bộ xử lý hiện đại. Để hiểu rõ hơn về điều này, vui lòng xem ví dụ này trên Wikipedia .

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

  1. NẾU - Lấy hướng dẫn từ bộ nhớ
  2. ID - Giải mã hướng dẫn
  3. EX - Thực hiện hướng dẫn
  4. WB - Ghi lại vào thanh ghi CPU

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

Quay trở 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, điều sau đây sẽ xảy ra:

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

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

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

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ả đúng và sai) là 7.

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

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

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

Nếu sau đó phát hiện ra rằng đoán 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 với nhánh chính xác, gây ra sự chậm trễ. Thời gian bị lãng phí trong trường hợp phân tích sai chi nhánh bằng số lượng 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ó các đường ống khá dài do đó độ trễ phát âm sai nằm trong khoảng từ 10 đến 20 chu kỳ xung nhịp. Đường ống càng dài thì nhu cầu về một công cụ dự đoán nhánh tốt càng lớn.

Trong mã của OP, lần đầu tiên khi có điều kiện, bộ dự đoán nhánh không có bất kỳ thông tin nào để đưa ra dự đoán, vì vậy lần đầu tiên nó sẽ chọn ngẫu nhiên hướng dẫn tiếp theo. Sau đó trong vòng lặp for, nó có thể dựa trên 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 yếu tố nhỏ hơn 128
  2. Tất cả các yếu tố đều lớn hơn 128
  3. Một số yếu tố bắt đầu mới nhỏ hơn 128 và sau đó nó trở nên lớn hơn 128

Chúng ta hãy giả định rằng người dự đoán sẽ luôn đảm nhận 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 lấy nhánh thực sự vì trong 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, nó sẽ dự đoán chính xác. Trong trường hợp thứ 3, ban đầu nó 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 thấy lỗ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ẽ quá ít về số lượng và kết quả là chỉ cần một vài lần cần loại bỏ các hướng dẫn được thực hiện một phần và bắt đầu lại với nhánh chính xác, dẫn đến chu kỳ CPU ít hơn.

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

765
Harsh Sharma

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

  1. Intel - Tránh chi phí cho việc hiểu sai chi nhánh
  2. Intel - Sắp xếp lại chi nhánh và vòng lặp để ngăn chặn các hành vi sai trái
  3. Tài liệu khoa học - kiến ​​trúc máy tính dự đoán chi nhánh
  4. Sách: J.L. Hennessy, D.A. Patterson: Kiến trúc máy tính: một cách tiếp cận định lượng
  5. Các bài báo 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 các dự đoán chi nhánh.

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

 2-bit state diagram

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

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

do đó, công cụ dự đoán sẽ thay đổi hai bên khi đòn std::Rand().

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


669
Surt

Trong cùng một dòng (tôi nghĩ rằng điều này không được làm nổi bật bởi bất kỳ câu trả lời nào), thật tốt khi đề cập rằng đôi khi (đặc biệt là trong phần mềm có hiệu năng quan trọng giống như trong nhân Linux), bạn có thể tìm thấy một số câu lệnh như sau:

if (likely( everything_is_ok ))
{
    /* Do something */
}

hoặc tương tự:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

Cả likely()unlikely() trên thực tế là các macro được xác định bằng cách sử dụng một cái gì đó như __builtin_expect của GCC để giúp trình biên dịch chèn mã dự đoán để ưu tiên điều kiện có tính đến thông tin do người dùng cung cấp. GCC hỗ trợ các nội dung khác có thể thay đổi hành vi của chương trình đang chạy hoặc phát ra các hướng dẫn cấp thấp như xóa bộ đệm, v.v. Xem tài liệu này đi qua các nội dung sẵn có của GCC.

Thông thường loại tối ưu hóa này chủ yếu được tìm thấy trong các ứng dụng thời gian thực hoặc hệ thống nhúng trong đó thời gian thực hiện là vấn đề quan trọng. Ví dụ: nếu bạn đang kiểm tra một số điều kiện lỗi chỉ xảy ra 1/10000000 lần, thì tại sao không thông báo cho trình biên dịch về điều này? Theo cách này, theo mặc định, dự đoán nhánh sẽ cho rằng điều kiện là sai.

634
rkachach

Các hoạt động Boolean thường được sử dụng trong C++ tạo ra nhiều nhánh trong chương trình được biên dịch. Nếu các nhánh này nằm trong các vòng lặp và khó dự đoán thì chúng có thể làm chậm quá trình thực thi đáng kể. Các biến Boolean được lưu dưới dạng số nguyên 8 bit với giá trị 0 cho false1 cho true.

Các biến Boolean được xác định quá mức theo nghĩa là tất cả các toán tử có biến Boolean là kiểm tra đầu vào nếu đầu vào có bất kỳ giá trị nào khác ngoài 0 hoặc 1, nhưng các toán tử có Booleans là đầu ra không thể tạo ra giá trị nào khác ngoài 0 hoặc 1. Điều này làm cho các hoạt động với các biến Boolean là đầu vào kém hiệu quả hơn mức cần thiết. Xem xét ví dụ:

bool a, b, c, d;
c = a && b;
d = a || b;

Điều này thường được trình biên dịch triển khai theo cách sau:

bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}

Mã này là xa tối ưu. Các chi nhánh có thể mất nhiều thời gian trong trường hợp dự đoán sai. Các hoạt động Boolean có thể được thực hiện hiệu quả hơn nhiều nếu biết chắc chắn rằng các toán hạng không có giá trị nào khác ngoài 01. Lý do tại sao trình biên dịch không đưa ra giả định như vậy là các biến có thể có các giá trị khác nếu chúng chưa được khởi tạo hoặc đến từ các nguồn không xác định. Mã trên có thể được tối ưu hóa nếu ab đã được khởi tạo thành các giá trị hợp lệ hoặc nếu chúng đến từ các toán tử tạo ra đầu ra Boolean. Mã được tối ưu hóa trông như thế này:

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

char được sử dụng thay vì bool để có thể sử dụng các toán tử bitwise (&|) thay cho các toán tử Boolean (&&||). Các toán tử bitwise là các lệnh đơn chỉ mất một chu kỳ xung nhịp. Toán tử OR (|) hoạt động ngay cả khi ab có các giá trị khác ngoài 0 hoặc 1. Toán tử AND (&) và toán tử EXCLUSIVE OR (^) có thể cho kết quả không nhất quán nếu toán hạng có các giá trị khác ngoài 01.

~ không thể được sử dụng cho KHÔNG. Thay vào đó, bạn có thể tạo Boolean KHÔNG trên một biến được biết là 0 hoặc 1 bằng cách XOR'ing nó với 1:

bool a, b;
b = !a;

có thể được tối ưu hóa để:

char a = 0, b;
b = a ^ 1;

a && b không thể được thay thế bằng a & b nếu b là một biểu thức không nên được đánh giá nếu afalse (&& sẽ không đánh giá b, & sẽ). Tương tự, không thể thay thế a || b bằng a | b nếu b là một biểu thức không nên được đánh giá nếu atrue.

Sử dụng toán tử bitwise sẽ thuận lợi hơn nếu toán hạng là biến so với nếu toán hạng là so sánh:

bool a; double x, y, z;
a = x > y && z < 5.0;

là tối ưu trong hầu hết các trường hợp (trừ khi bạn mong muốn biểu thức && tạo ra nhiều dự đoán sai chi nhánh).

603
Maciej

Chắc chắn rồi!...

Dự đoán nhánh làm cho logic chạy chậm hơn, do việc chuyển đổi xảy ra trong mã của bạn! Giống như bạn đang đi trên một con đường thẳng hoặc một con đường có rất nhiều ngã rẽ, chắc chắn con đường thẳng sẽ được thực hiện nhanh hơn! ...

Nếu mảng được sắp xếp, điều kiện của bạn là sai ở bước đầu tiên: data[c] >= 128, sau đó trở thành giá trị thực cho toàn bộ đường đến cuối đường. Đó là cách bạn đi đến cuối logic nhanh hơn. Mặt khác, bằng cách sử dụng một mảng chưa được sắp xếp, bạn cần rất nhiều thao tác xoay và xử lý khiến mã của bạn chạy chậm hơn chắc chắn ...

Nhìn vào hình ảnh tôi tạo ra cho bạn dưới đây. Con đường nào sẽ được hoàn thành nhanh hơn?

 Branch Prediction

Vì vậy, theo chương trình, dự đoán nhánh khiến quá trình chậm hơn ...

Cuối cùng, thật tốt khi biết chúng tôi có hai loại dự đoán nhánh mà mỗi loại sẽ ảnh hưởng đến mã của bạn khác nhau:

1. Tĩnh

2. Động

 Branch Prediction

Dự đoán nhánh tĩnh được sử dụng bởi bộ vi xử lý trong lần đầu tiên gặp nhánh có điều kiện và dự đoán nhánh động được sử dụng để thực hiện thành công mã nhánh có điều kiện.

Để viết mã của bạn một cách hiệu quả để tận dụng các quy tắc này, khi viết if-other hoặc switch statement, trước tiên hãy kiểm tra các trường hợp phổ biến nhất và làm việc dần dần xuống mức thấp nhất. Các vòng lặp không nhất thiết yêu cầu bất kỳ thứ tự mã đặc biệt nào cho dự đoán nhánh tĩnh, vì chỉ điều kiện của trình vòng lặp thường được sử dụng.

280
Alireza

Câu hỏi này đã được trả lời xuất sắc nhiều lần. Tuy nhiên, tôi vẫn muốn thu hút sự chú ý của nhóm vào một phân tích thú vị khác.

Gần đây, ví dụ này (được sửa đổi một chút) cũng được sử dụng như một cách để chứng minh làm thế nào một đoạn mã có thể được định hình trong chính chương trình trên Windows. Đồng thời, tác giả cũng chỉ ra cách sử dụng kết quả để xác định nơi mã dành phần lớn thời gian của nó trong cả trường hợp được sắp xếp & chưa sắp xếp. Cuối cùng, tác phẩm cũng cho thấy cách sử dụng một tính năng ít được biết đến của HAL (Lớp trừu tượng phần cứng) để xác định mức độ sai lầm của chi nhánh đang xảy ra trong trường hợp chưa được sắp xếp.

Liên kết có tại đây: http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htmlm

262
ForeverLearning

Như những gì đã được đề cập bởi những người khác, những gì đằng sau bí ẩn là Dự đoán chi nhánh .

Tôi không cố gắng thêm một cái gì đó nhưng giải thích khái niệm theo một cách khác. Có một giới thiệu ngắn gọn trên wiki có chứa văn bản và sơ đồ. Tôi thích cách giải thích dưới đây sử dụng sơ đồ để xây dựng Dự đoán chi nhánh theo trực giác.

Trong kiến ​​trúc máy tính, bộ dự báo nhánh là một mạch kỹ thuật số cố gắng đoán xem nhánh nào (ví dụ: cấu trúc if-then-other) sẽ đi trước khi điều này được biết chắc chắn. Mục đích của bộ dự báo nhánh là cải thiện dòng chảy trong đường ống dẫn. Các bộ dự báo nhánh đóng một vai trò quan trọng trong việc đạt được hiệu suất cao trong nhiều kiến ​​trúc bộ vi xử lý hiện đại như x86.

Phân nhánh hai chiều thường được thực hiện với một lệnh nhảy có điều kiện. Bước nhảy có điều kiện có thể "không được thực hiện" và tiếp tục thực hiện với nhánh mã đầu tiên ngay sau bước nhảy có điều kiện hoặc có thể được "lấy" và nhảy đến một vị trí khác trong bộ nhớ chương trình nơi có nhánh mã thứ hai lưu trữ. Người ta không biết chắc chắn liệu một bước nhảy có điều kiện sẽ được thực hiện hay không được thực hiện cho đến khi điều kiện được tính toán và bước nhảy có điều kiện đã qua giai đoạn thực hiện trong đường dẫn lệnh (xem hình 1).

 figure 1

Dựa trên kịch bản được mô tả, tôi đã viết một bản demo hoạt hình để cho thấy cách thực hiện các hướng dẫn trong một đường ống dẫn trong các tình huống khác nhau.

  1. Nếu không có Dự đoán chi nhánh.

Nếu không có dự đoán nhánh, bộ xử lý sẽ phải đợi cho đến khi lệnh nhảy có điều kiện vượt qua giai đoạn thực thi trước khi lệnh tiếp theo có thể vào giai đoạn tìm nạp trong đường ống.

Ví dụ chứa ba hướng dẫn và hướng dẫn đầu tiên là hướng dẫn nhảy có điều kiện. Hai lệnh sau có thể đi vào đường ống cho đến khi lệnh nhảy có điều kiện được thực thi.

 without branch predictor

Sẽ mất 9 chu kỳ đồng hồ để hoàn thành 3 hướng dẫn.

  1. Sử dụng Chi nhánh dự đoán và không thực hiện bước nhảy có điều kiện. Giả sử rằng dự đoán là không thực hiện bước nhảy có điều kiện.

 enter image description here

Sẽ mất 7 chu kỳ đồng hồ để hoàn thành 3 hướng dẫn.

  1. Sử dụng Chi nhánh dự đoán và thực hiện một bước nhảy có điều kiện. Giả sử rằng dự đoán là không thực hiện bước nhảy có điều kiện.

 enter image description here

Sẽ mất 9 chu kỳ đồng hồ để hoàn thành 3 hướng dẫn.

Thời gian bị lãng phí trong trường hợp phân tích sai chi nhánh bằng số lượng 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ó các đường ống khá dài do đó độ trễ phát âm sai nằm trong khoảng từ 10 đến 20 chu kỳ xung nhịp. Kết quả là, làm cho một đường ống dài hơn làm tăng nhu cầu về một công cụ dự đoán nhánh tiên tiến hơn.

Như bạn có thể thấy, có vẻ như chúng ta không có lý do gì để không sử dụng Chi nhánh dự đoán.

Đây là một bản demo khá đơn giản làm rõ phần rất cơ bản của Chi nhánh dự đoán. Nếu những gifs đó gây phiền nhiễu, xin vui lòng xóa chúng khỏi câu trả lời và khách truy cập cũng có thể lấy bản demo từ git

176
Gearon

Chi nhánh dự đoán tăng!

Điều quan trọng là phải hiểu rằng việc hiểu sai chi nhánh không làm chậm các chương trình. Chi phí của một dự đoán bị bỏ lỡ cũng giống như dự đoán nhánh không tồn tại và bạn chờ đợi đánh giá biểu thức để quyết định chạy mã nào (giải thích thêm trong đoạn tiếp theo).

if (expression)
{
    // Run 1
} else {
    // Run 2
}

Bất cứ khi nào có câu lệnh if-else\switch, biểu thức phải được ước tính để xác định khối nào sẽ được thực thi. Trong mã hội được tạo bởi trình biên dịch, các lệnh có điều kiện nhánh được chèn vào.

Lệnh rẽ nhánh có thể khiến máy tính bắt đầu thực hiện một chuỗi lệnh khác và do đó lệch khỏi hành vi mặc định của lệnh thực thi theo thứ tự (nghĩa là nếu biểu thức là sai, chương trình bỏ qua mã của khối if) tùy thuộc vào một số điều kiện, là đánh giá biểu hiện trong trường hợp của chúng tôi.

Điều đó đang được nói, trình biên dịch cố gắng dự đoán kết quả trước khi nó thực sự được đánh giá. Nó sẽ tìm nạp các hướng dẫn từ khối if và nếu biểu thức đó là đúng, thì thật tuyệt vời! Chúng tôi đã đạt được thời gian cần thiết để đánh giá nó và đạt được tiến bộ trong mã; nếu không thì chúng ta đang chạy mã sai, đường ống bị tuôn ra và khối chính xác được chạy.

Hình dung:

Giả sử bạn cần chọn tuyến đường 1 hoặc tuyến đường 2. Chờ đối tác kiểm tra bản đồ, bạn đã dừng tại ## và chờ đợi hoặc bạn chỉ có thể chọn tuyến đường 1 và nếu bạn may mắn (tuyến đường 1 là tuyến đường chính xác), sau đó, thật tuyệt khi bạn không phải đợi đối tác kiểm tra bản đồ (bạn đã tiết kiệm thời gian để anh ấy kiểm tra bản đồ), nếu không bạn sẽ quay lại.

Trong khi xả đường ống là siêu nhanh, ngày nay việc đánh bạc này là xứng đáng. Dự đoán dữ liệu được sắp xếp hoặc dữ liệu thay đổi chậm luôn dễ dàng và tốt hơn so với dự đoán thay đổi nhanh.

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------
168
Tony Tannous

Đó là về dự đoán chi nhánh. Nó là gì?

  • Công cụ dự đoán nhánh là một trong những kỹ thuật cải tiến hiệu suất cổ xưa mà vẫn tìm thấy sự liên quan đến các kiến ​​trúc hiện đại. Trong khi các kỹ thuật dự đoán đơn giản cung cấp tra cứu nhanh và hiệu quả năng lượng, họ phải chịu tỷ lệ sai lầm cao.

  • Mặt khác, dự đoán nhánh phức tạp, dựa trên thần kinh hoặc các biến thể của dự đoán nhánh hai cấp độ, cung cấp độ chính xác dự đoán tốt hơn, nhưng chúng tiêu thụ nhiều năng lượng hơn và độ phức tạp tăng theo cấp số nhân.

  • Thêm vào đó, trong các kỹ thuật dự đoán phức tạp, thời gian để dự đoán các nhánh rất cao, từ 2 đến 5 chu kỳ, có thể so sánh với thời gian thực hiện của các nhánh thực tế.

  • Dự đoán chi nhánh về cơ bản là một vấn đề tối ưu hóa (tối thiểu hóa) trong đó nhấn mạnh vào việc đạt được tỷ lệ bỏ lỡ thấp nhất có thể, tiêu thụ điện năng thấp và độ phức tạp thấp với các nguồn lực tối thiểu.

Thực sự có ba loại nhánh khác nhau:

Chuyển tiếp các nhánh có điều kiện - dựa trên điều kiện thời gian chạy, PC (bộ đếm chương trình) được thay đổi để trỏ đến một địa chỉ chuyển tiếp trong luồng lệnh.

Các nhánh có điều kiện lạc hậu - PC được thay đổi thành điểm lùi trong luồng lệnh. Nhánh dựa trên một số điều kiện, chẳng hạn như phân nhánh ngược về đầu vòng lặp chương trình khi một bài kiểm tra ở cuối vòng lặp cho biết vòng lặp sẽ được thực hiện lại.

Các nhánh vô điều kiện - bao gồm các bước nhảy, các thủ tục gọi và trả về không có điều kiện cụ thể. Ví dụ: một lệnh nhảy vô điều kiện có thể được mã hóa bằng ngôn ngữ hội là "jmp" và luồng lệnh phải ngay lập tức được dẫn đến vị trí đích được chỉ ra bởi lệnh nhảy, trong khi bước nhảy có điều kiện có thể được mã hóa là "jmpne" sẽ chỉ chuyển hướng luồng lệnh nếu kết quả so sánh hai giá trị trong hướng dẫn "so sánh" trước đó cho thấy các giá trị không bằng nhau. (Lược đồ địa chỉ được phân đoạn được sử dụng bởi kiến ​​trúc x86 làm tăng thêm độ phức tạp, vì các bước nhảy có thể là "gần" (trong một phân đoạn) hoặc "xa" (bên ngoài phân khúc). Mỗi loại có tác dụng khác nhau đối với thuật toán dự đoán nhánh.)

Dự đoán nhánh tĩnh/động : Dự đoán nhánh tĩnh được sử dụng bởi bộ vi xử lý khi lần đầu tiên gặp nhánh có điều kiện và dự đoán nhánh động được sử dụng để thực hiện thành công mã nhánh có điều kiện.

Tài liệu tham khảo:

113
Farhad

Bên cạnh thực tế là dự đoán nhánh có thể làm bạn chậm lại, một mảng được sắp xếp có một lợi thế khác:

Bạn có thể có một điều kiện dừng thay vì chỉ kiểm tra giá trị, theo cách này bạn chỉ lặp qua các dữ liệu liên quan và bỏ qua phần còn lại.
[.__.] Dự đoán chi nhánh sẽ chỉ bỏ lỡ một lần.

 // sort backwards (higher values first), may be in some other part of the code
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }
107
Yochai Timmer

Trên ARM, không có chi nhánh cần thiết, bởi vì mọi lệnh đều có trường điều kiện 4 bit, được kiểm tra với chi phí bằng không. Điều này giúp loại bỏ sự cần thiết của các nhánh ngắn và sẽ không có dự đoán chi nhánh nào. Do đó, phiên bản được sắp xếp sẽ chạy chậm hơn phiên bản chưa được sắp xếp trên ARM, do có thêm chi phí sắp xếp. Vòng lặp bên trong sẽ trông giống như sau:

MOV R0, #0     // R0 = sum = 0
MOV R1, #0     // R1 = c = 0
ADR R2, data   // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop    // Inner loop branch label
    LDRB R3, [R2, R1]     // R3 = data[c]
    CMP R3, #128          // compare R3 to 128
    ADDGE R0, R0, R3      // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1        // c++
    CMP R1, #arraySize    // compare c to arraySize
    BLT inner_loop        // Branch to inner_loop if c < arraySize
103
Luke Hutchison

Các mảng được sắp xếp được xử lý nhanh hơn một mảng chưa được sắp xếp, do hiện tượng được gọi là dự đoán nhánh.

Bộ dự báo nhánh là một mạch kỹ thuật số (trong kiến ​​trúc máy tính) đang cố gắng dự đoán một nhánh sẽ đi theo hướng nào, cải thiện dòng chảy trong đường dẫn lệnh. Mạch/máy tính dự đoán bước tiếp theo và thực hiện nó.

Đưa ra một dự đoán sai dẫn đến việc quay lại bước trước đó và thực hiện với một dự đoán khác. Giả sử dự đoán là chính xác, mã sẽ tiếp tục bước tiếp theo. Dự đoán sai dẫn đến lặp lại cùng một bước, cho đến khi dự đoán đúng xảy ra.

Câu trả lời cho câu hỏi của bạn rất đơn giản.

Trong một mảng chưa được sắp xếp, máy tính đưa ra nhiều dự đoán, dẫn đến tăng khả năng xảy ra lỗi. Trong khi đó, trong sắp xếp, máy tính đưa ra ít dự đoán hơn làm giảm khả năng xảy ra lỗi. Đưa ra dự đoán nhiều hơn đòi hỏi nhiều thời gian hơn.

Mảng được sắp xếp: Đường thẳng

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

Mảng không được sắp xếp: Đường cong

______   ________
|     |__|

Dự đoán chi nhánh: Đoán/dự đoán đường nào là thẳng và đi theo đường mà không cần kiểm tra

___________________________________________ Straight road
 |_________________________________________|Longer road

Mặc dù cả hai con đường đều đến cùng một đích, nhưng con đường thẳng lại ngắn hơn và con đường kia dài hơn. Nếu sau đó bạn chọn nhầm người khác, không có đường quay lại, và vì vậy bạn sẽ lãng phí thêm thời gian nếu bạn chọn con đường dài hơn. Điều này tương tự với những gì xảy ra trên máy tính và tôi hy vọng điều này sẽ giúp bạn hiểu rõ hơn.


Ngoài ra tôi muốn trích dẫn @Simon_Weaver từ các bình luận:

Nó không đưa ra dự đoán ít hơn - nó làm cho dự đoán không chính xác ít hơn. Nó vẫn phải dự đoán cho mỗi lần qua vòng lặp ..

92
Omkaar.K

Giả định bởi các câu trả lời khác mà người ta cần sắp xếp dữ liệu là không chính xác.

Đoạn mã sau không sắp xếp toàn bộ mảng, mà chỉ phân đoạn 200 phần tử của nó, và do đó chạy nhanh nhất.

Chỉ sắp xếp các phần tử k hoàn thành quá trình tiền xử lý trong thời gian tuyến tính thay vì n.log(n).

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

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

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

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

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

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

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

Điều này cũng "chứng minh" rằng nó không liên quan gì đến bất kỳ vấn đề thuật toán nào như thứ tự sắp xếp và nó thực sự là dự đoán nhánh.

14
user2297550

Bởi vì nó được sắp xếp!

Thật dễ dàng để lấy và thao tác dữ liệu theo thứ tự hơn là không có thứ tự.

Cũng giống như cách tôi chọn hàng may mặc từ các cửa hàng (đặt hàng) và từ tủ quần áo của tôi (rối tung lên).

0
Arun Joshla