Los mutex más rápidos

• Cosmopolitan Libc es conocido por ofrecer binarios ejecutables en múltiples sistemas operativos, y es una biblioteca de C que también puede ofrecer un rendimiento sobresaliente en entornos de producción.
• Benchmark de mutex para demostrar rendimiento: se compara el rendimiento de implementaciones de mutex con una prueba en la que 30 hilos incrementan el mismo entero 100,000 veces.
  • Windows
    • pthread_mutex_t de Cosmopolitan es 2.75 veces más rápido que SRWLOCK de Microsoft y usa 18 veces menos recursos de CPU.
    • El mutex de Cygwin tiene un rendimiento muy bajo, al punto de que sería mejor usar un spin lock.
  • Linux
    • pthread_mutex_t de Cosmopolitan es 3 veces más rápido que glibc y 11 veces más rápido que musl libc.
    • El uso de CPU es 42 veces menor que con glibc y 178 veces menor que con musl libc.
  • MacOS
    • Apple Libc muestra un rendimiento ligeramente mejor que el mutex de Cosmopolitan.
    • Cosmopolitan optimiza el rendimiento usando un algoritmo basado en el artículo "Futexes Are Tricky" de Ulrich Drepper.

¿Cómo es posible?

• Logra ese rendimiento excepcional usando la biblioteca nsync, escrita por el reconocido ingeniero de Google Mike Burrows.
  • Él fue quien programó Altavista, antiguo competidor de Google.
• Trucos y análisis de nsync
  • nsync usa de inmediato un CAS (compare and swap) optimista para bloquear rápidamente cuando no hay contención.
  • Cuando no puede adquirir el bloqueo, nsync agrega el hilo llamador a una lista doblemente enlazada de hilos en espera.
    • Cada hilo en espera recibe su propio semáforo en una línea de caché independiente.
    • Una vez que el hilo entra en espera, deja de tocar el bloqueo base.
    • La razón de esto se puede ver en el documento "What Every Programmer Should Know About Memory" de Ulrich Drepper.
    • Si varios núcleos tocan la misma línea de caché, se genera mucho overhead de comunicación dentro del procesador.
  • nsync recibe ayuda del sistema operativo mediante futex.
    • futex es una excelente abstracción inventada hace años en Linux, que luego comenzó a usarse rápidamente en otros sistemas operativos.
    • En MacOS se llama ulock, y en Windows se llama WaitOnAddress().
    • El único sistema operativo compatible con Cosmo que no tiene futex es NetBSD (implementa los semáforos POSIX en espacio de kernel, y cada semáforo necesita crear un nuevo descriptor de archivo).
    • Lo importante de futex y de los semáforos es que el SO puede poner a dormir los hilos. Gracias a eso, nsync no consume tiempo de CPU cuando no hay trabajo por hacer.
  • nsync evita el starvation con el concepto de "espera larga (long wait)".
    • Si un hilo en espera se despierta 30 veces y falla internamente al adquirir el bloqueo, se agrega un bit al candado para impedir que lo adquiera un hilo que aún no ha esperado.
    • El CAS inicial falla para todos los demás hasta que la cola de espera se alivie en cierta medida.
  • nsync usa el concepto de "designated waker" para acelerar el caso de uso medido en el benchmark (bloqueos en contención con secciones críticas pequeñas).
    • Cuando un hilo que intenta adquirir el bloqueo está despierto, este bit se establece en el bloqueo base.
    • En nsync, la función de desbloqueo se encarga de despertar al siguiente hilo que espera el bloqueo.
    • Con este bit, el hilo que desbloquea sabe que no necesita despertar un segundo lock, porque ya hay uno despierto.

Prueba en línea

• Se puede verificar el rendimiento mediante una demo en vivo de software que usa el mutex de Cosmopolitan.
• El servidor web http://ipv4.games/ muestra un rendimiento capaz de soportar incluso ataques DDoS a gran escala.

[GN⁺]

Comentarios de Hacker News

• Siempre es interesante ver nuevas implementaciones de mutex y comparaciones de su rendimiento. Pero este benchmark parece un microbenchmark. Normalmente se prueba el rendimiento usando programas multihilo a gran escala. En cargas de trabajo complejas, el rendimiento de los mutex se comporta de manera distinta

  • Tengo experiencia escribiendo el fast lock que usa WebKit y soy la persona que inventó la abstracción ParkingLot. También se usa en Rust y Unreal Engine

• La razón por la que Cosmopolitan Mutexes es bueno es porque usó una biblioteca llamada nsync. Esta biblioteca fue escrita por el reconocido ingeniero de Google Mike Burrows. Pero me pregunto por qué esta implementación de mutex no fue incluida en el benchmark

  • Si se usa __ulock en macOS, se puede implementar de forma más simple con las funciones wait() y notify_one() de la biblioteca atomic de libc++

• Hay muchas opiniones positivas sobre Cosmo/ape/redbean, pero nunca he visto a nadie usarlos realmente. Me pregunto si estas herramientas son de verdad innovadoras pero todavía no se usan ampliamente

• Valoro mucho el proyecto Cosmopolitan, pero desconfío de las afirmaciones exageradas de superioridad. La razón por la que no todas las bibliotecas de C han adoptado el mismo truco puede ser que solo sea siempre más rápido en ciertas arquitecturas, modelos de CPU o cargas de trabajo

• En entornos de producción, la confiabilidad es más importante que la velocidad o la eficiencia. Es más importante asegurarse de que el sistema no falle

• Tengo experiencia corrigiendo un bug que encontré en la función de desbloqueo de mutex de nsync. He estado viendo mejoras a nsync dentro del proyecto Cosmopolitan. Me pregunto si usar nsync upstream es seguro

• Los hilos y los mutex son uno de los elementos más complejos de la informática. Siempre soy escéptico hasta que una nueva implementación se use a gran escala. Cuando apareció Java, quedaron expuestos muchos bugs de hilos y mutex en Solaris

• Me sorprende que nsync sea mucho más rápido que SRWLOCK. Tengo experiencia haciendo ingeniería inversa de los SRWLOCK de win32

• Cada vez que veo mutex me genera una reacción negativa. He trabajado quitando locks de mucho código y reemplazándolos por abstracciones de colas o mensajería. Últimamente he estado explorando varios algoritmos de locking. Quiero probar herramientas de locking eficientes como nsync