4 ms·

I'm giving an example (vectorization) where experiments would be needed: "Am I being pedantic? Does the time required to multiply integers on modern machine de

• scott_s 17y ago
  Once we constrain the size of our integers - which most hashtable implementations do implicitly by only using numbers that are natively supported by hardware - number multiplication is once again a constant. From the other direction, if a hashtable implementation uses arbitrarily sized numbers to compute hashes, it probably has bad design.
  • lemire 17y ago
    Please consider vectorization. Natively, modern processors can multiply several 16-bit integers in the time it takes to multiply one pair of 64-bit integers.
    • scott_s 17y ago
      I am considering vectorization. There is always a maximum number of native values that can be operated on at one time by the processor. The maximum cycle costs are also known. Between the two of those, we have a maximum time spent on the computation, and it is a constant. Considering the size of numbers during algorithm analysis matters when the numbers are huge - that is, when the numbers are larger than the maximum values that can be represented natively by the processor. When that happens, "numbers" become a data structure unto themselves and must be analyzed as such.
• jfoutz 17y ago
  You have to admit it's a little silly to start with "This is one of the fundamental reason why pure theory is wasteful." and then not back it up with numbers. I'm a head in the clouds kind of guy, i'd have been fine if you'd said, here's all this extra stuff you might be overlooking. But when you frame the discussion with concrete measurements... I go looking for concrete measurements. That said, I broke the rule on not saying something in writing, that i wouldn't say face to face. (well, i would, but only after i knew you better) I apologize for being snarky. That was uncalled for.
  • 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 ago
      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.