Một bộ xử lý hiện đại (như i7) có theo dõi con trỏ và tìm nạp trước dữ liệu của chúng trong khi lặp qua danh sách chúng không?

Question

Tôi muốn tìm hiểu cách viết mã tốt hơn để tận dụng bộ nhớ cache của CPU. Làm việc với bộ nhớ liền kề dường như là tình huống lý tưởng. Điều đó đang được nói, tôi tò mò nếu có những cải tiến tương tự mà có thể được thực hiện với bộ nhớ không tiếp giáp, nhưng với một mảng của con trỏ để làm theo, như:

struct Position { 
    int32_t x,y,z; 
} 
... 
std::vector<Position*> posPointers; 
... 
updatePosition() { 
    for (uint32_t i = 0; i < posPointers.size(); i++) { 
     Position& nextPos = *posPointers[i]; 
     nextPos.x++; 
     nextPos.y++; 
     nextPos.z++; 
    } 
} 

Đây chỉ là một số mã mock-up thô , và vì lợi ích của việc học này đúng cách chúng ta hãy chỉ nói rằng tất cả các cấu trúc vị trí được tạo ngẫu nhiên trên tất cả các đống.

Các bộ vi xử lý hiện đại, thông minh, chẳng hạn như i7 của Intel nhìn phía trước và thấy rằng nó sẽ cần dữ liệu của X_ptr rất ngắn? Dòng mã sau có hữu ích không?

... // for loop 
Position& nextPos1 = *posPointers[i]; 
Position& nextPos2 = *posPointers[i+1]; 
Position& nextPos3 = *posPointers[i+2]; 
Position& nextPos4 = *posPointers[i+3]; 
... // Work on data here 

Tôi đã đọc một số trang trình bày dường như chỉ ra mã như thế này sẽ khiến bộ xử lý tìm nạp trước một số dữ liệu. Điều đó có đúng không? Tôi biết rằng có những cách không chuẩn, nền tảng cụ thể, cách gọi tìm nạp trước như __builtin_prefetch, nhưng việc ném tất cả các địa điểm đó dường như là một tối ưu hóa sớm xấu xí. Tôi đang tìm kiếm một cách tôi có thể tiềm thức viết mã bộ nhớ cache hiệu quả.

Answer 1

Tôi biết bạn đã không yêu cầu (và có thể không cần một bài giảng về cách xử lý thích hợp của bộ nhớ cache, nhưng tôi nghĩ tôi sẽ đóng góp hai xu của mình. Lưu ý rằng tất cả điều này chỉ áp dụng trong mã nóng. Hãy nhớ rằng tối ưu hóa sớm là gốc rễ của tất cả các điều ác.

Như đã được chỉ ra trong các ý kiến, cách tốt nhất là có các thùng chứa dữ liệu thực tế. ngay cả khi bạn phải sao chép một số dữ liệu và/hoặc trả một mức giá để thay đổi kích thước/di chuyển/chống phân mảnh cấu trúc dữ liệu của bạn. một mảng dữ liệu) chỉ trả hết nếu bạn truy cập chúng một cách tuyến tính và tuần tự phần lớn thời gian.

Nhưng chiến lược này có thể không phải lúc nào cũng có thể sử dụng được. Thay cho dữ liệu tuyến tính thực tế, bạn có thể sử dụng các chiến lược khác như sử dụng các trình phân bổ pool và lặp lại qua các nhóm, thay vì trên vectơ giữ các con trỏ. Điều này tất nhiên có những nhược điểm riêng của nó và có thể phức tạp hơn một chút.

Tôi chắc chắn bạn đã biết điều này, nhưng nó lại nhắc đến một trong những kỹ thuật hiệu quả nhất để tận dụng tối đa bộ nhớ cache của bạn là có dữ liệu nhỏ hơn! Trong đoạn mã trên, nếu bạn có thể lấy đi với int16_t thay vì int32_t, bạn chắc chắn nên làm như vậy.Bạn nên đóng gói nhiều số bool s và cờ và enums vào các trường bit, sử dụng các chỉ mục thay vì các con trỏ (đặc biệt trên các hệ thống 64 bit,) sử dụng các giá trị băm cố định trong cấu trúc dữ liệu của bạn thay vì chuỗi, v.v. Bây giờ, về câu hỏi chính của bạn là liệu bộ xử lý có thể theo dõi các con trỏ ngẫu nhiên xung quanh và đưa dữ liệu vào bộ nhớ cache trước khi chúng cần thiết hay không. Ở một mức độ rất hạn chế, điều này xảy ra. Có lẽ bạn biết, CPU hiện đại sử dụng rất nhiều thủ thuật để tăng tốc độ của chúng (tức là tăng tốc độ rút lui lệnh của chúng.) Các thủ thuật như có bộ đệm cửa hàng, thực thi ngoài đơn đặt hàng, đường ống superscalar, nhiều đơn vị chức năng thuộc mọi loại, chi nhánh dự đoán, vv Hầu hết thời gian, các thủ thuật này chỉ giúp CPU tiếp tục thực hiện các hướng dẫn, ngay cả khi các hướng dẫn hiện tại đã bị ngừng hoặc mất quá nhiều thời gian để hoàn tất. Đối với tải bộ nhớ (đó là điều chậm nhất để làm, iff dữ liệu không có trong bộ nhớ cache,) điều này có nghĩa là CPU sẽ nhận được hướng dẫn càng sớm càng tốt, tính toán địa chỉ, và yêu cầu dữ liệu từ bộ điều khiển bộ nhớ. Tuy nhiên, bộ điều khiển bộ nhớ có thể chỉ có một số lượng rất hạn chế các yêu cầu xuất sắc (thường là hai ngày này, nhưng tôi không chắc chắn.) Điều này có nghĩa là ngay cả khi CPU thực hiện các công cụ rất tinh vi để nhìn vào các vị trí bộ nhớ khác (ví dụ: các phần tử của vector posPointers của bạn) và suy ra rằng đây là địa chỉ của dữ liệu mới mà mã của bạn cần, nó không thể đi xa phía trước vì bộ điều khiển bộ nhớ chỉ có thể có quá nhiều yêu cầu đang chờ xử lý.

Trong mọi trường hợp, AFAIK, tôi không nghĩ rằng CPU thực sự làm điều đó. Lưu ý rằng đây là một trường hợp khó, vì địa chỉ của các vị trí bộ nhớ được phân phối ngẫu nhiên của bạn nằm trong bộ nhớ (ngược với việc đăng ký hoặc tính toán được từ nội dung của thanh ghi.) Và nếu các CPU đã làm, nó sẽ không có rất nhiều hiệu ứng anyways vì giới hạn giao diện bộ nhớ.

Kỹ thuật tìm nạp trước bạn đã đề cập có vẻ hợp lệ đối với tôi và tôi đã thấy nó được sử dụng, nhưng nó chỉ mang lại hiệu quả đáng chú ý nếu CPU của bạn có việc cần làm trong khi chờ dữ liệu trong tương lai đến. Việc tăng thêm ba số nguyên mất ít thời gian hơn nhiều so với việc tải 12 byte từ bộ nhớ (tải một dòng bộ nhớ cache, thực sự) và vì vậy nó không có ý nghĩa nhiều đối với thời gian thực thi. Nhưng nếu bạn có thứ gì đó đáng giá và nặng hơn để phủ lên đầu bộ nhớ tìm nạp trước (ví dụ: tính toán một hàm phức tạp không yêu cầu dữ liệu từ bộ nhớ!) Thì bạn có thể tăng tốc rất tốt. Bạn thấy đấy, thời gian để đi qua vòng lặp trên về cơ bản là tổng thời gian của tất cả các bộ nhớ cache bị mất; và bạn đang nhận được gia số tọa độ và sổ kế toán vòng lặp miễn phí. Vì vậy, bạn sẽ giành được nhiều hơn nếu các công cụ miễn phí có giá trị hơn!

Answer 2

Bộ vi xử lý hiện đại có cơ chế tìm nạp trước phần cứng: Intel Hardware prefetcher. Họ suy ra các mô hình truy cập sải chân vào bộ nhớ và tìm nạp trước các vị trí bộ nhớ có khả năng được truy cập trong tương lai gần.

Tuy nhiên trong trường hợp con trỏ hoàn toàn ngẫu nhiên theo đuổi các kỹ thuật đó không thể giúp ích. Bộ vi xử lý không biết rằng chương trình trong thực thi đang thực hiện theo dõi con trỏ, do đó nó không thể tìm nạp trước cho phù hợp. Trong những trường hợp như vậy, các cơ chế phần cứng có hại cho hiệu năng vì chúng sẽ tìm nạp trước các giá trị không có khả năng được sử dụng.

Điều tốt nhất bạn có thể làm là cố gắng tổ chức các cấu trúc dữ liệu trong bộ nhớ theo cách truy cập vào các phần tiếp giáp của bộ nhớ có nhiều khả năng hơn.