Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: PanVP 12. 01. 2020, 01:00:27
-
Ahoj,
řeším takový zapeklitý problém, potřebuji extrémně rychle kontrolovat, jestli určité číslo (64 bajtů) není ve slovníku.
Aktuálně stíhám asi dvě miliardy porovnání za vteřinu, ale potřebuji víc, ideálně 10x víc...
Vstup: Proud čísel, každé o délce 64 bajtů.
Zpracování: Ověřit, že kontrolované číslo není v seznamu nevalidních (zakázaných).
Tj. čísla vezmu a ověřuji je vůči seznamu, pokud nejsou, jsou ok, pokud by bylo, musím signalizovat chybu.
1235 ?: [1232,1234,1236] -> není
Rád bych zvýšil šanci, že vyhledávané číslo bude v cache L1/L2.
Teď vezmu číslo a podívám se, jestli není ve slovníku (asi 400+ MB * 15 procesů).
První číslo musím ověřit vůči začátku a druhé vůči konci slovníku, třetí třeba z prostředka.
Samozřejmě neprocházím celý seznam, první dva bajty čísla udávají startovní pozici, kde začínám hledat.
(Forma hash tabulky, B-strom nepodává dobrý výkon, má totiž problém s cache.)
Říkám si, že kdybych přicházející čísla řadil, řekněme do 65535 polí (použiji první dva bajty čísla pro určení pole), třeba bych zvýšil šanci na to, že data už v cache budou. Prostě si je "předtřídím". Číslo stejně musím přijmout a uložit.
Ale tak mě napadá, jestli zápis mimo paměť, která je v CPU, nevyvolá stejný výpadek stránky, nebo jestli je zápis řešený nějak jinak? Co se děje v případě, kdy požadovaná stránka není k dispozici, mi je naprosto jasné. Ale co v případě, kdy zapisuji do místa, které je mimo cache ???...musí se paměť připojit a až pak se provede zápis? Nebo to nějak ošéfuje řadič pomocí Cache?
Taky jsem přemýšlel, že bych prováděl distribuci čísel na jiné stroje.
Tj. čísla začínající na AA00 až FFFF bych posílal jinému stroji než 0000 až AA00.
Ale tady se bojím, že prosté odeslání datagramu UDP bude výpočetně náročnější než prohledání pole ::)
(Zapnout Jumbopakety není problém a stroje jsou propojené 25 Gbitem.)
Nebo se pletu?
Řeším to, že bych potřeboval zvýšit výkon a ještě k tomu mi roste slovník, už teď je asi 4.8 GB paměti stroje obsazeno...
::)
Co s tím?
S tím posíláním dat na jiný stroj... dost by mě zajímalo, jak výpočetně náročné to je :-D
Ale abych nezabil týden tím, že budu programovat klienta na odesílání, server na příjem a výsledek bude pomalejší, než hledání v paměti stroje :P
-
Třídění bych nedělal, tím výkon asi dost zabiješ.
Pokud znáš data "dopředu", tozn. čísla chodí v nějakém streamu a nevadí ti mírné zvýšení latencí a cílíš hlavně na vysokou propustnost, můžech použít prefetch (https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_mm_prefetch&expand=4391) dat z RAM do cache, před vlastním porovnáním se bude N budoucích čísel ze slovníku prefetchovat do cache. Tím zajistíš, že v okamžiku, kdy se čísla budou skutečně porovnávat, už budou data ze slovníku v cache a nečeká se na RAM.
Další možnost je použít AVX instrukce (https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_mm256_cmpeq_epi64&expand=782), tím se zrychlí vlastní porovnávání, ale je nutné mít data v cache, jinak se stejně čeká na RAM.
Docela dobrý trik jsou také pravděpodobnostní datové struktury, pro tento účel je asi nejlepší cuckoo filter (https://en.wikipedia.org/wiki/Cuckoo_filter). Hashovat nic nemusíš, "hash" se dá vytvořit třeba XORem z čísla. Z filtru vypadne výsledek buď číslo určtitě není ve slovníku, nebo číslo je možná ve slovníku (pak musíš udělat porovnání se slovníkem). Výhoda cuckoo filtru je, že jsou jeho data mnohem menší a vejdou do L2/L3 cache.
-
Ahoj,
zaujimavy problem a vpodstate trivialne zadanie.
Skusim najprv odpovedať na otázky a potom dať nejaké nevyžiadané rady.
Zápis do cache by imho mal spôsobiť relatívne lacnú operáciu invalidácie rovnakej nacachovanej veci v ostatných cache procesora. Toto je ale skôr môj pocit.
Rozdelenie na servery, určite má zmysel pri istých požiadavkách a istom spôsobe implementácie (serializácia requestov do json-u, poslanie do kafka topiku a jeho paralelné spracovanie nepatrí medzi zmysluplné spôsoby spracovania :). Nejaký ten smartbatching (ringbuffer) a sorting pri spracovaní by vedel pomôcť aj pri lokálnom spracovaní a aj pri distribuovanom.
Pri rieseni je potrebne ale brat v ohlad veci okolo:
- "black list" a jeho distribucia (uniformna, alebo nie? apt install ent; ent /tmp/blacklist.raw)
- je "black list" staticky, alebo sa do neho pridavaju data (nedajboze odoberaju, vid bloom/cuckoo filtre
- je cielom latencia a jej stabilita, maly rozptyl, alebo celkova priepustnost je cielova metrika?
- ak je cielom latencia, je viac cielom jej stabilita (aj za cenu vyssej hodnoty), alebo radsej vacsi rozptyl a nizsia absolutna hodnota?
- Je prúd vstupov asynchrónny, bez nejakého ovládania, alebo je cilom spracovať batch dát čo najrýchlejšie, ale len tak rýchlo, ako stíhame spracovávať (je tam backpressure; je tam biznis obmedzenie, že pri nejakej latencii stráca spacovanie vznam?)
Nasledne je potrebne oboznamit zadavatela ulohy, ze ladenie do extremov nie je praca na jeden vikend. Cokolvek spravis, je potrebne odtestovat na cielovom HW s cielovou zatazou/datami. A precitat vysledky testov tiez nie je trivialne. Teda precitatnie asi je lahke, ale ich vysvetlenie/interpretacia, je dost zlozita.
Mozne nastroje pri dosiahnutie cielu:
- cache hit (da sa merat cez nejaky intel specific nastroj v linuxe; mozno powertop)
- minimum vetvenia, skusit nevetviit program, ale vsetok vstup spracovavat "rovnako"
- brat viac vstupov naraz (spomenute SIMD instrukcie)
- "zmensenie" si problemu, pouzitie pravdepodobnostnych datovych struktur (spomenute cuckoo-ve filtre. ouziva ich i jadro linuxu, tusim v planovaci)
- distribuovanie na viac "cache" (socket, server)
- predspracovanie dat (napriklad vygenerovanie si Naive Bayes klasifikátoru podľa "black listu", prípadne mrknúť markov chain a podobne; a skúsiť využiť)
Mozne zdroje vedomosti (utrzkove, popularne a podobny mix):
- https://www.infoq.com/articles/lessons-learned-performance-testing/ (https://www.infoq.com/articles/lessons-learned-performance-testing/)
- https://www.infoq.com/presentations/simdjson-parser/?itm_source=presentations_about_json&itm_medium=link&itm_campaign=json (https://www.infoq.com/presentations/simdjson-parser/?itm_source=presentations_about_json&itm_medium=link&itm_campaign=json) -> parsovanie json-u s minimom vetvenia a podobne
V každom prípade testovať a testovať...
PS: Zaujímala by ma doména problému, ak to nie je tajné :)
-
predesly kolega se pta spravne, zkratim to na dotazy:
* meni se slovnik?
* vleze se slovnik cely do ram (podle me to je 6GB) ?
* kolik mate jader, ze by mohl byl slovnik v ramce a jadra by prohledavaly paralelne.
* pouziti clusteru, knihovna MPI.
* pouziti paralelizace na GPU.
-
https://softwareengineering.stackexchange.com/questions/280339/fastest-way-to-determine-if-a-value-is-in-a-list
-
Přijde mi, že dotaz má nějaké problémy s formulací:
1) Proč je v názvu dvakrát „zápis“ když jde o kontrolu čtením?
2) Jak by mělo fungovat „Rád bych zvýšil šanci, že vyhledávané číslo bude v cache L1/L2.“ když jsi nám nesdělil nic o tom, jaké mají vstupní čísla statistické rozdělení? A proč chceš mít v cache vyhledávané číslo, když tě nezajímá to číslo, ale informace, jestli je v seznamu?
3) Teď jsem si všiml, že 64 B * 2 miliardy/s = 128GB/s. To ta čísla generuješ lokálně, nebo jak je získáváš? Vždyť to musí být strašný problém do toho počítače vůbec dostat, ne? Vždyť to je víc než propustnost PCIe na většině procesorů a něco jako quad channel DDR4!
Pokud by statistické rozdělení bylo třeba takové, že tam čísla jednou jsou a pak se mnohokrát opakují, tak by mohl pomoct splay strom, resp. nějaká jeho cache-aware varianta. (ale opakování je potřeba mnohokrát, protože to musí vyvážit vysplayování prvku, což je log(n) *zápisů* což bude příšerně drahé; hm asi na to zapomeň, tohle nebude fungovat; i obyčejná hashtable si přece bude držet posledně použité buckety v cache)
Z té délky 512b bych to tipoval na kryptografii a pak to asi bude plně náhodné a máš smůlu.
Tvrdíš, že máš cca. 7 milionů čísel. U Bloom filtru se většinou udává něco jako 1 bajt na položku. Takže pokud máš alespoň 8 MB cache, mohl by se ti tam filtr vejít celý.
Ale tady se bojím, že prosté odeslání datagramu UDP bude výpočetně náročnější než prohledání pole
No to samozřejmě, musíš jich agregovat víc do jednoho datagramu.
Btw. použij hugepages, protože jinak budeš mít v cache kolize.
-
Ještě by se hodilo vědět, jestli existuje nějaký odhad pro to, kolik hitů asi tak bude -- řešení se může lišit podle toho, jestli jsou hity výjimečně, občas, nebo naopak skoro všechna čísla v seznamu jsou.
-
Naozaj su to 64 bajtove cisla? Ved to musi byt obrovske. V takom pripade neviem ci ma zmysel sa bavit o optimalizaciach na urovni cache. Myslim, ze jeden cache line je 64 bajtov takze to musis mat bez padovania, aby tam kazde cislo sadlo presne. Iteracia by mala byt tiez linearna, aby fungoval prefetch.
IMHO, prv nez budem optimalizovat cache, asi by som skusil Bloom filter alebo 64 bitovy RoaringBitmap (Ckova implementacia sa vola CRoaring).
Naozaj maju tie cisla 64 bajtov?
-
Zdar, čísla jsou 512bitová, ale vyskytují se i 1024bitové varianty, které jsou zatím výjimečné, ale na které se přejde.
Latence důležitá není, pokud systém vypadne, data se stejně ukládají do pole rychlostí asi 2 GB/s a za hodinu se nezaplní víc než několik 5-7 TB prostoru, to si řeší řadič.
Slovník se v průběhu práce nemění, mění se až na konci dne.
Slovník se ještě nějakou dobu do paměti vejde, není problém paměť dokoupit.
Ostatní zdroje si prostuduji večer a zamyslím se nad tím.
A ano, zadání je v podstatě triviální, ale dosáhnout maximální výkon...
-
Bloom filter
S tím jsem samozřejmě obeznámený.
Ale jak to funguje teď:
1) Vezmu začátek čísla
1234 -> ten použiju jako index pole cisla[1234] a získám ukazatel do pole.
(Pokud index cisla[1234] ukazuje NULL, mám vyřízeno, což je asi 1/3 případů.)
Začnu prohledávat od daného místa, kam ukazuje tento ukazatel a ve 1/3 případů mi stačí dva kroky, abych dokázal vyloučit, že číslo není invalidované.
Ve zbylé 1/3 případů potřebuji 3 až 5 kroků, abych se ujistil, že tam to číslo není.
(Krok je v podstatě jednoduché CMP dalšího bajtu. Je to jen několik instrukcí.)
Pokud bych začal provádět nějaký výpočet, celková výpočetní náročnost by se zvýšila.
Proto je tento "primitivní" systém mnohem rychlejší než B strom.
Pokud jsou data v paměti, celé se to dokáže zpracovat v rámci několika instrukcí, protože se to vejde do Pipeline procesoru.
-
Bloom filter
S tím jsem samozřejmě obeznámený.
A pomohl teda? ::)
Ale jak to funguje teď:
1) Vezmu začátek čísla
1234 -> ten použiju jako index pole cisla[1234] a získám ukazatel do pole.
(Pokud index cisla[1234] ukazuje NULL, mám vyřízeno, což je asi 1/3 případů.)
Začnu prohledávat od daného místa, kam ukazuje tento ukazatel a ve 1/3 případů mi stačí dva kroky, abych dokázal vyloučit, že číslo není invalidované.
Ve zbylé 1/3 případů potřebuji 3 až 5 kroků, abych se ujistil, že tam to číslo není.
Tomu se říká open addressing hashtable.
(Krok je v podstatě jednoduché CMP dalšího bajtu. Je to jen několik instrukcí.)
Pro vyloučení přece potřebuješ porovnat ne následující bajty, ale celá čísla, a to dokud se nezmění ten začátek. Kolik je ten začátek a tedy kolik je průměrná délka řetězce? Čekal bych z těch čísel co jsi napsal tak 3 bajty.
Pokud bych začal provádět nějaký výpočet, celková výpočetní náročnost by se zvýšila.
Ano, ale necachovaný fetch z paměti je klidně 200 instrukcí (s tím že pomocí out-of-order execution a AVX scatter-gather instrukcí se tomuhle dá pomoct), takže pokud ten výpočet bude kratší než toto a zabrání tomu fetchi (protože se díky tomu podaří požadavek uspokojit z cache), tak se to vyplatí.
Pokud jsou data v paměti, celé se to dokáže zpracovat v rámci několika instrukcí, protože se to vejde do Pipeline procesoru.
Furt jsi nám neřekl jak to s tou pamětí funguje, když DDR4-3200 (AFAIK nejrychlejší paměť co jde dneska koupit) má podle Wikipedie Peak transfer rate 25.6 GB/s, takže ta svoje data nemáš šanci protáhnout ani quad-channelem.
Slovník se ještě nějakou dobu do paměti vejde
No to doufám, vždyť jsi psal že má řádově 400 MB…
-
Pro vyloučení přece potřebuješ porovnat ne následující bajty
Proč?
Měj dvě stejně dlouhá čísla:
1234 (vzor)
1235
1236
1301
Na to, abys zjistil, jestli je číslo ve slovníku (samozřejmě setříděném), tak provnáš jedničky a víš, že zatím to je stejné, dvojky, stejné a už víš, že ta čísla stejná nejsou. A skončil jsi nejpozději u čísla 1301. Výpočetně je výhodnější porovnávat bajty...
Ano, ale necachovaný fetch z paměti je klidně 200 instrukcí
To je teorie a netvrdím, že není správná. Ale teoreticky by i B-tree mohl být výhodnější a není.
AVX jsem řešil a popravdě si nejsem jistý, jestli bych něco získal, protože HT (jedu dvě vlákna na každém CPU).
Furt jsi nám neřekl jak to s tou pamětí funguje
Běží to na běžných AMD Ryzen 1700X a 3700X, vycházely cenově nejlépe, za cenu jednoho pořádného serveru s Xeonem bylo 12 strojů. Takže Ram v Dualchannel. Proč je to důležité, protože na každém virtuálním procesoru běží tyto procesy dva. To zároveň zmírňuje výpadek stránky, jádro po dobu čekání provádí druhé vlákno. AVX se bojím, že by při takovém počtu vláken (15) dělalo spíš problémy, pokud se nepletu, AVX jednotky nejsou zdvojené.
No to doufám, vždyť jsi psal že má řádově 400 MB…
Pro každé vlákno, tedy *15 procesů.
Primárně nechci řešit stávající slovník, možná rozšířit délku indexu a použít předtříděná data.
AVX ale není plácnutí do prázdna, sám jsem o tom přemýšlel, ale ještě se mi do toho nechce.
Oproti tomu předtřídění mohu mít "zadarmo".... znáte to, lenost...
Budu to muset vyzkoušet, jestli to má dopad.
V podstatě si mohu vytvářet bloky o délce 8kb, které budu porovnávat s 8kb bloky, ale jen pokud to budu mít předtříděné... tj. začátek čísla srovnaný.
Ještě jedna věc je zajímavá, jen u velmi málo čísel je potřeba porovnat víc než osm bajtů.
Možná že zarovnáním pole bych mohl dosáhnout přesně toho, co potřebuji... ::)
Tj. mít ta pole dvě, jedno "úzké", oproti kterému provádím většinu porovnání a pokud dojedu na konec pole, mohu s tím stejným indexem hledat ve druhém poli, dokonce od stejné pozice ::)
-
(sorry) duplikát místo editu
-
Mna stale este zaujima zdroj streamu dat. Prichadzaju po sieti (json, xml, nejaka vhodnejsia datova struktura), alebo sageneruju nejakym algoritmom....
Tiez by som sa nebal toho, ze sedliacky rozum hovori, ze daco musi byt pomalsie ako daco ine. Proste to vyskusat a mozno sa budes divit...
PS: Rad by som sa pustil do tejto ulohy :D Znie dost zaujimavo. Pripomina mi to inu trivialitu, ktora pripocitavala k nejakym pocitadlam (tych bolo niekolko desiatok milionov) vstupne cisla. Teda vstup bol napriklad dvojica (pocitadla: 1234567, pripocitaj: 33.33). Genialne jednoduche, jednoducho paralelizovatelne, az na zaklad (k procesoru) jasna operacia ADD.... Dalo sa to dostat do rychlosti latencie L2 cache (kam sa takmer vosli vsetky pocitadla), ale problem je, ked si to nasledne pustis aj tak na virtuale spolu s X inimi srandami, co ti tu cache potensialne vyzeru...
-
zdroj streamu dat. Prichadzaju po sieti (json, xml, nejaka vhodnejsia datova struktura)
Data jsou binární a sice stream, který se parsuje po 512bit blocích, případně 1024. Technicky na tom není nic zajímavého. XML a JSON musíš jednak vytvořit a jednak parsovat, řada těch operací je neuvěřitelně pomalá (hlavně operace s řetězci).
Asi mi nezůstane nic jiného, než pokusně zjistit, jaká je penalizace při zápisu mimo dostupnou stránku. ::)
Stejně to nejspíš dopadne s tím odesíláním dat pryč, kolik takový UDP datagram sežere výkonu CPU netuším...
Jestli to je levná nebo drahá operace...asi bude záležet na ovladačích, co bude počítat kontrolní součet a kolik IRQ se provede. Nicméně tohle už je magie, které jsem se chtěl vyhnout...
...jen tak OT, teď musím něco napráskat v C#, tohle přepínání mozku z C do C# a z C# to C...bolí...
Shodou okolností musím generovat výstupní XML :-( fuj...
Ještě mě napadlo, že bych zkusil ten svůj program přeložit kromě GCC i Clangu. Jestli nějaký *magic* nezvládne překladač...
-
Asi mi nezůstane nic jiného, než pokusně zjistit, jaká je penalizace při zápisu mimo dostupnou stránku. ::)
Stejně to nejspíš dopadne s tím odesíláním dat pryč, kolik takový UDP datagram sežere výkonu CPU netuším...
Proč řešíš takové složitosti, jaký zápis, k čemu? Cuckoo filtr jsou dva lookupy, které můžeš prefetchovat, ale asi to ani nebude potřeba, protože celý filtr vejde do cache. Pokud máš náhodná data, tak to vyřeší 99+% případů. Nějaké UDP pakety a zbytečné zápisy jsou oproti tomu asi tak milionkrát pomalejší.
-
Ahoj, divoká myšlenka:
- čísla jsou 512-bitová => obor hodnot je obrovský
- slovník má kolem 400 MB, tedy v něm je asi 400/8 = 50M položek
50M je proti 2^512 tak nevýznamné číslo, že určitě půjde obrovské množství dat vytřídit pomocí předpočítaných patternů.
Kdybych to zjednodušil na bajty (8-bitová čísla), a měl slovník pro jednoduchost třeba { 0,1,128 }, tak si můžu pomocí testu (x & 0b01111110) == 0 eliminovat většinu vstupních možností a teprve pro zbytek udělám vyhledání.
Nevím jestli na předpočítání těch optimalizačních testů z obsahu slovníku existují slušné algoritmy, ale vzhledem tomu že (velikost slovníku << počet možných čísel), mohla by taková optimalizace výrazně pomoct.
-
Ahoj, divoká myšlenka:
Zamyslím se nad tím...
Dalo by se to nějak rozvést?
Cuckoo filtr jsou dva lookupy
To ano, ale pro každé to vstupní číslo (slovník si předpočítám) musíš spočítat hash, jestli penalizace při výpočtu hashe nebude horší než prostý formát. ::) Pokud bych měl větší data než 512bitů, dávalo by to smysl, ale 512bitů jsou "malinká data" a je jich hodně. Představa, že by se mi celý slovník vešel do cache je lákavá, ale nejsem si jistý, protože ve slovníku je mnoho milionů položek. Nedokážu na to korektně odpovědět.
Nějaké UDP pakety a zbytečné zápisy jsou oproti tomu asi tak milionkrát pomalejší.
Myslíš, že UDP má velkou režii? Osobně nemám ani tu nejmenší představu. Pro běžné použití tě to nezajímá, protože procesor jede 99% času stejně IDLE, ale při tomto použití...
V KAŽDÉM PŘÍPADĚ DÍKY! Potřebuji si to promyslet a vymyslet, kterým směrem se dám.
-
Ahoj, divoká myšlenka:
- čísla jsou 512-bitová => obor hodnot je obrovský
- slovník má kolem 400 MB, tedy v něm je asi 400/8 = 50M položek
50M je proti 2^512 tak nevýznamné číslo, že určitě půjde obrovské množství dat vytřídit pomocí předpočítaných patternů.
Kdybych to zjednodušil na bajty (8-bitová čísla), a měl slovník pro jednoduchost třeba { 0,1,128 }, tak si můžu pomocí testu (x & 0b01111110) == 0 eliminovat většinu vstupních možností a teprve pro zbytek udělám vyhledání.
Nevím jestli na předpočítání těch optimalizačních testů z obsahu slovníku existují slušné algoritmy, ale vzhledem tomu že (velikost slovníku << počet možných čísel), mohla by taková optimalizace výrazně pomoct.
Ano, takové algoritmy existují, jeden z nich se jmenuje Cuckoo filter ;). Nemá cenu znovu vymýšlet kolo, lepší je použít ověřená řešení.
-
A co je to za data? Protoze nejake aplikacne specificke veci lze zrychlit tim, ze postupny lookup se provede z jine pozice.
Ostatne to by byl i muj pristup - vzit slovnik, a vytvorit z nej optimalni strom = prvni lookup aby vyradil co nejvice polozek. Viz tvorbu stromu u Huffmana.
-
mozne optimalizace k otestovani:
- neporovnavat cisla od zacatku, ale v mistech, kde je nejvetsi pravdepodobnost, ze cislo neni ve slovniku, napriklad nejdive bajty 7 +8, pak 13+14, pak 1+2 etc..
- neporovnavat cela cisla na jednom jadru, ale vyhradit napriklad 10 jader na porovnani prvnich 4 paru bajtu (podle velikosti cache), coz zredukuje pocet cisel potencionalne ve slovniku napriklad na 1/100, tu pak zpracovat zbyvajicimy jadry.
- porovnat prvnich X paru bajtu najednou pro vetsi mnozstvi vstupu, nez bude treba 1000 vstupu jako kandidaty porovnat dale. To by taky melo udrzet pro vetsinu cisel informace v cache.
-
To ano, ale pro každé to vstupní číslo (slovník si předpočítám) musíš spočítat hash, jestli penalizace při výpočtu hashe nebude horší než prostý formát. ::)
Záleží na tom, co je to za data. Pokud jsou čísla víceméně náhodná, tak hash počítat vůbec nemusíš, jako hash poslouží část toho 512-bitového čísla. Pokud data moc náhodná nejsou, dá se hash spočítat třeba jako XOR částí čísla, to je rychlá operace a pro účely filtrování je to dostatečné.
Pokud se ti celý filtr podaří dostat do L2 cache, tak to škáluje s přidáváním jader lineárně, L2 je na Ryzenu exkluzivní k jádru.
-
A jeste mi chybi pocet matchu se slovnikem, ze vstupniho streamu. Jestli je to 1 z 1000, tak to snese hodne dlouhou latenci.
-
A jeste mi chybi pocet matchu se slovnikem
Match nastává cca jednou za tři až čtyři měsíce, naposledy minulé léto jeden a předtím v březnu dva.
Je okolo toho vždy hrozné haló, protože "match nesmí nastat"...
Jsou to 512bitová a 1024bitová čísla, takových čísel je opravdu hodně.
Nepříjemné je, že těch dat přitéká velké množství, nedají se dlouho skladovat, není na to kapacita a výsledek musí být znám do konce dne. Mimochodem, zápis na disky je poměrně drahá operace na procesorový čas.
mozne optimalizace k otestovani:
- neporovnavat cisla od zacatku, ale v mistech, kde je nejvetsi pravdepodobnost
- neporovnavat cela cisla na jednom jadru
První bod už mám (porovnávám od konce), druhý bod už mě taky napadl, ale na to je výhodné mít předem seřazená data. Proto jsem zmínil posílání UDP a zápisy mimo dostupnou paměť.
Nicméně tu padlo poměrně velké množství jiných nápadů, které budu muset prostě vyzkoušet...
-
to budou takove ty super-rychle obchodovaci operace na ruznych internetovych burzach ne???
-
zdroj streamu dat. Prichadzaju po sieti (json, xml, nejaka vhodnejsia datova struktura)
Data jsou binární a sice stream, který se parsuje po 512bit blocích, případně 1024. Technicky na tom není nic zajímavého. XML a JSON musíš jednak vytvořit a jednak parsovat, řada těch operací je neuvěřitelně pomalá (hlavně operace s řetězci).
Asi mi nezůstane nic jiného, než pokusně zjistit, jaká je penalizace při zápisu mimo dostupnou stránku. ::)
Stejně to nejspíš dopadne s tím odesíláním dat pryč, kolik takový UDP datagram sežere výkonu CPU netuším...
Jestli to je levná nebo drahá operace...asi bude záležet na ovladačích, co bude počítat kontrolní součet a kolik IRQ se provede. Nicméně tohle už je magie, které jsem se chtěl vyhnout...
...jen tak OT, teď musím něco napráskat v C#, tohle přepínání mozku z C do C# a z C# to C...bolí...
Shodou okolností musím generovat výstupní XML :-( fuj...
Ještě mě napadlo, že bych zkusil ten svůj program přeložit kromě GCC i Clangu. Jestli nějaký *magic* nezvládne překladač...
Skúsil by som na tvojom mieste venovat cca tyzden (5MD) spark-u a nabastlit to v tom. Parkety si rozdelovat napriklad podla hash-u (ak to zaezpeci rovnomerne rozlozenie blacklistu) a nasledne to davat na dedikovane stroje. Nevyuzivat viac vlakien, ako je nutne z pohladu vyuzitia celej cache a spustit to na par strojoch. Imho teraz, ked vyuzivas vsetky vlakna to je pomalsie, ako keby si vyuzival iba stvrtinu vlakien (tusim 4 vlakna budu mat spolocnu L1 cache, ci ako to ma ryzen).
PS: Overheadu sa nebat, bol by to skor proof-of-concept. Samozrejme, ak ti chodia data po sieti (stale neviem), tak skusit rovno na zdroji dat, ci sa daju smerovat podla hash-u. Ak citas z disku, tak skusit pred zapisom na disk rovno shard-ovat do roznych suborov aspon. Ak ti naozaj nezalezi na latencii, tak imho spark ti to zvladne za polovicny (pravdepodone mensi) cas, ako aktualne popisany pristup (na styroch strojoch).
-
jako hash poslouží část toho 512-bitového čísla
Ale tohle já přesně dělám.
Vezmu kus čísla a zjistím, jestli pro něj je v tabulce nějaká hodnota, používám jeho fixní část jako index.
Pokud daný index není NULL, pak teprve začnu provádět porovnání.
Samozřejmě neprocházím celý seznam, první dva bajty čísla udávají startovní pozici, kde začínám hledat.
(Forma hash tabulky, B-strom nepodává dobrý výkon, má totiž problém s cache.)
...mohl bych to rozšířit na čtyři bajty... ale několik milionů položek * 4 bajty = otravně velké pole...
Což by nemuselo vadit, kdybych měl pole předtříděné, každému vláknu bych poslal to, co má v cache...
Proto jsem řešil, jestli zápis mimo cache je penalizován... ::)
-
spark-u a nabastlit to v tom
Adu ani Spark jsem už dlouho neviděl.
tak imho spark ti to zvladne za polovicny
Spark vs čisté C? a Spark že bude o polovinu rychlejší ???
Spark je interpretovaný jazyk ne? ::)
Už někdo mi říkal, ať to zkusím přepsat v Go nebo Rustu, ale Spark ???
-
Ale tohle já přesně dělám.
Vezmu kus čísla a zjistím, jestli pro něj je v tabulce nějaká hodnota, používám jeho fixní část jako index.
Pokud daný index není NULL, pak teprve začnu provádět porovnání.
Cuckoo filtr je sofistikovanější, používá dvě různé hashovací funkce, takže každá položka se může vyskytovat na dvou různých pozicích, proto taky potřebuje dva lookupy. To umožňuje položky během kostrukce filtru (zřetězeně) přesouvat v případě kolize, takže se dá prakticky dosáhnout až 95% naplnění filtru. Opravdu jsou data relativně malá, tady je kalkulačka pro bloom filter (https://hur.st/bloomfilter/?n=5000000&p=0.01&m=&k=), pro 5 milionů prvků ve filtru a pravděpodobnost 1% false positive je velikost dat 5.7 MB, což typicky vejde celé do L3 cache. Cuckoo filter je prostorově ještě úspornější, pro něj jsem ale online kalkulačku nenašel.
-
Jo takhle...nezní to špatně!
-
spark-u a nabastlit to v tom
Adu ani Spark jsem už dlouho neviděl.
tak imho spark ti to zvladne za polovicny
Spark vs čisté C? a Spark že bude o polovinu rychlejší ???
Spark je interpretovaný jazyk ne? ::)
Už někdo mi říkal, ať to zkusím přepsat v Go nebo Rustu, ale Spark ???
Tu ide skor o to, ze moj subjektivny pocit je, ze sa v tom kusok "placas" a nechce sa ti do prototypovania UDP verzie. Pri pouziti spark-u (ano, bezi nad JVM, je pisany zvacsa v scala-e) by ti odpadol vyskum ako robis a odpadli by ti dalsie podruzne ulohy a za "hodiny" by si vedel zmenit cely pristup a videl by si ihned realny prinos zmeny. Takto to robis v nizkourovnovom jazyku a dovolim si tvrdit, ze i python by to dal dvojnasobne rychlejsie oproti aktualnej implementacii. Je potrebne sa ale nebat kusok komplikovanejsich datovych struktur a toho, ze "to nemoze byt rychlejsie". Proste sa nebranit Cuckoo filtru, lebo "hash je pomaly". Tam ide o to, ze namiesto 400MB blacklistu budes mat 1MB blacklist napriklad, ktory bude mat obcas false possitive hity, ktore budes musiet overit voci 400MB blacklistu, ale bude to dizajnovatelne percento a nebude ti rozhadzovat cache pri kazdej kontrole noveho vstupu.
PS: Vedel by si poslat ukazkove data? Myslim teda blacklist za jeden den a nejaku "minutu" vstupu? Je to zdielatelne (biznis/NDA rovina, ale i velkost)?
-
Vedel by si poslat ukazkove data? Myslim teda blacklist za jeden den a nejaku "minutu" vstupu?
To by asi nešlo, data nejsou moje.
Ty verze se vyvíjely, původně se ověřovalo pomocí DB, která byla neuvěřitelně pomalá.
(Zase to bylo implementačně jednoduché.)
Pak se přešlo na C# a Python, až pak na čisté C.
Každá nová verze byla řádově rychlejší, C oproti Pythonu 100x ...
B-tree napsaný oproti mé hash tabulce 6x...
Právě protože B-tree podával tak špatné výsledky, jsem trochu skeptický vůči těm filtrům, ale mohu se plést.
-
Az budete chtit na to dedikovany hw, treba s FPGA, tak se ozvete :) Zrovna hashe se tam pocitaji s nulovou cenou vuci propustnosti, pridana je jenom latence. Ale ty dva ruzne hashe by mela upocitat i grafika - navic je tam vyhoda velike propustnosti pameti. By me zajimalo jak moc ten slovnik lze zkomprimovat - a jaky je ocekavany narust poctu polozek, nebo trafficu.
Alternativne, co to zkusit na necem divocejsim - treba Phi 7250 (co tu mam), coz ma 16G rychle pameti na cipu (400GB/s+), takze cache miss (z 34MB) by nemusel tolik bolet. Plus to jde rozdelit na vice numa clusteru - nektera cast jader muze delat jen rychly filtr ze sve L1/2, a jine jadra pak full lookup z ram toho, co zbyde. U bezneho cpu jste precejen vice omezen dvojkanalovou pameti.
Pripadne se pohrat s tim, ze eliminacni cast stromu bude upocitatelna z cache (je treba dat pozor na to, co tvori klic do cache pro vas konkretni cpu a kolik podobnych zaznamu to dokaze ulozit - takze ta forma ulozeni stromu v pameti bude hodne specificka), Koncove seznamy pak mit v pameti ktera se necachuje - tim zarucite to, ze tyto nahodne pristupy do ram nebudou penalizovat vzdy potrebnej rychly rozhodovaci strom.
Predpokladat, ze v cache je poslednich XY MB pouzitych dat je naivni a ve skutecnosti to tak opravdu nefunguje - klicem byva hash z adresy a pro stejny hash si to pamatuje treba 8 hodnot :)
-
Díky za nabídku, vážím si jí.
Výhoda Phi je v tom, že na to není potřeba žádný extra kód, ale stačí prosté Cčko.
Nakonec se od toho ustoupilo, protože projekt ještě několik let poběží a Intel s Phi skončil.
https://www.cnews.cz/intel-nahle-zcela-zrusil-vypocetni-karty-xeon-phi-vsechny-zminky-o-nich-zmizely/
Důvod, proč nepoužít FPGA je snadný, jeden programošťoural (já) + hromada hardware, vyjde levněji než to táhnout přes FPGA. Doba opravy +/- desítky minut, nasazení dalšího stroje minuty, v nejhorším objednám v Alza a večer tu budu mít dalších dvacet strojů.
Tím ovšem neříkám, že FPGA se mi nelíbí :-) Osobně bych si na tom někdy něco hrozně rád vyzkoušel, ale asi tam je dost strmá křivka učení, nikdy jsem do toho hlouběji nepronikl a to v jiných (i srovnatelně obtížných) oblastech jsem uspěl...
-
řeším takový zapeklitý problém, potřebuji extrémně rychle kontrolovat, jestli určité číslo (64 bajtů) není ve slovníku.
Aktuálně stíhám asi dvě miliardy porovnání za vteřinu, ale potřebuji víc, ideálně 10x víc...
Nějak mi neštymujou čísla, ale možná mi něco nedochází:
Chápu správně, že "porovnáním" nazýváš test, zda číslo je nebo není ve slovníku? Tedy aktuálně zpracováváš 2 mld čísel za vteřinu?
Tedy taháš 2 gigaporovnání za vteřinu * 64 bajtů = 128 GB dat za vteřinu.
Jak to dokážeš protáhnout RAMkou? A už vůbec nerozumím, jak to ukládáš na disk?
-
Viz:
data se stejně ukládají do pole rychlostí asi 2 GB/s a za hodinu se nezaplní víc než několik 5-7 TB prostoru
To jsou běžné hodnoty na kontroléru (na vstupu), tedy "běžný vstup" je řekněme miliony čísel na vteřinu.
Špičky jsou jinde, navíc je to celé rozložené mezi víc strojů a ověření je jen jednou z úloh zpracování.
Zajímavá by byla možnost i opakování dávek z předchozích dnů. Nicméně, pokud zlepším propustnost celého systému, mohu žádat o víc dat = dostanu víc peněz. A popravdě o to tu jde v první řadě, trochu to zefektivnit nebo se na to podívat říct "líp už to nejde", pak vím, že to musím hnát počtem strojů, které se musí nejen napájet, ale i chladit...
-
A kdyby to někoho zajímalo, jen tak pro pobavení, pouštím to přes utilitu screen, aby to běželo na pozadí a neskončilo při ukončení SSH session, plus utilita parallel, aby mi běželo 15 úloh na každém fyzickém CPU. (16 zlobí...) To není moc elegantní co? :P Ale funguje to. Psaním vícevláknového serveru jsem se nezatěžoval. :P
Nějaký den omrknu, jestli některé patche, co lezou do jádra, to všechno zase nezpomalily :(
To se děje častěji, než nalezení nevalidního čísla. Budu muset pohledat nějaký aktuální článek, co v jádru všechno vypnout, abych získal pár procent výkonu navíc. ::)
-
To je asi docela zásadní chyba pouštět to přes parallel, protože procesy nesdílí paměť. Pokud na slovník pamět normálně alokuješ mallocem a nepoužíváš mmap, tak má každý proces vlastní stránky pro slovník, takže je v RAM zbytečně 15x to stejné a nejde to sdílet v L3 cache, která je společná pro více jader. Na tuto úlohu je jednoznačně lepší použít thready a ne procesy.
-
To je asi docela zásadní chyba pouštět to přes parallel, protože procesy nesdílí paměť. Pokud na slovník pamět normálně alokuješ mallocem a nepoužíváš mmap, tak má každý proces vlastní stránky pro slovník, takže je v RAM zbytečně 15x to stejné a nejde to sdílet v L3 cache, která je společná pro více jader. Na tuto úlohu je jednoznačně lepší použít thready a ne procesy.
Zajimave, mam dotaz, ladil(benchmarkoval) jsi nejak ty procesy? Ono context switche jsou dost drahe, pokud bys dokazal nejak sypat dostatek dat jednomu vlaknu, tkere je locknute na jednom core, tak by to mohlo udelat dost vykonu.
Dale jeste mirny offtopic, na zacatku jsi rikal, ze porovnavas nejdriv cast cisla. Beres tam v uvahu pipelining a ted nejaky loop unroll?
-
protože procesy nesdílí paměť
Ano, to je pravda, i proto uvažuji o setříděných vstupech.
Nicméně jsem dělal několik vícevláknových aplikací a musím říct, že to není tak snadné, jak to na první pohled vypadá.
Tady mám uptime v řádu měsíců.
ladil(benchmarkoval) jsi nejak ty procesy
Benchmarky mám na porovnání jednotlivých částí aplikace.
Při locknutí procesů na jednotlivá NUMA se objevuje podivné chování, kdy se jádro "zamyslí" a třeba 200msec nic nedělá.
Nepravidelně, nevím proč, prostě stojí. Výkon je měřitelně vyšší, pokud si všech patnáct procesů "plave" z jádra na jádro, proč nevím. Také jsem si původně myslel, že uzamčení procesu na jádro bude znamenat výkonový zisk.
Zajímavé je, že na Intelu se tohle neděje, ale výkon na Intelu je asi o 9% nižší na jádro (i8700), tak mě to netrápí.
-
Viz:
data se stejně ukládají do pole rychlostí asi 2 GB/s a za hodinu se nezaplní víc než několik 5-7 TB prostoru
To jsou běžné hodnoty na kontroléru (na vstupu), tedy "běžný vstup" je řekněme miliony čísel na vteřinu.
Špičky jsou jinde, navíc je to celé rozložené mezi víc strojů a ověření je jen jednou z úloh zpracování.
Zajímavá by byla možnost i opakování dávek z předchozích dnů. Nicméně, pokud zlepším propustnost celého systému, mohu žádat o víc dat = dostanu víc peněz. A popravdě o to tu jde v první řadě, trochu to zefektivnit nebo se na to podívat říct "líp už to nejde", pak vím, že to musím hnát počtem strojů, které se musí nejen napájet, ale i chladit...
OK, zkusím si tedy vydedukovat, jak rychle to tedy opravdu zpracováváš, tím, že budu ignorovat tvůj první příspěvek o dvou miliardách porovnání za vteřinu, a spočtu si to z těch 2GB/s.
2GB/s ~= 30 000 000 testovaných 64bajtových čísel za vteřinu.
Zkusil jsem si to bez větších chytristik naprogramovat v Rustu.
Slovník 10 000 000 čísel (tím o něco překračuji těch 400MB slovníku, co jsi někde zmiňoval), test kdy je jeden hit na 9999 misses.
Stroj: Intel(R) Core(TM) i5-2400 CPU @ 3.10GHz, čtyřjádro, tedy dneska skoro kancelářská plečka
Program běží ve čtyřech vláknech.
V opravdu jednoduchoučké verzi dosahuji cca 37 000 000 testů/s
S menší chytristikou se dostanu na 55 000 000 testů/s
Víc jsem nezkoušel, už takhle jsem tím dneska promarnil skoro čtyři hodiny (to se mi nemělo stát, že se objevil takovýhle zajímavý problém)
Jsou to zajímavá čísla, nebo ne? Kolik to teda dělá tobě?
-
Viz:
data se stejně ukládají do pole rychlostí asi 2 GB/s a za hodinu se nezaplní víc než několik 5-7 TB prostoru
To jsou běžné hodnoty na kontroléru (na vstupu), tedy "běžný vstup" je řekněme miliony čísel na vteřinu.
Špičky jsou jinde, navíc je to celé rozložené mezi víc strojů a ověření je jen jednou z úloh zpracování.
Zajímavá by byla možnost i opakování dávek z předchozích dnů. Nicméně, pokud zlepším propustnost celého systému, mohu žádat o víc dat = dostanu víc peněz. A popravdě o to tu jde v první řadě, trochu to zefektivnit nebo se na to podívat říct "líp už to nejde", pak vím, že to musím hnát počtem strojů, které se musí nejen napájet, ale i chladit...
OK, zkusím si tedy vydedukovat, jak rychle to tedy opravdu zpracováváš, tím, že budu ignorovat tvůj první příspěvek o dvou miliardách porovnání za vteřinu, a spočtu si to z těch 2GB/s.
2GB/s ~= 30 000 000 testovaných 64bajtových čísel za vteřinu.
Zkusil jsem si to bez větších chytristik naprogramovat v Rustu.
Slovník 10 000 000 čísel (tím o něco překračuji těch 400MB slovníku, co jsi někde zmiňoval), test kdy je jeden hit na 9999 misses.
Stroj: Intel(R) Core(TM) i5-2400 CPU @ 3.10GHz, čtyřjádro, tedy dneska skoro kancelářská plečka
Program běží ve čtyřech vláknech.
V opravdu jednoduchoučké verzi dosahuji cca 37 000 000 testů/s
S menší chytristikou se dostanu na 55 000 000 testů/s
Víc jsem nezkoušel, už takhle jsem tím dneska promarnil skoro čtyři hodiny (to se mi nemělo stát, že se objevil takovýhle zajímavý problém)
Jsou to zajímavá čísla, nebo ne? Kolik to teda dělá tobě?
psalo se tu o ruznych algoritmech, co's pouzil ty?
slovnik je v RAM?
-
Viz:
data se stejně ukládají do pole rychlostí asi 2 GB/s a za hodinu se nezaplní víc než několik 5-7 TB prostoru
To jsou běžné hodnoty na kontroléru (na vstupu), tedy "běžný vstup" je řekněme miliony čísel na vteřinu.
Špičky jsou jinde, navíc je to celé rozložené mezi víc strojů a ověření je jen jednou z úloh zpracování.
Zajímavá by byla možnost i opakování dávek z předchozích dnů. Nicméně, pokud zlepším propustnost celého systému, mohu žádat o víc dat = dostanu víc peněz. A popravdě o to tu jde v první řadě, trochu to zefektivnit nebo se na to podívat říct "líp už to nejde", pak vím, že to musím hnát počtem strojů, které se musí nejen napájet, ale i chladit...
OK, zkusím si tedy vydedukovat, jak rychle to tedy opravdu zpracováváš, tím, že budu ignorovat tvůj první příspěvek o dvou miliardách porovnání za vteřinu, a spočtu si to z těch 2GB/s.
2GB/s ~= 30 000 000 testovaných 64bajtových čísel za vteřinu.
Zkusil jsem si to bez větších chytristik naprogramovat v Rustu.
Slovník 10 000 000 čísel (tím o něco překračuji těch 400MB slovníku, co jsi někde zmiňoval), test kdy je jeden hit na 9999 misses.
Stroj: Intel(R) Core(TM) i5-2400 CPU @ 3.10GHz, čtyřjádro, tedy dneska skoro kancelářská plečka
Program běží ve čtyřech vláknech.
V opravdu jednoduchoučké verzi dosahuji cca 37 000 000 testů/s
S menší chytristikou se dostanu na 55 000 000 testů/s
Víc jsem nezkoušel, už takhle jsem tím dneska promarnil skoro čtyři hodiny (to se mi nemělo stát, že se objevil takovýhle zajímavý problém)
Jsou to zajímavá čísla, nebo ne? Kolik to teda dělá tobě?
psalo se tu o ruznych algoritmech, co's pouzil ty?
slovnik je v RAM?
HashSet :-) Zkoušel jsem i dvě implementace Cuckoo filteru, co tu zmiňoval Linuxák, ale vycházelo to pomaleji, ta Rustovská HashSet je asi dost optimalizovaná. Slovník je samozřejmě v RAM, ale jen jednou, nikoliv pro každý proces extra jak to má OP, je to vícevláknová aplikace.
Drobnou chytristiku si zatím nechám pro sebe, ale je to vcelku banalita a stejně to výkon nezvyšuje nějak kulervoucím způsobem (asi o 30%).
Ještě omluva. Ve skutečnosti je lepší verze jen asi 38 000 000 testů/s, nikoliv 55 000 000 testů/s. Měl jsem příliš malou testovací sadu (10 000 čísel, pro každé vlákno samozřejmě jiná), kterou jsem recykloval dokola, a nějaký čas se šetřil tím, že byla celá v nějaké L? cache, což samozřejmě v reálu nebude. Zvýšil jsem testovací sadu na 1 000 000 čísel, a výkon spadl na čísla uvedená výše.
-
alex6bbc:
- Pokud thready sdílí jen read only memory, tak jsou (skoro :-)) naprosto bezpečné.
- Plánovače jsou zpravidla tak dobré, že afinita u procesoru toho moc nevylepší. Plánování procesů je magie, do který bych se bejt tebou nepouštěl.
registrovany_ava:
a i tak je to rychlejší, než Ty filtry, co by se do L2 vejít měly?
-
golang, naplneni mapy 40 miliony uint64 a pak 600 milionu prohledavani v mape, cisla jdou za sebou.
jedno vlakno na i9-8950hk, cas procesu 42 sekund.
--------------------------------------------------
package main
import "fmt"
func main() {
var slovnik = make(map[uint64]uint64)
var i uint64
for i = 0 ; i < 40000000; i++ {
slovnik\[i\] = i+4
}
nalezeno := 0
for i = 0 ; i < 600000000; i++ {
_, ok := slovnik\[i\]
if ok {
nalezeno++
}
}
fmt.Println("nalezeno=",nalezeno)
}
-
registrovany_ava:
a i tak je to rychlejší, než Ty filtry, co by se do L2 vejít měly?
Jo, je, taky mě to překvapilo. Možná jsou bídně implementovaný, ale nechtělo se mi zkoušet další implementace a víc se v tom vrtat, už takhle mi stojí práce..
-
golang, naplneni mapy 40 miliony uint64 a pak 600 milionu prohledavani v mape, cisla jdou za sebou.
jedno vlakno na i9-8950hk, cas procesu 42 sekund.
my ale netestujeme 64bitová ale 64BAJTOVÁ čísla. A i kdyby to byla 64bajtová čísla tak výsledek nic moc, 14 000 000 testů za vteřinu, to to mám skoro třikrát rychlejší,
-
registrovany_ava:
a i tak je to rychlejší, než Ty filtry, co by se do L2 vejít měly?
Jo, je, taky mě to překvapilo. Možná jsou bídně implementovaný, ale nechtělo se mi zkoušet další implementace a víc se v tom vrtat, už takhle mi stojí práce..
Tak mám 80 000 000 testů/s, stále bez použití probabilistických filtrů :-)
-
Tak mám 80 000 000 testů/s, stále bez použití probabilistických filtrů :-)
....já...já...já teď hledám jestli berou u dopravních podniků průvodčí :-\
-
Tak ja si napsal taky jednoduchy test (1h, neco pres 100 radku), testovano na zcela nahodnych datech (z urandom, jak pro data tak pro slovnik s 10M polozkami). #nocheat really.
Ze vstupnich 64-byte se pocita 32bit hash (xor, podminen nahodnymi daty v objektech) ktery je pak index do LUT pole (slovniku) o 4G polozkach, tim ze je tam obsazeno jen 10M zaznamu, tento vstupni filtr redukuje nutnost plneho porovnani cca 1:400. Ze neni match trva vzdy 1 nahodne cteni z pameti, kdyz je, je to o neco vice (kontrola celeho retezce, ze seznamu linkovaneho z LUT (zde se vyuzije cache, ze 64B se nacte jednou pametovou transakci), adresaci seznamu resim proprietarne at se me LUT vejde do mene nez 16G ram a vyzaduje se, aby hash distribuoval hodnoty rovnomerne).
Z 10M * 64B zajmovych polozek ve slovniku pri zhasovani na 32bit zatim taky nemam kolize - takze efektivita vylouceni bude narustem polozek casem klesat - nastesti to znamena zachovani max 1 polozky v seznamu pro plne overeni. Prumerne se dela tedy 399*1 nahodne + 1*3 souvisle pametove operace pro 400 testu.
Staci vysoke frekvence cpu (hash se spocte z L1, ma minimalni dopad na vykon) a hlavne rychle pameti s nizkou latenci - tohle reseni je vlastne limitovano pameti.
Bez specialni mmx/sse/avx onanie, bez prefetchu, jen primitivni C kod, jde zpracovani z prednacteneho pole z pameti takto:
X3430 4C/4T @ 2.40GHz (2ch DDR3-1333 ecc reg), zde kompilovano s gcc9.2 -O4:
# 4 * 26.4 = 105.6 MT/s
# 8 * 14.8 = 118.4 MT/s
Phi7250 68C/288T @ 1.4G (58c/58t pouzitelnych ze starsiho gentoo livecd), stejna binarka tudiz neoptimalni -march, bez DDR4, jen onchip 16G MCDRAM:
# 8 * 14.7 = 117.6 MT/s
# 16 * 15.1 = 241.6 MT/s
# 32 * 14.5 = 464.0 MT/s
# 64 * 12.5 = 800.0 MT/s
Vypusteni vypoctu hashe pridava na vykonu cca 50% - takze v pripade paralelizace cekani na lookup (pres prefetch) a vypoctu dalsiho hashe tohle opravdu lze ziskat.
Prinos rychle pameti je evidentni :-) Myslim ze dosazeni 2GT/s po optimalizacich a s jadrem co umi SMT2/SMT4 je na Phi i realny, ale 128GB/s dat - vstupniho streamu pro tuhle kadenci tam ale nikdy nedostanete. (36L pcie gen3 da cca 32GB/s, a dve 100G rozhrani (eth/OPI/IB) po x16 pak prinejlepsim 25GB/s dohromady).
K testovani 25Gb/s streamu (vase pripojeni) postaci cokoliv co zvladne overovani rychlosti 50MT/s.
pozn. 1T = 1 transakce (test) s 512bit daty.
Rekl bych zaverem.. uzke hrdlo bude jinde, nez v cache :-)
-
Tak mám 80 000 000 testů/s, stále bez použití probabilistických filtrů :-)
Tazatel v prvním příspěvku píše, že má 2 miliardy testů/s, tedy 25x víc. Bohužel nám stále neodpověděl (pokud jsem to nepřehlédl, přijde mi, že diskuze podivně divergovala) na otázku, jak těch 128 GB/s do toho počítače dostává.
-
Máš v zásadě dvě možnosti. Jedna už padla někde na začátku - seřadit čísla i databázi a zvýšit tak šanci na cache-hit. Nemusí být nutně řazeno lexikograficky, může být podle hash apod - takže řazení může být konstantní operace (resp zařazení - v podstatě radix sort).
Druhá možnost, je klasická hash tabulka, ale trochu chytřeji orientovaná. Hash nesmí být per entry, ale musí být součástí indexu a měl by být taky dostatečně velký. Část hash (nebo případně agregovaný přes shift + xor + mask) se použije jako index do indexovací tabulky, najde se seznam teoretických záznamů v indexu, ale ještě u těch pointerů je uložený kompletnější hash, který eliminuje false hit. Až když větší hash odpovídá, jde se teprve na skutečnou entry, která může obsahovat zbytek hash (i index může obsahovat třeba jen 4-6 byte hash kvůli minimalizaci paměti) a samozřejmě kompletní data pro klíč a hodnotu. Použil jsem podobné řešení kdysi na persistentní mapovanou DB (takže o to horší, že data vlastně nebyly ani v RAM) a ten krok s umístěním hash do indexu zvedl performance o řády (klíčem bylo mít dost RAM aspoň na udržení indexu). Tady bude pořád limit cache a paměťová náročnost je samozřejmě daná počtem záznamů v databází, nikoli počtem look-ups.
-
Ahoj,
nenasadil jsem žádný z filtrů, ale rozšířil jsem vstupní délku klíče.
Tj. beru z čísla delší část, což nakonec zcela vyřešilo můj problém.
A jako poděkování, spíš tak pro zajímavost:
(https://i.imgur.com/T9ipzsg.png)
Případně odkaz (kdyby se ukazovala reklama): https://imgur.com/T9ipzsg
Ryzen 1700x vs Ryzen 3700x, oba stejná zátěž, stejná deska, stejný chladič, stejné paměti, stejný Bios. Rozdíl je skutečně jen v tom CPU.
(Stejné výsledky to ukazuje i na jiných strojích, není to unikát.)
První údaj: Získání balíku dat, pouze memcopy.
Naplnění zprávy je její vlastní zpracování. Probíhá v cache, zprávy jsou "malé".
Serializace serializuje zprávu (vytvoří jí ze struktury).
Test 1
Test 2
A nakonec ještě prověření, které má vyloučit, že zpráva už byla použita, to je ten můj test se slovníkem v paměti.
Ty hodnoty jsou dost rozdílné, měřeno pod plnou zátěží (15 vláken), v některých případech je Ryzen 3700x až dvakrát rychlejší. A čím větší zátěž, tím víc se ukazuje rozdíl mezi Ryzen 1700x a 3700x.
Samozřejmě jsem z hodnot nevytvářel žádný graf, hodnoty jsou rozdílné +/- deset procent pro každý test, ale rozdíl 30-50% je vidět v každém testu.
Každopádně mám zase nad čím přemýšlet, testy 1 a 2 dokážu přesunout na grafickou kartu, nebo je upravit a použít AVX.
Naplnění zprávy přepsat nezvládnu, ta knihovna není moje, jako by jí psal o divokém mejdanu Carmack s Bernstainem...
-
Hodnoty jsou vteřiny, puštěno na jednom vláknu (celkem běží 15 vláken), balík 1 milionů zpráv, tj. pokud dobře počítám, na tom Ryzen 3700x dám za vteřinu 10 mil. na proces * 15 vláken. Což je pořád významně méně, než 80 milionů na tom čtyřjádrovém 2500Kčku.
A takhle vypadají hodnoty, pokud proces běží na volném jádru (ostatní procesy vypnu nebo nechám běžet jen 7+1 proceů):
(https://i.imgur.com/iP27yPa.png)
https://imgur.com/iP27yPa
Doplněno: Ať jsou výsledky se zátěží vedle sebe:
(https://i.imgur.com/T9ipzsg.png)
https://imgur.com/T9ipzsg
-
(https://i.imgur.com/T9ipzsg.png)
..
Každopádně mám zase nad čím přemýšlet, testy 1 a 2 dokážu přesunout na grafickou kartu, nebo je upravit a použít AVX.
Naplnění zprávy přepsat nezvládnu, ta knihovna není moje, jako by jí psal o divokém mejdanu Carmack s Bernstainem...
No, asi je ti jasný, že i kdyby se ti podařilo zrychlit kroky "Serializace, Test1, Test2, Prověření," které teď na prvním obrázku trvají 2.07 vteřin, 1000000x, výsledek bude kvůli "Naplnění" stejně rychlejší jen (2.07 + 2.8 ) / (0.00000207 + 2.8 ) = 1.74x. Amdahlův zákon (taky bych chtěl aby podle mě někdo pojmenoval trojčlenku) je neúprosný, možná se na ten mejdan s Carmackem a Bernsteinem budeš muset přidat..
-
skus Apache Ignite, data nacacheuj do ramky a data distibuuj medzi nody, skaluje to horizontalne a linearne, ked nemas near cache ale cisto klient/server tak si limitovany "hrubkou rury" jake mas k tomu clusteru siet.
https://apacheignite-cpp.readme.io/docs/getting-started
-
asi je ti jasný
To ano, ale zrychlení o 100% znamená úsporu strojů.
Možná zkusím použít jiný překladač a nastuduju si nějaké optimalizace, které bych pro GCC mohl zapnout na ten první krok.
možná se na ten mejdan s Carmackem a Bernsteinem budeš muset přidat
Vařím dobrý kafe, to ano, kafe bych jim vařit mohl, ale tím to končí.
Každopádně všem díky, znovu se v tom pohrabu a zkusím část těch nápadů tady ve vláknu.
Děkuju :-)
-
asi je ti jasný
To ano, ale zrychlení o 100% znamená úsporu strojů.
možná se na ten mejdan s Carmackem a Bernsteinem budeš muset přidat
Vařím dobrý kafe, to ano, kafe bych jim vařit mohl, ale tím to končí.
Každopádně všem díky, znovu se v tom pohrabu a zkusím část těch nápadů tady ve vláknu.
Děkuju :-)
(V následujícím textu vycházím z tohoto obrázku, z toho nahoře:)
\(https://i.imgur.com/iP27yPa.png)
https://imgur.com/iP27yPa
100% (zrychlení 2x) by bylo hezký, ale
Teoretické maximální zrychlení při absolutní optimalizaci (čas 0s) všech kroků kromě naplnění je jen 1.74x, jak jsem psal výše.
Teoretické max. zrychlení při absolutní optimalizaci pouze kroku Prověření (nad kterým jsme tu trávili tolik času) je (4.8 + 0.06 ) / (4.8 ) = 1.0125x, teď už asi vůbec nestojí za to nad tím přemýšlet.
Naopak teor. max. zrychlení při optimalizaci Naplnění je 2.36x, to už vypadá jako hotspot, nad kterým stojí za to přemýšlet, i když se do toho člověku tolik nechce, je to bohužel na místě kde to může být užitečné.
Napsat jednotkové testy a property testy na ověření, že původní implementace a nová implementace dělají pořád to samé, benchmarkovat, pustit na to třeba CallGrind a KCacheGrind, třeba se něco povede..
Samozřejmě neznám skutečnou situaci, třeba je to opravdu rada mimo... Ale ty meze zrychlení jsou neúprosné.
-
Samozřejmě máš pravdu, ale pokud bych první z těch testů přepsal na AVX, čistě teoreticky, i když AVX jednotky nejsou zdvojené a není u nich výkonový zisk na HT, měl bych nějaký výkon navíc dostat, protože zbylé části programu nevyužívají AVX.
Výkon toho prohledávání byl horší, inspirovali jste mě k pár krokům, no a po několika drobných úpravách se z toho stalo opravdu něco, co nemá smysl dál řešit. Je to marginální záležitost.
Nástroje typu "CallGrind a KCacheGrind" neznám, podívám se na ně. Děkuju :-)
Výkon na tom Phi vypadá docela dobře, koukal jsem, že deska stojí 12k a procesory jsou fakticky zadarmo (3k za 64 jader na e-bay). Velmi dobrý tip! Děkuju!
PS: Náhodou nějaký návod "pro blbé", jak proniknout do FPGA?
Přiznám se, že nemám ponětí, jak rychle to může běžet ve srovnání s běžným CPU nebo GPU.
Chápu, že hardware za 50 000 tisíc je schopný běžný procesor naprosto deklasovat.
Ale co třeba takový nějaký board?
https://www.aliexpress.com/item/4000176584679.html (https://www.aliexpress.com/item/4000176584679.html)
(https://ae01.alicdn.com/kf/H5426a5b4adbb4310b7e4fd9e9303b234P/XC6VLX365T-ml605-xilinx-fpga-board-Virtex-6-fpga-board-pcie-board-2-X-SODIMM-DDR3-2.jpg)
Jak to může být rychlé?
Podobně jako kdybych ten výpočet pustil na highendové VGA kartě?
Pomalejší? Rychlejší?
Pokud bych totiž reorganizoval strukturu a sestavená data odsouval na samostatnou mašinu, mohl bych ušetřit celkem dost výkonu.
Špičkový programátor, který by dokázal přepsat tu knihovnu, by si za rok mohl vydělat tolik, že by do konce života už nemusel chodit do práce, kdyby nechtěl a to myslím naprosto vážně.
-
AD FPGA: Samozřejmě jsem viděl běžné tutoriály, určitě dokážu rozsvítit ledku, ale naprogramovat v tom obyčejný cyklus for nebo provést nějakou složitější matematickou operaci...mi hlava nebere...
-
Ta FPGA deska je jiz spis stary kram. Jako muzes mi napsat mail, poslu NDA a pak ti reknu jak moc realny je s tim neco udelat v rozumnem case, nebo se proste stav na pokec :-) U FPGA nejsou genericke navody - protoze ten "kod" resi vzdy nejakou specifickou ulohu a vse potrebuje jiny a individualni pristup.
-
Promyslím si to a když tak se ozvu.
Mám s lidmi dost špatné zkušenosti, naprosto obecně, rozhodně se tě nechci dotknout.
Díky ;-)
-
Padly tu dobré rady. Vyzkoušel jsi ten Cuckoo filter? Zatím jsi neodpověděl, odkud bereš data. Jak řešíš sdílení té hashtabulky mezi procesy?
-
Padly tu dobré rady. Vyzkoušel jsi ten Cuckoo filter? Zatím jsi neodpověděl, odkud bereš data. Jak řešíš sdílení té hashtabulky mezi procesy?
Mrkni do předchozích příspěvků. Cuckoo jsem zkoušel já. Problém řešený v tomto vlákně už je v podstatě vyřešený, bottleneck je nyní jinde a je to zřejmě úplně jiná pohádka.
-
Čistě ze zvědavosti, jaké oblasti se vlastně celý ten projekt týká? Jestli je to tajné, tak to pochopím..
-
Nic, co bych chtěl veřejně prezentovat.
Je v tom prostor pro práci víc lidí, peníze tu jsou skutečně až ten úplně poslední problém.
Nicméně zvýšení výkonu 100x by zřejmě vyžadovalo přepsat to pod OpenCL nebo na FPGA.
Ale obávám se, že jsem to dostal tam, kam to jen šlo.
První implementace celé té blbosti v Pythonu zvládala jednotky operací za vteřinu.
Teď už to není tak špatné, ale silně pochybuji, že to půjde zrychlit 10x bez OpenCL neb FPGA.
Tobě a RDa bych o tom mohl říct víc, ukázat zdrojáky a vysvětlit princip.
Pokud máš rád peníze a nebojíš se OpenCL, dej mi vědět.
Tohle je něco, co se dělá jen (skutečně jen) pro peníze, nic víc za tím není.
Je to jen pro peníze, ale bez vlastní finanční investice (nehrozí ztráta vlastních peněz) si člověk může vydělat tolik, aby za rok už nemusel nikdy pracovat nebo si koupil někde uprostřed města dům a tam si otevřel kavárnu, jen aby byl mezi lidmi.
-
tipuju rychle elektronicke burzovni operace.