Làm cách nào để tối ưu hóa dòng mã C này (phạm vi kiểm tra)?

Question

Có cách nào để tối ưu hóa dòng mã C sau đây (để tránh phân nhánh) không?

if ((i < -threshold) || (i > threshold)) 
{ 
    counter++; 
} 

Tất cả các biến là số nguyên được ký 16 bit. Một phiên bản được tối ưu hóa nên có tính di động cao.

Answer 1

Làm thế nào về:

counter += (i < -threshold) | (i > threshold); 

Giả sử mã ban đầu là hợp lệ, sau đó điều này nên làm việc quá, theo một cách cầm tay. Tiêu chuẩn cho biết rằng các toán tử quan hệ (<, > và vv) trả lại một int bằng 1 khi thành công hoặc 0 về lỗi.

CẬP NHẬT

Để trả lời bình luận Sheen dưới đây, đoạn mã sau:

int main() 
{ 
    short threshold = 10; 
    short i = 20; 
    short counter = 0; 

    counter += (i < -threshold) | (i > threshold); 

    return 0; 
} 

kết quả trong disassembler sau trên x86 sử dụng GCC, không có optimisations:

push %rbp 
    mov %rsp,%rbp 
    movw $0xa,-6(%rbp) 
    movw $0x14,-4(%rbp) 
    movw $0x0,-2(%rbp) 
    movswl -4(%rbp),%edx 
    movswl -6(%rbp),%eax 
    neg %eax 
    cmp %eax,%edx 
    setl %dl 
    movzwl -4(%rbp),%eax 
    cmp -6(%rbp),%ax 
    setg %al 
    or  %edx,%eax 
    movzbw %al,%dx 
    movzwl -2(%rbp),%eax 
    lea (%rdx,%rax,1),%eax 
    mov %ax,-2(%rbp) 
    mov $0x0,%eax 
    leaveq 
    retq 

Answer 2

So sánh tuyệt đối của cả hai số

short imask = i >> sizeof(short) * 8 - 1; //compute the sign bit 1 or 0 
short tmask = threshold >> sizeof(short) * 8 - 1; //compute the sign bit 1 or 0 

short iabsolute = (i + imask)^imask; // compute i absolute 
short tabsolute = (threshold + tmask)^tmask; // compute threshold absolute 

counter += iabsolute > tabsolute; 

Answer 3

Tùy thuộc vào việc phân phối giá trị của 'i', CPU của bạn có thể lưu bộ nhớ cache dự đoán chi nhánh cho bạn tốt hơn bất kỳ thay đổi mã nào bạn có thể thực hiện. Xem http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/ để có một ghi chú thú vị. Reddit thảo luận ở đây: http://www.reddit.com/r/programming/comments/c7ues/fast_and_slow_ifstatements_branch_prediction_in/

Answer 4

Bạn có thể sử dụng các thủ thuật sau đây giúp giảm các chi nhánh để chi nhánh duy nhất:

if (((unsigned) (i + threshold)) > (threshold << 1)) 
{ 
    counter++; 
} 

hoặc, đối với các pedantic:

if (((unsigned) i + (unsigned) threshold) > ((unsigned) threshold << 1)) 
{ 
    counter++; 
} 

Answer 5

này được dựa trên bit twiddling hacks, (được khuyến nghị)

#define CHAR_BIT 8 

int main() 
{ 
    int i=-3; // example input 
    int treshold=2; // example treshold 
    int count=0; 
    // step 1: find the absolute value of i 
    unsigned int r; // the result goes here 
    int const mask = i >> (sizeof(int) * CHAR_BIT - 1); 
    r = (i + mask)^mask; 
    // step 2: compute the sign of the difference 
    // sign becomes 0 (if r<=treshold) 
    // sign becomes 1 otherwise 
    int sign = 1^((unsigned int)(r-treshold-1) >> (sizeof(int) * CHAR_BIT - 1)); 
    count+=sign; 
    return count; 
} 

Làm việc này cho 32 bit số nguyên, thích ứng với 16 bit nên dễ dàng. Nó biên dịch bằng g ++.

Tốc độ phụ thuộc vào bộ xử lý đã sử dụng. Việc phân nhánh có thể nhanh hơn sau tất cả.

Answer 6

Oli Charlesworth, tôi nghĩ, có ý tưởng đúng. Tuy nhiên, tôi nghi ngờ rằng nó có thể được tối ưu hóa thêm (với chi phí dễ đọc).

Ngưỡng có thể được chuẩn hóa thành 0 để loại bỏ so sánh.

Đó là, ...

counter += ((unsigned) (i + threshhold) < (unsigned) (threshhold + threshhold)); 

Answer 7

Có một thành ngữ tiêu chuẩn cho phạm vi kiểm tra với một hướng dẫn so sánh duy nhất.Nó đi như:

(unsigned)x - a <= (unsigned)b - a /* a <= x <= b */ 
(unsigned)x - a < (unsigned)b - a /* a <= x < b */ 

Là một ví dụ phổ biến (phiên bản này nếu isdigit là đảm bảo được đúng theo tiêu chuẩn):

(unsigned)ch - '0' < 10 

Nếu loại ban đầu của bạn là lớn hơn int (ví dụ long long) sau đó bạn sẽ cần phải sử dụng các loại chưa ký lớn hơn (ví dụ unsigned long long). Nếu a và b là các hằng số hoặc đã có loại chưa ký hoặc nếu bạn biết b-a sẽ không tràn, bạn có thể bỏ qua đoạn trích từ b.

Để phương thức này hoạt động, tự nhiên bạn phải có a<=b và các loại/giá trị phải sao cho biểu thức gốc (ví dụ: a <= x && x <= b hoặc tương tự) hoạt động chính xác về mặt toán học. Ví dụ: nếu x được ký và b không được ký, x<=b có thể đánh giá sai khi x=-1 và b=UINT_MAX-1. Miễn là các loại ban đầu của bạn đều được ký hoặc nhỏ hơn loại chưa ký bạn đúc, đây không phải là vấn đề.

Đối với cách "lừa" này hoạt động, nó hoàn toàn xác định, sau khi giảm modulo UINT_MAX+1, cho dù x-a nằm trong khoảng 0 đến b-a.

Trong trường hợp của bạn, tôi nghĩ rằng những điều sau đây nên làm việc tốt:

(unsigned)i + threshold > 2U * threshold; 

Nếu threshold không thay đổi giữa lặp loop, trình biên dịch có lẽ có thể giữ cả threshold và 2U*threshold trong thanh ghi.

Nói về tối ưu hóa, trình biên dịch tốt nên tối ưu hóa thử nghiệm phạm vi ban đầu của bạn để sử dụng số học chưa ký, nơi nó biết các ràng buộc được đáp ứng. Tôi nghi ngờ nhiều người làm như vậy với a và b không đổi, nhưng có lẽ không phải với các biểu thức phức tạp hơn. Ngay cả khi trình biên dịch có thể tối ưu hóa nó, mặc dù, thành ngữ (unsigned)x-a<b-a vẫn cực kỳ hữu ích trong các macro mà bạn muốn đảm bảo rằng x được đánh giá chính xác một lần.

Answer 8

Ồ, quá xấu câu hỏi đã được trả lời. Để diễn giải câu trả lời Oli của, mã

#include <stdint.h> 
int main() 
{ 
    int32_t threshold_square = 100; 
    int16_t i = 20; 
    int16_t counter = 0; 

    counter += ((int32_t) i * i > threshold_square); 

    return 0; 
} 

mang lại sự lắp ráp x86 sau sử dụng GCC mà không cần tối ưu hóa

pushq %rbp 
movq %rsp, %rbp 
movl $100, -8(%rbp) 
movw $20, -2(%rbp) 
movw $0, -4(%rbp) 
movswl -2(%rbp),%edx 
movswl -2(%rbp),%eax 
imull %edx, %eax 
cmpl -8(%rbp), %eax 
setg %al 
movzbl %al, %edx 
movzwl -4(%rbp), %eax 
leal (%rdx,%rax), %eax 
movw %ax, -4(%rbp) 
movl $0, %eax 
leave 
ret 

mà là bốn hướng dẫn ít hơn sử dụng (i < -threshold) | (i > threshold).

Cho dù điều này tốt hơn hay không, tất nhiên, tùy thuộc vào kiến ​​trúc.

(Việc sử dụng stdint.h là dành cho mục đích minh họa, cho C89 nghiêm ngặt thay thế với bất cứ điều gì có liên quan cho hệ thống đích.)

Answer 9

Điều gì là sai với mã gốc? Liệu nó có thực sự cần tối ưu hóa tay không?

Bất kỳ trình biên dịch nào cũng có thể tối ưu hóa điều đó rất tốt. Bất kỳ sự tối ưu hóa bằng tay nào cũng có thể chỉ dẫn đến sự làm xáo trộn.

Answer 10

Mã này không có nhánh nào có độ di động cao (tuy nhiên, việc triển khai abs có thể có một).

#include <stdlib.h> 
counter += abs(i) > threshold; 

Đó là biểu thức tuân thủ tiêu chuẩn đơn giản nhất.

Nếu trình biên dịch của bạn không sử dụng macro được tối ưu hóa cho abs(), bạn có thể sử dụng hàm macro/nội tuyến của riêng bạn.

Đó là những ví dụ, rằng việc sử dụng bản chất của định dạng twos bổ sung được sử dụng trên hầu hết các máy:

#define ABS(x) ((x)*(((x)>>15)|1)) 

#define ABS(x) ((x)-((x)>>15)^((x)>>15)) 

Ngoài ra bạn có thể thay thế toán tử so sánh với biểu hiện như thế này:

#define LESS(x, y) (-((x)-(y))>>15)) 

mã kết quả:

counter -= ((threshold - abs(i)) >> 15); 

Tất cả các macro đó dựa trên thực tế, dịch chuyển sang phải sang số của các bit trừ đi một giá trị dương hoặc giá trị 0 bằng không, và các giá trị âm đến một giá trị âm. Nhưng thực hiện thats được xác định.