Hola habrozhiteli! El lenguaje C ++ se elige cuando necesita crear aplicaciones realmente rápidas. Y el procesamiento competitivo de alta calidad los hará aún más rápidos. Las nuevas características de C ++ 17 le permiten utilizar toda la potencia de la programación multiproceso para resolver fácilmente los problemas de procesamiento gráfico, aprendizaje automático, etc. Anthony Williams, un experto en procesamiento competitivo, considera ejemplos y describe tareas prácticas, así como comparte secretos que serán útiles para todos en incluidos los desarrolladores más experimentados.
En el libro • Una descripción completa de las características de C ++ 17. • Lanzamiento y control de flujo. • Sincronización de operaciones competitivas. • Desarrollo de código competitivo. • Depuración de aplicaciones multiproceso. El libro es adecuado para desarrolladores de nivel medio que usan C y C ++. No se requiere experiencia en programación competitiva.
Desarrollo de código competitivo
8.1. Formas de distribuir el trabajo entre hilos
Imagina que necesitas construir una casa. Para hacer esto, tendrá que cavar un pozo de cimentación, llenar la cimentación misma, erigir paredes, tender tuberías y cableado eléctrico, etc. Teóricamente, con suficientes habilidades, todo se puede hacer de forma independiente, pero lo más probable es que tome mucho tiempo y tendrá que cambiar de un trabajo a otro. otro Pero puedes contratar asistentes. Luego será necesario elegir cuántos asistentes contratar y decidir qué deberían poder hacer. Puede, por ejemplo, contratar a dos trabajadores y trabajar con ellos. Entonces, todavía tienes que cambiar de un trabajo a otro, pero ahora las cosas irán más rápido, ya que habrá más artistas.
Puede elegir otra opción: contratar un equipo de especialistas, como albañil, carpintero, electricista y plomero. Cada uno trabajará en su propia especialidad, por lo tanto, hasta que el plomero tenga un frente de trabajo, se sentará inactivo. Y sin embargo, las cosas irán más rápido que antes, ya que hay más trabajadores, y aunque el electricista llevará a cabo el cableado en la cocina, el plomero puede ir al baño. Pero cuando no hay trabajo para un especialista específico, se obtiene más tiempo de inactividad. Sin embargo, se puede observar que incluso teniendo en cuenta el tiempo de inactividad, el trabajo se mueve más rápidamente cuando los especialistas vienen a trabajar, en lugar de un equipo de trabajadores. Los especialistas no necesitan cambiar constantemente las herramientas, y seguramente cada uno de ellos llevará a cabo su tarea más rápido que el trabajador. Si esto realmente será así depende de las circunstancias específicas: todo se aprende en la práctica.
Incluso si involucra especialistas, aún debe elegir un número diferente de trabajadores de diversas especialidades. Quizás tenga sentido contratar, por ejemplo, más albañiles que electricistas. Además, la composición de su equipo y la efectividad general de su trabajo pueden cambiar si tiene que construir varias casas a la vez. Incluso si hay poco trabajo para un fontanero en una sola casa, cuando se construyen varias casas a la vez, se puede tomar todo el día. Además, si no tiene que pagar a especialistas por tiempo de inactividad, puede reclutar un equipo más grande, incluso si la cantidad de personas que trabajan simultáneamente no cambia.
Pero deja de hablar de la construcción. ¿Qué tiene que ver todo esto con los hilos? Y puede aplicarles consideraciones similares. Debe decidir cuántos hilos usar y qué tareas deben realizar. ¿Necesitamos hilos universales que hagan el trabajo que se necesita en un momento particular, o hilos especializados que estén bien adaptados a una sola cosa? ¿O tal vez vale la pena combinar ambos? Estas decisiones deben tomarse independientemente de los motivos para paralelizar el programa, y el rendimiento y la claridad del código dependen significativamente de su éxito. Por lo tanto, es muy importante imaginar qué opciones están disponibles para tomar una decisión competente al desarrollar la estructura de la aplicación. En esta sección, consideraremos una serie de métodos para distribuir tareas, comenzando con la distribución de datos entre subprocesos hasta que se realice cualquier otro trabajo.
8.1.1 Distribución de datos entre hilos antes de procesar
Los más fáciles de paralelizar son los algoritmos simples, como std :: for_each, que realizan operaciones en cada elemento de un conjunto de datos. Para paralelizar este algoritmo, puede asignar cada elemento a uno de los hilos de procesamiento. En el futuro, al considerar los problemas de rendimiento, quedará claro que la mejor opción de distribución para lograr un rendimiento óptimo depende de las características de la estructura de datos.
Al distribuir datos, el caso más simple es cuando los primeros N elementos se asignan a un flujo, los siguientes N elementos a otro, etc. (Fig. 8.1), pero se pueden usar otros esquemas. Independientemente del método de distribución de datos, cada subproceso procesa solo los elementos asignados a él, sin interactuar con otros subprocesos hasta que finaliza el procesamiento.
La estructura debe ser familiar para todos los que se han ocupado de la programación en la interfaz de paso de mensajes (MPI,
www.mpi-forum.org ) o OpenMP (http://www.openmp.org/): la tarea se divide en muchas tareas que se realizan en paralelo, los flujos de trabajo los ejecutan independientemente unos de otros, y los resultados se recopilan en la etapa final de la información. Este enfoque se utilizó en el ejemplo con la función de acumulación de la sección 2.4: tanto las tareas paralelas como la etapa de reducción son acumulación. Para un algoritmo simple for_each, falta el paso final, ya que no hay nada que reducir.
El hecho de que una mezcla se defina como la esencia de la etapa final juega un papel muy importante: una implementación elemental similar a la que se muestra en el Listado 2.9 realizará esta mezcla como una etapa secuencial final. Pero a menudo esta etapa también es paralela: la acumulación es una operación de reducción, por lo que el código en el Listado 2.9 se puede cambiar para obtener una llamada recursiva del mismo código cuando, por ejemplo, el número de hilos es mayor que el número mínimo de elementos procesados por el hilo. También puede obligar a los flujos de trabajo a realizar pasos de acumulación tan pronto como cada uno de ellos complete su tarea, en lugar de comenzar nuevos hilos cada vez.
A pesar de su eficacia, esta técnica no es versátil. A veces, los datos no se pueden dividir con precisión por adelantado, ya que la composición de cada parte se conoce solo durante el procesamiento. En particular, esto es evidente cuando se utilizan algoritmos recursivos como Quicksort, por lo que requieren un enfoque diferente.
8.1.2. Distribución recursiva de datos
El algoritmo Quicksort tiene dos etapas principales: dividir los datos en dos partes: todo lo que viene a uno de los elementos (referencia), y todo lo que viene después en el orden de clasificación final, y la clasificación recursiva de estas dos mitades. Es imposible paralelizarlo mediante la división preliminar de los datos, ya que es posible determinar en qué "mitad" caen solo durante el procesamiento de los elementos. Si tiene la intención de paralelizar este algoritmo, debe usar la esencia misma de la recursividad. En cada nivel de recursión, se realizan más y más llamadas a la función quick_sort, ya que tiene que ordenar tanto las que son más grandes que la referencia como las que son más pequeñas. Estas llamadas recursivas son independientes entre sí porque se refieren a conjuntos de elementos separados. Debido a esto, son los primeros candidatos para la competitividad. Esta distribución recursiva se muestra en la Fig. 8.2.
Esta implementación ya se cumplió en el Capítulo 4. En lugar de hacer dos llamadas recursivas para las mitades más grandes y más pequeñas, utilizamos la función std :: async (), que ejecuta tareas asincrónicas para la mitad más pequeña en cada paso. Debido al uso de std :: async (), la biblioteca de subprocesos de C ++ tuvo que decidir cuándo iniciar la tarea en un nuevo subproceso y cuándo, en modo sincrónico.
Hay una circunstancia importante: al ordenar un gran conjunto de datos, comenzar un nuevo hilo para cada recursión conducirá a un rápido aumento en el número de hilos. Al examinar problemas de rendimiento, se mostrará que demasiados hilos pueden ralentizar la aplicación. Además, con un gran conjunto de flujos de datos puede que simplemente no sea suficiente. La idea misma de dividir toda la tarea en un modo tan recursivo parece muy exitosa, solo necesita monitorear cuidadosamente la cantidad de hilos. En casos simples, la función std :: async () maneja esto, pero hay otras opciones.
Una de ellas es utilizar la función std :: thread :: hardware_concurrency () para seleccionar el número de hilos, como se hizo en la versión paralela de la función generate () del Listado 2.9. Luego, en lugar de comenzar un nuevo subproceso para cada llamada recursiva, puede colocar el fragmento para ordenarlo en una pila segura para subprocesos, por ejemplo, como se discutió en los capítulos 6 y 7. Si el subproceso no tiene nada que hacer o ha terminado de procesar todos sus fragmentos o está esperando que se ordene el fragmento, puede toma un fragmento de la pila y clasifícalo.
El listado 8.1 muestra una implementación simple de esta tecnología. Como en la mayoría de los otros ejemplos, solo demuestra la intención y no es un código listo para su uso práctico. Si usa el compilador C ++ 17 y su biblioteca lo admite, debe usar los algoritmos paralelos proporcionados por la biblioteca estándar de acuerdo con las descripciones dadas en el capítulo 10.
Listado 8.1. Un algoritmo paralelo de Quicksort que utiliza una pila de fragmentos en espera de clasificación
Aquí, la función parallel_quick_sort
(19) coloca la mayor parte de las responsabilidades funcionales en la clase sorter
(1) , que proporciona una manera fácil de agrupar la pila de fragmentos sin clasificar
(2) y múltiples hilos
(3) . El trabajo principal se realiza en la función del componente do_sort
(9) , que está ocupada por la partición de datos habitual
(10) . Esta vez, en lugar de comenzar un nuevo hilo para cada fragmento, empuja este fragmento en la pila (11) e inicia un nuevo hilo solo si hay un recurso de procesador libre (12). Dado que un fragmento con valores inferiores al de referencia puede ser procesado por otra secuencia, debemos esperar a que esté listo
(13) . Para que no se pierda el tiempo (en el caso de que tengamos un solo subproceso o todos los demás subprocesos ya estén ocupados), se intenta procesar fragmentos de la pila para este período de espera
(14) . La función try_sort_chunk recupera un fragmento de la pila
(7) , lo ordena
(8) y guarda los resultados en la promesa de promesa para que puedan recibir la secuencia que coloca este fragmento en la pila
(15) .
Ahora, los subprocesos recién lanzados están en un bucle e intentan ordenar fragmentos de la pila
(17) si el indicador end_of_data
(16) no está establecido. Entre las comprobaciones, ceden el recurso informático a otros subprocesos para que puedan llevar trabajo adicional a la pila. El trabajo del código en términos de ordenar estos hilos depende del destructor de su clase sorter
(4) . Cuando se ordenan todos los datos, la función do_sort devolverá el control (incluso manteniendo la actividad de los subprocesos de trabajo), el subproceso principal volverá desde parallel_quick_sort
(20) y destruirá el objeto del clasificador. Establecerá el indicador end_of_data
(5) y esperará a que los subprocesos terminen de funcionar
(6). Establecer el indicador detendrá el bucle en la función de subprocesos (16).
Con este enfoque, el problema del número ilimitado de subprocesos inherentes a la función spawn_task que lanzó el nuevo subproceso desaparecerá y la dependencia de la biblioteca de subprocesos de C ++, que seleccionará el número de subprocesos para usted, como lo hace al usar std :: async (), desaparecerá. En cambio, para evitar el cambio de tareas con demasiada frecuencia, el número de subprocesos está limitado por el valor devuelto por la función std :: thread :: hardware_concurrency (). Pero surge otro problema: administrar estos flujos e intercambiar datos entre ellos complica enormemente el código. Además, a pesar del hecho de que los subprocesos procesan elementos de datos individuales, todos acceden a la pila, agregando nuevos fragmentos y tomando fragmentos para el procesamiento. Tal competencia intensa puede reducir el rendimiento, incluso si se usa una pila sin bloqueo (por lo tanto, sin bloqueo), y las razones para esto pronto se considerarán.
Este enfoque es una versión especial del grupo de subprocesos: un conjunto de subprocesos, cada uno de los cuales recibe trabajo de la lista de trabajos diferidos, lo realiza y luego busca en la lista uno nuevo. Algunos problemas potenciales inherentes al grupo de subprocesos (incluida la competencia al acceder a la lista de trabajos), y las formas de resolverlos se discuten en el Capítulo 9. Al escalar la aplicación creada para que se ejecute en varios procesadores, discutiremos este capítulo un poco más adelante (ver subsección 8.2.1).
Al distribuir datos tanto antes del procesamiento como en modo recursivo, se supone que se corrigen de antemano y se está buscando su distribución. Pero esto no siempre sucede: si los datos se crean en modo dinámico o provienen de una fuente externa, este enfoque no funciona. En este caso, puede ser más razonable distribuir el trabajo de acuerdo con el tipo de tarea y no en función de los datos en sí.
8.1.3. Distribución del trabajo por tipo de tarea.
La distribución del trabajo entre subprocesos al asignar a cada uno de ellos (por adelantado o recursivamente durante el procesamiento de datos) diferentes datos en cualquier caso, se basa en el supuesto de que los subprocesos van a hacer el mismo trabajo en cada pieza. Una distribución alternativa del trabajo es la especialización de flujos, donde cada uno realiza una tarea separada, ya que los fontaneros y electricistas realizan diferentes tareas en la construcción de una casa. Las transmisiones pueden funcionar con datos diferentes o iguales, pero en el último caso lo hacen para diferentes propósitos.
Esta peculiar división del trabajo surge como resultado de la separación de tareas con la ayuda de la competencia: cada hilo tiene una tarea separada, que realiza independientemente de otros flujos. A veces, otros subprocesos pueden entregar datos a la secuencia o producir eventos a los que debería responder, pero en general, cada secuencia se concentra en el rendimiento de alta calidad de una sola tarea. Este es un buen diseño básico, donde cada parte del código debe ser responsable de una cosa.
Distribución del trabajo por tipo de tarea para compartir la responsabilidad.
Una aplicación de subproceso único tiene que hacer frente a conflictos relacionados con el principio de responsabilidad única, cuando hay varias tareas que deben realizarse continuamente durante un tiempo determinado, o la aplicación debe hacer frente al procesamiento de los eventos entrantes de manera oportuna (por ejemplo, un usuario presiona una tecla o los datos llegan a través de la red) en presencia de otras tareas pendientes. En un entorno informático de un solo subproceso, debe crear de forma independiente el código que ejecuta parte de la tarea A, parte de la tarea B, verifica si se presionó la tecla y no hay paquetes de red, y luego vuelve cíclicamente a la siguiente parte de la tarea A. Esto complica el código para la ejecución tareas A debido a la necesidad de mantener su estado y devolver periódicamente el control al bucle principal. Si agrega demasiadas tareas al ciclo, el trabajo puede disminuir significativamente y el usuario probablemente notará una reacción lenta a las pulsaciones de teclas. Estoy seguro de que todos observaron las manifestaciones extremas de una situación similar en ciertas aplicaciones: configura una tarea para la aplicación y la interfaz no reacciona ante nada hasta que se completa.
Aquí los flujos llegan al escenario. Si ejecuta cada tarea en un hilo separado, el sistema operativo puede hacer esto en lugar de usted. En el código para la tarea A, puede concentrarse en completar la tarea sin preocuparse por mantener el estado y volver al ciclo principal, o por cuánto tiempo pasará antes de que esto suceda. Es decir, el sistema operativo guardará automáticamente el estado y en el momento correcto cambiará a la tarea B o C, y si el sistema en el que se ejecutará el programa tiene varios núcleos o procesadores, será posible ejecutar simultáneamente las tareas A y B. El código para procesar pulsaciones de teclas o recibos los paquetes de red ahora se pueden ejecutar de manera oportuna, y todos se beneficiarán: el usuario recibirá una respuesta adecuada del programa y usted, como desarrollador, recibirá un código simplificado, ya que cada flujo puede ser dirigido para realizar operaciones directamente relacionadas con sus tareas, sin mezclarlas con el flujo de control y la interacción del usuario.
Está surgiendo una imagen ideal. Pero, ¿puede resultar todo de esa manera? Como siempre, todo depende de las circunstancias específicas. Si se respeta la independencia total y los flujos no necesitan intercambiar datos entre sí, entonces eso es exactamente lo que sucederá. Desafortunadamente, una situación similar se observa muy raramente. A menudo, las acciones necesarias para el usuario tienen la forma de tareas en segundo plano convenientes, y necesitan notificar al usuario sobre la tarea, actualizando la interfaz de usuario de alguna manera. O el usuario puede necesitar detener la tarea, por lo que la interfaz de usuario deberá enviar de alguna manera un mensaje a la tarea en segundo plano, haciendo que deje de ejecutarse. En ambos casos, es necesario considerar cuidadosamente el diseño y la sincronización adecuada, pero las tareas realizadas permanecerán fragmentadas. El subproceso de la interfaz de usuario aún controla esta interfaz, pero puede asignarse para realizar una actualización a petición de otros subprocesos. El subproceso que implementa la tarea en segundo plano todavía se concentra en las operaciones necesarias para completarlo; también sucede que uno de los subprocesos en segundo plano permite que la tarea detenga el otro subproceso. En ambos casos, a los flujos no les importa de dónde proviene la solicitud, solo les importa el hecho de que está diseñada para ellos y está directamente relacionada con sus responsabilidades.
Hay dos peligros graves en compartir la responsabilidad entre múltiples hilos. Primero, puede resultar que se distribuyan responsabilidades inapropiadas. Una señal de esto son demasiados datos compartidos por las transmisiones, o el hecho de que las transmisiones diferentes tienen que esperar entre sí. . . , , , , . , , — , , .
. , , .
, . : , , .
— . , , . , , , .
, 8.1.1, , . , .
, : , . , 20 , 3 . , . , , , , 12 , 24 — . . 20 . . . , , , , 12 . , 12 , . , : , , , , , . 3 12 .
, 9 , . . , , . 25 , — . , , : , 100 , , 1 , 100 , 1 100 . , , . , , , .
, , , , .
8.2. ,
, , . , , . , 16 , .
, — , , ( ), . , : ?
8.2.1. ?
( ) , . , , , . , . , . , , ( ) . , , , .
16- 16 : 16 . , 16 . , , ( ). , 16 , , , 1. (oversubscription).
, , C++11 (Standard Thread Library) std::thread::hardware_concurrency(). .
std::thread::hardware_concurrency() : - , , . , , std::thread::hardware_concurrency(), . std::async() , . .
, , , . — , , . , , , , C++. , std::async(), , , . , . , , std::thread::hardware_concurrency(), . , , , .
, . , , , , .
, — .
»Se puede encontrar más información sobre el libro en
el sitio web del editor»
Contenidos»
Extracto25% —
C++Tras el pago de la versión en papel del libro, se envía un libro electrónico por correo electrónico.