Posto je vrlo brz, okacio sam kod pseudorandom number generatora ovde:
http://www.dimkovic.com/node/22
Kod koristi SSE4 (kad moze) i brzi je nekih ~27 puta od MSVC rand() implementacije. I ne samo sto je brzi, vec je i daleko kvalitetniji po pitanju "slucajnosti" izlaza. U pitanju je MWC1616 algoritam (MWC = Multiply-with-carry) ciji je autor George Marsaglia. Period ovog algoritma je veci od 10^18, i kao takav je drasticno bolja alternativa od rand() implementacije u MSVC-u - kako po statistici tako i po brzini.
Na test masini, koristeci jedno jezgro moja SSE4 implementacija moze da generise oko
2 milijarde slucajnih brojeva u sekundi. Microsoftov rand() za istu kolicinu brojeva radi 27 sekundi. To prakticno znaci da za generisanje jednog pseudo-slucajnog broja moja MWC1616 implementacija trosi oko 1.5 ciklus ili ~0.5 ns.
Uskoro (sledece godine :-) ce biti moguce udvostruciti performanse uz pomoc AVX2 instrukcijskog seta koji ce biti lansiran sa Haswell arhitekturom. Doduse, vec Ivy Bridge ima hardverski generator slucajnih brojeva koji su FIPS-140 kompatibilni, ali je u stanju da ispuca manje brojeva za isto vreme (oko 2-3 Gbps).
Kod mozete skinuti
odavde, kod je licenciran pod BSD licencom, tako da ga mozete koristiti u vasim projektima.
Implementacija je neverovatno jednostavna - evo SSE4 snippeta, koji koristi SSE intrinsics f-je, pa bi trebao da radi na svakom postenom kompajleru:
Code:
//////////////////////////////////////
// MWC1616 --> SSE4 version //
// Copyright (C) 2012 Ivan Dimkovic //
// Licensed under BSD license //
//////////////////////////////////////
static inline void FastRand_SSE4(fastrand *f)
{
__m128i a = _mm_load_si128((const __m128i *)f->a);
__m128i b = _mm_load_si128((const __m128i *)f->b);
const __m128i mask = _mm_load_si128((const __m128i *)f->mask);
const __m128i m1 = _mm_load_si128((const __m128i *)f->m1);
const __m128i m2 = _mm_load_si128((const __m128i *)f->m2);
__m128i amask = _mm_and_si128(a, mask);
__m128i ashift = _mm_srli_epi32(a, 0x10);
__m128i amul = _mm_mullo_epi32(amask, m1);
__m128i anew = _mm_add_epi32(amul, ashift);
_mm_store_si128((__m128i *)f->a, anew);
__m128i bmask = _mm_and_si128(b, mask);
__m128i bshift = _mm_srli_epi32(b, 0x10);
__m128i bmul = _mm_mullo_epi32(bmask, m2);
__m128i bnew = _mm_add_epi32(bmul, bshift);
_mm_store_si128((__m128i *)f->b, bnew);
__m128i bmasknew = _mm_and_si128(bnew, mask);
__m128i ashiftnew = _mm_slli_epi32(anew, 0x10);
__m128i res = _mm_add_epi32(ashiftnew, bmasknew);
_mm_store_si128((__m128i *)f->res, res);
}
SSE4 verzija koristi
pmullud instrukciju koja omogucava da se u jednom prolazu pomnoze 2 vektora sa 4 32-bitna integera. Za CPU-ove bez SSE4 to mnozenje se mora razbiti na 2 dela - visi i nizi 16-bitni, i 32-bitni rezultat se na kraju dobija shift-ovanjem i OR-ovanjem medju-rezultata, sto zahteva nesto vise instrukcija od SSE4 verzije.
[Ovu poruku je menjao Ivan Dimkovic dana 04.06.2012. u 01:25 GMT+1]
DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.digicortex.net/node/1 Videos:
http://www.digicortex.net/node/17 Gallery:
http://www.digicortex.net/node/25
PowerMonkey - Redyce CPU Power Waste and gain performance! -
https://github.com/psyq321/PowerMonkey