Some really good observations in here about why libdispatch suffered from scalability issues (in that it created to many threads) and the dichotomy of having to sprinkle async everywhere even if it didn’t make sense because it needed to be used from an async function elsewhere.
Related; the difference between “red” and “blue” functions is worth a read:
> Every other OS and languages have tried their own variant of the libdispatch and from what I have read they all failed to some extent.
LibDispatch is Apple's re-implementation of SubmitThreadpoolWork WinAPI, introduced in Windows Vista 3 years before libdispatch. Thread pools work better in Windows because OS kernel support.
In libdispatch and similar cross-platform libraries, OS kernel is unaware of the thread pool. The kernel implements individual threads and schedules them fairly, the rest of the code is user mode.
Windows has I/O completion ports (IOCP) in the kernel since forever, more specifically since NT 3.5 shipped in 1994. That newer Vista API is probably built on top, or uses same kernel features.
Here's an important part from IOCP's documentation:
> The system also allows a thread waiting in GetQueuedCompletionStatus to process a completion packet if another running thread associated with the same I/O completion port enters a wait state for other reasons, for example the SuspendThread function.
This is the unique part which can't be implemented in a user mode library. If you create a thread pool with 1 OS thread per hardware thread, and call any blocking API from the pool, a hardware thread will go to sleep. If you create a thread pool with multiple OS threads per hardware thread, the OS will use all of them concurrently and you'll get overhead from context switches, also latency spikes.
The problem can only be solved in OS kernel. That's why in Windows, thread pools usually works OK.
There is very heavy integration between libdispatch and the kennel on macOS. In fact, when porting libdispatch to non macOS platforms for Swift on Linux, the developers were surprised that they couldn’t just unilaterally introduce changes into the Linux kernel in the same way that they had done on macOS itself.
As a result on Linux platforms, the libdispatch libraries are a software bolt on that doesn’t have the same level of tight integration (and therefore performance) than on macOS.
Given that libdispatch existed in macOS with kernel integration a long time before the Linux library port was added, your claim that it was cross platform doesn’t stand up. It was macOS first, with kernel integration, and then a separate compatibility layer afterwards for non-macOS platforms much later.
Source: I helped out with the porting of Swift to Linux when at Apple.
The issue is that dispatch needs to know what’s running and to allow for the threads to effectively work with the thread schedule to service dispatch in an appropriate way.
On macOS, the implementation is done in kernel, although there is a front end user library that used to interact with it.
This article, although a few years old, talks about the separation of the parts and goes to explain why it’s not a trivial port to other operating systems.
Years and years ago I took an OS course and the professor made us use this weird language called concurrent sp/k
It was a language based on pl/1 with interesting parallel primitives, like cobegin/coend, monitor and a bunch of other things where you could express your parallel needs in different ways. Even years and years later I remember that experience.
Since then I haven't seen cobegin/coend anywhere except in slides, and I haven't seen monitor at all (If I recall correctly it was a critical section allowing only one process inside)
I think the library-based parallel programming scheme is ok, but it might be time to build it into common languages and tools.
cobegin/coend sound very much like co-routines, which is a relatively simple implementation of co-operative multitasking[1]. I've seen it used a lot in embedded programming, and the original Mac OS (pre os-x) was co-operative. Not so common these days with linux/freeRTOS/others providing pre-emptive multitasking
As for 'monitor', that's a standard term for a high level synchronization concept - basically shared data between tasks, but you can only access that data via the monitor's procedures, and it enforces one-at-a-time access. You can create a monitor with a semaphore and a class-with-private-ivars, assuming all the accessors wait on the semaphore.
I generally fix performance problems nowadays by eliminating threads and queues, particularly "lock-free" queues, and splitting out work to whole separate single-thread processes that communicate only via ring buffers in mmapped hugepages.
The freedom to kill and restart the programs as needed makes a huge difference in ease of managing a system. I use kernel-bypass networking and "isolcpus" so the time-critical code never does any system calls. The programs do all their slow, mallocy OS-coupled work at startup, and then never again except to log errors or when shutting down. They mmap structs onto files under /dev/shm/ for status reporting, mostly just incrementing counters that another program, running every few seconds, formats into snapshot reports logged and displayed in grafana.
It is not the right architecture for everything, but it captures to disk all the activity of all the stock and options market exchanges in New York and Chicago using just a single 1U server attached to a 4U disk array.
"Lock-free" operations are not really lock-free at all; they involve atomic bus operations, which just do locking in hardware similarly to what you would otherwise have done. So, to get performance, you minimize interactions enough that the time wasted per interaction is negligible, and batch work so that the branch predictors and caches can get well primed and then used for a stretch. Atomic operations when you are the only writer, and so already own the cache lines, are cheap.
11 comments
[ 2.5 ms ] story [ 36.5 ms ] threadRelated; the difference between “red” and “blue” functions is worth a read:
https://journal.stuffwithstuff.com/2015/02/01/what-color-is-...
Here's an example of this in Objective-C: https://github.com/stevedekorte/ActorKit
LibDispatch is Apple's re-implementation of SubmitThreadpoolWork WinAPI, introduced in Windows Vista 3 years before libdispatch. Thread pools work better in Windows because OS kernel support.
In libdispatch and similar cross-platform libraries, OS kernel is unaware of the thread pool. The kernel implements individual threads and schedules them fairly, the rest of the code is user mode.
Windows has I/O completion ports (IOCP) in the kernel since forever, more specifically since NT 3.5 shipped in 1994. That newer Vista API is probably built on top, or uses same kernel features.
Here's an important part from IOCP's documentation:
> The system also allows a thread waiting in GetQueuedCompletionStatus to process a completion packet if another running thread associated with the same I/O completion port enters a wait state for other reasons, for example the SuspendThread function.
This is the unique part which can't be implemented in a user mode library. If you create a thread pool with 1 OS thread per hardware thread, and call any blocking API from the pool, a hardware thread will go to sleep. If you create a thread pool with multiple OS threads per hardware thread, the OS will use all of them concurrently and you'll get overhead from context switches, also latency spikes.
The problem can only be solved in OS kernel. That's why in Windows, thread pools usually works OK.
As a result on Linux platforms, the libdispatch libraries are a software bolt on that doesn’t have the same level of tight integration (and therefore performance) than on macOS.
Given that libdispatch existed in macOS with kernel integration a long time before the Linux library port was added, your claim that it was cross platform doesn’t stand up. It was macOS first, with kernel integration, and then a separate compatibility layer afterwards for non-macOS platforms much later.
Source: I helped out with the porting of Swift to Linux when at Apple.
Or is that kernel support only for message passing, callbacks, memory management, synchronization, logging or similar?
On macOS, the implementation is done in kernel, although there is a front end user library that used to interact with it.
This article, although a few years old, talks about the separation of the parts and goes to explain why it’s not a trivial port to other operating systems.
https://gigaom.com/2009/09/14/apple-open-sources-grand-centr...
It was a language based on pl/1 with interesting parallel primitives, like cobegin/coend, monitor and a bunch of other things where you could express your parallel needs in different ways. Even years and years later I remember that experience.
Since then I haven't seen cobegin/coend anywhere except in slides, and I haven't seen monitor at all (If I recall correctly it was a critical section allowing only one process inside)
I think the library-based parallel programming scheme is ok, but it might be time to build it into common languages and tools.
As for 'monitor', that's a standard term for a high level synchronization concept - basically shared data between tasks, but you can only access that data via the monitor's procedures, and it enforces one-at-a-time access. You can create a monitor with a semaphore and a class-with-private-ivars, assuming all the accessors wait on the semaphore.
[1]: https://en.wikipedia.org/wiki/Coroutine
My thought was that a construct like that would be clumsy to do with library-based multitasking
The freedom to kill and restart the programs as needed makes a huge difference in ease of managing a system. I use kernel-bypass networking and "isolcpus" so the time-critical code never does any system calls. The programs do all their slow, mallocy OS-coupled work at startup, and then never again except to log errors or when shutting down. They mmap structs onto files under /dev/shm/ for status reporting, mostly just incrementing counters that another program, running every few seconds, formats into snapshot reports logged and displayed in grafana.
It is not the right architecture for everything, but it captures to disk all the activity of all the stock and options market exchanges in New York and Chicago using just a single 1U server attached to a 4U disk array.
"Lock-free" operations are not really lock-free at all; they involve atomic bus operations, which just do locking in hardware similarly to what you would otherwise have done. So, to get performance, you minimize interactions enough that the time wasted per interaction is negligible, and batch work so that the branch predictors and caches can get well primed and then used for a stretch. Atomic operations when you are the only writer, and so already own the cache lines, are cheap.