Bạn cần biết những kỹ thuật nào để tránh phân nhánh có điều kiện?

Question

Đôi khi một vòng lặp mà CPU dành phần lớn thời gian có một số dự đoán chi nhánh bỏ lỡ (misprediction) rất thường xuyên (gần xác suất 0,5.) Tôi đã nhìn thấy một vài kỹ thuật về các chủ đề rất cô lập nhưng không bao giờ là một danh sách. Những cái tôi biết đã sửa chữa các tình huống mà tình trạng có thể được chuyển sang một bool và 0/1 được sử dụng theo một cách nào đó để thay đổi. Có các nhánh có điều kiện khác có thể tránh được không?

ví dụ: (Giả)

loop() { 
    if (in[i] < C) 
    out[o++] = in[i++] 
    ... 
} 

có thể được viết lại, cho là mất một số khả năng đọc, với một cái gì đó như thế này:

loop() { 
    out[o] = in[i] // copy anyway, just don't increment 
    inc = in[i] < C // increment counters? (0 or 1) 
    o += inc 
    i += inc 
} 

Ngoài ra tôi đã nhìn thấy các kỹ thuật trong tự nhiên thay đổi &&-& trong điều kiện trong những bối cảnh nhất định thoát khỏi tâm trí của tôi ngay bây giờ. Tôi là một tân binh ở cấp độ tối ưu hóa này nhưng nó chắc chắn cảm thấy như có được nhiều hơn.

Answer 1

Tôi tin rằng cách phổ biến nhất để tránh phân nhánh là tận dụng bit song song trong việc giảm tổng số bước nhảy hiện diện trong mã của bạn. Các khối cơ bản càng dài thì đường ống càng ít bị đỏ.

Như người khác đã đề cập, nếu bạn muốn thực hiện nhiều hơn việc bỏ vòng lặp và cung cấp các gợi ý chi nhánh, bạn sẽ muốn tham gia hội họp. Tất nhiên điều này nên được thực hiện với sự thận trọng tối đa: trình biên dịch điển hình của bạn có thể viết lắp ráp tốt hơn trong nhiều trường hợp hơn một con người. Hy vọng tốt nhất của bạn là cạo bỏ các cạnh thô và đưa ra các giả định rằng trình biên dịch không thể suy ra được.

Dưới đây là một ví dụ về mã C sau:

if (b > a) b = a; 

Trong lắp ráp mà không cần bất cứ nhảy, bằng cách sử dụng bit thao tác (và cực đoan cho ý kiến):

sub eax, ebx ; = a - b 
sbb edx, edx ; = (b > a) ? 0xFFFFFFFF : 0 
and edx, eax ; = (b > a) ? a - b : 0 
add ebx, edx ; b = (b > a) ? b + (a - b) : b + 0 

Lưu ý rằng trong khi di chuyển có điều kiện là ngay lập tức tăng lên bởi những người đam mê lắp ráp, đó là chỉ vì họ dễ dàng hiểu và cung cấp một khái niệm ngôn ngữ cấp cao hơn trong một hướng dẫn duy nhất thuận tiện. Chúng không nhất thiết phải nhanh hơn, không có sẵn trên các bộ vi xử lý cũ hơn, và bằng cách ánh xạ mã C của bạn vào các lệnh di chuyển có điều kiện tương ứng, bạn chỉ thực hiện công việc của trình biên dịch.

Answer 2

Việc khái quát hóa ví dụ bạn đưa ra là "thay thế đánh giá có điều kiện bằng toán học"; tránh chi phối có điều kiện chủ yếu là giảm xuống đó.

Điều gì đang xảy ra với việc thay thế && bằng & là vì && là ngắn mạch, nó cấu thành đánh giá có điều kiện trong và của chính nó. & sẽ cho bạn kết quả logic tương tự nếu cả hai bên là 0 hoặc 1 và không phải là ngắn mạch. Tương tự áp dụng cho || và | ngoại trừ bạn không cần phải đảm bảo các bên bị giới hạn ở 0 hoặc 1 (một lần nữa, chỉ cho mục đích logic, tức là bạn chỉ sử dụng kết quả Booleanly).

Answer 3

GCC đã đủ thông minh để thay thế các điều kiện có hướng dẫn đơn giản hơn. Ví dụ: bộ xử lý Intel mới hơn cung cấp cmov (di chuyển có điều kiện). Nếu bạn có thể sử dụng nó, SSE2 cung cấp một số hướng dẫn để compare 4 integers (hoặc 8 quần short, hoặc 16 ký tự) tại một thời điểm.

Additionaly để tính tối thiểu mà bạn có thể sử dụng (xem những magic tricks):

min(x, y) = x+(((y-x)>>(WORDBITS-1))&(y-x)) 

Tuy nhiên, chú ý đến những thứ như:

c[i][j] = min(c[i][j], c[i][k] + c[j][k]); // from Floyd-Warshal algorithm 

thậm chí không nhảy được ngụ ý là chậm hơn nhiều so với

int tmp = c[i][k] + c[j][k]; 
if (tmp < c[i][j]) 
    c[i][j] = tmp; 

Tôi đoán tốt nhất là trong đoạn đầu tiên bạn làm ô nhiễm bộ nhớ cache e thường xuyên hơn, trong khi thứ hai bạn không.

Answer 4

Theo ý kiến ​​của tôi nếu bạn đang tiếp cận với mức tối ưu hóa này, có thể là thời gian để thả ngay vào ngôn ngữ lắp ráp.

Về cơ bản, bạn đang tính toán trên trình biên dịch tạo ra một mẫu lắp ráp cụ thể để tận dụng tối ưu hóa này trong C. Thật khó để đoán chính xác mã trình biên dịch sẽ tạo ra, vì vậy bạn phải xem xét nó bất cứ lúc nào một thay đổi nhỏ được thực hiện - tại sao không chỉ làm điều đó trong hội đồng và được thực hiện với nó?

Answer 5

Mức tối ưu hóa này không có khả năng tạo nên sự khác biệt đáng giá trong tất cả trừ điểm nóng nhất của các điểm nóng.Giả sử nó (không chứng minh nó trong một trường hợp cụ thể) là một dạng của đoán và quy tắc tối ưu hóa đầu tiên là không hành động theo dự đoán.

Answer 6

Ở cấp độ này, mọi thứ phụ thuộc phần cứng và phụ thuộc vào trình biên dịch. Trình biên dịch bạn có đang sử dụng đủ thông minh để biên dịch < không có luồng điều khiển không? gcc trên x86 đủ thông minh; lcc thì không. Trên bộ hướng dẫn cũ hoặc nhúng, có thể không tính được < mà không có luồng điều khiển.

Ngoài cảnh báo giống như Cassandra này, thật khó để đưa ra bất kỳ câu lệnh chung hữu ích nào. Vì vậy, dưới đây là một số tuyên bố chung có thể không hữu ích:

• Phần cứng dự đoán nhánh hiện đại cực kỳ tốt. Nếu bạn có thể tìm thấy một chương trình thực sự mà dự đoán chi nhánh xấu chi phí hơn 1% -2% suy thoái, tôi sẽ rất ngạc nhiên.

• Bộ đếm hiệu suất hoặc các công cụ khác cho bạn biết nơi tìm thấy các giả định chi nhánh là không thể thiếu.

• Nếu bạn thực sự cần phải cải thiện các mã này, tôi muốn nhìn vào dấu vết lịch và vòng lặp unrolling:

  • Vòng unrolling tái tạo cơ quan loop và đưa ra ưu của bạn kiểm soát dòng chảy hơn để làm việc với.

  • Theo dõi lịch biểu xác định đường dẫn nào có nhiều khả năng được thực hiện nhất, và trong số các thủ thuật khác, nó có thể điều chỉnh hướng nhánh để phần cứng dự đoán nhánh hoạt động tốt hơn trên các đường dẫn phổ biến nhất. Với các vòng chưa được kiểm soát, có nhiều đường dẫn dài hơn, do đó, trình theo dõi lần truy cập có nhiều hoạt động hơn với

• Tôi sẽ cố gắng tự mã hóa bản thân mình khi lắp ráp. Khi chip tiếp theo xuất hiện với phần cứng dự đoán chi nhánh mới, rất có thể là tuyệt vời khi tất cả công việc khó khăn của bạn đi xuống cống. Thay vào đó, tôi sẽ tìm một trình biên dịch tối ưu hóa phản hồi hướng dẫn phản hồi.

Answer 7

Hầu hết các bộ xử lý cung cấp dự đoán chi nhánh tốt hơn 50%. Trên thực tế, nếu bạn nhận được cải thiện 1% trong dự đoán chi nhánh thì bạn có thể xuất bản một bài báo. Có một đống giấy tờ về chủ đề này nếu bạn quan tâm.

Bạn nên lo lắng về lần truy cập và lần truy cập bộ nhớ cache.

Answer 8

Phần mở rộng của kỹ thuật được trình bày trong câu hỏi ban đầu được áp dụng khi bạn phải thực hiện một số thử nghiệm lồng nhau để nhận câu trả lời. Bạn có thể xây dựng một bitmask nhỏ từ kết quả của tất cả các bài kiểm tra, và "tra cứu" câu trả lời trong một bảng.

if (a) { 
    if (b) { 
    result = q; 
    } else { 
    result = r; 
    } 
} else { 
    if (b) { 
    result = s; 
    } else { 
    result = t; 
    } 
} 

Nếu a và b gần như ngẫu nhiên (ví dụ, từ dữ liệu tùy ý) và điều này là trong vòng lặp chặt chẽ thì lỗi dự đoán nhánh có thể thực sự làm chậm quá trình này. Có thể được viết là:

// assuming a and b are bools and thus exactly 0 or 1 ... 
static const table[] = { t, s, r, q }; 
unsigned index = (a << 1) | b; 
result = table[index]; 

Bạn có thể khái quát hóa điều này thành một số điều kiện. Tôi đã nhìn thấy nó được thực hiện cho 4. Nếu làm tổ được rằng sâu, tuy nhiên, bạn muốn đảm bảo rằng thử nghiệm tất cả chúng thực sự nhanh hơn so với chỉ làm các bài kiểm tra tối thiểu được đề xuất bởi đánh giá ngắn mạch.

Answer 9

Sử dụng ví dụ Matt Joiner của:

if (b > a) b = a; 

Bạn cũng có thể làm như sau, mà không cần phải thâm nhập vào mã lắp ráp:

bool if_else = b > a; 
b = a * if_else + b * !if_else;