.[ ČeskéHry.cz ].
MyHash

 
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> Obecné
Zobrazit předchozí téma :: Zobrazit následující téma  
Autor Zpráva
mar



Založen: 16. 06. 2012
Příspěvky: 550

PříspěvekZaslal: 10. prosinec 2014, 23:44:04    Předmět: MyHash Odpovědět s citátem

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 Smile
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
Zobrazit informace o autorovi Odeslat soukromou zprávu
quas4



Založen: 18. 10. 2007
Příspěvky: 199

PříspěvekZaslal: 11. prosinec 2014, 16:19:00    Předmět: Odpovědět s citátem

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
Zobrazit informace o autorovi Odeslat soukromou zprávu
mar



Založen: 16. 06. 2012
Příspěvky: 550

PříspěvekZaslal: 11. prosinec 2014, 19:15:05    Předmět: Odpovědět s citátem

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 Smile
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
Zobrazit informace o autorovi Odeslat soukromou zprávu
]semo[



Založen: 29. 07. 2007
Příspěvky: 1482
Bydliště: Telč

PříspěvekZaslal: 12. prosinec 2014, 08:53:44    Předmět: Odpovědět s citátem

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
Zobrazit informace o autorovi Odeslat soukromou zprávu
mar



Založen: 16. 06. 2012
Příspěvky: 550

PříspěvekZaslal: 12. prosinec 2014, 12:30:49    Předmět: Odpovědět s citátem

Spíš je to asi taková moje úchylka Smile
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 Smile
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é Smile
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
rezna



Založen: 27. 07. 2007
Příspěvky: 2155

PříspěvekZaslal: 12. prosinec 2014, 13:33:54    Předmět: Odpovědět s citátem

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
Zobrazit informace o autorovi Odeslat soukromou zprávu
VODA



Založen: 29. 07. 2007
Příspěvky: 1695
Bydliště: Plzeň

PříspěvekZaslal: 12. prosinec 2014, 14:18:50    Předmět: Odpovědět s citátem

mar napsal:
Tak jsem rád, že ti to přijde aspoň trochu zajímavé Smile

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. Smile
_________________
Opravdovost se pojí s trýzní...
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
mar



Založen: 16. 06. 2012
Příspěvky: 550

PříspěvekZaslal: 12. prosinec 2014, 15:34:53    Předmět: Odpovědět s citátem

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ýmSmile
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
Zobrazit informace o autorovi Odeslat soukromou zprávu
mar



Založen: 16. 06. 2012
Příspěvky: 550

PříspěvekZaslal: 24. září 2015, 18:23:35    Předmět: Re: MyHash Odpovědět s citátem

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
Zobrazit informace o autorovi Odeslat soukromou zprávu
Zobrazit příspěvky z předchozích:   
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> Obecné Časy uváděny v GMT + 1 hodina
Strana 1 z 1

 
Přejdi na:  
Nemůžete odesílat nové téma do tohoto fóra
Nemůžete odpovídat na témata v tomto fóru
Nemůžete upravovat své příspěvky v tomto fóru
Nemůžete mazat své příspěvky v tomto fóru
Nemůžete hlasovat v tomto fóru


Powered by phpBB © 2001, 2005 phpBB Group


Vzhled udelal powermac
Styl "vykraden" z phpBB stylu MonkiDream - upraveno by rezna