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()

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).

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.

> 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

> 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.

> 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.

> 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.

> 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>))

> 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.

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.

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.

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).

> 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.

> 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.

> 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?

> 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).

> 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...

(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?

ping.

Charles-François's point about the algorithmic complexity is legitimate, so I think he was actually waiting for you to amend your patch ;)

> 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.

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.)

> 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

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?

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.

> 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 :-)

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.

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?

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.

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

Marking this as closed/rejected for the reasons listed above.

Thank you all for the thoughtful and intelligent discussion.