2 ms·
using multi-character tests to speed up the case of runs of 8 or more characters without a space will probably slow it down, not speed it up! Yes, although the
by nkurz 10y ago
using multi-character tests to speed up the case of runs of 8 or more characters without a space will probably slow it down, not speed it up!
Yes, although there is the option of combining the vectorized comparisons with a branchless approach. I modified his code to do this, and got what seemed to be a flat .40 cycles per character independent of input, which is about twice the speed Daniel illustrated on the input with 3% spaces. I'm sure it can be made even faster (what would the limiting factor be?), but I think this shows that a multi-character approach is faster on all input than would be possible with any single-character approach?
- rjeli 10y agoCould you share your code?
- nkurz 10y agoI'm working with the author, and it should be in his GitHub repository soon. But if you want to reproduce before then, you should be able to just change the line "if (mask16 == 0)" to "if (0)" in sse4_despace(), which is in include/despace.h. The idea is that rather than testing whether any spaces were found and taking a "shortcut", we always do a lookup on mask16, shuffle the bytes according to the result to remove the spaces, and advance the output pointer by 16 minus the number of spaces found. This costs 2-3 cycles for completely spaceless input, but saves the ~15 cycle branch misprediction penalty each time an unexpected space is found.