Tại sao xử lý một mảng đã sắp xếp nhanh hơn xử lý một mảng không được sắp xếp?

25045
GManNickG 2012-06-28 03:51.

Đây là một đoạn mã C ++ cho thấy một số hành vi 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 thần kỳ giúp 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;
}
  • Nếu không 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ĩ đâ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ử 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 khắc nghiệt hơn.


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

  • Điều gì đang xảy ra?
  • Tại sao xử lý một mảng đã sắp xếp nhanh hơn xử lý một mảng không được sắp xếp?

Mã là tổng hợp một số thuật ngữ độc lập, vì vậy thứ tự sẽ không thành vấn đề.

26 answers

32502
Mysticial 2012-06-28 03:56.

Bạn là nạn nhân của dự đoán nhánh không thành công.


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

Xem xét một giao lộ đường sắt:

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

Bây giờ để tranh luận, hãy giả sử điều này trở lại những năm 1800 - trước khi có liên lạc vô tuyến hoặc đường dài.

Bạn là người điều hành một ngã ba và bạn nghe thấy một đoàn tàu đang chạy tới. Bạn không biết nó phải đi theo con đường nào. Bạn dừng tàu để hỏi người lái tàu xem họ muốn đi hướng nào. Và sau đó bạn đặt 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, họ mất vĩnh viễn để khởi động và chạy chậm lại.

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

  • Nếu bạn đoán đúng, nó sẽ tiếp tục.
  • Nếu bạn đoán sai, đội trưởng sẽ dừng lại, lùi lại và quát bạn để lật công tắc. Sau đó, nó có thể khởi động lại theo đường dẫn khác.

Nếu bạn đoán đúng mọi lúc , 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ẽ mất rất nhiều thời gian để dừng lại, lùi xe và khởi động lại.


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

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 tạm dừng thực hiện và đợi cho đến khi các hướng dẫn trước đó hoàn tất. Sau đó, bạn tiếp tục đi xuống con đường chính xác.

Các bộ vi 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à "chậm lại".

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

  • 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à lăn trở lại nhánh. Sau đó, bạn có thể khởi động lại theo đường dẫn khác.

Nếu bạn đoán đúng mọi lúc , 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 sẽ mất rất nhiều thời gian để dừng, quay lại và khởi động lại.


Đây là dự đoán nhánh. Tôi thừa nhận đó không phải là sự so sánh 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 phút cuối cùng.

Vì vậy, bạn sẽ đoán một cách chiến lược như thế nào để giảm thiểu số lần tàu phải lùi và đi xuống con đường khác? Bạn nhìn vào lịch sử quá khứ! Nếu tàu đi bên trái 99% thời gian, thì bạn đoán là bên trái. Nếu nó thay đổi, thì bạn thay thế các phỏng đoán của mình. Nếu nó đi một chiều ba lần, bạn cũng đ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 nó. Đây ít nhiều là cách hoạt động của các công cụ dự đoán nhánh.

Hầu hết các ứng dụng đều có các nhánh hoạt động tốt. Vì vậy, các công cụ dự đoán nhánh hiện đại thường sẽ đạt được tỷ lệ truy cập> 90%. Nhưng khi đối mặt với các nhánh không thể đoán trước và không có các mẫu dễ nhận biết, các công 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ư đã gợi ý ở trên, thủ phạm 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ả họ sẽ nhập câu lệnh if.

Điều này rất thân thiện với bộ dự đoán chi nhánh vì 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 cũng sẽ dự đoán chính xác nhánh ngoại trừ một vài lần lặp lại sau khi nó chuyển hướng.

Hình dung 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, công cụ dự đoán nhánh sẽ trở nên vô dụng, vì nó không thể dự đoán dữ liệu ngẫu nhiên. Vì vậy, có thể sẽ có khoảng 50% dự đoán sai (không tốt hơn là đ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 động thái có điều kiện, bạn có thể thử một số phương pháp hack 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ỏ nhánh và thay thế nó bằng một số hoạt động 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 ban đầu. Nhưng trong trường hợp này, nó hợp lệ với 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ó một 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 ++, việ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 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 có -O3hoặc -ftree-vectorizetrê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.

    (Hoặc hơi nhanh: đối với trường hợp đã được sắp xếp, cmovcó thể chậm hơn, đặc biệt nếu GCC đặt nó vào đường dẫn quan trọng thay vì chỉ add, đặc biệt là trên Intel trước Broadwell, nơi cmovcó độ trễ 2 chu kỳ: cờ tối ưu hóa gcc-3 làm cho mã chậm hơn -O2 )

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

  • Intel C ++ Compiler (ICC) 11 làm được điều kỳ diệu. Nó hoán đổi giữa hai vòng lặp , do đó đưa nhánh không thể đoán trước ra vòng ngoài. Vì vậy, nó không chỉ miễn nhiễm với các nghi ngờ sai lầm mà còn nhanh hơn gấp đôi so với bất cứ thứ gì VC ++ và GCC có thể tạo ra! Nói cách khác, ICC đã tận dụng vòng lặp 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 nhánh, nó sẽ chỉ vectơ hóa nó ... và nhanh như với nhánh (với sự 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 rất nhiều về khả năng tối ưu hóa mã của chúng ...

4212
Daniel Fischer 2012-06-28 03:54.

Dự đoán rẽ nhánh.

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

3409
WiSaGaN 2012-06-28 16:14.

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 được loại bỏ, như được giải thích rõ ràng trong câu trả lời của Mysticial .

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 if... else...nhánh 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 câu lệnh di chuyển có điều kiện , câu lệnh này sẽ được biên dịch thành lệnh di chuyển có điều kiện : cmovl, trong một x86hệ thống. 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++, báo cáo kết quả, trong đó sẽ biên dịch trực tiếp (không có bất kỳ tối ưu hóa) vào hướng dẫn di chuyển có điều kiện ở x86, là các nhà điều hành ternary ... ? ... : .... Vì vậy, chúng tôi viết lại câu lệnh trên thành 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 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 thử nghiệm. Chúng tôi nhận được một sự tăng tốc tuyệt vời khi kết quả nhánh không thể đoán trước, nhưng chúng tôi bị thiệt hại một chút khi nó có thể dự đoán được. Trên 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ờ chúng ta hãy xem xét kỹ hơn bằng cách điều tra x86assembly mà chúng tạo ra. Để đơn giản, chúng tôi sử dụng hai hàm max1max2.

max1sử 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;
}

max2sử 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 -Stạo lắp ráp 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

max2sử dụng mã ít hơn nhiều do việc sử dụng hướng dẫn cmovge. Nhưng lợi ích thực sự là max2không liên quan đến các bước nhảy nhánh jmp, điều này sẽ có một hình phạt hiệu suất đáng kể nếu kết quả dự đoán 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 x86bộ xử lý điển hình , việc thực hiện một lệnh được chia thành nhiều giai đoạn. Đại khái, chúng tôi có các phần cứng khác nhau để xử lý các giai đoạn khác nhau. Vì vậy, chúng ta không cần phải đợi một lệnh kết thúc để bắt đầu một lệnh mới. Điều này được gọi là pipelining .

Trong trường hợp rẽ 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 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 được thực hiện được chia thành nhiều giai đoạn, nhưng các giai đoạn trước đó giống như FetchDecodekhô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 tôi đợi một phần nhỏ thời gian thực thi 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.

Cuốn sách Hệ thống máy tính: Quan điểm của một 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 Phần 3.6.6 để biết Hướng dẫn di chuyển có điều kiện , toàn bộ Chương 4 về Kiến trúc bộ xử lý và Phần 5.11.2 để biết cách xử lý đặc biệt đối với các Hình phạt Dự đoán Nhánh và Dự đoán 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 đang sử dụng trình biên dịch gốc của Visual Studio). Biết sự khác biệt về hiệu suất giữa một nhánh và một động thái 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 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.

2350
vulcan raven 2012-07-03 16:25.

Nếu bạn tò mò về nhiều tối ưu hóa 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 hoán đổ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điều kiện là không đổi trong suốt quá trình thực hiện ivòng lặp, vì vậy bạn có thể ifđưa 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 chấm động cho phép nó ( /fp:faství dụ: được ném)

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

Đó là nhanh hơn 100.000 lần so với trước đây.

1942
caf 2012-10-12 19:53.

Không nghi ngờ gì nữa, 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 cachegrindcó trình mô phỏng dự đoán nhánh, được kích hoạt bằng cách sử dụng --branch-sim=yescờ. Chạy nó trên các ví dụ trong câu hỏi này, với số lượng vòng lặp bên ngoài giảm xuống còn 10000 và được biên dịch với g++, sẽ 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%   )

Không đượ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 do cg_annotatechúng tôi tạo ra 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];
           .      .  .   .          }
           .      .  .   .      }

Không đượ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, if (data[c] >= 128)dòng đang gây ra 164.050.007 nhánh có điều kiện bị phân tích sai ( Bcm) trong 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 đã 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 bằng cách 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

Không đượ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 tính năng tháo rời.

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.

1392
atlaste 2013-04-24 20:26.

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

Một cách phổ biến để loại bỏ dự đoán rẽ 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 nhánh (mặc dù tôi chưa thử nghiệm nó trong trường hợp này).

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

  1. đó là một bảng nhỏ và có khả năng được lưu vào bộ nhớ đệm 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à lý do

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

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

Điều đầu tiên chúng ta cần biết nhỏ là gì? Mặc dù nhỏ hơn thường tốt hơn, nhưng một nguyên tắc chung là tuân theo các 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 thì có lẽ bạn nên 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 một bảng nhỏ. Điều tiếp theo cần làm là 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 phép toán số nguyên cơ bản (và, hoặc, xor, shift, thêm, bớt và có lẽ là nhân). Bạn muốn chức năng tra cứu dịch đầu vào của mình thành một loại 'khóa duy nhất' nào đó 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ó làm.

Trong trường hợp này:> = 128 có nghĩa là chúng ta có thể giữ nguyên 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 'VÀ': 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. 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 nó bằng một số 0 và rất nhiều 7FFFFFFFF của.

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

Bạn có thể thắc mắc 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 bằng một nhánh để đảm bảo bạn không làm lộn xộn ...

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

Đã có khá nhiều công việc về 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 đối với trình biên dịch rằng điều kiện biên sẽ không bao giờ được thực hiện. Ít nhất trình biên dịch JIT của Microsoft (nhưng tôi mong đợi Java làm những điều tương tự) sẽ nhận thấy điều này và loại bỏ hoàn toàn kiểm tra. WOW, có nghĩa là không có chi nhánh. Tương tự, nó sẽ giải quyết các trường hợp hiển nhiên 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 một & 0x[something]FFFvào chức năng tra cứu của bạn để làm cho việc kiểm tra ranh giới có thể dự đoán được - và xem nó diễn ra 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();
1245
Saqlain 2013-02-15 21:24.

Vì dữ liệu được phân phối từ 0 đến 255 khi mảng đượ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 iflệnh-( ifcâu lệnh được chia sẻ bên dưới).

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

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

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

Hiệu suất của một câu lệnh ifphụ thuộc vào việc điều kiện của nó có dạng có thể dự đoán được hay không. 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ẽ chọn mẫu. Mặt khác, nếu mô hình là không thể đoán trước, câu lệnh ifsẽ đắt hơn nhiều.

Hãy đo 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ẫu true-false " xấu " có thể tạo ra một câu lệnh ifchậm hơn tới sáu lần so với mẫu " tốt "! Tất nhiên, mẫu nào tốt và mẫu nào xấu phụ thuộc vào các lệnh chính xác được tạo bởi trình biên dịch và bộ xử lý cụ thể.

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

1171
steveha 2013-07-22 22:29.

Một cách để tránh lỗi dự đoán nhánh là xây dựng một bảng tra cứu và lập chỉ mục nó bằng cách sử dụng dữ liệu. Stefan de Bruijn đã thảo luận về điều đó 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 duy nhất sẽ cho chúng tôi biết liệu chúng tôi có muốn một giá trị hay không: bằng cách dịch chuyển dữ liệu ở bên phải 7 bit, chúng tôi còn lại với một bit 0 hoặc một bit 1, 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 vào một mảng, chúng ta có thể tạo mã 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 là 0, chúng tôi sẽ thêm giá trị vào một nơi nào đó 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ố lần bổ sung 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 có 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, có thể là do việc lập chỉ mục vào một 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 không tưởng tượng là lut"Bảng tìm kiếm" 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ó vừa vặn trong bộ nhớ cache và tất cả đều nhanh chóng. 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ố đó ... 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 trình bày ở trên: đầu tiên dịch chuyển các bit, 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, chúng tôi có thể dịch dữ liệu sang phải 12 bit và để lại giá trị 12 bit cho một chỉ mục bảng. Chỉ mục bảng 12 bit ngụ ý một bảng gồm 4096 giá trị, có thể thực tế.

Kỹ thuật lập chỉ mục vào một mảng, thay vì sử dụng một ifcâu lệnh, có thể được sử dụng để quyết định con trỏ nào sẽ 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 ( pLeftpRightbất cứ thứ gì) có một mảng con trỏ dài 2 và sử dụng kỹ thuật "bit quyết định" để quyết định cái nào sẽ tuân 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à một liên kết đến mã này: Red Black Trees , Eternally Confuzzled

1063
Yves Daoust 2013-07-24 21:57.

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 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 < 128và một vùng khác với data >= 128. Vì vậy, bạn nên tìm điểm phân vùng bằng tìm kiếm lưỡng phân (sử dụng phép Lg(arraySize) = 15so sánh), sau đó thực hiện tích lũy thẳng từ đ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 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];

Một cách tiếp cận nhanh hơn, đưa ra giải pháp gần đúng cho cả được sắp xếp hoặc chưa được sắp xếp là: sum= 3137536;(giả sử phân phối thực sự đồng đều, 16384 mẫu với giá trị mong đợi 191,5) :-)

869
Harsh Sharma 2015-07-04 05:35.

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

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

Bất kỳ lệnh nào cũng đượ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 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ộ xử lý hiện đại. Để hiểu rõ hơn, vui lòng xem ví dụ này trên Wikipedia .

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

  1. IF - Tìm nạp lệnh từ bộ nhớ
  2. ID - Giải mã hướng dẫn
  3. EX - Thực hiện lệnh
  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.

Quay lại câu hỏi trên, chúng ta 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 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 đợi cho đến khi lệnh A không đạt đến 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ì vậy, đường dẫn sẽ trông như thế này.

khi nếu điều kiện trả về true:

Khi if điều kiện trả về false:

Kết quả của việc chờ đợi 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 rẽ nhánh; cho cả đúng và sai) là 7.

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

Trình dự đoán rẽ nhánh sẽ cố gắng đoán xem một nhánh (cấu trúc if-then-else) sẽ đi theo hướng nào trước khi điều này được biết chắc chắn. Nó sẽ không đợi lệnh A đến 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 của ví dụ của chúng ta).

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

Nếu sau đó người ta phát hiện ra rằng đoán sai thì các lệnh được thực thi 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, 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 với 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 dẫn khá dài nên độ trễ của việc báo cáo sai là từ 10 đến 20 chu kỳ đồng hồ. Đườ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ã lệnh của OP, lần đầu tiên khi điều kiện, người dự đoán nhánh không có bất kỳ thông tin nào để làm cơ sở dự đoán, vì vậy lần đầu tiên nó sẽ chọn ngẫu nhiên lệnh tiếp theo. Sau đó trong vòng lặp for, nó có thể đưa ra dự đoán dựa trên 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

Chúng ta hãy giả định rằng bộ dự đoán sẽ luôn giả định nhánh đúng 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ật vì trong lịch sử tất cả các dự đoán của nó đều đúng. Trong trường hợp thứ 2, ban đầu sẽ dự đoán sai, nhưng sau vài lần lặp lại, nó sẽ dự đoán đúng. 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ó sẽ chính xác khi nó thấy dự đoán nhánh thất bại trong lịch sử.

Trong tất cả những trường hợp này, lỗi sẽ ít hơn về số lượng và kết quả là chỉ một vài lần nó sẽ phải hủy 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 sắp xếp ngẫu nhiên, dự đoán sẽ cần phải 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 hầu hết thời gian và dẫn đến nhiều chu kỳ CPU hơn so với mảng đã sắp xếp.

764
Surt 2015-10-12 11:05.

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

  1. Intel - Tránh chi phí do sai lệch chi nhánh
  2. Intel - Tổ chức lại nhánh và vòng lặp để ngăn chặn các hành vi sai trái
  3. Bài báo khoa học - kiến ​​trúc máy tính dự đoán nhánh
  4. Sách: JL Hennessy, DA Patterson: Kiến trúc máy tính: cách tiếp cận định lượng
  5. Các bài báo trên các ấn phẩm khoa học: TY Yeh, YN Patt đưa ra rất nhiều điều này về các dự đoán nhánh.

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

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

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

vì vậy người dự đoán sẽ đổi bên như một std::rand()cú đánh.

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


734
rkachach 2015-09-24 04:57.

Trong cùng một dòng (tôi nghĩ rằng điều này không được đánh dấu 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 trong phần mềm có hiệu suất quan trọng - như trong hạt nhân Linux), bạn có thể tìm thấy một số câu lệnh if như sau:

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

hoặc tương tự:

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

Cả hai likely()unlikely()trên thực tế đều là các macro được xác định bằng cách sử dụng một cái gì đó giống như GCC __builtin_expectđể giúp trình biên dịch chèn mã dự đoán để có lợi cho điều kiện có tính đến thông tin do người dùng cung cấp. GCC hỗ trợ các trình xây dựng 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ộ nhớ cache, v.v. Xem tài liệu hướng dẫn này về các nội trang 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 cứng hoặc các hệ thống nhúng, nơi mà thời gian thực thi rất quan trọng và nó rất 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? Bằng cách này, theo mặc định, dự đoán nhánh sẽ giả định rằng điều kiện là sai.

718
Maciej 2015-10-10 14:30.

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

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àm đầu vào sẽ kiểm tra xem đầu vào có bất kỳ giá trị nào khác hơn 0hoặc không 1, nhưng các toán tử có Boolean làm đầu ra không thể tạo ra giá trị nào khác hơn 0hoặc 1. Điều này làm cho các hoạt động với các biến Boolean làm đầu vào kém hiệu quả hơn mức cần thiết. Hãy 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 thực hiện 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 sai sót. Các phép toán 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. Đoạn 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để làm cho nó có thể sử dụng các toán tử bitwise ( &|) thay vì 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ỳ đồng hồ. Toán tử OR ( |) hoạt động ngay cả khi abcó các giá trị khác 0hoặ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 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à có 0hoặc 1bằng cách XỬ LÝ 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 && bkhông thể được thay thế bằng a & bif blà một biểu thức không nên được đánh giá if ais false( &&sẽ không đánh giá b, &sẽ). Tương tự, a || bkhông thể được thay thế bằng a | bif blà một biểu thức không nên được đánh giá if ais true.

Sử dụng toán tử bitwise sẽ có lợi hơn nếu toán hạng là biến hơn là nếu toán hạng là phép 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 đợi &&biểu thức tạo ra nhiều sai lệch nhánh).

377
Alireza 2017-06-19 01:40.

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

Dự đoán rẽ nhánh làm cho logic chạy chậm hơn, do quá trình chuyển đổi xảy ra trong mã của bạn! Giống như bạn đang đi một con đường thẳng hoặc một con đường có nhiều chỗ rẽ, chắc chắn rằng 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ị đúng cho toàn bộ con đường đến cuối phố. Đó là cách bạn đi đến phần cuối của logic nhanh hơn. Mặt khác, sử dụng một mảng chưa được sắp xếp, bạn cần phải chuyển và xử lý nhiều lần, điều này khiến mã của bạn chắc chắn chạy chậm hơn ...

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

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

Cuối cùng, thật tốt khi biết rằng 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 một cách khác nhau:

1. Tĩnh

2. Động

Dự đoán nhánh tĩnh được bộ vi xử lý sử dụng 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 thi 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 các câu lệnh if-else hoặc switch , trước tiên hãy kiểm tra các trường hợp phổ biến nhất và giảm dần các trường hợp ít phổ biến nhất. 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 lặp vòng lặp thường được sử dụng.

334
ForeverLearning 2017-01-12 15:50.

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

Gần đây, ví dụ này (được sửa đổi rất ít) cũng được sử dụng như một cách để chứng minh cách một đoạn mã có thể được cấu 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ã đang sử dụng phần lớn thời gian của nó trong cả trường hợp được sắp xếp & không được sắp xếp. Cuối cùng, phần này cũng chỉ ra 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ệch nhánh đang xảy ra trong trường hợp không được phân loại.

Liên kết ở đây: Một minh chứng về việc tự lập hồ sơ

306
Eugene 2017-11-07 06:15.

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

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

Trong kiến ​​trúc máy tính, bộ dự đoán nhánh là một mạch kỹ thuật số cố gắng đoán một nhánh (ví dụ: cấu trúc if-then-else) sẽ đi theo cách nào 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 lệnh. Các bộ dự đoán nhánh đóng một vai trò quan trọng trong việc đạt được hiệu suất hiệu quả cao trong nhiều kiến ​​trúc bộ vi xử lý hình ống hiện đại như x86.

Phân nhánh hai chiều thường được thực hiện với lệnh nhảy có điều kiện. Một bước nhảy có điều kiện có thể là "không được thực hiện" và tiếp tục thực hiện với nhánh mã đầu tiên tiếp theo ngay sau bước nhảy có điều kiện hoặc nó có thể được "thực hiện" và nhảy đến một vị trí khác trong bộ nhớ chương trình nơi nhánh mã thứ hai. được 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 cho đến khi điều kiện đã được tính toán và bước nhảy có điều kiện đã vượt qua giai đoạn thực thi trong đường dẫn lệnh (xem hình 1).

Based on the described scenario, I have written an animation demo to show how instructions are executed in a pipeline in different situations.

  1. Without the Branch Predictor.

Without branch prediction, the processor would have to wait until the conditional jump instruction has passed the execute stage before the next instruction can enter the fetch stage in the pipeline.

The example contains three instructions and the first one is a conditional jump instruction. The latter two instructions can go into the pipeline until the conditional jump instruction is executed.

It will take 9 clock cycles for 3 instructions to be completed.

  1. Use Branch Predictor and don't take a conditional jump. Let's assume that the predict is not taking the conditional jump.

It will take 7 clock cycles for 3 instructions to be completed.

  1. Use Branch Predictor and take a conditional jump. Let's assume that the predict is not taking the conditional jump.

It will take 9 clock cycles for 3 instructions to be completed.

The time that is wasted in case of a branch misprediction is equal to the number of stages in the pipeline from the fetch stage to the execute stage. Modern microprocessors tend to have quite long pipelines so that the misprediction delay is between 10 and 20 clock cycles. As a result, making a pipeline longer increases the need for a more advanced branch predictor.

As you can see, it seems we don't have a reason not to use Branch Predictor.

It's quite a simple demo that clarifies the very basic part of Branch Predictor. If those gifs are annoying, please feel free to remove them from the answer and visitors can also get the live demo source code from BranchPredictorDemo

238
Tony Tannous 2017-08-05 00:07.

Branch-prediction gain!

It is important to understand that branch misprediction doesn't slow down programs. The cost of a missed prediction is just as if branch prediction didn't exist and you waited for the evaluation of the expression to decide what code to run (further explanation in the next paragraph).

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

Whenever there's an if-else \ switch statement, the expression has to be evaluated to determine which block should be executed. In the assembly code generated by the compiler, conditional branch instructions are inserted.

A branch instruction can cause a computer to begin executing a different instruction sequence and thus deviate from its default behavior of executing instructions in order (i.e. if the expression is false, the program skips the code of the if block) depending on some condition, which is the expression evaluation in our case.

That being said, the compiler tries to predict the outcome prior to it being actually evaluated. It will fetch instructions from the if block, and if the expression turns out to be true, then wonderful! We gained the time it took to evaluate it and made progress in the code; if not then we are running the wrong code, the pipeline is flushed, and the correct block is run.

Visualization:

Let's say you need to pick route 1 or route 2. Waiting for your partner to check the map, you have stopped at ## and waited, or you could just pick route1 and if you were lucky (route 1 is the correct route), then great you didn't have to wait for your partner to check the map (you saved the time it would have taken him to check the map), otherwise you will just turn back.

While flushing pipelines is super fast, nowadays taking this gamble is worth it. Predicting sorted data or a data that changes slowly is always easier and better than predicting fast changes.

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------
194
Luke Hutchison 2017-12-23 03:13.

On ARM, there is no branch needed, because every instruction has a 4-bit condition field, which tests (at zero cost) any of 16 different different conditions that may arise in the Processor Status Register, and if the condition on an instruction is false, the instruction is skipped. This eliminates the need for short branches, and there would be no branch prediction hit for this algorithm. Therefore, the sorted version of this algorithm would run slower than the unsorted version on ARM, because of the extra overhead of sorting.

The inner loop for this algorithm would look something like the following in ARM assembly language:

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

But this is actually part of a bigger picture:

CMP opcodes always update the status bits in the Processor Status Register (PSR), because that is their purpose, but most other instructions do not touch the PSR unless you add an optional S suffix to the instruction, specifying that the PSR should be updated based on the result of the instruction. Just like the 4-bit condition suffix, being able to execute instructions without affecting the PSR is a mechanism that reduces the need for branches on ARM, and also facilitates out of order dispatch at the hardware level, because after performing some operation X that updates the status bits, subsequently (or in parallel) you can do a bunch of other work that explicitly should not affect (or be affected by) the status bits, then you can test the state of the status bits set earlier by X.

The condition testing field and the optional "set status bit" field can be combined, for example:

  • ADD R1, R2, R3 performs R1 = R2 + R3 without updating any status bits.
  • ADDGE R1, R2, R3 performs the same operation only if a previous instruction that affected the status bits resulted in a Greater than or Equal condition.
  • ADDS R1, R2, R3 performs the addition and then updates the N, Z, C and V flags in the Processor Status Register based on whether the result was Negative, Zero, Carried (for unsigned addition), or oVerflowed (for signed addition).
  • ADDSGE R1, R2, R3 performs the addition only if the GE test is true, and then subsequently updates the status bits based on the result of the addition.

Most processor architectures do not have this ability to specify whether or not the status bits should be updated for a given operation, which can necessitate writing additional code to save and later restore status bits, or may require additional branches, or may limit the processor's out of order execution efficiency: one of the side effects of most CPU instruction set architectures forcibly updating status bits after most instructions is that it is much harder to tease apart which instructions can be run in parallel without interfering with each other. Updating status bits has side effects, therefore has a linearizing effect on code. ARM's ability to mix and match branch-free condition testing on any instruction with the option to either update or not update the status bits after any instruction is extremely powerful, for both assembly language programmers and compilers, and produces very efficient code.

When you don't have to branch, you can avoid the time cost of flushing the pipeline for what would otherwise be short branches, and you can avoid the design complexity of many forms of speculative evalution. The performance impact of the initial naive imlementations of the mitigations for many recently discovered processor vulnerabilities (Spectre etc.) shows you just how much the performance of modern processors depends upon complex speculative evaluation logic. With a short pipeline and the dramatically reduced need for branching, ARM just doesn't need to rely on speculative evaluation as much as CISC processors. (Of course high-end ARM implementations do include speculative evaluation, but it's a smaller part of the performance story.)

If you have ever wondered why ARM has been so phenomenally successful, the brilliant effectiveness and interplay of these two mechanisms (combined with another mechanism that lets you "barrel shift" left or right one of the two arguments of any arithmetic operator or offset memory access operator at zero additional cost) are a big part of the story, because they are some of the greatest sources of the ARM architecture's efficiency. The brilliance of the original designers of the ARM ISA back in 1983, Steve Furber and Roger (now Sophie) Wilson, cannot be overstated.

167
Yochai Timmer 2017-11-24 04:28.

Besides the fact that the branch prediction may slow you down, a sorted array has another advantage:

You can have a stop condition instead of just checking the value, this way you only loop over the relevant data, and ignore the rest.
The branch prediction will miss only once.

 // 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];               
 }
163
Farhad 2017-10-03 23:47.

It's about branch prediction. What is it?

  • A branch predictor is one of the ancient performance improving techniques which still finds relevance into modern architectures. While the simple prediction techniques provide fast lookup and power efficiency they suffer from a high misprediction rate.

  • On the other hand, complex branch predictions –either neural based or variants of two-level branch prediction –provide better prediction accuracy, but they consume more power and complexity increases exponentially.

  • In addition to this, in complex prediction techniques the time taken to predict the branches is itself very high –ranging from 2 to 5 cycles –which is comparable to the execution time of actual branches.

  • Branch prediction is essentially an optimization (minimization) problem where the emphasis is on to achieve lowest possible miss rate, low power consumption, and low complexity with minimum resources.

There really are three different kinds of branches:

Forward conditional branches - based on a run-time condition, the PC (program counter) is changed to point to an address forward in the instruction stream.

Backward conditional branches - the PC is changed to point backward in the instruction stream. The branch is based on some condition, such as branching backwards to the beginning of a program loop when a test at the end of the loop states the loop should be executed again.

Unconditional branches - this includes jumps, procedure calls and returns that have no specific condition. For example, an unconditional jump instruction might be coded in assembly language as simply "jmp", and the instruction stream must immediately be directed to the target location pointed to by the jump instruction, whereas a conditional jump that might be coded as "jmpne" would redirect the instruction stream only if the result of a comparison of two values in a previous "compare" instructions shows the values to not be equal. (The segmented addressing scheme used by the x86 architecture adds extra complexity, since jumps can be either "near" (within a segment) or "far" (outside the segment). Each type has different effects on branch prediction algorithms.)

Static/dynamic Branch Prediction: Static branch prediction is used by the microprocessor the first time a conditional branch is encountered, and dynamic branch prediction is used for succeeding executions of the conditional branch code.

References:

  • Branch predictor

  • A Demonstration of Self-Profiling

  • Branch Prediction Review

  • Branch Prediction

147
omkaartg 2017-12-08 07:28.

Sorted arrays are processed faster than an unsorted array, due to a phenomena called branch prediction.

The branch predictor is a digital circuit (in computer architecture) trying to predict which way a branch will go, improving the flow in the instruction pipeline. The circuit/computer predicts the next step and executes it.

Making a wrong prediction leads to going back to the previous step, and executing with another prediction. Assuming the prediction is correct, the code will continue to the next step. A wrong prediction results in repeating the same step, until a correct prediction occurs.

The answer to your question is very simple.

In an unsorted array, the computer makes multiple predictions, leading to an increased chance of errors. Whereas, in a sorted array, the computer makes fewer predictions, reducing the chance of errors. Making more predictions requires more time.

Sorted Array: Straight Road ____________________________________________________________________________________ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

Unsorted Array: Curved Road

______   ________
|     |__|

Branch prediction: Guessing/predicting which road is straight and following it without checking

___________________________________________ Straight road
 |_________________________________________|Longer road

Although both the roads reach the same destination, the straight road is shorter, and the other is longer. If then you choose the other by mistake, there is no turning back, and so you will waste some extra time if you choose the longer road. This is similar to what happens in the computer, and I hope this helped you understand better.


Also I want to cite @Simon_Weaver from the comments:

It doesn’t make fewer predictions - it makes fewer incorrect predictions. It still has to predict for each time through the loop...

139
Shan 2012-12-31 06:16.

I tried the same code with MATLAB 2011b with my MacBook Pro (Intel i7, 64 bit, 2.4 GHz) for the following MATLAB code:

% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);


%Sort the data
data1= sort(data); % data1= data  when no sorting done


%Start a stopwatch timer to measure the execution time
tic;

for i=1:100000

    for j=1:arraySize

        if data1(j)>=128
            sum=sum + data1(j);
        end
    end
end

toc;

ExeTimeWithSorting = toc - tic;

The results for the above MATLAB code are as follows:

  a: Elapsed time (without sorting) = 3479.880861 seconds.
  b: Elapsed time (with sorting ) = 2377.873098 seconds.

The results of the C code as in @GManNickG I get:

  a: Elapsed time (without sorting) = 19.8761 sec.
  b: Elapsed time (with sorting ) = 7.37778 sec.

Based on this, it looks MATLAB is almost 175 times slower than the C implementation without sorting and 350 times slower with sorting. In other words, the effect (of branch prediction) is 1.46x for MATLAB implementation and 2.7x for the C implementation.

72
user2297550 2018-12-09 20:18.

The assumption by other answers that one needs to sort the data is not correct.

The following code does not sort the entire array, but only 200-element segments of it, and thereby runs the fastest.

Sorting only k-element sections completes the pre-processing in linear time, O(n), rather than the O(n.log(n)) time needed to sort the entire array.

#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;
}

This also "proves" that it has nothing to do with any algorithmic issue such as sort order, and it is indeed branch prediction.

54
Selcuk 2019-10-15 13:34.

Bjarne Stroustrup's Answer to this question:

That sounds like an interview question. Is it true? How would you know? It is a bad idea to answer questions about efficiency without first doing some measurements, so it is important to know how to measure.

So, I tried with a vector of a million integers and got:

Already sorted    32995 milliseconds
Shuffled          125944 milliseconds

Already sorted    18610 milliseconds
Shuffled          133304 milliseconds

Already sorted    17942 milliseconds
Shuffled          107858 milliseconds

I ran that a few times to be sure. Yes, the phenomenon is real. My key code was:

void run(vector<int>& v, const string& label)
{
    auto t0 = system_clock::now();
    sort(v.begin(), v.end());
    auto t1 = system_clock::now();
    cout << label 
         << duration_cast<microseconds>(t1 — t0).count() 
         << " milliseconds\n";
}

void tst()
{
    vector<int> v(1'000'000);
    iota(v.begin(), v.end(), 0);
    run(v, "already sorted ");
    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
    run(v, "shuffled    ");
}

At least the phenomenon is real with this compiler, standard library, and optimizer settings. Different implementations can and do give different answers. In fact, someone did do a more systematic study (a quick web search will find it) and most implementations show that effect.

One reason is branch prediction: the key operation in the sort algorithm is “if(v[i] < pivot]) …” or equivalent. For a sorted sequence that test is always true whereas, for a random sequence, the branch chosen varies randomly.

Another reason is that when the vector is already sorted, we never need to move elements to their correct position. The effect of these little details is the factor of five or six that we saw.

Quicksort (and sorting in general) is a complex study that has attracted some of the greatest minds of computer science. A good sort function is a result of both choosing a good algorithm and paying attention to hardware performance in its implementation.

If you want to write efficient code, you need to know a bit about machine architecture.

47
hatirlatici 2019-10-24 11:35.

This question is rooted in Branch Prediction Models on CPUs. I'd recommend reading this paper:

Increasing the Instruction Fetch Rate via Multiple Branch Prediction and a Branch Address Cache

When you have sorted elements, IR could not be bothered to fetch all CPU instructions, again and again, It fetches them from cache.

40
Manoj Kashyam 2020-01-21 23:08.

One way to avoid branch prediction errors is to build a lookup table, and index it using the data. Stefan de Bruijn discussed that in his answer.

But in this case, we know values are in the range [0, 255] and we only care about values >= 128. That means we can easily extract a single bit that will tell us whether we want a value or not: by shifting the data to the right 7 bits, we are left with a 0 bit or a 1 bit, and we only want to add the value when we have a 1 bit. Let's call this bit the "decision bit".

By using the 0/1 value of the decision bit as an index into an array, we can make code that will be equally fast whether the data is sorted or not sorted. Our code will always add a value, but when the decision bit is 0, we will add the value somewhere we don't care about. Here's the code:

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

This code wastes half of the adds but never has a branch prediction failure. It's tremendously faster on random data than the version with an actual if statement.

But in my testing, an explicit lookup table was slightly faster than this, probably because indexing into a lookup table was slightly faster than bit shifting. This shows how my code sets up and uses the lookup table (unimaginatively called lut for "LookUp Table" in the code). Here's the C++ code:

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

In this case, the lookup table was only 256 bytes, so it fits nicely in a cache and all was fast. This technique wouldn't work well if the data was 24-bit values and we only wanted half of them... the lookup table would be far too big to be practical. On the other hand, we can combine the two techniques shown above: first shift the bits over, then index a lookup table. For a 24-bit value that we only want the top half value, we could potentially shift the data right by 12 bits, and be left with a 12-bit value for a table index. A 12-bit table index implies a table of 4096 values, which might be practical.

The technique of indexing into an array, instead of using an if statement, can be used for deciding which pointer to use. I saw a library that implemented binary trees, and instead of having two named pointers (pLeft and pRight or whatever) had a length-2 array of pointers and used the "decision bit" technique to decide which one to follow. For example, instead of:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;
this library would do something like:

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

It's a nice solution and maybe it will work.

Related questions

MORE COOL STUFF

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

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

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

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

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

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

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

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

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

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

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

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

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

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

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

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

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

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

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

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

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

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

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

Một thương hiệu kế thừa khác có được cuộc sống mới khi những người chủ mới của Black Opal có được Hội chợ thời trang

Một thương hiệu kế thừa khác có được cuộc sống mới khi những người chủ mới của Black Opal có được Hội chợ thời trang

Desiree Rogers, trái, và Cheryl Mayberry McKissack Chuyển sang, Fenty Beauty và Pat McGrath, có một đế chế làm đẹp mới do phụ nữ làm chủ đang trỗi dậy. Sau thương vụ mua lại mỹ phẩm Black Opal vào tháng 9, đội ngũ quyền lực của Giám đốc điều hành công ty Desiree Rogers và Chủ tịch Cheryl Mayberry McKissack đã thông báo mua lại thương hiệu làm đẹp tiên phong Fashion Fair từ người sáng lập Johnson Publishing Company (JPC).

Ngoài việc trở nên vô nghĩa, các bên bộc lộ giới tính giờ đây đã trở nên chết người

Ngoài việc trở nên vô nghĩa, các bên bộc lộ giới tính giờ đây đã trở nên chết người

Đối với những người có quá nhiều thời gian, tiệc tiết lộ giới tính là một cách thú vị để không cần áp đặt những định kiến ​​hạn chế lên thai nhi trước một đối tượng bạn bè giả vờ quan tâm một cách lịch sự. Tuy nhiên, việc chỉ dựa vào những chiếc bánh nướng có màu nhân tạo để biểu thị một tiếng hoo-ha hoặc một đứa trẻ đi tè đã trở nên xa xỉ trong các bậc cha mẹ trên Instagram.

Kirstjen Nielsen đang cố gắng đổi mới bản thân với tư cách là một người phụ nữ 'nói ra sự thật cho sức mạnh'

Kirstjen Nielsen đang cố gắng đổi mới bản thân với tư cách là một người phụ nữ 'nói ra sự thật cho sức mạnh'

Hôm thứ Tư, cựu Bộ trưởng An ninh Nội địa Kirstjen Nielsen vì một lý do nào đó đã được đưa ra một diễn đàn để phát biểu tại Hội nghị thượng đỉnh Những người phụ nữ quyền lực nhất của Fortune. Và có thể đoán trước được, người phụ nữ giám sát các nỗ lực (đang diễn ra) của chính quyền Trump nhằm chia cắt các gia đình ở biên giới đã sử dụng thời gian của mình như một cơ hội để tự bảo vệ mình và tự nhận mình là người — và hãy hít thở sâu ở đây — “đã nói sự thật với quyền lực.

Toyota Racing Development sẽ cho ra mắt Supra 3000GT Concept, Massive Wing vào tháng tới

Toyota Racing Development sẽ cho ra mắt Supra 3000GT Concept, Massive Wing vào tháng tới

Vì thế hệ mới nhất của chiếc xe điều chỉnh được yêu thích trên thế giới hiện đã có mặt tại đây, nên chỉ có điều kiện là Toyota Racing Development sẽ đưa phiên bản Supra thế hệ thứ năm sửa đổi của riêng mình đến SEMA vào tháng tới. Toyota đã cho chúng tôi một gợi ý về những gì sẽ xảy ra trong tuần này: một chiếc Concept GR Supra 3000GT hiện đại.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Language