4 ms·
I have implemented this algorithm twice, once in ARM assembly and once in C. In some ways the assembly implementation was easier as you aren't forever fighting
by nickcw 6y ago
I have implemented this algorithm twice, once in ARM assembly and once in C.
In some ways the assembly implementation was easier as you aren't forever fighting with the compiler to get it to generate the correct instructions.
The 32 X 32 to 64 bit multiply is one example. There isn't a way of expressing that in C - you do a 64 X 64 bit multiply of 32 bit variables casted to 64 bits and hope the compiler gets the hint that it should be doing a 32 X 32 to 64 bit multiply not a 64 X 64 bit multiply. This of course involves reading the assembly output.
The other thing you'd like is addition with carry. It is possible to express this in C and have the compiler recognise what you are doing and generate the correct instructions but it is a pain! I noted the other day that zig has @addWithOverflow which is a step in the right direction.
I can see why the Author of the article found so many things to criticize in the algorithm studied, but I think they are mostly an artifact of the fact that C (and most high level languages) is a poor choice for low level arithmetic.
- haberman 6y ago> I noted the other day that zig has @addWithOverflow which is a step in the right direction. This seems reasonably easy to implement in C: #include <stdint.h> typedef struct { uint64_t val; uint64_t carry; } Result; Result addWithOverflow(uint64_t x, uint64_t y) { Result res = {x + y, x + y < x}; return res; } On GCC and Clang this does the right thing (grabs the carry flag): https://godbolt.org/z/dzP3TPGTW https://godbolt.org/z/dzP3TPGTW I agree a dedicated intrinsic like in Zig is even better, but it is nice that modern compilers make it reasonably straightforward to get the desired code even without dedicated intrinsics.
- nickcw 6y ago@addWithOverflow is easy to implement in C, but you still need to look at the assembler code to see if the compiler did the right thing. I don't like that tension between C code you've arranged in just the right way and hoping that it continues to generate the assembler output it did once. I guess a portable set of compiler intrinsics it what is really needed to solve this problem. There is an x86 intrinsic for 32 x 32 -> 64 bit multiply now-a-days https://docs.microsoft.com/en-us/cpp/intrinsics/emul-emulu?view=msvc-160 https://docs.microsoft.com/en-us/cpp/intrinsics/emul-emulu?v... And one for 32 + 32 -> 32 + carry also. Though I don't know how portable __emulu is.. does it work on ARM for instance?
- bombcar 6y agoToo bad you can’t put some sort of assert saying “this code should generate this assembly assuming x86-64” or something - at least get a warning if the compiler upgrade changes it.
- Karliss 6y agoIf the performance is important you can have performance regression tests. If not, then it probably doesn't matter too much if it always generates optimal assembly for this specific line of code.
- globular-toast 6y agoWhat about "addWithCarry", ie. ADC? Getting the carry bit seems only half the battle. I'd not seen this compiler tool before so had a quick play around with it. It's very cool! But I couldn't get a compiler to recognise it could use ADC.
- haberman 6y agoThis seems to work. The compiler has to see the previous add to know what is in the carry flag. #include <stdint.h> uint64_t addWithCarry(uint64_t x, uint64_t y, uint64_t z) { return x + y + (y + z < y); } Output here: https://godbolt.org/z/zfP7PnGcs https://godbolt.org/z/zfP7PnGcs
- teleforce 6y agoPerhaps it is best to implement algorithm D in D language ;-) Joking aside, since D natively support inline assembler it won't be a poor compromise and trade-off for algorithm D implementation in D. [1]https://en.m.wikipedia.org/wiki/Inline_assembler https://en.m.wikipedia.org/wiki/Inline_assembler