C, zápis do pole čísel a zápis mimo cache L1/L2

PanVP

C, zápis do pole čísel a zápis mimo cache L1/L2
« kdy: 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
« Poslední změna: 12. 01. 2020, 01:04:29 od PanVP »


Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #1 kdy: 12. 01. 2020, 05:33:21 »
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 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, 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. 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.

luvar

  • ***
  • 225
    • Zobrazit profil
    • E-mail
Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #2 kdy: 12. 01. 2020, 08:02:28 »
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):

V každom prípade testovať a testovať...

PS: Zaujímala by ma doména problému, ak to nie je tajné :)

alex6bbc

  • *****
  • 1 432
    • Zobrazit profil
    • E-mail
Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #3 kdy: 12. 01. 2020, 08:25:27 »
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.



_Jenda

  • *****
  • 1 550
    • Zobrazit profil
    • https://jenda.hrach.eu/
    • E-mail
Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #5 kdy: 12. 01. 2020, 09:52:06 »
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ý.

Citace
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.
« Poslední změna: 12. 01. 2020, 09:57:14 od _Jenda »

_Jenda

  • *****
  • 1 550
    • Zobrazit profil
    • https://jenda.hrach.eu/
    • E-mail
Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #6 kdy: 12. 01. 2020, 10:01:17 »
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.

kimec

Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #7 kdy: 12. 01. 2020, 10:19:39 »
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?

PanVP

Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #8 kdy: 12. 01. 2020, 17:32:41 »
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...




PanVP

Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #9 kdy: 12. 01. 2020, 17:43:07 »
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.
« Poslední změna: 12. 01. 2020, 17:48:43 od PanVP »

_Jenda

  • *****
  • 1 550
    • Zobrazit profil
    • https://jenda.hrach.eu/
    • E-mail
Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #10 kdy: 12. 01. 2020, 18:06:54 »
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.

Citace
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…
« Poslední změna: 12. 01. 2020, 18:10:01 od _Jenda »

PanVP

Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #11 kdy: 12. 01. 2020, 20:03:29 »
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  ::)
« Poslední změna: 12. 01. 2020, 20:08:54 od PanVP »

PanVP

Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #12 kdy: 12. 01. 2020, 20:09:27 »
(sorry) duplikát místo editu

luvar

  • ***
  • 225
    • Zobrazit profil
    • E-mail
Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #13 kdy: 12. 01. 2020, 21:06:44 »
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...

PanVP

Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #14 kdy: 12. 01. 2020, 21:25:43 »
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č...
« Poslední změna: 12. 01. 2020, 21:30:03 od PanVP »