8 ms·
Avoid character-by-character processing when performance matters
- PudgePacket 6y agoCurious 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 https://redis.io/topics/protocol
- 56quarters 6y agoThe 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 6y 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.
- nkurz 6y agoI'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 https://godbolt.org/z/WfPWEz
- lilyball 6y agoIs the optimizer allowed to add extra memory accesses to locations that otherwise wouldn’t have been accessed? Because that’s required here.
- kevingadd 6y agoIn 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.
- deathanatos 6y agoNo, what they mean is that, say we have a block read of 8 in the unrolled version, and all upcoming 8 indexes are valid memory locations, that is, a read would never segfault and never cause UB. Say they are: 20 20 20 20 ff 20 20 20 ^^ The ff is where the naïve algorithm would abort. But, some versions of an unrolled loop, if they do an 8-byte move to a register would read/access all 8 bytes. But the naïve version won't; it'll stop at the ff, never accessing the last 3 bytes. Even if we can guarantee the bytes are valid, does C somehow guarantee that the accesses would not occur? But, even with that, you can still unroll the loop to: bounds check the next 8 bytes (is idx + 8 < size) read 1 byte, abort if not ascii read 1 byte, abort if not ascii etc. It isn't as efficient as reading 8 bytes in one fell swoop and using math magic to process them all in one pass. But it still means that, so long as we remain in this unrolled version, we're eliding 7 out of 8 bounds checks and increments to the index.
- BeeOnRope 6y agoThe benefit of unrolling like this is quite small: just some reduction of loop overhead. The primary trick demonstrated here is combining 8 checks into a single operation.
- deathanatos 6y agoOh, absolutely, the trick demonstrated in the article is significantly better. (That I had to elide 75% of the instructions in the psuedo-code that I wrote is practically proof of that.) My point was only that it is possible to unrolled the loop without introducing UB.
- kevingadd 6y agoThis 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.
- userbinator 6y agoThings 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
- jeffbee 6y agoTo 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 6y agoExactly 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;}); }
- im3w1l 6y agoSo 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.
- jonstewart 6y agoSTL is great! How’s the performance, though, compared with TFA’s optimistic and hybrid versions?
- cornstalks 6y agoAnd 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 6y agoClang 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 https://godbolt.org/z/oefzhx
- 6y ago
- reagent_finder 6y agoBitwise 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 6y agoThis 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 6y 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.
- jonstewart 6y agoDaniel Lemire’s code is most definitely in production, returning fast results so your client code can burn CPU on JavaScript frameworks.
- wruza 6y agoAs if we chose to burn cpu on specifically javascript frameworks.
- RcouF1uZ4gsC 6y agoWhile 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 6y agoA 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 6y agoYou can see Mozilla iterating on the same example of is_ascii() here, using SSE: https://bugzilla.mozilla.org/show_bug.cgi?id=585978 https://bugzilla.mozilla.org/show_bug.cgi?id=585978
- deleted 6y ago[deleted]
- jakeogh 6y agoFast getdelim() replacement: https://github.com/ThePythonicCow/rawscan https://github.com/ThePythonicCow/rawscan ebuild: https://github.com/jakeogh/jakeogh/blob/master/dev-libs/rawscan/rawscan-9999.ebuild https://github.com/jakeogh/jakeogh/blob/master/dev-libs/raws...