Tác động bất lợi của các vectơ lồng nhau so với các mảng liền kề

Question

Đã có bất kỳ kiểm tra đáng tin cậy nào hiển thị rõ ràng sự khác biệt hiệu suất giữa truy cập và ghi vào vectơ lồng nhau so với các mảng dựng sẵn của C++ không? Tôi đã nghe nói rằng việc sử dụng các vectơ lồng nhau (đa chiều) thường có một số chi phí hiệu năng so với các phần tử truy cập trong một mảng đơn (tất cả các phần tử được lưu trữ trong bộ nhớ liền kề), nhưng điều này dường như chỉ là giả thiết đối với tôi. Tôi chưa thấy bất kỳ thử nghiệm nào thực sự cho thấy những khác biệt này. Chúng có ý nghĩa không? Tôi chắc chắn rằng nó phụ thuộc vào kịch bản, nhưng là một lập trình viên thiếu kinh nghiệm, tôi không hoàn toàn chắc chắn ở mức độ nào những khác biệt này trở nên có ý nghĩa.

Answer 1

Nó chắc chắn phụ thuộc vào kịch bản, trong phạm vi mà tôi không nghĩ rằng nó có thể trả lời một cách chung mà cách tiếp cận là nhanh nhất. Cách tiếp cận nhanh nhất sẽ là phương thức truy cập có vị trí dữ liệu tốt nhất - phụ thuộc rất lớn vào mẫu truy cập cũng như cách cấu trúc được đặt trong bộ nhớ, trong trường hợp vectơ lồng nhau phụ thuộc vào bộ cấp phát và có thể thay đổi khá nhiều giữa các trình biên dịch.

Tôi sẽ tuân thủ quy tắc chung về tối ưu hóa, đầu tiên viết mọi thứ theo cách đơn giản nhất và sau đó thử tối ưu hóa khi bạn có thể chứng minh có một nút cổ chai.

Answer 2

Hai điều góp phần vào sự chênh lệch thời gian chạy giữa mảng lồng nhau và phẳng:
Caching hành vi và gián tiếp

• CPU sử dụng một hệ thống các Caches để tránh truy cập vào RAM trực tiếp quá thường xuyên. Điều này khai thác thực tế rằng hầu hết các truy cập bộ nhớ là liền kề hoặc có một số địa điểm thời gian nhất định, tức là những gì được truy cập gần đây sẽ sớm được truy cập lại.
  Điều này có nghĩa rằng nếu các mảng trong cùng của mảng lồng nhau của bạn khá lớn, bạn sẽ thấy nhỏ hoặc không có sự khác biệt với mảng phẳng nếu bạn lặp qua các giá trị theo kiểu liền kề. Điều này có nghĩa là khi lặp qua một loạt các giá trị, đối với các mảng phẳng, vòng lặp trong cùng của bạn sẽ lặp qua các phần tử liên tiếp, đối với các mảng lồng nhau, vòng lặp trong cùng của bạn sẽ lặp qua mảng trong cùng.
• Nếu các mẫu truy cập của bạn là ngẫu nhiên, sự khác biệt quan trọng nhất về thời gian là các số:
  Đối với mảng phẳng, bạn sử dụng một cái gì đó như A[(Z * M + Y) * N + X], do đó bạn thực hiện 4 phép tính số học và sau đó truy cập bộ nhớ.
  Đối với mảng lồng nhau, bạn sử dụng A[Z][Y][X], vì vậy có ba truy cập bộ nhớ phụ thuộc lẫn nhau: Bạn cần biết A[Z] trước khi bạn có thể truy cập A[Z][Y] và cứ tiếp tục như vậy. Do kiến ​​trúc siêu cứng của CPU hiện đại, các hoạt động có thể được thực thi song song là các hoạt động đặc biệt hiệu quả, phụ thuộc lẫn nhau không quá nhiều. Vì vậy, bạn có một số phép toán số học và tải bộ nhớ ở một bên và ba tải phụ thuộc lẫn nhau ở phía bên kia, chậm hơn đáng kể. Có thể đối với mảng lồng nhau, nội dung của A và cũng có thể là A[Z] đối với một số giá trị của Z trong cấu trúc bộ nhớ cache, nhưng nếu mảng lồng nhau của bạn đủ lớn, nó sẽ không bao giờ khớp hoàn toàn vào bộ nhớ cache, nhiều bộ nhớ cache bị mất và tải bộ nhớ (lồng nhau) thay vì chỉ một bộ nhớ cache bỏ lỡ và tải (phẳng) cho một truy cập ngẫu nhiên duy nhất vào mảng.

Xem thêm his question, đặc biệt là các câu trả lời ngắn dưới đây cho một cuộc thảo luận chi tiết hơn về bộ nhớ đệm (câu trả lời của tôi) và gián tiếp (câu trả lời Phêrô), mà còn cung cấp một ví dụ nơi không có khác biệt đáng chú ý giữa các mảng lồng nhau và phẳng (sau khi sửa chữa các lỗi lập chỉ mục tất nhiên;))

Vì vậy, nếu bạn muốn biết nếu có sự khác biệt thời gian chạy đáng kể giữa chúng, câu trả lời của tôi sẽ là:

• Nếu bạn làm truy cập ngẫu nhiên, bạn sẽ chắc chắn thông báo nhiều gián tiếp tiện ích, do đó dẫn đến thời gian chạy lớn hơn cho các mảng lồng nhau.

• Nếu bạn truy cập tiếp giáp và sử dụng thứ tự đúng của các vòng (loop trong cùng = mảng trong cùng/index trong cùng cho mảng phẳng) và chiều trong cùng bạn của mảng đa chiều là đủ lớn, sau đó sự khác biệt sẽ là không thể bỏ qua, vì trình biên dịch sẽ có thể di chuyển tất cả các indirections ra khỏi vòng lặp trong cùng.