このリビジョンはどうですか?
int total = 0;
for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++){
total += (mask & 0x0001) * value[j];
}
16 ビットの符号なし範囲に制限さmask
れたコピーを作成しましたが、コードはマスクの最後のビットが設定されているかどうかをチェックし、配列の値にそのビットを掛けます。i
反復ごとの操作が少なく、メイン ループの分岐と条件のみが必要なため、これは単純に高速になるはずです。i
また、最初からが小さい場合、ループは早期に終了する可能性があります。
これは、測定が重要である理由を示しています。古い Sun SPARC を使用しています。質問の 2 つの候補をテスト 0 とテスト 1 として、私自身の回答をテスト 2 として、示されているようにテスト プログラムを作成しました。次に、タイミング テストを実行しました。「合計」はサニティ チェックとして出力されます。これは、アルゴリズムがすべて同じ答えを出すことを保証するためです。
最適化されていない 64 ビット:
gcc -m64 -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib/sparcv9 -ljl -lposix4
Test 0: (sum = 1744366) 7.973411 us
Test 1: (sum = 1744366) 10.269095 us
Test 2: (sum = 1744366) 7.475852 us
ナイス: 私のは元のバージョンよりもわずかに高速で、強化されたバージョンは低速です。
最適化された 64 ビット:
gcc -O4 -m64 -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib/sparcv9 -ljl -lposix4
Test 0: (sum = 1744366) 1.101703 us
Test 1: (sum = 1744366) 1.915972 us
Test 2: (sum = 1744366) 2.575318 us
ダーン - 私のバージョンは劇的に遅くなりました。オプティマイザは良いです!
32 ビットに最適化:
gcc -O4 -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib -ljl -lposix4
Test 0: (sum = 1744366) 0.839278 us
Test 1: (sum = 1744366) 1.905009 us
Test 2: (sum = 1744366) 2.448998 us
最適化されていない 32 ビット:
gcc -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib -ljl -lposix4
Test 0: (sum = 1744366) 7.493672 us
Test 1: (sum = 1744366) 9.610240 us
Test 2: (sum = 1744366) 6.838929 us
(32ビット)Cygwinとそれほど古くないラップトップ(32ビット、最適化)で同じコード
Test 0: (sum = 1744366) 0.557000 us
Test 1: (sum = 1744366) 0.553000 us
Test 2: (sum = 1744366) 0.403000 us
今、私のコードは最速です。だからこそ測る!また、生計を立てるためにベンチマークを実行している人々が取り乱す理由も示しています。
timer.h
テスト ハーネス (およびtimer.c
コードが必要な場合は叫ぶ):
#include <stdio.h>
#include "timer.h"
static volatile int value[] =
{
12, 36, 79, 21, 31, 93, 24, 15,
56, 63, 20, 47, 62, 88, 9, 36,
};
static int test_1(int i)
{
int total = 0;
for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++)
{
if (i & mask)
total += value[j];
}
return(total);
}
static int test_2(int i)
{
int total = 0;
for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++)
{
total += ((i & mask) != 0) * value[j];
}
return(total);
}
static int test_3(int i)
{
int total = 0;
for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++)
{
total += (mask & 0x0001) * value[j];
}
return(total);
}
typedef int(*func_pointer)(int);
static func_pointer test[] = { test_1, test_2, test_3 };
#define DIM(x)(sizeof(x)/sizeof(*(x)))
int main()
{
int i, j, k;
char buffer[32];
for (i = 0; i < DIM(test); i++)
{
Clock t;
long sum = 0;
clk_init(&t);
clk_start(&t);
for (j = 0; j < 0xFFFF; j += 13)
{
int rv;
for (k = 0; k < 1000; k++)
rv = (*test[i])(j);
sum += rv;
}
clk_stop(&t);
printf("Test %d: (sum = %ld) %9s us\n", i, sum,
clk_elapsed_us(&t, buffer, sizeof(buffer)));
}
}
最適化するとコードが遅くなる理由を解明するのに時間を費やしていません。