[Python-Dev] collections module
jcarlson at uci.edu
Sat Jan 10 01:40:22 EST 2004
> That doesn't demonstrate you had a sane design <wink>.
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.
> 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
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
You're right, I was too quick with my fingers when I did a block indent
> > 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 <wink>. 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
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
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):
r = self._l.acquire(block)
if not block and not r:
while block and len(self._q) == 0:
if timeout is not None:
if len(self._q) > 0:
a = self._q.get()
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
> > 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