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

Đây là một đoạn code 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 trước khi xử lý đã làm cho chương trình chạy nhanh hơn gần gấp 6 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 như:

• Không có std::sort(data, data + arraySize); thì chương trình chạy xong mất 11.54 giây
• Với dữ liệu được sắp xếp, chương trình chỉ chạy trong 1,93 giây.

Bạn có thể nghĩ rằng vì C là ngôn ngữ biên dịch đặc biệt nên nó có thể xảy ra như thế. Tuy nhiên. Tôi đã thử với 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à kết quả nhận được tương tự như C nhưng ít cực đoan hơn.

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

Vậy điều gì đang xảy ra?

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

Để trả lời câu hỏi này, trước tiên chúng ta đi tìm hiểu về Branch Prediction

Branch Prediction là gì?

Để dễ hiểu, hãy lấy ví dụ về một ngã ba đường sắt.

Bây giờ, giả sử trên tàu không thể liên lạc vô tuyến hay điện thoại.

Bạn là người điều hành ở một ngã ba và bạn thấy một chuyến tàu đang đến. Bạn không biết nên mở đường cho tau đi theo hướng nào.

Bạn báo dừng tàu để hỏi lái tàu xem họ muốn hướng nào. Và sau đó bạn mới thiết lập để chuyển hướng cho tàu đi.

Xe lửa nặng và có nhiều quán tính. Vì vậy, quá trình dừng và tăng tốc làm chậm tiến trình đi rất nhiều.

Có cách nào tốt hơn không? => Bạn có thể dự đoán hướng tàu sẽ đi!

• Nếu bạn đoán đúng, nó sẽ tiếp tục
• Nếu bạn đoán sai, lái tàu sẽ dừng lại và chửi ầm lên để bạn điều chỉnh đúng. Sau đó, nó có thể tiếp tục chạy theo đường khác.

Có nghĩa là:

• Nếu bạn đoán đúng tất 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, tăng tốc từ đầu.

Hãy xem xét một câu lệnh if: Ở cấp độ bộ xử lý, đây 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 rẽ. Bạn không biết sẽ đi theo hướng nào. Bạn sẽ làm gì? Dừng thực thi và đợi cho các hướng dẫn trước hoàn thành. Sau đó, bạn tiếp tục xuống đi theo đường chính xác.

Bộ xử lý hiện đại rất phức tạp và có đường dẫn dài. Vì vậy, họ mất nhiều thời gian để ‘khởi động’ và ‘chậm lại’.

Có cách nào tốt hơn? => Dự đoán hướng rẽ nhánh.!

• Nếu đ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 dẫn và quay trở lại với các nhánh. Sau đó bạn có thể khởi động tiếp trên con đường khác.

Điều này cũng tương tự như đã nói ở trên:

• 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 thường xuyên, bạn dành rất nhiều thời gian để dừng lại kiểm tra, quay lại và lại khởi động chạy tiếp.

Đây là dự đoán nhánh (Branch Prediction). Mình thừa nhận đó không phải là so sánh tương tự tốt nhất vì tàu 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ẽ chạy theo hướng nào cho đến giây cuối cùng.

Vậy làm thế nào bạn có chiến lược dự đoán để giảm thiểu số lần tàu phải lùi và đi theo con đường khác?

Hãy thử nhìn vào lịch sử đã qua! Nếu 99% số lần tàu rẽ trái thì bạn đoán là trái. Và căn cứ vào kết quả lịch sự để bạn dự đoán hướng đi.

Nói cách khác, bạn cứ cố gắng xác định một mô hình và mong rằng tương lai mô hình cũng sẽ tương tự. Đây là việc tối thiểu bạn có thể làm.

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

>> Tìm hiểu thêm về Branch trên Wikipedia

Như đã phân tích ở trên, nguyên nhân 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 khá gần giống với dự đoán rẽ nhánh vì nó rẽ nhánh liên tiếp cùng một hướng nhiều lần. Ngay cả một khi cache bão hòa cũng có thể dự đoán gần đùng (trừ một vài trường hợp)

Bạn có thể hình dung như sau:

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, branch predictor 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% đoán sai (không tốt hơn so với dự đ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ì vậy,

Chúng ta làm gì với Branch Pretictor

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

Thay thế:

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

Bằng

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

Điều này giúp loại bỏ branch và thay thế nó bằng một số thao tác bitwise

Chúng ta có thể thử nghiệm tốc độ xử lý sau khi sắp xếp mảng.

Tốc độ xử lý được tính trên máy: Core i7 920 @ 3.5 GHz:

Tốc độ với ngôn ngữ C++ – Visual Studio 2010 – x64 Release

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Tốc độ xử lý với ngôn ngữ 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

Đối với Branch: 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

Đối với Hack: Không có sự khác biệt giữa dữ liệu được sắp xếp và chưa được sắp xếp.

Trong C++: Hack thực sự chậm hơn một chút so với Branch khi sử dụng 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 lặp quan trọng (chẳng hạn như trong ví dụ này)

Tổng kết

Như vậy bạn đã biết tại sao xử lý một mảng được sắp xếp nhanh hơn xử lý một mảng chưa sắp xếp. Và bạn cũng biết rằng ngay cả các trình biên dịch hiện đại lớn cũng có thể thay đổi mạnh mẽ về khả năng tối ưu hóa code ..

>. Tham khảo: Thuật toán Quicksort trong PHP tự viết nhanh hay chậm?