Tôi vừa đọc một số article bởi Rico Mariani rằng các mối quan ngại về hiệu suất truy cập bộ nhớ được cung cấp cho các địa phương, kiến trúc, căn chỉnh và mật độ khác nhau.Điều gì gây ra sự sụt giảm đáng kinh ngạc về hiệu năng này với số lượng mục * trung bình *?
Tác giả đã tạo một mảng có kích thước khác nhau chứa danh sách được liên kết gấp đôi với trọng tải là int, được chuyển thành một tỷ lệ nhất định. Ông đã thử nghiệm với danh sách này và tìm thấy một số kết quả phù hợp trên máy tính của mình.
Trích dẫn một trong những bảng kết quả:
Pointer implementation with no changes
sizeof(int*)=4 sizeof(T)=12
shuffle 0% 1% 10% 25% 50% 100%
1000 1.99 1.99 1.99 1.99 1.99 1.99
2000 1.99 1.85 1.99 1.99 1.99 1.99
4000 1.99 2.28 2.77 2.92 3.06 3.34
8000 1.96 2.03 2.49 3.27 4.05 4.59
16000 1.97 2.04 2.67 3.57 4.57 5.16
32000 1.97 2.18 3.74 5.93 8.76 10.64
64000 1.99 2.24 3.99 5.99 6.78 7.35
128000 2.01 2.13 3.64 4.44 4.72 4.80
256000 1.98 2.27 3.14 3.35 3.30 3.31
512000 2.06 2.21 2.93 2.74 2.90 2.99
1024000 2.27 3.02 2.92 2.97 2.95 3.02
2048000 2.45 2.91 3.00 3.10 3.09 3.10
4096000 2.56 2.84 2.83 2.83 2.84 2.85
8192000 2.54 2.68 2.69 2.69 2.69 2.68
16384000 2.55 2.62 2.63 2.61 2.62 2.62
32768000 2.54 2.58 2.58 2.58 2.59 2.60
65536000 2.55 2.56 2.58 2.57 2.56 2.56
Tác giả giải thích:
Đây là phép đo cơ bản. Bạn có thể thấy cấu trúc là một vòng 12 byte đẹp và nó sẽ sắp xếp tốt trên x86. Nhìn vào cột đầu tiên, không có xáo trộn, như mong đợi mọi thứ trở nên tệ hơn và tồi tệ hơn khi mảng trở nên lớn hơn cho đến khi bộ nhớ cache không giúp được nhiều và bạn có điều tồi tệ nhất bạn sẽ nhận được, khoảng 2.55ns trung bình cho mỗi mục.
Nhưng một cái gì đó khá kỳ lạ có thể được nhìn thấy xung quanh 32k mục:
Kết quả cho xáo trộn không chính xác những gì tôi mong đợi. Ở kích thước nhỏ, nó không có sự khác biệt. Tôi mong đợi điều này bởi vì về cơ bản toàn bộ bảng đang nóng trong bộ nhớ cache và do đó địa phương không quan trọng. Sau đó, khi bảng phát triển bạn thấy rằng xáo trộn có tác động lớn ở khoảng 32.000 yếu tố. Đó là 384k dữ liệu. Có khả năng vì chúng tôi đã thổi qua giới hạn 256k.
Bây giờ điều kì lạ là: sau khi chi phí xáo trộn này thực sự giảm xuống, đến mức sau đó nó hầu như không có vấn đề gì cả. Bây giờ tôi có thể hiểu rằng tại một số điểm xáo trộn hoặc không xáo trộn thực sự nên làm cho không có sự khác biệt bởi vì mảng là rất lớn mà thời gian chạy phần lớn là gated bởi băng thông bộ nhớ bất kể thứ tự. Tuy nhiên ... có những điểm ở giữa, nơi mà chi phí của các địa phương không thực sự tồi tệ hơn nhiều so với kết quả cuối cùng.
Điều tôi mong đợi thấy là việc xáo trộn đã khiến chúng tôi đạt đến mức tối đa sớm hơn và ở lại đó. Điều gì thực sự xảy ra là tại miền Trung, kích thước không phải là địa phương dường như gây ra điều cần đi rất rất xấu ... Và tôi không biết tại sao :)
Vì vậy, câu hỏi là: Điều gì có thể đã gây ra hành vi bất ngờ này?
Tôi đã nghĩ về điều này một thời gian, nhưng không tìm thấy lời giải thích tốt. Mã thử nghiệm có vẻ ổn với tôi. Tôi không nghĩ rằng dự đoán nhánh CPU là thủ phạm trong trường hợp này, vì nó phải được quan sát sớm hơn so với 32k mục, và cho thấy một cành nhọn hơn rất nhiều.
Tôi đã xác nhận hành vi này trên hộp của tôi, có vẻ khá giống hệt nhau.
Tôi nhận thấy nó có thể do chuyển tiếp trạng thái CPU, vì vậy tôi đã thay đổi thứ tự hàng và/hoặc tạo cột - hầu như không có sự khác biệt về đầu ra. Để đảm bảo, tôi đã tạo dữ liệu cho mẫu liên tục lớn hơn.Để dễ dàng xem, tôi đặt nó vào excel:
And another independent run for good measure, negligible difference
