Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Implement mechanism to wait on any of several futexes

lkml.org

Post reply on HN
Print view View original

91–100 of 158 posts

Re: Implement mechanism to wait on any of several futexes

#91

Post by pizlonator »

badamp wrote: post #66
Asooka wrote: post #62

I know the patch mentions interactive multimedia applications (games) in particular, but an actual mechanism to implement WaitForMultipleObjects on Linux would be very welcome for many high-performance multi-threaded applications. Say you have one worker thread per CPU core. On Windows, each thread would get an Event object and you would WaitOnMultiple to be able to act on the first unit of work that was complete. On…

Linux already has what you’re talking about with eventfd and epoll. In Linux each thread can get an eventfd and you can POLLIN all of them. In fact I would argue that using futexes is the “roll your own solution” using lower level primitives (and easier to fuckup) much more so than eventfd and epoll. As mentioned somewhat poorly in the post, using futexes gives a performance boost which is not surprising since they a…

You’re talking about interfaces for waiting on multiple kernel resources but the new futex interface enables you to wait for multiple user resources.

Though it can emulate a win32 api for waiting on multiple “objects”, it’s strictly more powerful than WaitForMultiple if you are dealing with user objects since futexes impose very few constraints on how your user synchronization object is shaped and how it works.

So, the new interface is totally different from things like epoll. In one case the kernel is helping you wait for multiple user objects and in the other case it’s helping you wait for multiple kernel objects. The distinction is intentional because the whole point is that the user object that has the futex can be shaped however user likes, and can implement whatever synchro protocol the use likes.

Finally, it’s worth remembering that futex interfaces are all about letting you avoid going into kernel unless there is actually something to wait for. The best part of the api is that it helps you to avoid calling it. So for typical operations, if the resource being waited on can have its wait state represented as a 32-bit int in user memory, the futex based apis will be a lot faster.

Re: Implement mechanism to wait on any of several futexes

#92

Post by [deleted] »

pjc50 wrote: post #76
pizlonator wrote: post #75

Earlier quoted context omitted.

Its much more than timeouts. Here’s the killer use case outside wine: - program with fine grained locks - you have an algorithm that needs to acquire N of those locks, one at a time, and can do it in any order In that case, you really want to: - first attempt fast path locking on all of them in any order - if that fails tell the kernel about all of the locks you are waiting on at once. This means that you will become…

You can't acquire locks in any order, that's a recipe for deadlock when one process has acquired half the locks and another has the different half, resulting in them waiting on each other. Use of WaitForMultipleObjects is more usually for completion of tasks, in the way that win32 "overlapped" works.

[deleted]

Re: Implement mechanism to wait on any of several futexes

#93

Post by mehrdadn »

monocasa wrote: post #90
jdsully wrote: post #89

Earlier quoted context omitted.

Thats my point. They should just bite the bullet and implement WaitForMultipleObjects instead of having all these disjoint APIs. Plus sometimes you want to wait for both and this is very difficult with Linux. Its also telling Linux has gone through the whole select/poll/epoll madness while WaitForMultipleObjects has worked well in windows NT since the 90s. Its a proven design.

I mean.. epoll is already better than WFMO. It doesn't have that silly 64 item cap, or O(N) entry and exit on the wait like it's 1995 all over again. (And that's not to say that epoll is the pinnacle of design, just that WFMO is worse. We can do better than both) And this better too, you don't need to register futexes with the kernel, the futex wait call is just "I want to sleep until the data at this memory address…

The thing is, on Windows, you're not supposed to wait on a thousand handles at once. You're supposed to use overlapped I/O, completion ports, etc. which work quite well.

Re: Implement mechanism to wait on any of several futexes

#94

Post by monocasa »

mehrdadn wrote: post #93
monocasa wrote: post #90

Earlier quoted context omitted.

I mean.. epoll is already better than WFMO. It doesn't have that silly 64 item cap, or O(N) entry and exit on the wait like it's 1995 all over again. (And that's not to say that epoll is the pinnacle of design, just that WFMO is worse. We can do better than both) And this better too, you don't need to register futexes with the kernel, the futex wait call is just "I want to sleep until the data at this memory address…

The thing is, on Windows, you're not supposed to wait on a thousand handles at once. You're supposed to use overlapped I/O, completion ports, etc. which work quite well.

This use case in the article isn't about I/O at all though. Futexes are user space mutexes. Overlapped I/O and completion ports don't help you in that case.

Re: Implement mechanism to wait on any of several futexes

#95

Post by dpcx »

lostmsu wrote: post #78
bityard wrote: post #49

Earlier quoted context omitted.

It's the same reason you dress nice and comb your hair for a job interview. If the developer of the patch couldn't get the easy minor details right before submitting, I wouldn't have much confidence that they spent a lot of effort thinking about the hard, major details either.

I think this is very backwards. When solving major problems details of taste are usually a blocker or waste of time.

I think a law that says speeding is very backwards. When I'm late, details like how far over the speed limit I'm going are a blocker or a waste of time.

The kernel team came up with rules about how code is formatted. If you don't follow the rules, they are under no obligation to allow your code to be merged in to the main repo, and in fact, are within their rights to reject it. I take the initial response more as a "I'm going to let you off with a warning" versus "Here's your ticket, see you in court"

Re: Implement mechanism to wait on any of several futexes

#96

Post by mehrdadn »

monocasa wrote: post #94
mehrdadn wrote: post #93

Earlier quoted context omitted.

The thing is, on Windows, you're not supposed to wait on a thousand handles at once. You're supposed to use overlapped I/O, completion ports, etc. which work quite well.

This use case in the article isn't about I/O at all though. Futexes are user space mutexes. Overlapped I/O and completion ports don't help you in that case.

Right, but when do you need to simultaneously wait on more than 64 things other than for I/O? I've never had to wait on that many mutexes...

(P.S. there is a really ugly way to get around this on Windows if for some bizarre reason you really need to, which is to have 1 thread per 64 handles, then wait on the thread handle instead. I've never found a need do even get close to doing such a thing though.)

Re: Implement mechanism to wait on any of several futexes

#97

Post by monocasa »

mehrdadn wrote: post #96
monocasa wrote: post #94

Earlier quoted context omitted.

This use case in the article isn't about I/O at all though. Futexes are user space mutexes. Overlapped I/O and completion ports don't help you in that case.

Right, but when do you need to simultaneously wait on more than 64 things other than for I/O? I've never had to wait on that many mutexes... (P.S. there is a really ugly way to get around this on Windows if for some bizarre reason you really need to, which is to have 1 thread per 64 handles, then wait on the thread handle instead. I've never found a need do even get close to doing such a thing though.)

Off the top of my head, timers?

Re: Implement mechanism to wait on any of several futexes

#98

Post by badamp »

Taniwha wrote: post #81
badamp wrote: post #66

Earlier quoted context omitted.

Linux already has what you’re talking about with eventfd and epoll. In Linux each thread can get an eventfd and you can POLLIN all of them. In fact I would argue that using futexes is the “roll your own solution” using lower level primitives (and easier to fuckup) much more so than eventfd and epoll. As mentioned somewhat poorly in the post, using futexes gives a performance boost which is not surprising since they a…

They point out that they already have an implementation that does just this .... and it fails on some programs due to running out of file descriptors (they have one program that needs ~1 million of them ...)

If you read the full thread that is a bit of a red herring and beside the point (thats why I said the conveyance of the performance implication was poor)... indeed window WFMO only supports 64 objects per call. They mention that the fd issue is due to leaking objects in many windows programs..which was an odd mention and a little off the main subject. The main motivator is performance. If eventfds performed better it would likely be better to fix the fd leak issue with a cache.

Again.. eventfd and epoll covers the same use case as WFMO and EVENTs.

Re: Implement mechanism to wait on any of several futexes

#99

Post by LukeShu »

Shorel wrote: post #71
gnufied wrote: post #46

Personally for me - the problematic part of gaming on Linux has been input(i.e mouse) latency and acceleration profile. I am not sure if this is just my experience but when using libinput on Fedora for example - the cursor movement is not exactly precise. This is not obvious when working but while gaming this is a deal breaker.

Games in Windows can get raw mouse input just by writing the code for it, and Linux games usually don't because that would require root permissions, to add the user to the input group, etc. It is a security issue and an X-Window design issue.

Normal human users will/should almost always be members of the 'input' group.

Re: Implement mechanism to wait on any of several futexes

#100

Post by Asooka »

badamp wrote: post #66
Asooka wrote: post #62

I know the patch mentions interactive multimedia applications (games) in particular, but an actual mechanism to implement WaitForMultipleObjects on Linux would be very welcome for many high-performance multi-threaded applications. Say you have one worker thread per CPU core. On Windows, each thread would get an Event object and you would WaitOnMultiple to be able to act on the first unit of work that was complete. On…

Linux already has what you’re talking about with eventfd and epoll. In Linux each thread can get an eventfd and you can POLLIN all of them. In fact I would argue that using futexes is the “roll your own solution” using lower level primitives (and easier to fuckup) much more so than eventfd and epoll. As mentioned somewhat poorly in the post, using futexes gives a performance boost which is not surprising since they a…

Yes, and you have to cobble together an event implementation out of eventfd and epoll. There are two problems (specifically talking about multi-platform software)

1. You'll likely get it wrong and have subtle bugs.

2. This is significantly different than the Windows model where you wait on events. Now you have two classes of events - regular ones, and ones that can be waited on in multiple. The second class also comes with its own event manager class that needs to manage the eventfd for this group of events.

You end up with a specialised class of event that needs to be used whenever you need to wait in several of them at once. Then you realise you used a normal POSIX event somewhere else and now you want to wait on that as well, so you have to rewrite parts of your program to use your special multi-waitable event.

It's mostly trivial to write a event wrapper on top of POSIX events that behaves the same as Windows Events, except for the part where you might want to wait on multiple of them. I would expect that once this kernel interface is implemented we'll get GNU extensions in glibc allowing for waiting on multiple POSIX events. I absolutely do not want to roll my own thread synchronisation primitives except for very thin wrappers over the platform-specific primitives. Rolling your own synchronisation primitives is about as fraught with peril as rolling your own crypto.

To be honest, WaitForMultipleObjects will probably become not very useful in the near future. We're getting 32-core workstation CPUs today, it's quite likely there will be CPUs with more than 64 cores in near future workstations making it impossible to use this classic Windows primitive, but I suspect Microsoft will provide WaitForMultipleObjectsEx2.

Post reply on HN