Earlier quoted context omitted.
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.
Now you can’t detect overflow?
The radix 2^51 trick (2017)
71–80 of 86 posts
Re: The radix 2^51 trick (2017)
#72Earlier quoted context omitted.
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)
Wouldn’t that produce 2^n possible results to choose from, where n is the number of chunks? That seems like a lot of additional (he-he) instructions executed.
Nope. Just 2n: each chunk pair is added once without carry, and once won't carry=1.
For as long as radix=2, you either have a carry or you don't.
Re: The radix 2^51 trick (2017)
#73Earlier quoted context omitted.
Wouldn’t that produce 2^n possible results to choose from, where n is the number of chunks? That seems like a lot of additional (he-he) instructions executed.
Nope. Just 2n: each chunk pair is added once without carry, and once won't carry=1. For as long as radix=2, you either have a carry or you don't.
For a single addition, the radix is irrelevant, the carry is always zero or one: (r-1) + (r-1) = 2r - 2 < 2r.
Re: The radix 2^51 trick (2017)
#74I wish I came across this article a couple months ago.
I was trying to encode and decode some buffers into an arbitrary base, and I eventually came to the conclusion (after far too long) that a carry could ripple all the way down the buffer, which dramatically slows down the algorithm.
Actually, the eventual solution I came up might have some stuff in common with this trick too. I did eventually chunk up the buffer leaving some unused headroom to 'handle carries'. Not exactly though, I just have some wasted bits which uses a tiny bit more storage or network bandwidth but saves on compute. I wonder if I could instead pool up the carries like this and 'resolve' it in a later step. Have my cake and eat it too? Wishful thinking.
Re: The radix 2^51 trick (2017)
#75Earlier quoted context omitted.
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 The key insight here is that unless the sum at a particular limb position is all 1s the carry out from that position DOES NOT DEPEND on the carry in to that limb position, but only on whether the original add in that position produces a carry. If the sum is all 1s the the carry out…
I think you want to write: if (s1 == -1) c1 = c0; if (s2 == -1) c2 = c1; These can become conditional moves on x86. I've often thought RISC-V should have implemented an IF instruction instead of compare and branch. IF would cause the next instruction to be executed conditionally while not needing a flag register at the ISA level. They could have required only branch and jump to be conditional, but it turns out condit…
That sounds like it would be quite a pain to implement and program. E.g. what happens if there's an interrupt between the IF and the following instruction? You need to add a CSR to read/write the conditional state, similar to the vector control CSRs (vstart etc.). Hard to see how that extra complexity would be worth it.
Modern branch predictors are very good and most branches are very predictable.
Re: The radix 2^51 trick (2017)
#76Earlier quoted context omitted.
Intel is also supposed to introduce the new APX instructions which include a bunch of instructions that duplicate existing ones but don't set any flags. The only plausible reason to add these is for performance reasons.
This isn't just due to the actual dependencies of flag instructions at hardware level (although likely be a factor), it also majorly affects code layout. On Arm64 for example, you can make a comparison, do other operations, and then consume the result of that comparison afterwards, which is excellent for the pipeline and OoO engine. However, because most instructions on x86_64 write flags, you can't do this, and so y…
OoO should actually be the care where that doesn't matter I'd think - the CPU can, well, execute the instructions not in the order they're in the binary; it's in-order implementations are where that matters more.
And with compare & jump being adjacent they can be fused together into one uop, which Intel, AMD, and Apple Silicon all do.
Re: The radix 2^51 trick (2017)
#77Notwithstanding HN guidelines about not editorializing titles, I don't like these clickbaity titles amplifying a smaller claim to something overly broad: this one should have been titled:
"The radix 2^51 trick to adding 64-bit integers on *some* x86 architectures in parallel without slowing the pipeline due to dependencies on carry"
Re: The radix 2^51 trick (2017)
#78Earlier quoted context omitted.
What I didn't get about this: the technique shown seems to be about making sure that the ripple carry only happens once instead of N-1 times while adding N values. The carry operation is more complex, but this allows the actual addition to be parallelized. But - you still have to split the input numbers into sets of 5 registers in the first place, right? So doesn't that need to be parallelizable somehow as well in or…
That is paralelizable. Each of the 5 registers has no depence on the value of the others.
But when you split from 4 registers to 5, the bits for a given destination register may come from two different source registers.
Re: The radix 2^51 trick (2017)
#79Saw 2^51 and thought it was about storing integers into doubles. But nope, the number for that particular use is 2^53-1, not 2^51.
Re: The radix 2^51 trick (2017)
#80Earlier quoted context omitted.
>> because the software workaround for detecting integer overflow, which is mandatory for any program that claims to be written in a safe way, lowers the attainable performance much more than the workarounds for not having carry That's absurd. A better way is to ensure that your algorithms don't overflow. Detecting an overflow just means your code has to STOP which is usually not safe. It'd be insane to have conditio…
While there is no direct access to flags in standard C, you can nevertheless on gcc and clang compile with -ftrapv and get your signed integer arithmetic be overflow-checked. Or you can use __builtin_add_overflow & co and get access to the overflow flags that way. Rust debug builds trap on signed and unsigned integer overflow, and you can make release builds do so too. While it'd be nice to have a formal proof that e…
Oh, also, C23 added standard ckd_add & ckd_sub & ckd_mul for getting a boolean of whether the operation overflows (i.e. standard equivalent to __builtin_add_overflow)!