3 ms·
Implementing vectorized hash tables is no joke, so I don't think it is silly to have merely evoked the possibility rather than implementing it. It would have ta
by lemire 17y ago
Implementing vectorized hash tables is no joke, so I don't think it is silly to have merely evoked the possibility rather than implementing it. It would have taken me days of work, possibly, and even then, people could have questioned my code. I do have a day job, doing academic research and teaching Computer Science. Maybe one day I will research vectorized hash tables, but the result will not be a mere blog post.
- jfoutz 17y agofwiw, gcc-4.2 foo.c; time ./a.out; gcc-4.2 -ftree-vectorize -ffast-math -ftree-vectorizer-verbose=3 -funsafe-math-optimizations -O3 foo.c; time ./a.out foo.c: In function ‘main’: foo.c:16: warning: incompatible implicit declaration of built-in function ‘printf’ 0 real 0m0.095s user 0m0.093s sys 0m0.002s foo.c: In function ‘main’: foo.c:16: warning: incompatible implicit declaration of built-in function ‘printf’ foo.c:6: note: not vectorized: unsupported use in stmt. foo.c:11: note: LOOP VECTORIZED. foo.c:2: note: vectorized 1 loops in function. 0 real 0m0.018s user 0m0.017s sys 0m0.001s int main () { int a[256], b[256], c[256]; int count = 100000; int i; for(i=0; i < 256; i++) { a[i] = i; b[i] = 255 - i; } do{ for(i=0; i < 256; i++) { c[i] = a[i] * b[i]; } } while(count--); printf("%i", c[0]);// avoid c being optimized away. } so, i'd assert that vectorized multiplication is a speed win rather than a loss. upping the count a few orders of magnitude indicates vectorized multiplication grows slower than regular multiplication. So, I claim the vectorization of multiplication is probably not detrimental to the Big O of a hashtable. ymmv.