entre - ¿Por qué se ha agregado std:: reduce en C++ 17?

diferencias entre c++ y c++ 11 (2)

Estaba buscando una explicación detallada del significado de la descripción del "Valor de retorno" para std::reduce , que según cppreference.com, es:

Tal vez después de que pueda percibir correctamente la idea detrás de la sección "Valor de retorno", puedo determinar mejor dónde debo elegir std::reduce over std::accumulate .

Como solicitó una explicación completa y la respuesta anterior cubre solo lo básico, me permito la libertad de agregar una más completa.

std::reduce está destinado a realizar el segundo paso importante del modelo de programación MapReduce . La idea básica es que la plataforma (en este caso, la implementación de C ++) proporciona estas dos operaciones primitivas mapea y reduce, y el programador proporciona operaciones de devolución de llamada para cada uno de los dos que realizan el "trabajo real".

Básicamente, la devolución de llamada para la operación de mapa asigna un valor de entrada a un valor intermedio. La devolución de llamada para reducir combina dos valores intermedios en un valor intermedio. El último valor intermedio que queda se convierte en la salida de todo el MapReduce. Parece ser un modelo muy restrictivo en sí mismo, pero aún así, tiene una gran variedad de aplicaciones.

La plataforma tiene que hacer más, por supuesto, como "barajar" (distribuir las entradas, generalmente en grupos, a diferentes unidades de procesamiento) y programar, pero esto es de poca importancia para el programador de la aplicación.

Por cierto, en la biblioteca estándar de C ++, la operación de "mapa" se llama transform . También ha recibido soporte de paralelismo en C ++ 17, pero más adelante entraré en el paralelismo.

Aquí hay un ejemplo inventado: digamos que tenemos una función que convierte un número entero en una representación de cadena. Ahora, dada una lista de enteros, queremos que la representación textual contenga la mayor proporción de consonantes y voces. P.ej

Entrada: 1, 17, 22, 4, 8
Salida: veintidós

(Pruébalo tú mismo si no crees este resultado).

Podríamos usar MapReduce aquí usando nuestra función int-to-text como la devolución de llamada al mapa (rsp. std::transform ), y una función que cuenta el número de consonantes y voces y luego selecciona la mano izquierda o la mano derecha argumento en consecuencia. Hay algunas ineficiencias aquí, en particular, la "relación" se debe almacenar en caché, pero estos son detalles.

Ahora tu pregunta puede y posiblemente debería ser: ¿Por qué debería importarme? Después de todo, hasta ahora no ganó mucho con el uso de, por ejemplo, std::transform y std::reduce de esta manera, y también podría haber usado std::accumulate en lugar de este último. Por supuesto, la respuesta, dada una cantidad suficientemente grande de valores de entrada , son las políticas de ejecución: las dos plantillas de funciones estándar anteriores tienen sobrecargas que permiten un paralelismo implícito. Pero eso sigue planteando la pregunta de por qué uno usaría MapReduce y no un grupo de subprocesos o std::async , y un montón de bucles escritos a mano. Primero, especialmente para los cálculos "puros" en vectores grandes u otros contenedores, sin E / S, a menudo es más conveniente escribir las dos devoluciones de llamada de MapReduce porque no tiene que lidiar con todos los detalles de cómo son los datos de entrada Se extendió por diferentes hilos y luego se combinó.

En segundo lugar, MapReduce fomenta la disciplina de estructurar sus cálculos de manera que pueda paralelizarse de manera muy efectiva. Por supuesto, en un lenguaje de programación que soporta el paradigma imperativo, como C ++, todavía puedes desordenar las cosas bloqueando un grupo de mutexes, o cualquier forma que tengas de interferir con otros hilos. Pero el paradigma MapReduce alienta la escritura de devoluciones de llamadas de mapeo independientes. Como regla general, si estas tareas comparten datos, entonces debería ser de solo lectura para que las copias de los mismos puedan almacenarse en múltiples cachés de CPU al mismo tiempo. Las tareas bien escritas, combinadas con una implementación eficiente de la plataforma de los algoritmos subyacentes, pueden escalar hasta cientos o incluso miles de núcleos de CPU, como lo demuestran las plataformas MapReduce que ya son de uso común (como Apache Hadoop, pero toman esto solo como necesario Ejemplo y no como publicidad gratuita).

Pero la pregunta era principalmente sobre std::reduce : todavía podríamos realizar este mapeo altamente escalable y luego ejecutar std::accumulate en los resultados intermedios, ¿verdad? Y aquí es donde llegamos a lo que François Andrieux escribió anteriormente. accumulate realiza lo que los matemáticos llaman un pliegue izquierdo. Si ve las operaciones y sus operandos como un árbol binario, entonces este sería un árbol inclinado hacia la izquierda, por ejemplo, para agregar 1, 2, 3 y 4:

+ / / + 4 / / + 3 / / 1 2

Como puede ver, el resultado de cada operación es uno de los argumentos de la siguiente operación. Esto significa que hay una cadena lineal de dependencias de datos, y esa es la perdición de todo paralelismo. Para agregar un millón de números, necesita un millón de operaciones consecutivas, que bloquearán un solo núcleo, y no puede hacer uso de núcleos adicionales. No tendrán nada que hacer la mayor parte del tiempo, y la sobrecarga de comunicación superará en gran medida el costo de los cálculos. (En realidad, es peor que eso, ya que las CPU modernas pueden realizar múltiples cálculos simples por reloj, pero esto no funciona cuando hay tantas dependencias de datos, por lo que la mayoría de las ALUs o las FPU no se utilizan).

Al eliminar la restricción de que se debe usar un pliegue a la izquierda, std::reduce permite a la plataforma hacer un uso más eficiente de los recursos computacionales. Incluso si usa la sobrecarga de un solo hilo , la plataforma podría, por ejemplo, usar SIMD para agregar un millón de enteros en mucho menos de un millón de operaciones, y la cantidad de dependencias de datos se reducirá en gran medida. Una aceleración de 10x en una reducción de suma de enteros bien escrita no me sorprendería. Concedido, este caso especial en particular probablemente podría optimizarse bajo la regla "como si" porque la implementación de C ++ "sabe" que la suma de enteros es (casi, ver más abajo) asociativa.

Pero reducir va más allá de eso, como se mencionó, al apoyar las políticas de ejecución, es decir, en la mayoría de los casos, el paralelismo de múltiples núcleos. En teoría, podría usarse un árbol binario equilibrado de operaciones. (Recuerde que un árbol está equilibrado si la profundidad es menor que dos, o si la profundidad del subárbol izquierdo es diferente de la profundidad del subárbol derecho como máximo 1.) Un árbol de este tipo solo tiene una profundidad logarítmica. Si tenemos un millón de enteros, la profundidad mínima del árbol es 20, por lo que, teóricamente, si se tienen suficientes núcleos y no hay sobrecarga de comunicación, podríamos alcanzar un factor de 50,000 de aceleración incluso sobre el cálculo optimizado de un solo hilo. Por supuesto, en la práctica, eso es un montón de ilusiones, pero aún podemos esperar grandes aceleraciones.

Dicho todo esto, permítame agregar una rápida advertencia / recordatorio de que el rendimiento no es lo mismo que la eficiencia. El uso de 64 núcleos por 100 ms significa un rendimiento mucho mayor que el uso de un núcleo por 1.000 ms, pero mucho menos eficiencia de CPU. Otra forma de decirlo es que el rendimiento es la eficiencia en el sentido de minimizar el tiempo transcurrido, pero existen otras medidas de eficiencia: el tiempo total de CPU utilizado, la memoria RAM utilizada, la energía utilizada, etc. La motivación principal de MapReduce paralelo es proporcionar un mayor rendimiento. No está claro si reduce el tiempo de CPU o el consumo de energía, y es muy probable que aumente el uso máximo de RAM.

Para colmo, aquí hay algunas advertencias . Como se mencionó, reduce no es determinista si las operaciones no son asociativas o no conmutativas. Afortunadamente, las operaciones aritméticas más importantes, como la suma y la multiplicación, son asociativas y conmutativas, ¿no? Todos sabemos que la suma de enteros y puntos flotantes, por ejemplo, tiene ambas propiedades. Y por supuesto, estoy siendo gracioso. En C ++, ni la suma de enteros con signo ni la suma de punto flotante son asociativas. Para los números de punto flotante, esto se debe a posibles diferencias en el redondeo de los resultados intermedios. Esto se visualiza fácilmente si, como ejemplo, seleccionamos un formato de coma flotante decimal simple con dos dígitos significativos, y consideramos la suma 10 + 0.4 + 0.4. Si las reglas de sintaxis de C ++ normales lo hacen como un pliegue a la izquierda, obtenemos (10 + 0.4) + 0.4 = 10 + 0.4 = 10 porque cada vez que el resultado se redondea a 10. Pero si lo hacemos como 10 + (0.4 + 0.4), el primer resultado intermedio es 0.8, y 10 + 0.8 se redondea a 11. Además, los errores de redondeo se pueden magnificar en gran medida por una gran profundidad del árbol de operaciones, por lo que hacer un pliegue a la izquierda es realmente uno de las peores cosas que uno podría hacer cuando se trata de precisión. Hay varias formas de lidiar con este comportamiento, desde ordenar y agrupar las entradas hasta usar una mayor precisión intermedia, pero cuando se trata de reduce , simplemente no hay manera de obtener una consistencia de ejecución para ejecución del 100%.

La otra observación, posiblemente más sorprendente, es que la suma de enteros con signo no es asociativa en C ++. La razón de esto es la posibilidad de desbordamiento, para decirlo sin rodeos: (-1) + 1 + INT_MAX . De acuerdo con las reglas de sintaxis normales, o accumulate , el resultado es INT_MAX . Pero si usa reduce , esto podría reescribirse como (-1) + (1 + INT_MAX) que contiene un desbordamiento de enteros y, por lo tanto, un comportamiento indefinido . De hecho, dado que reduce puede cambiar arbitrariamente el orden de los operandos, esto es cierto incluso si las entradas son { INT_MAX, -1, 1 } .

Mi recomendación aquí es asegurar que la devolución de llamada para reduce no pueda producir un desbordamiento. Esto podría hacerse limitando el rango permitido de entradas (por ejemplo, si agrega 1000 int s, asegúrese de que ninguna de ellas sea mayor que INT_MAX / 1000 o menor que INT_MIN / 1000 , redondeada hacia arriba), por ejemplo, o, de manera equivalente, mediante el uso de un tipo entero más grande o, como último recurso absoluto (debido a que es costoso y difícil de manejar correctamente), poner controles adicionales en la reduce devolución de llamada. Sin embargo, en la mayoría de los casos prácticos, reduce solo es marginalmente menos seguro con respecto al desbordamiento de enteros que a la accumulate .

std::accumulate iteraciones sobre el contenedor en el orden en que std:reduce podría no hacerlo. Debido a que el pedido no está garantizado, std::reduce introduce requisitos adicionales:

El comportamiento no es determinista si binary_op no es asociativo o no es conmutativo. El comportamiento no está definido si binary_op modifica cualquier elemento o invalida cualquier iterador en [first; último], incluyendo el iterador final.

Sin embargo, std::reduce proporciona sobrecargas que admiten la paralelización que no están disponibles con std::accumulate . std::reduce permite paralelizar automáticamente su operación, siempre que cumpla con los requisitos mencionados anteriormente.