Скажем, нам нужно сгенерировать \(n\) объектов двух типов.
def f(n):
zeros = 0
ones = 0
for i in range(n):
value = random.randint(0, 1)
if value == 0:
zeros += 1
else:
ones += 1
return zeros, ones
При \(n = 144 \cdot 10^6\) такая программа выполняется за 2,17 с.
1. Наивная версия на C++ выполняется за 1,47 с.
size_t zeros{}, ones{};
for (size_t i{}; i < n; ++i)
{
++(distribution(range) % 2 == 0 ? zeros : ones);
}
distribution(range) — это вызов нового генератора случайных чисел (C++17).
2. \(n\) вызовов генератора случайных чисел — это слишком много. Можно создать 64 объекта из одного случайного числа (если sizeof(type) == 64). Битовая маска последовательно смещается и поразрядно умножается на это число. Результат будет либо равен, либо не равен нулю.
value 1010110100110110111011010011000000000101010011001101001101101
mask 0000000000000000000000000000000000000000000000000000000000001
& 0000000000000000000000000000000000000000000000000000000000001 ≠ 0
value 1010110100110110111011010011000000000101010011001101001101101
mask 0000000000000000000000000000000000000000000000000000000000010
& 0000000000000000000000000000000000000000000000000000000000000 = 0
value 1010110100110110111011010011000000000101010011001101001101101
mask 0000000000000000000000000000000000000000000000000000000000100
& 0000000000000000000000000000000000000000000000000000000000100 ≠ 0
.............................................................
value 1010110100110110111011010011000000000101010011001101001101101
mask 1000000000000000000000000000000000000000000000000000000000000
& 1000000000000000000000000000000000000000000000000000000000000 ≠ 0
Таким образом, \(n\) разбивается на части (chunks) максимум по 64 элемента. Число \(n\) не обязано быть кратным разрядности случайного числа. Из-за этого приходится подсчитывать каждый разряд (++counter).
constexpr size_t bitsPerChunk{ sizeof(type) * 8u };
size_t zeros{}, ones{};
size_t counter{};
for (size_t i{}, chunks{ (n + bitsPerChunk - 1) / bitsPerChunk }; i < chunks; ++i)
{
const auto value{ distribution(range) };
type mask{ 1u };
for (size_t j{}; j < bitsPerChunk && counter < n; ++j)
{
++(value & mask ? zeros : ones);
mask <<= 1u;
++counter;
}
}
Такой код выполняется за 0,2 с.
3. Проблема предыдущей версии — лишний инкремент счётчика и сравнение с ним. Для каждой части можно рассчитать, будут там все 64 бита или не все (что может случиться с последней частью).
constexpr size_t bitsPerChunk{ sizeof(type) * 8u };
size_t zeros{}, ones{};
for (size_t i{}, chunks{ (n + bitsPerChunk - 1) / bitsPerChunk }; i < chunks; ++i)
{
const auto value{ distribution(range) };
type mask{ 1u };
const size_t bits{ i == chunks - 1 ? n - i * bitsPerChunk : bitsPerChunk };
for (size_t j{}; j < bits; ++j)
{
++(value & mask ? zeros : ones);
mask <<= 1u;
}
}
Теперь время выполнения — 0,186 с. Но выделенный фрагмент требует много процессорных инструкций, что видно ниже (GCC 11.2, x86-64).
mov rax, QWORD PTR [rbp-40]
sub rax, 1 ; chunks - 1
cmp QWORD PTR [rbp-8], rax ; i == chunks - 1?
jne .L21
mov rax, QWORD PTR [rbp-8]
sal rax, 6 ; i <<= 6 i.e. i *= 64 (bitsPerChunk)
mov rdx, rax
mov rax, QWORD PTR [rbp-112]
sub rax, rdx ; n - i * bitsPerChunk
jmp .L22
.L21:
mov eax, 64 ; bitsPerChunk
.L22:
mov QWORD PTR [rbp-56], rax ; bits = ...
4. Можно развернуть ситуацию: сначала посчитать, сколько разрядов в потенциально неполной части. Например, если \(n = 232\), то это три части по 64 бита и одна из 40. Станем обрабатывать эту часть первой.
size_t zeros{}, ones{};
const auto chunks{ (n + bitsPerChunk - 1) / bitsPerChunk };
size_t bits{ n - (chunks - 1) * bitsPerChunk };
for (size_t i{}; i < chunks; ++i)
{
const auto value{ distribution(range) };
type mask{ 1u };
for (size_t j{}; j < bits; ++j)
{
++(value & mask ? zeros : ones);
mask <<= 1u;
}
bits = bitsPerChunk;
}
Теперь в цикле оказывается одно «лишнее» выражение (поскольку его нужно выполнить только один раз), но ему соответствует лишь она процессорная инструкция.
mov QWORD PTR [rbp-8], 64 ; bits = bitsPerChunk
Этот код выполняется за 0,166 с. На генерацию одного объекта уходило примерно 15,07 нс, теперь — 1,14 нс.