Dlaczego wc jest tak wolne?

Dlaczego narzędzie wc jest tak wolne?

Kiedy uruchamiam go na dużym pliku, zajmuje to około 20 razy dłużej niż 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

To nie tylko dziwny stan krawędzi, ponieważ plik jest pełen zer, widzę tę samą różnicę w wydajności, nawet jeśli plik jest wypełniony losowymi danymi lub jest plikiem tekstowym.

(dotyczy wersji Ubuntu 13.04, 64-bitowej)

performance wc

— Jasio
źródło

Uwaga dla tych, którym zależy tylko na liczbie wierszy: wc -l <nazwa_pliku> jest znacznie szybsza na bardzo dużych plikach.

— EL,

Odpowiedzi:

Poszedłem więc do źródła i wygląda na to, że powolność polega na obsłudze znaków dwubajtowych. Zasadniczo, dla każdego wczytywanego znaku, musi on wywołać, mbrtowc()aby spróbować przekonwertować go na szeroki znak, a następnie ten szeroki znak jest testowany, aby sprawdzić, czy jest to separator słów, separator wierszy itp.

Rzeczywiście, jeśli zmienię LANGzmienną ustawień narodowych z domyślnej en_US.UTF-8(UTF-8 to zestaw znaków wielobajtowych) i ustawię ją na „ C” (prosty zestaw znaków jednobajtowych), będę wcmógł zastosować optymalizacje jednobajtowe, co znacznie ją przyspieszy, zajmuje tylko około jednej czwartej tak długo jak wcześniej.

Dodatkowo musi sprawdzać każdy znak tylko wtedy, gdy liczy się słowo ( -w), długość linii ( -L) lub znak ( -m). Jeśli wykonuje tylko liczenie bajtów i / lub wierszy, może pominąć obsługę szerokich znaków, a następnie działa niezwykle szybko - szybciej niż md5sum.

Pobiegłem go przez gprof, a funkcje, które są wykorzystywane do obsługi znaków wielobajtowych ( mymbsinit(), mymbrtowc(), myiswprint()itp) zajmują około 30% czasu wykonania samego, a kod podjęcie kroków przez bufor jest o wiele bardziej skomplikowane, ponieważ ma do obsługiwać kroki o zmiennej wielkości przez bufor dla znaków o zmiennej wielkości, a także wypychać częściowo ukończone znaki, które rozciągają bufor z powrotem na początek bufora, aby można go było obsłużyć następnym razem.

Teraz, gdy wiem, czego szukać, znalazłem kilka postów o powolności utf-8 z niektórymi narzędziami:

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

— Jasio
źródło

Och, właśnie zdałem sobie sprawę, że jesteś OP. : p

— Ivan Chau

Chociaż jest to najbardziej pozytywna odpowiedź, jest nieistotna. md5sumnigdy nie pozwoli ci policzyć słowa i wcnie obliczy skrótu md5 pliku! To tak, jakby pytać, dlaczego mój samochód jest tak wolny w porównaniu do mojej maszyny do pisania podczas pisania tekstu.

— user49468,

@ user49468: Rozsądnie jest założyć, że oba są związane z operacjami we / wy, ponieważ oba muszą czytać każdy bajt pliku wejściowego. Ta odpowiedź dowodzi, że wcw rzeczywistości jest on związany z procesorem podczas przetwarzania znaków wielobajtowych.

— MSalters

@ user49468: wc i md5sum mogą robić różne rzeczy, ale zarówno czytają plik, jak i wykonują stosunkowo proste obliczenia, jeden oblicza sumę kontrolną, jeden liczy bajty, separatory słów i znaki nowej linii. Cóż, myślałem, że to proste, ale nie uwzględniłem dodatkowej złożoności zestawów znaków wielobajtowych. Bardziej przypomina pytanie „Dlaczego mój samochód jest 20 razy szybszy w drodze do sklepu niż mój minivan?” Można spodziewać się pewnej różnicy między nimi, ale nie 20-krotnej różnicy.

— Johnny

@Johnny you porównanie samochodu / minivana nie ma aspektu, że oba są przeznaczone do transportu do sklepu. Tak więc istnieje porównanie prędkości. Bardziej odpowiednie jest porównanie samochodu z pojazdem do malowania pasków. Tylko dlatego, że obaj korzystają z ulic, ich prędkości nie są istotne, ponieważ malarz w paski nie nadaje się na zakupy i odwrotnie.

— user49468,

Tylko zgadnij, ale w pewnym sensie porównujesz jabłka do pomarańczy pod względem tego, co wcsię robi, a co md5sumsię robi.

Zadanie md5sum

Podczas md5sumprzetwarzania pliku po prostu otwiera plik jako strumień, a następnie rozpoczyna przepływ strumienia przez funkcję sumy kontrolnej MD5, która wymaga bardzo mało pamięci. Zasadniczo jest związany z procesorem i dyskami we / wy.

zadanie wc

Po wcuruchomieniu robi o wiele więcej niż tylko parsowanie pliku po znaku. Musi w rzeczywistości analizować strukturę pliku, linie na raz, ustalając, gdzie są granice między znakami i czy jest to granica słowa, czy nie.

Przykład

Pomyśl o następujących ciągach i o tym, jak każdy z algorytmów musiałby się przez nie przemieszczać podczas ich analizy:

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

W przypadku MD5 trywialnie porusza się po tych ciągach po znaku. Na wcto musi zdecydować, co to słowo linia graniczna i śledzenie liczby wystąpień, że widzi.

Dodatkowe dyskusje na temat wc

Znalazłem to wyzwanie kodowania z 2006 roku, które omawia implementację wcw .NET. Trudności są dość oczywiste, gdy spojrzysz na niektóre pseudo-kody, więc może to pomóc w wyjaśnieniu, dlaczego wcwydaje się być o wiele wolniejszy niż inne operacje.

— slm
źródło

Opisujesz coś innego niż standardowe uniksowe polecenie wc (przynajmniej nie to, które jest dostarczane z Ubuntu). To wc nie liczy wyjątkowych słów, tylko słowa, więc „hello hello world” to 3 słowa, a nie 2.

— Johnny,

W oparciu o tę teorię wydaje się, że prostsze zadanie, takie jak liczenie linii, przebiegałoby szybciej. Czy zmiana „wc” w celu określenia liczby wierszy znacząco modyfikuje wyniki? „wc -l”

— Joshua Miller

@Johnny - Nigdy nie mówiłem, że liczy unikalne słowa, które powiedziałeś. wcliczy wiele rzeczy podczas analizowania pliku. Liczy liczbę słów, linii i bajtów podczas analizy pliku. Przeczytaj stronę podręcznika man!

— slm

@JoshuaMiller - niejasne, czy mówienie, wcaby liczyć tylko linie, ogranicza jego wewnętrzną analizę, tak aby liczył tylko te rzeczy, czy tylko raportował wyniki linii, mimo że nadal liczy wszystko.

— slm

@slm Powiedziałeś, że liczy unikalne słowa, twój przykład mówi „Cześć! Greg ”powoduje Hello 1, Greg 1 , tzn. Liczy się dla każdego słowa. A projekt .Net, z którym łączysz się, mówi: „Jednym z jego głównych zadań jest przejrzenie zestawu danych i policzenie liczby powtórzeń danego słowa. Na przykład biorąc pod uwagę zdanie„ Cześć, tak cześć ”, powiedziałoby to słowo „Cześć” zostało użyte dwukrotnie, a słowo „tak” zostało użyte raz ”. Podczas gdy w rzeczywistości wynik echa „Cześć, tak cześć” | wc --words , jest „3”, a nie „Hello: 2, Yes: 1”

— Johnny,