5 ms·

Secrets of dispatch_once; x86 performance trickery

107 points by mattgodbolt 12y ago

quotemstr 12y ago
Relying on an implementation detail of the cpuid instruction seems like a very bad idea. It'd be safer, I think, and just as fast, to initially use the atomic version of the code, then NOP out the LOCK prefix once initialization is complete.
- jsnell 12y ago
  That can't possibly work. There's just one dispatch_one function but many callsites, and for each callsite you could have multiple distinct predicates.
  - quotemstr 12y ago
    You'd allocate a trampoline for each predicate, jump unconditionally into that, then jump unconditionally back to mainline code. Each trampoline can be modifier individually. Of course that doesn't work with the current dispatch_once API, though.
    - mikeash 12y ago
      Doesn't this have all the same problems as the way they currently do it? The only difference between the two is that Apple's implementation puts the flag in a variable, while you're basically proposing to put the flag in code. You still need to ensure proper ordering on both reads and writes and ensure that speculative execution doesn't end up giving you the wrong answer.
- mikeash 12y ago
  The rules are different when you're an OS vendor who makes all of the hardware that the OS officially supports. It would be a bad idea for you or I, but for Apple there's no problem. If Intel ever ships a CPU that needs something else, then Apple can update their code for the OS release that goes out on the corresponding Macs.
- adamjernst 12y ago
  Requires writing to executable pages, which iOS doesn't have.
  - MichaelGG 12y ago
    iOS doesn't have x86 processors either, does it?
    - paxswill 12y ago
      Unless I'm mistaken, the simulator is an x86 implementation of iOS.
- userbinator 12y ago
  Intel specifies CPUID to be serialising, this is unlikely to change in the future.
  - cfallin 12y ago
    It's actually part of the architectural definition, so Intel could not change this without breaking ISA compatibility. And they take x86 compatibility very seriously!
userbinator 12y ago
What I would do is have dispatch_once NOP out the call instruction that called it as one of its first operations. Inside, an atomic exchange + compare on the predicate to stop any other threads that slipped past the call, and that's all there is to it. CPUs are optimised for executing NOPs since they're so commonly used for alignment, so the only thing this costs is fetch bandwidth. Here's a quick x86 implementation PoC off the top of my head: ; assumptions: ; * this function is called via a 2-byte call instruction ; * cdecl register allocation ; * [esp] : return addr ; * [esp+4] : predicate ptr ; * [esp+8] : ptr to func() to be called once dispatch_once: pop edx ; edx = block pop ecx ; ecx = pred ptr mov eax, 1 xchg eax, [ecx] test eax, eax ; was a different thread here before us? jnz dispatch_done mov eax, [esp] ; return address mov [eax-2], word 0x9090 ; overwrite the call jmp edx ; execute the block +return dispatch_done: ret As the saying goes, "The fastest way to do something is to not do it at all." In this case, the compare + function call can be completely eliminated after the first time.
- MichaelGG 12y ago
  This is used in JITs, too - is there a reason why the author wouldn't cover it? Other than being "cheating" so to speak? I suppose environments (like game consoles) where you cannot write to executable pages?
- mikeash 12y ago
  Even ignoring W^X problems, how do you ensure that the reads and writes of the data are properly ordered with respect to the reads and writes of the code?
  - cfallin 12y ago
    x86 self-modifying code semantics are actually quite strong relative to most other ISAs -- a store to the currently executing code-stream logically takes effect immediately, so you could in theory modify the instruction immediately following the store, and be OK. In other words, instruction memory ordering is exactly as strong as data memory ordering. (That said, self-modifying code is usually a bad idea when performance is concerned, because the CPU must conservatively flush the pipeline when it detects that any store might have modified the raw bytes of any instruction in the pipeline, and might have to conservatively throw away other state -- probably more expensive than whatever other atomic operations we were playing tricks to avoid.)
colin_mccabe 12y ago
The missing element from this explanation (or maybe I missed it?) is that dispatch_once uses atomic instructions (cmpxchg, to be exact), to ensure that even if multiple threads attempt to create the singleton, only one succeeds. The fast path for reads only kicks in after everything else has been tidied up. Another way to do this kind of thing on Linux is to use ELF TLS to have a thread-local variable identifying if the expensive operation has been completed. If the TLS is not there, you can take a mutex and fall back to the slow path.
comex 12y ago
Copying my comment from the post: I don't think the cpuid is actually required, but feel free to tell me that I'm wrong. The comment in dispatch_once talks about systems with weakly ordered memory models like ARM. But x86 has a strongly ordered model: among other things, "any two stores are seen in a consistent order by processors other than those performing the stores" [Intel]. After calling dispatch_once, I expect to see any writes performed by the once routine, but once the store to the dispatch_once_t flag has been observed, this is already guaranteed. The main reordering pitfall in x86 is that reads may be reordered with earlier writes to different locations, but I don't see how that would cause a problem here.
- nkurz 12y ago
  I'm tending to agree with your reasoning, but am reaching a slightly different conclusion: there might be a problem, but if there is, I don't see how 'cpuid' solves it. Like any delay, it reduces the chances that it will occur, but I don't think it provides any guarantee. What is to prevent a process from reading the initial predicate==0 and then being swapped out for thousands of cycles just before the conditional is executed? I presume the solution for this is that the "write side" does CAS before it actually executes the block. But since it's doing this anyway, I don't see how the 'cpuid' is actually helping things. I think the CAS will be doing a read-to-own whether or not it succeeds, and thus it should never see the wrong state. Edit: Looking at the comments in the source through the link that Marat supplied below, I'm now realizing that the (supposed) purpose of the 'cpuid' is not to prevent double execution of the initialization block, but to prevent the process that performs the initialization from pre-reading a data variable that is not yet initialized. Since this isn't necessary on x86, it seems even more likely the 'cpuid' is doing anything useful here.
  - deleted 12y ago
    [deleted]
nkurz 12y ago
Great article! I'm still trying to wrap my head around this, but in the meantime I'll quibble about one tiny throwaway aside: DISPATCH_EXPECT is a macro that tells the compiler to emit code that tells the CPU that the branch where 8predicate is ~0l is the more likely path. This can improve the success of branch prediction, and thus improve performance. While this is what the macro would do on processors that support such code, x86/x64 isn't one of those processors (Itanium was). Instead, it's more important purpose here is to hint to the compiler (not the processor) to lay out the conditional in assembly such that the expected result is on the faster "branch not taken" path. That said, is the actual implementation of the "write side" viewable online?
- Marat_Dukhan 12y ago
  There are hints for taken/non-taken branches in x86. However, the only family to use them was Pentium 4; other processors silently ignore those hints. As for the write side, you'll find it here: https://opensource.apple.com/source/libdispatch/libdispatch-339.90.1/src/once.c https://opensource.apple.com/source/libdispatch/libdispatch-...
  - gsg 12y ago
    Hints are useless, but arranging for cold code to be on a forward branch can be beneficial.
n0rm 12y ago
Can someone link a mirror? I get timeout for some reason.
rossjudson 12y ago
This feels racy, and I'm not sure it will work on multi-node NUMA architectures. It's one thing to delay and hope that your write is visible in the local processor cache; it's another to ensure that write is visible to other processor nodes, when there's no explicit cache coherence rule that says it will be.

107 points by mattgodbolt 12y ago

Relying on an implementation detail of the cpuid instruction seems like a very bad idea. It'd be safer, I think, and just as fast, to initially use the atomic version of the code, then NOP out the LOCK prefix once initialization is complete.

jsnell 12y ago
That can't possibly work. There's just one dispatch_one function but many callsites, and for each callsite you could have multiple distinct predicates.
- quotemstr 12y ago
  You'd allocate a trampoline for each predicate, jump unconditionally into that, then jump unconditionally back to mainline code. Each trampoline can be modifier individually. Of course that doesn't work with the current dispatch_once API, though.
  - mikeash 12y ago
    Doesn't this have all the same problems as the way they currently do it? The only difference between the two is that Apple's implementation puts the flag in a variable, while you're basically proposing to put the flag in code. You still need to ensure proper ordering on both reads and writes and ensure that speculative execution doesn't end up giving you the wrong answer.
mikeash 12y ago
The rules are different when you're an OS vendor who makes all of the hardware that the OS officially supports. It would be a bad idea for you or I, but for Apple there's no problem. If Intel ever ships a CPU that needs something else, then Apple can update their code for the OS release that goes out on the corresponding Macs.
adamjernst 12y ago
Requires writing to executable pages, which iOS doesn't have.
- MichaelGG 12y ago
  iOS doesn't have x86 processors either, does it?
  - paxswill 12y ago
    Unless I'm mistaken, the simulator is an x86 implementation of iOS.
userbinator 12y ago
Intel specifies CPUID to be serialising, this is unlikely to change in the future.
- cfallin 12y ago
  It's actually part of the architectural definition, so Intel could not change this without breaking ISA compatibility. And they take x86 compatibility very seriously!

userbinator 12y ago

What I would do is have dispatch_once NOP out the call instruction that called it as one of its first operations. Inside, an atomic exchange + compare on the predicate to stop any other threads that slipped past the call, and that's all there is to it. CPUs are optimised for executing NOPs since they're so commonly used for alignment, so the only thing this costs is fetch bandwidth. Here's a quick x86 implementation PoC off the top of my head: ; assumptions: ; * this function is called via a 2-byte call instruction ; * cdecl register allocation ; * [esp] : return addr ; * [esp+4] : predicate ptr ; * [esp+8] : ptr to func() to be called once dispatch_once: pop edx ; edx = block pop ecx ; ecx = pred ptr mov eax, 1 xchg eax, [ecx] test eax, eax ; was a different thread here before us? jnz dispatch_done mov eax, [esp] ; return address mov [eax-2], word 0x9090 ; overwrite the call jmp edx ; execute the block +return dispatch_done: ret As the saying goes, "The fastest way to do something is to not do it at all." In this case, the compare + function call can be completely eliminated after the first time.

MichaelGG 12y ago
This is used in JITs, too - is there a reason why the author wouldn't cover it? Other than being "cheating" so to speak? I suppose environments (like game consoles) where you cannot write to executable pages?
mikeash 12y ago
Even ignoring W^X problems, how do you ensure that the reads and writes of the data are properly ordered with respect to the reads and writes of the code?
- cfallin 12y ago
  x86 self-modifying code semantics are actually quite strong relative to most other ISAs -- a store to the currently executing code-stream logically takes effect immediately, so you could in theory modify the instruction immediately following the store, and be OK. In other words, instruction memory ordering is exactly as strong as data memory ordering. (That said, self-modifying code is usually a bad idea when performance is concerned, because the CPU must conservatively flush the pipeline when it detects that any store might have modified the raw bytes of any instruction in the pipeline, and might have to conservatively throw away other state -- probably more expensive than whatever other atomic operations we were playing tricks to avoid.)

colin_mccabe 12y ago

The missing element from this explanation (or maybe I missed it?) is that dispatch_once uses atomic instructions (cmpxchg, to be exact), to ensure that even if multiple threads attempt to create the singleton, only one succeeds. The fast path for reads only kicks in after everything else has been tidied up. Another way to do this kind of thing on Linux is to use ELF TLS to have a thread-local variable identifying if the expensive operation has been completed. If the TLS is not there, you can take a mutex and fall back to the slow path.

comex 12y ago

Copying my comment from the post: I don't think the cpuid is actually required, but feel free to tell me that I'm wrong. The comment in dispatch_once talks about systems with weakly ordered memory models like ARM. But x86 has a strongly ordered model: among other things, "any two stores are seen in a consistent order by processors other than those performing the stores" [Intel]. After calling dispatch_once, I expect to see any writes performed by the once routine, but once the store to the dispatch_once_t flag has been observed, this is already guaranteed. The main reordering pitfall in x86 is that reads may be reordered with earlier writes to different locations, but I don't see how that would cause a problem here.

nkurz 12y ago
I'm tending to agree with your reasoning, but am reaching a slightly different conclusion: there might be a problem, but if there is, I don't see how 'cpuid' solves it. Like any delay, it reduces the chances that it will occur, but I don't think it provides any guarantee. What is to prevent a process from reading the initial predicate==0 and then being swapped out for thousands of cycles just before the conditional is executed? I presume the solution for this is that the "write side" does CAS before it actually executes the block. But since it's doing this anyway, I don't see how the 'cpuid' is actually helping things. I think the CAS will be doing a read-to-own whether or not it succeeds, and thus it should never see the wrong state. Edit: Looking at the comments in the source through the link that Marat supplied below, I'm now realizing that the (supposed) purpose of the 'cpuid' is not to prevent double execution of the initialization block, but to prevent the process that performs the initialization from pre-reading a data variable that is not yet initialized. Since this isn't necessary on x86, it seems even more likely the 'cpuid' is doing anything useful here.
- deleted 12y ago
  [deleted]

nkurz 12y ago

Great article! I'm still trying to wrap my head around this, but in the meantime I'll quibble about one tiny throwaway aside: DISPATCH_EXPECT is a macro that tells the compiler to emit code that tells the CPU that the branch where 8predicate is ~0l is the more likely path. This can improve the success of branch prediction, and thus improve performance. While this is what the macro would do on processors that support such code, x86/x64 isn't one of those processors (Itanium was). Instead, it's more important purpose here is to hint to the compiler (not the processor) to lay out the conditional in assembly such that the expected result is on the faster "branch not taken" path. That said, is the actual implementation of the "write side" viewable online?

Marat_Dukhan 12y ago
There are hints for taken/non-taken branches in x86. However, the only family to use them was Pentium 4; other processors silently ignore those hints. As for the write side, you'll find it here: https://opensource.apple.com/source/libdispatch/libdispatch-339.90.1/src/once.c https://opensource.apple.com/source/libdispatch/libdispatch-...
- gsg 12y ago
  Hints are useless, but arranging for cold code to be on a forward branch can be beneficial.

n0rm 12y ago

Can someone link a mirror? I get timeout for some reason.

rossjudson 12y ago

This feels racy, and I'm not sure it will work on multi-node NUMA architectures. It's one thing to delay and hope that your write is visible in the local processor cache; it's another to ensure that write is visible to other processor nodes, when there's no explicit cache coherence rule that says it will be.