Path: csiph.com!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From: Paul Rubin <no.email@nospam.invalid>
Newsgroups: comp.lang.python
Subject: Re: how to convert code that uses cmp to python3
Date: Fri, 08 Apr 2016 00:03:53 -0700
Organization: A noiseless patient Spider
Lines: 12
Message-ID: <87y48ooa3q.fsf@nightsong.com>
References: <57064D0D.1030701@rece.vub.ac.be> <CAPTjJmrGiQS9uhFU-+TQ4nUWQ2p4gmJoQitMotS0Ob--qm1iWg@mail.gmail.com> <mailman.22.1460031736.2253.python-list@python.org> <87a8l5p6ek.fsf@nightsong.com> <874mbdi5ai.fsf@elektro.pacujo.net> <8760vtp1d3.fsf@nightsong.com> <87pou0hgqe.fsf@elektro.pacujo.net> <ne7ij7$4ab$1@ger.gmane.org> <mailman.66.1460096435.2253.python-list@python.org> <87zit4fv6r.fsf@elektro.pacujo.net>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: mx02.eternal-september.org; posting-host="52eac348160ce62b68e4635eee7cc854"; logging-data="27244"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+pnn01ATa6q4OXQcQldZgs"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux)
Cancel-Lock: sha1:scWyUWXbZ5imUmr8boJ49zpHOR0= sha1:AtZGP7CW20pHvZAd6G+MJkmru00=
Xref: csiph.com comp.lang.python:106655

Marko Rauhamaa <marko@pacujo.net> writes:
> On the surface, the garbage collection scheme looks dubious, but maybe
> it works perfect in practice.

It looked suspicious at first glance but I think it is ok.  Basically on
at most every timeout event (scheduling, expiration, or cancellation),
it does an O(n) operation (scanning and re-heapifying the timeout list)
with probability O(1/n) where n is the queue size, which itself changes
(by 0, +1 or -1) when a timeout event happens.  That is, its overhead is
a constant factor unless I'm missing something.  There are some
efficiency gains possible but it seems par for the course for Python
code.