А как насчет этой ревизии?
int total = 0;
for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++){
total += (mask & 0x0001) * value[j];
}
Я превратил mask в копию i, ограниченную 16-разрядным диапазоном без знака, но код проверяет, установлен ли последний бит маски, умножая значение массива на этот бит. Это должно быть быстрее просто потому, что на одну итерацию приходится меньше операций, и нужны только ветви и условия основного цикла. Кроме того, цикл может завершиться рано, если i мал для начала.
Это показывает, почему измерения важны. Я использую устаревший Sun SPARC. Я написал тестовую программу, как показано, с двумя претендентами из вопроса в качестве теста 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)));
}
}
Я не потратил время на выяснение, почему мой код медленнее при оптимизации.