Re: [sync] Optimizing Boost's sync using futex2

From: André Almeida (andrealmeid_at_[hidden])
Date: 2021-05-14 16:35:56

Às 18:07 de 13/05/21, Andrey Semashev via Boost escreveu:
> Beware of a long post.
> 
> On 5/13/21 5:27 PM, André Almeida wrote:
>> Hi there,
>>
>> I'm the author of futex2[0], a WIP new set of Linux's syscalls that
>> allows userspace to write efficient sync mechanisms. I would like to
>> hear from Boost's developers if the project would benefit from this new
>> interface.
>>
>> Â From Boost/sync's codebase, I can see that you are already familiar with
>> futexes, but just in case:
> 
> [snip]
> 
>> The detailed description of the API can be seen in the documentation
>> patch[1]. Do you think that Boost would benefit from it?
> 
> Hi, and thank you for working on this and especially for including
> 64-bit futex support in the latest patches. I have already described
> some of the use cases in my earlier post on LKML[1], but I'll try to
> recap and expand on it here.

Sorry for not replying your post, I thing it got lost in my inbox.

<snip>

> Of the libraries I mentioned, the prime user of futex2 would be
> Boost.Atomic. With the current implementation based on existing futex
> API, the important missing part is support for futex sizes other than 32
> bits. This means that for atomics other than 32-bit Boost.Atomic must
> use an internal lock pool to implement waiting and notifying operations,
> which increases thread contention. For inter-process atomics, this means
> that waiting must be done using a spin loop, which is terribly
> inefficient. So, the support for 8, 16 and 64-bit futexes would be very
> much needed here.

Cool, I'll be adding "better support for userspace atomics" as an use
case for variable size futexes.

So far, I've been advertising that variable sized futexes would be good
for saving some memory. Do you think that using 8bit sized futexes for
e.g. Boost's mutexes would save something or would be unlikely noticed?

> 
> Another potential use case for futex2 is the mass locking algorithms[2]
> in Boost.Thread. Basically, the algorithm accepts a list of lockable
> objects (e.g. locks or mutexes) and attempts to lock them all before
> returning. Here, I imagine, the support for waiting on multiple futexes
> could come in handy. It should be noted that the algorithms are generic,
> so they must work on any type of lockable objects, including those that
> do not use or expose a futex, so the optimization is not trivial or
> universally applicable. However, if the algorithm is applied to
> Boost.Thread primitives, and those expose a futex, this could work quite
> well.

In Wine, wait on multiples futexes is used as backend for a operation
that can wait on different things as well (WaitForMultipleObjects), so I
think the solution was to add a `unsigned int futex` at those objects.
It's good to see that more use cases would benefit from this feature.

> 
> Alternatively, futex2 could offer a new API for implementing robust
> primitives in userspace.

Yes, robust futexes are not part of futex2 discussion for now, but
thanks anyway for your proactive feedback. I'll revisit this suggestion
and ping you when it's time for it.

<snip>

> 
> As for use cases outside Boost, that application that I described in the
> LKML post would benefit not only from 64-bit futexes but also from the
> ability to wait on multiple futexes.
> [...]
> I can provide more details on this use case, if you're
> interested.
> 

Please, I would love to hear more about that.

Thank you very much Andrey, your detailed feedback will help me a lot
with futex2 development!

André