classification
Title: threading.Condition to allow notify on a specific waiter
Type: enhancement Stage: resolved
Components: Library (Lib) Versions: Python 3.4
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: JBernardo, neologix, pitrou, rhettinger, richardnwhitehead, sbt
Priority: normal Keywords: patch

Created on 2013-05-28 03:40 by JBernardo, last changed 2019-08-23 22:11 by rhettinger. This issue is now closed.

Files
File name Uploaded Description Edit
wait_for_any.patch JBernardo, 2013-05-29 14:39 wait_for_any, from_condition review
Messages (31)
msg190173 - (view) Author: João Bernardo (JBernardo) * Date: 2013-05-28 03:40
If users could provide an inner lock for `threading.Condition` acquire when making a thread wait, it would allow for notifying a specific waiter.

Because of race conditions, using:

    cond.notify(1)

may not wake the thread I want. Also, I may not want to wake the first waiter at all.

So my proposal is something along the lines:



class Condition:
    ...

    def wait(self, timeout=None, lock=None):
        ...
        waiter = _allocate_lock() if lock is None else lock
        ...

    def notify_one(self, lock): 
        # Maybe could notify a list of locks?

        try:
            self._waiters.remove(lock)
        except ValueError:
            pass 
            # Maybe RuntimeError("Lock not waiting in this Condition")
        else:
            lock.release()
msg190193 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-28 11:03
I'm not sure what the point is. If you want to wake up a specific thread, you'd probably be better off with a dedicated per-thread synchronization primitive (either a Condition or something else).
msg190194 - (view) Author: João Bernardo (JBernardo) * Date: 2013-05-28 11:10
I usually have hundreds of threads waiting on a single Condition object and I wake them with .notify_all()

Sometimes, I want a specific thread to wake from this condition and finish their job apart from the others.

The problem is that I have 2 "conditions" to wait for. I can't just add another Condition object and ask for it to wait for the first (unless there is some sort of `select` mechanism).

BTW, I find .notify(N) not much useful, because the docs say it may wake more threads on a different implementation and also I can't never know whom am I waking.
msg190214 - (view) Author: Richard Oudkerk (sbt) * (Python committer) Date: 2013-05-28 14:36
> BTW, I find .notify(N) not much useful, because the docs say it may wake 
> more threads on a different implementation and also I can't never know 
> whom am I waking.

The fact that more than N threads can wake up is not a problem if you are retesting an appropriate predicate as soon as your waiting threads awakes.  (And if you are not retesting then you are abusing the condition variable.)

But it might be nice to be able to wait on multiple conditions at once, assuming they are associated with the same lock.  Maybe we could have a static method

    Condition.wait_for_any(cond_to_pred: dict, timeout=None) -> condition

where cond_to_pred is a mapping from condition variable to predicate function to test for.  The return value would be the condition variable whose predicate is true (or None if there was a timeout).  So then

    cond.wait_for(pred)

would be equivalent to

    Condition.wait_for_any({cond: pred}) is cond
msg190216 - (view) Author: João Bernardo (JBernardo) * Date: 2013-05-28 14:55
> But it might be nice to be able to wait on multiple conditions at 
> once, assuming they are associated with the same lock.  Maybe we could 
> have a static method

This could solve the waiting problem for the "thread", but also may keep the other Condition objs waiting -- and that may not be problem because I'm already using .notify_all()

Probably this function have more use cases than my original idea, but is it simple to wait on several locks?

It could be in the form:

Condition.wait_for_any(cond_to_pred: dict|list, timeout=None) -> condition

For cases when there's no need for a predicate function.
msg190221 - (view) Author: Richard Oudkerk (sbt) * (Python committer) Date: 2013-05-28 15:37
> This could solve the waiting problem for the "thread", but also may 
> keep the other Condition objs waiting -- and that may not be problem 
> because I'm already using .notify_all()

I don't understand what you mean.

> Probably this function have more use cases than my original idea, but 
> is it simple to wait on several locks?

It would be for waiting for several conditions associated with the same lock, not for waiting for several locks.

> It could be in the form:
>
> Condition.wait_for_any(cond_to_pred: dict|list, timeout=None) -> condition
>
> For cases when there's no need for a predicate function.

There is always a need for a predicate function.
msg190222 - (view) Author: João Bernardo (JBernardo) * Date: 2013-05-28 15:52
> It would be for waiting for several conditions associated with the 
> same lock, not for waiting for several locks.

A Condition uses a 2 lock mechanism: 
  - outer lock: one for all the waiters to access the Condition object 
  - inner lock: one for each waiter to wait on.

You cannot associate several conditions to the *inner lock*, because you don't have access to them (otherwise I wouldn't open this issue).
You said you want to have several conditions on the lock passed by the user:

    lock = Lock()
    cond1 = Condition(lock)
    cond2 = Condition(lock)
    Condition.wait_for_any({cond1: foo, cond2: bar})

but because this "lock" object is not the one the thread is waiting on, it won't work.


> There is always a need for a predicate function.

You may not need to test for a predicate when using .wait() . Only when you're using .wait_for()
This is what I'm most interested in mimicking.
msg190227 - (view) Author: Richard Oudkerk (sbt) * (Python committer) Date: 2013-05-28 17:15
> You cannot associate several conditions to the *inner lock*, because you 
> don't have access to them (otherwise I wouldn't open this issue).

Condition.wait_for_any() would create a single inner lock and add it to the _waiters list for each of the condition variables.  notify() and notify_all() would need to deal with the possibility that releasing the inner lock fails with ThreadError because it has already been unlocked.

> You may not need to test for a predicate when using .wait() . Only when you're 
> using .wait_for()
> This is what I'm most interested in mimicking.

(Ignoring timeouts) wait() should be used with the idiom

    while <expr>:
        cond.wait()

This allows the woken thread to check whether it is really supposed to continue --
it sounds like you are not doing this.  The only advantage of using wait() over wait_for() is that sometimes it avoids you having to create a named function or lambda function like in

    cond.wait_for(lambda: not (<expr>))
msg190228 - (view) Author: João Bernardo (JBernardo) * Date: 2013-05-28 17:32
> Condition.wait_for_any() would create a single inner lock and add it 
> to the _waiters list for each of the condition variables

Now I see your point!
Could it also have one (optional) argument so I can provide this lock myself? 

>    while <expr>:
>        cond.wait()
> This allows the woken thread to check whether it is really supposed
> to continue --

Yes, I use that, but sometimes I have the thread just waiting for cleanup time and there's no need to check a condition. This is one my use cases though... You may want it to be more generic.
msg190310 - (view) Author: João Bernardo (JBernardo) * Date: 2013-05-29 14:39
I did what @Richard Oudkerk said and created the "wait_for_any" classmethod for the Condition class.

Other Changes:

 - I had to refactor "wait" and "wait_for" to be specializations of "wait_for_any".
 - try...except on "notify" because the inner lock might have been released by other condition.
 - Added two helper functions "_remove_waiter" and "_wait" (the part of the old wait function to re-acquire the inner lock)

Bonus:
To simplify the use, I added a "from_condition" constructor to create a new condition using the same lock as an existing one.
That way, you don't need to record the lock someplace else before creating a new Condition for the same lock.


* The current tests pass.

* Missing: new tests and docs.


----

Sample:

    lock = Lock()
    cond1 = Condition(lock)
    cond2 = Condition(lock)
    cond3 = Condition.from_condition(cond1)

    with lock:
        Condition.wait_for_any({cond1: foo, cond2: bar})
        Condition.wait_for_any([cond1, cond2, cond3]) # no predicates
                                                      # used on "wait"
    with cond2: # same thing
        Condition.wait_for_any({cond3: foo})

---

PS: the patch text is messy because of refactoring and some lines were moved. It is easy to read when applied.
msg190556 - (view) Author: João Bernardo (JBernardo) * Date: 2013-06-03 18:56
Hi,
This code is working quite well on my system, but I'm still not sure if the behavior of multiple predicates is the one other people want. So, for the thread start running again:

- Should it test only the predicates from the awakened Conditions an accept if one of them is true?
- Or any of the predicates must be true (current implementation)?
- Or all of them must be true (less likely, but possible)?

Another option is that we allow the behavior to be configurable.
msg190591 - (view) Author: Charles-François Natali (neologix) * (Python committer) Date: 2013-06-04 07:01
I'm not convinced it's really useful.
Furthermore, the complexity is rather bad: if T is the average number
of waiting threads, an C the number of conditions being waited on, the
wait is O(C) (appending to C wait queues) and wakeup is O(CT) (C
removal from a T-length deque).
msg190594 - (view) Author: João Bernardo (JBernardo) * Date: 2013-06-04 11:01
> I'm not convinced it's really useful.

It doesn't seem a lot useful until you *really* need it. I've got 2 highly parallel programs that took advantage of this pattern.


> the wait is O(C) (appending to C wait queues) and wakeup
> is O(CT) (C removal from a T-length deque).

That's another thing that I wanted to address, but I didn't want to change the data structure in this patch.

The complexity for `notify` and `notify_all` is the same as before.
msg190597 - (view) Author: Richard Oudkerk (sbt) * (Python committer) Date: 2013-06-04 14:06
> Furthermore, the complexity is rather bad: if T is the average number
> of waiting threads, an C the number of conditions being waited on, the
> wait is O(C) (appending to C wait queues) and wakeup is O(CT) (C
> removal from a T-length deque).

Which just means that waiting on C conditions is C times more expensive than waiting on 1 currently is.  That seems reasonable enough to me, and anyway, I would expect C to be fairly small.

Note that the alternative is to use a single condition and use notify_all() instead of notify().  That is likely to be much more expensive because every waiting thread must wake up to see if it should continue.

But I am still not sure it is worth it.

BTW, I think it would be better to have wait_for_any() return a list of ready conditions rather than a boolean.
msg190599 - (view) Author: João Bernardo (JBernardo) * Date: 2013-06-04 14:39
> BTW, I think it would be better to have wait_for_any() 
> return a list of ready conditions rather than a boolean.

That was the original idea until I realized `wait` and `wait_for` were just specializations of `wait_for_any`.

This can probably be done with another helper function. (BTW: There are 2 commented lines in the patch that can be used to see the ready Conditions). 
Any suggestions?
msg190604 - (view) Author: Charles-François Natali (neologix) * (Python committer) Date: 2013-06-04 16:25
> Which just means that waiting on C conditions is C times more expensive than
> waiting on 1 currently is.  That seems reasonable enough to me, and anyway,
> I would expect C to be fairly small.

Waking up a single thread (through notify()) is currently O(1) (since
it's unqueued from the head of the deque). Here, removing a thread
from a wait queue other than the one from which it was signalled is
O(waiting threads).
msg190605 - (view) Author: João Bernardo (JBernardo) * Date: 2013-06-04 17:01
> Here, removing a thread
> from a wait queue other than the one from which it was signalled is
> O(waiting threads).

To be fair, You will probably never have more than a few hundred/thousand threads on a process. Usually you'll work under a few dozen threads.

To reduce the complexity on average, you could use a set, but `notify` no longer will be able to follow insertion order.

I was hoping it could be done later...
msg191448 - (view) Author: João Bernardo (JBernardo) * Date: 2013-06-19 06:27
(ping)
It would be nice to have the feature on 3.4.
What changes should I do to the patch? Is anyone else working on that?
msg193641 - (view) Author: João Bernardo (JBernardo) * Date: 2013-07-24 12:39
ping.
msg193642 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-07-24 12:48
Charles-François's point about the algorithmic complexity is legitimate, so I think he was actually waiting for you to amend your patch ;)
msg193643 - (view) Author: João Bernardo (JBernardo) * Date: 2013-07-24 13:03
> Charles-François's point about the algorithmic complexity is 
> legitimate, so I think he was actually waiting for you to amend
> your patch ;)

This doesn't seems to be the actual issue as it would require a big change for something that wasn't proven important... The old behavior is still O(1) in the new implementation. 

I might change that, but can someone give me an actual idea to implement that? Also, this can be done on another patch.


** The real problem **

I pointed out one issue about which conditions should be considered when waking up and there was no answer: http://bugs.python.org/msg190556

Also, Richard Oudkerk wrote he was expecting "wait_for_any() return a list": http://bugs.python.org/msg190597

I need to get feedback about the first one to change the second one.
msg193659 - (view) Author: Richard Oudkerk (sbt) * (Python committer) Date: 2013-07-24 15:47
IMHO

1) It should check all predicates.
2) It should return a list of ready conditions.
3) It should *not* accept a list of conditions.
4) from_condition() should be removed.

Also notify() should try again if releasing a waiter raises RuntimeError because it has already been released.  Otherwise notify() can be a noop even when there are threads waiting on the condition.

I would also put

    for cond in conditions:
	cond._remove_waiter(waiter)

in wait_for_any() in to a finally clause in case the wait was interrupted by KeyboardInterrupt.  (Accounting for KeyboardInterrupt everywhere is not feasible, but for blocking calls which can be interrupted I think we should try.)
msg193660 - (view) Author: João Bernardo (JBernardo) * Date: 2013-07-24 16:18
> 1) It should check all predicates.
OK. Maybe later there could be an option for customization?

> 2) It should return a list of ready conditions.
OK.

> 3) It should *not* accept a list of conditions.
The list option would be to simplify the "wait" method... Avoiding things like:  {cond: (lambda: True)}

> 4) from_condition() should be removed.
OK. Could the Lock object be made part of the api, then? like "self.lock" instead of "self._lock"

I'm OK with the rest of your post. Will make new patch
msg194442 - (view) Author: João Bernardo (JBernardo) * Date: 2013-08-05 00:17
I've been thinking about returning a list on "wait_for_any", but that way you will not be able to implement "wait_for" using it!

"wait_for" will return False on timeouts while "wait_for_any" will return a list with some conditions(evaluates to True).

Also, "wait_for" will show the result of the predicate when there's no timeout. It may clash with the boolean value of the list in some cases.

Suggestions?
msg194443 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-08-05 01:48
FWIW, I don't support adding this functionality.  I don't see precedents for Condition Variables behaving this way in other languages.  Also, I don't think it is worth the added complexity, learning curve, and maintenance burden.  Condition variables are used as primitive for other mutexes and I think we ought to keep them somewhat simple.

If someone wants to notify a specific waiter, then they have other options  such as using a separate condition variable that shares the same underlying lock (much as the code in the queue module does).  That approach is easy to reason about.
msg194449 - (view) Author: Charles-François Natali (neologix) * (Python committer) Date: 2013-08-05 05:33
> FWIW, I don't support adding this functionality.  I don't see precedents for
> Condition Variables behaving this way in other languages.  Also, I don't
> think it is worth the added complexity, learning curve, and maintenance
> burden.  Condition variables are used as primitive for other mutexes and I
> think we ought to keep them somewhat simple.
>
> If someone wants to notify a specific waiter, then they have other options
> such as using a separate condition variable that shares the same underlying
> lock (much as the code in the queue module does).  That approach is easy to
> reason about.

That's exactly what the point I was trying to make, but Raymond sums
it really nicely :-)
msg194482 - (view) Author: João Bernardo (JBernardo) * Date: 2013-08-05 14:35
Seems like "just because I never used I don't support". Boost C++ libraries has a wait_for_any functionality to synchronize futures. C# has a WaitAny in the WaitHandle class (like our Condition).

Another problem is: the Condition class cannot be easily subclassed because all the important bits are _protected... Can you add an interface for the "_waiters" list and "_lock" objects?? If you do that I'll be happy subclassing it.
msg334254 - (view) Author: Richard Whitehead (richardnwhitehead) Date: 2019-01-23 10:44
Condition.wait_for_any is still a desirable feature, e.g. to wait on multiple command queues, or a work queue and a command queue.
Is there any chance of pulling this into the latest version?
msg334260 - (view) Author: João Bernardo (JBernardo) * Date: 2019-01-23 14:17
Don't keep your hopes up. People here don't like implementing features they don't understand about even if they could verify elsewhere it works well.

My solution at the time was to create a decent "Condition" class based on the original one (subclassing this one is not safe). Feel free to use my patch above.
msg334287 - (view) Author: Richard Whitehead (richardnwhitehead) Date: 2019-01-24 09:55
Thanks João.

We are working on a medical prototype, and I wouldn't want to rely on our own version of something so fundamental without having a thorough test harness for it, which would obviously be quite time-consuming, and something of a dead-end.

I've worked around the issue now (the system pushing to a queue has to be given a Condition to set when they push, so that if a system listens on multiple queues it can give all the senders the same Condition), but it makes the architecture quite messy, just being able to wait on one of several Conditions would have been neater and less error-prone.

I suppose I expected to see this method because I'm familiar with the Windows API. But I checked and it is not present in the posix threading API, so there is some justification for peoples' reluctance to implement it in Python.

Thanks again,

Richard
msg350334 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-08-23 22:11
Marking this as closed/rejected for the reasons listed above.

Thank you all for the thoughtful and intelligent discussion.
History
Date User Action Args
2019-08-23 22:11:35rhettingersetstatus: open -> closed
resolution: rejected
messages: + msg350334

stage: resolved
2019-01-24 09:55:51richardnwhiteheadsetmessages: + msg334287
2019-01-23 14:17:24JBernardosetmessages: + msg334260
2019-01-23 10:44:03richardnwhiteheadsetnosy: + richardnwhitehead
messages: + msg334254
2013-08-05 20:35:18rhettingersetassignee: rhettinger
2013-08-05 14:35:25JBernardosetmessages: + msg194482
2013-08-05 05:33:19neologixsetmessages: + msg194449
2013-08-05 01:48:09rhettingersetmessages: + msg194443
2013-08-05 00:17:28JBernardosetmessages: + msg194442
2013-07-24 16:18:36JBernardosetmessages: + msg193660
2013-07-24 15:47:12sbtsetmessages: + msg193659
2013-07-24 13:03:42JBernardosetmessages: + msg193643
2013-07-24 12:48:18pitrousetmessages: + msg193642
2013-07-24 12:39:52JBernardosetmessages: + msg193641
2013-06-19 06:27:22JBernardosetmessages: + msg191448
2013-06-04 17:01:54JBernardosetmessages: + msg190605
2013-06-04 16:25:18neologixsetmessages: + msg190604
2013-06-04 14:39:00JBernardosetmessages: + msg190599
2013-06-04 14:06:39sbtsetmessages: + msg190597
2013-06-04 11:01:26JBernardosetmessages: + msg190594
2013-06-04 07:01:03neologixsetmessages: + msg190591
2013-06-03 18:56:37JBernardosetmessages: + msg190556
2013-05-31 06:51:55rhettingersetnosy: + rhettinger
2013-05-29 14:39:54JBernardosetfiles: + wait_for_any.patch
keywords: + patch
messages: + msg190310
2013-05-28 17:32:37JBernardosetmessages: + msg190228
2013-05-28 17:15:20sbtsetmessages: + msg190227
2013-05-28 15:52:38JBernardosetmessages: + msg190222
2013-05-28 15:37:15sbtsetmessages: + msg190221
2013-05-28 14:55:11JBernardosetmessages: + msg190216
2013-05-28 14:36:21sbtsetnosy: + sbt
messages: + msg190214
2013-05-28 11:10:05JBernardosetmessages: + msg190194
2013-05-28 11:03:34pitrousetnosy: + neologix
messages: + msg190193
2013-05-28 09:58:58serhiy.storchakasetnosy: + pitrou
2013-05-28 03:40:19JBernardocreate