Re: [RFC] pthread support for FUTEX_WAIT_MULTIPLE

[Florian Weimer <fweimer at redhat dot com>]

* Pierre-Loup A. Griffais:

> On 8/1/19 2:39 AM, Florian Weimer wrote:
>> * Pierre-Loup A. Griffais:
>>
>>> I would think there's still a queue somewhere to acquire jobs, this
>>> would be used before and after. For instance, job threads want to
>>> sleep until work has been queued, or another system event occurs that
>>> might require them to wake up, like app shutdown or scene
>>> transition. Similarly, after firing off N jobs, the job manager will
>>> want to sleep until one of the jobs is complete to perform some
>>> accounting and publish the results to other systems. For both of these
>>> usecases, using eventfd to wait for multiple events seems to result in
>>> more CPU spinning than the futex-based solution, both in userspace and
>>> the kernel.
>>
>> Why do you consider eventfd the only viable alternative?  If you want a
>> futex-based solution today, you can use condition variables.  It won't
>> give you the theoretical minimum of context switches, but neither does
>> FUTEX_WAIT_MULTIPLE, as far as I can tell.
>
> I think there's two main aspects to this, one is purely technical and
> I can try to speak to it a bit below:
>
> Unless I'm missing something, in the scenario where I have N (where N
> is probably close to the CPU count on the machine) job threads
> processing work and needing to report back to a job system, then
> promptly get back to work, wouldn't trying to implement this with
> condition variables introduce unwanted contention between the job
> threads at reporting that wouldn't exist otherwise? Or, unwanted
> spinning on the job manager side.

I don't really see how FUTEX_WAIT_MULTIPLE supports this nicely.  Since
the mutex you get back is arbitrary, you cannot unconditionally enqueue
a job on that worker thread because you might always get back the same
worker thread, leading to unbounded queue growth.  So the submitting
needs to synchronize with the chosen worker thread anyway.

And the contention is there with FUTEX_WAIT_MULTIPLE as well, except
that you don't have one very hot cache line, but several cache lines
bouncing around between CPUs.

I guess the architecture just isn't clear to me.

> The other aspect is that we're dealing with a bunch of applications
> that have their threading model already defined by the time they
> target Linux. They can use WaitForMultiple() on Windows and kqueue on
> macOS; they typically opt for lower-performance "emulation" of the
> desired behavior using multiple mutexes, condition variables, or
> eventfd. I think this new primitive would let them quickly port to
> something that is equally as efficient, or more efficient, than their
> starting point.

I really doubt that a futex-based WaitForMultipleObjects implementation
can have equally efficient performance, unless the Windows
implementation is really, really bad.  It's hard to optimize
WaitForMultipleObjects (just as it is hard to optimize select/poll), but
I think it's impossible if all you have is an array of concrete futexes
with fixed semantics.

Thanks,
Florian