Midpoint obsession
namark@disroot.org
namark@disroot.org
Sun Sep 6 16:24:52 GMT 2020
Hello, what do you think about this midpoint implementation for integers?
https://git.sr.ht/~namark/libsimple_support/tree/a35dc5f34bac6139cd8394311ef9d7dbffdd02b0/source/simple/support/algorithm.hpp#L361-371
The best way I can explain it is 2's complement with the carry as a sign and the unsigned integer as the lower bits. For the addition and subtraction the sign doesn't matter as it doesn't affect the lower bits (which we know can hold the result). The division on the other hand is sign sensitive, so in case of negative difference between a and b it is done in three steps (negation -> division -> negation).
Even though I wrote it with conditional move in mind, something about it makes gcc prefer to generate a branch on x86, and usually I wouldn't argue, but to validate my efforts I asked for -fno-guess-branch-probability, which proved it can produce shorter(better?) branchless assembly as well. Also got slight shortening on armv7-a. I believe the code doesn't make any more assumptions than the current implementation, though I haven't tested it on other platforms.
Any feedback is appreciated, and I'm happy to contribute if you think this is a meaningful improvement.
More information about the Libstdc++
mailing list