4 ms·
Somehow the article fails to mention that the speed will depend heavily on the input string: both its size and distribution of whitespace characters. Even assu
by dzdt 10y ago
Somehow the article fails to mention that the speed will depend heavily on the input string: both its size and distribution of whitespace characters.
Even assuming the question is for the limit of very long strings, the distribution makes a huge difference. Natural English has spaces on average every 5.1 characters [1], so 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!
[1]https://arxiv.org/pdf/1208.6109 https://arxiv.org/pdf/1208.6109
- nkurz 10y agousing 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.
- hyperpape 10y agoQuoting: "It is going to be faster as long as most blocks of eight characters do not contain any white space." Your point is still helpful because it seems that not having whitespace is probably less common, but there is a mention.
- dzdt 10y agoFair enough. I should have said "fails to emphasize" not "fails to mention".
- wmil 10y agoPerhaps he's using it on authors known to be grandiloquent, loquacious, and sesquipedalian.
- dekhn 10y agoyou forgot mellifluous
- DoofusOfDeath 10y agoDon't be fatuous, Dekhn.
- Razengan 10y agoI propose "Iousoquentalian" to describe all such words.
- parasubcutaneor 10y agoA punctilious notion to be sure.
- btilly 10y agoFor natural language, yes. But log files tend to have a very different distribution of whitespace.