4 ms·
Instead of generating shuffle at runtime, couldn't a table be used for shuffling lower and higher parts of the register separately, then merging the result? Al
by lostmsu 8y ago
Instead of generating shuffle at runtime, couldn't a table be used for shuffling lower and higher parts of the register separately, then merging the result?
Also, for uncommon patterns, the register could be split further to make the shuffle table fit into L1.
Also, I am not sure compiler can optimize that continue statement. The non-AVX version might be improved by removing the if alltogether, and replacing dst++ with
dst = followed by dst += (src[i] == ' ' || src[i] == '\r' || src[i] == '\n') ? 0 : 1
- jsd1982 8y agoThe ternary operator a?b:c is still a conditional operation and may result in a branch instruction, same as an if statement. I wouldn't think it would matter much how exactly the branch condition was spelled in C code. It'll get translated to low level IR and optimized at that level.
- kccqzy 8y agoIn this case, the GP is having code of the form a ? 0 : 1 which can usually be rewritten as !a Any worthwhile compiler should compile that into one instruction or two, like `setne` or something else.
- lostmsu 8y agoI was hoping for a direct translation to CMOV. Anyway, the assembly has to be analyzed to be sure.
- Karliss 8y agoNo need to speculate. https://godbolt.org/z/AC2NKY https://godbolt.org/z/AC2NKY . Results significantly vary between compilers. In almost all cases there is at least one jump generated due to the way comparison with 3 values less than 32 is done. If the number is less than or equal to 32 compiler does a lookup in bitmask indicating which values to skip. Often Clang and MSVC generated a second jump.
- lostmsu 8y agoNone of the compilers generated branch-free loop. Looks like or short-circuiting is the reason. Now I wonder if getting rid of branches at assembly level actually gives any benefit. That can be achieved by using | instead of ||.
- kccqzy 8y agoIf I were writing it, I would probably compare the `src[i]` against the three values, setne for each, `and` them together, and add that to the destination pointer.
- caf 8y agoYou could also do the inversion yourself: dst += (src[i] != ' ' && src[i] != '\r' && src[i] != '\n'); (This also misses some other whitespace, like '\t', '\f' and '\v', which if you included might change the balance between the vector and scalar versions).
- vardump 8y ago> The non-AVX version might be improved by removing the if alltogether, and replacing dst++ with dst = followed by dst += (src[i] == ' ' || src[i] == '\r' || src[i] == '\n') ? 0 : 1 Could you give me an example where that would actually generate different code? Every time I've checked, if 'if' form generates a branch, so will the ternary form. Of course, that's also what one would expect, because both forms would generate same or almost same AST.
- lostmsu 8y agoAs I mentioned below, the ifs were due to short-circuiting. Just replace || with |. Actually, I just tried that on MSVC, and to my surprise it became slower a little bit. See remove_scalar_2 here: https://godbolt.org/z/taCqw9 https://godbolt.org/z/taCqw9
- vardump 8y agoYou did manage to remove data dependant branch (which indeed should improve performance), but I guess the dependency chain it created was too long. It might even be a dependency through "dst" value. CPU reorder buffers are nowadays long, ~200 instructions, so not knowing where to write on the next loop iteration might be stall the core. Didn't have time to analyze this very deeply. Then again, not knowing (or more like only conditionally data dependant known, with a dependency to previous iteration) where to write on next round is a pretty fundamental problem when you want to remove chars from string.
- lostmsu 8y agoPerhaps branch prediction works better with jumps than CMOV. Or maybe it has something to do with HT (if it is on).