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

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?

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *