Qual é a velocidade de um pipe no Linux? (2022)

 (mazzo.li)
1 pontos por GN⁺ 2023-10-06 | 1 comentários | Compartilhar no WhatsApp
  • Acompanhando a taxa de transferência de pipes no Linux com perf e análise do caminho no kernel, uma implementação simples baseada em write/read foi levada dos 3.7GiB/s iniciais até 62.5GiB/s no fim
  • O ponto de partida do gargalo é que o pipe funciona como um buffer em anel que guarda referências a páginas de 4KiB, pagando ao mesmo tempo os custos de cópia, alocação de páginas, locks e espera/despertar
  • vmsplice e splice reduzem a cópia entre memória de usuário e buffers do kernel, elevando a taxa de transferência para cerca de 12.7GiB/s e 32.8GiB/s, respectivamente
  • Depois disso, o custo de converter faixas de endereços virtuais em struct page passa a se destacar, e o uso de huge pages de 2MiB reduz a carga da navegação pela tabela de páginas, chegando a 51.0GiB/s
  • A otimização final, com SPLICE_F_NONBLOCK e busy loop, aumenta ainda mais a taxa de transferência, mas mantém o núcleo de CPU ocupado enquanto espera o estado de prontidão

Objetivo do experimento e desempenho de referência

  • O objetivo é observar como os pipes Unix são implementados no Linux e otimizar gradualmente um programa de teste que escreve e lê dados de um pipe
  • O ambiente de testes usa uma CPU Intel Skylake i7-8550U e Linux 5.17; como a implementação interna do Linux muda continuamente, os números podem variar conforme o ambiente
  • O ponto de partida é um programa que envia repetidamente um buffer de 256KiB para o pipe usando as system calls write e read
    • write continua escrevendo o mesmo buffer de 256KiB
    • read lê um total de 10GiB e imprime a taxa de transferência
    • O código está em pipes-speed-test
  • Como referência de comparação, um programa FizzBuzz altamente otimizado produz cerca de 36.2GiB/s medidos com pv
    • O FizzBuzz usa blocos de 256KiB, o mesmo tamanho do cache L2
    • Este experimento também usa blocos de 256KiB, mas sem calcular o conteúdo da saída, para observar um valor mais próximo do limite de IO do pipe
  • O resultado da primeira implementação foi o seguinte
    • ./write | ./read
    • 3.7GiB/s, buffer de 256KiB, 40960 repetições, total de 10GiB transferidos

Por que write e read são lentos

  • Verificando com perf record -g e perf report, cerca de 47% do tempo do lado de write é gasto em pipe_write
  • Dentro de pipe_write, copy_page_from_iter e __alloc_pages têm grande peso
    • cópia de dados
    • alocação de páginas
    • escalonamento
    • espera e despertar
    • aquisição e liberação de locks
  • Um pipe no Linux é um buffer em anel que contém referências a páginas
    • pipe_inode_info possui head, tail e um array de pipe_buffer
    • pipe_buffer contém struct page *page, offset e len
    • No x86-64, o tamanho normal de página é 4KiB
    • O número padrão de slots do buffer em anel é 16, e no exemplo um pipe com 8 slots pode armazenar no máximo 32KiB
  • head representa a ponta de escrita e tail a ponta de leitura
    • quando o pipe enche, write bloqueia
    • quando o pipe está vazio, read bloqueia
  • pipe_write normalmente segue a sequência abaixo
    • se o pipe já estiver cheio, espera até surgir espaço
    • se houver espaço no buffer apontado pelo head atual, ele o preenche primeiro
    • se houver slots vazios e ainda restarem dados, aloca novas páginas, preenche e atualiza o head
  • pipe_read faz o inverso: consome páginas, libera as páginas totalmente lidas e atualiza o tail
  • Nesse caminho, cada página é copiada duas vezes
    • uma da memória do usuário para o kernel
    • outra do kernel de volta para a memória do usuário
  • As cópias ocorrem em unidades de páginas de 4KiB, misturadas com sincronização e alocação/liberação de páginas
  • Na mesma máquina, uma leitura sequencial de RAM em thread única foi de cerca de 16GiB/s; considerando a complexidade do caminho do pipe, não é surpreendente que write/read sejam cerca de 4 vezes mais lentos

Reduzindo cópias com vmsplice e splice

  • Em IO rápido, o custo de cópia entre memória do usuário e buffers do kernel pode virar gargalo
  • O Linux fornece system calls relacionadas a pipes para movimentação sem cópia
    • splice: move dados entre um pipe e um descritor de arquivo
    • vmsplice: move dados da memória do usuário para um pipe
  • vmsplice usa um array de struct iovec para indicar os buffers que entrarão no pipe
    • o valor de retorno é o número de bytes realmente colocados no pipe
    • por causa do limite de tamanho do buffer em anel do pipe, o tamanho total pedido pode não entrar de uma vez só
  • vmsplice conecta a memória do usuário ao pipe sem copiar, então é preciso tomar cuidado para não reutilizar o buffer antes que o lado leitor consuma os dados
  • O programa FizzBuzz usa double buffering para isso
    • divide um buffer de 256KiB em duas metades de 128KiB
    • define o tamanho do pipe como 128KiB, criando 32 slots com páginas de 4KiB
    • preenche alternadamente as duas metades e as envia ao pipe com vmsplice
  • O programa de teste na prática não reescreve o conteúdo do buffer, mas mantém o double buffering por ser semelhante à estrutura necessária em programas reais de geração de saída
  • Ao trocar write por vmsplice, a taxa de transferência sobe para 12.7GiB/s
    • o volume de cópia cai pela metade
    • melhoria de mais de 3 vezes em relação a write/read
  • Trocando também o lado de leitura por splice, toda a cópia é removida e o resultado chega a 32.8GiB/s
  • Ainda assim, a segurança de vmsplice exige cuidado
    • se a página for novamente submetida a splice, sua vida útil pode se estender
    • não está claro se é inseguro mesmo sem SPLICE_F_GIFT
    • usar pipes zero-copy com segurança exige atenção especial

iov_iter_get_pages e o custo de conversão de páginas

  • Depois de aplicar vmsplice e splice, o perf passa a mostrar bastante tempo no caminho de vmsplice
    • iov_iter_get_pages
    • __mutex_lock.constprop.0
    • add_to_pipe
  • iov_iter_get_pages converte a faixa de memória virtual do struct iovec passado para vmsplice em uma lista de struct page que o pipe pode armazenar
  • Processos usam endereços virtuais, não endereços físicos de memória
    • a CPU converte endereços virtuais em físicos por meio da tabela de páginas
    • no x86-64, o tamanho normal de página é 4KiB
    • a tabela de páginas do x86-64 costuma ser descrita como uma árvore de 4 níveis com 512 entradas por nível
  • O pipe_buffer do pipe referencia struct page
    • struct page é a estrutura central usada pelo kernel para lidar com páginas físicas e seus metadados associados
    • portanto, vmsplice precisa converter a faixa de memória virtual de entrada em referências a páginas físicas
  • A maior parte do tempo dentro de iov_iter_get_pages é gasta em get_user_pages_fast
    • com um buffer de 128KiB e páginas de 4KiB, é preciso obter um total de 32 páginas
    • o código do pipe, por implementação, chama com nr_pages = 16 por vez e repete se necessário, mas o total de páginas submetidas por splice continua sendo 32
  • get_user_pages_fast percorre a tabela de páginas em software, de forma parecida com o que a CPU faz, para coletar struct page
  • Enquanto o chamador usa as páginas, é preciso aumentar o contador de referência de cada struct page para impedir que a página física seja reutilizada
    • depois, put_page precisa reduzir esse contador de referência
  • Preencher o buffer com memset no início faz com que as entradas da tabela de páginas sejam criadas antecipadamente, evitando o caminho lento de get_user_pages_fast
    • sem memset, no exemplo a taxa de transferência cai para 25.0GiB/s
    • com huge pages, esse fenômeno não aparece da mesma forma

Reduzindo o custo de páginas com huge pages

  • Além das páginas normais de 4KiB, o x86-64 suporta huge pages de 2MiB e 1GiB
    • os experimentos seguintes tratam apenas de huge pages de 2MiB
    • páginas de 1GiB são relativamente raras e consideradas excessivas para este caso
  • Huge pages representam a mesma faixa de memória com menos páginas, reduzindo o custo de gerenciamento
    • ao converter endereço virtual em físico, também se elimina um nível da tabela de páginas
    • isso também pode ajudar a reduzir a carga sobre a TLB da CPU
  • Neste experimento, o gargalo direto não é a caminhada de hardware pela tabela de páginas, e sim o caminho em software do kernel em get_user_pages_fast
  • No Linux, é possível solicitar o uso de huge pages alocando memória alinhada a 2MiB e chamando madvise(..., MADV_HUGEPAGE)
  • Com huge pages, a taxa de transferência sobe para 51.0GiB/s
  • O motivo da melhora não é que uma única struct page passe a apontar diretamente para uma página de 2MiB inteira
    • o código do kernel em geral assume que struct page aponta para a página de tamanho padrão da arquitetura atual
    • huge pages são representadas por uma struct page head e várias struct page tail
    • uma huge page de 2MiB pode ser representada por até 512 struct page no padrão de 4KiB
  • Ainda assim, depois de encontrar a primeira entrada, as struct page seguintes podem ser geradas com um loop simples, reduzindo o custo de percorrer a tabela de páginas várias vezes
  • Em kernels após o Linux 5.17, existe struct folio, que identifica explicitamente a head page e reduz a necessidade de verificar head/tail em tempo de execução

Reduzindo o custo de sincronização com busy loop

  • Depois de aplicar huge pages, o perf destaca o tempo em wait_for_space e __wake_up_common_lock
    • custo de esperar por espaço disponível para escrita
    • custo de acordar o lado leitor
  • Para evitar esse custo de sincronização, é possível usar SPLICE_F_NONBLOCK com vmsplice e splice
    • se não for possível escrever no pipe, a chamada retorna EAGAIN imediatamente
    • o chamador entra em busy loop até ficar pronto
  • Com busy loop, a taxa de transferência sobe até 62.5GiB/s
  • O custo também é claro
    • enquanto espera vmsplice ou splice ficarem prontos, o núcleo de CPU fica totalmente ocupado
    • é uma troca de mais uso de CPU por menor latência ou maior taxa de transferência
  • No fim, esse benchmark sintético melhorou de cerca de 3.5GiB/s para algo em torno de 65GiB/s

Detalhes restantes e temas práticos

  • O processo de otimização foi conduzido observando a saída do perf junto com o código-fonte do Linux
  • Os temas tratados se conectam a tópicos mais amplos de programação de alto desempenho, indo além de pipes e splicing em si

    • operações sem cópia

      • buffers em anel
      • paginação e memória virtual
      • overhead de sincronização
      • em código real, os dois buffers são alocados separadamente para reduzir contenção na tabela de páginas
      • get_user_pages aumenta o contador de referência das entradas da tabela de páginas e put_page o reduz
      • se os dois buffers usarem entradas diferentes da tabela de páginas, a contenção ao modificar esses contadores de referência diminui
      • o teste foi executado com taskset, fixando os processos ./write e ./read em dois núcleos
      • o repositório também inclui um benchmark sintético para get_user_pages_fast
      • é possível medir a diferença de velocidade conforme o uso ou não de huge pages
      • o splicing continua sendo um conceito ambíguo e arriscado, e os problemas relacionados seguem pesando para os desenvolvedores do kernel

Leituras relacionadas

1 comentários

 
GN⁺ 2023-10-06
Opiniões no Hacker News

  • Se entendi corretamente, vmsplice parece mais um pequeno mecanismo de memória compartilhada entre dois processos quando usado simultaneamente nas duas pontas, a de leitura e a de escrita
    Ou seja, ambos os processos precisam tomar extremo cuidado com quando ler e escrever no buffer e como devolvê-lo após o uso. É um método rápido, mas ao mesmo tempo assustador, e também é uma pena que a implementação ingênua que todo mundo provavelmente escreveria seja 20 vezes mais lenta do que o desempenho possível

    • Se você tentar escrever a versão 20 vezes mais rápida, seus colegas vão achar que você está complicando demais e não agindo como alguém que joga em equipe
    • Não acho que vmsplice seja um pequeno mecanismo de memória compartilhada entre dois processos. Ele só oferece cópia zero da memória do usuário para o pipe; no sentido inverso, há cópia
      Para mais detalhes, veja https://mazzo.li/posts/fast-pipes.html#fn10

  • Fico curioso se existe alguma biblioteca de processamento de dados que abstraia pipes, sockets, arquivos e memória e ainda faça essas otimizações
    Gostaria de saber se há uma biblioteca assim em C, C++, Rust ou outra linguagem de sistemas. Como não estou familiarizado com APIs como splice() e vmsplice() mencionadas no texto, fiquei pensando se, ao criar aplicações de baixo nível, haveria alguma biblioteca que aproveitasse automaticamente essas otimizações quando possível. Também fico curioso se libuv, tokio e Netty tratam isso automaticamente no Linux; pelo que procurei rapidamente, talvez seja o caso

    • Pode ser diferente do fluxo comum, mas isso não é portável, então não há muito valor em abstrair. É bem provável que você acabe implementando diretamente em cada lugar onde precisar
      Código de nível mais alto usa esses recursos apenas raramente, porque eles têm propósito bastante específico e precisam ser especializados para Linux. Se você só vai mover dados no Linux sem inspecioná-los, splice é útil. Para aplicações como proxies TCP/UDP, ele é claramente necessário, mas não combina muito com um servidor HTTP comum. Se você estiver criando esse tipo de app, vai encontrar com frequência palavras-chave como zero copy, e splice será um dos primeiros resultados que verá
    • Existe um crate para tokio. Não é automático, mas pode ser interessante: https://lib.rs/crates/tokio-splice
    • Vale a pena dar uma olhada no Cosh. Estou lendo esse artigo agora e pensando sobre ele; é um modelo que oferece uma abstração de passagem de mensagens ao mesmo tempo em que permite otimizações
      Parece não ser muito conhecido fora do ambiente de pesquisa, e é bem possível que escrever uma implementação eficiente de Cosh leve bastante tempo. Resumindo, há três modos de transferência: move, share e copy. Por exemplo, uma transferência move entrega completamente ao receptor os dados sobre os quais o remetente tinha permissões de leitura/escrita, e pode ser implementada por remapeamento de memória virtual nas tabelas de páginas. Também existem atributos strong/weak que indicam se é possível confiar que remetente e receptor vão cooperar, ou se é preciso isolá-los rigorosamente por meio de remapeamento de permissões de memória virtual. Para ser sincero, não sei se isso pode ser otimizado bem o bastante para competir de forma confiável com algo como um pipe ultraotimizado, e talvez vire um problema de “compilador suficientemente inteligente”. Ainda assim, acho que vale tentar
      [1] https://barrelfish.org/publications/trios14-baumann-cosh.pdf

  • Discussão anterior a 2022: https://news.ycombinator.com/item?id=31592934

  • Um fato surpreendente que descobri por acaso há 4 anos é que usar pipes no Linux pode gerar comportamento não determinístico
    https://www.gibney.org/the_output_of_linux_pipes_can_be_inde...

    • Não é algo surpreendente. O pipe criado não transmite de fato nada dos dados enviados por echo
      (echo red; echo green 1>&2) | echo blue cria dois subshells separados pelo símbolo |. Como subshells são processos filhos do shell atual, eles herdam propriedades importantes, como a tabela de descritores de arquivos abertos. Os dois subshells executam ao mesmo tempo, e o shell pai apenas chama wait() até que todos os processos filhos terminem. Em geral, não dá para prever qual filho vai executar primeiro e, em sistemas multicore, eles podem literalmente executar simultaneamente. A saída padrão do subshell à esquerda é conectada à extremidade de escrita do pipe, e a entrada padrão do subshell à direita é conectada à extremidade de leitura. Mas echo blue não lê a entrada; ele apenas escreve na saída, então nada é lido do pipe. echo green >&2 envia a saída padrão para onde o erro padrão aponta, não para o pipe. No fim, echo green e echo blue escrevem diretamente no mesmo arquivo, provavelmente o terminal, criando uma condição de corrida, e a ordem depende de qual deles é escalonado primeiro
    • Pensando um pouco mais a fundo, isso é totalmente natural. Os programas em um pipeline executam simultaneamente
      Se não fosse assim, pipelines não seriam úteis. Por exemplo, em um pipeline que baixa um arquivo tar com curl e o extrai imediatamente, se fosse preciso esperar curl terminar para então executar tar, surgiriam problemas como onde armazenar o grande arquivo tar intermediário. O tar precisa rodar junto enquanto o curl está em execução para manter o buffer pequeno e executar rápido. O único fluxo de controle entre programas de um pipeline é feito por entrada padrão e saída padrão. No exemplo, a escrita está indo para o erro padrão, então naturalmente não faz parte de um fluxo de controle determinístico
    • Se você gosta de E/S sem cópia rápida no Linux, este texto também vale a leitura
      A propósito, para evitar confusão: “Indeterministic” é um termo da filosofia; o termo da ciência da computação é “nondeterministic”
      0. https://blog.superpat.com/zero-copy-in-linux-with-sendfile-a...
    • Isso é tão surpreendente assim? Acho que seria mais fácil desfazer a confusão sabendo qual saída a pessoa esperava e por que pensava assim
      Esse comando provavelmente foi feito de propósito para parecer estranho, e qualquer revisor de código certamente ficaria com a pulga atrás da orelha. Há um echo red, mas ele não é entregue a lugar nenhum. Pode até ser uma piada com “red herring”. echo green vai para o erro padrão, então só aparece se terminar antes de echo blue. A ordem exata depende do buffering de saída, que por sua vez depende de qual fatia de tempo é atribuída primeiro, variando conforme o número de CPUs e a carga. Então é não determinístico, mas do mesmo jeito que top é não determinístico
    • Há casos em que isso causa problemas reais? Sinceramente, este exemplo parece bastante artificial

  • Em resumo, supondo que os dois programas tenham sido escritos da forma mais otimizada possível, a velocidade máxima de um pipe fica próxima da velocidade com que um núcleo do sistema consegue ler e escrever
    Essencialmente, como o kernel mapeia as mesmas páginas de memória física da saída padrão de um programa para a entrada padrão de outro, a operação acaba sendo sem cópia ou, em situações menos ideais, próxima de uma cópia única rápida. Depois que se sabe disso, fazer tarefas de altíssimo desempenho com scripts de shell que conectam duas ou mais ferramentas por pipes é recompensador e até engraçado. É uma das ferramentas mais úteis da caixa

    • Pipes só são sem cópia quando se usa splice ou vmsplice. Essas chamadas de sistema específicas do Linux são difíceis de usar, especialmente vmsplice
      A maioria dos programas e filtros de shell, com exceções notáveis como pv, não as usa, então paga o custo de copiar para a memória do kernel e depois copiar de volta
    • Pelo que sei, uma limitação séria dos pipes é que, no Linux x86, eles só conseguem fazer buffer de 64 KB / 16 páginas. Em geral, é provável que isso seja mais lento que a largura de banda entre núcleo e memória
    • Por isso, threads não são tão importantes quanto muitos programadores imaginam
      Dependendo das características de carga, a aplicação que você está construindo pode muito bem ser implementada de forma mais limpa com pipes+processos ou com threads verdes/no espaço do usuário. Pode ser menos conveniente, mas passagem de mensagens geralmente é melhor que um inferno de deadlocks
    • É engraçado porque pessoas ou equipes gastam semanas e muito dinheiro para obter resultados piores
    • Não entendo muito dessa magia de sistemas, mas os dados precisam mesmo ir totalmente até a memória? Ou o cache impede esse trajeto de ida e volta?

  • Este texto trata de como tornar pipes no Linux mais rápidos, mas outros métodos, como memória compartilhada ou filas de mensagens, ainda podem ser mais rápidos
    Em sistemas que precisam mover muitos dados rapidamente, as etapas extras dos pipes podem reduzir a velocidade. Quando várias threads compartilham dados, pipes também podem criar mais problemas que outras abordagens. Por isso, as melhorias descritas no texto talvez não ajudem muito em situações reais em que velocidade é crucial

    • Você pode dar um exemplo? Ao processar dados em lotes, escolher algo como io_uring traz vantagens
      Mas, em comunicação bidirecional, qualquer um dos lados precisa de uma notificação de que os dados estão prontos. Talvez você não queira ficar gastando CPU com polling, e não vejo bem como essas alternativas tratariam essa sincronização mais rápido que pipes
    • Usar uma biblioteca de fila de mensagens também tem a vantagem de exigir menos preocupação com incompatibilidades entre várias plataformas

  • Eu já conhecia coisas como tabelas de páginas, mas conectar isso à análise de desempenho com perf deixa claro o quanto elas são centrais para a vazão

  • Pipes são excelentes. Sinceramente, pouco importa se o outro processo está em outra CPU ou em outra máquina
    https://github.com/nathants/s4/blob/master/examples/nyc_taxi...

  • Pipes são rápidos o suficiente para combinar repetidamente cat, sed, awk, cut, grep, uniq, jq etc.