Ví dụ về hàm C đơn giản được triển khai nhanh hơn trong lắp ráp nội tuyến là gì?

Question

Tôi đang gặp khó khăn khi đánh bại trình biên dịch bằng cách sử dụng lắp ráp nội tuyến.

Một ví dụ tốt, không có lợi của một chức năng mà trình biên dịch có thời gian khó thực hiện, thực sự nhanh chóng và đơn giản là gì? Nhưng đó là tương đối đơn giản để thực hiện với lắp ráp nội tuyến.

Answer 1

Vì nó liên quan đến mã iPhone và lắp ráp sau đó tôi sẽ đưa ra một ví dụ có liên quan trong thế giới iPhone (và không phải một số sse hoặc x86 asm). Nếu ai đó quyết định viết mã lắp ráp cho một số ứng dụng thế giới thực, thì rất có thể đây sẽ là một số loại xử lý tín hiệu số hoặc thao tác hình ảnh. Ví dụ: chuyển đổi không gian màu của pixel RGB, mã hóa hình ảnh sang định dạng jpeg/png hoặc mã hóa âm thanh thành mp3, amr hoặc g729 cho các ứng dụng voip. Trong trường hợp mã hóa âm thanh có nhiều trình dịch không thể dịch bởi trình biên dịch thành mã asm hiệu quả, chúng đơn giản là không tương đương trong C. Ví dụ về các công cụ thường được sử dụng trong xử lý âm thanh: toán học bão hòa, nhân, tích lũy thường trình, nhân ma trận .

Ví dụ về bổ sung bão hòa: 32-bit ký int có phạm vi: 0x8000 0000 < = int32 < = 0x7fff ffff. Nếu bạn thêm hai kết quả ints có thể tràn, nhưng điều này có thể không được chấp nhận trong một số trường hợp nhất định trong xử lý tín hiệu kỹ thuật số. Về cơ bản, nếu kết quả tràn hoặc underflows bão hòa thêm nên trả về 0x8000 0000 hoặc 0x7fff ffff. Đó sẽ là một hàm c đầy đủ để kiểm tra điều đó. một phiên bản tối ưu hóa các add bão hòa có thể là:

 
int saturated_add(int a, int b) 
{ 
    int result = a + b; 

    if (((a^b) & 0x80000000) == 0) 
    { 
     if ((result^a) & 0x80000000) 
     { 
      result = (a < 0) ? 0x80000000 : 0x7fffffff; 
     } 
    } 
    return result; 
} 

bạn cũng có thể làm nhiều if/else để kiểm tra tràn hoặc trên x86, bạn có thể kiểm tra tràn cờ (mà cũng đòi hỏi bạn phải sử dụng asm). iPhone sử dụng cv armv6 hoặc v7 có dsp asm. Vì vậy, hàm saturated_add với nhiều brunches (if/else statements) và 2 hằng số 32 bit có thể là một lệnh asm đơn giản chỉ sử dụng một chu kỳ CPU. Vì vậy, chỉ cần làm saturated_add để sử dụng lệnh asm có thể làm cho toàn bộ thuật toán nhanh gấp hai đến ba lần (và nhỏ hơn về kích thước). Dưới đây là hướng dẫn QADD: QADD

ví dụ khác về mã mà thường thực hiện trong vòng dài là

 
res1 = a + b1*c1; 
res2 = a + b2*c2; 
res3 = a + b3*c3; 

có vẻ như không có gì không thể được tối ưu hóa ở đây, nhưng trên ARM cpu bạn có thể sử dụng hướng dẫn dsp cụ thể mất ít chu kỳ hơn để làm phép nhân đơn giản! Đúng vậy, a + b * c với các hướng dẫn cụ thể có thể thực thi nhanh hơn đơn giản * b. Đối với loại trình biên dịch đơn giản này không thể hiểu logic của mã của bạn và không thể sử dụng các hướng dẫn dsp này trực tiếp và đó là lý do tại sao bạn cần viết asm theo cách thủ công để tối ưu hóa mã, NHƯNG bạn chỉ nên viết thủ công một số phần mã cần làm được tối ưu hóa. Nếu bạn bắt đầu viết các vòng đơn giản bằng tay thì hầu như chắc chắn bạn sẽ không đánh bại trình biên dịch! Có nhiều giấy tờ tốt trên web để lắp ráp nội tuyến để mã bộ lọc linh sam, mã hóa/giải mã amr, v.v.

Answer 2

Chiến thắng tốt nhất của tôi trên trình biên dịch là một thói quen đơn giản ... Tôi bỏ qua rất nhiều công cụ thiết lập cơ bản (ví dụ, tôi không cần nhiều khung ngăn xếp, vì vậy tôi lưu một vài chu kỳ ở đó), và đã làm một vài điều khá lông.

Đó là khoảng 6 năm trước, với một số trình biên dịch độc quyền có chất lượng không xác định. Tôi sẽ phải khai thác mã tôi đã có và thử nó với GCC ngay bây giờ; Tôi không biết rằng nó có thể nhận được bất kỳ nhanh hơn, nhưng tôi sẽ không loại trừ nó ra.

Cuối cùng, mặc dù memcpy của tôi trung bình nhanh hơn 15 lần so với thư viện C của chúng tôi, tôi chỉ giữ nó trong túi sau trong trường hợp tôi cần nó. Đó là một món đồ chơi cho tôi để chơi với lắp ráp PPC, và tăng tốc là không cần thiết trong ứng dụng của chúng tôi.

Answer 3

Nếu bạn muốn thực hiện các công việc như hoạt động SIMD, bạn có thể đánh bại trình biên dịch. Điều này đòi hỏi kiến ​​thức tốt về kiến ​​trúc và tập lệnh mặc dù.

Answer 4

Nếu bạn không xem xét các hoạt động SIMD gian lận, bạn thường có thể viết SIMD lắp ráp mà thực hiện tốt hơn nhiều so với khả năng của trình biên dịch autovectorization của bạn (Nếu nó thậm chí có autovectorization!)

Here's một SSE rất cơ bản (Một trong những của x86 Bộ hướng dẫn SIMD) hướng dẫn. Đó là cho Visual C++ lắp ráp trực tuyến.

Chỉnh sửa: Đây là một cặp chức năng nhỏ nếu bạn muốn tự mình thử. Đó là tính toán của một sản phẩm có độ dài dấu chấm n. Một là sử dụng SSE 2 hướng dẫn trực tuyến (GCC trong dòng cú pháp) khác là rất cơ bản C.

Nó rất đơn giản và tôi sẽ rất ngạc nhiên nếu một trình biên dịch tốt không thể vectơ hóa vòng lặp C đơn giản , nhưng nếu không, bạn sẽ thấy tốc độ tăng lên trong SSE2. Phiên bản SSE 2 có thể nhanh hơn nếu tôi sử dụng nhiều thanh ghi nhưng tôi không muốn kéo dài kỹ năng SSE rất yếu của mình :).

float dot_asm(float *a, float*b, int n) 
{ 
    float ans = 0; 
    int i; 
    // I'm not doing checking for size % 8 != 0 arrays. 
    while(n > 0) { 
    float tmp[4] __attribute__ ((aligned(16))); 

    __asm__ __volatile__(
      "xorps  %%xmm0, %%xmm0\n\t" 
      "movups  (%0), %%xmm1\n\t" 
      "movups  16(%0), %%xmm2\n\t" 
      "movups  (%1), %%xmm3\n\t" 
      "movups  16(%1), %%xmm4\n\t" 
      "add  $32,%0\n\t" 
      "add  $32,%1\n\t" 
      "mulps  %%xmm3, %%xmm1\n\t" 
      "mulps  %%xmm4, %%xmm2\n\t" 
      "addps  %%xmm2, %%xmm1\n\t" 
      "addps  %%xmm1, %%xmm0" 
      :"+r" (a), "+r" (b) 
      : 
      :"xmm0", "xmm1", "xmm2", "xmm3", "xmm4"); 

    __asm__ __volatile__(
     "movaps  %%xmm0, %0" 
     : "=m" (tmp) 
     : 
     :"xmm0", "memory");    

    for(i = 0; i < 4; i++) { 
     ans += tmp[i]; 
    } 
    n -= 8; 
    } 
    return ans; 
} 

float dot_c(float *a, float *b, int n) { 

    float ans = 0; 
    int i; 
    for(i = 0;i < n; i++) { 
    ans += a[i]*b[i]; 
    } 
    return ans; 
} 

Answer 5

Trừ khi bạn là một assembly guru tỷ lệ cược của đập trình biên dịch là rất thấp.

Một đoạn từ đường link trên,

Ví dụ, các bit theo định hướng "XOR % EAX,% EAX" hướng dẫn là cách nhanh nhất để thiết lập một đăng ký để không trong thế hệ đầu của x86, nhưng hầu hết mã được tạo bởi trình biên dịch và trình biên dịch hiếm khi tạo lệnh XOR. Vì vậy, các IA nhà thiết kế, quyết định chuyển thường xuyên xảy ra trình biên dịch hướng dẫn tạo lên phía trước của decode logic tổ hợp làm cho chữ "movl $ 0,% EAX" hướng dẫn thực hiện nhanh hơn so với hướng dẫn XOR.

Answer 6

Tôi đã triển khai một tương quan chéo đơn giản bằng cách sử dụng triển khai "eo biển C" chung. Và THÌ khi mất nhiều thời gian hơn so với số lần tôi có, tôi đã sử dụng thuật toán song song rõ ràng và sử dụng bộ xử lý nội tại để buộc các hướng dẫn cụ thể được sử dụng trong các phép tính. Đối với trường hợp cụ thể này, thời gian tính toán giảm từ> 30ms xuống còn hơn 4ms. Tôi đã có một cửa sổ 15ms để hoàn tất quá trình xử lý trước khi việc thu thập dữ liệu tiếp theo xảy ra.

Đây là loại tối ưu hóa SIMD trên bộ xử lý VLWI. Điều này chỉ yêu cầu 4 hoặc hơn về nội tại của bộ xử lý, đó là các hướng dẫn ngôn ngữ lắp ráp cơ bản cho sự xuất hiện của một lời gọi hàm trong mã nguồn. Bạn có thể làm tương tự với lắp ráp nội tuyến nhưng cú pháp và quản lý đăng ký là một chút đẹp hơn với bộ xử lý nội tại.

Khác với điều đó nếu kích thước quan trọng, người lắp ráp là vua. Tôi đã đi học với một anh chàng người đã viết một trình soạn thảo văn bản toàn màn hình trong ít hơn 512 byte.

Answer 7

Tôi có thuật toán tổng kiểm tra yêu cầu từ được xoay bởi một số bit nhất định. Để thực hiện nó, tôi đã có macro này:

//rotate word n right by b bits 
#define ROR16(n,b) (((n)>>(b))|(((n)<<(16-(b)))&0xFFFF)) 

//... and inside the inner loop: 
sum ^= ROR16(val, pos); 

VisualStudio phát hành xây dựng mở rộng như thế này: (val là rìu, pos là trong dx, sum là trong bx)

mov   ecx,10h 
sub   ecx,edx 
mov   ebp,eax 
shl   ebp,cl 
mov   cx,dx 
sar   ax,cl 
add   esi,2 
or   bp,ax 
xor   bx,bp 

Càng hội đồng được tạo bằng tay tương đương hiệu quả sẽ là:

mov  cl,dx 
ror  ax,cl 
xor  bx,ax 

Tôi chưa tìm ra cách phát ra chỉ dẫn ror từ thuần túy 'c' mã. Tuy nhiên ...
Trong khi viết điều này lên, tôi nhớ bản chất trình biên dịch. Tôi có thể tạo tập hợp hướng dẫn thứ hai với:

sum ^= _rotr16(val,pos); 

Câu trả lời của tôi là: Ngay cả khi bạn nghĩ rằng bạn có thể đánh bại trình biên dịch thuần túy, hãy kiểm tra nội tại trước khi sử dụng để lắp ráp nội tuyến.