Por que o wc é tão lento?

Question

Por que o utilitário wc é tão lento?

Quando eu o executo em um arquivo grande, ele demora cerca de 20 vezes mais do que o md5sum:

MyDesktop:/tmp$ dd if=/dev/zero bs=1024k count=1024 of=/tmp/bigfile
1024+0 records in
1024+0 records out
1073741824 bytes (1.1 GB) copied, 0.687094 s, 1.6 GB/s

MyDesktop:/tmp$ time wc /tmp/bigfile 
         0          0 1073741824 /tmp/bigfile

real    0m45.969s
user    0m45.424s
sys     0m0.424s

MyDesktop:/tmp$ time md5sum /tmp/bigfile 
cd573cfaace07e7949bc0c46028904ff  /tmp/bigfile

real    0m2.520s
user    0m2.196s
sys     0m0.316s

Não é apenas uma condição de borda estranha porque o arquivo está cheio de nulos, vejo a mesma diferença no desempenho, mesmo que o arquivo esteja cheio de dados aleatórios ou seja um arquivo de texto.

(isso é no Ubuntu 13.04, 64 bits)

    

Answer 1

Então eu fui para a fonte, e parece que a lentidão está no tratamento de caracteres de byte duplo. Essencialmente, para cada caractere lido, ele precisa chamar mbrtowc() para tentar convertê-lo em um caractere largo, então esse caractere largo é testado para ver se é um separador de palavras, um separador de linhas, etc.

De fato, se eu alterar minha variável de local LANG do padrão en_US.UTF-8 (UTF-8 é um conjunto de caracteres multibyte) e defini-la como " C " (conjunto de caracteres simples de byte único), wc é capaz de usar otimizações de byte único, o que acelera consideravelmente, levando apenas cerca de um quarto do tempo anterior.

Além disso, ele só precisa verificar se cada caractere está em andamento ( -w ), o comprimento da linha ( -L ) ou o caractere ( -m ) conta. Se estiver apenas fazendo contagem de bytes e / ou linhas, ele pode ignorar o tratamento de caracteres amplo e, em seguida, é executado com extrema rapidez - mais rápido do que md5sum .

Eu o executei através de gprof , e as funções que são usadas para manipular os caracteres multibyte ( mymbsinit() , mymbrtowc() , myiswprint() , etc) estão ocupando cerca de 30% do tempo de execução sozinho, e o código que percorre o buffer é muito mais complexo porque ele tem que manipular etapas de tamanhos variáveis através do buffer para caracteres de tamanho variável, bem como preencher quaisquer caracteres parcialmente completos que abranjam o buffer de volta ao início do buffer para que ele possa ser tratou da próxima vez.

Agora que sei o que procurar, encontrei alguns posts mencionando a lentidão do utf-8 com alguns utilitários:

link link

    

Answer 2

Apenas um palpite, mas você está comparando maçãs com laranjas em relação ao que wc está fazendo versus o que md5sum está fazendo.

tarefa do md5sum

Quando md5sum processa um arquivo, ele simplesmente abre o arquivo como um fluxo e, em seguida, começa a executar o fluxo por meio da função de soma de verificação MD5 que precisa de muito pouca memória. É essencialmente CPU & limite de E / S de disco.

tarefa do wc

Quando wc é executado, ele está fazendo muito mais do que apenas analisando o arquivo de um caractere por vez. Ele tem que realmente analisar a estrutura do arquivo, linhas de cada vez fazendo determinações sobre onde os limites entre os caracteres são e se é um limite de palavra ou não.

Exemplo

Pense nas seguintes strings e em como cada um dos algoritmos teria que passar por elas ao analisá-las:

“Hello! Greg”
“Hello!Greg”
“Hello\nGreg”
“A.D.D.”
“Wow, how great!”
“wow     \n\n\n    great”
“it was a man-eating shark.”

Para o MD5, ele movimenta trivialmente por essas cadeias um caractere por vez. Para wc , tem que decidir o que é uma palavra & limite de linha e acompanhe o número de ocorrências que ele vê.

Discussões adicionais sobre o wc

Encontrei este desafio de codificação de 2006 que discute a implementação wc no .NET. As dificuldades são bastante óbvias quando você olha para alguns dos pseudo-códigos, então isso pode ajudar a começar a esclarecer por que wc parece ser muito mais lento que outras operações.