int[] và int[,] trong C#: Ai nhanh hơn

Trong bài viết này, tôi sẽ so sánh các loại mảng khác nhau trong C#. Hiểu được sự khác biệt giữa các loại mảng này sẽ giúp bạn chọn cấu trúc dữ liệu chính xác cho mọi trường hợp.

Ví dụ

Hãy xem đoạn code sau:

public class ArraysTest : PerformanceTest
{
    protected override bool MeasureTestA()
    {
        // fill a 3-dimensional array
        var size = Iterations;
        var array = new int[size, size, size];
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                for (int k = 0; k < size; k++)
                {
                    array[i, j, k] = 3;
                }
            }
        }
        return true;
    }

    protected override bool MeasureTestB()
    {
        // do the same with a flattened 1-dimensional array
        var size = Iterations;
        var array = new int[size * size * size];
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                for (int k = 0; k < size; k++)
                {
                    var index = k + size * (j + size * i);
                    array[index] = 3;
                }
            }
        }
        return true;
    }

    protected override bool MeasureTestC()
    {
        // do the same with a flattened array and incremental access
        var size = Iterations;
        var array = new int[size * size * size];
        var index = 0;
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                for (int k = 0; k < size; k++)
                {
                    array[index] = 3;
                    index++;
                }
            }
        }
        return true;
    }
}

Phương thức MeasureTestA tạo một mảng 3 chiều, duyệt qua từng phần tử mảng và gán giá trị 3 cho nó.

Phương thức MeasureTestB cũng tương tự, nhưng nó sử dụng một mảng 1 chiều để thay thế và tính toán index bằng cách sử dụng các biến i, j, k và vòng lặp.

Điều đó không tạo ra sự khác biệt nào, phải không? Bạn sẽ mong đợi rằng các mảng 3 chiều trong .NET sử dụng logic tương tự như những gì tôi đã viết trong MeasureTestB.

Kết quả benchmark

Vâng, chúng ta hãy xem kết quả benchmark:

int[] và int[,] trong C#: Ai nhanh hơn

Bạn có thấy sự khác biệt không?

Code sử dụng mảng 3 chiều trong phương thức MeasureTestA chậm hơn 31% so với code sử dụng mảng 1 chiều trong phương thức MeasureTestB.

Chuyện gì đang xảy ra ở đây?

Giải thích kết quả benchmark

Hãy cùng tìm hiểu. Chúng ta sẽ bắt đầu bằng cách xem code sử dụng mảng 3 chiều trong phương thức MeasureTestA. Vòng lặp bên trong được biên dịch sang ngôn ngữ trung gian (IL) như sau:

int[] và int[,] trong C#: Ai nhanh hơn

Phần được đánh dấu là nơi điều kỳ diệu xảy ra. Phương thức Array.Set sử dụng các chỉ số i, j và k để ghi giá trị 3 trực tiếp vào bộ nhớ.

Đó chỉ là 6 câu lệnh với một lần gọi phương thức. Không có gì xấu cả!

Bây giờ chúng ta hãy xem xét vòng lặp bên trong phương thức MeasureTestB:

int[] và int[,] trong C#: Ai nhanh hơn

Bây giờ chúng ta có nhiều câu lệnh ngôn ngữ trung gian (IL) hơn trong vòng lặp bên trong. Và bạn có thể thấy rõ các lệnh muladd tính toán độ lệch mảng theo cách thủ công từ các chỉ số i, j và k.

Nhưng bạn có nhận thấy rằng không có một lệnh gọi phương thức nào trong vòng lặp không?

Thay vào đó, có một lệnh stelem tại IL_0033 ghi giá trị 3 trực tiếp vào mảng 1 chiều.

Và đó là lý do cho sự khác biệt về hiệu suất: trình thực thi .NET có các chỉ dẫn ngôn ngữ trung gian (IL) chuyên biệt để làm việc với mảng 1 chiều!

Do đó, mã trong phương thức MeasureTestB hoàn toàn không cần thực hiện các lệnh gọi phương thức trong vòng lặp bên trong và điều đó giúp tiết kiệm rất nhiều thời gian.

Vì vậy, nếu bạn đang làm việc với các mảng nhiều chiều trong một vòng lặp nóng trong code của mình, hãy cân nhắc làm phẳng mảng xuống 1 chiều. Điều đó sẽ loại bỏ một cuộc gọi phương thức khỏi nội dung vòng lặp bên trong của bạn và tăng tốc mã đáng kể.

Cuối cùng, chúng ta hãy xem xét phương thức MeasureTestC.

Phương thức này cũng sử dụng mảng 1 chiều nhưng bỏ qua các chỉ số i, j, k và tránh tính toán độ lệch mảng. Vì chúng tôi đang cập nhật mảng một cách tuần tự, nên mã này chỉ bắt đầu ở chỉ số 0 và tăng chỉ mục index lên mỗi lần.

Code đã biên dịch trông như thế này:

int[] và int[,] trong C#: Ai nhanh hơn

Điều này hiệu quả như chúng ta sẽ nhận được.

Đoạn mã sử dụng lệnh stelem để ghi giá trị 3 trực tiếp vào mảng 1 chiều, sau đó tăng chỉ số index lên một.

Lưu ý rằng không có các lệnh mul ở bất kỳ đâu vì chúng ta không tính chỉ số index từ i, j và k nữa.

Điều này mang lại cho chúng ta một mức tăng hiệu suất nhỏ. Mã trong phương thức MeasureTestC nhanh hơn 2% so với phương thức MeasureTestB.

Điều đó chỉ cho thấy các phép nhân số nguyên nhanh như thế nào trên các CPU hiện đại. Việc loại bỏ 2 lệnh mul trong một vòng lặp hầu như không tạo ra sự khác biệt.

Trong thực tế, tối ưu hóa cuối cùng này có lẽ không đáng giá.

Vậy bạn nghĩ như thế nào? Bạn có định cấu trúc lại code cho mảng của mình không?

Lập Trình C#Lập Trình C# Cơ Bản
Bài Viết Liên Quan:
Làm việc với PriorityQueue của .NET 6
Trung Nguyen 25/10/2021
Làm việc với PriorityQueue của .NET 6

Bài viết này sẽ giúp bạn tìm hiểu PriorityQueue của .NET 6 là gì, cách chúng ta thêm các phần tử và cách chúng ta có thể xếp hàng lại cho các phần tử.

Hướng dẫn nhanh và ví dụ về pattern matching trong C#
Trung Nguyen 23/10/2021
Hướng dẫn nhanh và ví dụ về pattern matching trong C#

Bài viết này sẽ trình bày một số ví dụ về pattern matching hữu ích và bạn có thể xem xét sử dụng trong các dự án hiện tại hoặc tương lai của bạn.

Sử dụng chuỗi kết nối Redis-CLI trong StackExchange.Redis
Trung Nguyen 18/10/2021
Sử dụng chuỗi kết nối Redis-CLI trong StackExchange.Redis

Bài viết này sẽ hướng dẫn chúng ta cách viết một phương thức mở rộng để phân tích chuỗi kết nối redis-cli có thể sử dụng với thư viện StackExchange.Redis.

Sử dụng .NET để xác thực JSON bằng lược đồ JSON
Trung Nguyen 17/10/2021
Sử dụng .NET để xác thực JSON bằng lược đồ JSON

JSON được cho là một trong những định dạng dữ liệu phổ biến nhất hiện nay. Chúng ta sẽ tìm hiểu cách đọc và xác thực JSON bằng lược đồ JSON.