¿Qué tan rápidos son los pipes de Linux? (2022)

 (mazzo.li)
1 puntos por GN⁺ 2023-10-06 | 1 comentarios | Compartir por WhatsApp
  • Al rastrear el throughput de los pipes de Linux con perf y análisis de la ruta del kernel, una implementación simple basada en write/read pasó de 3.7GiB/s a 62.5GiB/s
  • El punto de partida del cuello de botella es que el pipe funciona como un ring buffer que contiene referencias a páginas de 4KiB, por lo que paga a la vez costos de copia, asignación de páginas, locks y espera/despertar
  • vmsplice y splice reducen las copias entre la memoria de usuario y los buffers del kernel, elevando el throughput a alrededor de 12.7GiB/s y 32.8GiB/s, respectivamente
  • Después de eso, el costo de convertir rangos de direcciones virtuales en struct page se vuelve más visible, y usando huge pages de 2MiB la carga de recorrer las tablas de páginas baja, subiendo hasta 51.0GiB/s
  • La optimización final, SPLICE_F_NONBLOCK y un busy loop, aumenta todavía más el throughput, pero mantiene ocupado el core de CPU mientras espera el estado listo

Objetivo del experimento y rendimiento de referencia

  • El objetivo es revisar cómo están implementados los pipes de Unix en Linux e ir optimizando paso a paso un programa de prueba que escribe y lee datos a través de un pipe
  • El entorno de prueba usa un CPU Intel Skylake i7-8550U y Linux 5.17; como la implementación interna de Linux cambia constantemente, las cifras pueden variar según el entorno
  • El punto de partida es un programa que envía repetidamente un buffer de 256KiB por el pipe usando las system calls write y read
    • write sigue escribiendo el mismo buffer de 256KiB
    • read lee un total de 10GiB e imprime el throughput
    • El código está en pipes-speed-test
  • Como referencia de comparación, un programa de FizzBuzz altamente optimizado entrega cerca de 36.2GiB/s medidos con pv
    • FizzBuzz usa bloques de 256KiB, del mismo tamaño que la caché L2
    • Este experimento también usa bloques de 256KiB, pero busca acercarse al límite del IO del pipe sin calcular el contenido de salida
  • El resultado de la primera implementación fue el siguiente
    • ./write | ./read
    • 3.7GiB/s, buffer de 256KiB, 40960 iteraciones, 10GiB transferidos en total

Por qué write y read son lentos

  • Al revisar con perf record -g y perf report, cerca del 47% del tiempo del lado de write se consume en pipe_write
  • Dentro de pipe_write, copy_page_from_iter y __alloc_pages representan una parte importante
    • copia de datos
    • asignación de páginas
    • scheduling
    • espera y despertar
    • adquisición y liberación de locks
  • Un pipe de Linux es un ring buffer que contiene referencias a páginas
    • pipe_inode_info tiene head, tail y un arreglo de pipe_buffer
    • pipe_buffer tiene struct page *page, offset, len
    • El tamaño normal de página en x86-64 es 4KiB
    • El ring buffer por defecto tiene 16 slots, y el pipe de 8 slots del ejemplo puede contener hasta 32KiB
  • head representa el final de escritura y tail el final de lectura
    • Si el pipe está lleno, write se bloquea
    • Si el pipe está vacío, read se bloquea
  • pipe_write avanza más o menos en este orden
    • Si el pipe ya está lleno, espera hasta que haya espacio
    • Si el buffer al que apunta head tiene espacio, primero lo llena
    • Si hay slots vacíos y datos restantes, asigna una nueva página, la llena y actualiza head
  • pipe_read hace lo contrario: consume páginas, libera las páginas completamente leídas y actualiza tail
  • En esta ruta, cada página se copia dos veces
    • una vez de memoria de usuario al kernel
    • y otra vez del kernel a memoria de usuario
  • La copia ocurre en unidades de páginas de 4KiB, mezclada con sincronización y asignación/liberación de páginas
  • En la misma máquina, una lectura secuencial de RAM en un solo hilo daba cerca de 16GiB/s; considerando la complejidad de la ruta del pipe, no sorprende que write/read sean unas 4 veces más lentos

Reducir copias con vmsplice y splice

  • En IO rápido, el costo de copia entre la memoria de usuario y los buffers del kernel puede convertirse en el cuello de botella
  • Linux ofrece system calls relacionadas con pipes para mover datos sin copia
    • splice: mueve datos entre un pipe y un file descriptor
    • vmsplice: mueve datos desde memoria de usuario hacia un pipe
  • vmsplice especifica los buffers a insertar en el pipe mediante un arreglo de struct iovec
    • Su valor de retorno es la cantidad de bytes que realmente entraron al pipe
    • Por el límite de tamaño del ring buffer del pipe, puede que no entre de una vez todo el tamaño solicitado
  • vmsplice conecta la memoria de usuario al pipe sin copiarla, así que hay que tener cuidado de no reutilizar el buffer antes de que el lado lector consuma esos datos
  • El programa de FizzBuzz usa double buffering para esto
    • Divide un buffer de 256KiB en dos mitades de 128KiB
    • Ajusta el tamaño del pipe a 128KiB para crear 32 slots con páginas de 4KiB
    • Va llenando alternadamente las dos mitades del buffer y las inserta en el pipe con vmsplice
  • Aunque el programa de prueba en realidad no vuelve a escribir el contenido del buffer, mantiene el double buffering porque se parece a la estructura que necesitaría un programa real que genera salida
  • Si se cambia write por vmsplice, el throughput sube a 12.7GiB/s
    • la cantidad de copia se reduce a la mitad
    • mejora más de 3 veces frente a write/read
  • Si también se cambia el lado lector a splice, se eliminan todas las copias y sube hasta 32.8GiB/s
  • Aun así, la seguridad de vmsplice requiere cuidado
    • una página puede extender su vida útil si vuelve a ser spliced
    • no está claro si sigue siendo inseguro incluso sin SPLICE_F_GIFT
    • usar pipes zero-copy de forma segura requiere precaución especial

iov_iter_get_pages y el costo de convertir páginas

  • Después de aplicar vmsplice y splice, en perf se ve mucho tiempo en la ruta de vmsplice
    • iov_iter_get_pages
    • __mutex_lock.constprop.0
    • add_to_pipe
  • iov_iter_get_pages convierte el rango de memoria virtual del struct iovec pasado a vmsplice en una lista de struct page que el pipe puede almacenar
  • Los procesos usan direcciones virtuales, no direcciones de memoria física
    • La CPU convierte direcciones virtuales en físicas a través de las tablas de páginas
    • El tamaño normal de página en x86-64 es 4KiB
    • Las tablas de páginas de x86-64 suelen describirse como una estructura de árbol de 4 niveles y 512 vías por nivel
  • El pipe_buffer del pipe hace referencia a struct page
    • struct page es la estructura central con la que el kernel maneja páginas físicas y sus metadatos asociados
    • Por eso vmsplice tiene que convertir el rango de memoria virtual de entrada en referencias a páginas físicas
  • La mayor parte del tiempo dentro de iov_iter_get_pages se consume en get_user_pages_fast
    • Con un buffer de 128KiB y páginas de 4KiB, hay que obtener un total de 32 páginas
    • El código del pipe, por implementación, llama con nr_pages = 16 cada vez y repite si hace falta, pero el total de páginas spliced sigue siendo 32
  • get_user_pages_fast recorre por software las tablas de páginas, de manera parecida a lo que hace la CPU, para reunir struct page
  • Mientras quien llama usa la página, hay que incrementar el contador de referencias de struct page para que la página física no se reutilice
    • después hay que bajar ese contador con put_page
  • Si al inicio se llena el buffer con memset, las entradas de la tabla de páginas se crean con anticipación y se evita la ruta lenta de get_user_pages_fast
    • sin memset, en el ejemplo el throughput baja a 25.0GiB/s
    • con huge pages este fenómeno no aparece de la misma forma

Bajar el costo de manejo de páginas con huge pages

  • x86-64 soporta huge pages de 2MiB y 1GiB además de las páginas normales de 4KiB
    • Los experimentos posteriores solo tratan las huge pages de 2MiB
    • Las páginas de 1GiB son relativamente poco comunes y se consideran excesivas para este trabajo
  • Las huge pages representan el mismo rango de memoria con menos páginas, reduciendo el costo de administración
    • Al convertir direcciones virtuales en físicas, también se elimina un nivel de tabla de páginas
    • También pueden ayudar a reducir la carga sobre la TLB de la CPU
  • En este experimento, el cuello de botella directo no es el page-table walk de hardware, sino la ruta de software del kernel en get_user_pages_fast
  • En Linux se puede pedir el uso de huge pages asignando memoria alineada a 2MiB y llamando a madvise(..., MADV_HUGEPAGE)
  • Al aplicar huge pages, el throughput sube a 51.0GiB/s
  • La mejora no ocurre porque struct page apunte directamente a toda una página de 2MiB
    • El código del kernel normalmente asume que struct page apunta al tamaño de página estándar de la arquitectura actual
    • Una huge page se representa con una struct page head y varias struct page tail
    • Una huge page de 2MiB puede representarse con hasta 512 struct page si se toma 4KiB como base
  • Aun así, después de encontrar la primera entrada, las struct page siguientes pueden generarse con un loop simple, reduciendo el costo de recorrer repetidamente la tabla de páginas
  • En kernels posteriores a Linux 5.17, existe struct folio, que identifica explícitamente la head page y reduce la necesidad de comprobar en runtime si una página es head o tail

Reducir el costo de sincronización con busy loop

  • Después de aplicar huge pages, en perf destacan los tiempos de wait_for_space y __wake_up_common_lock
    • costo de esperar espacio disponible para escritura
    • costo de despertar al lado lector
  • Para evitar este costo de sincronización se puede usar SPLICE_F_NONBLOCK en vmsplice y splice
    • si no se puede escribir en el pipe, devuelve EAGAIN de inmediato
    • quien llama entra en un busy loop hasta que esté listo
  • Al aplicar busy loop, el throughput sube hasta 62.5GiB/s
  • El costo también es claro
    • mientras espera a que vmsplice o splice estén listos, ocupa por completo un core de CPU
    • es una forma de cambiar mayor uso de CPU por menor latencia o mayor throughput
  • Al final, este benchmark sintético mejora desde cerca de 3.5GiB/s hasta alrededor de 65GiB/s

Detalles pendientes y temas prácticos

  • El proceso de optimización se hizo mirando en conjunto la salida de perf y el código fuente de Linux
  • Los temas tratados se conectan con cuestiones más amplias de programación de alto rendimiento, más allá de los pipes y del splicing en sí

    • Operaciones sin copia

      • ring buffer
      • paginación y memoria virtual
      • overhead de sincronización
      • en código real, se asignan los dos buffers por separado para reducir la contención en las tablas de páginas
      • get_user_pages incrementa el contador de referencias de las entradas de la tabla de páginas y put_page lo reduce
      • si ambos buffers usan entradas distintas de la tabla de páginas, se reduce la contención al modificar esos contadores de referencia
      • la prueba se ejecuta fijando los procesos ./write y ./read a dos cores con taskset
      • el repositorio también incluye un benchmark sintético para get_user_pages_fast
      • se puede medir la diferencia de velocidad según se usen o no huge pages
      • el splicing sigue siendo un concepto ambiguo y riesgoso, y los problemas relacionados siguen siendo una carga constante para los desarrolladores del kernel

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-10-06
Opiniones en Hacker News

  • Si entendí bien, vmsplice, cuando se usa al mismo tiempo en ambos extremos —el de lectura y el de escritura—, parece más cercano a un pequeño mecanismo de memoria compartida entre dos procesos.
    Es decir, ambos procesos tienen que ser extremadamente cuidadosos sobre cuándo leer y escribir el búfer, y cómo devolverlo después de usarlo. Es una forma rápida, pero también intimidante; además, es una lástima que la implementación ingenua que cualquiera escribiría sea 20 veces más lenta que el rendimiento posible.

    • Si intentas escribir la versión 20 veces más rápida, tus colegas probablemente pensarán que la estás complicando demasiado y que no trabajas en equipo.
    • No parece que vmsplice sea un pequeño mecanismo de memoria compartida entre dos procesos. Solo admite zero-copy desde la memoria de usuario hacia el pipe; en la dirección contraria sí hay copia.
      Para más detalles, ver https://mazzo.li/posts/fast-pipes.html#fn10

  • Me pregunto si existe alguna biblioteca de procesamiento de datos que abstraiga pipes, sockets, archivos y memoria, y que además haga este tipo de optimizaciones.
    Me gustaría saber si hay alguna biblioteca así en C, C++, Rust u otro lenguaje de sistemas. No estoy familiarizado con API como splice() y vmsplice() mencionadas en el artículo, así que me surge la duda de si existe alguna biblioteca que, al crear aplicaciones de bajo nivel, aproveche automáticamente estas optimizaciones cuando sea posible. También me pregunto si libuv, tokio o Netty se encargan de esto automáticamente en Linux; por lo que busqué rápidamente, parece que tal vez sí.

    • Puede que vaya contra la corriente general, pero esto no es portable, así que no vale mucho la pena abstraerlo. Lo más probable es que termines implementándolo directamente donde lo necesites.
      El código de más alto nivel usa estas funciones solo rara vez, porque son bastante especializadas y hay que adaptarlas específicamente a Linux. Si solo vas a mover datos en Linux sin inspeccionarlos, splice es útil. Para aplicaciones como proxies TCP/UDP definitivamente lo necesitas, pero no encaja tanto en un servidor HTTP común. Si estás construyendo este tipo de apps, te vas a topar con frecuencia con términos como zero copy, y splice será uno de los primeros resultados que veas.
    • Hay un crate para tokio. No es automático, pero puede ser interesante: https://lib.rs/crates/tokio-splice
    • Vale la pena mirar Cosh. Ahora estoy leyendo ese paper y pensándolo; es un modelo que ofrece una abstracción de paso de mensajes, pero permite optimizaciones.
      Fuera del entorno de investigación no parece ser muy conocido, y escribir una implementación eficiente de Cosh probablemente llevaría bastante tiempo. En resumen, tiene tres modos de transferencia: move, share y copy. Por ejemplo, una transferencia move entrega por completo al receptor datos sobre los que el emisor tenía permisos de lectura/escritura, y podría implementarse mediante remapeo de memoria virtual en la tabla de páginas. También tiene atributos strong/weak que indican si se puede confiar en que el emisor y el receptor cooperan, o si deben aislarse estrictamente mediante remapeo de permisos de memoria virtual. Sinceramente, no sé si podría optimizarse lo suficiente como para igualar de forma confiable algo como un pipe hiperoptimizado; tal vez termine siendo un problema de “compilador suficientemente inteligente”. Aun así, creo que vale la pena intentarlo.
      [1] https://barrelfish.org/publications/trios14-baumann-cosh.pdf

  • Discusión anterior a 2022: https://news.ycombinator.com/item?id=31592934

  • Un hecho sorprendente que descubrí por casualidad hace 4 años es que usar pipes de Linux puede producir comportamiento no determinista
    https://www.gibney.org/the_output_of_linux_pipes_can_be_inde...

    • No es tan sorprendente. El pipe que se creó en realidad no transmite nada de los datos que se hicieron con echo
      (echo red; echo green 1>&2) | echo blue crea dos subshells a cada lado del símbolo |. Un subshell es un proceso hijo del shell actual, así que hereda propiedades importantes como la tabla de descriptores de archivos abiertos. Los dos subshells se ejecutan al mismo tiempo, y el shell padre solo hace wait() hasta que terminen todos los procesos hijos. En general no se puede predecir cuál hijo se ejecutará primero, y en un sistema multicore incluso pueden ejecutarse literalmente al mismo tiempo. La salida estándar del subshell de la izquierda queda conectada al extremo de escritura del pipe, y la entrada estándar del subshell de la derecha al extremo de lectura. Pero echo blue no lee la entrada, solo escribe salida, así que no se lee nada del pipe. echo green >&2 envía la salida estándar a donde apunte el error estándar, no al pipe. Al final, echo green y echo blue escriben en el mismo archivo, probablemente directamente en la terminal, lo que crea una condición de carrera, y el orden depende de cuál se programe primero
    • Si se piensa un poco más a fondo, es completamente natural. Los programas de un pipeline se ejecutan al mismo tiempo
      Si no fuera así, los pipelines no serían útiles. Por ejemplo, en un pipeline que descarga un archivo tar con curl y lo descomprime de inmediato, si se esperara a que curl terminara para ejecutar tar, aparecerían problemas como dónde guardar el gran archivo tar intermedio. tar tiene que ejecutarse junto con curl para mantener pequeño el búfer y correr rápido. El único flujo de control entre programas de un pipeline se da por la entrada estándar y la salida estándar. En el ejemplo se está escribiendo al error estándar, así que obviamente no forma parte de un flujo de control determinista
    • Si te gusta la E/S sin copia rápida en Linux, este artículo también vale la pena
      Además, para evitar confusiones, “Indeterministic” es un término filosófico; el término de ciencias de la computación es “nondeterministic”
      0. https://blog.superpat.com/zero-copy-in-linux-with-sendfile-a...
    • ¿Eso es tan sorprendente? Sería más fácil aclarar la confusión si supiéramos qué salida se esperaba y por qué se pensaba eso
      Este comando probablemente está hecho a propósito para verse raro, y cualquier revisor de código sin duda habría levantado una ceja. Está echo red, pero no se transmite a ningún lado. Quizá sea un chiste de “red herring”. echo green va al error estándar, así que solo se ve antes que echo blue si termina primero. El orden exacto depende del buffering de salida, que a su vez depende de qué time slice se asigne primero, y cambia según la cantidad de CPU y la carga. Por eso es no determinista, pero del mismo modo en que top es no determinista
    • ¿Hay casos en los que esto cause problemas reales? Sinceramente, este ejemplo se ve bastante artificial

  • En resumen, suponiendo que los dos programas estén escritos de la forma más óptima posible, la velocidad máxima de un pipe se acerca a la velocidad a la que un core del sistema puede leer y escribir
    En esencia, como el kernel mapea las mismas páginas de memoria física desde la salida estándar de un programa hacia la entrada estándar de otro, el trabajo se vuelve sin copia o, en situaciones menos óptimas, cercano a una copia única rápida. Una vez que se sabe esto, resulta satisfactorio y hasta gracioso hacer tareas de altísimo rendimiento con scripts de shell que conectan dos o más herramientas mediante pipes. Es una de las herramientas más útiles de la caja

    • Los pipes son sin copia solo cuando se usa splice o vmsplice. Estas llamadas al sistema específicas de Linux son difíciles de usar, especialmente vmsplice
      La gran mayoría de los programas y filtros de shell, salvo excepciones llamativas como pv, no las usan, así que pagan el costo de copiar a memoria del kernel y volver a sacar los datos
    • Según entiendo, una limitación seria de los pipes es que, en Linux x86, solo pueden bufferizar 64 KB / 16 páginas. En general, probablemente sea más lento que el ancho de banda core-memoria
    • Por eso no es tan importante como creen muchos programadores con muchos hilos
      Según las características de carga, la aplicación que estás construyendo probablemente pueda implementarse de forma más limpia con pipes+procesos o con hilos verdes/de espacio de usuario. Puede ser menos cómodo, pero el paso de mensajes suele ser mejor que el infierno de los deadlocks
    • Lo gracioso es que personas o equipos gastan semanas y mucho dinero para obtener peores resultados
    • No entiendo bien esta magia de sistemas, pero ¿los datos tienen que subir completamente hasta la memoria? ¿O la caché evita ese viaje de ida y vuelta?

  • Este artículo trata sobre cómo hacer más rápidos los pipes de Linux, pero otros métodos como la memoria compartida o las colas de mensajes aún pueden ser más rápidos
    En sistemas donde se necesita mover muchos datos rápidamente, los pasos adicionales de los pipes pueden reducir la velocidad. Cuando varios hilos comparten datos, los pipes también pueden crear más problemas que otros enfoques. Por eso, las mejoras del artículo quizá no ayuden mucho en situaciones reales donde la velocidad es importante

    • ¿Puedes dar un ejemplo? Cuando se procesan datos por lotes, elegir algo como io_uring tiene ventajas
      Pero en la comunicación bidireccional, cualquiera de las dos partes necesita una notificación de que los datos están listos. Tal vez no quieras quemar CPU haciendo polling, y no tengo claro cómo esas opciones manejarían esa sincronización más rápido que un pipe
    • Usar una biblioteca de colas de mensajes también tiene la ventaja de que hay que preocuparse menos por incompatibilidades entre varias plataformas

  • Sabía de cosas como las tablas de páginas, pero al conectarlo con el análisis de rendimiento mediante perf, queda claro lo centrales que son para el throughput

  • Los pipes son excelentes. Sinceramente, no importa mucho si el otro proceso está en otro CPU o en otra máquina
    https://github.com/nathants/s4/blob/master/examples/nyc_taxi...

  • Los pipes son lo bastante rápidos como para combinar repetidamente cat, sed, awk, cut, grep, uniq, jq, etc.