Dyzzet|
C++ Data Science Алгоритмы Темы · Блог · YouTube
Оптимизация цикла

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

17 января 2022
C++ misc
Зарегистрируйтесь и войдите, чтобы оставлять комментарии и голосовать.

Также может быть интересным
© MMXI—MMXXIII. RSS. Поддержать сайт
Светлая тема / тёмная тема