10 ms·
How quickly can you remove spaces from a string?
- et1337 10y agoCached text-only version: http://webcache.googleusercontent.com/search?q=cache%3Ahttp%3A%2F%2Flemire.me%2Fblog%2F2017%2F01%2F20%2Fhow-quickly-can-you-remove-spaces-from-a-string%2F&strip=1 http://webcache.googleusercontent.com/search?q=cache%3Ahttp%...
- octo_t 10y agoSo using 128bits instructions would imply you had 'words' which were over 16 characters long on average, right? The average (english) word is ~5 characters long, so most of the time, you'd be forced to check anyway.
- countryqt30 10y agoYou are so right - everything depends on the dataset. Now after all, just skipping 4 characters (1 byte, 32 bit arch) actually seems VERY reasonable. 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
- nkurz 10y agoThis is a good instinct, but doesn't work well in practice unless the prevalence of spaces is very low. And if it's very low, you only need the largest check followed by a single fallback. The problem is that mispredicted branches (for example, 'if statements' that require different code paths without a clear pattern) are relatively expensive. 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.
- drdrey 10y agoNot all strings are made of English text
- sfrailsdev 10y agoyou don't even have to go to non english, just utf-8 has stuff like mathematic spaces and spaces of different em sizes. http://perldoc.perl.org/perlrecharclass.html http://perldoc.perl.org/perlrecharclass.html has a reasonably good list of non ascii spaces, though I'm not sure where to dig through for locale specific lists. 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.
- criddell 10y agoIs there a clever way to remove all the space characters? https://www.cs.tut.fi/~jkorpela/chars/spaces.html https://www.cs.tut.fi/~jkorpela/chars/spaces.html
- gravypod 10y ago"ZERO WIDTH NO-BREAK SPACE foobar No width (the character is invisible)" Time to insert this into some of my friends code.
- squeaky-clean 10y agoI've actually joked with colleagues about this, and often it doesn't work. Try using the U+FEFF in Javascript, in Chrome it's taken as a space (but the console will mark it as a red circle, not an invisible no-width character), and Firefox refuses to even allow it to be entered. 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.
- nitrogen 10y agoI've had problems with code having non-ASCII spaces appended, and the terminal rendering them as zero-width, so I had to use hexdump to find the problem.
- sedachv 10y agoAlso fun are left-to-right and right-to-left marks.
- squeaky-clean 10y agoThis is a level of evil I hadn't considered.
- 10y ago
- mnarayan01 10y agoI feel like you have to at least include non-breaking spaces if you're going to say you're removing spaces from UTF-8 strings.
- dsp1234 10y agoThis code will work on all UTF-8 encoded strings… which is the bulk of the strings found on the Internet if you consider that UTF-8 is a superset of ASCII. 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
- delinka 10y agoDo you mean to say that TFA makes the incorrect assumption that UTF-8 is a single byte encoding?
- averell 10y agoNo, the article states the method will correctly remove the mentioned whitespace characters even from UTF-8 text, because they are part of the 7 bit subset this method works on.
- deleted 10y ago[deleted]
- MereInterest 10y agoOne neat thing about UTF-8 is that all bytes that compose non-ASCII characters will have the high bit set. ASCII values range from 0-127, so no ASCII values will ever have the high bit set. Therefore, a byte that corresponds to an ASCII value is guaranteed to be the same character as the corresponding ASCII encoding.
- ajross 10y ago
- austincheney 10y agoIsn't this the very kind of thing Regular Expressions were created to solve? * Remove spaces - myString.replace(/\u0020+/g, ""); * Remove common line terminators - myString.replace(/(\r|\n)+/g, ""); * Remove all white space - myString.replace(/\s+/g, "");
- SonicSoul 10y agothe post is not so much about most convenient way to remove spaces, but about efficiency of such an operation.
- austincheney 10y agoIs regex execution considered efficient? I have always been impressed with its speed.
- throwanem 10y agoSimple regexes can be reasonably quick, but you're almost certainly never going to do better than linear time, and if you get fancy, it's easy to go exponential with a large exponent.
- deleted 10y ago[deleted]
- pjscott 10y agoIf you want to guarantee that this will never happen, RE2 and similar regular expression engines are guaranteed to run in O(n) time, where n is the length of the target string. https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/ I've had nothing but good experiences with it. (Rust's looks similar, by the way, and quite impressive.)
- burntsushi 10y agoIndeed. Rust's regex engine is descended from RE2. rsc's blog posts were my guide when I first wrote it.
- hcrisp 10y agoNot claiming to be the fastest, but here are two Python solutions suggested by Dave Beazley [0], plus one I extended using compiled regular expressions: # 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' [0] https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwiDwpPQytHRAhVJWCwKHSTmD5wQFggaMAA&url=https%3A%2F%2Fwww.safaribooksonline.com%2Flibrary%2Fview%2Fpython-cookbook-3rd%2F9781449357337%2Fch02s11.html&usg=AFQjCNEZqL6SV76UmE4ojyJ5poOgeCexEQ&sig2=I9kGVDVg5DyLxZ3pCJ1FIw&bvm=bv.144224172,d.bGg https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&c...
- Darge 10y agoDoes anyone know how to do such a benchmark?
- sp332 10y agoCheck out the linked Github repo.
- dzdt 10y agoSomehow 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.
- 10y ago
- saretired 10y agoThe “optimized” functions have a bug when the number of remaining bytes is less than the block size.
- nkurz 10y agoCertainly possible, but are you looking at the excerpts in his blog post, or the actual code that he links to? https://github.com/lemire/despacer/blob/master/include/despacer.h https://github.com/lemire/despacer/blob/master/include/despa...
- saretired 10y agoI'm looking at the excepts in his post, which are broken.
- stelund 10y agoMaybe the asm to do scan for byte in memory is an alternative. Repne scab. It won't find all characters in a single scan. But maybe do 3 passes over a buffer which fits in cache.
- cowardlydragon 10y agoASCII/1 byte characters? I stopped reading then. UNICODE or GTFO. Should be embarassingly parallel for a contiguous array.
- foxhill 10y agothis is in no way embarrassingly parallel at all! in fact, it's entirely non trivial to parallelise, writing the output is an inhertintly a serial operation.
- mrkgnao 10y agoCould you not do something like chunk the input and operate on the pieces in parallel? I'd think you could use something like a rope (à la text editors) to support the concurrent writes. (I may or may not have forgotten the differences between concurrency and parallelism.)
- foxhill 10y agoyeah, you could split the input into chunks, but then you're left with the problem of recombining the outputs from each portion into one string - that operation must be serial and would likely outweigh the benefits of the initial parallelism in most cases.
- ascotan 10y agoI guess you could write CUDA code to do this on a GPU, but then the question becomes why? :/
- castratikron 10y agoI don't think this particular problem would be well suited for a GPU. GPUs are not vector processors, they're matrix processors, and the problem that OP is describing is a vector problem. Basically this problem would be limited by the memory bandwidth of a GPU, which isn't a good thing: https://crd.lbl.gov/departments/computer-science/PAR/research/roofline/ https://crd.lbl.gov/departments/computer-science/PAR/researc...
- antonmks 10y agoOk, here it is : https://gist.github.com/antonmks/17e0c711d41fb07d1b6f3ada3f5f29ee https://gist.github.com/antonmks/17e0c711d41fb07d1b6f3ada3f5... 0.25 cycles/byte using GTX 1080.
- mkagenius 10y agoThe Why has multiple answers - one is human curiosity for possibilities of better result (which is the sole cause of all the technology we see around us).
- ebbv 10y agoOptimizing by hand is rarely the fastest thing to do nowadays. I wonder how the original naive approach fairs with all optimizations turned on for gcc and with realistic input?
- Too 10y agoThe optimization flags used should be good enough. https://github.com/lemire/despacer/blob/master/Makefile https://github.com/lemire/despacer/blob/master/Makefile CFLAGS = -fPIC -std=c99 -O3 -march=native
- aib 10y agoI wonder how much of a difference using a separate destination buffer would make. Apart from some memory/cache/invalidation/magic thing that I'm not certain might occur, it would allow one to use the extended instructions used for scanning.
- fisherjeff 10y agoAdding lookup tables to the naïve implementation gave me a ~3x speedup with virtually no extra effort. Branch penalties are a real killer.
- twoodfin 10y agoYou have to be careful with lookup tables. They can be impressive each at a time when microbenchmarking a single loop, but in the aggregate hurt performance by crowding other useful data out of limited cache space.
- nogracias 10y ago6.5MB for the tables to drive this faster de-spacer? No thank you. It would blow out the L1 cache and make your program slower. https://raw.githubusercontent.com/lemire/despacer/master/include/despacer_tables.h https://raw.githubusercontent.com/lemire/despacer/master/inc...
- jnordwick 10y agoMy pet peeve: using table lookups so a benchmark show faster when in reality your L1 cache is going to be stomped on. Not only will you be waiting on the L1 cache to populate but you also evict all the useful data.
- exDM69 10y agoI've seen this elsewhere too. For relatively mundane task (I think it was Morton code conversion), a giant lookup table was constructed and it gave a nice 2x or 4x performance improvement. 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.
- brianpgordon 10y agoThis reminded me of spray-json's JsonParser. It has a bit of Scala code to seek past whitespace: @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() } https://github.com/spray/spray-json/blob/765c83248e0bbe867ddc9d479b4fe79493569a54/src/main/scala/spray/json/JsonParser.scala#L186 https://github.com/spray/spray-json/blob/765c83248e0bbe867dd...
- hota_mazi 10y agoThe compiler needs to be extremely clever on @tailrec for not blowing up the L1 cache on this code. 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).
- jnordwick 10y agoCan you please explain why it would blow up the L1 cache?
- computator 10y agoWhat strikes me is how many sites won't accept a login name, credit card number, phone number, or other field with leading or trailing spaces. This for something where the speed of the code doesn't matter at all. I can't think of any explanation other than incredible laziness or incompetence for not stripping off spaces. 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.
- edblarney 10y agoYou hit the issue in a roundabout way: 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.
- open-source-ux 10y agoAs a culture, we are are obsessive about 'performance'. 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.
- tjalfi 10y agoI have an excellent example of this. 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.
- johnnyb9 10y agoGoing to start using this as an interview question!
- webo 10y agoPlease don't. Especially for a typical software engineering position.
- chrismorgan 10y agoA variant of this problem yields further interesting possibilities: if you’re trying to remove control characters like CR and LF, but replacing them with whitespace would be acceptable. That way you can work on it in-place, without needing to copy memory or allocate or anything like that.
- Too 10y agoSomeone file a compiler bug? 14x difference between the readable code and the optimized code is a lot. The first code is extremely straightforward, you shouldn't have deal with that SIMD mess manually.
- Sharlin 10y agoFailure to optimize is never a bug, by definition. Automatic vectorization of sequential code is a very difficult problem in general. Especially when your code still depends on testing single bytes in the input and vectorizing that is only possible using some very clever bit twiddling.
- exDM69 10y agoCan you come up with a vectorization optimizer pass that could do what the OP did in the article? 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.
- Annatar 10y agoawk ' { gsub(/[[:blank:]\015]/, ""); printf("%s", $0); }' input | tee output stripping out LF isn't necessary because AWK does it on every record automatically. For even more speed, the code can be translated into ANSI C and compiled with awka[1] using an optimizing C compiler. [1] http://awka.sourceforge.net/index.html http://awka.sourceforge.net/index.html
- deleted 10y ago[deleted]
- jakobegger 10y agoFun story: When I implemented the syntax highlighting feature in Sequel Pro, I needed a way to determine the string length of UTF-8 encoded strings. I didn't find a function available on macOS that worked directly on a char*, so I googled and found a really simple UTF-8 strlen function. It was easy to understand and very fast. I think it was this: http://canonical.org/~kragen/strlen-utf8.html http://canonical.org/~kragen/strlen-utf8.html 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-strlen.html 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.
- exDM69 10y agoI am surprised to see any speedup in this! 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. 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) Here's the diff to the original: http://pasteall.org/208511 http://pasteall.org/208511 edit2: surprisingly, Clang is about 10% slower than GCC in my experiments.