Скажем, нам нужно сгенерировать \(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 нс.