Ý nghĩa của địa phương về cấu trúc dữ liệu là gì?

Question

Tôi đã đọc bài viết sau đây,

What Every Programmer Should Know About Compiler Optimizations

Có tối ưu hóa quan trọng khác hiện đang vượt quá khả năng của bất kỳ trình biên dịch-ví dụ, thay thế một thuật toán hiệu quả với một hiệu quả, hoặc thay đổi cách bố trí cấu trúc dữ liệu để cải thiện địa phương.

Điều đó có nghĩa là nếu tôi thay đổi thứ tự (bố cục) của thành viên dữ liệu trong lớp, nó có thể ảnh hưởng đến hiệu suất không?

Vì vậy,

class One 
{ 
int data0; 
abstract-data-type data1; 
}; 

Differes trong hoạt động từ,

class One 
{ 
abstract-data-type data0; 
int data1; 
}; 

Nếu điều này là đúng, quy tắc của ngón tay cái trong khi xác định các lớp học hoặc cấu trúc dữ liệu là gì?

Answer 1

Địa phương theo nghĩa này chủ yếu là nói đến vùng bộ nhớ cache. Viết cấu trúc dữ liệu và thuật toán để hoạt động chủ yếu trong bộ nhớ cache làm cho thuật toán chạy nhanh nhất có thể. Vị trí bộ nhớ cache là một trong những lý do để nhanh chóng sắp xếp nhanh sắp xếp.

Đối với cấu trúc dữ liệu, bạn muốn giữ các phần của cấu trúc dữ liệu của bạn liên kết với nhau tương đối gần nhau, để tránh làm sạch các dòng bộ nhớ cache hữu ích.

Ngoài ra, bạn có thể sắp xếp lại cấu trúc dữ liệu để trình biên dịch sẽ sử dụng lượng bộ nhớ tối thiểu cần thiết để giữ tất cả các thành viên và vẫn truy cập hiệu quả chúng. Điều này giúp đảm bảo cấu trúc dữ liệu của bạn tiêu thụ số lượng tối thiểu các dòng bộ nhớ cache.

_{Một dòng bộ nhớ cache duy nhất trên kiến ​​trúc x86-64 hiện tại (lõi i7) là 64 byte.}

Answer 2

Tôi không phải là một chuyên gia về dữ liệu/địa phương cấu trúc, nhưng nó đã làm với cách bạn tổ chức dữ liệu của bạn để tránh các bit CPU bộ nhớ đệm của bộ nhớ từ khắp nơi trên CPU do đó làm chậm chương trình của bạn bằng cách liên tục chờ đợi để tìm nạp bộ nhớ.

Ví dụ: danh sách được liên kết có thể nằm rải rác khắp bộ nhớ của bạn. Tuy nhiên, nếu bạn thay đổi thành một phần tử "" thì chúng sẽ lưu lại thời gian truy cập bộ nhớ nếu bạn cần duyệt qua chúng cùng một lúc (chỉ với một ví dụ)

Ngoài ra: Cũng là một số thư viện STL, một lần nữa tôi không chắc chắn 100% là tốt nhất, nhưng một số trong số đó (ví dụ như danh sách) là khá xấu về địa phương. Một ví dụ khác, có lẽ phổ biến hơn là một mảng con trỏ, trong đó các phần tử trỏ đến các phần tử có thể được phân tán xung quanh bộ nhớ. Tất nhiên, bạn không phải lúc nào cũng tránh điều này dễ dàng vì đôi khi bạn cần có khả năng thêm/di chuyển/chèn/xóa các phần tử động ...

Tóm tắt: Về cơ bản, điều này có nghĩa là bạn sẽ lưu ý cách bố trí dữ liệu của mình liên quan đến truy cập bộ nhớ.

Answer 3

Sắp xếp thành viên lớp theo tần suất bạn sẽ truy cập chúng. Điều này tối đa hóa "độ nóng" của dòng bộ nhớ cache có chứa phần đầu của lớp học của bạn, làm tăng khả năng của nó được lưu trong bộ nhớ cache. Một yếu tố khác mà bạn quan tâm là đóng gói - do căn chỉnh, sắp xếp lại thứ tự các thành viên được khai báo có thể dẫn đến giảm kích thước lớp của bạn, điều này sẽ làm giảm áp lực bộ nhớ cache.

(Không ai trong số họ là dứt khoát, tất nhiên. Những quy tắc của ngón tay cái không phải là một thay thế cho hồ sơ.)