Плохая производительность векторного <bool> в 64-битной цели с VS2012

Ответ 1

Я тестировал это с помощью vector<bool> в VS2010: для 32-разрядных запросов требуется 1452 мс, тогда как для 64-разрядных бит требуется 1264 мс для i3.

Тот же тест в VS2012 (на i7 на этот раз) требует 700 мс (32-бит) и 2730 мс (64-разрядный), поэтому в компиляторе VS2012 есть что-то не так. Возможно, вы можете сообщить об этом в качестве ошибки в Microsoft.

UPDATE

Проблема заключается в том, что компилятор VS2012 использует временную переменную стека для части кода во внутреннем for-loop при использовании int в качестве итератора. Компоненты сборки, перечисленные ниже, являются частью кода внутри <vector>, в += operator std::vector<bool>::iterator.

size_t как итератор

При использовании size_t в качестве итератора часть кода выглядит следующим образом:

or  rax, -1
sub rax, rdx
shr rax, 5
lea rax, QWORD PTR [rax*4+4]
sub r8, rax

Здесь все инструкции используют очень быстрые регистры CPU.

int как итератор

При использовании int в качестве итератора эта же часть выглядит следующим образом:

or  rcx, -1
sub rcx, r8
shr rcx, 5
shl rcx, 2
mov rax, -4
sub rax, rcx
mov rdx, QWORD PTR _Tmp$6[rsp]
add rdx, rax

Здесь вы видите используемую переменную стека _Tmp $6, что приводит к замедлению.

Компилятор точки в нужном направлении

Самое смешное, что вы можете указать компилятор в правильном направлении, используя vector<bool>::iterator напрямую.

struct Sieve {
  std::vector<bool> isPrime;

  Sieve (int n = 1) {
    isPrime.assign(n + 1, true);

    std::vector<bool>::iterator it1 = isPrime.begin();
    std::vector<bool>::iterator end = it1 + n;
    *it1++ = false;
    *it1++ = false;
    for (int i = 2; i <= (int)sqrt((double)n); ++it1, ++i)
        if (*it1)
            for (std::vector<bool>::iterator it2 = isPrime.begin() + i * i; it2 <= end; it2 += i)
                *it2 = false;
  }
};

Ответ 2

std::vector<bool> здесь не является прямой ошибкой. Разница в производительности в конечном итоге обусловлена ​​использованием 32-битного типа int в ваших циклах и некоторым довольно низким распределением регистров компилятором. Рассмотрим, например, ваш самый внутренний цикл:

for (int j = i*i; j <= n; j += i)
    isPrime[j] = false;

Здесь j - это 32-разрядное целое число со знаком. Однако, когда он используется в isPrime[j], его необходимо продвигать (и расширять с помощью знака) до 64-разрядного целого, чтобы выполнить вычисление индекса. Компилятор не может просто рассматривать j как 64-битное значение, потому что это изменит поведение цикла (например, если n является отрицательным). Компилятор также не может выполнить вычисление индекса, используя 32-разрядную величину j, поскольку это изменит поведение этого выражения (например, если j отрицательно).

Итак, компилятор должен сгенерировать код для цикла с использованием 32-разрядного j, тогда он должен сгенерировать код для преобразования этого j в 64-разрядное целое для вычисления индекса. Он должен сделать то же самое для внешнего цикла с помощью i. К сожалению, похоже, что компилятор довольно плохо выделяет регистры в этом случае ^(*) - он начинает проливать временные ряды в стек, что приводит к тому, что производительность становится видимой.

Если вы измените свою программу на использование size_t всюду (это 32-разрядная версия на x86 и 64-разрядной версии на x64), вы увидите, что производительность на одном уровне с x86, потому что сгенерированный код должен работать только с значения одного размера:

Sieve (size_t n = 1)
{
    isPrime.assign (n+1, true);
    isPrime[0] = isPrime[1] = false;

    for (size_t i = 2; i <= static_cast<size_t>(sqrt((double)n)); ++i)
        if (isPrime[i]) 
            for (size_t j = i*i; j <= n; j += i)
                isPrime[j] = false;
}

Вы все равно должны это делать, потому что смешивание подписанных и неподписанных типов, особенно когда эти типы имеют разную ширину, опасно и может привести к непредвиденным ошибкам.

Обратите внимание, что использование std::vector<char> также "решает" проблему, но по другой причине: вычисление подстроек, необходимое для доступа к элементу a std::vector<char>, существенно проще, чем для доступа к элементу std::vector<bool>. Оптимизатор способен генерировать лучший код для более простых вычислений.

(*) Я не работаю над генерацией кода, и я вряд ли являюсь экспертом в сборе или оптимизации производительности на низком уровне, но, глядя на сгенерированный код, и учитывая, что здесь сообщается, что Visual С++ 2010 генерирует лучший код, я бы предположил, что есть возможности для улучшения в компиляторе. Я убеждаюсь, что обнаруженная вами ошибка подключения передается команде компилятора, чтобы они могли взглянуть.

Ответ 3

vector<bool> - очень специальный контейнер, который специализируется на использовании 1 бит на элемент, а не на стандартную семантику контейнера. Я подозреваю, что логика манипуляции бит намного дороже при компиляции 64 бит (либо она по-прежнему использует 32-битные фрагменты для хранения бит, либо по какой-либо другой причине). vector<char> ведет себя как обычный vector, поэтому нет специальной логики.

Вы также можете использовать deque<bool>, который не имеет специализации.