Pomiędzy bitami

Dziś na kanale IRC znajomy szukał błędu w skrypcie bashowym. Danych dużo, skrypt wykonuje się długo (kilkadziesiąt minut). Błąd pojawiał mu się w sort, skrypt złożony. Jakoś tak stwierdził, że przepisze na Perla, będzie szybciej. Tyle tytułem wstępu, bo potem rozpoczęliśmy akademickie rozważania pt. czy sortowanie w Perlu będzie szybsze.

Postanowiłem się pobawić w praktykę. Nie ukrywam, że sporą rolę maiła tu niedawna dyskusja nt. algorytmów (i czemu zabawy z nimi są fajne) z M.^[0]

Najpierw wygenerowanie sporego zestawu danych testowych [1]. 10 mln liczb z zakresu 0-99, 28999760 bajtów.

Następnie prosty sort [2]. Wyniki oscylują w granicach 16-18 sekund.

Pierwszy skrypt w Perlu[3] Jest minimalnie szybciej, bo 15 sekund.

Widać parę niepotrzebnych przepisań i da się to skrócić [4]. Po skróceniu wyniki oscylują w granicach 14,4 sekundy.

Pora na mały cheat, bo wiemy, że większość danych się powtarza. Czyli wersja z hashem – zliczamy ilości wystąpień, a na koniec sortujemy tyko klucze hasha (których jest 100) i wyświetlamy tyle razy, ile razy wystąpiły [5].

Jest dużo szybciej. Okolice 4,7 sekundy. Szczerze mówiąc nie sądziłem, że aż tyle da się urwać.

Na koniec postanowiłem sprawdzić, czy różnica wynika z powtarzających się danych. Wygenerowałem mały plik z praktycznie niepowtarzającymi się danymi [6]

Tutaj sort wykonywał się ok. 70 ms, natomiast – ku mojemu zdziwieniu – Perl nadal był szybszy i wykonywał się ok. 50 ms.

Daleki jestem od wyciągania z tego benchmarku daleko idących wniosków, nikogo też na przechodzenie wszędzie na Perla nie namawiam. Bardziej chodziło mi o pokazanie ciekawostki. Zwykle 10 sekund różnicy nie ma znaczenia, narzut na pisanie nie zwróci się nigdy, a wersja z sort jest po prostu czytelniejsza. I pewnie nadal będę używał sort. Niemniej warto wiedzieć, że w prosty sposób da się szybciej. Taki mały hack.

Inna sprawa, że IMVHO pisanie skryptów w bashu zwykle nie ma sensu i lepiej użyć Perla, Pythona itp. Szybciej, więcej można w prosty sposób zrobić, a skrypty bashowe mają tendencję do puchnięcia z elementami dziwnych rzeźb.

Uwagi: Wynik sortowania jest identyczny, choć nie to było priorytetem. Sortowanie nie jest numeryczne (jak ktoś chce, może się bawić, stawiam, że wyniki będą podobne). Skrypty są pisane mało optymalnie, mało czytelnie itd. ale tak na szybko piszę onelinery z głowy, a nie bawiłem się w upiększanie, bardziej chciałem szybko notkę zrobić. Tak, wiem nie ma close (F), w skryptach, ale nie jest tu potrzebne. Nie ma potrzeby korzystania z open, spokojnie można było robić „tradycyjne” while (<>) i czytać ze STDIN; jak sprawdziłem później nie powoduje to zauważalnej różnicy w czasie wykonania.

Ponieważ Blox wyczynia cuda z tekstami w pre podczas edycji notki, efektem czego jest znikanie większej części skryptów i tekstu, poniżej wklejka z wszystkimi poleceniami (odnośniki powyżej).

 

[0] Jest szansa, że pojawi się parę zadań z algorytmami. Ale niczego nie obiecuję. Zresztą, chyba lepiej, żeby takie rzeczy działy się na blogu jakiegoś programisty… A jak zobaczyłem, co robi Blox z groźnymi nawiasami trójkątnymi, to zupełnie odeszła mnie ochota na pisanie czegoś wymagającego fragmentów kodu tutaj.

UPDATE: Jak trafnie zauważyli czytelnicy w komentarzach, sort można przyspieszyć (analogicznie, jak przyspieszyć można grep) poprzez ustawienie LC_ALL=C lub LANG=C. Po tym zabiegu sort, dla podanych danych, działa szybciej od dotychczasowego najszybszego Perla, w okolicach 4,2 sekundy.