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

luvar

  • ***
  • 225
    • Zobrazit profil
    • E-mail
Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #30 kdy: 13. 01. 2020, 06:02:06 »
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)?
« Poslední změna: 13. 01. 2020, 06:04:31 od luvar »


PanVP

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

RDa

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

PanVP

Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #33 kdy: 14. 01. 2020, 01:47:41 »

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

Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #34 kdy: 14. 01. 2020, 10:34:47 »
ř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?
« Poslední změna: 14. 01. 2020, 10:37:38 od registrovany_ava »


PanVP

Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #35 kdy: 14. 01. 2020, 16:24:02 »

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...
« Poslední změna: 14. 01. 2020, 16:27:09 od PanVP »

PanVP

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

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

nula

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

PanVP

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

Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #40 kdy: 14. 01. 2020, 21:47:05 »

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

alex6bbc

  • *****
  • 1 431
    • Zobrazit profil
    • E-mail
Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #41 kdy: 14. 01. 2020, 21:57:13 »

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?

Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #42 kdy: 14. 01. 2020, 22:10:57 »

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.

Logik

  • *****
  • 1 022
    • Zobrazit profil
    • E-mail
Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« Odpověď #43 kdy: 14. 01. 2020, 22:14:39 »
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?

alex6bbc

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