Swift Actor/Tasks concurrency on Linux - Lock contention in rand()

[freef4ll]

We have a workload pipeline which is chaining several thousand Actors to each other via AsyncStream processing pipeline.
There is a multiplication affect that a single event at the start of the processing pipeline will be amplified as the event will be delivered to several Tasks processing the events concurrently. The processing time of each wakeup is currently quite small and on several microseconds range currently.

Under Linux, what was observed when stressing this processing pipeline is that ~45% of the stacks show __DISPATCH_ROOT_QUEUE_CONTENDED_WAIT__(), which is leading to lock contention in glibc rand() - as there are ~60 threads which are created and they all contend here:

            7f193794a2db futex_wait+0x2b (inlined)
            7f193794a2db __GI___lll_lock_wait_private+0x2b (inlined)
            7f19378ff29b __random+0x6b (/usr/lib/x86_64-linux-gnu/libc.so.6)
            7f19378ff76c rand+0xc (/usr/lib/x86_64-linux-gnu/libc.so.6)
            7f1937bac612 __DISPATCH_ROOT_QUEUE_CONTENDED_WAIT__+0x12 (/usr/lib/swift/linux/libdispatch.so)

This is occurring in every entrance of DISPATCH_ROOT_QUEUE_CONTENDED_WAIT(), while using macro _dispatch_contention_wait_until() which in turn uses _dispatch_contention_spins(), in here the rand() call comes in and the macro produces just these 4 values: 31, 63, 95 and 127 for how many pause/yield instructions to execute.

The following example can reproduce the issue where ~28% of the time when sampling is spent in the code path mentioned.
The example creates 5000 tasks which work between 1μs and 3μs and then sleep for random 6-10 milliseconds. The point of the test is to create the contention and to illustrate the issue with rand():

// $ swift package init --type executable --name RandomTasks
// $ cat  Sources/RandomTasks/main.swift &&  swift run -c release

import Foundation

let numberOfTasks = 5000
let randomSleepRangeMs: ClosedRange<UInt64> = 6 ... 10

// correlates closely to processing amount in micros
let randomWorkRange: ClosedRange<UInt32> = 1 ... 3

@available(macOS 10.15, *)
func smallInfinitiveTask() async {
    let randomWork = UInt32.random(in: randomWorkRange)
    let randomSleepNs = UInt64.random(in: randomSleepRangeMs) * 1_000_000
    print("Task start; sleep: \(randomSleepNs) ns, randomWork: \(randomWork) ")

    while true {
        do {
            var x2: String = ""
            x2.reserveCapacity(2000)
            for _ in 1 ... 50 * randomWork {
                x2 += "hi"
            }
            // Thread.sleep(forTimeInterval: 0.001) // 1ms
            try await Task.sleep(nanoseconds: randomSleepNs)
        } catch {}
    }
}

@available(macOS 10.15, *)
func startLotsOfTasks(_ tasks: Int) {
    for _ in 1 ... tasks {
        Task {
            await smallInfinitiveTask()
        }
    }
}

if #available(macOS 10.15, *) {
    startLotsOfTasks(numberOfTasks)
} else {
    // Fallback on earlier versions
    print("Unsupported")
}

sleep(600)

When run on Ryzen 5950X system, 18-19 HT cores are spent processing the workload. While on M1 Pro just ~4.

[freef4ll]

A semi-related issue was present in Windows, that was resolved with: #453 / #455

[hassila]

Would it be possible to use the Windows optimization for Linux also possibly to work around this?

[weissi]

CC @rokhinip

[ilya-fedin]

Is there any plan to solve this issue? It's reaching a third year since reported :(

[weissi]

CC @ktoso / @rokhinip / @rjmccall do you know what the plans w.r.t. Concurrency runtime and dispatch are? Clearly there are a bunch of things that need addressing and corelibs-dispatch isn't getting updated...

[ilya-fedin]

Silence :(

[ktoso]

Hi everyone,
we've been doing a lot of thinking about the executor pool provided here by (corelibs) Dispatch for Swift Concurrency.
We're leaning towards a fresh thread-pool implementation, that would be tailored towards Swift Concurrency's needs specifically, rather than thinking about the DispatchQueue APIs explicitly. Instead of explicitly having 1:1 dispatch API's back Swift Concurrency on various platforms, I think we're more interested in specialized executor implementations per platform, which then Swift Concurrency uses.

Sadly this is no small feat and a large project in itself. We don't currently have more details to share on the long term.

We'd certainly welcome any PRs that could help remove the short-term pain, but medium-to-long term we think replacing the executors backing Swift Concurrency may be a preferable direction here.

[ilya-fedin]

What does this mean for me if I use libdispatch directly in a C++ application as a lock-free thread pool implementation? Is this variant of libdispatch officially discontinued?

[ilya-fedin]

We'd certainly welcome any PRs that could help remove the short-term pain

Would such a PR be ok?

diff --git a/src/shims/yield.h b/src/shims/yield.h
index 53eb800..c8e5eed 100644
--- a/src/shims/yield.h
+++ b/src/shims/yield.h
@@ -98,7 +98,7 @@ void *_dispatch_wait_for_enqueuer(void **ptr);
 #define _dispatch_contention_spins() \
                ((DISPATCH_CONTENTION_SPINS_MIN) + ((DISPATCH_CONTENTION_SPINS_MAX) - \
                (DISPATCH_CONTENTION_SPINS_MIN)) / 2)
-#elif defined(_WIN32)
+#else
 // Use randomness to prevent threads from resonating at the same frequency and
 // permanently contending. Windows doesn't provide rand_r(), so use a simple
 // LCG. (msvcrt has rand_s(), but its security guarantees aren't optimal here.)
@@ -108,12 +108,6 @@ void *_dispatch_wait_for_enqueuer(void **ptr);
                os_atomic_store(&_seed, _next * 1103515245 + 12345, relaxed); \
                ((_next >> 24) & (DISPATCH_CONTENTION_SPINS_MAX)) | \
                                (DISPATCH_CONTENTION_SPINS_MIN); })
-#else
-// Use randomness to prevent threads from resonating at the same
-// frequency and permanently contending.
-#define _dispatch_contention_spins() ({ \
-               ((unsigned int)rand() & (DISPATCH_CONTENTION_SPINS_MAX)) | \
-                               (DISPATCH_CONTENTION_SPINS_MIN); })
 #endif
 #define _dispatch_contention_wait_until(c) ({ \
                bool _out = false; \

[rjmccall]

Is this variant of libdispatch officially discontinued?

No. The Swift project is just considering whether it should continue to use libdispatch as the standard implementation of our thread pool on non-Darwin platforms.

What does this mean for me if I use libdispatch directly in a C++ application as a lock-free thread pool implementation?

Without any changes to make the thread pools coordinate, they'd both create their own threads. Out of the box, that means you could end up with 2 * ncpus threads — or more, given that normal uses of libdispatch don't hard-cap the thread count. IIRC, you can manually cap libdispatch's thread usage with environment variables, and I assume we'd want to offer the same capability with a Swift thread pool. We might also choose to offer direct APIs to schedule work on Swift's thread pool.

[ilya-fedin]

Without any changes to make the thread pools coordinate, they'd both create their own threads.

Both? Perhaps there's a misunderstanding: I don't use Swift, I just use libdispatch.

[rjmccall]

We'd certainly welcome any PRs that could help remove the short-term pain

Would such a PR be ok?

That seems abstractly right; could you adjust the comment and make a real PR?

[rjmccall]

Without any changes to make the thread pools coordinate, they'd both create their own threads.

Both? Perhaps there's a misunderstanding: I don't use Swift, I just use libdispatch.

Then you would not be affected by Swift's use of a different thread pool implementation.

[ilya-fedin]

Well, my question was about what it means for libdispatch bugs priority & maintenance in general :)