6 ms·
If you were careful, it seems pretty plausible to be able to use some indexing tricks and CMOV to write a jump/branchless version of wc. You are basically count
by jnordwick 7y ago
If you were careful, it seems pretty plausible to be able to use some indexing tricks and CMOV to write a jump/branchless version of wc. You are basically counting newlines and runs of whitespace.
- zerr 7y agoCMOV aside, I remember it was proved MOV itself is turing-complete.
- orangse 7y agohttps://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator posting for anyone wondering
- agumonkey 7y agoslightly related, does embedding arithmetic in mov instructions go faster than explicit ALU operations ?
- Filligree 7y agoDepending on the arithmetic, it seems that yes it can! I've noticed gcc using LEA instructions for arithmetic of the form (x * a + b), where 'a' and 'b' fit with the instruction.
- jnordwick 7y agoUsing LEA (load effective address) for calculation seems to be pretty common in most programs for both gcc and llvm. You basically get smaller code, and it used to schedule them better across more execution ports. Not sure if the CPU can fuse the ADD+MUL now.
- pasquinelli 7y ago"Counting newlines" implies branching.
- gpderetta 7y agoNot really: cnt += *ptr++ == '\n' Should compile down to no branches (not even cmov) by summing the value of the flag register directly. Would be a it hard to stop without taking a branch though. Would you consider function pointer calls a branch? If that's too easy, what about taking a segfault?
- BeeOnRope 7y agoEven if you do the branchiest thing possible in the source, no bitwise or "looks cmov-y" stuff, all compilers that matter will do this without a branch with optimization on: https://godbolt.org/z/XCBGYW https://godbolt.org/z/XCBGYW Only icc vectorizes this at -O2 (still branchless, of course), but clang and gcc vectorize it if you go to -O3.
- gpderetta 7y agoSure, but where's the code golfing fun in there ;)
- BeeOnRope 7y ago:) I guess I'm not fun at [code golfing] parties. I just want to gently push back on the notion that the source level branchy-ness is tightly tied to the generated assembly level branchiness. Sometimes, it is - but it is a long topic to characterize when. For simple things like counters based on a condition, you'll almost always get branch-free. Same for assignment/return value based on a condition, where the possibilities don't involve lots of asymmetric work (or a asymmetric memory access).
- rcoveson 7y agoYou could subtract the value of '\n' from each byte, bitwise-or the result with its negated value, right shift the sign bit into the least significant position, and push that into an accumulator. Basically, it is possible to reduce a byte into a one or a zero if it does or does not match a value using only bitwise instructions. I don't know if the way I just described uses the fewest instructions, but you can definitely do it without branching. In fact, you can do this to test any integer comparison. Start by subtracting the arguments to the comparison operator, and then use one of these "squash" functions for the comparison operator in question (assuming 32 bit signed integers are being compared): == : ~(c | -c) >>> 31 != : (c | -c) >>> 31 > : -c >>> 31 >= : ~c >>> 31 < : c >>> 31 <= : ~-c >>> 31
- BeeOnRope 7y agoYeah, it's Nnt just plausible, it's fairly straightforward. Here are some untested versions that have branch-free inner loops for lines (easiest, this will probably compile branch-free even if you aren't careful), and words: https://godbolt.org/z/JNU-_G https://godbolt.org/z/JNU-_G