Почему std :: lower нуждается в коммутативности? - PullRequest
Новая
       8

Почему std :: lower нуждается в коммутативности?

6 голосов
/ 13 февраля 2020

https://en.cppreference.com/w/cpp/algorithm/reduce

Это говорит о том, что поведение операции не определено, если операция не является коммутативной, но почему? Мы просто делим массив на блоки и затем объединяем результат. Нужно ли иметь ассоциативность?

Ответы [ 3 ]

7 голосов
/ 14 февраля 2020

std::reduce требует как ассоциативности, так и коммутативности. Ассоциативность явно необходима для параллельного алгоритма, так как вы хотите выполнить вычисления для отдельных кусков и затем объединить их.

Что касается коммутативности: Согласно сообщение Reddit от MSV C Разработчик STL Билли О'Нил, это необходимо для того, чтобы разрешить векторизацию для инструкций SIMD:

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

vecRegister = load_contiguous(first);
while (a vector register sized chunk is left) {
    first += packSize;
    vecRegister = add_packed(load_contiguous(first), vecRegister);
}
// combine vecRegister's packed components

et c., Который дает целые числа и регистры SSE, а a * b * c * d * e * f * g * h дает что-то вроде (a * e) * (b * f) * (c * g) * (d * h).

Большинство других языков не делают явных вещей, чтобы сделать векторизацию своего сокращения возможной. И ничто не говорит о том, что мы не сможем добавить некоммутативное_редуцирование или что-то подобное в будущем, если кто-то придумает убедительный вариант использования.

2 голосов
/ 14 февраля 2020

Поведение фактически недетерминировано c, если операция между операндами не является коммутативной. «недетерминированный c» - это не то же самое, что «неопределенный». Например, математика с плавающей точкой не коммутативна. Это одна из причин, почему вызов std::reduce может не быть детерминированным c, потому что двоичная функция применяется в неопределенном порядке.

См. это примечание в стандарте:

Примечание. Разница между reduce и accumulate заключается в том, что сокращение применяется binary_op в неопределенном порядке, что дает недетерминированный c результат для неассоциативного или некоммутативного binary_op такие как сложение с плавающей точкой. —Конечная записка]

1 голос
/ 14 февраля 2020

Стандарт определяет обобщенную сумму следующим образом: цифра c .defns

Определить GENERALIZED_NONCOMMUTATIVE_SUM (op, a1, ..., aN) следующим образом:

  • a1, когда N равно 1, в противном случае

  • op (GENERALIZED_NONCOMMUTATIVE_SUM (op, a1, ..., aK), op (GENERALIZED_NONCOMMUTATIVE_SUM (op , aM, ..., aN)) для любого K, где 1

Определить GENERALIZED_SUM (op, a1, ..., aN) как GENERALIZED_NONCOMMUTATIVE_SUM (op, b1, ..., bN) где b1, ..., bN может быть любой перестановкой a1, ..., aN.

Итак, порядок суммирования, а также порядок операндов не указан. Так что если двоичная операция не является коммутативной или не ассоциативной, результат не уточняется.

Это также явно указано здесь .

Относительно того, почему: он дает поставщикам библиотек больше свободы, поэтому они могут или не могут реализовать его лучше. В качестве примера, где реализация может извлечь выгоду из коммутативности. Рассмотрим сумму a+b+c+d+e, сначала мы вычисляем a+b и c+d параллельно. Теперь a+b возвращается раньше, чем c+d (как это может случиться, потому что это делается параллельно). Вместо ожидания возвращаемого значения c+d теперь мы можем напрямую вычислить (a+b)+e и затем добавить этот результат к результату c+d. Итак, в итоге мы вычислили ((a+b)+e)+(c+d), что представляет собой перестановку a+b+c+d+e.

...