Motor Peredvizhnikov: un motor de juegos lock-free escrito en C++20

 (github.com/eduard-permyakov)
4 puntos por GN⁺ 2023-09-11 | 1 comentarios | Compartir por WhatsApp
  • Un motor de juegos completamente lock-free escrito en C++20, que implementa el modelo de actores para computación concurrente sobre las primitivas de corrutinas del lenguaje
  • Usando la abstracción del modelo de actores, es posible desarrollar lógica paralela compleja aislándose de los detalles de sincronización entre hilos
  • La implementación totalmente lock-free ofrece garantía de progreso incluso ante la terminación arbitraria de hilos, prevención de deadlocks, latencia predecible para reaccionar a eventos importantes y tolerancia a fallos
  • Ofrece la garantía de que el motor seguirá ejecutándose incluso si uno de los hilos worker termina de forma asíncrona
  • La implementación incluye Software Transactional Memory, colas lock-free, primitivas de serialización lock-free, std::atomic_shared_ptr, scheduler lock-free, asignador de memoria lock-free y un DAG en tiempo de compilación, entre otros
  • Los algoritmos lock-free, la justificación del diseño y los benchmarks se tratan en el documento Peredvizhnikov Engine: Design and Implementation of a Completely Lock-Free Scheduler
  • Para ayudar al diseño orientado a datos, implementa una base de datos en memoria optimizada para acceso por componentes y compatible con conjuntos de datos de gran escala
  • La base de datos en memoria se basa en las estructuras de datos Flat Hash Map y Bitwise Trie with Bitmap
  • Actualmente la única plataforma compatible es Linux, y para compilar desde el código fuente se requiere Clang++ 16
  • El código fuente se ofrece bajo licencia GPLv3, y el permiso para usar parte o la totalidad del código bajo otra licencia puede concederse caso por caso

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-09-11
Opiniones en Hacker News

  • En el framework de actores usan un std::deque común como cola de punteros a métodos, y al encolar mensajes aplican bloqueo con el enfoque Benaphore.
    Originalmente, al estilo Futex, combina operaciones atómicas con primitivas de bloqueo, aunque mi primitiva de bloqueo funciona como una combinación de spinlock/mutex según la cantidad de reintentos. En los benchmarks, la función de push de mensajes casi nunca se bloquea, y como la posibilidad de un cambio de contexto del sistema operativo también es baja, aunque de vez en cuando un hilo bloqueado sea sacado de la CPU, no ocurre con la frecuencia suficiente como para justificar el costo de un algoritmo lock-free.
    En resumen, una cola no lock-free es mucho más rápida que una lock-free, pero hay que aceptar que, muy rara vez, aparezcan latencias largas por cambios de contexto en los que nadie obtiene el bloqueo. En hardware moderno se pueden encolar 10 millones de mensajes por segundo por cada hilo worker.

    • Dije “originalmente Futex”, pero Benaphore es una idea bastante antigua, y Futex no es simplemente un “Benaphore al estilo Linux”.
      La clave está en que un objeto del kernel, es decir, una primitiva de bloqueo aparte, en realidad no es necesaria. Ese es el punto en el que la idea pasa de ser “una técnica conocida por todos” a “una funcionalidad que hay que meter ya en el sistema operativo”.
      En el diseño de Futex, en vez de usar un objeto de sincronización del sistema operativo para manejar colisiones, el sistema operativo mantiene una lista de mapeos dirección→hilo. Si el hilo T se duerme en el futex de la dirección X, se agrega a la lista para que X apunte a T; y si llega una solicitud para despertar el futex X, el sistema operativo recorre la lista y despierta a T.
      La diferencia se nota en las limitaciones. Algo como Benaphore es un recurso caro a nivel de todo el sistema; recuerdo que BeOS solo permitía unos 65536 por máquina. En cambio, un Futex es simplemente memoria, así que no hay razón para ponerle un límite.
    • Un artículo tan interesante debería incluir un enlace al código. Así se respaldan las afirmaciones, y gente como yo, a la que le resulta interesante la idea, puede ir directo a ver la implementación.
    • Depende muchísimo de los detalles de la situación. Si hay mucha contención, el rendimiento cae en picada, e incluso las instrucciones atómicas pueden convertirse en un cuello de botella (https://stackoverflow.com/q/2538070).
      Creo que la observación de que en muchos casos basta con usar bloqueos y no preocuparse es correcta. Pero también hay aplicaciones o situaciones en las que se puede hacer algo mejor. Si se tiene cuidado, un enfoque donde el consumidor saca todos los elementos de la cola con una sola operación de bloqueo, y los productores le envían una señal al consumidor, puede mejorar la eficiencia y el throughput de la cola. Por ejemplo, no hay que enviar una señal cada vez que se inserta un elemento, sino solo cuando la cola pasa de estar vacía a no estarlo.
    • ¿Las estructuras de datos lock-free no tienen más sentido para reducir el impacto de la contención que para aumentar el throughput cuando hay poca contención?
    • Eso de que “el costo es aceptable” tiene una excepción: las personas con requisitos fuertes de que esas latencias largas, impredecibles y poco frecuentes que mencionaste jamás deben ocurrir.

  • El scheduler lock-free sin duda se ve interesante, y destaca especialmente la linealizabilidad del broadcast de eventos. Dicho eso, en los benchmarks del paper, con 12 pares de actores (¿y 12 cores?), el máximo es de 43,500 mensajes por segundo, y el gráfico de un solo core también muestra alrededor de 5,000 mensajes por segundo, lo cual es sorprendentemente bajo para un benchmark de este tipo.
    Todavía no pude reproducirlo porque el engine requiere Linux y, más importante, x86 (por las instrucciones en assembly), pero esperaría al menos alrededor de 1 millón de solicitudes por segundo por cada par de actores. Si uno piensa en casos como Erlang, por debajo de eso el overhead se vuelve prohibitivo.
    Este engine se enfoca en el paso de mensajes, pero por experiencia ese enfoque es muy difícil de manejar. Las máquinas de estado son difíciles, y trabajar con varios subactores lo vuelve todavía más complicado. En el fondo, diría que los actores tienen más que ver con aislar estado sin bloqueos que con el paso de mensajes. Creo que Swift actors lo hizo bien: si se usan llamadas a métodos en vez de mensajes, no solo es más fácil razonar sobre el código, sino que además se indican mejor los puntos donde el contexto puede cambiar en tiempo de ejecución, sin que necesariamente tenga que intervenir el scheduler. El estado compartido es lento y perjudica la escalabilidad.
    Hace poco hice una biblioteca header-only que implementa algo parecido a Swift actors con corrutinas de C++20. Si te interesa, búscala como “coroactors”. Sin contención alcanza alrededor de 10 millones de solicitudes por segundo, y aun así me pareció que entre 1 y 3 millones de solicitudes por segundo con contención y dependiendo del scheduler tenía demasiado overhead. Sobre todo si se lo compara con una llamada a un método normal sobre estado compartido protegido por un mutex. Las corrutinas tienden a volverse contagiosas: cada vez más funciones terminan siendo corrutinas async, y en una base de código no trivial se acumulan muchas llamadas a corrutinas o pasos de mensajes. Por eso el overhead debe ser lo más bajo posible; de lo contrario, se termina pasando más tiempo cambiando de tarea que haciendo trabajo útil.

  • Se dice que está basado en actores, y se explica que enviar un mensaje a un actor equivale a ejecutar la función del actor bajo un mutex. Es decir, aunque N hilos envíen mensajes, solo hay 1 hilo ejecutando el código del actor, así que se serializa como con un mutex.
    Por eso, aunque técnicamente pueda ser “totalmente lock-free”, mientras se usen actores no hay mejora en la paralelización

    • No necesariamente. En un actor basado en mutex, si el hilo del actor se suspende, ese mutex, es decir, el código del actor, queda bloqueado hasta que se reanude el hilo original. Como el mutex que posee el hilo suspendido está bloqueado, aunque haya más paralelismo no se puede “reiniciar” ni “reanudar” ese código del actor.
      Esta implementación depende mucho de funciones reiniciables para que otro hilo paralelo pueda tomar y continuar el trabajo de un actor que ya estaba en curso pero quedó suspendido. Basta ver la página 3 del excelente documento de diseño: https://github.com/eduard-permyakov/peredvizhnikov-engine/bl...
      Así que quizá no sea estrictamente “más paralelo” (porque la cantidad de actores es la misma), pero parece aprovechar mejor más paralelismo para completar el mismo conjunto de tareas.
    • ¿Dónde dice que “enviar un mensaje a un actor equivale a ejecutar la función del actor bajo un mutex”? Según entiendo, el modelo de actores implica paso de mensajes y ejecución asíncrona. De hecho, si hay N actores, N hilos podrían ejecutarse en paralelo.
    • Es cierto que no hay mejora en la paralelización, pero tampoco reduce el paralelismo. Es otra forma de pensar la concurrencia y, para mí, una forma más fácil.
      Si es más fácil de razonar, también se ve mejor dónde habrá contención sobre los mismos recursos, y en la práctica eso ayuda a mejorar el paralelismo potencial. Si notas una oportunidad concreta para que SMP aumente la velocidad, en el modelo de actores puedes apartarte un poco y hacer que varios hilos reciban de una cola de mensajes; y si eso no es posible, basta con agregar más actores para dividir mejor los datos.

  • ¿Alguien ha depurado o perfilado secciones críticas con mucha contención en STM y las ha comparado con una implementación tradicional con mutex? Al final se necesita algo que arbitre el acceso concurrente a memoria compartida, y no hay almuerzo gratis. Los mutex están muy optimizados, perfilados y entendidos.
    En cambio, no sé si STM está al mismo nivel. ¿No podría una transacción reintentarse indefinidamente (?)?

    • En este caso, el árbitro es el scheduler. En la práctica es quien invoca el bloque asíncrono y, si falla, potencialmente lo reintenta. En el código del post original hay bloques atómicos, ejecución secuencial de bloques y bloques con estado para garantizar un solo acceso a la vez.
      La clave es scheduler.cpp, y usa std::coroutines.
      Es similar a async/await en otros lenguajes. El scheduler tiene una cola de tareas (corutinas) y un pool de hilos (N>0) que las ejecuta.
      Aquí, las tareas que contienen datos se envían mensajes entre sí. A cambio de usar más memoria, no se necesitan bloqueos.
    • De hecho, en un STM sin inanición, el número de reintentos de una transacción está acotado. Un ejemplo es 2PLSF, y también hay varios otros métodos. https://zenodo.org/record/7886718

  • ¿No tiene aire a BEAM?
    https://youtu.be/bo5WL5IQAd0?feature=shared

  • No vi que se mencionara qué tan difícil es depurar un motor así.

  • No tengo tiempo para leer la implementación, pero solo con el README suena como un sistema distribuido clásico entre hilos de juego. Supongo que patrones como retry-backoff serán comunes.

  • “Lock-free” suena genial, pero creo que cualquier código que use operaciones atómicas de forma significativa debería venir acompañado de una prueba formal y, si es posible, verificada por máquina. Usar correctamente órdenes atómicos que no sean consistencia secuencial es demasiado difícil. He visto varias veces código mal escrito, y los bugs que salen de ahí son de lo peor.

  • ¿Dónde está la demo de juego? Hoy en día, para considerarlo un motor de juego, también hacen falta herramientas reales, exportadores para Maya o 3DSMax, y cosas como herramientas de colaboración, métricas y alertas.

    • No estoy de acuerdo. “Motor de juego” no necesariamente significa “algo que pueda reemplazar a Unity o Unreal”.

  • Aunque dice “lock-free”, parece que todavía no lo es.
    export std::mutex iolock{};
    export std::mutex errlock{};
    SDL_PollEvent