How quickly can you remove spaces from a string?
lemire.me
lemire.me
I committed my syntax highlighting code, and a few days later someone had replaced the simple UTF8 strlen function with the really long vectorised version from this page: http://www.daemonology.net/blog/2008-06-05-faster-utf8-strle...
But the funny thing is, that the supposedly fast vectorised strlen was optimised for very long strings. The benchmarks shows results for megabytes of texts. But we measured the length of tokens, usually only a few characters long, so in most cases the new function was actually slower!
I was a very junior dev, didn't want to piss off anybody, and the strlen wasn't in the hot path anyway, so I didn't say anything. But I was a bit sad, that my easy-to-read code was replaced by such a monstrosity.
What's my point? Before you go and use these functions in your code, profile your code to see if it would actually affect performance.
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!
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?
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.
Your point is still helpful because it seems that not having whitespace is probably less common, but there is a mention.
But log files tend to have a very different distribution of whitespace.
You might not notice this if you use a password manager or browser autofill, but it's a lot of sites, including companies like major airlines for example.
Never mind that -- it's just a miracle when you can enter a credit card number formatted as 4123 4567 8901 2345 rather than squished together.
The very premise of the article 'how quickly can we remove whitespaces' is rooted in the intellectual foundations of CS. As a culture, we are are obsessive about 'performance'.
This is because back in the day, it's always been important - and even today 'under the hood' it's always important. And of course there are situations in which it's still important (complex algs, limitations of mobile devices).
But in reality - these things are never the issue.
The 'issue' is the pragmatic application of basic algorithms to do a number of basic things elegantly, which together form the foundation of a good user experience.
Yes - the issue of 'no spaces' in card numbers etc. is a clumsy thing, and it's laziness by developers.
Also - things like 'performance' are objectively measurable, you can get cool data for it etc..
A 'bad experience' is sometimes difficult to define.
My purely anecdotal impression is quite the opposite. Speed of delivery and convenience for the developer (not the end user) seem to be the norm.
Frameworks, scripting languages, browser-based desktop and web apps: none of these have the characteristics of being small, nimble, lightweight, or performant. They certainly make life easier for the developer. Whether users get a 'good experience' out of the end result is open to debate.
I worked at a small technical training company in early 2001. We had an in house application which was used for scheduling classes. If you entered a trailing space the program would beep 3 times and display a dialog box warning you in capital letters that trailing spaces would corrupt the database. The button to close the dialog box was labeled "I understand and will obey". It probably took the developer more time to create the dialog box than to sanitize all inputs.
Note that the first set of code (and possibly the rest), only work as the space, newline, and carriage return are the 7 bit ASCII set is included in UTF-8. However, the extended 8-bit ASCII set is not, but is often included when people speak of ASCII. So for example, if the request was to remove all "Copyright Sign" symbols, which is U00A9, it would not work correctly. The UTF-8 encoding for this symbol is 0xC2 0xA9, but the code only works on individual bytes, so it would remove the A9 byte, leaving a C2 byte and then whatever byte came next. Additionally, it would hit other UTF-8 characters like the "Greek Capital Letter Omega" (Ω which is encoded in UTF-8 as 0xCE 0xA9)
tl;dr Only works for the 7-bit ASCII set, but not the common extended 8-bit ASCII sets
Basically the blog post was correct and precise: it removes ASCII characters from UTF-8. There is no elaboration needed.
Again, though, the post was about using SIMD primitives to optimize what looks like a scalar problem.
Having said that, I clearly remember arguing with people that encodings with the eighth bit set were not part of ASCII. As you say, there were many people who didn't understand. My guess is that the GP never interacted with those people. Especially if you were around pre-DOS I think it would be easy to do.
https://en.wikipedia.org/wiki/Extended_ASCII
If you used Macs in the 80s and 90s and shared files with PC users, you heard about it all the time, because high-ascii characters would map incorrectly across the platforms.
https://en.wikipedia.org/wiki/Latin-1_Supplement_(Unicode_bl...
There's nothing region specific there.
Also ISO-8859-1 is Latin-1:
> ISO 8859-1 encodes what it refers to as "Latin alphabet no. 1," consisting of 191 characters from the Latin script.
Now there are a few code points in ISO 8859-1 that are undefined, whereas they are defined in Unicode Latin-1, and Windows-1252, but they're mostly the same. The major difference is € and the TM symbol.
Exactly as it sounds. The characters encoded in Latin-1 are specific for Western Europe and thus may not appear in other ISO-8859 character sets.
> I don't think that is right. Here is the list of Latin-1 characters (as part of Unicode)...There's nothing region specific there.
Unicode is a different set of character sets (note: Unicode isn't even 1 specific character set!) yet again. Latin-1 is not unicode. In fact the point of Unicode was to address the problems that arose with region specific character sets like Latin-1. Hence why there's Latin-1 characters included in Unicode as well as characters from of locales. What you're referencing is the Latin-1 block within the UTF-8 character set.
> Also ISO-8859-1 is Latin-1
It is. But I was referencing ISO-8859 (without the -1) which covers Latin-1 as well as a bunch of other locales.
> Now there are a few code points in ISO 8859-1 that are undefined, whereas they are defined in Unicode Latin-1, and Windows-1252, but they're mostly the same. The major difference is € and the TM symbol.
You're drifting all over the place there:
1. there's no such thing as "Unicode Latin-1". They're different character sets albeit Unicode will have a Latin-1 block (much like Latin-1 has an ASCII block).
2. With regards to your point about the € and TM differences: that is precisely the reason I suggested using ISO-8859 (without the -1) as a reference rather than a region specific character set.
https://raw.githubusercontent.com/lemire/despacer/master/inc...
But no application will ever be doing only string despacing or Morton codes, so the "fast" lookup table algorithm will make everything else slower by evicting good cache lines. And once something else runs and evicts the lookup tables, the next run will be slow again.
@tailrec private def ws(): Unit =
// fast test whether cursorChar is one of " \n\r\t"
if (((1L << cursorChar) & ((cursorChar - 64) >> 31) & 0x100002600L) != 0L) { advance(); ws() }
To me, this looks like a perfect example of a developer thinking they're very smart while they're actually writing code that's worse that its naive counterpart version (a good summary of Scala in my experience).
The average (english) word is ~5 characters long, so most of the time, you'd be forced to check anyway.
Maybe do it log> 1) check if you can jump 16, 2) check if you can jump 8, 3) check if you can jump 4, execute
The scalar operations of reading a character, checking whether it's a space (0x20), and writing it to an output can often be done in a single cycle (the processor is 'superscalar'). A mispredicted branch costs about 15 cycles. Thus for simple tasks like this, if the average distance between spaces is 16 or less, you are likely better off with the simpler straightforward approach.
That said, while it may not be a solution for every case, it's a solution for the common case and a starting point for other cases, and thus pretty nifty and potentially useful.
Time to insert this into some of my friends code.
You can also use a character and combining character to make a symbol that looks exactly like a semicolon, but technically isn't. Browsers treat it as a semicolon anyways. I wanted to be able to do `var ; = "foobar";`
Maybe it will sneak by other languages that allow unicode in the code? Though I don't know of many.
It generated a friggin' binary search tree! Some of the leaves were a sequence of straight-line comparisons, because that's more compact, but the higher levels were all a bunch of "if (c > 0x167F) { ... }" sort of code. At one point it subtracts 8192 from something and then compares with 12, and I think this is because the x86 instruction encoding is shorter and the compiler knows that the register won't be needed again along either of the code paths from that point.
Compilers are amazing sometimes.
Subtraction and addition implicitly sets the flags, so you can generate very small code with inc/dec (1-byte instructions), like this:
dec ax
jz ax_was_zero
dec ax
jz ax_was_one
...It won't find all characters in a single scan. But maybe do 3 passes over a buffer which fits in cache.
awk '
{
gsub(/[[:blank:]\015]/, "");
printf("%s", $0);
}' input | tee output
Looking at the benchmark code, this is using rdtsc to read the CPU time stamp counter. That does not take waiting for memory into account, does it?
I wonder if there's a difference when measured in wall clock time. It's still somewhat beneficial to have the CPU work efficiently to give an opportunity for hyperthreading to take place when waiting for memory.
If you really wanted to make something like this faster, you should focus on cache utilization and make use of prefetching instructions. x86 has pretty bad prefetching instructions and pretty good speculative fetching, so don't expect massive speedups but on ARM or Aarch64, you have a finer grained control over cache prefetching (L1 and L2 separately) and you could see much bigger differences.
As for benchmarking this kind of problems: you obviously want to measure real world performance, so you need wall clock time as well as time stamp counter, but I'd look for optimization clues in "perf stat" and other CPU perf counters, with an emphasis on cache misses and branch mispredictions.
The figure you should be staring at is the total throughput of the algorithm, measured in gigabytes per second. You should be getting figures close to the memory bandwidth available (25-50 GB/s depending on CPU and memory).
edit: I measured the wall clock time with clock_gettime before/after all the repeats (using a megabyte sized buffer) and there is indeed no significant difference, here's my results:
memcpy(tmpbuffer,buffer,N): 0.122945 cycles / ops 1495907352 nsec (1.495907 sec)
countspaces(buffer, N): 3.657322 cycles / ops 1544915395 nsec (1.544915 sec)
despace(buffer, N): 6.521193 cycles / ops 1621204460 nsec (1.621204 sec)
faster_despace(buffer, N): 1.721657 cycles / ops 1500507217 nsec (1.500507 sec)
despace64(buffer, N): 3.595031 cycles / ops 1544993649 nsec (1.544994 sec)
despace_to(buffer, N, tmpbuffer): 6.307885 cycles / ops 1615101563 nsec (1.615102 sec)
avx2_countspaces(buffer, N): 0.190992 cycles / ops 1460961459 nsec (1.460961 sec)
avx2_despace(buffer, N): 5.750583 cycles / ops 1615971010 nsec (1.615971 sec)
sse4_despace(buffer, N): 0.985002 cycles / ops 1482901389 nsec (1.482901 sec)
sse4_despace_branchless(buffer, N): 0.338737 cycles / ops 1460874704 nsec (1.460875 sec)
sse4_despace_trail(buffer, N): 1.950657 cycles / ops 1502268447 nsec (1.502268 sec)
sse42_despace_branchless(buffer, N): 0.562246 cycles / ops 1468638389 nsec (1.468638 sec)
sse42_despace_branchless_lookup(buffer, N): 0.624913 cycles / ops 1472445127 nsec (1.472445 sec)
sse42_despace_to(buffer, N,tmpbuffer): 1.747046 cycles / ops 1507705780 nsec (1.507706 sec)
edit2: surprisingly, Clang is about 10% slower than GCC in my experiments.
Looking at the benchmark code, this is using rdtsc to read the CPU time stamp counter. That does not take waiting for memory into account, does it?
On modern Intel processors, the "time stamp counter" is monotonically increasing at a constant rate, so it does take memory latency into account. On many Linux systems (including the one used here) clock_gettime() uses the same underlying clock source, so there should be no difference in accuracy for long measurements. The CPUID-RDTSC/RDSTCP-CPUID pattern used here has the advantage of a somewhat lower and significantly more predictable overhead, which helps when measuring shorter events.
I'd expect something trivial like this to be completely memory bound with the CPU sitting almost idle waiting for bytes coming in from memory.
If I remember the numbers right, the Skylake processor this is running on can read about 64B per cycle if the source is L1, about 24B per cycle if the source is L3, and about 6B per cycle from main memory. Using the existing RDTSC framework, I get equal speeds at L3 size, and still get sub .4B/cycle coming from main memory.
I measured the wall clock time with clock_gettime before/after all the repeats (using a megabyte sized buffer) and there is indeed no significant difference
I agree that testing on larger buffers would be informative (as would testing different ratios of whitespace) but I don't think your approach is capturing what you think it is. The macro being used for time measurement uses a different random input for each iteration (look at 'pre'), and the unoptimized time of initializing this dominates the clock time. So while I think your test is worthwhile, I think you need a better way to perform the measurement. I think you'll see that RDTSC maps exactly to wall time in this case, but surprises are definitely possible.
I'd look for optimization clues in "perf stat" and other CPU perf counters, with an emphasis on cache misses and branch mispredictions.
Yes, although as with wall time, one needs to be sure to measure only on the section of code that one is optimizing. Perf makes this difficult, so something like "likwid" with an API that allows profiling fragments of code would be required. I haven't done that yet for this, but at the faster speeds (sse4_despace_branchless) I don't think there are any cache misses or branch mispredictions in the code of interest.
surprisingly, Clang is about 10% slower than GCC in my experiments
My surprise was the opposite. Clang was 25% faster than GCC and ICC on the L1- and L3-sized vectorized branchless (.25 cycles/byte versus .33 cycles/byte, although the code I'm running is not quite what's on Github). Most of this benefit seems to be because clang unrolls 2x to reduce loop overhead.
And how sloppy of me! I didn't notice the `pre;` in the code consuming most of the time (to be fair it's just 4 characters and I didn't put too much time to it). When I move that outside of the loop, before the timer, I get results that show improvement with the optimized version.
And indeed it looks like rdtsc is giving similar figures to clock_gettime now. I falsely presumed that it counts retired instructions.
I'm still surprised to see a speedup, and how badly the original version is performing.
My guess is that the conditional stores are poison to the CPU pipelines. The 64 bit version gets most of the performance out of it already, I presume it's because of the more efficient memory usage pattern.
I can't edit my earlier post any more, I'd correct it if I could.
Clang:
memcpy(tmpbuffer,buffer,N): 0.000000 cycles / ops 65232 nsec (0.000065 sec)
countspaces(buffer, N): 0.000000 cycles / ops 65176 nsec (0.000065 sec)
despace(buffer, N): 4.547286 cycles / ops 7654310198 nsec (7.654310 sec)
faster_despace(buffer, N): 1.582721 cycles / ops 2651677500 nsec (2.651678 sec)
despace64(buffer, N): 0.583952 cycles / ops 1025215835 nsec (1.025216 sec)
despace_to(buffer, N, tmpbuffer): 0.000000 cycles / ops 63847 nsec (0.000064 sec)
avx2_countspaces(buffer, N): 0.000000 cycles / ops 63697 nsec (0.000064 sec)
avx2_despace(buffer, N): 0.307253 cycles / ops 602528061 nsec (0.602528 sec)
sse4_despace(buffer, N): 0.310504 cycles / ops 534542967 nsec (0.534543 sec)
sse4_despace_branchless(buffer, N): 0.353851 cycles / ops 594652080 nsec (0.594652 sec)
sse4_despace_trail(buffer, N): 0.314221 cycles / ops 562439990 nsec (0.562440 sec)
sse42_despace_branchless(buffer, N): 0.608811 cycles / ops 1020576734 nsec (1.020577 sec)
sse42_despace_branchless_lookup(buffer, N): 0.608494 cycles / ops 1020062750 nsec (1.020063 sec)
sse42_despace_to(buffer, N,tmpbuffer): 1.779908 cycles / ops 2983955982 nsec (2.983956 sec)
memcpy(tmpbuffer,buffer,N): 0.285702 cycles / ops 489599835 nsec (0.489600 sec)
countspaces(buffer, N): 0.000000 cycles / ops 63995 nsec (0.000064 sec)
despace(buffer, N): 4.751018 cycles / ops 8014809122 nsec (8.014809 sec)
faster_despace(buffer, N): 1.718575 cycles / ops 2898082416 nsec (2.898082 sec)
despace64(buffer, N): 0.883421 cycles / ops 1560479651 nsec (1.560480 sec)
despace_to(buffer, N, tmpbuffer): 6.424313 cycles / ops 10892716258 nsec (10.892716 sec)
avx2_countspaces(buffer, N): 0.031227 cycles / ops 52369789 nsec (0.052370 sec)
avx2_despace(buffer, N): 0.315633 cycles / ops 627793484 nsec (0.627793 sec)
sse4_despace(buffer, N): 0.319739 cycles / ops 554173689 nsec (0.554174 sec)
sse4_despace_branchless(buffer, N): 0.366240 cycles / ops 615638316 nsec (0.615638 sec)
sse4_despace_trail(buffer, N): 0.318973 cycles / ops 572262343 nsec (0.572262 sec)
sse42_despace_branchless(buffer, N): 0.638114 cycles / ops 1070772787 nsec (1.070773 sec)
sse42_despace_branchless_lookup(buffer, N): 0.637988 cycles / ops 1069642163 nsec (1.069642 sec)
sse42_despace_to(buffer, N,tmpbuffer): 1.768081 cycles / ops 2963488990 nsec (2.963489 sec)This isn't a compiler bug or a shortcoming, it's a non-trivial optimization. Especially given the aliasing between the input and output (ie. it's an in-place algorithm) this is going to be a very difficult optimization.
0.25 cycles/byte using GTX 1080.
https://github.com/lemire/despacer/blob/master/Makefile
CFLAGS = -fPIC -std=c99 -O3 -march=native
UNICODE or GTFO.
Should be embarassingly parallel for a contiguous array.
(I may or may not have forgotten the differences between concurrency and parallelism.)
* Remove spaces - myString.replace(/\u0020+/g, "");
* Remove common line terminators - myString.replace(/(\r|\n)+/g, "");
* Remove all white space - myString.replace(/\s+/g, "");
https://swtch.com/~rsc/regexp/
I've had nothing but good experiences with it. (Rust's looks similar, by the way, and quite impressive.)
those engines too trade power for speed.
So it's not quite the fastest possible because it doesn't use SIMD, but this is mostly because we don't have good explicit SIMD support on stable Rust yet. Once we do, this immediately becomes a strong candidate to optimize to something like the OP's fastest version (and also probably generalizing to AVX2 instructions as well).
N.B. My sibling comment linked to my blog post on ripgrep, which uses Rust's regex engine. ;-)
[1] - https://github.com/BurntSushi/rust-memchr/blob/master/src/li...
Regular Expressions are efficient in that one line of code can save you writing hundreds of lines. But they're normally slower (even pre-compiled) than thoughtful hand written code simply due to the overhead.
Generally the simpler the objective the worse Regular Expressions are. They're better for complex operations. Plus people write regular expressions REALLY poorly, doubly so for UNICODE.
Ideally you should use the standard library for this. For example C# has Char.IsWhiteSpace() which supports tons of UNICODE whitespace and can be updated with whitespace which doesn't even exist today.
You're responding to a point never made.
# string replacement
s = ' hello world \n'
s.replace(' ', '')
# 'helloworld'
# regular expression
import re
re.sub('\s+', '', s)
# 'helloworld'
# compiled regular expression
pat = re.compile('\s+')
pat.sub('', s)
# 'helloworld'
s = ' hello world \n'
s = ''.join(s.split())