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