Clever Geek Handbook

枝を取り除く必要がありますか？ -たとえば、sign、abs、min、max

コミュニティにパイロット実験に参加してもらいたいと思います。 その本質は、コンピューターでC ++で書かれたプログラムを実行し、関数sign（x）、abs（x）、min（a、b）およびmax（ a、b）分岐ありと分岐なしで実行。 記事では、動機を説明し、機能自体を示し、最後に、実験への参加条件とその（alas）制限を提供します。



やる気



プログラマー、特に90年代後半のどこかでプログラミングを学んだプログラマーの間では、分岐のないアルゴリズムのほうが分岐のあるアルゴリズムよりも優れているという確信がまだあります。 プログラマーがより効率的であるように思えたために、分岐せずにいくつかの単純な関数を実装しようとする際に、私はしばしば極端な狂信に会いました。 このような単純な関数の中で、特にこれまでに4つを挙げました。数値の符号、数値の絶対値、最小値と最大値（2つのバージョン：符号のある数値とない数値の場合）。 実験が成功したら、他の多くのアルゴリズムを取り上げます。



IFを使用しないほうが速いのは本当ですか？



いいえ、そうではありません。 より正確に言うと、分岐を取り除くと、速度が向上するか、状況が数回悪化する可能性があります。 それはすべて、特定のコードが実行される特定のマシンとコンパイラに依存します。 私の古いコンピューター、Core 2 Duo E8400 @ 3GHzの例を挙げましょう-その上で、提案されたすべての機能は、IFバージョンで高速に動作します。 コンパイラVC ++ 2015、コンパイルオプション/ Oxがあります。



テストすることを提案している機能を詳しく見てみましょう。 4つの関数はそれぞれ、6つのオプションで記述できます。これらはすべて、記事の最後にあるリンク[1-7]を使用して学習できます。 これらのオプションをすべてテストし、それぞれの機能に対して2つを選択しました：クラシックと分岐のない1つ（私の測定で最高）。 繰り返しますが、私の実験が成功した場合、私は知っているすべてのオプションの一般的な同様の比較を行います[4-7]。



まず、データ型のエイリアスとシフトの定数を紹介します。 



typedef int32_t   i32;
typedef uint32_t  u32;
typedef int8_t    sign_t;
const u32 SHIFT = 31;


– sign



: 



sign_t sign0 (i32 a) {
  if (a>0)  return +1;
  if (a<0)  return -1;
  return 0;
}


: 



sign_t sign1 (i32 a) {
  return (a >> SHIFT) | ((u32)(-a) >> SHIFT);
}


, , . : .



. 2,87 , 3,97 13,02 vs 1,26 .



– abs



. IF, , , : 



u32 abs0 (i32 a) {
  if (a<0)  return -a;
  return a;
}


( ) : 



u32 abs1 (i32 a) {
 const i32 b = a >> SHIFT; 
 return (a+b) ^ b;
}


2,29, — 2,33 12,01 vs 0,81 . : , abs, [3]. , IF, , . .



— mini maxi



- , : 



i32 mini0 (i32 a, i32 b) {
  return a<b ? a:b;
}
i32 maxi0 (i32 a, i32 b) {
  return a>b ? a:b;
}


( ) : 



i32 mini0 (i32 a, i32 b) {
  return a>b ? b:a;
}
i32 maxi0 (i32 a, i32 b) {
  return a<b ? b:a;
}


, , . , , (a b, ). , . , , inc ecx , lea eax, [eax+1], , .



( ): 



i32 mini1 (i32 a, i32 b) {
  i32 d = a-b;
  return a - (d&(~(d^((a^b)&(d^a))) >> SHIFT));
}
i32 maxi1 (i32 a, i32 b) {
  i32 d = a-b;
  return b + (d&(~(d^((a^b)&(d^a))) >> SHIFT));
}


. 3,5 , – 9 2 vs 6 . .



, x86 cmovl, . , , , . , , , , .



— minu maxu



, i32 u32: 



u32 minu0 (u32 a, u32 b) {
  return a>b ? b:a;
}
u32 maxu0 (u32 a, u32 b) {
  return a<b ? b:a;
}


: 



u32 minu1 (u32 a, u32 b) {
  u32 d = a-b;
  return a - (d&~(int((~a&b)|(~(a^b)&d)) >> SHIFT));
}
u32 maxu1 (u32 a, u32 b) {
  u32 d = a-b;
  return b + (d&~(int((~a&b)|(~(a^b)&d)) >> SHIFT));
}


: 3,5 , 9,5 2 6 .





, . (GitHub) ( meduzik ivas, — . , — ). . , , , . , .



, STDOUT ( ) 

sign: 2.87 vs 3.97
 abs: 2.29 vs 2.33
mini: 3.46 vs 8.93
maxi: 3.45 vs 9.10
minu: 3.45 vs 9.46
maxu: 3.45 vs 9.81


IF, – . STDERR , , .



: 

sign: 13.02 vs 1.26
 abs: 12.01 vs 0.81
mini: 1.89 vs 5.97
maxi: 1.93 vs 6.31
minu: 1.89 vs 6.44
maxu: 1.92 vs 6.70


: ( , ) , . , .



, , , .

  1. . , std::chrono. , , - ++. , Visual C++ 2015 GCC 4.8.1 ( MinGW) OS Windows 7 (64). 32- . SO, , .
  2. — .
  3. , . . chrono . runexe, , .


, , .





  1. Hacker's Delight
  2. Bit Twiddling Hacks
  3. Optimized abs function
  4. sign(x) —
  5. abs(x) —
  6. min(a,b) max(a,b)
  7. min(a,b) max(a,b)






meduzik ivas, , , .


More articles:


All Articles