deque class should include high-water mark

[roysmith]

BPO	4680
Nosy	@tim-one, @rhettinger, @pitrou

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2008-12-17.17:47:59.666>
created_at = <Date 2008-12-17.03:06:39.158>
labels = ['type-feature', 'library']
title = 'deque class should include high-water mark'
updated_at = <Date 2008-12-18.02:04:40.327>
user = 'https://bugs.python.org/roysmith'

bugs.python.org fields:

activity = <Date 2008-12-18.02:04:40.327>
actor = 'tim.peters'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2008-12-17.17:47:59.666>
closer = 'pitrou'
components = ['Library (Lib)']
creation = <Date 2008-12-17.03:06:39.158>
creator = 'roysmith'
dependencies = []
files = []
hgrepos = []
issue_num = 4680
keywords = []
message_count = 9.0
messages = ['77955', '77976', '77979', '77981', '77986', '77989', '77998', '78008', '78009']
nosy_count = 5.0
nosy_names = ['tim.peters', 'rhettinger', 'roysmith', 'pitrou', 'LambertDW']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = None
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue4680'
versions = ['Python 2.7']

[roysmith]

It would be nice if Queue.Queue included a way to access the high-water
mark, i.e. the largest value which qsize() has ever reached. This is
often useful when assessing application performance.

I am assuming this is cheap, i.e. O(1), to provide.

[pitrou]

It is probably easy enough to do so in a custom Queue subclass, and it's
too specialized to put in the standard library IMHO.
I'm closing the bug, another developer can reopen it if he thinks it is
truely useful.

[rhettinger]

I concur with Antoine.

[roysmith]

I'm suppose you could implement this in a subclass, but it would be
inefficient. You'd have to over-ride put() and get(), call qsize(),
then delegate to Base.put() and Base.get().

A cleaner solution would be in the C implementation of deque, in
Modules/collectionsmodule.c. There's just a couple of places where
queue->len gets incremented. All that needs to happen is add:

if (queue->len > queue->high_water_mark) {
    queue->high_water_mark = queue->len;
}

after each one and then add the appropriate accessor functions in deque
and Queue to expose it to users. The run-time cost is a couple of
machine instructions for each item added to the deque.

If I were to write the code and submit it, would you be willing to
accept it?

[rhettinger]

Will think about it for a bit. My initial inclination is against
because there have been no other such requests to instrument all the
fundamental data types, because it's not hard to add instrumentation
using your own pure python additions around size-mutating calls, because
it clutters the API, and because it's unclear whether a maximum-size
statistic has much utility.

For deques, should the clear() method zero-out the high-water mark? How
about the equivalent code where the contents are all popped-off (down to
zero size) before the structure is re-used?

[roysmith]

I'm not actually sure what the use case is for clear(). It's easy
enough to just create a new deque. If you can do that, why do you need
clear()? Since I don't ever see a reason anybody would want to call
clear(), I'm not 100% if it should reset the high-water mark or not. I
don't *think* it should, but I'm willing to believe that a use case
could exist which would make me change my mind about that.

Popping all the elements off the deque certainly should *not* reset the
high water mark. The whole point of tracking the high water mark is to
know if the consumer thread ever fell behind the producer thread (yes, I
realize queues could be used for non-threading purposes). It's
perfectly normal for the queue to drain completely at times, and there's
absolutely no reason this should affect the high-water mark.

You do raise a good question about whether all of the standard
containers should be instrumented. I don't know the answer to that.
Queues and, say, dicts are different beasts. It's common to use queues
where the putting-in and taking-out are asynchronous, and thus the
high-water mark is an indicator of overall application health. I don't
see that for dicts, or lists (well, maybe if used as a stack) or most
other kinds of containers.

[rhettinger]

FWIW, here's a trivial Queue subclass with instrumentation:

class HighWaterQueue(Queue):

    def _init(self, maxsize):
        Queue.__init__(self, maxsize)
        self.highwater = 0

    def _put(self, item):
        Queue._put(self, item)
        self.highwater = max(self.highwater, self._qsize())

[roysmith]

And, FWIW, I did figure out a use case for clear(). I create a queue and
pass it to two threads. One side or the other decides to abandon processing
of the events currently in the queue. I can't just create a new queue,
because you have no way to tell the other thread about it. You need to have
clear() to do this. And, no, it should not clear the high water mark.

As I see it, it comes down to this:

If you bury this in the C code inside deque(), it's very efficient compared
to the Python wrapper class. The downside is it makes the API larger than
it would otherwise be, to satisfy a use case with limited demand.

If you feel the efficiency gain doesn't justify the added complexity in the
API, I'm OK with that. I just didn't want this shot down on the basis of,
"He's asking us to invest the effort to write the code for something we
don't see a need for", hence the offer to write it myself. But, it's your
call if you want it or not.

[tim-one]

There's no need to keep asking -- this report was already rejected ;-)

Seriously, the efficiency argument carries no weight with me -- in 15
years of using Queue in a variety of applications, the time it takes to
.put and .get "here's a piece of work to do" descriptors is trivial
compared to the cost of /doing/ the "piece of work". A Python-coded
subclass would have been plenty fast enough in any of those apps
(assuming I ever wanted to track a highwater mark, which to date I never
have).