Como o ksh93 é tão rápido?

9

Portanto, em geral, costumo procurar sedprocessamento de texto - especialmente para arquivos grandes - e geralmente evito fazer esse tipo de coisa no próprio shell.

Eu acho que isso pode mudar. Eu estava bisbilhotando man kshe notei isso:

<#pattern     Seeks forward to the beginning of the
              next line containing pattern.

<##pattern    The same as <# except that  the  por
              tion  of  the file that is skipped is
              copied to standard output.

Cético em relação à utilidade do mundo real, decidi experimentar. Eu fiz:

seq -s'foo bar
' 1000000 >file

... para um milhão de linhas de dados parecidas com:

1foo bar
...
999999foo bar
1000000

... e jogou contra sed:

p='^[^0-8]99999.*bar'
for c in "sed '/$p/q'" "ksh -c ':<##@(~(E)$p)'"    
do </tmp/file eval "time ( $c )"
done | wc -l

Portanto, ambos os comandos devem chegar a 999999foo bar e sua implementação de correspondência de padrões deve avaliar pelo menos o início e o fim de cada linha para fazer isso. Eles também precisam verificar o primeiro caractere em relação a um padrão negado. Isso é uma coisa simples, mas ... Os resultados não eram o que eu esperava:

( sed '/^[^0-8]99999.*bar/q' ) \
    0.40s user 0.01s system 99% cpu 0.419 total
( ksh -c ':<##@(~(E)^[^0-8]99999.*bar)' ) \
    0.02s user 0.01s system 91% cpu 0.033 total
1999997

kshusa ERE aqui e sedum BRE. Eu fiz a mesma coisa com kshum padrão de shell antes, mas os resultados não diferiram.

Enfim, é uma discrepância bastante significativa - kshsupera em sed10 vezes. Eu li antes que David Korn escreveu sua própria io lib e a implementou ksh- possivelmente isso está relacionado? - mas não sei quase nada sobre isso. Como é que o shell faz isso tão bem?

Ainda mais surpreendente para mim é que kshrealmente deixa seu deslocamento exatamente onde você pergunta. Para obter (quase) o mesmo (GNU), sed você precisa usar -u- muito devagar .

Aqui está um teste grepv.ksh

1000000         #grep + head
( grep -qm1 '^[^0-8]99999.*bar'; head -n1; ) \
    0.02s user 0.00s system 90% cpu 0.026 total
999999foo bar   #ksh + head
( ksh -c ':<#@(~(E)^[^0-8]99999.*bar)'; head -n1; )  \
    0.02s user 0.00s system 73% cpu 0.023 total

kshbatidas grepaqui - mas nem sempre - elas estão praticamente empatadas. Ainda assim, isso é excelente e ksh fornece informações que o lookahead- headinicia antes de sua correspondência.

Parece bom demais para ser verdade, eu acho. O que esses comandos estão fazendo de maneira diferente sob o capô?

Ah, e aparentemente não há nem um subconjunto aqui:

ksh -c 'printf %.5s "${<file;}"'
mikeserv
fonte
É patternuma expressão regular ou um padrão de shell mais simples?
Muru
@muru - Pode ser, mas eu não sou muito bom em mudar isso. No exemplo, é um padrão de shell - o padrão.
mikeserv
@ muru - eu adicionei um w / a regex.
mikeserv

Respostas:

8

O ksh não apenas usa o sfio, como também usa seu próprio alocador de memória personalizado.

No entanto, meu palpite é que o sfio faz a diferença nesse caso. Eu apenas tentei executar seu exemplo no strace e posso ver que o ksh chama de leitura / gravação ~ 200 vezes (blocos de 65 KB) enquanto o sed o faz ~ 3400 vezes (blocos de 4 KB). Com sed -u, meu laptop quase derreteu, as leituras são feitas por byte e as gravações por linha. O Ksh simple usa lseek. O Grep usa leitura ~ 400 vezes (blocos de 32 KB).

Franco de Miroslav
fonte
Sim - sem buffer não é para os fracos de coração. Gostaria de saber se ksho mecanismo de regex é eficiente como seu io? De qualquer forma, muito obrigado pela resposta. Minhas desculpas pelo seu laptop. Mas e o alocador de memória personalizado? Você tem mais alguma coisa sobre isso?
mikeserv
1
Infelizmente não. É claro que você pode baixar o código-fonte do site da at & t, mas é isso. A biblioteca é chamada AST e contém alocador, mecanismo de regex e muitas outras coisas. Portanto, é perfeitamente possível que a combinação de todas essas coisas torne o ksh muito mais rápido.
Franco Miroslav
Obrigado - isso também parece promissor: Alguns dos componentes disponíveis na coleção de software AST são: Comandos POSIX A maioria dos comandos POSIX padrão estão disponíveis na coleção AST. Muitos são codificados como funções de biblioteca que podem ser adicionadas ao ksh como comando interno que melhora drasticamente o desempenho. - Agora eu tenho figura só tenho que descobrir como construí-lo,
mikeserv
1
O @mikeserv ksh pode ser construído para usar o alocador vmalloc do Phong Vo . Artigos de periódicos disponíveis nesse link.
Mark Plotnick