lsr - o `ls` ultrarrápido baseado em io_uring

• lsr é um novo programa substituto do ls(1), desenvolvido com a biblioteca de IO ourio, baseada em io_uring
• Em comparação com o ls tradicional e ferramentas alternativas (eza, lsd, uutils ls), a execução do comando é muito mais rápida e o número de chamadas de sistema é mais de 10 vezes menor
• Para maximizar o desempenho, toda a IO principal, como abertura de diretórios, stat e lstat, é processada de forma assíncrona e em lote com io_uring. Quanto mais arquivos houver, mais rápido ele fica
• Usa o StackFallbackAllocator do Zig para minimizar chamadas a mmap durante a alocação de memória
• É compilado estaticamente, sem linkagem dinâmica, então até o tamanho do executável é menor que o do ls tradicional

---

Introdução e relevância

• O projeto lsr é uma alternativa ao comando ls comum, uma ferramenta rápida de listagem de diretórios que usa io_uring
• Em comparação com ls, eza, lsd e uutils ls, ele apresenta desempenho excepcional em velocidade de execução e uso de chamadas de sistema
• Executa o máximo possível de IO diretamente com a biblioteca de IO desenvolvida pelo próprio autor, ourio
• Os benchmarks mostram que o lsr comprova desempenho rápido e qualidade mesmo em ambientes com grande volume de arquivos

Resultados de benchmark

• Foi usado hyperfine para medir o tempo de execução de cada comando em diretórios com n arquivos regulares
  • Com lsr -al, no intervalo de 10 a 10.000 arquivos, ele registrou tempos de execução muito menores que os do ls tradicional e de suas alternativas
  • Exemplo: com 10.000 arquivos, o lsr registrou 22,1 ms, superando o ls tradicional (38,0 ms), eza (40,2 ms), lsd (153,4 ms) e uutils ls (89,6 ms), alcançando a melhor velocidade
• A contagem de chamadas de sistema foi feita com strace -c
  • lsr -al: de no mínimo 20 chamadas (n=10) até no máximo 848 (n=10.000), mantendo uma contagem muito baixa
  • O ls chegou a 30.396 chamadas (n=10.000), e o lsd a 100.512; as demais alternativas também ficaram na faixa de milhares a centenas de milhares
  • Nas mesmas condições, o lsr alcançou a melhor eficiência com pelo menos 10 vezes menos syscalls

Estrutura e implementação do lsr

• O programa funciona em três etapas: parse de argumentos, coleta de dados e saída de dados
• Toda a IO acontece na segunda etapa, de coleta de dados, e todo acesso a arquivos e consulta de informações possível é tratado com io_uring
  • Abertura do diretório de destino, stat, lstat e consulta de informações de tempo/usuário/grupo são todos executados com base em io_uring
  • O processamento em lote de stat reduz drasticamente o número de chamadas de sistema
• Com o Zig StackFallbackAllocator, 1 MB de memória é pré-alocado para minimizar chamadas adicionais de sistema, como mmap

Build estático e otimização

• Como é um build totalmente estático, sem linkagem dinâmica com libc, o overhead de execução é significativamente menor
• Em comparação com o GNU ls, o tamanho do build ReleaseSmall do lsr é menor: 138,7 KB vs 79,3 KB
• Porém, o lsr não tem suporte a locale (idioma/região). O ls comum tem overhead por oferecer suporte a vários idiomas

Análise de chamadas de sistema e problemas de desempenho

• O lsd chama clock_gettime mais de 5 vezes por arquivo; o motivo é desconhecido (supõe-se medição interna de tempo, etc.)
• A tarefa de ordenação (sorting) representa uma parte significativa do trabalho total (cerca de 30%)
  • O uutils ls é eficiente em chamadas de sistema, mas fica mais lento no processamento de ordenação
• Só a adoção de io_uring já confirma o potencial de ganhos revolucionários de desempenho em ambientes de IO de alta carga, como servidores

Conclusão

• O tempo de desenvolvimento também não foi longo, e o efeito da otimização de syscalls superou as expectativas
• O lsr é um substituto experimental do ls que alcança ao mesmo tempo alta velocidade, poucas chamadas de sistema e tamanho enxuto
• É muito adequado para ambientes com grande volume de arquivos ou sistemas em que IO de alto desempenho é importante
• Embora tenha algumas limitações de funcionalidade, como a falta de suporte a locale, ele mostra resultados inovadores tanto na prática quanto nos benchmarks

[GN⁺]

Comentários no Hacker News

• O autor do projeto se identificou e comentou que é possível ver um texto de apresentação sobre o lsr baseado em io_uring aqui

  • Compartilhou a experiência de ter trabalhado em um projeto de I18N na Sun. Para oferecer suporte a vários ambientes (localização, utf8 etc.), é preciso adicionar vários tratamentos ao programa, então o custo para produzir o resultado e a velocidade tendem a ser inversamente proporcionais. O ls(1) original do UNIX era extremamente rápido por causa do design simples, mas foi ficando mais lento com o acúmulo de pequenos custos de vários recursos extras, VFS, vários conjuntos de caracteres, suporte a cores etc. Achou que isso rende uma discussão interessante sobre o custo de abstração que o io_uring lida
  • O projeto bfs também usa io_uring (link do código-fonte). Ficou curioso sobre a comparação de desempenho entre lsr e bfs -ls. Atualmente o bfs usa io_uring apenas em multithreading, mas talvez valha pensar em usar também em single thread (bfs -j1)
  • Medir tempo com tim (link de apresentação) talvez seja melhor do que com hyperfine. Como foi escrito em Nim, pode ser um desafio, mas é engraçado como os nomes se parecem por coincidência
  • Está pensando em portar um projeto em C++ para Zig. A libevring que criou ainda está no começo, então mantém a mente aberta para substituí-la por ourio, se necessário. Acha que, se projetos baseados em Zig oferecerem suporte a bindings para C/C++, isso pode ser útil na migração de C/C++ para Zig
  • Como esse texto de apresentação explica melhor o contexto, pretende usá-lo como link principal e adicionar a thread do repositório acima

• Fiquei curioso sobre como seria o desempenho do lsr em um servidor NFS, especialmente em um ambiente de rede ruim. É evidente que usar syscalls POSIX bloqueantes em um serviço de rede instável é uma desvantagem do design do NFS. Também seria interessante observar o quanto o io_uring consegue aliviar esse problema

  • Os projetistas do NFS implementaram sistemas distribuídos para se comportarem de forma muito consistente, como se fossem discos rígidos. Era uma vantagem que ferramentas existentes (ls etc.) não precisassem lidar diretamente com erros de rede. O protocolo NFS original não guardava estado, então mesmo após reinicializar o servidor o cliente se recuperava automaticamente. Fico curioso se o io_uring repassa corretamente os erros nesses casos. Também interessa saber como isso é tratado em timeouts de NFS
  • Em casa, usa $HOME via NFS em vários PCs e considera a usabilidade média do NFS bastante satisfatória, desde que a rede seja boa e se evitem casos mais complicados como escrita paralela. Dito isso, já sofreu bastante quando o cabo de rede estava instável por causa das desconexões
  • É um incômodo conhecido quando ctrl+c não funciona em apps que estão lendo uma pasta NFS. Em teoria, a opção de montagem intr permitia interromper operações em andamento em um servidor remoto ao entregar um sinal, mas no Linux isso já foi removido há muito tempo (hoje só resta a opção soft) (referência 1, referência 2, suporte no FreeBSD)
  • O Samba também tem um problema parecido

• É interessante que, mesmo reduzindo em 35 vezes o número de chamadas de syscall, a melhora de velocidade tenha sido de só cerca de 2 vezes

  • A maioria das syscalls é feita por meio do VDSO, então o custo não é tão alto
  • Em benchmarks sobre io_uring que leu no passado, às vezes as syscalls baseadas em io_uring apareciam como mais pesadas do que as syscalls tradicionais. Mesmo assim, na prática a melhora parece bem grande. Não lembra a fonte exata, mas isso ficou marcado

• O projeto chama mais atenção como exemplo de uso de io_uring para ganhos de desempenho de longo prazo, ou como introdução/tutorial de uso, do que pelo ganho prático em si. Em comparação com ferramentas existentes como eza, não parecia haver uma motivação intuitiva clara para precisar disso. Se listar dez mil arquivos leva 40 ms contra 20 ms, provavelmente não daria para sentir diferença nenhuma em uma execução isolada

  • É um projeto experimental feito por diversão para aprender a usar io_uring. O ganho real de tempo é pequeno (algo como economizar 5 segundos ao longo da vida), e esse nunca foi o ponto principal
  • Na prática, em diretórios com milhões de arquivos JSON, executar ls/du leva vários minutos. Os comandos padrão do coreutils muitas vezes não conseguem aproveitar direito o desempenho de SSDs modernos

• O lsr é legal, mas o suporte a cores e ícones do eza é melhor. A pessoa usa a configuração eza --icons=always -1, então arquivos de música (.opus etc.) já aparecem com ícone e cor automaticamente, enquanto no lsr são mostrados só como arquivos comuns. Ainda assim, ficou claro para ela que o lsr é fácil de aplicar patch e extremamente rápido. Também criou expectativa de ver cat e outros utilitários feitos nesse estilo, achou curioso o uso de tangled.sh e atproto, e por ter sido escrito em Zig parece mais acessível para iniciantes do que Rust

  • bat é um substituto moderno para cat (bat aqui)
  • Para suporte a cores, o ideal provavelmente é implementar uma forma padrão como LS_COLORS/dircolors. O GNU ls tem cores bonitas

• Ficou curioso sobre por que nem todas as ferramentas de CLI usam io_uring. Ao conectar um nvme em usb 3.2 gen2, com ferramentas comuns obtém 740 MB/s, mas com ferramentas baseadas em aio ou io_uring chega a 1005 MB/s. Acha que isso também tem a ver com estratégia de profundidade de fila e redução de locks

  • Para manter portabilidade, tradicionalmente os programas eram escritos sem ramificações por macros como #ifdef, então a adoção de novas tecnologias específicas de plataforma/versão é lenta. Hoje em dia, acha que a vantagem da compatibilidade entre várias plataformas tipo POSIX já não é tão grande quanto antes
  • Para usar io_uring com eficiência, é preciso um modelo assíncrono orientado a eventos. A maioria das ferramentas de CLI existentes foi escrita de forma intuitiva e sequencial. Se async fosse algo natural no nível da linguagem, talvez a migração fosse mais fácil, mas hoje seria preciso um grande refactor. O io_uring também ainda não está totalmente estabilizado, então talvez valha observar o surgimento de tecnologias novas ou até ferramentas/IA de migração automática
  • O io_uring teve problemas graves de segurança no começo da adoção, por volta de 2 anos atrás. Hoje muitos já foram resolvidos, mas isso prejudicou a disseminação
  • O io_uring é muito difícil do ponto de vista de segurança
  • Como o io_uring ainda é uma tecnologia muito nova, o coreutils (e seus pacotes predecessores) carrega uma tradição de décadas, então a adoção ainda deve demorar. Vai levar tempo até que syscalls em modelo de “buffer circular compartilhado” se tornem padrão no lugar do modelo síncrono existente

• No strace, foi observado que o lsd chama clock_gettime algo como 5 vezes por arquivo. Não se sabe exatamente o motivo; talvez seja para calcular expressões como “há tantos minutos/horas/dias” para cada timestamp, ou talvez seja legado de alguma biblioteca

  • Hoje em dia clock_gettime não é uma syscall de verdade, e sim algo tratado via vDSO (veja man 7 vDSO). Fica a dúvida se o Zig não estaria aproveitando essa estrutura

• Fugindo um pouco do assunto, surgiu curiosidade sobre, em servidores enterprise com Mellanox 4 ou 5 e NIC de 10G, quanto o io_uring reduz na prática o overhead de latência de socket em microssegundos em comparação com LD_PRELOAD. Parece que os efeitos não se acumulam, e gostaria de ouvir números concretos de experiência real ou benchmarks

• O io_uring não oferece suporte a getdents, então o principal ganho aparece em stat em lote (por exemplo, ls -l). Fica a sensação de que seria bom se desse para tornar o processamento de getdents assíncrono e sobreposto

  • Se o POSIX padronizasse a operação “readdirplus” do NFS (getdents + stat), parte da vantagem específica do io_uring provavelmente seria anulada

• Parece engraçado haver ícones para extensões .mjs e .cjs, mas não para extensões como .c, .h e .sh