News for hackers. Stuff that matters.
Re:How quickly can you remove spaces from a string? by dzdt on Friday January 20, 2017 @04:21PM (#13447071)
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

Re:How quickly can you remove spaces from a string? by nkurz on Friday January 20, 2017 @04:52PM (#13447269)
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?

Re:How quickly can you remove spaces from a string? by rjeli on Friday January 20, 2017 @08:10PM (#13448221)
Could you share your code?
Re:How quickly can you remove spaces from a string? by nkurz on Friday January 20, 2017 @09:58PM (#13448509)
I'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.

Re:How quickly can you remove spaces from a string? by wmil on Friday January 20, 2017 @05:52PM (#13447625)
Perhaps he's using it on authors known to be grandiloquent, loquacious, and sesquipedalian.
Re:How quickly can you remove spaces from a string? by dekhn on Friday January 20, 2017 @06:44PM (#13447869)
you forgot mellifluous
Re:How quickly can you remove spaces from a string? by DoofusOfDeath on Friday January 20, 2017 @08:18PM (#13448249)
Don't be fatuous, Dekhn.
Re:How quickly can you remove spaces from a string? by Razengan on Saturday January 21, 2017 @01:04AM (#13449073)
I propose "Iousoquentalian" to describe all such words.
Re:How quickly can you remove spaces from a string? by parasubcutaneor on Saturday January 21, 2017 @04:38AM (#13449509)
A punctilious notion to be sure.
Re:How quickly can you remove spaces from a string? by hyperpape on Friday January 20, 2017 @04:57PM (#13447295)
Quoting: "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.

Re:How quickly can you remove spaces from a string? by dzdt on Friday January 20, 2017 @06:44PM (#13447871)
Fair enough. I should have said "fails to emphasize" not "fails to mention".
Re:How quickly can you remove spaces from a string? by btilly on Friday January 20, 2017 @06:58PM (#13447942)
For natural language, yes.

But log files tend to have a very different distribution of whitespace.