fwiw, 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: I

fwiw, 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.