Viết chậm vào mảng trong C++

Question

Tôi đã tự hỏi liệu đây có phải là hành vi được mong đợi trong C++ hay không. Đoạn code dưới đây chạy vào khoảng 0,001 ms:

for(int l=0;l<100000;l++){ 
     int total=0; 
     for(int i = 0; i < num_elements; i++) 
     { 
      total+=i; 
     } 
    } 

Tuy nhiên nếu kết quả được ghi vào một mảng, thời gian thực hiện bắn lên đến 15 ms:

int *values=(int*)malloc(sizeof(int)*100000); 
     for(int l=0;l<100000;l++){ 
      int total=0; 
      for(unsigned int i = 0; i < num_elements; i++) 
      { 
       total+=i; 
      } 
      values[l]=total; 
     } 

tôi có thể hiểu rằng văn bản cho mảng mất thời gian nhưng là thời gian tỷ lệ?

Chúc mừng mọi người

Answer 1

Ví dụ đầu tiên có thể được triển khai chỉ sử dụng thanh ghi CPU. Chúng có thể được truy cập hàng tỷ lần mỗi giây. Ví dụ thứ hai sử dụng rất nhiều bộ nhớ mà nó chắc chắn tràn L1 và có thể cache L2 (tùy thuộc vào mô hình CPU). Điều đó sẽ chậm hơn. Tuy nhiên, 15 ms/100.000 viết đi ra đến 1,5 ns cho mỗi viết - 667 Mhz hiệu quả. Đó là không phải là chậm.

Answer 2

Dường như trình biên dịch tối ưu hóa vòng lặp hoàn toàn trong trường hợp đầu tiên.

Tổng hiệu lực của vòng lặp là một no-op, do đó trình biên dịch chỉ xóa nó.

Answer 3

Tôi nghi ngờ rằng những gì bạn thấy là ảnh hưởng của virtual memory và có thể phân trang. Cuộc gọi malloc sẽ phân bổ một bộ nhớ có kích thước phù hợp có thể được đại diện bởi một số trang ảo. Mỗi trang được liên kết vào bộ nhớ quá trình riêng biệt.

Bạn cũng có thể đo chi phí gọi số malloc tùy thuộc vào cách bạn định thời gian vòng lặp. Trong cả hai trường hợp, hiệu suất sẽ rất nhạy cảm với các tùy chọn tối ưu hóa trình biên dịch, tùy chọn luồng, phiên bản trình biên dịch, phiên bản thời gian chạy và mọi thứ khác. Bạn không thể giả định một cách an toàn rằng chi phí là tuyến tính với kích thước của phân bổ. Điều duy nhất bạn có thể làm là đo lường nó và tìm ra cách tối ưu hóa tốt nhất khi nó đã được chứng minh là một vấn đề.

Answer 4

Rất đơn giản. Trong trường hợp đầu tiên, bạn chỉ có 3 biến, có thể dễ dàng lưu trữ trong GPR (mục đích chung), nhưng không có nghĩa là chúng luôn ở đó, nhưng chúng có thể nằm trong bộ nhớ cache L1, có nghĩa là chúng có thể được truy cập rất nhanh.

Trong trường hợp thứ hai Bạn có hơn 100 nghìn biến và Bạn cần khoảng 400kB để lưu chúng. Đó là deffinitely đến nhiều cho đăng ký và bộ nhớ cache L1. Trong trường hợp tốt nhất nó có thể là trong bộ nhớ cache L2, nhưng có lẽ không phải tất cả chúng sẽ ở trong L2. Nếu một cái gì đó không phải là trong đăng ký, L1, L2 (Tôi giả định rằng bộ vi xử lý của bạn không có L3) có nghĩa là bạn cần phải tìm kiếm nó trong bộ nhớ RAM và phải mất muuuuuch nhiều thời gian hơn.