Related. Others?
The radix 2^51 trick - https://news.ycombinator.com/item?id=33706153 - Nov 2022 (6 comments)
The radix 2^51 trick (2017) - https://news.ycombinator.com/item?id=23351007 - May 2020 (83 comments)
The radix 2^51 trick (2017)
11–20 of 86 posts
Re: The radix 2^51 trick (2017)
#12Someone working entirely on x86_64 very nicely demonstrates that RISC-V is not wrong to omit the carry flag.
Also, there is another way to do this while keeping 64 bit limbs. All variables uint64_t.
s0 += a0;
s1 += a1;
s2 += a2;
s3 += a3;
c0 = s0 If you express this with a conditional branch which is overwhelmingly predicted as not taken then the code should execute each block of instructions entirely in parallel, provided that multiple conditional branches can be predicted as not-taken in the same clock cycle.
One time in 2^64 it will execute very slowly.
With 4 limb numbers on a 4-wide machine this doesn't offer an advantage over `adc` as there are also 4 code blocks. But on, say, an 8-wide machine with 8 limb numbers you're really starting to gain.
It's probably not going to help on current x86_64, but might well do on Apple's M* series, where even the M1 is 8-wide, though it might be tricky to work around the Arm ISA.
When the 8-wide RISC-V Ascalon processor from Tenstorrent hits hopefully late this year or early 2026 we will really see. And others such as Ventana, Rivos, XiangShan.
This will work even better in a wide SIMD, if you have a fast 1-lane shift (Called slideup on RISC-V).
Re: The radix 2^51 trick (2017)
#13The main takeaway: doing more operations may be faster if they are largely independent, and thus can execute in parallel. Doing fewer operations may be slower if they are forced to execute serially due to data dependency. This idea has wider applicability than operations on long integers.
Yes. Another approach would be to use regular 64 bit chunks and speculatively execute each add with and without carry in parallel. Then select the correct variant based on carry result of less significant addition.
With double the amount of additions this allows for log(bits) propagation time (versus linear)
Re: The radix 2^51 trick (2017)
#14The main takeaway: doing more operations may be faster if they are largely independent, and thus can execute in parallel. Doing fewer operations may be slower if they are forced to execute serially due to data dependency. This idea has wider applicability than operations on long integers.
Yes. Another approach would be to use regular 64 bit chunks and speculatively execute each add with and without carry in parallel. Then select the correct variant based on carry result of less significant addition. With double the amount of additions this allows for log(bits) propagation time (versus linear)
There's not just "result with carry" and "result without carry" but rather one variant of that per word of the input
... Which likely isn't that bad to code up.
Re: The radix 2^51 trick (2017)
#15> Aside: Why 13 bits instead of 12? For our purposes, we’re going to ignore the carries in the most significant limb, allowing numbers to wrap when they overflow past 2256 - 1 (just like how unsigned addition works in C with normal size integer types). As a result, we can assign 52 bits to the most significant limb and ignore the fact that it will run out of room for carries before the other limbs do. Why not give th…
[deleted]
Re: The radix 2^51 trick (2017)
#16> Aside: Why 13 bits instead of 12? For our purposes, we’re going to ignore the carries in the most significant limb, allowing numbers to wrap when they overflow past 2256 - 1 (just like how unsigned addition works in C with normal size integer types). As a result, we can assign 52 bits to the most significant limb and ignore the fact that it will run out of room for carries before the other limbs do. Why not give th…
Then you would need 6 words to hold a 256-bit value instead of 5 in the OP, and consequently more instructions to add them.
Re: The radix 2^51 trick (2017)
#17> Aside: Why 13 bits instead of 12? For our purposes, we’re going to ignore the carries in the most significant limb, allowing numbers to wrap when they overflow past 2256 - 1 (just like how unsigned addition works in C with normal size integer types). As a result, we can assign 52 bits to the most significant limb and ignore the fact that it will run out of room for carries before the other limbs do. Why not give th…
Then you would need 6 words to hold a 256-bit value instead of 5 in the OP, and consequently more instructions to add them.
64 + 48 * 4 == 256... still just five 64-bit words.
Re: The radix 2^51 trick (2017)
#18I'm seriously doubtful that adc is inherently slower than add on a modern CPU other then the data hazard introduced by the carry bit. I realize the point of the article is the data hazard so this is a really minor nit.
You are right: it can be done with the same ALU, for sure. But the data dependency on the carry flag makes it a really different instruction from the point of view of the CPU: three data dependencies in stead of two. For the CPU it is beneficial to treat the instructions differently.
Re: The radix 2^51 trick (2017)
#19Would it be legal for a C(++?) compiler to implement this optimization?
Does C++ have native support for uint256?
With C, it is _BitInt(256) if the compiler supports it. The upper limit of _BitInt is implementation-defined though, so 256 is not guaranteed to be supported. Eg clang on RV64 only supports upto 128, but does support 256 on x64_64. gcc seems to not support _BitInt on RV64 at all, but does support 256 on x86_64.
With C++ the existence of such "extended integer" types is implementation defined. clang at least supports the same _BitInt construct for C++ too. gcc seems to not support it.
So, for the 256 case on x86_64, both clang and gcc seem to only generate the simple adc ripple version: https://gcc.godbolt.org/z/nxoEda3q5 https://gcc.godbolt.org/z/bYf4bor3f
Re: The radix 2^51 trick (2017)
#20The main takeaway: doing more operations may be faster if they are largely independent, and thus can execute in parallel. Doing fewer operations may be slower if they are forced to execute serially due to data dependency. This idea has wider applicability than operations on long integers.
Yes. Another approach would be to use regular 64 bit chunks and speculatively execute each add with and without carry in parallel. Then select the correct variant based on carry result of less significant addition. With double the amount of additions this allows for log(bits) propagation time (versus linear)