Я искал подробное объяснение значения описания "Возвращаемое значение" для std::reduce, которое согласно cppreference.com:
Возможно, после того, как я смогу правильно понять идею раздела "Возвращаемое значение", я могу лучше определить, где я должен выбрать std::reduce over std::accumulate.
Поскольку вы попросили подробное объяснение, и предыдущий ответ охватывает только основы, я беру на себя смелость добавить более тщательный.
std::reduce предназначен для выполнения второго крупного шага модели программирования MapReduce. Основная идея заключается в том, что платформа (в данном случае реализация С++) обеспечивает эти две примитивные операции и уменьшает карту, а программист обеспечивает операции обратного вызова для каждого из двух, которые выполняют "фактическую работу".
В принципе, обратный вызов для операции карты отображает входное значение в промежуточное значение. Обратный вызов для сокращения объединяет два промежуточных значения в одно промежуточное значение. Последнее промежуточное значение слева становится результатом всего MapReduce. Это, по-видимому, очень ограничительная модель сама по себе, но все же она имеет большой диапазон приложений.
Платформа должна, конечно, делать больше, например, "перетасовка" (распределение входов, обычно в группах, на разные процессоры) и планирование, но это не имеет особого отношения к программисту приложений.
Кстати, в стандартной библиотеке С++ операция "map" называется transform. Он получил поддержку parallelism в С++ 17, но позже я войду в parallelism.
Здесь приведенный пример: пусть говорят, что у нас есть функция, которая преобразует целое число в строковое представление. Теперь, учитывая список целых чисел, мы хотим, чтобы текстовое представление содержало наибольшее соотношение согласных к вокалу. Например.
(Попробуйте сами, если вы не верите этому результату.)
Мы могли бы использовать MapReduce здесь, используя нашу функцию int-to-text в качестве обратного вызова к карте (rsp. std::transform) и функцию, которая подсчитывает количество согласных и вокалов, а затем выбирает либо левую, либо правую соответственно. Здесь есть некоторая неэффективность, в частности, "отношение" должно быть кэшировано, но это детали.
Теперь ваш вопрос может и, возможно, должен быть: Почему я должен заботиться? В конце концов, до сих пор вы мало выиграли от использования, например, std::transform и std::reduce таким образом, и вы могли бы использовать std::accumulate вместо последнего. Ответ, конечно, при достаточно большом количестве входных значений, - это политики выполнения - у предыдущих двух стандартных шаблонов функций есть перегрузки, которые допускают неявный parallelism. Но это все еще вызывает вопрос, почему можно использовать MapReduce, а не пул потоков или std::async, и кучу ручных петель? Во-первых, особенно для "чистых" вычислений на больших векторах или других контейнерах без ввода-вывода, часто бывает удобнее писать два обратных вызова MapReduce, потому что вам не нужно иметь дело со всеми подробностями о том, как входные данные распространяются на разные потоки, а затем объединены.
Во-вторых, MapReduce поощряет дисциплину структурирования ваших вычислений таким образом, что можно эффективно распараллелить. Конечно, на языке программирования, который поддерживает настоятельную парадигму, такую как С++, вы все равно можете испортить вещи, заблокировав кучу мьютексов или каким бы то ни было способом вмешательства в другие потоки. Но парадигма MapReduce побуждает писать независимые обратные вызовы отображения. Как простое правило, если эти задачи совместно используют данные, тогда он должен быть доступен только для чтения, поэтому его копии могут храниться в нескольких кэшах процессора одновременно. Хорошо написанные задачи в сочетании с эффективной платформенной реализацией основных алгоритмов могут масштабироваться до сотен или даже тысяч ядер процессора, как показывают платформы MapReduce, которые уже широко используются (например, Apache Hadoop, но принимают это только как необходимое пример, а не как безвозмездная реклама).
Но вопрос в основном касался std::reduce - мы могли бы выполнить это высокомасштабируемое отображение, а затем запустить std::accumulate на промежуточных результатах, правильно? И здесь мы добираемся до того, что ранее писал Франсуа Андри. accumulate выполняет то, что математики называют левой складкой. Если вы просмотрите операции и их операнды как двоичное дерево, тогда это будет левое дерево, например. добавить 1, 2, 3 и 4:
+
/ \
+ 4
/ \
+ 3
/ \
1 2
Как вы можете видеть, результат каждой операции является одним из аргументов следующей операции. Это означает, что существует линейная цепочка зависимостей данных, и это провал всех parallelism. Чтобы добавить миллион номеров, вам понадобится миллион последовательных операций, которые блокируют одно ядро, и вы не сможете использовать дополнительные ядра. Им больше нечего будет делать, и коммуникационные издержки значительно перевесят стоимость вычислений. (На самом деле это хуже, потому что современные процессоры могут выполнять несколько простых вычислений за такт, но это не работает, когда существует так много зависимостей данных, поэтому большая часть ALU или FPU не используются.)
Поднимая ограничение на использование левой складки, std::reduce позволяет платформе более эффективно использовать вычислительные ресурсы. Даже если вы используете однопоточную перегрузку, платформа может, например, использовать SIMD, чтобы добавить миллион целых чисел на сумму менее миллиона операций, а количество зависимостей данных будет значительно уменьшено. 10-кратное ускорение на хорошо написанном уменьшении целого числа не удивит меня. Конечно, этот особый случай, вероятно, может быть оптимизирован в соответствии с правилом as-if, поскольку реализация С++ "знает", что целочисленное добавление (почти, см. Ниже) ассоциативно.
Но сокращение идет дальше, чем указано, поддерживая политики выполнения, т.е. в большинстве случаев многоядерные parallelism. Теоретически можно использовать сбалансированное двоичное дерево операций. (Помните, что дерево сбалансировано, если глубина либо меньше двух, либо глубина левого поддерева отличается от глубины правого поддерева не более чем на 1.) Такое дерево имеет только логарифмическую глубину. Если у нас есть миллион целых чисел, минимальная глубина дерева равна 20, поэтому - теоретически - при наличии достаточного количества ядер и отсутствующих коммуникационных издержек мы могли бы добиться ускорения на 50 000 долларов даже по оптимизированному однопоточному вычислению. Конечно, на практике это нагрузка желаемого за действительное, но мы все еще можем ожидать больших ускорений.
Все, что сказал, позвольте мне добавить быстрый отказ от ответственности/напоминание о том, что производительность не такая же, как эффективность. Использование 64 ядер на 100 мс каждый означает гораздо более высокую производительность, чем использование одного ядра на 1000 мс, но гораздо меньше эффективности процессора. Другой способ сказать, что производительность - это эффективность в смысле минимизации прошедшего времени, но есть и другие меры эффективности - общее время работы центрального процессора, используемая ОЗУ, используемая энергия и т.д. Первичная мотивация параллельного MapReduce заключается в обеспечении более высокой производительности. Является ли это сокращением времени процессора или потребления энергии, неясно, и это, скорее всего, увеличит пиковое использование ОЗУ.
В довершение ко всему, вот некоторые предостережения. Как уже упоминалось, reduce не является детерминированным, если операции не являются ассоциативными или не коммутативными. К счастью, наиболее важные арифметические операции, такие как сложение и умножение, являются ассоциативными и коммутативными, правильно? Мы все знаем, что, например, добавление целых чисел и с плавающей запятой имеет оба этих свойства. И, конечно же, я преуспеваю. В С++ ни подписанное целочисленное сложение, ни добавление с плавающей запятой не являются ассоциативными. Для чисел с плавающей запятой это связано с возможными различиями в округлении промежуточных результатов. Это легко визуализируется, если мы, например, выберем простой десятичный формат с плавающей запятой с двумя значащими цифрами и рассмотрим сумму 10 + 0,4 + 0,4. Если это выполняется стандартными правилами синтаксиса С++ как левое сложение, мы получаем (10 + 0,4) + 0,4 = 10 + 0,4 = 10, потому что каждый раз, когда результат округляется до 10, но если мы делаем это как 10 + (0,4 + 0,4), первый промежуточный результат равен 0,8, а затем 10 + 0,8 округляется до 11. Кроме того, ошибки округления могут значительно увеличиваться на большой глубине дерева операций, поэтому левая свая на самом деле одна из худших вещей, которые можно было бы сделать, когда дело доходило до точности. Существует несколько способов борьбы с этим поведением: от сортировки и группировки входов до использования увеличенной промежуточной точности, но когда дело доходит до reduce, не может быть никакого способа получить 100% -ную согласованность выполнения для запуска.
Другое, возможно, более удивительное, наблюдение заключается в том, что целое число со знаком не является ассоциативным в С++. Причиной этого является возможность переполнения, прямо говоря: (-1) + 1 + INT_MAX. В соответствии с обычными правилами синтаксиса или accumulate результат равен INT_MAX. Но если вы используете reduce, это может быть переписано как (-1) + (1 + INT_MAX), которое содержит целочисленное переполнение и, следовательно, поведение undefined. На самом деле, поскольку reduce может произвольно изменять порядок операндов, это даже верно, если входы { INT_MAX, -1, 1 }.
Моя рекомендация здесь заключается в том, чтобы обратный вызов reduce не мог вызвать переполнение. Это может быть сделано путем ограничения допустимого диапазона входов (например, если вы добавляете 1000 int s, убедитесь, что ни одна из них не больше INT_MAX / 1000 или меньше INT_MIN / 1000, округленная), например, или, эквивалентно, используя более крупный целочисленный тип или, как абсолютное последнее средство (потому что это дорого и сложно обрабатывать правильно), добавив дополнительные проверки в обратный вызов reduce. В большинстве практических случаев reduce является лишь менее безопасным в отношении переполнения целых чисел, чем accumulate.
std::accumulate итерации по контейнеру, где std:reduce, возможно, нет. Поскольку заказ не гарантируется, std::reduce вводит дополнительные требования:
Поведение недетерминировано, если binary_op не ассоциативно или не является коммутативным. Поведение undefined, если binary_op изменяет любой элемент или делает недействительным любой итератор в [first; last], включая конечный итератор.
Однако std::reduce предоставляет перегрузки, которые поддерживают распараллеливание, недоступные с std::accumulate. std::reduce позволяет автоматически распараллеливать вашу работу при условии, что она соответствует указанным выше требованиям.