3 ms·
If I'm doing my mental compilation correctly, these can't actually be parallelized, due to 'ret' being referenced and set by each line. I'm curious if this is a
by falcolas 9y ago
If I'm doing my mental compilation correctly, these can't actually be parallelized, due to 'ret' being referenced and set by each line. I'm curious if this is actually the case, and if an actual parallel implementation is possible (and how fast).
- alexlarsson 9y agoYeah, the data dependencies means this will never be fast. Additionally, "(haystack[4] <= needle) ? 4 : 0" is basically a branch. I mean, a smart compiler could make it a conditional move, but that is in no way guaranteed.
- Atrix256 9y agoThis 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 agoI 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 agoIt 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.
- pranjalv123 9y agoSure, but you could run several searches in parallel on a SIMD architecture with this.
- falcolas 9y agoYou could always run several searches in parallel with normal binary searches as well, since this offers no substantial advantages over a branching method. Unless I'm missing something major?
- mistercow 9y agoHow would you run several searches in parallel on a single core without doing something like this?