[Python-Dev] collections module

[Josiah Carlson]

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

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

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

 - Josiah