mẹo hiệu suất cơ chế vòng lặp

Question

Vì tôi đang sử dụng các vòng lặp trên các mảng nhiều mảng lớn, mọi tiết kiệm trên chính cơ chế for-loop đều có ý nghĩa.

Theo đó, tôi đang tìm bất kỳ mẹo nào về cách giảm chi phí này.

ví dụ: : đếm ngược bằng cách sử dụng uint thay vì int và! = 0 như stop thay vì> 0 cho phép CPU làm công việc ít hơn (nghe nó một lần, không chắc chắn nó luôn luôn đúng)

Answer 1

Đầu tiên, đừng đổ mồ hôi những thứ nhỏ. Chi tiết như đếm ngược so với đếm ngược thường hoàn toàn không liên quan trong thời gian chạy. Con người nổi tiếng là xấu khi phát hiện các khu vực trong mã cần được tăng tốc. Sử dụng một hồ sơ. Trả ít hoặc không chú ý đến bất kỳ phần nào của vòng lặp không lặp lại, trừ khi trình lược tả nói khác đi. Hãy nhớ rằng những gì được viết trong một vòng lặp bên trong không nhất thiết phải được thực hiện trong một vòng lặp bên trong, vì các trình biên dịch hiện đại là khá thông minh về việc tránh sự lặp lại không cần thiết.

Điều đó đang được nói, rất thận trọng với việc bỏ vòng lặp trên các CPU hiện đại. Họ càng chặt chẽ, thì họ càng phù hợp với bộ nhớ cache. Trong một ứng dụng hiệu suất cao mà tôi đã làm việc vào năm ngoái, tôi đã cải thiện hiệu suất đáng kể bằng cách sử dụng các vòng thay vì mã thẳng, và thắt chặt chúng càng nhiều càng tốt. (Có, tôi đã lược tả, chức năng được đề cập chiếm 80% thời gian chạy.Tôi cũng đã chấm điểm lần so với đầu vào điển hình, vì vậy tôi biết những thay đổi này đã giúp.)

Hơn nữa, không có hại trong việc phát triển các thói quen có lợi cho mã hiệu quả. Trong C++, bạn nên có thói quen sử dụng pre-increment (++ i) thay vì post-increment (i ++) để tăng các biến vòng lặp. Nó thường không quan trọng, nhưng có thể tạo ra một sự khác biệt đáng kể, nó không làm cho mã ít đọc được hoặc có thể ghi, và sẽ không bị tổn thương.

Answer 2

Một gợi ý quan trọng: di chuyển càng nhiều tính toán vòng lặp bên ngoài càng tốt. Không phải tất cả các trình biên dịch đều có thể thực hiện điều đó một cách tự động. Đối với eample, thay vì:

for row = 0 to 999 
    for col = 0 to 999 
     cell[row*1000+col] = row * 7 + col 

sử dụng:

for row = 0 to 999 
    x = row * 1000 
    y = row * 7 
    for col = 0 to 999 
     cell[x+col] = y + col 

Answer 3

Như vòng của bạn sẽ có O (n^d) phức tạp (d = chiều), những gì thực sự đếm là những gì bạn đưa vào vòng lặp , không phải bản thân vòng lặp. Tối ưu hóa một vài chu kỳ trong khuôn khổ vòng lặp từ hàng triệu chu kỳ của một thuật toán không hiệu quả bên trong vòng lặp chỉ là dầu rắn.

Answer 4

Ghi vòng lặp có thể là một cách. Đó là:

for (i=0; i<N; i++) { 
    a[i]=...; 
} 

biến thành:

for (i=0; i<N; i+=4) { 
    a[i]=...; 
    a[i+1]=...; 
    a[i+2]=...; 
    a[i+3]=...; 
} 

Bạn sẽ cần phải xử lý đặc biệt khi N không phải là một bội số của 4 trong ví dụ trên.

Answer 5

Bạn đã đo chi phí? Bạn có biết bao nhiêu thời gian đã được xử lý cho các vòng lặp so với bao nhiêu thời gian được thực hiện mã ứng dụng của bạn? Mục tiêu của bạn là gì?

Answer 6

Đây không phải là một câu hỏi bất khả tri về ngôn ngữ, nó phụ thuộc rất cao vào ngôn ngữ không chỉ, mà còn phụ thuộc vào trình biên dịch. Hầu hết các trình biên dịch tôi tin sẽ biên dịch hai phần tử này tương đương:

for (int i = 0; i < 10; i++) { /* ... */ } 

int i = 0; 
while (i < 10) { 
    // ... 
    i++; 
} 

Trong hầu hết các ngôn ngữ/trình biên dịch, vòng lặp chỉ là cú pháp cho vòng lặp sau. Foreach là một câu hỏi khác một lần nữa, và phụ thuộc nhiều vào ngôn ngữ/trình biên dịch như thế nào nó được thực hiện, nhưng nó thường ít hiệu quả hơn là một vòng lặp bình thường trong/while. Làm thế nào nhiều hơn nữa là một lần nữa, ngôn ngữ và trình biên dịch phụ thuộc.

Đặt cược tốt nhất của bạn có thể là chạy một số điểm chuẩn với một số biến thể khác nhau trên một chủ đề và xem những gì xuất hiện trên đầu trang.

Chỉnh sửa: Để kết thúc, số suggestions here có thể giúp bạn tiết kiệm nhiều thời gian hơn là lo lắng về chính vòng lặp đó.

Answer 7

Tôi đồng ý với @Greg. Điều đầu tiên bạn cần làm là đặt một số điểm chuẩn tại chỗ. Sẽ có ít điểm tối ưu hóa bất cứ điều gì cho đến khi bạn chứng minh nơi mà tất cả thời gian xử lý của bạn đang được chi tiêu. "Tối ưu hóa sớm là gốc rễ của tất cả các điều ác"!

Answer 8

Cố gắng làm cho các vòng lặp của bạn tiếp giáp trong bộ nhớ, điều này sẽ tối ưu hóa việc sử dụng bộ nhớ cache. Nghĩa là, không làm điều này:

for (int i = 0; i < m; i++) 
    for (j = 0; j < n; j++) 
     s += arr[j][i]; 

• Nếu hình ảnh chế biến, chuyển đổi hai vòng một vòng lặp trên các điểm ảnh với một chỉ số duy nhất.
• Đừng tạo vòng lặp sẽ chạy 0 lần vì đường ống được tối ưu hóa để giả sử vòng lặp sẽ tiếp tục thay vì kết thúc.

Answer 9

BTW, trừ khi bạn cần tăng sau, bạn nên luôn sử dụng toán tử tăng trước. Nó chỉ là một sự khác biệt nhỏ, nhưng nó hiệu quả hơn.

Bên này là sự khác biệt:

• bài viết Tăng

  i++;

  là giống như:

  int postincrement(int &i)
{
int itmp = i;
i = i + 1;
return itmp;
}
  

• Pre Inc Re-ment

  ++i;

  là giống như:

  int preincrement(int &i)
{
i = i + 1;
return i;
}

Answer 10

Tôi nghĩ rằng hầu hết các trình biên dịch có lẽ sẽ làm việc này dù sao, bước xuống không nên hiệu quả hơn, như một tấm séc trị zero là rất nhanh cho bộ vi xử lý. Một lần nữa, mặc dù, bất kỳ trình biên dịch có giá trị trọng lượng của nó sẽ làm điều này với hầu hết các vòng anyway. Bạn cần phải loo vào những gì trình biên dịch đang làm.

Answer 11

Không có đủ thông tin để trả lời chính xác câu hỏi của bạn. Bạn đang làm gì bên trong vòng lặp của bạn? Tính toán trong một lần lặp có phụ thuộc vào giá trị được tính trong lần lặp trước không. Nếu không, bạn gần như có thể cắt giảm thời gian của bạn bằng một nửa chỉ đơn giản bằng cách sử dụng 2 chủ đề, giả sử bạn có ít nhất một bộ xử lý lõi kép. Một điều khác cần xem là cách bạn truy cập dữ liệu, nếu bạn đang thực hiện xử lý mảng lớn, để đảm bảo rằng bạn truy cập dữ liệu theo thứ tự vì nó được lưu trong bộ nhớ, tránh xóa bộ nhớ cache L1/L2 của bạn trên mỗi lần lặp lại (nhìn thấy điều này trước khi trên bộ đệm L1 nhỏ hơn, sự khác biệt có thể gây ấn tượng).

Một lần nữa, tôi sẽ xem xét những gì bên trong vòng lặp đầu tiên, nơi mà hầu hết các lợi ích (> 99%) sẽ là, thay vì hệ thống ống nước vòng lặp bên ngoài.

Nhưng sau đó một lần nữa, nếu mã vòng lặp của bạn là I/O bị ràng buộc, thì mọi thời gian dành cho tối ưu hóa đều bị lãng phí.

Answer 12

Có một số thông tin liên quan trong số các câu trả lời cho câu hỏi ngăn xếp chồng khác, how cache memory works. Tôi tìm thấy giấy theo số Ulrich Drepper được đề cập trong câu hỏi this đặc biệt hữu ích.

Answer 13

Nhân tiện, sử dụng short thay vì int trong vòng lặp nếu công suất Int16 được đảm bảo là đủ?