7 ms·

What kind of code is reasonably written as 40+ cores spinlocking the same lock? Seems like a strange design, IMHO…

by m_eiman 8y ago

xpuente 8y ago
This is a PITA for coherence controllers.
mickronome 8y ago
There shouldn't really be any outside of the kernel, and preferably none inside.
- dragontamer 8y ago
  On the contrary: Spinlocks are faster than any other lock. In fact, they're faster than many atomics-based lock-free datastructures (!!!) in many cases. https://www.youtube.com/watch?v=9hJkWwHDDxs https://www.youtube.com/watch?v=9hJkWwHDDxs Atomics-based lock-free data-structures scale beyond 40+ core counts. But note that x86's "lock" instruction is fundamental to the system. x86 doesn't have relaxed atomics or barriers under most circumstances. As such, the spinlock best represents what the x86 instruction set offers.
_wmd 8y ago
You could easily find examples of this - for example in any textbook threaded socket server design (thread pool contending on accept())
- lallysingh 8y ago
  Yeah, those textbooks aren't talking about good implementations that scale up to that many cores.
- spacenick88 8y ago
  But wouldn't that use a non spinning OS lock. I.e. the scheduler knows which threads are waiting on the accept and can randomly pick one to directly wake up?
  - mickronome 8y ago
    If your design have multiple threads waiting for accept on the same socket, then leaving it to the OS to schedule said threads on accept should at least be the first to try. If nothing else because it's the least surprising thing to do.
- smaddox 8y ago
  Does textbook equate to real-world, though? Don't real world applications either use a thread per socket (i.e. per TCP stream) or something like epoll? Genuine questions, because I really don't know.
  - the8472 8y ago
    Real world implementations would use OS-specific socketopts to create multiple listen sockets sharing the same port and then use one socket per thread.
    - _wmd 8y ago
      You're among the 1% of engineers who both care enough to know and actually know about these kinds of facilities. For the rest of them, whatever they got at school or off Stack Overflow is as far as it goes, unless some business priority demands something different - and even in that case "throw more hardware at it" is often the route taken
      - gpderetta 8y ago
        The rest of them is probably, hopefully, using some library abstraction that implement this optimization.
    - blattimwind 8y ago
      I dunno about the BSDs but SO_REUSEPORT is a fairly recent addition. Was there a way to achieve this before then?
- dragontamer 8y ago
  That's not a spinlock. The "Socket textbook example" is either a semaphore or a mutex. The textbook example of a spinlock is maybe a synchronized counter (iterations++), or maybe a producer/consumer queue.
  - _wmd 8y ago
    The accept call on Linux: - invokes the accept() function of the socket family: https://github.com/torvalds/linux/blob/be779f03d563981c65cc7417cc5e0dbbc5b89d30/net/socket.c#L1635 https://github.com/torvalds/linux/blob/be779f03d563981c65cc7... - which invokes the accept() function of the protocol: https://github.com/torvalds/linux/blob/be779f03d563981c65cc7417cc5e0dbbc5b89d30/net/ipv4/inet_connection_sock.c#L425 https://github.com/torvalds/linux/blob/be779f03d563981c65cc7... - which invokes lock_sock_nested(), which spins https://github.com/torvalds/linux/blob/be779f03d563981c65cc7417cc5e0dbbc5b89d30/net/core/sock.c#L2847 https://github.com/torvalds/linux/blob/be779f03d563981c65cc7...
    - dragontamer 8y ago
      The accept call sleeps if no sockets are available. The thread goes to sleep entirely and stops executing on the core completely. Yes, there are spin-locks involved in the process. But I'm talking about these lines of code: > error = inet_csk_wait_for_connect(sk, timeo); > mutex_acquire(&sk->sk_lock.dep_map, subclass, 0, _RET_IP_); Etc. etc. You know, the stuff that causes milliseconds to multiple-seconds worth of delay, as opposed to "pause / spinlocks" which is measured in nanoseconds.
      - _wmd 8y ago
        The parent context asked what code could have 40 cores spinning, I picked the first example I could think of. You said it wasn't a spinlock, it was. Sure there is a followup lock that sleeps for the empty-queue case, but that doesn't relate to OP's question You can find similar behaviour in the filesystem APIs, anything touching the VM (mmap_sem IIRC is also a spinlock), pretty much any OS API where threads are all banging at the same shared resource that isn't expected to require a long wait. struct file also contains a spinlock, but doesn't look like it's used in normal operation
dragontamer 8y ago
From my understanding: a spinlock is actually faster than atomics-based datastructures for less than ~40ish cores. https://www.youtube.com/watch?v=9hJkWwHDDxs https://www.youtube.com/watch?v=9hJkWwHDDxs So actually, you're about right. Its "wrong" to spinlock above 40 cores. But at 40-cores or less, you probably should prefer spinlocks over atomics or other primitives on the x86 platform. As for what? Well, you need a synchronization primitive for a producer-consumer queue. A spinlock would be a good choice for that, even on 40+ core machines (since most of those cores wouldn't be spinning at the same time, even if they're all locking the same lock). Remember, x86 primitive for synchronization is the "LOCK" prefix. When an x86 core "LOCK"s an instruction, no other core is allowed to touch the data its touching. (In MESI protocol: the cache line goes into the "exclusive" state). As such, spinlocks match the fundamental nature of the x86 instruction set very very well.
- bumblebritches5 8y ago
  Ok? It's still the wrong way to write code, and most importantly it's a premature optimization.
- nhaehnle 8y ago
  This seems extremely suspicious. Of course it depends on the nature of the data structure, but in the presentation he compares an atomic increment with a non-atomic increment guarded by a spinlock and comes to the conclusion that the latter is faster for at least on one micro-architecture. Can anybody actually explain this result? The spinlock needs at least one atomic operation and a write (for lock + unlock) and one non-atomic read-modify-write per iteration while the atomic increment needs only a single atomic operation per iteration and no other memory access. How on Earth can the latter variant be slower? The only thing I can think of right now is that due to some micro-architectural idiosyncracies, the relevant cache lines end up migrating between cores more often in the atomic increment case, while in the spinlock case, the same core ends up winning the lock back-to-back more often (and so cachelines migrate less frequently which reduces the overall running time). That seems like it would most likely only ever be relevant to this kind of extremely micro benchmark, but I'd be interested to hear if there are other explanations (I haven't watched the whole talk, but at least the slides don't seem to make an attempt to explain this).

What kind of code is reasonably written as 40+ cores spinlocking the same lock? Seems like a strange design, IMHO…

xpuente 8y ago

This is a PITA for coherence controllers.

mickronome 8y ago

There shouldn't really be any outside of the kernel, and preferably none inside.

dragontamer 8y ago
On the contrary: Spinlocks are faster than any other lock. In fact, they're faster than many atomics-based lock-free datastructures (!!!) in many cases. https://www.youtube.com/watch?v=9hJkWwHDDxs https://www.youtube.com/watch?v=9hJkWwHDDxs Atomics-based lock-free data-structures scale beyond 40+ core counts. But note that x86's "lock" instruction is fundamental to the system. x86 doesn't have relaxed atomics or barriers under most circumstances. As such, the spinlock best represents what the x86 instruction set offers.

_wmd 8y ago

You could easily find examples of this - for example in any textbook threaded socket server design (thread pool contending on accept())

lallysingh 8y ago
Yeah, those textbooks aren't talking about good implementations that scale up to that many cores.
spacenick88 8y ago
But wouldn't that use a non spinning OS lock. I.e. the scheduler knows which threads are waiting on the accept and can randomly pick one to directly wake up?
- mickronome 8y ago
  If your design have multiple threads waiting for accept on the same socket, then leaving it to the OS to schedule said threads on accept should at least be the first to try. If nothing else because it's the least surprising thing to do.
smaddox 8y ago
Does textbook equate to real-world, though? Don't real world applications either use a thread per socket (i.e. per TCP stream) or something like epoll? Genuine questions, because I really don't know.
- the8472 8y ago
  Real world implementations would use OS-specific socketopts to create multiple listen sockets sharing the same port and then use one socket per thread.
  - _wmd 8y ago
    You're among the 1% of engineers who both care enough to know and actually know about these kinds of facilities. For the rest of them, whatever they got at school or off Stack Overflow is as far as it goes, unless some business priority demands something different - and even in that case "throw more hardware at it" is often the route taken
    - gpderetta 8y ago
      The rest of them is probably, hopefully, using some library abstraction that implement this optimization.
  - blattimwind 8y ago
    I dunno about the BSDs but SO_REUSEPORT is a fairly recent addition. Was there a way to achieve this before then?
dragontamer 8y ago
That's not a spinlock. The "Socket textbook example" is either a semaphore or a mutex. The textbook example of a spinlock is maybe a synchronized counter (iterations++), or maybe a producer/consumer queue.
- _wmd 8y ago
  The accept call on Linux: - invokes the accept() function of the socket family: https://github.com/torvalds/linux/blob/be779f03d563981c65cc7417cc5e0dbbc5b89d30/net/socket.c#L1635 https://github.com/torvalds/linux/blob/be779f03d563981c65cc7... - which invokes the accept() function of the protocol: https://github.com/torvalds/linux/blob/be779f03d563981c65cc7417cc5e0dbbc5b89d30/net/ipv4/inet_connection_sock.c#L425 https://github.com/torvalds/linux/blob/be779f03d563981c65cc7... - which invokes lock_sock_nested(), which spins https://github.com/torvalds/linux/blob/be779f03d563981c65cc7417cc5e0dbbc5b89d30/net/core/sock.c#L2847 https://github.com/torvalds/linux/blob/be779f03d563981c65cc7...
  - dragontamer 8y ago
    The accept call sleeps if no sockets are available. The thread goes to sleep entirely and stops executing on the core completely. Yes, there are spin-locks involved in the process. But I'm talking about these lines of code: > error = inet_csk_wait_for_connect(sk, timeo); > mutex_acquire(&sk->sk_lock.dep_map, subclass, 0, _RET_IP_); Etc. etc. You know, the stuff that causes milliseconds to multiple-seconds worth of delay, as opposed to "pause / spinlocks" which is measured in nanoseconds.
    - _wmd 8y ago
      The parent context asked what code could have 40 cores spinning, I picked the first example I could think of. You said it wasn't a spinlock, it was. Sure there is a followup lock that sleeps for the empty-queue case, but that doesn't relate to OP's question You can find similar behaviour in the filesystem APIs, anything touching the VM (mmap_sem IIRC is also a spinlock), pretty much any OS API where threads are all banging at the same shared resource that isn't expected to require a long wait. struct file also contains a spinlock, but doesn't look like it's used in normal operation

dragontamer 8y ago

From my understanding: a spinlock is actually faster than atomics-based datastructures for less than ~40ish cores. https://www.youtube.com/watch?v=9hJkWwHDDxs https://www.youtube.com/watch?v=9hJkWwHDDxs So actually, you're about right. Its "wrong" to spinlock above 40 cores. But at 40-cores or less, you probably should prefer spinlocks over atomics or other primitives on the x86 platform. As for what? Well, you need a synchronization primitive for a producer-consumer queue. A spinlock would be a good choice for that, even on 40+ core machines (since most of those cores wouldn't be spinning at the same time, even if they're all locking the same lock). Remember, x86 primitive for synchronization is the "LOCK" prefix. When an x86 core "LOCK"s an instruction, no other core is allowed to touch the data its touching. (In MESI protocol: the cache line goes into the "exclusive" state). As such, spinlocks match the fundamental nature of the x86 instruction set very very well.

bumblebritches5 8y ago
Ok? It's still the wrong way to write code, and most importantly it's a premature optimization.
nhaehnle 8y ago
This seems extremely suspicious. Of course it depends on the nature of the data structure, but in the presentation he compares an atomic increment with a non-atomic increment guarded by a spinlock and comes to the conclusion that the latter is faster for at least on one micro-architecture. Can anybody actually explain this result? The spinlock needs at least one atomic operation and a write (for lock + unlock) and one non-atomic read-modify-write per iteration while the atomic increment needs only a single atomic operation per iteration and no other memory access. How on Earth can the latter variant be slower? The only thing I can think of right now is that due to some micro-architectural idiosyncracies, the relevant cache lines end up migrating between cores more often in the atomic increment case, while in the spinlock case, the same core ends up winning the lock back-to-back more often (and so cachelines migrate less frequently which reduces the overall running time). That seems like it would most likely only ever be relevant to this kind of extremely micro benchmark, but I'd be interested to hear if there are other explanations (I haven't watched the whole talk, but at least the slides don't seem to make an attempt to explain this).