Установка / очистка битов: битовое смещение или поиск битовой маски?
Я работаю над шахматным движком на основе битборта, и одно из действий, выполненных щедро, — установка / очистка битов в 64-битном целом без знака. Так как я не очень хорошо разбираюсь в том, какой код будет работать «быстрее» на определенных процессорах, я не могу полностью обдумать это.
Установка и очистка битов — довольно простая операция, но я должен использовать (для установки):
uint64_t bitboard |= 1ULL << index;
или же:
uint64_t bitboard |= BITMASK[index];
где BITMASK[] некоторый предварительно вычисленный массив целых чисел, где ровно один бит (в index) установлено.
На первый взгляд, сдвиг битов кажется очевидным более быстрым выбором, поскольку сдвиг битов всегда будет быстрее, чем поиск в памяти.
Но в контексте шахматного движка, где эта операция, вероятно, будет выполняться в изобилии, имеет смысл сохранить таблицу поиска в кеше процессора, что, возможно, ускорит использование таблицы поиска. Или это будет?
Кроме того, это даже имеет значение?
Может быть, глупое соображение, но это не больно знать.
Решение
Метод сдвига должен быть быстрее по сравнению с поиском в таблице, поскольку он избегает дополнительной ссылки на память. Но для образовательных целей было бы интересно оценить.
Другие решения
Я быстро запустил эту (очень грубую, простите) функцию:
#include <iostream>
#include <random> // std::mt19937()
typedef unsigned long long uint64;
uint64 SET_BITMASK[64];
void init_bitmask()
{
for(int i = 0; i < 64; i++) SET_BITMASK[i] = 1ULL << i;
}
int main()
{
std::mt19937 gen_rand(42);
uint64 bb = 0ULL;
double avg1, avg2;
init_bitmask();
for(unsigned int i = 0; i < 10; i++)
{
std::clock_t begin = std::clock();
for(unsigned int j = 0; j < 99999999; j++)
{
bb |= 1ULL << (gen_rand() % 64);
}
std::clock_t end = std::clock();
std::cout << "For bitshifts, it took: " << (double) (end - begin) / CLOCKS_PER_SEC << "s." << std::endl;
avg1 += (double) (end - begin) / CLOCKS_PER_SEC;
bb = 0ULL;
begin = std::clock();
for(unsigned int j = 0; j < 99999999; j++)
{
bb |= SET_BITMASK[gen_rand() % 64];
}
end = std::clock();
std::cout << "For lookups, it took: " << (double) (end - begin) / CLOCKS_PER_SEC << "s." << std::endl << std::endl;
avg2 += (double) (end - begin) / CLOCKS_PER_SEC;
}
std::cout << std::endl << std::endl << std::endl;
std::cout << "For bitshifts, the average is: " << avg1 / 10 << "s." << std::endl;
std::cout << "For lookups, the average is: " << avg2 / 10 << "s." << std::endl;
std::cout << "Lookups are faster by " << (((avg1 / 10) - (avg2 / 10)) / (avg2 / 10))*100 << "%." << std::endl;
}
В среднем десять более ста миллионов наборов битов для каждой итерации 1.61603s для сдвигов и 1.57592s для поиска последовательно (даже для различных начальных значений).
Столы поиска удивительно кажутся последовательно быстрее примерно 2.5% (в данном конкретном случае использования).
Замечания: Я использовал случайные числа, чтобы предотвратить любые несоответствия, как показано ниже.
Если я использую i % 64 сдвиг / индексирование, сдвиг битов быстрее примерно на 6%,
Если я использую константу для сдвига / индексации, результат варьируется примерно на 8%, от -4% до 4%, что наводит меня на мысль, что в игру вступают какие-то забавные предположения. Либо так, либо они в среднем до 0%;)
Я не могу сделать вывод, поскольку это, конечно, не реальный сценарий, поскольку даже в шахматном движке эти наборы битов не будут следовать друг за другом в быстрой последовательности. Все, что я могу сказать, это то, что разница, вероятно, незначительна. Я также могу добавить, что таблицы поиска несовместимы, так как вы зависите от того, были ли таблицы кэшированы. Я лично собираюсь использовать битовые сдвиги в моем движке.
detector