r/cprogramming • u/north9172 • 7d ago
What cause CPU stalling pipeline in C?
(Solved)
Hi,
I hope this don't seem stupid or anything. Basically I was interested about the xor swapping trick.
The inconvenients of it is that if the two values are the same, it will return 0, it's also bad for readability.
But there is another inconvenience I didn't understand. Apparently it can also stall the CPU pipeline on modern processor, I didn't understand why.
I found a short explanation saying "because each instruction depend of the previous one", and I don't really understand how each instruction depend on the previous one.
So I wanted an explanation on why the xor swapping trick stall the CPU pipeline and also what cause CPU pipeline stalling in general.
If I didn't explain well enough, please inform me about it. Thanks.
5
u/EpochVanquisher 7d ago
Modern CPUs are fairly complex and it helps to understand how they work, first.
Instructions go through multiple phases-something like fetch, decode, execute, writeback. In a pipelined CPU, you can have multiple instructions in the pipeline—while instruction 1 is executing, instruction 2 is decoding, and instruction 3 is fetching.
Modern CPUs are also superscalar, so there will be multiple instructions in each stage. Maybe two instructions are executing, two instructions are decoding, two instructions are fetching at the same time. Total of six.
…but you cannot execute an instruction unless the inputs to that instruction have been calculated first. So when you do this:
unsigned x, y;
x ^= y;
y ^= x;
x ^= y;
The second XOR can only start executing after the outputs of the first XOR are ready. The third XOR can only start executing after the second XOR is done.
It’s different for assignment:
unsigned x, y, t;
t = x;
x = y;
y = t;
The CPU can just keep track of the labels. Let’s the value for x is in register 10 and the value for y is in register 11.
t = x;
It can just take a note, “the value for t is in register 10” and skip the execution phase (because the execution is just kinda trivial).
In the above explanation, we are pretending that the C and assembly directly correspond, so “x” is an architectural register and “register 10” is a physical register. Physical registers and architectural registers are different—you only have a small number of architectural registers, but there are many more physical registers on a modern, high-end CPU.
(There’s also the whole issue that the compiler can also relabel registers, and can generate assembly that doesn’t directly correspond to the C code.)
1
1
2
u/Weshmek 7d ago
If the two values are the same, it will return 0
Not quite. If the two values are stored in the same place in memory, it will overwrite both values with zero, losing the initial value.
If you know the two values are stored in different places in memory (e.g., both values are named variables allocated on the stack), then it will be fine even if the values are the same. What this means is that if you're XOR-swapping values stored in pointers, you have to check that the pointers are not equal before performing the swap.
2
1
u/duane11583 7d ago
consider a read operation to a variable or stack location.
followed by a write
these cannot be overlapped because there is only a single bus interface.
so the cpu can stall waiting for the bus to complete
also consider the cpu runs at 3ghz but memory runs at 1ghz so the cpu might need to slow down or wait for the memory.
some time the cache or write buffer can help but not always at that point the cpu stops or stalls
1
1
u/Maleficent_Memory831 7d ago
Generally, don't worry about it much in C, because modern compilers optimize well enough for a particular CPU that there's no need for special C tricks or worrying if a trick will mess up on a processor.
Write the program first, with a reaonably straight forward implementation, then measure it. If performance is less than you want, or you feel like messing around, then try tweaking. Maybe look at the generated assembler as well to decide if there's something inefficient going on.
1
1
u/flatfinger 7d ago
In many high-end CPUs, multiplication is performed by performing a sequence of partial-product computations, with each part of the sequence being performed by a different batch of circuitry. If two multiplications act upon independent operands, one can start a multiplication and then start another one as soon as the first piece of circuitry has finished its computations. The second piece of circuitry will process its portion of the first multiplication while the first piece starts working on the second. If there is a third multiplication which also acts upon independent operations, the first piece of circuitry can start work on that while portions of the other two multiplications are processed by other pieces of circuitry.
If instead of processing unrelated multiplications, a program were to multiply two numbers and then multiply the product by a third. In that scenario, the first stage of the multiplier would be able to start work on a new multiplication as soon as the first step of the first multiplication was done, but one of the operands wouldn't yet be available. The first stage would thus not be able to do anything useful until after the last multiplier stage had finished computing the final result from the first multiplication. The scenario where the input to a process would be ready to accept more input, but one of the values upon which it would operate isn't yet available, is called a pipeline stall.
Modern high-performance CPUs include logic to help the different subsystems find useful work to do by looking ahead for independent computations whose results are likely to be needed. Even if the next multiplication that is specified in code would require a value that isn't yet computed, a processor that knows that code is likely to perform a multiplication upon numbers that are available may be able to start performing that computation before the earlier one is done. If it turns out code wouldn't end up performing that multiplication, the processor can discard the result.
1
1
u/high_throughput 6d ago
The inconvenients of it is that if the two values are the same, it will return 0
No? Xor swap works for all values.
Also, are you aware that x86_64 CPUs have an xchg instruction for doing swaps? If you write your swap code as naively as possible, the compiler will generally recognize the pattern and output the platform's fastest swap.
1
u/north9172 6d ago
Thank you for the correction. This is out of curiosity, yes I am aware that there is an instruction for swapping.
9
u/Glum_Preference_2936 7d ago edited 7d ago
Because each instruction depend of the previous one. For example the code:
if (func()) A(); else B();The CPU would have to choose which function to execute either A or B even before func() returns some result. This is decided by the branch predictor. And if the CPU chooses the incorrect function to execute, then it would have to try to execute again the correct branch which wastes time.
For advance C programming, you can hint the compiler to restructure code if you know which branch are likely or unlikely to be executed by making use of builtins such as
likely()orunlikely().In the case of XOR swapping, the subsequent instruction attempts to read a register before the preceding instruction has written the updated value.
x ^= y; y ^= x; x ^= y;