Datová průchodnost unixových příkazů 2

10. 7. 2015 | Karel Kulhavý

Články - Datová průchodnost unixových příkazů 2  

V minulém díle jsem změřil a porovnal rychlost přenosu dat mezi procesy dd, cat, vliv polovodičové a diskové paměti. V dnešním díle se podívám na textový procesor grep.

Grep

Já mám dojem, že grep je z těhle příkazů takový nejoblíbenější. Však se i říká - grepovat. Zato neslýchám téerovat, cutovat, catovat to ještě ano. Na grepu mě velmi překvapil jeho silný průfuk, blížící se v některých případech 800 MB/s. U nástroje implementujícího algoritmus této úrovně sofistikace bych to rozhodně nečekal. Můžete posoudit sami:

Příkaz	Výkon [MB/S]
grep a < /dev/zero

Prásk. Tak tohle nevyšlo. U nástroje typu grep bych rozhodně nečekal, že první způsob jak změřit jeho rychlost, který mě napadne, složí nejen jej, ale i celý můj počítač. Nicméně tento se podařilo pomocí dvou žehliček zase oživit.

grep zřejmě alokuje řádku do paměti, a vzhledem k tomu, že tato je nekonečně dlouhá, potřebuje na to - pozor přijde překvapení! - nekonečné množství paměti! Takové bohužel nemám - mám jen 1 GB. A tak to jde do swapu a vytrashuje PC. To mi připomíná jednoho spolupracovníka v jedné práci, který měl za úkol napsat RTP streamování MP3. Celou MP3 naalokoval do paměti. Na MP3 vytvořené z celého CD s koncertem klasické hudby to ještě tak tak fungovalo, i když se počítač pořádně zadýchal. To by se ještě dalo řešit mantrou "výkon vašeho počítač nevyhovuje požadavkům tohoto software, musíte jej upgradovat." Kdy ale tento programátorský skvost přestal fungovat definitivně bylo, když měl streamovat MP3 stream z internetového rádia. Ten celý do paměti už naalokovat nejde, neboť je nekonečný, a opravit to nejde ani upgradem hardwaru. Tady by se musel upgradovat celý vesmír - tuto pokročilou programovací techniku totiž nepodporuje samotná logika.

Napadá mě hned teď otázka, co když má někdo na vstupu svého HTTP serveru na příjmu POST požadavků uploadovaných souborů grep? Nemá z toho pak pěkný DoS? Nestačí uploadovat dlouhý soubor bez konců řádků na složení serveru?

Incident dle mého názoru upozorňuje na návrhovou slabinu Unixu nebo Linuxu - špatnou virtualizaci prostředků v případě jejich plného využití. Říká se, že unixový multitasking by měl dělat uživateli dojem, že je na mašině sám. Což v případě vytrashování kvůli obyčejnému legitimnímu testu grepu jiným uživatelem rozhodně nedělá.

Pomocí příkazu yes vytvořím tedy testovací soubor o velikosti 100 MB který obsahuje opakující se testovací řádku

yes "nejoblibenejsi nekonecne dlouhy prikaz"| head -c 100000000 > test.txt

Teď budu grepovat řetězec "nej", který se na řádce vyskytuje dvakrát, a navíc se tam třikrát vyskytuje jeho prefix, který není jeho výskytem.

Ozkouším variantu s -o, která tiskne jen část řádky co se vyskytuje a bez, která tiskne řádku celou. A pak -c, která jen výskyty počítá. Tak uvidíme, kolik námahy programu zabere samotné hledání a kolik tisknutí.

Ozkouším i fgrep, který umí hledat jen obyčejné řetězce, neumí regulární výrazy. Bude rychlejší? Myslím že písmenko f v jeho názvu má naznačovat fast tedy rychlý.

Vyzkouším varianty s LC_ALL=C a bez něj. Bez něj musí grep parsovat UTF-8 znaky, protože moje defaultní locale na systému je UTF-8, což je dnes běžné. S LC_ALL=C bere vstup jako obyčejné bajty.

příkaz	s LC_ALL=C	bez
fgrep	77 MB/s	50 MB/s
grep	76 MB/s	50 MB/s
fgrep -o	31.3 MB/s	13.3 MB/s
grep -o	4.5 MB/s	4.4 MB/s
fgrep -c	149 MB/s	78 MB/s
grep -c	143 MB/s	77 MB/s

Rychlost se pohybuje v rozsahu 4.4 MB/s až 149 MB/s. To je 33-násobný rozdíl! Kdo chce vyhlídkovou jízdu, může si dát grep -o a tam už je jedno jestli vypneme UTF-8 nebo ne. Naopak nejvyšší rychlost jsem dosáhl u -c s LC_ALL=C a tam je jedno jestli to je fgrep nebo grep. Zapnutím UTF-8 dekodéru se ale rychlost sníží na polovinu, a to i tehdy, když na vstupu žádné UTF-8 znaky nejsou.

A jak si povede na souboru, který obsahuje UTF-8? Vezmu 100-megabajtový korpus khmerštiny, která má v UTF-8 jeden blok, kódovaný 3-bajtovými kódy. 1. bajt je vždy stejný, druhý má několik málo variant, a třetí se velmi mění. Mimochodem v khmerštině existují písmenka co se píšou za, pod, před, nad nebo okolo předchozího písmenka a dají se z toho konstruovat různá monstra, s kterými se dá pak testovat podpora Unikódu v různých programech, zda program text neořezává, nepíše následující řádky přes sebe, správně kombinuje tato písmenka atd.

Nejčastějším slovem v khmerštině je ning, což znamená "a". Já to sem radši psát nebudu, protože vím, v kterém článek píšu, je defektní a když je v textu khmerština, při editaci maže jiné části textu než co ukazuje že maže, což vede k závažnému poškození dat. Toto slovo ning použiji jako hledaný řetězec.

Protože korpus mám bez konců řádek, nahradím mezery konci řádek. Mezery v khmerštině plní funkci interpunkce vyskytují se asi tak často jako u nás tečky a čárky. 100 MB soubor má pak 1.9 milionu řádek o průměrné délce 53 bajtů a slovo ning se vyskytuje na 63 tisíc řádkách tedy na 3.5% řádek.

příkaz	s LC_ALL=C	bez
fgrep	714 MB/s	16.9 MB/s
grep	680 MB/s	500 MB/s
fgrep -o	595 MB/s	16.7 MB/s
grep -o	118 MB/s	110 MB/s
fgrep -c	769 MB/s	16.5 MB/s
grep -c	752 MB/s	571 MB/s

Vidím, že se situace v mnoha bodech změnila. Zůstává stále že vypnutím unikódu nemůžeme nic pokazit. Zdá se teď, že vyhlídkové jízdy jsou specialitou příkazu fgrep se zapnutým unikódem, a nedá se mu ulehčit ani tím, že po něm budeme chtít řádky jen počítat, ne vypisovat. Paradoxně, ač fgrep toho umí méně než grep. V těchto testech grepu se vstupní zpracovaná rychlost pohybovala mezi 4.4 až 769 MB/s, což je poměr 1:175!

Může se tedy v případě zpracování většího množství dat vyplatit popřemýšlet, zda můžeme vypnout unikód. Nepoužívat grep | wc -l ale místo toho grep -c. A případně ozkoušet zda pojede rychleji fgrep nebo grep.

grep i fgrep co jsem zkoušel jsou verze 2.16 GNU grep.

V příštím díle podobným způsobem proklepnu standardní unixový příkaz sed, což je něco jako grep, který umí řádky textu i editovat.

Diskuse k tomuto článku

[arrange]

"grep zřejmě alokuje řádku do paměti, a vzhledem k tomu, že tato je nekonečně dlouhá, potřebuje na to - pozor přijde překvapení! - nekonečné množství paměti!"

grep používá standardní postupné alokování zvětšujícího se bufferu (a la "newbuf *= 2"), a v případě, že xmalloc() selže, vyhodí chybu. Jedná se o řádek main.c:630 ve funkci fillbuf(). Problém nebude v grepu.

U mě:

$ uname -r
2.6.35-32-generic

$ ./grep --version
./grep (GNU grep) 2.16

# chybí PATTERN - příkaz nefunguje
$ ./grep < /dev/zero
Usage: ./grep [OPTION]... PATTERN [FILE]...
Try './grep --help' for more information.

$ ./grep a < /dev/zero
./grep: memory exhausted

[hvd]

potvrzuji, grep: paměť vyčerpána Jen teda system behem toho kdy se o prikaz pokousel moc pouzitelny nebyl, ale to je asi tim ze je bezi na stare T43

[Jendа]

Mně to řekne grep: input is too large to count.

Jen teda system behem toho kdy se o prikaz pokousel moc pouzitelny nebyl, ale to je asi tim ze je bezi na stare T43

Ne, já mám lepší stroj (Core i3 Sandy Bridge, 8 GB RAM) a vyčerpání paměti znamená 20minutový zátuh. Reportoval jsem to a dozvěděl jsem se, že mám používat menší swap - mám 8 GB RAM a 1,3 GB swapu. Od té doby jsem názoru že Linux prostě neumí spravovat operační paměť. V LKLM hnije patch, ale nevypadá to, že by to někdo řešil.

[Yarda]

grep-2.21:

grep hi < /dev/zero grep: input is too large to count

To musela být nějaká prehistorická verze grepu. Pak je ale otázkou, jestli má vůbec smysl s takovouto verzí grepu dělat podobné porovnání, když se do grepu pořád sypou nějaké výkonostní optimalizace. IIRC grep-2.20+ má pro některé patterny dost brutální speedup.

Co se týká DOSu při HTTP upload, každý rozumný člověk tam má nějaký limit.

20 minutové zátuhy lze umravnit vypnutím swap nebo alespoň vypnutím overcommit při alokaci paměti.

[Yarda]

Moje mašina je celkem plečka, přesto grep-2.21:

$ yes "nejoblibenejsi nekonecne dlouhy prikaz"| head -c 100000000 > test.txt
$ grep >/dev/null nej ./test.txt

Propustnost:

LANG=cs_CZ.utf8 grep 142.3 MB/s
LANG=C          grep 320.5 MB/s

Samozřejmě mezi jednotlivými měreními je nutné vyprázdnit IO cache, např:

# echo 3 > /proc/sys/vm/drop_caches; sync

[Yarda]

Nebo raději: # sync; echo 3 > /proc/sys/vm/drop_caches; sync

[Michal Kubeček]

Naopak. Pokud chceme opravdu benchmarkovat grep a ne čtení z disku, je potřeba zajistit, aby se z disku nečetlo vůbec. Např. tím, že soubor umístíme na tmpfs. Pokud si budeme jistí, že to neovlivní výsledky, můžeme data nechat rovnou generovat.

[Yarda]

Záleží co chceme benchmarkovat. Já to pochopil, že propustnost při praktickém používání grep a tam záleží i jak to čte z disku. Nejsem si jistý jak je to s VM cache u TMPFS, ale tipnul bych si, že se asi taky použije. Tudíž doporučuji i tam flushovat, aby měření nebylo ničím ovlivněno, nic se s tím nezkazí.

[Michal Kubeček]

Záleží co chceme benchmarkovat. Já to pochopil, že propustnost při praktickém používání grep a tam záleží i jak to čte z disku.

Pokud mne zajímá propustnost grepu, je potřeba, abych opravdu měřil propustnost grepu. Pokud budu číst ze vstupu, který nebude schopen poskytovat data tak rychle, aby byl úzkým hrdlem grep, pak neměřím propustnost grepu, ale něco úplně jiného.

Navíc podle těch čísel, která ukazujete, ve skutečnosti ani vy z disku nejspíš nečtete; tipoval bych, že proto, že ten flush děláte před testem a ne mezi vytvořením souboru a spuštěním grepu.

Nejsem si jistý jak je to s VM cache u TMPFS, ale tipnul bych si, že se asi taky použije.

Použije - ale jinak, než si myslíte: tmpfs je vlastně page cache, která pod sebou nemá žádné zařízení. Takže flushnout nejde, protože kdyby se vám to nějakým způsobem podařilo, o data přijdete.

Tudíž doporučuji i tam flushovat, aby měření nebylo ničím ovlivněno, nic se s tím nezkazí.

Nezkazí - ale také to nemá žádný efekt.

[Yarda]

Tipujete špatně. Soubor se vytvoří jednou a flushe mezi spouštěním grepu.

Pokud budu grepovat zdrojáky nebo jiné soubory na disku, tak propustnost na TMPFS je údaj, který mi bude celkem k ničemu, ale pro váš klid, to stejné na TMPFS:

585 MB/s

Reálná propustnost bude asi vyšší, protože na tak malém vzorku mám potíže to změřit. To nic nemění na faktu, že údaje v článku i použitá metodika jsou dost prapodivné.

[Michal Kubeček]

V tom případě to zase až taková plečka nebude, když se z disku čte přinejmenším 320 MB/s…

[Yarda]

Dále záleží na tom jak se měří. Pokud se jednoduše změří pouze čas běhu grepu a vypočte se propustnost ze znalosti velikosti souboru, což je primitivní, ale často používaná metoda, tak v případě, že grep sám není na TMPFS, tak režije pro načtení grepu do paměti a spuštění může u takto malých vzorků převážit. Tudíž flushem se nikdy nic nezkazí a výsledky budou alespoň konzistentní a porovnatelné.

[Jendа]

Co se týká DOSu při HTTP upload, každý rozumný člověk tam má nějaký limit.

Nevím jestli jde nastavit limit pro všechny klienty dohromady. Umím to jenom per-request. Ale nezkoumal jsem to podrobně. (a nejlepší řešení by bylo neukládat proboha celý POST do paměti) A nevím, jak jsi přišel zrovna na tento případ, já si zatím složil počítač 1) vlastním programem s bugem který prostě naalokoval a použil strašně moc paměti, 2) pokusem o napsání make -j 4 s vypnutým numlockem, takže to spustilo 200 instancí g++, 3) otevřením několika 100MPx obrázků ve Firefoxu.

20 minutové zátuhy lze umravnit vypnutím swap

To má negativní dopad na výkon.

nebo alespoň vypnutím overcommit při alokaci paměti

S tím mi nefungovalo Wine a možná nebude fungovat i něco dalšího.

[cezz]

20 minutové zátuhy lze umravnit vypnutím swap

To má negativní dopad na výkon.

Nevravim, ze nemas pravdu, len napisem svoje skusenosti:

Na desktope mi zvycajne prislo lepsie, ked aplikacia hned spadla pri nedostatku pamati, nez ked predtym 10 minut nechala pocitac nezmyselne swapovat. Podla mna ma v tomto pripade swap zmysel jedine v pripade, ze pouzivas aplikaciu ktora proste potrebuje vela virtualnej pamati a pridanie RAM nie je moznost. (ci uz financne, alebo technicky, ale to potom pouzivas bud nepsravny SW alebo HW..) Jediny realny zmysel swapu vidim v suspend to disk ale este som nemal to stastie ze by to niekde fungovalo 100% vzdy, takze to beztak nepouzivam.

Na server podla mna vo vacsine pripadov swap nepatri vobec, lebo ak sa co i len blizi vyuzitie pamati 100% tak je cas na optimalizaciu SW aby bol pamatovo efektivnejsi, alebo na viac HW. Zvlast v dobe EC2 a pod. je IMHO lepsie nechat server/service spadnut a nechat loadbalancer nastartovat sluzbu na inom stroji, nez mat 10 minut latenciu taku, ze je server prakticky nepouzitelny. (a uzivatel trpi)

Pravda, ak na HW nie su peniaze, tak si asi clovek nepomoze, ale to je skor financny problem, nez technicky.

[johniez]

Man grep:
fgrep is the same as grep -F
-F, --fixed-strings

Kam se schovalo fast? ;)

[2X4B-523P]

je to rychlejsi nez napsat grep -F

[Michal Kubeček]

Po prvním dílu jsem doufal, že to byl jen takový pomalý a trochu zmatený rozjezd a že zbytek už bude lepší. Teď už se jen děsím, co bude příště.

[tuxmartin]

Informacne celkem zajimave na precteni. Ale uroven textu je jednoznacne na blog. V clanku by se podobne obraty a historky vyskytovat nemely...

[Michal Kubeček]

Z věcného hlediska to bohužel není o moc lepší.

[2X4B-523P]

jiste ze nekomu, kdo si je techto informaci dobre vedom z praxe, se muze clanek takto jevit, nicmene si clanky ctou i ctenari, kteri se tim vyhnou laborovani a ziskane informace mohou pouzit pro optimalizace, ktere dosud nepotrebovali... existuji situace, kdy muze jednoducha zmena usetrit cas i potrebny vypocetni vykon... osobne si nedelam iluze, ze vsichni pisi skripty efektivne jiz od prvni chvile co zacnou pouzivat prikazovou radku...

[2X4B-523P]

zrovna toto tema je na clanek nevdecne, nejaka omacka se k tomu hodi a je na autorovi, jaky styl si zvoli... jinak by samozrejme stacilo napsat pouzity prikaz a tabulku rychlosti zpracovani, jenze to by bylo na clanek az prilis strohe IMHO... mezi blogy se take kolikrat objevi tema vhodne na cely clanek, ale autor se rozhodne ho uverejnit jen jako zapisek... myslim si, ze uroven webu otistenim takoveho clanku neutrpela a pro nekoho muze byt odlehceny styl psani prijemna zmena, oproti cteni firemnich mailu a vyrocnich zprav...

[nobody]

jaky je racionalni duvod proti pouziti podobnych obratu a historek v clanku?
jeste volat po tom, aby clanek byl psan vyhradne v obleku od gucci ne ? :D

[Michal Kubeček]

Historka sama o sobě je úsměvná. Problémem je kontext: snaží se demonstrovat, jak je grep špatně navržený. Autor se nejspíš nezkusil zamyslet nad tím, jak by implementoval filtr operující na obecně neseekovatelném vstupu, jehož úkolem je vypsat (celé) řádky obsahující vzorek, aniž by načetl do paměti všechno až po první výskyt vzorku nebo newline. Mne by to třeba docela zajímalo.

[stalin]

Jestli jste nepochopil tak jednoduchy a zaroven uzitecny clanek tak si zatrest sectete vsechny prvocisla mezi 12345494-12345491 a 12345491-12345480. A sepiste o tom clanek hodny Nature zverejneny v Rudem Pravu. A zitra vsechny noviny zverejni fotku vasi rodne planety.

[kyknos]

jsou lidi, co se proste narodi jako suchari :) lek na to zatim nikdo nenasel a eutanazie neni v tomto pripade povolena :)

[stalin]

Jo dik za podporu stoupajici hvezdy mladeho (minimalne duchem) autora!

Minule to mel take dobre a mistni ajtaci se nad tim sebeukajeli o106.

Je to borec!

[little.owl]

+1

[indy]

Já to sem radši psát nebudu, protože vím, v kterém článek píšu, je defektní a když je v textu khmerština, při editaci maže jiné části textu než co ukazuje že maže, což vede k závažnému poškození dat.

tady se mi, již dost krabatá, šedá kůra ještě více zkrabatila. nejdřiv jsem si položil otázku, co autor ví. první, co mne napadlo, že autorovi vypadl defektní jazyk:

Já to sem radši psát nebudu, protože vím, že jazyk v kterém článek píšu, je defektní a když je v textu khmerština, při editaci maže jiné části textu než co ukazuje že maže, což vede k závažnému poškození dat.

ale to mi nedával smysl zbytek souvětí, nehledě na fakt, že z toho vyplývající autorovo přesvědčení o defektní češtině mi zvedal krevní tlak. Uklidniv jej odkázáním do patříčných mezí jeho, jal jsem se prošetřovati další hypotézu a to obrácenou, že tam je něco navíc. Tato hypotéza se ukazuje býti nejpravděpodobnějsí. Doufám, že autor už též objevil, kde mu co přebývá.

[Michal Kubeček]

vím → vim :-)

Ale taky mi chvíli trvalo, než mi to došlo.

[Petr Tomášek]

Ať žijou automatické korektury

[Sinuhet]

Myslím, že tam mělo být "že redakční systém".

Taky mě první napadl jazyk, pak cosi o defektním autorovi, a nakonec jsem se snažil vymyslet, proč a hlavně co za speciální znak použil z khmerštiny, že se to umazalo.

Redakční systém je pravděpodobnější než vim vzhledem k autorově stylu psaní. A i vzhledem k tomu, jestli vim neumí khmerštinu.

[nobody]

co to zeres za prasky? autor je mimojine autor conzoloveho browseru links, optickeho pojitka Ronja, legendarni konzolove/ascii deathmatch hry 0verkill a dalsi..
to ze se ti neco nezda, je spis problem tveho omezeneho vnimani nez jeho ;)

[dosmanak]

Diky za clanek. Je super, ze si nekdo dal tu praci, ale rychlost grepu se taky znatelne meni se slozitosti pouziteho regularniho vyrazu Uz se tesim na dil o awk!

[Honza]

Mam pocit ze klasicky uzivatel ma iplementovane limity (prikaz ulimit a /etc/secure/limits.conf) a pokud alokace prekroci hardlimit pak bude systemem ukoncena. Nebo se mylim ? :)

[Jendа]

nproc limit mi funguje, ale mám taky jenda hard rss 6000000 (na stroji s 8 GB RAM) a stejně ho dokážu položit (viz bugreport výše).