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.
Ad.[0]. Zamienia je w encje html czy wrzuca jak jest i rozwala wygląd strony każąc to przeglądarce rozkminić jako kod strony? Kiepsko, że rozwala PRE podczas edycji – ewidentna niedoróbka edytora. Może czas przesiąść się na coś innego jako silnik bloga? ;o)
Część zamienia w encje html, część znika. Co gorsza znika też fragmenty notki. Nie wnikałem za bardzo, ale przypomniało mi się, że faktycznie było coś takiego. Żeby było śmieszniej, robi to na zaciąganiu do powtórnej edycji – na czysto można raz wpisać z ostrymi nawiasami cokolwiek.
Nie chce mi się rozkminiać, czy któryś edytor w starym Blox jest tego pozbawiony. Wygląda, że w nowym Blox jest OK (ale nie przesiadłem się jeszcze, a przełączać mi się nie chce). Zresztą nowy edytor ma innego buga (w trybie edycji HTML ó jest zamieniane na htmlowe o acute). Poczekam pewnie.
A co tam siedzi? TinyMCE?
WordPress też nie jest bez wad, ma edytor z dwoma zakładkami, wizualny i czysty HTML obok siebie, ale przy złożonych rzeczach też potrafi coś sam pozmieniać przy przełączaniu widoków lub wczytaniu do ponownej edycji. Narzędzie idealne chyba nie istnieje… :o)
Dają do wyboru:
1. prosty edytor tekstowy
2. zaawansowany edytor TinyMCE
3. TinyMCE z nowymi zdjęciami
Używam tego środkowego. Pierwszy to klepanie HTML z palca. Ostatnie dwa nie wiem czym się różnią. Przy czym Blox ogólnie ma jakąś fazę „bezpieczeństwa” z wycinaniem ostrych nawiasów. Z komentarzy też wycina, więc stawiam, że to pokłosie i jakiś dodatek do TinyMCE, nie samoistna faza. 😉
Mimo szczerych chęci nie udało mi się powtórzyć Twoich wyników w każdym przypadku sort okazywał się o 0.050.1s szybszy.
@Barthalion Nie wiem co robisz źle, ale coś na pewno. Nie jest możliwe, żeby różnica była we wszystkich przypadkach jednakowa. BTW sprawdziłem na innej maszynie i systemie (Wheezy, wcześniej był unstable):
sort:
real 0m42.658s
user 1m59.636s
sys 0m0.608s
perl:
real 0m22.004s
user 0m21.908s
sys 0m0.044s
sort (mały dataset):
real 0m0.120s
user 0m0.116s
sys 0m0.000s
perl:
real 0m0.095s
user 0m0.088s
sys 0m0.004s
Ew. jakieś dziwne dane Ci się losują. Wystaw swoje datasety, popatrzymy…
Sort może działać szybciej. Ustaw locale na zakres ASCII ani pełen UTF-8.
time LC_ALL=C sort 2sort.txt > /dev/null
Wyniki: sprunge.us/JUHK
Dane: paste.xinu.at/87e5es/
Po każdym teście czyściłem cache, w innym wypadku rezultaty można wyrzucić do kosza ze względu na ich bezużyteczność. Jak widać sort bez znajomości UTF-8 wypada znacznie lepiej od Perla, a skoro nie bierzemy pod uwagi poprawności wyników, zwycięzca nasuwa się sam.
@Barthalion Cache nie ma znaczenia (o ile żaden z testów nie jest robiony bez danych w cache) – w końcu nie testujemy odczytu z dysku. TBH pierwsze testy (te z wpisu) leciały u mnie z tmpfs.
Trick z ustawieniem locale znałem dla grepa nfsec.pl/1line/5621 i nie pomyślałem o jego wykorzystaniu dla sort. Ciekawe czy jeszcze jakieś polecenia można przyspieszyć w ten sposób.
Dzięki, niebawem zaktualizuję wpis.
Komentarz usunięty na życzenie autora.
Z ciekawych rzeczy, które warto zachować, sort ma sporo opcji -s, -S, –parallel, które mogą wpływać na wydajność (man sort).