☰

Por que o banheiro é tão lento?

tag-icon • tag-icon performance wc
Por que o banheiro é tão lento?

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

Quando executo em um arquivo grande, demora cerca de 20 vezes mais 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 causada pelo arquivo estar cheio de nulos, vejo a mesma diferença no desempenho mesmo se o arquivo estiver preenchido com dados aleatórios ou for um arquivo de texto.

(isso está no Ubuntu 13.04, 64 bits)

Responder1

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

Na verdade, se eu alterar minha LANGvariável de localidade do padrão en_US.UTF-8(UTF-8 é um conjunto de caracteres multibyte) e defini-la como " C" (conjunto simples de caracteres de byte único), wcé possível usar otimizações de byte único, o que acelera consideravelmente, demorando apenas cerca de um quarto do tempo anterior.

Além disso, ele só precisa verificar cada caractere se estiver fazendo contagens de palavras ( -w), comprimento de linha ( -L) ou caracteres ( -m). Se estiver fazendo apenas contagens de bytes e/ou linhas, ele poderá pular a manipulação ampla de caracteres e, em seguida, será executado de forma extremamente rápida - mais rápido que md5sum.

Eu executei isso gprofe as funções usadas para lidar com os caracteres multibyte ( mymbsinit(), mymbrtowc(), myiswprint(), etc) estão ocupando cerca de 30% do tempo de execução sozinhos, e o código que percorre o buffer é muito mais complexo porque tem que manipular etapas de tamanho variável através do buffer para caracteres de tamanho variável, bem como preencher quaisquer caracteres parcialmente concluídos que abranjam o buffer de volta ao início do buffer para que possam ser manipulados na próxima vez.

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

https://stackoverflow.com/questions/13913014/grepping-a-huge-file-80gb-any-way-to-speed-it-up http://dtrace.org/blogs/brendan/2011/12/08/2000x-performance-win/

Responder2

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

tarefa do md5sum

Ao md5sumprocessar um arquivo, ele simplesmente abre o arquivo como um fluxo e então começa a executar o fluxo através doFunção de soma de verificação MD5que precisa de muito pouca memória. É essencialmente vinculado à E/S da CPU e do disco.

tarefa do wc

Quando wcexecutado, ele faz muito mais do que apenas analisar o arquivo, um caractere por vez. Ele realmente precisa analisar a estrutura do arquivo, linhas por vez, determinando onde estão os limites entre os caracteres 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 à medida que as analisam:

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

Para MD5, ele move trivialmente essas strings, um caractere por vez. Pois wcele precisa decidir o que é um limite de palavra e linha e controlar o número de ocorrências que vê.

Discussões adicionais sobre banheiro

Eu achei istodesafio de codificação de 2006que discute a implementação wcem .NET. As dificuldades são bastante óbvias quando você olha alguns dos pseudocódigos, então isso pode ajudar a começar a esclarecer por que wcparece ser muito mais lento do que outras operações.

informação relacionada