[Python-Dev] collections module (original) (raw)

Josiah Carlson jcarlson at uci.edu
Sat Jan 10 01:40:22 EST 2004

That doesn't demonstrate you had a sane design .

Indeed, which is why the software was never released publically. I still need to get around to rewriting it, it has only been 2 years.

> The below is quite fast for most reasonable numbers of threads - it > does wake all threads up that were waiting, but I find it considerably > clearer, and can be done with a single synchronization primitive.

I think you mean a single synchronization instance variable.

Right.

As I noted last time, Queue was written before Condition variables-- or even the threading module --existed. (Note that it still imports the ancient low-level 'thread' module instead.) There's no question about condvars being clearer than raw locks for anything fancier than a plain critical section, and I'd be in favor of rewriting Queue.py to use condvars, provided nothing important is lost.

I don't believe it would be too difficult to modify what I provided to be in the style of the Queue module methods for allowing different types of sequences.

It may also be a desireable option to be able to pass in a class with put/get/len methods, so that Queue wouldn't need to be subclassed when the object already exists.

The way the code uses it, -1 would work fine -- even on 128-bit machines .

Actually it does need it. In put, there is a comparison that makes all the difference: len(self._q) < self._m, which would always return false, if the underlying sequence wasn't braindead.

> try: > self.l.acquire()

That line should go before the "try:" (if the acquire() attempt raises an exception for some reason, the "finally:" block will try to release an unacquired condvar, raising a new exception, and so masking the real problem).

You're right, I was too quick with my fingers when I did a block indent for try/finally.

> while block and len(self.q) == self.m: > self.l.wait() > self.l.release() > self.l.acquire()

Note that the last two lines there aren't necessary. Or, if they are, this is much more obscure than Queue.py . wait() releases the associated lock as part of waiting, and reacquires it as part of waking up.

looks at docs I could have sworn the docs said that a release and acquire was necessary, but I suppose the last time I read the docs for Condition was 2 years ago shakes cobwebs out of head, so I probably messed something up along the way.

It's not clear why this isn't plain notify(). Note that if self.q.put()

You're right, it should be notify.

raises an exception (for example, MemoryError if the box is plain of out memory), no notify is done, and so other threads blocked in put() and/or get() that could make progress aren't woken up. Queue.py endures excruciating pain to try to prevent endcase glitches like that.

Part of the simplification here is due to the use of a condvar. A great deal more is due to that it's simply ignoring some of the bells and whistles Queue.py has sprouted: a defined protocol for subclassing so that "the real queue" can have any concrete representation and semantics (e.g., it's easy to make a stack-like Queue subclass now, or a priority-queue-like Queue subclass) without the subclasses needing to know anything about the thread convolutions); optional timeouts on get and put; and anal attention paid to the consequences of "unexpected" exceptions.

It would be relatively easy to drop in any object with put, get and len methods. Adding code to be additionally anal about "unexpected" exceptions may or may not be too bad, depending on the level of "anal attention" required.

In terms of having a timeout, I did not notice the functionality because I was looking on docs for 2.2, I see them now. Adding timeouts when using Condition() is fairly easy. Farther down is a snippet for both this functionality and the fast on nowait option.

A possible advantage of the condvar logic is that it doesn't raise Full unless the queue is actually full, or Empty unless the queue is actually empty. The current code can raise those now for another reason, and users have a hard time understanding this: self.mutex just doesn't happen to be instantly available. OTOH, that's also a feature, taking "don't block" very seriously, not even waiting for a queue operation that happens to take a long time. For example, one thread gets into self.q.put(item) and loses its timeslice. Some other thread tries to do put(item, block=False). Under Queue.py today, the latter thread raises Full at once, because it can't instantly acquire the mutex. Under the condvar scheme, it does block, and may block for a long time (the former thread has to get enough timeslices to finish its q.put(item), get through its self.l.release(), and the latter thread may not acquire the condvar even then (any number of other threads may get it first)). The tradeoffs here are murky, but the condvar scheme would be a change in actual behavior in such cases, so they can't be ignored.

A quick modification to put/get alters it to be fast in those cases where you don't want to block.

def get(self, block=1, timeout=None):
    if FAST:
        r = self._l.acquire(block)
        if not block and not r:
            raise Empty
    else:
        self._l.acquire()
    try:
        while block and len(self._q) == 0:
            self._l.wait(timeout)
            if timeout is not None:
                break
        if len(self._q) > 0:
            a = self._q.get()
            self._l.notify()
            return a
        raise Empty
    finally:
        self._l.release()

Setting FAST to 1 would result in the put/get to be as fast as Queue when you want it to be, but setting FAST to 0 would give you the earlier behavior.

> I agree completely, most locking mechanisms are slow as hell. There > are some tricks that can be done with critical sections (or its > equivalent on multiple platforms); an article was written about > multithreaded locking performance on IBM at least a year ago. I > wonder if any of those performance-tuning semantics can be used with > the underlying locks in Python.

[and later] > One thing that bothered me about using the three mutexes as given > in Queue.Queue is that it relies on the fact that a thread can > unlock an underlying thread.lock that it didn't acquire. To me, > this is strange behavior. All those are related. If you port Python to a new thread implementation, there's only one synchronization object you have to implement in C: thread.lock. While it may seem strange to you, it's a "universal"

"One lock to rule them all" isn't strange at all. I was just commenting that even using threading.Lock (the same as thread.allocate_lock) with acquire/release, seem to be slow. Is it really that the underlying locks are slow, or is the thread switching such a performance killer that lock performance doesn't matter?

> Oh, by adding a second Condition(), you don't need to notify everyone > and can replace the 'while' uses with 'if'. Even faster.

You can't replace 'while' with 'if' then (think about it, and note that the docs explicitly warn that .notify() may wake more than one thread), and

I forgot about that. Maybe that is why I my brain said you had to release and acquire after wait, probably.

More information about the Python-Dev mailing list