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

[registrovany_ava]

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

[Reklama]

[registrovany_ava]

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]

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ů :-)

[PanVP]

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

[RDa]

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:

Kód: [Vybrat]

# 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:

Kód: [Vybrat]

#  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 :-)

[Reklama]

[_Jenda]

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

[kvr kvr]

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.

[PanVP]

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:


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

[PanVP]

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://imgur.com/iP27yPa

Doplněno: Ať jsou výsledky se zátěží vedle sebe:

https://imgur.com/T9ipzsg

[registrovany_ava]

..

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

[tralala5]

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

[PanVP]

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

[registrovany_ava]

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://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é.

[PanVP]

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



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

[PanVP]

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