Avoid character-by-character processing when performance matters

https://lemire.me/blog/2020/07/21/avoid-character-by-character-processing-when-performance-matters/

by ingve • 6 years ago

76 51 6 years ago

Curious how this would apply to the Redis protocol. It's a text protocol that is friendly/intended for character by character parsing. The example code at the bottom of the page is an example of iterating the characters of a byte stream.

https://redis.io/topics/protocol

56quarters• 6 years ago

The Redis protocol uses length prefixes for bulk strings and arrays (per your linked document). That enables it to read multiple bytes at a time off the socket, though it does seem like you'll still end up doing a bit of character by character processing with the result.

  RESP uses prefixed lengths to transfer bulk data, so there is never a need to scan the payload for special characters like it happens for instance with JSON, nor to quote the payload that needs to be sent to the server.

  The Bulk and Multi Bulk lengths can be processed with code that performs a single operation per character while at the same time scanning for the CR character, like the following C code:

mac-chaffee• 6 years ago

After the first CR is identified, it can be skipped along with the following LF without any processing. Then the bulk data can be read using a single read operation that does not inspect the payload in any way.

Sounds like it only does the character-by-character processing for a dozen or so characters (to read the the command, control chars, and the length). And I think the character-by-character processing is also converting the string "123" to an integer, so the trick of using &&/|| might not work.

nkurz3• 6 years ago

I'm somewhat surprised that compilers doesn't optimize this automatically. I thought at first that it might be something C++ related, but I tried a straight C equivalent[1] with Godbolt and it wasn't optimized by any the main compilers either. Is there a standard related reason why this can't be optimized to work on chunks of 8B ints? Or even longer vectors? Or is this just proof of the fact that there are so many possible optimizations that a compiler can't possibly do all of them?

[1] https://godbolt.org/z/WfPWEz

lilyball• 6 years ago

Is the optimizer allowed to add extra memory accesses to locations that otherwise wouldn’t have been accessed? Because that’s required here.

kevingadd3• 6 years ago

In another language, perhaps. It'd definitely be introducing undefined behavior if you did it to C or C++, and it would likely cause intermittent crashes.

ridiculous_fish4• 6 years ago

This particular code cannot be effectively optimized because of the early exit inside the loop. What if `size` was enormous and the first character was negative? One extra byte of lookahead might SIGSEGV! So it must gingerly step one byte at a time.

Rewrite it to always consume the full string, and it goes 8 bytes at a time: https://godbolt.org/z/xG7avr

In practice the best implementations will manually align and then unroll.

mehrdadn3• 6 years ago

What if `size` was enormous and the first character was negative? One extra byte of lookahead might SIGSEGV! So it must gingerly step one byte at a time.

Pages aren't 1 byte each, they're 4KiB. You can't just segfault at by crossing 1 byte at any arbitrary address. Some alignment checks to handle edge cases should let the compiler at least read things 8-byte aligned in the steady state and only fall back on edge cases.

userbinator2• 6 years ago

More interestingly: if I use "good old-school C89" char instead of bool and make the loop body branchless, I get actual vector instructions that appear to be consuming 256 bytes at a time:

https://godbolt.org/z/57766b

Wow!

If I use bool and keep the body branchless (z |= (string[i] < 0);), the vector instructions disappear and it goes back to doing only 4 bytes at a time. That is very odd.

deathanatos4• 6 years ago

This particular code cannot be effectively optimized because of the early exit inside the loop. What if `size` was enormous and the first character was negative? One extra byte of lookahead might SIGSEGV! So it must gingerly step one byte at a time.

If `size` was enormous and the first character "was negative"¹, then one extra byte of lookahead would never SIGSEGV; `size` is enormous, and by definition, that is presumably more than our lookahead.

If you mean, "the first character of the lookahead's block" then it still doesn't make sense. Even in the case where we exit later, we still can't access later bytes of the lookahead if we don't know them to be out of bounds.

In the example Godbolt you linked to, the compiler is doing 8 byte jumps with the index. (It's not doing a great job, as we're still reading a byte at a time. But the bounds checks and the index increment will get reduced.) But, what the compiler is doing in your example could also be done in the early exit example. It'd be basically the same code, but replace .LBB0_10 with something like,

    cmpb $0, (%rdi,%rdx)
    js do_exit
    cmpb $0, 1(%rdi,%rdx)
    js do_exit
    # etc. for the remaining 6 reads
  .do_exit
    xorl    %eax, %eax
    retq

This is very similar to your Godbolt, which also does 8 individual memory accesses. We know they won't segfault here for the same reason we know they won't in your Godbolt: we check ahead that we can access the next 8 bytes and abort to the non-unrolled version if not.

The cmp/js's are very likely not as efficient as the mov/or's, but that's not the point; the point is the unroll is possible.

It is not the early exit that prevents a loop unroll. Something else is stopping it, either it does not think it worth it, is not sufficiently intelligent, or some arcana of C prevents it.

(Your example alternates between mov and or, in a very interesting pattern, which makes me suspect it also knows something there, and perhaps more opportunity.)

¹This is an ugly example, since the implementation is free to have a char with range 0-255.

Someone• 6 years ago

I don’t think the compiler can assume the entire memory range from string to string+size (exclusive) can be read (the ‘C machine’ only reads it up to the first byte ≥ 128), but even if so, the compiler doesn’t know whether bytes ≥ 128 are rare or common, nor does it know the distribution of buffer lengths.

⇒ I think you should only start complaining if the compiler had pragmas to indicate that returning ‘false’ is extremely rare and that size can run in the kilobytes, and the program used them.

kevingadd3• 6 years ago

This is a great example of what I'd call "vectorization without vector instructions", though you could also just call it pipelining. You recognize that you're going to be operating on big chunks of data at once, so you make allowances to be able to only operate in chunks - like ensuring you can overrun the end of the buffer - or split your main loop out so there is a 'slow path' for the start/end of your operation and a fast path for the rest of it. Then you just operate on as much data as possible in one go and ignore things like branching, early out, etc. You can mask your results at the end or simply discard unused outputs. The '(running & 0x8080808080808080)' example in this article is perfect because it recognizes that in the end you only need to be sure that nothing failed, you don't need to know what and you don't need to know when.

Most of the time if you see people doing this it's using vector registers and newer instruction sets, because that's where you get 2-10x speedups by doing it. But even on ARM and x86 without using vector registers, careful pipelining and vectorization can deliver pretty sizable speedups. It increases cache locality, cuts down on branches, and reduces register pressure.

I ended up working on a project a while ago where we had to port a game's software rasterizer to multiple targets, including a low-spec ARM device. Instead of trying to hand-code a NEON implementation (I don't remember for sure if it even had NEON...) I started by just vectorizing it to operate on groups of 4 pixels instead of one (because I could fit 4 pixels in a single regular-sized integer register) so that each iteration of the main loop was doing more work and spending less time waiting on memory. Just that alone ended up improving performance considerably at the kind of clock speeds I was dealing with, and on higher-spec x86 cores it was still a slight improvement for about a day of hacking and staring at disassembly.

userbinator2• 6 years ago

Things like this are why I wish x86 would've exploited its CISC-ness to do more autovectorisation in hardware, something like this:

    mov rsi, ptr
    mov rcx, size
    repz andb 80h ; while(rcx-- && !(al = *rsi++ & 0x80)) ;
    setz al

jeffbee2• 6 years ago

To be perfectly honest what I want to see, for the specific C++ case cited, is std::all_of with a suitable predicate. Let the compiler figure it out.

Plugged it into compiler explorer and clang 10 does unroll the std::all_of version, doing four chars at a time.

galkk• 6 years ago

Exactly that, I was surprised to see that looong for loop definition (I'm not using C++ at all) and wanted to see if there's anything else to simplify. First I found for_each then all_of

If anyone is interested, here is simpler version:

    bool is_ascii_branchy(const std::string_view v) {
        return std::all_of(v.begin(), v.end(), [](auto i) { 
    return uint8_t(i) < 128;});
    }

im3w1l2• 6 years ago

So I guess this would be the best way to write it if you have a set of long strings most of which are non-ascii, and most such strings having a high proportion of non-ascii? Since then early exit will really help.

jonstewart2• 6 years ago

STL is great! How’s the performance, though, compared with TFA’s optimistic and hybrid versions?

cornstalks• 6 years ago

And for a fair comparison, here's an imperative loop that's way cleaner than what TFA used:

    bool is_ascii_branchy(std::string_view v) {
        for (auto c : v) if (uint8_t(c) < 128) return false;
        return true;
    }

afmos• 6 years ago

Clang 10 appears to unroll the loop 4x, but does not perform the optimization from the blog post where comparisons are made 64 bits at a time (rather than 8 bits): https://godbolt.org/z/oefzhx

BeeOnRope8• 6 years ago

This doesn't generate anything close to what the author is talking about: it still does character-by-character comparisons. Sure, it has unrolled the loop (but this is nothing to do with std:: and everything to do with what optimizations are enabled by clang at various -O levels), but it hasn't combined 8 individual checks into a single 64-bit wide check of the same cost.

jeffbee2• 6 years ago

All true. But I’d expect an exceptional justification for the optimization in the article, balanced against readability and maintainability.

reagent_finder• 6 years ago

Bitwise hacks in production code? Seriously?

This is a nice gimmick to show off in an interview because the interviewer is definitely not going to get it, however it might backfire because the interviewer might realize a) you'll be out to get his job b) you might actually want to put stuff like this into production.

The idea is solid, don't get me wrong, and clever code is always clever code. Also like u/kevingadd mentions, the principle behind the thought is an important one, knowing when and how to handle data in bulk since you are looking for a needle in the haystack. For instance SQL and streams in Java are places where you need this kind of thinking.

But please, for the love of Gord, never put this bit of code in production.

cbsmith• 6 years ago

This isn't really about interview questions.

In the real world, this kind of approach is critical to making effective use of compute resources. This is the kind of stuff you want in production.

rainbow-road• 6 years ago

Bitwise hacks

There's nothing hacky about this — it's a very simple procedure.

the interviewer is definitely not going to get it,

I sure hope any interviewer for a software engineering position would get it. But this has nothing to do with interviews.

jonstewart2• 6 years ago

Daniel Lemire’s code is most definitely in production, returning fast results so your client code can burn CPU on JavaScript frameworks.

wruza• 6 years ago

As if we chose to burn cpu on specifically javascript frameworks.

RcouF1uZ4gsC• 6 years ago

While a neat trick, there are some caveats. First of all, the is_ascii_branchless can be written in c++ as

    return std::all_of(sv.begin(),sv.end(),[](uint8_t c){return c < 128;});

Once you do that, the differences in code complexity between this and the other solutions becomes even more stark.

Second, even the slow case is 2 GB/s. While the principle is helpful, the extra complexity may not be worth it in the vast majority of real life code.

P-ala-din• 6 years ago

A thing I want to stress, is that you pay for the "complexity" just once, and it gets amortized over all projects that use this code.

This is a standard technique, that is often used in String functions. You can see it also in implementations of strlen.

tyingq• 6 years ago

You can see Mozilla iterating on the same example of is_ascii() here, using SSE: https://bugzilla.mozilla.org/show_bug.cgi?id=585978

jakeogh• 6 years ago

Fast getdelim() replacement: https://github.com/ThePythonicCow/rawscan

ebuild: https://github.com/jakeogh/jakeogh/blob/master/dev-libs/raws...

Avoid character-by-character processing when performance matters

Related Stories