17

While stepping through some Qt code I came across the following. The function QMainWindowLayout::invalidate() has the following implementation:

void QMainWindowLayout::invalidate()
{
QLayout::invalidate()
minSize = szHint = QSize();
}

It is compiled to this:

<invalidate()>        push   %rbx
<invalidate()+1>      mov    %rdi,%rbx
<invalidate()+4>      callq  0x7ffff4fd9090 <QLayout::invalidate()>
<invalidate()+9>      movl   $0xffffffff,0x564(%rbx)
<invalidate()+19>     movl   $0xffffffff,0x568(%rbx)
<invalidate()+29>     mov    0x564(%rbx),%rax
<invalidate()+36>     mov    %rax,0x56c(%rbx)
<invalidate()+43>     pop    %rbx
<invalidate()+44>     retq

The assembly from invalidate+9 to invalidate+36 seems stupid. First the code writes -1 to %rbx+0x564 and %rbx+0x568, but then it loads that -1 from %rbx+0x564 back into a register just to write it out to %rbx+0x56c. This seems like something the compiler should easily be able to optimize into just another move immediate.

So is this stupid code (and if so, why wouldn't the compiler optimize it?) or is this somehow very clever and faster than using just another move immediate?

(Note: This code is from the normal release library build shipped by ubuntu, so it was presumably compiled by GCC in optimize mode. The minSize and szHint variables are normal variables of type QSize.)

Billy ONeal
  • 104,103
  • 58
  • 317
  • 552
JanKanis
  • 6,346
  • 5
  • 38
  • 42
  • 3
    QT is a UI, correct? How many times in succession would you need to invalidate a window? How performant would that actually need to be? The kind of micro-optimization that you are describing is almost certainly not worth the effort for the minimal benefit that would accrue. – Robert Harvey May 21 '13 at 20:45
  • It seems suboptimal indeed, maybe the peephole optimizer just didn't get this. –  May 21 '13 at 20:45
  • 11
    @RobertHarvey But that's not the point here - OP isn't trying to optimize, he's trying to understand the reason. –  May 21 '13 at 20:46
  • 4
    QSize() is an object. This is clearly C++ code, not plain C. The constructor for QSize() does something. The assignment operator for QSize() could be doing something else. You need to see the source code for those things. – jxh May 21 '13 at 20:47
  • 4
    Just some small detail: The two mov’s at the end are 64 bit operations, so they load/store BOTH -1’s previously written. Also, from the offsets, it’s evident that the two mov’s take less space (7 bytes each) than the movl’s (10 bytes each), so doing things that way is not entirely without merit. – microtherion May 21 '13 at 20:50
  • Also note that the 64-bit load is actually misaligned. (if we assume that `rbx` is aligned) – Mysticial May 21 '13 at 20:50
  • 1
    Ultimately, the awkwardness of the code might be due to a struct being involved. Compilers always have a harder time dealing with 2 32 bit fields than with one 64 bit scalar. – microtherion May 21 '13 at 20:52
  • @user315052 QSize is an object with two int data members that are initialized to -1. It does not have a copy constructor (other than the compiler-generated one). But that should not matter, by generating this code the compiler shows it already knows that nothing else is going on except for moving some data around. – JanKanis May 21 '13 at 21:00
  • @microtherion: Ah, that may be it. I missed that it was a 64 bit load/store. I guess that makes some sense as it is shorter. – JanKanis May 21 '13 at 21:02
  • Wouldn't the base implementation be seen as a side effect by the compiler? – Captain Obvlious May 21 '13 at 21:07
  • 2
    @Somejan: So, assuming `rbx` holds the `this` pointer, the two `movl`s is initializing one of the two variables via code taken from the inlined constructor, and the other two moves is copying the data into a 64bit register and copying it back into the other variable. – jxh May 21 '13 at 21:17
  • 1
    You are also assuming that the binary shipped with your distribution was compiled with a high level of optimization which might or not be true. – David Rodríguez - dribeas May 21 '13 at 21:21
  • @Mysticial $rbx is 8 byte aligned. So the load/store is not. But it is still within a single cache line, don't know if that matters. – JanKanis May 21 '13 at 21:56
  • user315052: yes. @David Rodríguez: Shipped release code on Ubuntu is normally compiled with optimizations. I can tell from the code I've stepped through a bit that it was optimized. Some functions are inlined which GCC only does at optimization level 2. – JanKanis May 21 '13 at 22:03
  • Is there any `volatile` variable involved? – JimmyB Apr 25 '16 at 15:44

4 Answers4

12

Not sure you're correct when you're saying it's stupid. I think the compiler might be trying to optimize the code size here. There is no 64-bit immediate to memory mov instruction. So the compiler has to generate 2 mov instructions just like it did above. Each of them would be 10 bytes, the 2 moves generated are 14 bytes. It's been written to so there is most likely no memory latency so I do not think you'll take any performance hit here.

Guillaume
  • 2,044
  • 12
  • 11
  • ... and in addition, if you do a `mov ..., (addr)` followed by a `mov (addr),...` then the 2nd is cache-hot, i.e. there's little penalty for it. The only optimization I can think of here would've been `pcmpeq %xmm0, %xmm0; movdqu %xmm0, 0x564(%rbx)` to set the entire 16 bytes to all `0xff..`, but it's a pretty tough ask to "merge" two variables in this fashion - and probably not entirely standards-conformant wrt. to C++ load/store visibility guarantees. – FrankH. May 21 '13 at 21:33
  • 2
    +1 for *"There is no 64-bit immediate to memory mov instruction,"* that's all that needs to be said. – BlueRaja - Danny Pflughoeft May 21 '13 at 21:52
  • I didn't know the part about the no 64 bit move immediate, so that is probably the solution. Additionally, there appears to be no real cost on x86 if an unaligned memory access does not cross cache line boundaries – JanKanis May 21 '13 at 22:09
  • I'm not sure about it... `clang++ -O2` gives the following asm: `movq $0xffffffffffffffff,0x8(%rdi); movq $0xffffffffffffffff,(%rdi);` (well, the code is a bit stripped, hence the different offsets). That's just about 16 bytes. – rodrigo May 21 '13 at 22:15
  • 2
    @GuillaumeMorin: For `movq $0xffffffffffffffff,0x8(%rdi)` it is `48 c7 47 08 ff ff ff ff` and for `movq $0xffffffffffffffff,(%rdi)` it is `48 c7 07 ff ff ff ff`. It looks like it is doing a _move 32-bit literal into 64-bit memory with sign extension_ or something. Smart... – rodrigo May 21 '13 at 22:42
  • Ah, looks like it is the sign extended 32-bit mov - this is not an full 64-bit immediate move. – Guillaume May 21 '13 at 22:42
  • Oops, replied at the same time. So yeah, what I said was true but in this specific case, it looks like it could have been optimized. gcc might not have an optimizer that's smart enough. I still think the gcc code is not stupid but thank you for bringing this up – Guillaume May 21 '13 at 22:44
  • 1
    @GuillaumeMorin: Just for fun, if I change the values of the `QSize()` constructor to `1` so that the sign extension trick will not work, it gives `movabs $0x..., %rax; mov %rax,0x8(%rdi); mov %rax,(%rdi)`. Still shorter than GCC ;-) But I agree that GCC is far from stupid, just that CLang++ has learnt some tricks... – rodrigo May 21 '13 at 22:47
  • I didn't say it was stupid, I was wondering if it was stupid or brilliant. – JanKanis May 21 '13 at 23:15
  • @rodrigo: for other readers: the absolute value clang generates is 0x100000001, so it initializes both fields of the QSize. (That confused me when first reading your comment.) – JanKanis May 21 '13 at 23:54
  • @rodrigo: this is probably what I would have written by hand but note (as Somejan also pointed out) that the 64-bit value is not aligned on a 64-bit boundary in the original ask, while it is aligned in your case – Guillaume May 22 '13 at 01:18
  • @GuillaumeMorin: The alignment is by chance... I've added a padding byte before the `QSize` values and the generated code is similar. x86_64 processors can do with unaligned access just fine. – rodrigo May 22 '13 at 07:30
  • They can do it but it is definitely slower than a mov to an aligned boundary. In particular, I meant that the clang code might not be faster than the gcc one because of non-aligned boundary. Anyway, we're talking a few cycles here and there. I guess I am beating a dead horse – Guillaume May 22 '13 at 12:28
8

The code is "less than perfect".

For code size, those 4 instructions add up to 34 bytes. A much smaller sequence (19 bytes) is possible:

00000000  31C0              xor eax,eax
00000002  48F7D0            not rax
00000005  48898364050000    mov [rbx+0x564],rax
0000000C  4889836C050000    mov [rbx+0x56c],rax

;Note: XOR above clears RAX due to zero extension

For performance things aren't so simple. The CPU wants to do many instructions at the same time, and the code above breaks that. For example:

xor eax,eax
not rax                 ;Must wait until previous instruction finishes
mov [rbx+0x564],rax     ;Must wait until previous instruction finishes
mov [rbx+0x56c],rax     ;Must wait until "not" finishes

For performance you want to do this:

00000000  48C7C0FFFFFFFF        mov rax,0xffffffff
00000007  C78364050000FFFFFFFF  mov dword [rbx+0x564],0xffffffff
00000011  C78368050000FFFFFFFF  mov dword [rbx+0x568],0xffffffff
0000001B  C7836C050000FFFFFFFF  mov dword [rbx+0x56c],0xffffffff
00000025  C78370050000FFFFFFFF  mov dword [rbx+0x570],0xffffffff

;Note: first MOV sets RAX to 0xFFFFFFFFFFFFFFFF due to sign extension

This allows all of the instructions to be executed in parallel, with no dependencies anywhere. Sadly, it's also much larger (45 bytes).

If you try to get a balance between code size and performance; then you could hope that the first instruction (that sets the value in RAX) completes before the last instruction/s needs to know the value in RAX. This might be something like this:

mov rax,-1
mov dword [rbx+0x564],0xffffffff
mov dword [rbx+0x568],0xffffffff
mov dword [rbx+0x56c],rax

This is 34 bytes (the same size as the original code). This is likely to be a good compromise between code size and performance.

Now; let's look at the original code and see why it is bad:

mov dword [rbx+0x564],0xffffffff
mov dword [rbx+0x568],0xffffffff
mov rax,[rbx+0x564]                ;Massive problem
mov [rbx+0x56C],rax                ;Depends on previous instruction

Modern CPUs do have something called "store forwarding", where writes are stored in a buffer and future reads can get the value from this buffer to avoid reading the value from cache. Ironically, this only works if the size of the read is smaller than or equal to the size of the write. The "store forwarding" will not work for this code as there are 2 writes and the read is larger than both of them. This means that the third instruction has to wait until the first 2 instructions have written to cache and then has to read the value from cache; which could easily add up to a penalty of about 30 cycles or more. Then the fourth instruction must wait for the third instruction (and can't happen in parallel with anything) so that's another problem.

Brendan
  • 35,656
  • 2
  • 39
  • 66
  • +1 for using intel syntax. Quick question, the original code has `mov [rbx+0x56C],rax` but in your optimized example `mov dword [rbx+0x56C],rax`. Does this mean the original moves 8-bytes(QWORD) into `[rbx+0x56c]` while yours move 4-bytes(DWORD)? Is this intended? – greatwolf May 22 '13 at 02:19
  • 1
    I'd suggest 7-byte `mov rax, -1` then two qword stores as the performance option. Only 3 instructions for the front-end. The `mov`-immediate has no input dependencies so OoO exec can run it as early as it wants. That will normally trump being able to do the first half of one store earlier. Apparently (from epatel's answer) this is a 64-bit object with 2 fields, which explains the missed optimization with then-current GCC. (Store coalescing was re-introduced in GCC7, after being missing since gcc2.95 or gcc3 or something.) Storing the first half of the object isn't necessarily useless, but... – Peter Cordes Jun 17 '19 at 17:11
  • 1
    Optimizing for parallel stores is useless (until IceLake) because CPUs only have one store-data port. The other option would be `pcmpeqd xmm0,xmm0` ; `movups [rbx+0x564], xmm0`, especially if we don't need a value in RAX. Nice and short, the `modrm+disp32` only appears once. And on CPUs after Core2, very efficient to decode / execute unless the store crosses a cache-line boundary. – Peter Cordes Jun 17 '19 at 17:13
  • @PeterCordes: Optimizing for any specific CPU is useless (they all have different characteristics and nobody can guess what the characteristics of future CPUs will be). By identifying a system of "meta-behaviors" (e.g. "any store may be forwarded to any later load", "multiplication will always be at least as expensive as addition", "no instruction can complete until whatever it depends on completes", ...) you can optimize for all possible (past and future) CPUs. – Brendan Jun 17 '19 at 18:26
  • @PeterCordes: The alternative (for assembly language, where you don't have a compiler optimizing specifically for the exact CPU) is to write about 200 versions of all your code (and then find that "Core-i7 4990 with faster RAM" is different to "Core-i7 4990 with slower RAM" and bump that up to several thousand different versions of all your code). – Brendan Jun 17 '19 at 18:32
  • 1
    Yes sure, but we're actually looking at gcc `-mtune=generic` output, so it is appropriate to think about what's optimal across the range of CPUs that were relevant in 2013. Having a data dependency on a `mov`-immediate is unlikely to ever matter much, and the code-size saving is significant enough to outweigh it in any case where the front-end didn't get to this code *before* the back-end is getting around to executing these instructions. – Peter Cordes Jun 17 '19 at 19:10
  • 1
    @Peter is right, I don't think it is worth doing `mov [...],0xfffffff` at all once you have -1 in `rax`. – BeeOnRope Jun 17 '19 at 21:04
  • @BeeOnRope: maybe one day I'll have nothing better to do with my time than spending it on relatively minor/inconsequential piece of an answer that ceased to be relevant almost 6 years ago. If/when that day comes, I'll figure out if Peter was right. – Brendan Jun 17 '19 at 21:42
2

I'd break down the lines as this (think several have comment same steps)

These two lines comes from the inline definition of QSize() http://qt.gitorious.org/qt/qt/blobs/4.7/src/corelib/tools/qsize.h which set each field separately. Also, my guess is that 0x564(%rbx) is the address of szHint which is also set at the same time.

<invalidate()+9>      movl   $0xffffffff,0x564(%rbx)
<invalidate()+19>     movl   $0xffffffff,0x568(%rbx)

These lines are finally setting minSize using 64bit operations because the compiler now know the size of a QSize object. And the address of minSize is 0x56c(%rbx)

<invalidate()+29>     mov    0x564(%rbx),%rax
<invalidate()+36>     mov    %rax,0x56c(%rbx)

Note. First part is setting two separate fields, and next part is copying a QSize object (regardless content). The question then is, should the compiler be smart enough to build a compound 64bit value because it saw preset values just earlier? Not sure about that...

epatel
  • 45,805
  • 17
  • 110
  • 144
  • 2
    Yes, compilers are generally able to do these kind of optimizations. It's known as constant folding. – JanKanis May 21 '13 at 22:08
1

In addition to Guillaume's answer, the 64 bit load/store is not aligned. But according to the Intel optimization guide (p 3-62)

Misaligned data access can incur significant performance penalties. This is particularly true for cache line splits. The size of a cache line is 64 bytes in the Pentium 4 and other recent Intel processors, including processors based on Intel Core microarchitecture.

An access to data unaligned on 64-byte boundary leads to two memory accesses and requires several μops to be executed (instead of one). Accesses that span 64-byte boundaries are likely to incur a large performance penalty, the cost of each stall generally are greater on machines with longer pipelines.

Which imo implies that an unaligned load/store that does not cross a cache line boundary is cheap. In this case the base pointer in the process I was debugging was 0x10f9bb0, so the two variables are 20 and 28 bytes into the cacheline.

Normally Intel processors use store to load forwarding, so a load of a value that was just stored doesn't even need to touch the cache. But the same guide also states that a large load of several smaller stores does not store-load-forward but stalls: (p 3-66, p 3-68)

Assembly/Compiler Coding Rule 49. (H impact, M generality) The data of a load which is forwarded from a store must be completely contained within the store data.

; A. Large load stall
mov     mem, eax        ; Store dword to address “MEM"
mov     mem + 4, ebx    ; Store dword to address “MEM + 4"
fld     mem             ; Load qword at address “MEM", stalls

So the code in question probably causes a stall, and therefore I'm inclined to believe it is not optimal. I wouldn't be very surprised if GCC does not take such limitations fully into account. Does anyone know if/how much modelling of store-to-load forwarding limitations GCC does?

EDIT: some experimenting with adding filler values before the minSize/szHint fields shows that GCC does not care at all where the cache line boundaries are, and neither does clang.

JanKanis
  • 6,346
  • 5
  • 38
  • 42