Monthly Archives: Ноябрь 2015

Сравнение скорости некоторых способов организации простейших циклов по std::vector

На написание данного поста меня сподвигла статья Есть ли практический смысл использовать для итераторов префиксный оператор инкремента ++it, вместо постфиксного it++. У меня появилось желание посмотреть поведение большего числа вариантов и на современном компиляторе — в моём случае это Microsoft Visual C++ 2015 (платформа: Windows 7 x64, компиляция под x64).

Методика тестирования: заполнение массива (vector) псевдослучайными числами на основе случайного зерна размером в 10 миллионов элементов типа double, замер времени выполнения каждого варианта с помощью стандартного high_resolution_clock (имеет микросекундную точность в MSVC2015). Повторы выполнялись вручную для оценки погрешности теста «на глаз», так как высокая точность здесь не требуется, а аномалии не ожидаются (и не были обнаружены). Полученная таким образом погрешность оказалась меньше 4%.

Результаты приведены в таблице ниже. Числа соответствуют debug-сборке, запущенной из Visual Studio под отладчиком. Запуск непосредственно exe-файла без отладчика демонстрирует увеличение скорости примерно на 5% — на грани погрешности. Числа получены делением времени работы debug-сборки на время работы release-сборки. Release-сборка демонстрирует одинаковое время работы для всех вариантов (в том числе, при запуске из-под Visual Studio и запуске непосредственно exe-файла).

Вариант Замедление к release
v1, it++ 1210
v2, ++it 610
v3, it != e; ++it 230
v4, for(:) 230
v5, accumulate 18
v6, items[i] 184
v7, p[i] 3

Ниже приведён исходный код всех вариантов.

Вариант 1. Постфиксный инкремент итератора.

  for (auto it = begin(items); it != end(items); it++)
    s += *it;

Вариант 2. Префиксный инкремент итератора (быстрее варианта 1 вдвое).

  for (auto it = begin(items); it != end(items); ++it)
    s += *it;

Вариант 3. Сохранение конца диапазона в переменную (быстрее варианта 2 втрое).

  for (auto it = begin(items), e = end(items); it != e; ++it)
    s += *it;

Вариант 4. Цикл for по диапазону (эквивалентен по скорости варианту 3).

  for (auto &&item : items)
    s += item;

Вариант 5. Стандартный алгоритм accumulate (быстрее вариантов 3 и 4 более, чем в 12 раз).

  return accumulate(begin(items), end(items), Item{ 0 });

Вариант 6. Целочисленный индекс вместо итератора (незначительно быстрее вариантов 3 и 4).

  for (size_t i = 0, sz = items.size(); i < sz; ++i)
    s += items[i];

Вариант 7. Целочисленный индекс, обращение по указателю (убирает проверки диапазона при отладке, в шесть раз быстрее варианта 5).

  const auto p = items.data();
  const auto sz = items.size();
  for (size_t i = 0; i < sz; ++i)
    s += p[i];

Код теста целиком.

Итак, влияние на скорость отладки может быть очень значительным.

На мой взгляд, разумно использовать вариант 4 во всех случаях, когда нет дополнительных обстоятельств. Сделать ошибку при использовании for(:) цикла сложнее всего. Варианты 1 и 2 использовать не следует никогда. Если вариант 5 подходит к конкретной ситуации (вроде рассмотренной здесь суммы), то, наверное, следует предпочесть его, хотя и не совсем ясно, почему он оказался быстрее варианта 4. Вариант 7 я использую при написании узких циклов на векторах: опыт показывает, что на таком коде оптимизирующий компилятор обычно способен достичь большего, чем на других вариантах (правда, на такой простой задаче как сумма, это не сказалось). Данный вариант является условно-опасным: в нём даже в отладочной сборке в цикле не выполняются проверки на выход за пределы диапазона (в отличие от варианта 6).

Алгоритм построения траектории при наличии фазовых ограничений II

Трубка внутри множества достижимости в обход препятствий

Трубка внутри множества достижимости в обход препятствий

Подчищенная и сокращённая версия (март 2015) предыдущего варианта.

Презентация (PDF)

К тому моменту я сделал тестовую реализацию алгоритма в двумерном пространстве (с визуализацией в 3D). К сожалению, запустить её на конференции не получилось, так как оказалось, что на Windows XP SP3 exe, скомпилированные Visual Studio 2013, не запускаются. На случай подобных проблем у меня, естественно, были заготовлены скриншоты:

Иллюстрации к слайдам 10–14

Иллюстрации к слайдам 20–22