3 ms·

Could you explain your reasoning? I would think that bounds and overflowing checking should have fantastic performance on modern processors. The almost-always

by nkurz 8y ago

Could you explain your reasoning? I would think that bounds and overflowing checking should have fantastic performance on modern processors. The almost-always-false test gets correctly predicted as false, speculative execution chooses the correct branch without delay, and a few cycles later (but without visible delay) some simple math confirms that the correct branch was chosen. In my mind, the hardware support is already there and almost perfect; it's the languages and compilers that are lagging. But maybe I'm missing something obvious. Where do you think the issue is?

bsder 8y ago
> he almost-always-false test gets correctly predicted as false, speculative execution chooses the correct branch without delay, and a few cycles later (but without visible delay) some simple math confirms that the correct branch was chosen. So, why don't compilers do this already? Nothing stops them. The answer is that they lose a ton of performance. There is a lot of housekeeping in order to keep track of speculative execution and it happens on every single mathematical operation in your regime. And you pay that continually for an operation that happens "very rarely" as you point out. Overflow/underflow probably isn't so bad, but array bounds checks are very bad. You have at least one bound that is variable and so causes an extra "Compare to X" where X is a non-zero constant and so needs to be loaded. So your tight loops all look like "increment I; compare I to 0; compare I to X; do real work" That's two extra instructions that the speculative execution system has to keep track of every loop and it eats a lot of the speculative execution resources very quickly. An in-order chip like the 21164 doesn't execute the loops any faster, but it doesn't have to pay hardware chip area because of speculative execution. Given that everything is moving to high multi-core, it would be better to let a stuck core give way to another quickly than to try speculate deeper--especially as SSDs continue to increase in speed--and especially because, quite often in a battery operated world, your would rather shut down while waiting. In addition, if you trap on these, it will break an enormous amount of software in existence. Look at how many people went absolutely ape over gcc suddenly doing aggressive optimizations on undefined behavior. (And, by the way, every microprocessor used to compute underflow on arithmetic instructions (8080, Z80, 6800, etc.), so you need to ask why that went away.)
- 0815test 8y ago
  > ... So your tight loops all look like "increment I; compare I to 0; compare I to X; do real work" ... Compilers are generally smart enough to hoist these comparisons out of the loop, at least in a static, AOT-compiled language like Rust. You're right though that in-order chips are a lot more power-efficient, and the in-order approach is the one that's taken in most RISC-V implementations (which seems to be a highly comparable architecture to the Alpha you mention).
- BeeOnRope 8y ago
  I had a bit of a hard time following your argument, but nkurz is right here in the sense that things like overflow and bounds checks are practically the poster child for things that perform well on wide OoO processors. They are leaves in dependency graph and hence don't add to dependency chains, and on wide designs the ALU op(s) will often execute almost for free. It is in-order designs that take a slightly larger relative penalty since in some sense "all instructions matter" there so bounds checks cost similar to surrounding operations that do real work. You make a lot of valid observation about the cost of actually implementing a modern, deep and wide out of order architecture: it is much harder and uses more silicon that some in-order designs, but once you have it (and largely that's what we have today as general purpose CPUs), the type of branches that are involved in overflow and bounds checks are not costly.

by nkurz 8y ago

bsder 8y ago

> he almost-always-false test gets correctly predicted as false, speculative execution chooses the correct branch without delay, and a few cycles later (but without visible delay) some simple math confirms that the correct branch was chosen. So, why don't compilers do this already? Nothing stops them. The answer is that they lose a ton of performance. There is a lot of housekeeping in order to keep track of speculative execution and it happens on every single mathematical operation in your regime. And you pay that continually for an operation that happens "very rarely" as you point out. Overflow/underflow probably isn't so bad, but array bounds checks are very bad. You have at least one bound that is variable and so causes an extra "Compare to X" where X is a non-zero constant and so needs to be loaded. So your tight loops all look like "increment I; compare I to 0; compare I to X; do real work" That's two extra instructions that the speculative execution system has to keep track of every loop and it eats a lot of the speculative execution resources very quickly. An in-order chip like the 21164 doesn't execute the loops any faster, but it doesn't have to pay hardware chip area because of speculative execution. Given that everything is moving to high multi-core, it would be better to let a stuck core give way to another quickly than to try speculate deeper--especially as SSDs continue to increase in speed--and especially because, quite often in a battery operated world, your would rather shut down while waiting. In addition, if you trap on these, it will break an enormous amount of software in existence. Look at how many people went absolutely ape over gcc suddenly doing aggressive optimizations on undefined behavior. (And, by the way, every microprocessor used to compute underflow on arithmetic instructions (8080, Z80, 6800, etc.), so you need to ask why that went away.)

0815test 8y ago
> ... So your tight loops all look like "increment I; compare I to 0; compare I to X; do real work" ... Compilers are generally smart enough to hoist these comparisons out of the loop, at least in a static, AOT-compiled language like Rust. You're right though that in-order chips are a lot more power-efficient, and the in-order approach is the one that's taken in most RISC-V implementations (which seems to be a highly comparable architecture to the Alpha you mention).
BeeOnRope 8y ago
I had a bit of a hard time following your argument, but nkurz is right here in the sense that things like overflow and bounds checks are practically the poster child for things that perform well on wide OoO processors. They are leaves in dependency graph and hence don't add to dependency chains, and on wide designs the ALU op(s) will often execute almost for free. It is in-order designs that take a slightly larger relative penalty since in some sense "all instructions matter" there so bounds checks cost similar to surrounding operations that do real work. You make a lot of valid observation about the cost of actually implementing a modern, deep and wide out of order architecture: it is much harder and uses more silicon that some in-order designs, but once you have it (and largely that's what we have today as general purpose CPUs), the type of branches that are involved in overflow and bounds checks are not costly.