| Zobrazit předchozí téma :: Zobrazit následující téma |
| Autor |
Zpráva |
mar
Založen: 16. 06. 2012
Příspěvky: 602
|
 Zaslal: 10. prosinec 2014, 23:44:04 Předmět: MyHash |
 |
|
Trochu jsem vylepšil svoji obecnou hashovací funkci (32-bit).
Oproti MurmurHash3_x86_32 je o ~33% rychlejší,
oproti MurmurHash3_x86_128 je o ~8% rychlejší (ale zase má výstup pouze 32 bitů)
oproti MurmurHash3_x64_128 o ~66% pomalejší.
Pokud by se to někomu hodilo, samozřejmě public domain 
Projde smhasher testy.
| kód: |
#include <stdint.h>
#include <assert.h>
static const uint32_t KEY1 = 0xdb91908du;
static const uint32_t KEY2 = 0x6be5be6fu;
static const uint32_t KEY3 = 0x53a28fc9u;
static const uint32_t KEY4 = 0xf8ffd50bu;
// single instruction on x86/x64
static inline uint32_t Rotate( uint32_t u, uint8_t amount )
{
return (u << amount) | (u >> (uint8_t)(32-amount));
}
static inline uint32_t MyHashWord( uint32_t u, uint32_t h )
{
u = Rotate( u*KEY1, 1 );
return u - Rotate( h ^ KEY2, 11 );
}
uint32_t MyHash( const void *buf, size_t len, uint32_t seed /*= 0*/ )
{
const uint8_t *b = (const uint8_t *)buf;
assert( len < 4 || !((uintptr_t)b & 3) );
const uint32_t *u = (const uint32_t *)b;
size_t ulen = len/4;
uint32_t last = 0;
uint32_t h = KEY3 ^ seed;
h ^= len * KEY4;
b += ulen*4;
len &= 3;
while ( ulen-- ) {
h = MyHashWord( *u++, h );
}
// process remaining data if any (falling through deliberately):
switch( len )
{
case 3:
last = (uint32_t)b[2] << 16;
case 2:
last |= (uint32_t)b[1] << 8;
case 1:
last |= (uint32_t)b[0];
h = MyHashWord( last, h );
}
// finalize (avalanche)
h ^= h >> 7;
h ^= h << 21;
return h;
}
|
Málem bych zapomněl: vyžaduje buffer zarovnaný na 4 byty.
Na big endian systémech bude samozřemě dávat jiné výsledky, ale to nevadí, není to CRC.
C-style casty kvůli tomu, že by to mělo teoreticky fungovat i v C. |
|
| Návrat nahoru |
|
 |
quas4
Založen: 18. 10. 2007
Příspěvky: 199
|
| Zaslal: 11. prosinec 2014, 16:19:00 Předmět: |
|
|
pro hash(void*) -- pointer hash pouzivam toto:
| kód: |
inline uint32_t pointer_hash(const void* Key, uint32_t C = 0)
{
#define mix(a,b,c) \
{ \
a -= b; a -= c; a ^= (c>>13); \
b -= c; b -= a; b ^= (a<<8); \
c -= a; c -= b; c ^= (b>>13); \
a -= b; a -= c; a ^= (c>>12); \
b -= c; b -= a; b ^= (a<<16); \
c -= a; c -= b; c ^= (b>>5); \
a -= b; a -= c; a ^= (c>>3); \
b -= c; b -= a; b ^= (a<<10); \
c -= a; c -= b; c ^= (b>>15); \
}
uint32_t A;
uint32_t B;
A = B = 0x9e3779b9;
// Avoid LHS stalls on PS3 and Xbox 360
#if __LP64__ // PLATFORM_64BITS on IOS
// Ignoring the lower 4 bits since they are likely zero anyway.
// Higher bits are more significant in 64 bit builds.
A += (reinterpret_cast<uintptr_t>(Key) >> 4);
#else
A += reinterpret_cast<uintptr_t>(Key);
#endif
mix(A, B, C);
return C;
#undef mix
}
|
uz si nepamatuju odkud jsem ji vykradl. Specialne jen pro pointery muze mit lepsi charakteristiky - dusledne jsem ale nezkoumal protoze samotna funkce je pro me ucely rychla dost a kolizi je minimum. |
|
| Návrat nahoru |
|
|
mar
Založen: 16. 06. 2012
Příspěvky: 602
|
| Zaslal: 11. prosinec 2014, 19:15:05 Předmět: |
|
|
Naprosto souhlasím, že pro elementární typy je použití obecné hashovací funkce overkill, v některých případech bych klidně použil i přímo hodnotu.
Co se koukám u tebe na ten mix, tak je tam krásně vidět, proč je to rychlé - minimalizuje pipeline dependency
(což je třeba důvod, proč je crc-32 standardně pomalé, i když existuje způsob (slicing) pomocí 4 nebo 8mi tabulek (to vymysleli kluci z Intelu),
který má za následek 2x+ zrychlení, viz http://create.stephan-brumme.com/crc32/.
Docela mě překvapuje, že toto nemají třeba v zlibu, protože z benchmarků co jsem dělal na své implementaci gzipu při dekompresi
se standardním crc-32 s jednou tabulkou jenom výpočet crc zabíral skoro třetinu času (!),
takže pokud někdo používá zip+zlib jako vfs, doporučil bych crc vypnout)
Co jsem postnul já je dobré třeba pro stringy nebo složité klíče,
testoval jsem to na wordlistu 1.6M slov a dobré hashovací funkce měly ~350 kolizních 32-bitových hashů. Třeba SuperFastHash měl 8k kolizí, což mě překvapilo.
Adler32 byl nejrychlejší, ale zároveň měl taky nejhorší rozložení (1.3M kolizních hashů - jenom doufám, že nemám bug v implementaci
Trochu mě taky zklamal optimizer clangu, který z nějakého důvodu první rotaci neudělá pomocí rol (na x86), ale provádí mul KEY1*2/shift/or. Druhou dá přitom v pohodě...
Co jsem koukal, tak ARM umí pouze ROR, ale překladač by to mohl jednoduše zvládnout přetransformovat (což je dobré, protože jsem původně myslel, že instrukci pro rotace nemá).
Možná tu rotaci ještě předělám, aby byla doprava, ale nemyslím, že to bude mít na něco vliv. |
|
| Návrat nahoru |
|
|
]semo[
Založen: 29. 07. 2007
Příspěvky: 1525
Bydliště: Telč
|
| Zaslal: 12. prosinec 2014, 08:53:44 Předmět: |
|
|
Sice moc lidí neodpovídá, ale je dobře, že to sem dáváš. Je to zajímavé čtení.
Osobně jsem rezignoval na takové ty optimalizace typu: "tohle se přeloží pro toto CPU s tímto překladačem na 2 instrukce, na jiným na 5". Ani to neumím, ale možná je to tak lepší, ještě bych to všude řešil ;-).
Tyhle hashovací a random funkce děláš ze záliby, nebo s nějakým větším využitím?
_________________
Kdo jede na tygru, nesmí sesednout.
---
http://www.inventurakrajiny.cz/sipka/
Aquadelic GT, Mafia II, simulátory |
|
| Návrat nahoru |
|
|
mar
Založen: 16. 06. 2012
Příspěvky: 602
|
| Zaslal: 12. prosinec 2014, 12:30:49 Předmět: |
|
|
Spíš je to asi taková moje úchylka
Reálně ten rozdíl u těchto mikrooptimalizací bývá minimální, ale záleží na konkrétním případu.
U toho random generátoru primární motivace byla, že pre-C++11 std knihovny měly mizerné PRNG (co do náhodnosti),
většinou to byl nějaký LCG a taky že mi to běží všude stejně.
Mersenne Twister mi zase přijde jako overkill a je relativně pomalý (což je samozřejmě úplně jedno, pokud potřebuješ jenom pár čísel na frame).
Inner loopy v MMX assembleru už taky dávno nepíšu, vždycky se víc vyplatí high level optimalizace (pokud je možná), případně parelelizace.
Na druhou stranu si myslím, že není špatné mít aspoň nějaký přehled o tom,
co můžeš čekat na té nebo oné platformě.
Třeba moc lidí neví, že ARMy (aspoň donedávna) neměly instrukci pro celočíselné dělení.
Kdysi jsme dělali kdysi v práci nějaké věci pro PDA (WinCE + ARM) a pak jsme se moc divili, když jsme zjistili, že to nemělo koprocesor
Takže se pak masivně přepisovalo do fixed pointu.
Naštěstí v dnešní době toto na mobilech/tabletech už není problém.
Tak jsem rád, že ti to přijde aspoň trochu zajímavé |
|
| Návrat nahoru |
|
|
rezna
Založen: 27. 07. 2007
Příspěvky: 2156
|
| Zaslal: 12. prosinec 2014, 13:33:54 Předmět: |
|
|
| mar napsal: |
| Inner loopy v MMX assembleru už taky dávno nepíšu, vždycky se víc vyplatí high level optimalizace (pokud je možná), případně parelelizace. |
tohle sdeleni nekde vytesat do kamene. to je hlavni princip vyvoje, optimalizovat high-level. ne si nalozit na zada nesmyslny algoritmus nebo zbytecne hromady dat a snazit se mikrooptimalizovat.
jsou mista kde uz to samozrejme nejde, pak nastupuji mikrooptimalizace. ale vzdy je nutne se prvne zamyslet nad tim jak omezit vstup nebo teoreticky zrychlit vypocet nez zkouset sachovat s registry. |
|
| Návrat nahoru |
|
|
VODA
Založen: 29. 07. 2007
Příspěvky: 1721
Bydliště: Plzeň
|
| Zaslal: 12. prosinec 2014, 14:18:50 Předmět: |
|
|
| mar napsal: |
| Tak jsem rád, že ti to přijde aspoň trochu zajímavé |
Mně to také přijde velice zajímavé. Dokonce Tvůj kód na PRNG jsem použil v jedné své semestrálce a s Tvým dovolením bych si ho rád zabudoval do enginu (pochopitelně, že mám v plánu zmínit v enginu Tvé jméno, alespoň v komentáři, pokud Ti to bude stačit).
Rozhodně budu rád, když vyprodukuješ ještě něco podobného, protože mě tím vždy strašně inspiruješ a já mám hned chuť si rozšiřovat obzory.
_________________
Opravdovost se pojí s trýzní... |
|
| Návrat nahoru |
|
|
mar
Založen: 16. 06. 2012
Příspěvky: 602
|
| Zaslal: 12. prosinec 2014, 15:34:53 Předmět: |
|
|
rezna: určitě, pokud mám n^2 a můžu to mít třeba n*log n (pro velké n), pak mi nepomůže ani C++ ani assembler ani živá voda (s malým
VODA: to jsem moc rád, že se ti to hodí, na jméno se vykašli, já jsem se vlastně taky inspiroval u Boba Jenkinse (je to ten druhý, ne ten komentátor).
Nakonec je to jenom pár elementárních operací, které dohromady dobře fungují. |
|
| Návrat nahoru |
|
|
mar
Založen: 16. 06. 2012
Příspěvky: 602
|
| Zaslal: 24. září 2015, 18:23:35 Předmět: Re: MyHash |
|
|
Tak jsem po čase zjistil, že moje hashovací fce má trochu problémy s hashováním sparse bitsetů, opravená verze (bohužel pomalejší), přesto (s msc) pořád o 8% rychlejší, než 32-bit Murmur3:
| kód: |
static inline uint32_t MyHashWord( uint32_t u, uint32_t h )
{
u = Rotate( u*KEY1, 31 );
return u + Rotate( h*3 + KEY2, 11 );
}
|
Docela mě překvapuje, že jenom clang dokáže udělat h*3+KEY2 v jedné instrukci pomocí lea, ale zase neumí foldnout jednu z rotací...
Je tedy škoda, že clang nemá builtiny pro rotace, o to víc, že ARM má ror instrukci. |
|
| Návrat nahoru |
|
|
|
Hlavní strana
FAQ
Test
Hledat
Seznam uživatelů
Uživatelské skupiny
Registrace
Ke Stažení
Nastavení
Přihlášení
Calendar
