7 ms·
Why would useless MOV instructions speed up a tight loop in x86_64 assembly?
- incision 13y agoInteresting, relevant paper mentioned in response to the linked SO question: MAO - an Extensible Micro-Architectural Optimizer - http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/37077.pdf http://static.googleusercontent.com/external_content/untrust...
- kilowatt 13y agoThere are figures on page 6 that answer the OP's question directly. And there's also this money quote: "Building an accurate model for modern processors is virtually impossible."
- rayiner 13y agoA good way to test that would be to insert NOP's of the right length in place of the MOV to see if its an alignment or predictor line sharing issue.
- PuercoPop 13y agoVery interesting indeed. In particular: "we find that most performance results stay flat, in particular for the Nop Killer pass (NOPKILL), which leads to the conclusion that most alignment directives are not helping"
- rayiner 13y agoThis is Core 2, so it still has the P6's micro architectural limitation that it can only read two (or three?) values from the register files each cycle. But it's a 4-way processor, so it can potentially need up to 8 operands. If the other operands are on the bypass networks, it's fine. If not, then the CPU stalls. My guess would be that the MOV has the effect of keeping an operand on the bypass network long enough to avoid a stall. Totally guessing, though, but that might explain why it's so sensitive to instruction ordering.
- Filligree 13y agoSorry, what's a bypass network in this context?
- rayiner 13y agoThe outputs and inputs of execution units are connected by busses that allow results to be communicated directly to dependent instructions without being written to the register file.
- Filligree 13y agoI see.. well, it makes sense to build something like that. 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).
- jleader 13y agoThe last time I got my hands dirty at this level was almost 20 years ago, optimizing a software renderer's texture mapping code for the original Pentium, so I don't know much about the details these days, but it sounds like the MOV would touch the data item, which might keep it from getting aged out of the cache-like thing in question (ETA: "bypass network"), so it would still be available when it was actually needed a few instructions later. 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.
- rayiner 13y agoI don't remember the exact way it works on Core 2, but generally a NOP is thrown out very early in the pipeline. So it won't usually have an effect on the execution order of other instructions. But a MOV has source operands (address), and produces an output value. It'll sit in the issue queues until its inputs are available, and in doing so it might cause some other instructions to execute in a different order. If that pushes two other dependent instructions closer together, that might avoid a stall. 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.
- conductor 13y agoSorry for the off topic discussion, but I would like to give some attention to FreePascal. In my opinion, it is a great piece of software, and is so underrated. If you find C/C++ too error-prone or hard to learn, Object Pascal is a very good alternative. FreePascal is a multi-platform, Delphi compatibe Object Pascal compiler, can generates pretty optimized native code for multiple architectures (including ARM) and has plenty of libraries. If you already hadn't, please give Lazarus[1] a try, it's a nice RAD IDE (very similar to Borland Delphi 7) shipped with the FreePascal compiler. [1] - http://lazarus.freepascal.org http://lazarus.freepascal.org
- dom96 13y agoIf I may also use this opportunity to advertise a Pascal-like language, as it is also severely underrated. The language's name is Nimrod [1], it compiles to C so it is also very portable, uses whitespace to delimit blocks, is statically typed with generics and has great support for metaprogramming. I am developing an IDE for it called Aporia [2], it is written in Nimrod, it definitely doesn't have as many features as Lazarus but it works well as a simple editor. Other nimrod projects can be found in the nimrod-code organisation on github[3]. [1] - http://nimrod-code.org http://nimrod-code.org [2] - https://github.com/nimrod-code/aporia https://github.com/nimrod-code/aporia [3] - https://github.com/nimrod-code/ https://github.com/nimrod-code/
- X4 13y agoDoes it require a runtime? I mean can I develop an OS with it, without shipping the runtime? What language do you know, where that is possible?
- pbsd 13y agoThe code keeps using high registers for no discernible reason, instead of sticking with EAX--EDI; this means that each instruction is 1 byte longer than it could be. 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.
- nkurz 13y agoThe code keeps using high registers for no discernible reason 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_mjw.pas https://github.com/tangentstorm/coinops/blob/junkops/sha256_...
- rogerbinns 13y agoI highly recommend the Stanford EE380 video "Things CPU Architects Need To Think About". Even though it is from 2004, much of the material is still relevant. Bob Colwell notes that they had similar unexpected throughput slowdowns when implementing the P6 and Netburst processor cores, and discovered that adding random delays cleared them out. The cause for throughput hiccups could be traced back, sometimes hundreds or thousands of instructions, but were extremely difficult to address. They also found that manufacturing assembly lines had similar problems that were also addresses by adding delay. http://www.stanford.edu/class/ee380/ay0304.html http://www.stanford.edu/class/ee380/ay0304.html (18 Feb 2004, site appears to be having issues at the moment)
- zwegner 13y agoThanks for the link! Looks interesting. Here's an alternative link, that actually works: http://lang.stanford.edu/courses/ee380/2003-2004/040218-ee380-100.wmv http://lang.stanford.edu/courses/ee380/2003-2004/040218-ee38...
- acqq 13y agoIt's such a good talk. There's even the point where he almost says "we're sorry" regarding Pentium 4, at the time where a lot of people still believed Intel's marketing that it's "the best." I understood him, as the application I worked on at the time was significantly faster on the Pentium M than on the Pentium 4.
- rogerbinns 13y agoI also love the bit about the floating point divide non-optimisation, and how it turned into a success.
- monistowl 13y agoI don't know, but I blame the NSA.
- raymondh 13y agoAdding a MOV shifts subsequent instructions and can relieve deleterious aliasing in the branch prediction buffer. Here's a full explanation (with references and links to the diagnostic tools): http://stackoverflow.com/a/17906589/1001643 http://stackoverflow.com/a/17906589/1001643
- mistercow 13y agoI'm not sure that I'm buying that a 0.7% time difference is anything other than noise after only 25 runs.
- rwallace 13y agoIn my experience the timing jitter on a general-purpose PC - the typical difference between runs of the same code on the same data - is in the ballpark of a couple of percent (and no, back-to-back runs aren't fully independent of each other so you can't average it out over a couple of dozen runs). 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.
- Havoc 13y agoFrom the stackoverflow page: >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.
- ryen 13y agoShouldn't something like this be measured using #CPU ops per CPU-time instead of just 'seconds'?
- DannyBee 13y agoThe answer can be one of a billion reasons: dependency chain breaking, register renaming deficiencies, alias breaking, etc. 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.