Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The radix 2^51 trick (2017)

chosenplaintext.ca

Post reply on HN
Print view View original

31–40 of 86 posts

Re: The radix 2^51 trick (2017)

#31

Post by animal531 »

russdill wrote: post #3

I'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.

CPU's are really funny and interesting things. Us programmers work with them daily and make so many assumptions about them, as well as the whole code chain from the compiler, runtimes, how code works when it comes to loops, methods etc., you name it.

I've been working on my own Entity Component System in C# and basically had to start from the ground up and test every assumption possible. There have only really been a few instances where my gut was correct, more often than not there are so many surprising gotchas hidden everywhere.

Re: The radix 2^51 trick (2017)

#32

Post by adrian_b »

brucehoult wrote: post #6

Someone working entirely on x86_64 very nicely demonstrates that RISC-V is not wrong to omit the carry flag.

There remain many frequently-encountered cases when carry-save addition is worse than addition using add-with-carry.

Neither of the 2 multi-word addition algorithms can replace the other, both have their use cases, so ADC/SBB instructions are included in any decent ISA, because the cost of adding them is negligible. A dedicated flag register is not necessary, some ISAs store the carry/borrow flags in general-purpose registers, when used.

Not having carry is by far not the worst feature of RISC-V. Much worse is not having an integer overflow flag, 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.

Re: The radix 2^51 trick (2017)

#34

Post by noduerme »

rollcat wrote: post #24
nine_k wrote: post #9

The 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.

This rule scales up all the way to multi-node supercomputers / cloud. The overhead is negligible when you can employ 10.000 cores.

Abstractly, when any parallel system scales up large enough without cross checking or waiting between "threads", the cost of de-duplicating and merging the output will probably outweigh the advantage of producing new results in tandem. I think. That's just a hypothesis, but feels correct. With stuff like a-life distributed over lots of servers all converging on evolutionary answers to a problem, it's the collation and analysis layer that's most expensive and slow. Sharing more frequently / allowing more reliance on central historical truth slows each one down but avoids duplication and redundancy. I guess where that point is depends on what problem you're trying to solve.

Re: The radix 2^51 trick (2017)

#35

Post by volemo »

Sukera wrote: post #28
addaon wrote: post #2

> 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…

Because adding the top limbs of two encoded numbers would overflow too soon. If you set both to 2^63 for example, they overflow immediately. Might be fine for wraparound arithmetic, but not in general.

Setting both to 2^63 means your original 256-bit numbers were 2^255, thus the addition would overflow no matter what intermediate encoding you’re using.

Re: The radix 2^51 trick (2017)

#36

Post by credit_guy »

rollcat wrote: post #24
nine_k wrote: post #9

The 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.

This rule scales up all the way to multi-node supercomputers / cloud. The overhead is negligible when you can employ 10.000 cores.

Actually the overhead crushes you when you employ 10000 cores. If the overhead of a process is 10% and the parallel part is 90%, then 2 cores will result in a run time of 55% = 10% + 90%/2 of the original time. And 10 cores will get you to 19%. And 100 cores to 10.9%. If you then buy 9900 more cores to bring it to a total of 10000, you just reduced the runtime from 10.9% to 10.009%. In other words, you increased your bill by a factor of 100 to reduce your run time by almost nothing.

Re: The radix 2^51 trick (2017)

#37

Post by volemo »

repelsteeltje wrote: post #13
nine_k wrote: post #9

The 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)

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.

Re: The radix 2^51 trick (2017)

#38

Post by volemo »

credit_guy wrote: post #36
rollcat wrote: post #24

Earlier quoted context omitted.

This rule scales up all the way to multi-node supercomputers / cloud. The overhead is negligible when you can employ 10.000 cores.

Actually the overhead crushes you when you employ 10000 cores. If the overhead of a process is 10% and the parallel part is 90%, then 2 cores will result in a run time of 55% = 10% + 90%/2 of the original time. And 10 cores will get you to 19%. And 100 cores to 10.9%. If you then buy 9900 more cores to bring it to a total of 10000, you just reduced the runtime from 10.9% to 10.009%. In other words, you increased your…

You two are talking about different kinds of overhead though.

Re: The radix 2^51 trick (2017)

#39

Post by yusina »

animal531 wrote: post #31
russdill wrote: post #3

I'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.

CPU's are really funny and interesting things. Us programmers work with them daily and make so many assumptions about them, as well as the whole code chain from the compiler, runtimes, how code works when it comes to loops, methods etc., you name it. I've been working on my own Entity Component System in C# and basically had to start from the ground up and test every assumption possible. There have only really been a…

It's because they are providing abstractions which we/the compilers use, but just doing that would be too slow, so they implement optimizations, but those are based on certain assumptions, so then the users adjust what they do to match those assumptions well, so the optimizations have now leaked into the API, and after many rounds of doing this for decades, you end up with this terrible mess we are in.

Re: The radix 2^51 trick (2017)

#40

Post by vitus »

volemo wrote: post #35
Sukera wrote: post #28

Earlier quoted context omitted.

Because adding the top limbs of two encoded numbers would overflow too soon. If you set both to 2^63 for example, they overflow immediately. Might be fine for wraparound arithmetic, but not in general.

Setting both to 2^63 means your original 256-bit numbers were 2^255, thus the addition would overflow no matter what intermediate encoding you’re using.

Sure, then set one to 2^62 and the other to -2^62 (namely: 0b1100..00). It's overflow as far as unsigned arithmetic is concerned, but not in the case of signed arithmetic.

That said, when you're dealing with 256-bit integers, you're almost assuredly not working with signed arithmetic.

Post reply on HN