Разница в производительности: STD :: накопить против STD :: inner_product против цикла

Question

Сегодня я хочу поделиться тем, что поражало меня, когда я пытался реализовать эту простую операцию:

Я нашел разные способы выполнить одну и ту же операцию:

1. Используя std::inner_product.
2. Реализация предиката и использование функции std::accumulate.
3. Использование цикла в стиле C.

Я хотел выполнить какой-то тест, используя Quick Bench и включив все оптимизации.

Прежде всего, я сравнил две альтернативы C ++ с плавающими значениями. Этот код используется с помощью std::accumulate:

const auto predicate = [](const double previous, const double current) {
    return previous + current * current;
};
const auto result = std::accumulate(input.cbegin(), input.cend(), 0, predicate);

По сравнению с этим кодом с использованием функции std::inner_product:

const auto result = std::inner_product(input.cbegin(), input.cend(), input.cbegin(), 1);

После запуска теста с включенной оптимизацией я получил такой результат:

Оба алгоритма, похоже, достигают одинаковой производительности. Я хотел пойти дальше и попробовать реализацию C:

double result = 0;
for (auto i = 0; i < input.size(); ++i) {
  result += input[i] * input[i];
}

И удивительно, я нашел:

Я не ожидал этого результата. Я был уверен, что что-то не так, поэтому я проверил реализацию GCC:

template<typename _InputIterator1, typename _InputIterator2, typename _Tp>
inline _Tp
inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
      _InputIterator2 __first2, _Tp __init)
{
  // concept requirements
  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
  __glibcxx_requires_valid_range(__first1, __last1);

  for (; __first1 != __last1; ++__first1, (void)++__first2)
__init = __init + (*__first1 * *__first2);
  return __init;
}

Я обнаружил, что он делает то же самое, что и реализация C. Изучив реализацию, я обнаружил нечто странное (или, по крайней мере, я не ожидал, что это окажет такое значительное влияние): во всех внутренних накоплениях он выполнял приведение типа итератора value_type к типу начального значения.

В моем случае я инициализировал начальные значения равными 0 или 1, значения считались целыми числами, и в каждом накоплении компилятор выполнял приведение. В различных тестовых примерах мой входной массив хранит усеченные плавающие точки, поэтому результат не изменился.

После обновления начального значения двойным типом:

const auto result = std::accumulate(input.cbegin(), input.cend(), 0.0, predicate);

И

const auto result = std::inner_product(input.cbegin(), input.cend(), input.cbegin(), 0.0);

Я получил ожидаемый результат:

Теперь я понимаю, что оставление начального значения независимым типом от базового типа итератора может сделать функцию более гибкой и позволить делать больше вещей. Но,

Если я накапливаю элементы массива, я ожидаю получить тот же тип в результате. То же самое для внутреннего продукта.

Должно ли это быть поведение по умолчанию?

Почему стандарт решил выполнить его таким образом?

Answer 1

Если я накапливаю элементы массива, я ожидаю получить такой же тип в результате.

Ваше ожидание неверно (хотя не совсем понятно, что означает «тот же тип, что и результат»), как вы можете ясно увидеть из std :: аккумулировать документацию:

template< class InputIt, class T >
T accumulate( InputIt first, InputIt last, T init );

template< class InputIt, class T, class BinaryOperation >
T accumulate( InputIt first, InputIt last, T init,
              BinaryOperation op );

тип возвращаемого значения точно такой же, какой вы используете для начального значения. Тот же эффект, который вы можете иметь в цикле:

auto result = 0; // vs auto result = 0.0;
for (auto i = 0; i < input.size(); ++i) {
  result += input[i] * input[i];
}

Почему стандарт решил выполнить его таким образом?

Потому что таким образом вы можете решить, какой тип вы используете для агрегирования. Примечание std::accumulate можно использовать для левого сгиба и случаев, когда T не равен std::iterator_traits<InputIt>::value_type не реже (возможно, даже больше), чем когда они совпадают.