Это один из тех вопросов, который помогает узнать вашу микроархитектуру. Я просто рассчитал два варианта в gcc 4.3.3, скомпилированных с -O3, используя встроенные в C ++ значения, чтобы исключить накладные расходы на вызовы функций, один миллиард итераций, сохраняя текущую сумму всех подсчетов, чтобы компилятор не удалил ничего важного, используя rdtsc для синхронизации ( тактовый цикл точный).
inline int pop2(unsigned x, unsigned y)
{
x = x - ((x >> 1) & 0x55555555);
y = y - ((y >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
y = (y & 0x33333333) + ((y >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
y = (y + (y >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
y = y + (y >> 8);
x = x + (x >> 16);
y = y + (y >> 16);
return (x+y) & 0x000000FF;
}
Неизменный Восторг Хакера занял 12,2 гигациклов. Моя параллельная версия (считая вдвое больше битов) работает в 13,0 гигациклов. Всего 10,5 с прошло для обоих вместе на 2,4 ГГц Core Duo. 25 гигациклов = чуть более 10 секунд на этой тактовой частоте, поэтому я уверен, что мои настройки правильные.
Это связано с цепочками зависимостей команд, что очень плохо для этого алгоритма. Я мог бы почти удвоить скорость снова, используя пару 64-битных регистров. На самом деле, если бы я был умен и добавил х + у чуть раньше, я мог бы сбрить некоторые смены. 64-битная версия с некоторыми небольшими изменениями получилась бы ровной, но снова посчитала вдвое больше битов.
С 128-разрядными SIMD-регистрами, еще одним фактором, равным двум, и наборами инструкций SSE также часто имеют хитроумные сокращения.
Нет причин для того, чтобы код был особенно прозрачным. Интерфейс прост, на алгоритм можно ссылаться онлайн во многих местах, и он поддается всестороннему модульному тестированию. Программист, который натыкается на это, может даже чему-то научиться. Эти битовые операции чрезвычайно естественны на уровне машины.
ОК, я решил протестировать 64-битную версию. Для этого один размер (без знака long) == 8
inline int pop2(unsigned long x, unsigned long y)
{
x = x - ((x >> 1) & 0x5555555555555555);
y = y - ((y >> 1) & 0x5555555555555555);
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
y = (y & 0x3333333333333333) + ((y >> 2) & 0x3333333333333333);
x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
y = (y + (y >> 4)) & 0x0F0F0F0F0F0F0F0F;
x = x + y;
x = x + (x >> 8);
x = x + (x >> 16);
x = x + (x >> 32);
return x & 0xFF;
}
Это выглядит правильно (хотя я не тщательно проверяю). Теперь время выходит на 10,70 гигациклов / 14,1 гигациклов. Это более позднее число составило 128 миллиардов битов и соответствует 5,9 с, прошедшим на этой машине. Непараллельная версия немного ускоряется, потому что я работаю в 64-битном режиме, и ей нравятся 64-битные регистры немного лучше, чем 32-битные.
Давайте посмотрим, будет ли здесь больше конвейерной обработки OOO. Это было немного сложнее, так что я немного протестировал. Каждый термин в сумме равен 64, а все вместе - 256.
inline int pop4(unsigned long x, unsigned long y,
unsigned long u, unsigned long v)
{
enum { m1 = 0x5555555555555555,
m2 = 0x3333333333333333,
m3 = 0x0F0F0F0F0F0F0F0F,
m4 = 0x000000FF000000FF };
x = x - ((x >> 1) & m1);
y = y - ((y >> 1) & m1);
u = u - ((u >> 1) & m1);
v = v - ((v >> 1) & m1);
x = (x & m2) + ((x >> 2) & m2);
y = (y & m2) + ((y >> 2) & m2);
u = (u & m2) + ((u >> 2) & m2);
v = (v & m2) + ((v >> 2) & m2);
x = x + y;
u = u + v;
x = (x & m3) + ((x >> 4) & m3);
u = (u & m3) + ((u >> 4) & m3);
x = x + u;
x = x + (x >> 8);
x = x + (x >> 16);
x = x & m4;
x = x + (x >> 32);
return x & 0x000001FF;
}
Я был взволнован на мгновение, но оказалось, что gcc играет встроенные трюки с -O3, хотя я не использую ключевое слово inline в некоторых тестах. Когда я позволяю gcc играть трюки, миллиард вызовов pop4 () занимает 12,56 гигациклов, но я решил, что это сворачивание аргументов в виде константных выражений. Более реалистичное число кажется 19,6gc для еще 30% ускорения. Мой тестовый цикл теперь выглядит следующим образом, убедившись, что каждый аргумент достаточно различен, чтобы gcc не играл трюки.
hitime b4 = rdtsc();
for (unsigned long i = 10L * 1000*1000*1000; i < 11L * 1000*1000*1000; ++i)
sum += pop4 (i, i^1, ~i, i|1);
hitime e4 = rdtsc();
256 миллиардов битов за 8,17 секунды. Работает до 1,02 с для 32 миллионов битов, как это было указано в 16-битной таблице поиска. Невозможно сравнить напрямую, потому что другой стенд не дает тактовой частоты, но выглядит так, будто я выплюнул сопли из 64-килобайтного настольного издания, что, во-первых, трагическое использование кэша L1.
Обновление: решил сделать очевидное и создать pop6 (), добавив еще четыре дублированных строки. Вышел на 22,8gc, 384 миллиардов битов, суммированных за 9,5 с. Так что есть еще 20% сейчас при 800 мс для 32 млрд бит.