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

[linuxak]

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ší.

[Reklama]

[Jan Remeš]

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.

[PanVP]

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.

[linuxak]

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í.

[RDa]

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.

[Reklama]

[milanroubal]

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.

[linuxak]

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.

[RDa]

A jeste mi chybi pocet matchu se slovnikem, ze vstupniho streamu. Jestli je to 1 z 1000, tak to snese hodne dlouhou latenci.

[PanVP]

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...

[alex6bbc]

to budou takove ty super-rychle obchodovaci operace na ruznych internetovych burzach ne???

[luvar]

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).

[PanVP]

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... 

[PanVP]

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 

[linuxak]

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, 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.

[PanVP]

Jo takhle...nezní to špatně!