3 ms·

Yeah, the data dependencies means this will never be fast. Additionally, "(haystack[4] <= needle) ? 4 : 0" is basically a branch. I mean, a smart compiler coul

• Atrix256 9y ago
  This isn't a parallelized implementation, no. To have that, imagine that instead of a size_t for ret, that it was something like size_t[4], and that each operation you did acted on all 4 items at once (this is how SIMD operations work, they do the same thing to each item in a vector of values). You would end up returning a size_t[4], which would have the results of your 4 searches in it, which ran in parallel. Regarding the ternary operator, you can always check your assembly (here's some that shows it https://godbolt.org/g/BM6tfc https://godbolt.org/g/BM6tfc), but the article also shows how to do it with a multiply instead of the ternary operator. The biggest thing sticking out of this as being slow would be the cache unfriendliness of binary searching, but the link at the end shows how to clear that up (which is not the point of the article, but the ideas are compatible and combinable).
• MereInterest 9y ago
  I think the branching could be avoided by using a cast from boolean to integer, "(haystack[4] <= needle)*4", instead of a ternary operator. It doesn't help at all with the data lookups, though, which is the bigger problem.
  • pacman128 9y ago
    It depends on the optimization level. Using no optimization, gcc 5.4 will use branches for this case, but using -O2, it avoids the branches (on x86_64). Verified by using gcc -S to show the assembly generated.