3 ms·

Perhaps this is layman's understanding, but afaik all CPU operations are only done on registers, so any variable has to be moved to registers when it's operated

Perhaps this is layman's understanding, but afaik all CPU operations are only done on registers, so any variable has to be moved to registers when it's operated on (or are some operations possible on memory without going to registers?) and so the answer to "which variables" would be "all of them". Or is the question about which variables are kept in registers for a bit longer time even while they're not actively being computed on right now?

noelwelsh 2y ago
That's not 100% correct but it's correct enough to give sufficient intuition to understand the problem.
yubblegum 2y ago
It's basically a caching problem. Unloading variables and saving them and loading another one because it is needed for a compuation takes time. So you want to minimize that, just like with a cache. Now a compiler has an advantage over a pure cache in that it actually gets to read the code and so knows the exact number of variables and when they get used! whereas with a pure cache it has to be an oracle :) so, a compiler can try and optimize the cache placements (register assignments) ahead of time by analyzing the code. That's where these algorithms come into play. So knowing nothing we can safely guess that all compiler algorithms must be beating something simple like an LRU ..
cesarb 2y ago
> Perhaps this is layman's understanding, but afaik all CPU operations are only done on registers, so any variable has to be moved to registers when it's operated on From the CPU point of view, yes, but many instructions set architectures (including the very common x86 family) have instructions in which one of the operands can be either a register or a memory location. When it's a memory location, the CPU will load it into an internal register, do the operation there, and write it back to memory if it's the destination operand; but from the point of view of the compiler, the CPU is operating directly on memory. > (or are some operations possible on memory without going to registers?) Some atomic memory operations (like atomic compare and exchange) can be thought of as being done directly on memory (or on the cache which sits above the memory). Some CPUs might even implement it that way (by having an "atomic memory operation" command between the CPU and the cache, instead of doing the operation on the CPU).
mystified5016 2y ago
It extremely depends on the target CPU. Some CPUs do have instructions that operate on RAM directly, no register required. However, the tradeoff is that RAM is almost always 2-4 times slower than writing to registers. Most of the time it's more efficient to copy from RAM to a register and back. Most CPUs are designed to operate on registers, but it's not too uncommon to see simple things like incrementing a variable in RAM without an intermediate copy. There might be more, I don't know a lot about x86
WalterBright 2y ago
> all CPU operations are only done on registers Not correct for the X86_64, such as: INC EA https://www.felixcloutier.com/x86/inc https://www.felixcloutier.com/x86/inc
- cyco130 2y ago
  Even 6502 from 1975 has it (and a few more like shift/rotate instructions).

noelwelsh 2y ago

That's not 100% correct but it's correct enough to give sufficient intuition to understand the problem.

yubblegum 2y ago

It's basically a caching problem. Unloading variables and saving them and loading another one because it is needed for a compuation takes time. So you want to minimize that, just like with a cache. Now a compiler has an advantage over a pure cache in that it actually gets to read the code and so knows the exact number of variables and when they get used! whereas with a pure cache it has to be an oracle :) so, a compiler can try and optimize the cache placements (register assignments) ahead of time by analyzing the code. That's where these algorithms come into play. So knowing nothing we can safely guess that all compiler algorithms must be beating something simple like an LRU ..

cesarb 2y ago

> Perhaps this is layman's understanding, but afaik all CPU operations are only done on registers, so any variable has to be moved to registers when it's operated on From the CPU point of view, yes, but many instructions set architectures (including the very common x86 family) have instructions in which one of the operands can be either a register or a memory location. When it's a memory location, the CPU will load it into an internal register, do the operation there, and write it back to memory if it's the destination operand; but from the point of view of the compiler, the CPU is operating directly on memory. > (or are some operations possible on memory without going to registers?) Some atomic memory operations (like atomic compare and exchange) can be thought of as being done directly on memory (or on the cache which sits above the memory). Some CPUs might even implement it that way (by having an "atomic memory operation" command between the CPU and the cache, instead of doing the operation on the CPU).

mystified5016 2y ago

It extremely depends on the target CPU. Some CPUs do have instructions that operate on RAM directly, no register required. However, the tradeoff is that RAM is almost always 2-4 times slower than writing to registers. Most of the time it's more efficient to copy from RAM to a register and back. Most CPUs are designed to operate on registers, but it's not too uncommon to see simple things like incrementing a variable in RAM without an intermediate copy. There might be more, I don't know a lot about x86

WalterBright 2y ago

> all CPU operations are only done on registers Not correct for the X86_64, such as: INC EA https://www.felixcloutier.com/x86/inc https://www.felixcloutier.com/x86/inc

cyco130 2y ago
Even 6502 from 1975 has it (and a few more like shift/rotate instructions).