collections.sortedtree
I have made a full implementation of a balanced tree and would like to know what the process is to have it considered for inclusion in Python 3. To summarize, the implementation closely parallels dict() features and resides in _collectionsmodule.c under the name collections.sortedtree. It uses solely the "<" operator to compare keys. I have chosen the AVL tree as an implementation technique. The views support a number of optional arguments: sorteddict.keys(reversed=False, start=unspecified, inclusive=True) The primary objective of having a balanced tree in the standard library is to support ordered access in an efficient manner. The typical applications would include timers (networking), aging (cache) and prefix patterns (routing). Marko
On 03/26/2014 01:31 PM, Marko Rauhamaa wrote:
I have made a full implementation of a balanced tree and would like to know what the process is to have it considered for inclusion in Python 3.
Open a ticket on the tracker [1], post your code to that ticket, sign the CLA [2], answer questions, etc., that come up in the code review. I believe Raymond Hettinger is the Guardian of the collections module; add him as nosy. -- ~Ethan~ [1] http://http://bugs.python.org [2] https://www.python.org/psf/contrib/contrib-form
Actually, the first step is publish it on PyPI, the second is to get a fair number of happy users there. The bar for getting something included into the stdlib is pretty high -- you need to demonstrate that there is a need *and* that having it as a 3rd party module is a problem. And that once it's in, (a) it will be stable, and (b) someone who cares about it and knows the code thoroughly is available maintain it for years. On Wed, Mar 26, 2014 at 1:53 PM, Ethan Furman <ethan@stoneleaf.us> wrote:
On 03/26/2014 01:31 PM, Marko Rauhamaa wrote:
I have made a full implementation of a balanced tree and would like to know what the process is to have it considered for inclusion in Python 3.
Open a ticket on the tracker [1], post your code to that ticket, sign the CLA [2], answer questions, etc., that come up in the code review.
I believe Raymond Hettinger is the Guardian of the collections module; add him as nosy.
-- ~Ethan~
[1] http://http://bugs.python.org [2] https://www.python.org/psf/contrib/contrib-form
_______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/ guido%40python.org
-- --Guido van Rossum (python.org/~guido)
Guido van Rossum <guido@python.org>:
Actually, the first step is publish it on PyPI, the second is to get a fair number of happy users there. The bar for getting something included into the stdlib is pretty high -- you need to demonstrate that there is a need *and* that having it as a 3rd party module is a problem.
I hear you about the process. About the need part, I'm wondering if you haven't felt it in implementing the timers for asyncio. I have had that need in several network programming projects and have ended up using my AVL tree implementation (C and Python). Well, time will tell if frequent canceled timers end up piling up the heap queue. Marko
I haven't felt it, heapq feels natural to me for this use case. :-) I'm aware of the issue of frequent cancelled timers, but chose to wait and see rather than preemptively fix it (only so many hours in a day). IIRC pyftplib has a clever cleanup algorithm that we can easily add if that usage pattern becomes popular. On Wed, Mar 26, 2014 at 2:36 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
Guido van Rossum <guido@python.org>:
Actually, the first step is publish it on PyPI, the second is to get a fair number of happy users there. The bar for getting something included into the stdlib is pretty high -- you need to demonstrate that there is a need *and* that having it as a 3rd party module is a problem.
I hear you about the process.
About the need part, I'm wondering if you haven't felt it in implementing the timers for asyncio. I have had that need in several network programming projects and have ended up using my AVL tree implementation (C and Python).
Well, time will tell if frequent canceled timers end up piling up the heap queue.
Marko
-- --Guido van Rossum (python.org/~guido)
for our stackless socket framework we have the same issue. Windows provides an opaque timer system where a timer can be cancelled by handle. But on linux one has to craft one's own. One thing with this particular use case is that a heapq is overkill for network timer. . For network timers a granularity of one second should typically be sufficient. Thus, one can implement a map of future times (in quantisized time, e.g. whole seconds) to sets of timers. A timer is then keyed by its quantisized due time plus its callback. Cancellation can then be O(1). From: Python-Dev [mailto:python-dev-bounces+kristjan=ccpgames.com@python.org] On Behalf Of Guido van Rossum Sent: 26. mars 2014 21:42 To: Marko Rauhamaa Cc: Python-Dev Subject: Re: [Python-Dev] collections.sortedtree I haven't felt it, heapq feels natural to me for this use case. :-) I'm aware of the issue of frequent cancelled timers, but chose to wait and see rather than preemptively fix it (only so many hours in a day). IIRC pyftplib has a clever cleanup algorithm that we can easily add if that usage pattern becomes popular. On Wed, Mar 26, 2014 at 2:36 PM, Marko Rauhamaa <marko@pacujo.net<mailto:marko@pacujo.net>> wrote: Guido van Rossum <guido@python.org<mailto:guido@python.org>>:
Actually, the first step is publish it on PyPI, the second is to get a fair number of happy users there. The bar for getting something included into the stdlib is pretty high -- you need to demonstrate that there is a need *and* that having it as a 3rd party module is a problem. I hear you about the process.
About the need part, I'm wondering if you haven't felt it in implementing the timers for asyncio. I have had that need in several network programming projects and have ended up using my AVL tree implementation (C and Python). Well, time will tell if frequent canceled timers end up piling up the heap queue.
On 3/26/2014 4:59 PM, Guido van Rossum wrote:
Actually, the first step is publish it on PyPI, the second is to get a fair number of happy users there. The bar for getting something included into the stdlib is pretty high -- you need to demonstrate that there is a need *and* that having it as a 3rd party module is a problem. And that once it's in, (a) it will be stable, and (b) someone who cares about it and knows the code thoroughly is available maintain it for years.
Perhaps the collections doc should mention that there are other specializes container types available on PyPI and either list some or point to a wiki page listing some. There must be at least 10 that could be included in such a list. -- Terry Jan Reedy
Terry Reedy <tjreedy@udel.edu>:
Perhaps the collections doc should mention that there are other specializes container types available on PyPI and either list some or point to a wiki page listing some. There must be at least 10 that could be included in such a list.
There *is* a relatively high threshold of importing C extensions from an external source. If I build an application making use of them and advise coworkers to use it, they would likely balk at having to compile them. Not all machines have a development toolkit. Furthermore: # which pip /usr/bin/which: no pip in (/usr/local/sbin:/usr/local/bin:/sbin:/bin:\ /usr/sbin:/usr/bin:/root/bin) # yum install pip No package pip available. Marko
On 27 Mar 2014 07:02, "Guido van Rossum" <guido@python.org> wrote:
Actually, the first step is publish it on PyPI, the second is to get a
fair number of happy users there. The bar for getting something included into the stdlib is pretty high -- you need to demonstrate that there is a need *and* that having it as a 3rd party module is a problem. And that once it's in, (a) it will be stable, and (b) someone who cares about it and knows the code thoroughly is available maintain it for years. The "why not a third party module?" bar also got a fair bit higher with Python 3.4 - by bundling pip, we have deliberately made third party modules easier to consume, thus weakening the convenience argument that applies to stdlib inclusion. The Python Packaging Authority are also working to reduce the barriers to distribution and consumption of C extensions, which will again weaken the argument for stdlib inclusion of third party C extensions. The metadata 2.0 efforts are also designed to streamline the process of conversion to platform specific formats like RPM. It's not that I don't see a sorted tree as valuable - I do. I just also see it as a fairly specialised type. The main case I could see being made for inclusion is if it made a major difference to the implementation of something else that was already in the stdlib. I believe that's where most other additions to the collections and types modules have come from in recent releases - we wanted to *use* them, and it seemed better to do the work to design an appropriate public API rather than keep them private (enum and generic function support arrived the same way, although we haven't actually redesigned pprint to rely on the latter yet). Cheers, Nick.
On Wed, Mar 26, 2014 at 1:53 PM, Ethan Furman <ethan@stoneleaf.us> wrote:
On 03/26/2014 01:31 PM, Marko Rauhamaa wrote:
I have made a full implementation of a balanced tree and would like to know what the process is to have it considered for inclusion in Python 3.
Open a ticket on the tracker [1], post your code to that ticket, sign
the CLA [2], answer questions, etc., that come up in the code review.
I believe Raymond Hettinger is the Guardian of the collections module;
add him as nosy.
-- ~Ethan~
[1] http://http://bugs.python.org [2] https://www.python.org/psf/contrib/contrib-form
_______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe:
https://mail.python.org/mailman/options/python-dev/guido%40python.org
-- --Guido van Rossum (python.org/~guido)
_______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/ncoghlan%40gmail.com
Nick Coghlan writes:
On 27 Mar 2014 07:02, "Guido van Rossum" <guido@python.org> wrote:
Actually, the first step is publish it on PyPI, the second is to get a fair number of happy users there. The bar for getting something included into the stdlib is pretty high
The "why not a third party module?" bar also got a fair bit higher with Python 3.4 - by bundling pip, we have deliberately made third party modules easier to consume, thus weakening the convenience argument that applies to stdlib inclusion.
Maybe. That depends on if you care about the convenience of folks who have to get new modules past Corporate Security, but it's easier to get an upgrade of the whole shebang. I don't think it's ever really been resolved whether they're a "typical case that won't go away" or a special group whose special needs should be considered. Steve
On Thu, Mar 27, 2014 at 10:11 AM, Stephen J. Turnbull <stephen@xemacs.org> wrote:
Nick Coghlan writes:
On 27 Mar 2014 07:02, "Guido van Rossum" <guido@python.org> wrote:
Actually, the first step is publish it on PyPI, the second is to get a fair number of happy users there. The bar for getting something included into the stdlib is pretty high
The "why not a third party module?" bar also got a fair bit higher with Python 3.4 - by bundling pip, we have deliberately made third party modules easier to consume, thus weakening the convenience argument that applies to stdlib inclusion.
Maybe. That depends on if you care about the convenience of folks who have to get new modules past Corporate Security, but it's easier to get an upgrade of the whole shebang. I don't think it's ever really been resolved whether they're a "typical case that won't go away" or a special group whose special needs should be considered.
Steve
And random pieces of C included in the standard library can be shuffled under the carpet under the disguise of upgrade or what are you suggesting?
On 27 March 2014 08:16, Maciej Fijalkowski <fijall@gmail.com> wrote:
And random pieces of C included in the standard library can be shuffled under the carpet under the disguise of upgrade or what are you suggesting?
The sort of thing that happens is that the relevant approvers will accept python-dev as a "trusted supplier" and then Python upgrades are acceptable subject to review of the changes, etc. For a new module, there is a whole other level of questions around how do we trust the person who developed the code, do we need to do a full code review, etc? It's a bit unfair to describe the process as "random pieces of C" being "shuffled under the carpet". (Although there probably are environments where that is uncomfortably close to the truth :-() Paul
On Thu, Mar 27, 2014 at 11:07 AM, Paul Moore <p.f.moore@gmail.com> wrote:
On 27 March 2014 08:16, Maciej Fijalkowski <fijall@gmail.com> wrote:
And random pieces of C included in the standard library can be shuffled under the carpet under the disguise of upgrade or what are you suggesting?
The sort of thing that happens is that the relevant approvers will accept python-dev as a "trusted supplier" and then Python upgrades are acceptable subject to review of the changes, etc. For a new module, there is a whole other level of questions around how do we trust the person who developed the code, do we need to do a full code review, etc?
It's a bit unfair to describe the process as "random pieces of C" being "shuffled under the carpet". (Although there probably are environments where that is uncomfortably close to the truth :-()
Paul
I just find "my company is stupid so let's work around it by putting stuff to python standard library" unacceptable argument for python-dev and all the python community.
On 27 March 2014 19:10, Maciej Fijalkowski <fijall@gmail.com> wrote:
On Thu, Mar 27, 2014 at 11:07 AM, Paul Moore <p.f.moore@gmail.com> wrote:
On 27 March 2014 08:16, Maciej Fijalkowski <fijall@gmail.com> wrote:
And random pieces of C included in the standard library can be shuffled under the carpet under the disguise of upgrade or what are you suggesting?
The sort of thing that happens is that the relevant approvers will accept python-dev as a "trusted supplier" and then Python upgrades are acceptable subject to review of the changes, etc. For a new module, there is a whole other level of questions around how do we trust the person who developed the code, do we need to do a full code review, etc?
It's a bit unfair to describe the process as "random pieces of C" being "shuffled under the carpet". (Although there probably are environments where that is uncomfortably close to the truth :-()
Paul
I just find "my company is stupid so let's work around it by putting stuff to python standard library" unacceptable argument for python-dev and all the python community.
Due diligence and prudent risk management are not stupid - most open source projects and small companies just don't have the luxury of worrying about them, as they're so far down the list of concerns that the additional risk of using arbitrary code downloaded off the internet doesn't even register. As organisations get larger, they have more to lose, so they typically start worrying about that kind of thing. Properly vetting software for licensing and potential security issues is expensive though, so they usually prefer to outsource that task to trusted providers (this is one of the key concepts that gets me paid). Contractual arrangements and brand reputations start to replace blind trust in upstream developers. Is this less efficient than full open collaboration? Yes, it is - the "verify" part of "trust, but verify" comes at a real cost in time and money. However, there are plenty of good reasons that phrase is "trust, but verify" rather than "trust unconditionally". You may choose not to care about those more cautious users, and that's fine - but they're still worth taking into account when making design decisions if you want to cross the marketing chasm from "early adopters" to everyone else. Regards, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On Thu, Mar 27, 2014 at 8:58 PM, Nick Coghlan <ncoghlan@gmail.com> wrote:
On 27 March 2014 19:10, Maciej Fijalkowski <fijall@gmail.com> wrote:
I just find "my company is stupid so let's work around it by putting stuff to python standard library" unacceptable argument for python-dev and all the python community.
Due diligence and prudent risk management are not stupid - most open source projects and small companies just don't have the luxury of worrying about them, as they're so far down the list of concerns that the additional risk of using arbitrary code downloaded off the internet doesn't even register.
I don't think anyone's saying it's stupid to be cautious, but more that it's stupid to blindly accept the latest python.org release and *not* accept something from another source. And if that's stupid, well, I'm stupid too - blindly accepting a whole lot of binary package updates because they're on ftp.au.debian.org, for instance. Why do I trust that, and not random sites on the internet? Because I trust that the Debian package maintainers to check what goes through, and I trust that there are people with reputations at stake, who won't want to send something dodgy through. It's not perfect, but it's a whole lot easier than checking every single package that goes through. ChrisA
On 27 March 2014 20:38, Chris Angelico <rosuav@gmail.com> wrote:
On Thu, Mar 27, 2014 at 8:58 PM, Nick Coghlan <ncoghlan@gmail.com> wrote:
On 27 March 2014 19:10, Maciej Fijalkowski <fijall@gmail.com> wrote:
I just find "my company is stupid so let's work around it by putting stuff to python standard library" unacceptable argument for python-dev and all the python community.
Due diligence and prudent risk management are not stupid - most open source projects and small companies just don't have the luxury of worrying about them, as they're so far down the list of concerns that the additional risk of using arbitrary code downloaded off the internet doesn't even register.
I don't think anyone's saying it's stupid to be cautious, but more that it's stupid to blindly accept the latest python.org release and *not* accept something from another source. And if that's stupid, well, I'm stupid too - blindly accepting a whole lot of binary package updates because they're on ftp.au.debian.org, for instance. Why do I trust that, and not random sites on the internet? Because I trust that the Debian package maintainers to check what goes through, and I trust that there are people with reputations at stake, who won't want to send something dodgy through. It's not perfect, but it's a whole lot easier than checking every single package that goes through.
Right - trusting the PSF and the Debian package review process are reasonable trade-offs at a personal level. However, it highlights why this is still a benefit of bringing things into the standard library: a lot of the overhead in review and audit processes is incurred based on the *number of components to be reviewed*, rather than the amount of code they contain. Other aspects of the overhead are incurred *per organisation trusted*. Inclusion in the standard library means not only bringing something under the PSF's "trust umbrella", but also within the core Python component. While we usually use corporate environments as our example, it applies equally to Linux distros - they generally have Python packaged already, and will eventually inherit standard library improvements. For third party packages, it requires someone to do the work to get them installed. Extending our trust to include a new component isn't to be done lightly, but it *does* genuinely save work in the long run for a whole lot of other people whenever we choose to do so, and that is the point Stephen was making. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On Thu, Mar 27, 2014 at 10:10 PM, Nick Coghlan <ncoghlan@gmail.com> wrote:
Extending our trust to include a new component isn't to be done lightly, but it *does* genuinely save work in the long run for a whole lot of other people whenever we choose to do so, and that is the point Stephen was making.
Exactly so. Blessing a module as part of the stdlib is an important mark of trust, and one that is most definitely not stupid to respect. (In case my previous message was ambiguous, I am fully in favour of people trusting python.org in this way, and fully understanding of people NOT trusting other sources, or at least not automatically.) ChrisA
Surely you can show empathy and still explain why it's not that easy. On Mar 27, 2014 2:11 AM, "Maciej Fijalkowski" <fijall@gmail.com> wrote:
On Thu, Mar 27, 2014 at 11:07 AM, Paul Moore <p.f.moore@gmail.com> wrote:
On 27 March 2014 08:16, Maciej Fijalkowski <fijall@gmail.com> wrote:
And random pieces of C included in the standard library can be shuffled under the carpet under the disguise of upgrade or what are you suggesting?
The sort of thing that happens is that the relevant approvers will accept python-dev as a "trusted supplier" and then Python upgrades are acceptable subject to review of the changes, etc. For a new module, there is a whole other level of questions around how do we trust the person who developed the code, do we need to do a full code review, etc?
It's a bit unfair to describe the process as "random pieces of C" being "shuffled under the carpet". (Although there probably are environments where that is uncomfortably close to the truth :-()
Paul
I just find "my company is stupid so let's work around it by putting stuff to python standard library" unacceptable argument for python-dev and all the python community.
Maciej Fijalkowski writes:
I just find "my company is stupid
I find labeling companies as "stupid", merely because they are cautious about what external code they allow their developers to depend on, unacceptable. And I'll go to the trouble of explaining why.
so let's work around it by putting stuff to python standard library" unacceptable argument for python-dev and all the python community.
Then you're completely missing the point. There are two issues in including code in the Python standard library. The first is technical excellence. You need to hurdle a certain bar, or the code won't go in. Furthermore, this bar includes a comprehensive set of regression tests. This implies that (1) human review of the code is on average much easier for CPython stdlib code than for PyPI code, and (2) a claim that no relevant-to-the-company behavior has actually changed is (again, on average) much more verifiable and plausible for CPython than for PyPI code. This is at least some convenience for *all* users, and a near necessity for some strictly controlled environments. In the latter, the "gatekeeper" is all too likely to say "PyPI? Bring us a CTO signoff that 'this module is essential', or forget it". The second is a purely economic tradeoff: is the value of Python aggregated across all our users better enhanced by restricting additions to the stdlib, and thus reducing future maintenance effort and (presumably) increasing the rate at which Python code is improved, or by improving the batteries that are included (with the opposite effects)? That's a judgment call.
On Fri, Mar 28, 2014 at 3:26 PM, Stephen J. Turnbull <stephen@xemacs.org> wrote:
This is at least some convenience for *all* users, and a near necessity for some strictly controlled environments. In the latter, the "gatekeeper" is all too likely to say "PyPI? Bring us a CTO signoff that 'this module is essential', or forget it".
Don't forget, of course, that there is a middle ground. Something that's really REALLY awesome on PyPI but isn't in the stdlib might be packaged by various Linux distros. If you use Debian, typing "apt-cache pkgnames python-" (or using tab completion on an "apt-get install") will show you a veritable ton of packages, many of which are originally off PyPI. Even if you don't actually use that distribution, it might be worth telling the gatekeeper that Debian and/or Red Hat have indicated trust for some particular version of some particular package, which might help get over that hump. But it's still going to be a much bigger hump than "it's in CPython 3.4". ChrisA
Chris Angelico writes:
Don't forget, of course, that there is a middle ground. Something that's really REALLY awesome on PyPI but isn't in the stdlib might be packaged by various Linux distros.
Oh, agreed, and any organization that cares that much will already have the RHEL or Ubuntu LTS (etc, those are the ones my buddies use) contract. CPython is not the only certification that is trusted (to whatever degree) by users of CPython. But forget Debian and Gentoo at least -- all it takes get in to those distros is a license (free) and a maintainer (at application time). And they'll even wink at the license given sufficient user demand. Steve
Maciej Fijalkowski writes:
On Thu, Mar 27, 2014 at 10:11 AM, Stephen J. Turnbull <stephen@xemacs.org> wrote:
Maybe. That depends on if you care about the convenience of folks who have to get new modules past Corporate Security, but it's easier to get an upgrade of the whole shebang. I don't think it's ever really been resolved whether they're a "typical case that won't go away" or a special group whose special needs should be considered.
Steve
And random pieces of C included in the standard library can be shuffled under the carpet under the disguise of upgrade or what are you suggesting?
CPython doesn't do stuff like that; C code in CPython gets careful review, and can hardly be called "random". PyPI packages do do stuff like that. Not all of them by far, but to tell the difference you need to review line-by-line. So I'm simply saying (as Nick did) that it is often easier to get changes past a corporate bureaucracy if they are certified by inclusion in CPython (not to exclude PyPy or Jython, but the corporate consideration is about a specific distribution), than if it's a random package on PyPI.
On 27 March 2014 18:11, Stephen J. Turnbull <stephen@xemacs.org> wrote:
Nick Coghlan writes:
On 27 Mar 2014 07:02, "Guido van Rossum" <guido@python.org> wrote:
Actually, the first step is publish it on PyPI, the second is to get a fair number of happy users there. The bar for getting something included into the stdlib is pretty high
The "why not a third party module?" bar also got a fair bit higher with Python 3.4 - by bundling pip, we have deliberately made third party modules easier to consume, thus weakening the convenience argument that applies to stdlib inclusion.
Maybe. That depends on if you care about the convenience of folks who have to get new modules past Corporate Security, but it's easier to get an upgrade of the whole shebang. I don't think it's ever really been resolved whether they're a "typical case that won't go away" or a special group whose special needs should be considered.
I'm all too well aware of this particular problem (although thankfully don't have to deal with it myself any more), and it's a key part of why I said "a fair bit higher" rather than "insurmountable" :) Such environments *do* usually have procedures to get additional open source software approved, it's just a pain. That pain then becomes another factor to take into account deciding between using a simpler solution, rolling your own custom solution, or tackling your organisation's module approval process. That said, getting approval is definitely easier when the request is to trust "the Python Software Foundation" vs "J. Random Programmer's account on GitHub", so yes, it still counts in favour of sufficiently compelling stdlib additions. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
Nick Coghlan writes:
On 27 March 2014 18:11, Stephen J. Turnbull <stephen@xemacs.org> wrote:
I don't think it's ever really been resolved whether they're a "typical case that won't go away" or a special group whose special needs should be considered.
That said, getting approval is definitely easier when the request is to trust "the Python Software Foundation" vs "J. Random Programmer's account on GitHub", so yes, it still counts in favour of sufficiently compelling stdlib additions.
I note that this *still* doesn't resolve the alternatives presented above.<wink/> I hasten to add, it doesn't need to be done *now*. Yes, I do think it matters. Steve
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/27/2014 04:11 AM, Stephen J. Turnbull wrote:
Maybe. That depends on if you care about the convenience of folks who have to get new modules past Corporate Security, but it's easier to get an upgrade of the whole shebang. I don't think it's ever really been resolved whether they're a "typical case that won't go away" or a special group whose special needs should be considered.
ISTM that such concerns should be addressed via some kind of paid support contract (a la RHEL), and not used to drive decisions for the underlying FLOSS project. The existence of aggregated resources from such a support organization would then be relevant to the "include / exclude" discussion: presumably the support organization could fund the maintenance of the otherwise-excluded module based on its customers' paid-for needs. Tres. - -- =================================================================== Tres Seaver +1 540-429-0999 tseaver@palladion.com Palladion Software "Excellence by Design" http://palladion.com -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iEYEARECAAYFAlM1jtQACgkQ+gerLs4ltQ5OOgCdHeOjBjpfJ1w5mkAWZsajflWK U3wAmgIxnc7BFIaoouQ0kdkCgoF+lMr3 =yhYm -----END PGP SIGNATURE-----
Tres Seaver writes:
On 03/27/2014 04:11 AM, Stephen J. Turnbull wrote:
Maybe. That depends on if you care about the convenience of folks who have to get new modules past Corporate Security, but it's easier to get an upgrade of the whole shebang. I don't think it's ever really been resolved whether they're a "typical case that won't go away" or a special group whose special needs should be considered.
ISTM that such concerns should be addressed via some kind of paid support contract (a la RHEL), and not used to drive decisions for the underlying FLOSS project. The existence of aggregated resources from such a support organization would then be relevant to the "include / exclude" discussion: presumably the support organization could fund the maintenance of the otherwise-excluded module based on its customers' paid-for needs.
So, let me get this straight: you think that one user should pay Red Hat to vet the package for RHEL, and another user should pay to get it into Ubuntu, and another user to get it into SuSE? And then the distros should all pay lawyers to write contracts to make sure that nobody is paying too much for support in the stdlib when they eventually get it in? (Except the customers, of course, everybody will be happy if *they* pay more than they need to.) Seems to me that putting it into stdlib in the first place makes more sense, if it's going to end up there at all. Another way to put it is, we need a better way to fund support of "routine maintenance" (ie, the unfun parts) than negotiating it module by module.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/28/2014 11:57 AM, Stephen J. Turnbull wrote:
So, let me get this straight: you think that one user should pay Red Hat to vet the package for RHEL, and another user should pay to get it into Ubuntu, and another user to get it into SuSE? And then the distros should all pay lawyers to write contracts to make sure that nobody is paying too much for support in the stdlib when they eventually get it in? (Except the customers, of course, everybody will be happy if *they* pay more than they need to.)
No, I'm arguing that *if* the concerns you articulate represent a significant number of "corporate* customers (i.e., a "market"), their interests would be better represented by *some* organization who is paid to reflect them. RHEL and Ubuntu LTS could potentially be contributors to that pool. I'm mostly arguing the FLOSS project should feel free to ignore high-maintenance-cost commercial concerns until those concerns bring either blook (funded developer time) or treasure (pooled to pay for the same time) to the table to pay for them. Tres. - -- =================================================================== Tres Seaver +1 540-429-0999 tseaver@palladion.com Palladion Software "Excellence by Design" http://palladion.com -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iEYEARECAAYFAlM1oPAACgkQ+gerLs4ltQ52ZgCg06AobjcZa1lGBDtFzRk6IjEK 6DkAnj33xAkqcDUjLGaT9NP4YtZdkAos =62VL -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/28/2014 12:18 PM, Tres Seaver wrote:
I'm mostly arguing the FLOSS project should feel free to ignore high-maintenance-cost commercial concerns until those concerns bring either blook (funded developer time) or treasure (pooled to pay for the same time) to the table to pay for them.
Dangit, s/blook/blood/ Tres. - -- =================================================================== Tres Seaver +1 540-429-0999 tseaver@palladion.com Palladion Software "Excellence by Design" http://palladion.com -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iEYEARECAAYFAlM1ocMACgkQ+gerLs4ltQ6k8ACgm+ycaOaqZGsefJU5iu9kL4bS 1e4AmQHq/vb4Q6GV/MNuCZQr4HKG/JER =8fLu -----END PGP SIGNATURE-----
On 28 March 2014 16:22, Tres Seaver <tseaver@palladion.com> wrote:
On 03/28/2014 12:18 PM, Tres Seaver wrote:
I'm mostly arguing the FLOSS project should feel free to ignore high-maintenance-cost commercial concerns until those concerns bring either blook (funded developer time) or treasure (pooled to pay for the same time) to the table to pay for them.
Dangit,
s/blook/blood/
Rats. I thought I'd just learned a new word. Regardless of reality, I think "blook" should be a real word :-) Paul
On 2014-03-28 16:39, Paul Moore wrote:
On 28 March 2014 16:22, Tres Seaver <tseaver@palladion.com> wrote:
On 03/28/2014 12:18 PM, Tres Seaver wrote:
I'm mostly arguing the FLOSS project should feel free to ignore high-maintenance-cost commercial concerns until those concerns bring either blook (funded developer time) or treasure (pooled to pay for the same time) to the table to pay for them.
Dangit,
s/blook/blood/
Rats. I thought I'd just learned a new word. Regardless of reality, I think "blook" should be a real word :-)
Yes, and it should mean "funded developer time on or for an open source project".
Tres Seaver writes:
I'm mostly arguing the FLOSS project
You mean "a (mostly) volunteer-supported" FLOSS project, no?
should feel free to ignore
Given the above qualification, you can put a period here, as far as I'm concerned. My question is "what does *Python* *want* to ignore?", not "is it allowed to ignore?"
high-maintenance-cost
What "high" maintenance cost? A stdlib addition is a marginal increase in cost. Do too many, and it's a serious burden, of course. So there needs to be *some* hurdle that any addition must clear, and that barrier becomes higher in proportion to the "code base to developers who actually do maintenance" ratio. But I think the question should be "how high?" not "can they pay?"
commercial concerns until those concerns bring either blook (funded developer time) or treasure (pooled to pay for the same time) to the table to pay for them.
I really don't think commercial profit as the motive for a request, or ability to pay, should be an important reason to *ignore* user wants. This smacks of the proposals for "ransom software", which (a) sort of turns the principle of *volunteer* FLOSS on its head (if that doesn't bother most of the developers, no problem, but for one it bothers *me*), and (b) doesn't actually work AFAICT (it's not quite the same as "crowdfunding", which does work). It's rather the reverse: I believe we should be prepared to deal with the conflict of interest that results when *some* of the developers are offered money to provide *cater* to such concerns[1] where the community doesn't think the benefit is that high. Footnotes: [1] Should not be that hard in *this* community, but that is the issue IMO.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/29/2014 03:46 AM, Stephen J. Turnbull wrote:
I really don't think commercial profit as the motive for a request, or ability to pay, should be an important reason to *ignore* user wants.
We've already got corrosion on the terminals the leaky batteries-included stdlib (ssl, anyone?). I see nothing wrong with rejecting additional batteries proposed purely FBO organizations who have the kind of policies you describe, but don't contribute blood-or-treasure toward their maintenannce (*especially* because they are in the "enterprise" space, and could be expected to pay for that kind of support). This kind of "Python-in-a-tie" discussion is probably moot for any version of Python that python-dev actually cares about, BTW: by the time such organizations get around to using 3.5, it likely won't even be getting security releases from the core developers. Tres. - -- =================================================================== Tres Seaver +1 540-429-0999 tseaver@palladion.com Palladion Software "Excellence by Design" http://palladion.com -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iEYEARECAAYFAlM3Q2wACgkQ+gerLs4ltQ7Y5QCdGhrpenkXJnRXoseVabQDwJHX 0zcAn0tAf6iHT276oxjZS/ZhPu49wF8M =6Gci -----END PGP SIGNATURE-----
On 29 March 2014 01:57, Stephen J. Turnbull <stephen@xemacs.org> wrote:
Another way to put it is, we need a better way to fund support of "routine maintenance" (ie, the unfun parts) than negotiating it module by module.
Yes, yes we do, and there *are* people working on that (see https://wiki.python.org/moin/PythonSoftwareFoundation/BoardCandidates2014) :) Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On Wed, Mar 26, 2014, at 13:31, Marko Rauhamaa wrote:
I have made a full implementation of a balanced tree and would like to know what the process is to have it considered for inclusion in Python 3.
It's not a bad idea. (I believe others have proposed an red-black tree.) Certainly, it requires a PEP and a few months of bikesheding, though.
On Mar 26, 2014, at 01:55 PM, Benjamin Peterson wrote:
It's not a bad idea. (I believe others have proposed an red-black tree.) Certainly, it requires a PEP and a few months of bikesheding, though.
Generally, PEPs aren't necessary for simple or relatively uncontroversial additions to existing modules or the stdlib. If you're proposing an addition to an existing module, file a tracker issue and nosy the module expert (for collections, it's Raymond Hettinger[1]). Others may see the new issue and decide to nosy themselves in if they want to provide additional feedback and input. If you're proposing an entirely new module, it's best to publish it first on PyPI, get lots of users, and listen to their feedback as you evolve the library. Once you feel like it's had plenty of time to bake as a third party module *and* the API is sufficiently stable that you won't mind the Python stdlib 18 month development cycle, then you can propose that it be included in Python. Cheers, -Barry [1] http://docs.python.org/devguide/experts.html
On Wed, Mar 26, 2014, at 14:25, Barry Warsaw wrote:
On Mar 26, 2014, at 01:55 PM, Benjamin Peterson wrote:
It's not a bad idea. (I believe others have proposed an red-black tree.) Certainly, it requires a PEP and a few months of bikesheding, though.
Generally, PEPs aren't necessary for simple or relatively uncontroversial additions to existing modules or the stdlib.
I would have said that, too, several years ago, but I think we've been requiring (or using anyway) PEPs for a lot more things now. OrderedDict had a PEP for example. I'm not sure if that's a good thing or not.
On Mar 26, 2014, at 02:27 PM, Benjamin Peterson wrote:
I would have said that, too, several years ago, but I think we've been requiring (or using anyway) PEPs for a lot more things now. OrderedDict had a PEP for example.
I'm not sure if that's a good thing or not.
Hmm, me neither! I guess if someone *wants* to go through the PEP gauntlet, I won't stop them. It builds character. -Barry
On Mar 26, 2014, at 5:30 PM, Barry Warsaw <barry@python.org> wrote:
On Mar 26, 2014, at 02:27 PM, Benjamin Peterson wrote:
I would have said that, too, several years ago, but I think we've been requiring (or using anyway) PEPs for a lot more things now. OrderedDict had a PEP for example.
I'm not sure if that's a good thing or not.
Hmm, me neither! I guess if someone *wants* to go through the PEP gauntlet, I won't stop them. It builds character.
-Barry _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/donald%40stufft.io
Is that what it’s called? “character” >:] ----------------- Donald Stufft PGP: 0x6E3CBCE93372DCFA // 7C6B 7C5D 5E2B 6356 A926 F04F 6E3C BCE9 3372 DCFA
On Wed, 26 Mar 2014 17:37:40 -0400 Donald Stufft <donald@stufft.io> wrote:
On Mar 26, 2014, at 5:30 PM, Barry Warsaw <barry@python.org> wrote:
On Mar 26, 2014, at 02:27 PM, Benjamin Peterson wrote:
I would have said that, too, several years ago, but I think we've been requiring (or using anyway) PEPs for a lot more things now. OrderedDict had a PEP for example.
I'm not sure if that's a good thing or not.
Hmm, me neither! I guess if someone *wants* to go through the PEP gauntlet, I won't stop them. It builds character.
-Barry _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/donald%40stufft.io
Is that what it’s called? “character” >:]
Preferably unicode. Regards Antoine.
On 03/26/2014 02:46 PM, Antoine Pitrou wrote:
On Wed, 26 Mar 2014 17:37:40 -0400 Donald Stufft wrote:
On Mar 26, 2014, at 5:30 PM, Barry Warsaw wrote:
I guess if someone *wants* to go through the PEP gauntlet, I won't stop them. It builds character.
Is that what it’s called? “character” >:]
Preferably unicode.
Indeed, a lot more swear symbols available in Unicode! ;) -- ~Ethan~
On Wed, Mar 26, 2014 at 2:27 PM, Benjamin Peterson <benjamin@python.org>wrote:
On Wed, Mar 26, 2014, at 14:25, Barry Warsaw wrote:
On Mar 26, 2014, at 01:55 PM, Benjamin Peterson wrote:
It's not a bad idea. (I believe others have proposed an red-black tree.) Certainly, it requires a PEP and a few months of bikesheding, though.
Generally, PEPs aren't necessary for simple or relatively uncontroversial additions to existing modules or the stdlib.
I would have said that, too, several years ago, but I think we've been requiring (or using anyway) PEPs for a lot more things now. OrderedDict had a PEP for example.
This is probably a natural outcome of the rising popularity of Python in the last few years. Much more users, more core developers, more at stake...
I'm not sure if that's a good thing or not.
YMMV but IMHO this is a good thing. PEPs provide a single point of reference to a discussion that would otherwise be spread over multiple centi-threads (not that PEPs don't create centi-threads, but they outlive them in a way). Eli
On 03/26/2014 07:11 PM, Eli Bendersky wrote:
On Wed, Mar 26, 2014 at 2:27 PM, Benjamin Peterson wrote:
I'm not sure if that's a good thing or not.
YMMV but IMHO this is a good thing. PEPs provide a single point of reference to a discussion that would otherwise be spread over multiple centi-threads (not that PEPs don't create centi-threads, but they outlive them in a way).
Plus the PEP can help prevent multiple mega-threads as the same idea is revisited again and again and again... -- ~Ethan~
Eli Bendersky writes:
On Wed, Mar 26, 2014 at 2:27 PM, Benjamin Peterson <benjamin@python.org> wrote:
I would have said that, too, several years ago, but I think we've been requiring (or using anyway) PEPs for a lot more things now.
YMMV but IMHO this is a good thing.
FWIW I was just talking to Matz yesterday, and asked him about it. He said he thought PEPs worked great for Python (in the context of explain that his (and Ruby's) style is different). Just-ask-the-nearest-independent-opinion-ly y'rs,
On 27 March 2014 12:11, Eli Bendersky <eliben@gmail.com> wrote:
On Wed, Mar 26, 2014 at 2:27 PM, Benjamin Peterson <benjamin@python.org> wrote:
I'm not sure if that's a good thing or not.
YMMV but IMHO this is a good thing. PEPs provide a single point of reference to a discussion that would otherwise be spread over multiple centi-threads (not that PEPs don't create centi-threads, but they outlive them in a way).
From my point of view, the primary purpose of the PEP process is to provide a way for us to finally say "yes" to controversial proposals that have valid arguments against them. When things are obviously good ideas that don't impose a big maintenance burden, nobody really objects if we skip the PEP process (that isn't always a good thing - directory and zipfile execution flew under the radar for years because it was such a neat idea that Guido approved it directly in the issue, and then we forgot to mention it in the 2.6 What's New).
Some ideas aren't obviously good, or a suitable API isn't obvious, or they impose a major additional maintenance burden, or they require a change to our development policies. In those cases, the PEP process allows us to collectively ask the question "Is this worth the hassle?". Cases like the restoration of binary interpolation support, or my proposal to backport network security features, also showcase how the PEP process can be used to refine the *question* so the PEP champion is forced to figure out what they *really* want, and propose a solution that clearly solves that specific problem, rather than overreaching and asking for more than is needed. (This is also reflected in the relative fates of the current matrix multiplication proposal and previous more general proposals) With the introduction of the BDFL-Delegate system, and then the decision last year to give the "Discussions-To" header a bit more force and allow groups like the Python Packaging Authority to make use of the PEP process independently of python-dev, the PEP process is also becoming more streamlined, making it more effective in its role as a tool for establishing consensus - there's less need to convince someone to drop a veto without a PEP, as the PEP process itself is getting less painful. Most of the time when I hear people say "the PEP process is too difficult", I eventually find that what they really mean is "learning the kinds of things that python-dev are likely to be worried about, and ensuring that the PEP adequately addresses their concerns, and listening to feedback, and reconsidering what I actually want, and revising my proposal, such that they eventually say yes is too time consuming". Helping people to learn exactly how to navigate that process is actually one of the main roles of python-ideas these days, although we don't do a good job (at all) of advertising that fact. Regards, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On Thu, 27 Mar 2014 20:32:02 +1000 Nick Coghlan <ncoghlan@gmail.com> wrote:
Most of the time when I hear people say "the PEP process is too difficult", I eventually find that what they really mean is "learning the kinds of things that python-dev are likely to be worried about, and ensuring that the PEP adequately addresses their concerns, and listening to feedback, and reconsidering what I actually want, and revising my proposal, such that they eventually say yes is too time consuming".
Well, the PEP process *is* difficult and not only because you have to learn the kinds of things that python-dev are likely to be worried about. Getting a PEP accepted for a feature is much more work than getting a feature accepted in the bug tracker. Regards Antoine.
On 28 March 2014 21:12, Antoine Pitrou <solipsis@pitrou.net> wrote:
On Thu, 27 Mar 2014 20:32:02 +1000 Nick Coghlan <ncoghlan@gmail.com> wrote:
Most of the time when I hear people say "the PEP process is too difficult", I eventually find that what they really mean is "learning the kinds of things that python-dev are likely to be worried about, and ensuring that the PEP adequately addresses their concerns, and listening to feedback, and reconsidering what I actually want, and revising my proposal, such that they eventually say yes is too time consuming".
Well, the PEP process *is* difficult and not only because you have to learn the kinds of things that python-dev are likely to be worried about. Getting a PEP accepted for a feature is much more work than getting a feature accepted in the bug tracker.
Oh, agreed. It's only the "too" qualifier that I question - I'm not sure how much easier we could make it before it ceased to serve its filtering purpose. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On Wed, Mar 26, 2014 at 1:55 PM, Benjamin Peterson <benjamin@python.org> wrote:
On Wed, Mar 26, 2014, at 13:31, Marko Rauhamaa wrote:
I have made a full implementation of a balanced tree and would like to know what the process is to have it considered for inclusion in Python 3.
It's not a bad idea. (I believe others have proposed an red-black tree.) Certainly, it requires a PEP and a few months of bikesheding, though.
I'd recommend a plain binary tree (for random keys), red-black tree and treap (both for ordered or mostly-ordered keys, where red-black tree gives low operation duration standard deviation, and treap gives low average operation duration). https://en.wikipedia.org/wiki/Binary_search_tree#Performance_comparisons http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/ It'd likely make sense to have either a pure python implementation, or pure python and C-extended, so that Pypy and Jython can share the feature with CPython.
Dan Stromberg <drsalists@gmail.com>:
It'd likely make sense to have either a pure python implementation, or pure python and C-extended, so that Pypy and Jython can share the feature with CPython.
Jython can build directly on Java's native SortedMap implementation. The API should not tie it to a tree. Optimizations and refactorings should be allowed. Only O(log N) worst-case behavior should be mandated. (And now I notice I named this thread wrong; I named my thingy collections.sorteddict.) Marko
On Wed, Mar 26, 2014 at 3:52 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
Dan Stromberg <drsalists@gmail.com>:
It'd likely make sense to have either a pure python implementation, or pure python and C-extended, so that Pypy and Jython can share the feature with CPython.
Jython can build directly on Java's native SortedMap implementation. The API should not tie it to a tree. Optimizations and refactorings should be allowed. Only O(log N) worst-case behavior should be mandated.
Rare worst cases should be fine for a good reason - see python dict's.
On Wed, Mar 26, 2014 at 9:55 PM, Benjamin Peterson <benjamin@python.org>wrote:
On Wed, Mar 26, 2014, at 13:31, Marko Rauhamaa wrote:
I have made a full implementation of a balanced tree and would like to know what the process is to have it considered for inclusion in Python 3.
It's not a bad idea. (I believe others have proposed an red-black tree.) Certainly, it requires a PEP and a few months of bikesheding, though.
Not to mention discussion about whether it shouldn't just be an existing PyPI package, like http://pypi.python.org/pypi/blist, rather than a new implementation. -- Thomas Wouters <thomas@python.org> Hi! I'm an email virus! Think twice before sending your email to help me spread!
Thomas Wouters <thomas@python.org>:
Not to mention discussion about whether it shouldn't just be an existing PyPI package, like http://pypi.python.org/pypi/blist, rather than a new implementation.
I'm fine with any implementation as long as it is in the standard library. Marko
On Wed, 26 Mar 2014 22:31:56 +0200 Marko Rauhamaa <marko@pacujo.net> wrote:
The primary objective of having a balanced tree in the standard library is to support ordered access in an efficient manner. The typical applications would include timers (networking), aging (cache)
Wouldn't a heapq work as well for those two? Regards Antoine.
Antoine Pitrou <solipsis@pitrou.net>:
Wouldn't a heapq work as well for those two?
In my experience, networking entities typically start a timer at each interaction and cancel the pending one. So you have numerous timers that virtually never expire. You might have 100 interactions per second, each canceling and restarting a 10-minute timer. I don't know first hand if that causes heap queues to cause measurable heap or CPU pressure. Marko
On Wed, 26 Mar 2014 23:41:42 +0200 Marko Rauhamaa <marko@pacujo.net> wrote:
Antoine Pitrou <solipsis@pitrou.net>:
Wouldn't a heapq work as well for those two?
In my experience, networking entities typically start a timer at each interaction and cancel the pending one. So you have numerous timers that virtually never expire. You might have 100 interactions per second, each canceling and restarting a 10-minute timer.
I don't know first hand if that causes heap queues to cause measurable heap or CPU pressure.
Each individual heapq operation (push or pop) will be O(log n). That's not different from a balanced search tree (although of course the constant multiplier may vary). Regards Antoine.
Antoine Pitrou <solipsis@pitrou.net>:
Marko Rauhamaa <marko@pacujo.net> wrote:
In my experience, networking entities typically start a timer at each interaction and cancel the pending one. So you have numerous timers that virtually never expire. You might have 100 interactions per second, each canceling and restarting a 10-minute timer.
Each individual heapq operation (push or pop) will be O(log n). That's not different from a balanced search tree (although of course the constant multiplier may vary).
Yes, but if I have 1000 connections with one active timer each. The size of my sorted tree is 1000 timer objects. There are typically no expiries to react to. If the canceled timer lingers in the heapq till its expiry (in 10 minutes), the size is 100 * 10 * 60 = 60,000. The CPU has to wake up constantly to clear the expired timers. In practice, none of that might matter. Marko
On Wed, 26 Mar 2014 23:57:27 +0200 Marko Rauhamaa <marko@pacujo.net> wrote:
Antoine Pitrou <solipsis@pitrou.net>:
Marko Rauhamaa <marko@pacujo.net> wrote:
In my experience, networking entities typically start a timer at each interaction and cancel the pending one. So you have numerous timers that virtually never expire. You might have 100 interactions per second, each canceling and restarting a 10-minute timer.
Each individual heapq operation (push or pop) will be O(log n). That's not different from a balanced search tree (although of course the constant multiplier may vary).
Yes, but if I have 1000 connections with one active timer each. The size of my sorted tree is 1000 timer objects. There are typically no expiries to react to.
If the canceled timer lingers in the heapq till its expiry (in 10 minutes), the size is 100 * 10 * 60 = 60,000. The CPU has to wake up constantly to clear the expired timers.
Ideally, I think you should be able to replace the cancelled item with the last item in the heap and then fix the heap in logarithmic time, but the heapq API doesn't seem to provide a way to do this. Regards Antoine.
On Wed, Mar 26, 2014 at 6:02 PM, Antoine Pitrou <solipsis@pitrou.net> wrote:
On Wed, 26 Mar 2014 23:57:27 +0200 Marko Rauhamaa <marko@pacujo.net> wrote:
Antoine Pitrou <solipsis@pitrou.net>:
Marko Rauhamaa <marko@pacujo.net> wrote:
In my experience, networking entities typically start a timer at each interaction and cancel the pending one. So you have numerous timers that virtually never expire. You might have 100 interactions per second, each canceling and restarting a 10-minute timer.
Each individual heapq operation (push or pop) will be O(log n). That's not different from a balanced search tree (although of course the constant multiplier may vary).
Yes, but if I have 1000 connections with one active timer each. The size of my sorted tree is 1000 timer objects. There are typically no expiries to react to.
If the canceled timer lingers in the heapq till its expiry (in 10 minutes), the size is 100 * 10 * 60 = 60,000. The CPU has to wake up constantly to clear the expired timers.
Ideally, I think you should be able to replace the cancelled item with the last item in the heap and then fix the heap in logarithmic time, but the heapq API doesn't seem to provide a way to do this.
Heaps provide easy access to the first item, but you can't find the last element without scanning the whole thing. With a heap, I think the best approach to the timer-cancellation problem is to periodically rebuild the heap from the non-cancelled items (Tornado keeps a count of cancellations and rebuilds the heap when the number of cancelled timeouts is half of the total. If cancellations are infrequent then they're just left in the heap until their time comes due). -Ben
Regards
Antoine. _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/ben%40bendarnell.com
On Wed, 26 Mar 2014 18:14:19 -0400 Ben Darnell <ben@bendarnell.com> wrote:
If the canceled timer lingers in the heapq till its expiry (in 10 minutes), the size is 100 * 10 * 60 = 60,000. The CPU has to wake up constantly to clear the expired timers.
Ideally, I think you should be able to replace the cancelled item with the last item in the heap and then fix the heap in logarithmic time, but the heapq API doesn't seem to provide a way to do this.
Heaps provide easy access to the first item, but you can't find the last element without scanning the whole thing.
I was talking about the last element, not the largest. The point of replacing with the last element is that shrinking is O(1). Regards Antoine.
Yeah, so the pyftp fix is to keep track of how many timers were cancelled, and if the number exceeds a threshold it just recreates the heap, something like heap = [x for x in heap if not x.cancelled] heapify(heap) On Wed, Mar 26, 2014 at 3:02 PM, Antoine Pitrou <solipsis@pitrou.net> wrote:
On Wed, 26 Mar 2014 23:57:27 +0200 Marko Rauhamaa <marko@pacujo.net> wrote:
Antoine Pitrou <solipsis@pitrou.net>:
Marko Rauhamaa <marko@pacujo.net> wrote:
In my experience, networking entities typically start a timer at each interaction and cancel the pending one. So you have numerous timers that virtually never expire. You might have 100 interactions per second, each canceling and restarting a 10-minute timer.
Each individual heapq operation (push or pop) will be O(log n). That's not different from a balanced search tree (although of course the constant multiplier may vary).
Yes, but if I have 1000 connections with one active timer each. The size of my sorted tree is 1000 timer objects. There are typically no expiries to react to.
If the canceled timer lingers in the heapq till its expiry (in 10 minutes), the size is 100 * 10 * 60 = 60,000. The CPU has to wake up constantly to clear the expired timers.
Ideally, I think you should be able to replace the cancelled item with the last item in the heap and then fix the heap in logarithmic time, but the heapq API doesn't seem to provide a way to do this.
Regards
Antoine. _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/guido%40python.org
-- --Guido van Rossum (python.org/~guido)
True. I've long since added a heapdel() to our local fork. a heappop(idx=0) extension would do the same I can provide a patch if there is interest. K Ideally, I think you should be able to replace the cancelled item with the last item in the heap and then fix the heap in logarithmic time, but the heapq API doesn't seem to provide a way to do this. Regards Antoine.
On Thu, 27 Mar 2014 09:25:05 +0000 Kristján Valur Jónsson <kristjan@ccpgames.com> wrote:
True. I've long since added a heapdel() to our local fork. a heappop(idx=0) extension would do the same I can provide a patch if there is interest.
I think either of them would be cool. I don't know it would be approved by Raymond or whoever else. Regards Antoine.
27.03.14 00:16, Guido van Rossum написав(ла):
Yeah, so the pyftp fix is to keep track of how many timers were cancelled, and if the number exceeds a threshold it just recreates the heap, something like
heap = [x for x in heap if not x.cancelled] heapify(heap)
See also http://bugs.python.org/issue13451 which proposes such approach for the sched module.
Guido van Rossum <guido@python.org>:
Yeah, so the pyftp fix is to keep track of how many timers were cancelled, and if the number exceeds a threshold it just recreates the heap, something like
heap = [x for x in heap if not x.cancelled] heapify(heap)
I measured my target use case with a simple emulation on my linux PC. The simple test case emulates this scenario: Start N connections at frequency F and have each connection start a timer T. Then, rotate over the connections at the same frequency F restarting timer T. Stop after a duration that is much greater than T. Four different timer implementations were considered: HEAPQ: straight heapq HEAPQ*: heapq with the pyftp fix (reheapify whenever 80% of the outstanding timers have been canceled) SDICT: sorteddict (my C implementation) PyAVL: Python AVL tree (my implementation) Here are the results: N = 1000, F = 100 Hz, T = 10 min, duration 1 hr ============================================= Virt Res max len() urs sys CPU MB MB s s % ============================================= HEAPQ 22 16 60001 21.5 4.3 0.7 HEAPQ* 11 7 5000 18.4 4.2 0.6 SDICT 11 6 1000 18.2 3.9 0.6 PyAVL 11 6 1000 39.3 3.6 1.2 ============================================= N = 10000, F = 1000 Hz, T = 10 min, duration 1 hr ============================================= Virt Res max len() urs sys CPU MB MB s s % ============================================= HEAPQ 125 120 600044 223.0 25.8 6.9 HEAPQ* 21 16 50000 186.8 30.0 6.0 SDICT 15 10 10000 196.6 25.7 6.2 PyAVL 16 11 10000 412.5 22.3 12.1 ============================================= Conclusions: * The CPU load is almost identical in HEAPQ, HEAPQ* and SDICT. * HEAPQ* is better than HEAPQ because of the memory burden. * PyAVL is not all that bad compared with SDICT. Marko
On Wed, Mar 26, 2014 at 3:02 PM, Antoine Pitrou <solipsis@pitrou.net> wrote:
Ideally, I think you should be able to replace the cancelled item with the last item in the heap and then fix the heap in logarithmic time, but the heapq API doesn't seem to provide a way to do this.
Due to way the heapq is implemented, it can't provide an efficient API for removing an arbitrary item. Swapping with the last element allows you to efficiently remove the item at a particular index, but you first need to find the current index of an item, which requires a O(n) scan. To provide efficient cancellation and removal, a heap implementation needs some way to efficiently answer "What is the current index of this item?". There are a couple of ways to achieve that, but they all require more storage than heapq's list-based approach. -- Daniel Stutzbach
On Thu, 27 Mar 2014 08:50:01 -0700 Daniel Stutzbach <stutzbach@google.com> wrote:
Due to way the heapq is implemented, it can't provide an efficient API for removing an arbitrary item. Swapping with the last element allows you to efficiently remove the item at a particular index, but you first need to find the current index of an item, which requires a O(n) scan.
To provide efficient cancellation and removal, a heap implementation needs some way to efficiently answer "What is the current index of this item?". There are a couple of ways to achieve that, but they all require more storage than heapq's list-based approach.
You are right. I was assuming the index is already known. Regards Antoine.
-----Original Message----- From: Python-Dev [mailto:python-dev- bounces+kristjan=ccpgames.com@python.org] On Behalf Of Antoine Pitrou Sent: 27. mars 2014 15:53 To: python-dev@python.org Subject: Re: [Python-Dev] collections.sortedtree
On Thu, 27 Mar 2014 08:50:01 -0700 Daniel Stutzbach <stutzbach@google.com> wrote:
To provide efficient cancellation and removal, a heap implementation needs some way to efficiently answer "What is the current index of this item?". There are a couple of ways to achieve that, but they all require more storage than heapq's list-based approach.
You are right. I was assuming the index is already known.
Regards
Antoine.
Yes. But for rare occurrances, it is annoying that heap.remove(item) is more expensive than it needs to be. It is a reasonable operation, just like list.remove() is. I'll be willing to experiment with extending the heapq. methods to take an optional "map" argument. 'map' would be a dict, mapping objects in the heap to indices. If provided, each of the heapq methouds would take care to update the map of any objects that it touches with the current index of the object. Usage could be something like: heap = [] map = {} def insert(i): heapq.heappush(heap, I, map) def pop(i): return heapq.heappop(heap, map) def remove(i): heapq.heapdel(heap, map[i], map) K
On Fri, Mar 28, 2014 at 09:20:35AM +0000, Kristján Valur Jónsson wrote:
I'll be willing to experiment with extending the heapq. methods to take an optional "map" argument. 'map' would be a dict, mapping objects in the heap to indices. If provided, each of the heapq methouds would take care to update the map of any objects that it touches with the current index of the object.
Usage could be something like:
heap = [] map = {} def insert(i): heapq.heappush(heap, I, map)
def pop(i): return heapq.heappop(heap, map)
def remove(i): heapq.heapdel(heap, map[i], map)
If you're going to make heapq more complex, wouldn't it be better to encapsulate the logic into a Heap class? heapq should remain the same, and Heap could (if accepted) move into collections. And should this discussion move to python-ideas? -- Steven
On Wed, Mar 26, 2014 at 1:31 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
sorteddict.keys(reversed=False, start=unspecified, inclusive=True)
FYI - there are already several packages on PyPi that provide a sorteddict: https://pypi.python.org/pypi?%3Aaction=search&term=sorteddict&submit=search -- Daniel Stutzbach (I wrote one of them)
On Mar 26, 2014, at 1:31 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
I have made a full implementation of a balanced tree and would like to know what the process is to have it considered for inclusion in Python 3.
To summarize, the implementation closely parallels dict() features and resides in _collectionsmodule.c under the name collections.sortedtree. It uses solely the "<" operator to compare keys. I have chosen the AVL tree as an implementation technique.
FWIW, I think there may be room for a sorted collection somewhere in the standard library. As others have said, the best place to start is by putting a module on PyPi to let it mature and to compete with other approaches to the problem. Here are a few random thoughts on the over-all idea: * An AVL balanced tree isn't the only solution or necessarily the best solution to the problem. Tree nodes tend to take more space than denser structures and they have awful cache locality (these are the same reasons that deques use doubly-linked blocks rather than a plain doubly linked lists). * Another approach I have experimented with uses lazy sorting. That lets insertion be an O(1) step and incurs a one-time sorting cost upon the next lookup (and because Timsort exploits partial orderings, this can be very cheap). A lazy sorted list is dense and sequentially ordered in memory (reducing space overhead, taking full advantage of cache locality and memory controller auto-prefetch, and providing fast iteration speed by not needing to chase pointers). The lazy sort approach works best in applications that spend most of the time doing lookups and have only infrequent deletions and insertions. * The name of the tool probably should not be sortedtree. Ideally, the tool should be named for what it does, not how it does it (for the most part, users don't need to know whether the underlying implementation is a red-black tree, b-tree, judy array, sqlite database, or lazy list). That is why (I think) that Python dicts are called dicts rather than hash tables (the implementation) or an associative array (the computer science term for the abstract datatype). * There are plenty of data structures that have had good utility and popularity outside of the standard library. I that it is a good thing that blists, numpy arrays, databases, and panda dataframes all live outside the standard library. Those tools are easier to maintain externally and it is easier for you to keep control over the design. Remember the saying, "the standard library is where code goes to die" (and I would add that it should already be mature (or nearly dead) by the time it gets there). * That said, it is a reasonable possibility that the standard library would benefit from some kind sorted collection (the idea comes up from time to time). Raymond Hettinger
Raymond Hettinger <raymond.hettinger@gmail.com>:
* An AVL balanced tree isn't the only solution or necessarily the best solution to the problem. Tree nodes tend to take more space than denser structures and they have awful cache locality (these are the same reasons that deques use doubly-linked blocks rather than a plain doubly linked lists).
Maybe. The key is the API. The implementation underneath should be changeable. For example, Jython would probably use SortedTree to implement it. Performance tests should help decide when an implementation is switched for a more efficient one. In some of my tests, I haven't seen any significant performance differences between RB trees and AVL trees, for example. The blist implementation, which I have taken a quick glance at, buys cache locality at the price of block copying; I have no data to decide if the tradeoff is a good one. The main thing, IMO, is to get one sorted dictionary in.
* The name of the tool probably should not be sortedtree.
Correct. That was a mistake on the Subject line. In the code, it's sorteddict.
* That said, it is a reasonable possibility that the standard library would benefit from some kind sorted collection (the idea comes up from time to time).
Yes. As a user, I have craved for an implementation, which is readily available in Java and the linux kernel, for example. Marko
On Fri, Mar 28, 2014 at 2:54 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
The blist implementation, which I have taken a quick glance at,
buys cache locality at the price of block copying; I have no data to
decide if the tradeoff is a good one.
There's actually a compile-time parameter so that you can tune the tradeoff by adjusting how wide each of blist's nodes are. Like most tradeoffs, whether it's good or bad depends on what you're trying to do. RedBlack trees are very similar to a B-tree with a node-width of 4: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Analogy_to_B-trees_of_or... blist's sorteddict is written in Python on top of the blist type (which is written in C). Because of the Python layer, it's slower by a constant factor compared to pure-C implementations in microbenchmarks. -- Daniel Stutzbach
On Fri, Mar 28, 2014 at 5:48 PM, Daniel Stutzbach <stutzbach@google.com> wrote:
On Fri, Mar 28, 2014 at 2:54 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
The blist implementation, which I have taken a quick glance at,
buys cache locality at the price of block copying; I have no data to decide if the tradeoff is a good one.
There's actually a compile-time parameter so that you can tune the tradeoff by adjusting how wide each of blist's nodes are. Like most tradeoffs, whether it's good or bad depends on what you're trying to do. RedBlack trees are very similar to a B-tree with a node-width of 4: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Analogy_to_B-trees_of_or...
blist's sorteddict is written in Python on top of the blist type (which is written in C). Because of the Python layer, it's slower by a constant factor compared to pure-C implementations in microbenchmarks.
It grieves me a bit to say this, and blist and blist's sorteddict are probably a good tool for an appropriate job, but blist's sorteddict type is quite a bit slower than several pure python implementations of dictionaries with ordered keys. In my testing blist.sorteddict was dead last for random keys, and wasn't last but was still significantly underperforming for sequential keys (outperforming only binary tree and scapegoat tree, behind all others): http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/2014...
On Fri, Mar 28, 2014 at 6:45 PM, Dan Stromberg <drsalists@gmail.com> wrote:
In my testing blist.sorteddict was dead last for random keys, and wasn't last but was still significantly underperforming for sequential keys (outperforming only binary tree and scapegoat tree, behind all others):
http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/2014...
Could you post the source code for your test tools, so that I can reproduce them locally and understand the results better? I think I'm confused about what you're trying to measure. It looks like the tests perform get and set operations, neither of which required a sorted dict. Wouldn't a good comparison of sorted dict types include at least one operation that relies on the sorted property? Possibly I've misunderstood how your tests work. -- Daniel Stutzbach
vne On Mon, Mar 31, 2014 at 2:01 PM, Daniel Stutzbach <stutzbach@google.com> wrote:
On Fri, Mar 28, 2014 at 6:45 PM, Dan Stromberg <drsalists@gmail.com> wrote:
In my testing blist.sorteddict was dead last for random keys, and wasn't last but was still significantly underperforming for sequential keys (outperforming only binary tree and scapegoat tree, behind all others):
http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/2014...
Could you post the source code for your test tools, so that I can reproduce them locally and understand the results better?
I think I'm confused about what you're trying to measure. It looks like the tests perform get and set operations, neither of which required a sorted dict. Wouldn't a good comparison of sorted dict types include at least one operation that relies on the sorted property? Possibly I've misunderstood how your tests work.
The code is at http://stromberg.dnsalias.org/svn/python-tree-and-heap-comparison/trunk/ You're right, I'm not comparing find_min, find_max, generate_in_order or generate_reverse_order. The first two tend to be the same as find_arbitrary. I've been thinking about trying to import some C extension module trees, and just ignoring them if they fail to import. But I haven't. Trunk only compares pure python implementations - even for treap, which has a cython version. I tossed my changes after checking blist. Trunk does operations/second.
participants (24)
-
Antoine Pitrou -
Barry Warsaw -
Ben Darnell -
Benjamin Peterson -
Chris Angelico -
Dan Stromberg -
Daniel Stutzbach -
Donald Stufft -
Eli Bendersky -
Ethan Furman -
Guido van Rossum -
Kristján Valur Jónsson -
Maciej Fijalkowski -
Marko Rauhamaa -
MRAB -
Nick Coghlan -
Paul Moore -
Raymond Hettinger -
Serhiy Storchaka -
Stephen J. Turnbull -
Steven D'Aprano -
Terry Reedy -
Thomas Wouters -
Tres Seaver