Why would useless MOV instructions speed up a tight loop in x86_64 assembly?
github.com
github.com
What's the source for your claim that the Core uarch's register file is underdesigned in comparison to the dispatch width? I'd be extremely surprised if this were the case. Last time I looked at the data, about 50-70% of the reads go to the register file not the bypass network.
Intel's optimization manual describes the stall: http://www.intel.com/content/dam/doc/manual/64-ia-32-archite... (3.5.2.1, "ROB Read Port Stalls.").
The optimization manual mentions examples of the stall occurring when e.g. often-used constants are stored in registers, or when a load is hoisted "too high" and the value "goes cold" before its consumers use it.
Agner Fog's manual has a discussion starting on p. 69, 84 of his manual: http://www.agner.org/optimize/microarchitecture.pdf. Note his use of an unnecessary MOV to "refresh" a register to avoid the stall.
I only glanced at the code quickly, but the comment about how he got rid of a load by holding a value in a register made me think the load was keeping the value from "going cold." Of course, I didn't profile it so I'm probably completely wrong...
In designs which rename using the ROB, the register file holds values produced by instructions which are completed and retired, the ROB holds values from instructions that are completed but not retired, and the bypass network supplies values from instructions currently completing.
What Agner is doing in his example with the seemingly useless instruction is transferring a value from the the register file to the ROB so that instructions which try to read logical register ECX will now source it from the ROB instead of the register file. But when I look at the code in the stack overflow question, nothing actually reads from s1. So these are even "more useless" instructions than Agner's example.
Some people have already mentioned instruction alignment issues, so that is one likely explanation. There are a whole bunch of other possible issues involving the scheduler and dispatch restrictions. For example, I've seen processors where there were two pipelines with slightly different instruction schedulers. So adding a useless instruction like this might push your bottleneck instruction into a pipe with a scheduler that is slightly better for your code. Sometimes bypassing across different pipes is more expensive than within the same pipe, so again the useless instruction might push some instructions into pipes that have more of their sources. It could one of any number of reasons and it's going to be very hard to tell from the outside without knowing the details of the microarchitecture.
I still don't understand why a pointless mov instruction is superior to a nop, though, or why a stall differs from a nop (assuming it does).
As I said, I'm just guessing. But Core 2 has several architectural quirks that can make it sensitive to things like this. Most are things where a useless instruction would not affect things (each reading a 32 bit register after writing the lower 16 bits of it), but this one is such that a useless instruction could trigger or avoid it.
Could also be something more mundane, like the load kicking off the prefetcher for a value that's later needed. As I said, I'm throwing out ideas. Someone needs to test.
A stall can last several clock cycles, potentially quite a bit longer than a NOP.
In the code I worked on, rearranging the order of MOV instructions made the inner loop execute twice as fast, just by avoiding stalls. I think at one point I added a NOP to avoid a stall, but I don't remember if it survived into the final version of the code.
r8d/r9d are used "a lot" so it may have something to do with dependencies between steps, especially from end of the loop to the beginning (if I understood correctly)
They need to freeze development and go look at the documentation for python, perl, racket or a whole host of other languages.
https://github.com/tangentstorm/coinops/blob/junkops/sha256_...
This junkops branch contains an experiment that shows how adding useless junk operations (moving the contents of an arbitrary register into ram) can increase the speed of the executed code."
[1] - http://nimrod-code.org
http://www.stanford.edu/class/ee380/ay0304.html (18 Feb 2004, site appears to be having issues at the moment)
Here's an alternative link, that actually works: http://lang.stanford.edu/courses/ee380/2003-2004/040218-ee38...
MAO - an Extensible Micro-Architectural Optimizer - http://static.googleusercontent.com/external_content/untrust...
This has consequences to the instruction fetching and decoding circuitry, where (in the Core 2) you can only read 16 instruction bytes per cycle (or 6 instructions). It is possible that the extraneous MOV instructions are just resulting in a better instruction alignment.
The function[1] inside of which the assembly is located declares a lot of variables as well. I don't know how well Free Pascal does register allocation, but perhaps this avoid clobbering the registers it prefers. Alignment seems like a likely candidate, but isn't likely to explain why the exact ordering of the extra ops makes a difference.
Would help to see the assembly for the whole function.
[1] https://github.com/tangentstorm/coinops/blob/junkops/sha256_...
Here's a full explanation (with references and links to the diagnostic tools): http://stackoverflow.com/a/17906589/1001643
First step needs to be the hardware performance counters. Usually it will tell you something interesting, but leave you scratching your head.
Then you find a friend at intel, who laughs, and explains some wildly esoteric detail of the core2 processor that causes this.
This is why scheduling and register allocation models in compilers don't bother with ILP based modeling for x86 processors. Even if you modeled the externally published architecture perfectly, including port restrictions, decode lengths, branch stalls, cycle counts, register requirements, etc, the processor just does whatever it wants internally anyway, because they don't really give you all the details.
The claimed timing difference was less than one percent so while I certainly can't say it wasn't real, I'm not seeing any evidence that it was.
>randomly inserting nop instructions in programs can easily increase performance by 5% or more, and no, compilers cannot easily exploit this.
Could someone please help me understand why this isn't exploitable? Surely one could just tack a module onto the end of the compiler that bruteforces this? Or something like a genetic algo to trial & error it.