8 ms·
Eliminating branches in Rust for fun but not much profit
- vbezhenar 11y agoNot everyone running Haswell. Would be interesting to compare this performance with other processors.
- zamalek 11y agoAnecdotally I've had similar experiences with older processors in C#, dating back to ~2007.
- acconsta 11y agoAlso mobile. ARM processors have less-sophisticated branch prediction, and on the lower end, no branch prediction at all!
- masklinn 11y agoIsn't that because lower end ARM is in-order?
- bonzini 11y agoIt's a bit weird that he doesn't provide his solution. I would be surprised if this isn't faster: pub fn is_token1(c: u8) -> bool { let mask = if c < 32 { !0 } // c != 32 && c != 34 && c != 40 && c != 41 && c != 44 && c != 47 && !(c > 57 && c < 64) else if c < 64 { 1 + 4 + 256 + 512 + 4096 + 32768 - (1 << 25) } // c != 64 && !(c > 90 && c < 94) else if c < 96 { 1 + (1 << 30) - (1 << 26) } // c != 123 && c != 125 else if c < 128 { (1 << 27) + (1 << 29) } else { !0 }; ((mask >> (c & 31)) & 1) == 0 } or this for 64-bit: pub fn is_token2(c: u8) -> bool { // roughly follows the order of ascii chars: "\"(),/:;<=>?@[\\]{} \t" let mask = if c < 64 { (1u64 << 33) - 1 + ((4u64 + 256u64 + 512u64 + 4096u64 + 32768u64) << 32) + !((1u64 << 57) - 1) } else if c < 128 { 1 + (1 << 30) - (1 << 26) + (1u64 << 59) + (1u64 << 61) } else { !0u64 }; ((mask >> (c & 63)) & 1) == 0 } (Forgive me, it's the first time ever I write Rust...) and if it is slower, it could also be because LLVM generates a slow bt instruction.
- Gankro 11y agoNote that rust has bit literals, so you can explicitly write bit masks out: let mask = if blah { 0b11111110000000001001001100000101u64 } else { 0 } and you can include optional underscores wherever for clarity let mask = if blah { 0b_11111110_00000000_10010011_00000101_u64 } else { !0 }
- deleted 11y ago[deleted]
- masklinn 11y ago/u/dbaupp made the same remarks: https://www.reddit.com/r/rust/comments/3l3bnn/eliminating_branches_in_rust_for_fun_but_not_much/cv329g5 https://www.reddit.com/r/rust/comments/3l3bnn/eliminating_br...
- viraptor 11y agoThere are some really good alternatives in reddit comments: https://www.reddit.com/r/rust/comments/3l3bnn/eliminating_branches_in_rust_for_fun_but_not_much/ https://www.reddit.com/r/rust/comments/3l3bnn/eliminating_br...
- phkahler 11y agoFor some cases I've found bitwise stuff to be faster. I'd try replacing: (c < 128 && c > 31) With ((c < 128) & (c > 31)) != 0 if this were in C.
- Gankro 11y agoThis strikes me as the kind of peephole optimization that LLVM would do anyway (similar to people manually converting `x / 2` to `x >> 1`, my nemesis). But maybe it's esoteric enough for them to not bother?
- deleted 11y ago[deleted]
- chrisdew 11y agofn is_token(c: u8) -> bool { // roughly follows the order of ascii chars: "\"(),/:;<=>?@[\\]{} \t" c < 128 && c > 32 && c != b'\t' && c != b'"' && c != b'(' && c != b')' && c != b',' && c != b'/' && !(c > 57 && c < 65) && !(c > 90 && c < 94) && c != b'{' && c != b'}' } I've not done much with Rust, but why is it stated: “LOOK && AT && ALL && THOSE && BRANCHES!” I don't see branches, just the evaluation of a complex bool expression. If there were lots of "ifs" and "elses" I would see branches. Can someone explain?
- masklinn 11y ago> Can someone explain? && short-circuits, so before each &&, if the LHS is false it will jump to the end of the whole thing with a `false` result If you plug the function into goldbot (http://rust.godbolt.org http://rust.godbolt.org) you see a bunch of conditional jumps: cmpl $7, %ecx jb .LBB0_10 movzbl %dil, %ecx cmpl $47, %ecx je .LBB0_10 cmpl $44, %ecx je .LBB0_10 movb %dil, %dl andb $-2, %dl movzbl %dl, %edx cmpl $40, %edx je .LBB0_10 cmpl $34, %ecx je .LBB0_10 cmpl $33, %ecx jb .LBB0_10 testb %dil, %dil js .LBB0_10
- chrisdew 11y agoThanks, I'd not seen godbolt before - this is very useful.
- userbinator 11y agoShort-circuit evaluation. The structure of the flow looks like a ladder. The (x86) assembly produced would look something like this: cmp al, 128 jae false cmp al, 32 jbe false cmp al, 9 jz false cmp al, '"' jz false cmp al, '(' jz false cmp al, ')' jz false ... Edit: yes, I know 9 is less than 32 and would've been caught by the condition before it; I was just "mentally compiling" the expression directly without thinking much about optimising it.
- chrisdew 11y agoThanks for that. Would adding extra brackets (turning it into a tree structure) allow the CPU to use multiple ALUs to evaluate branches in parallel? ( ( ( c < 128 && c > 32 ) && ( c != b'\t' && c != b'"' ) ) && ( ( c != b',' && c != b'/' ) && ( !(c > 57 && c < 65) && !(c > 90 && c < 94) ) && ( c != b'{' && c != b'}' ) ) )
- userbinator 11y agoTesting if a value is in one of two sets reminds me of this article: http://www.hugi.scene.org/online/coding/hugi%2017%20-%20coaax.htm http://www.hugi.scene.org/online/coding/hugi%2017%20-%20coaa... Depending on whether the sets line up, this can be done in 2(!) instructions totaling to 4 bytes, and around 25 clock cycles. Nowhere near as fast as the bit-table lookup approach, but possibly the smallest.
- evmar 11y agoI went down a similar route in a performance-sensitive lexer (started with naive code, spent some time fiddling with different ways to express it) and eventually used a lexer generator, which uses a combination of lookup tables and tests. https://github.com/martine/ninja/blob/master/src/lexer.cc#L117 https://github.com/martine/ninja/blob/master/src/lexer.cc#L1...
- rcthompson 11y agoI know the (non-bitwise) boolean operators have shortcutting behavior, but if evaluating the second clause has no side effects, couldn't the compiler just cheat by evaluating both clauses unconditionally and then combining the two boolean results using the equivalent bitwise operation, thus avoiding a branch?
- drewm1980 11y agoThis sounds like a textbook candidate for superoptimization.