[PATCH 2 of 2] cleanup: use the deque type where appropriate
Adrian Buehlmann
adrian at cadifra.com
Tue May 15 14:18:49 CDT 2012
On 2012-05-15 19:46, Bryan O'Sullivan wrote:
> # HG changeset patch
> # User Bryan O'Sullivan <bryano at fb.com>
> # Date 1337103983 25200
> # Node ID bbd6f7e937abe78790e26c28163f2ec05535c7a9
> # Parent 4c5bca2a37682d39974eb38b5b313597a981b50a
> cleanup: use the deque type where appropriate
>
> There have been quite a few places where we pop elements off the
> front of a list. This can turn O(n) algorithms into something more
> like O(n**2). Python has provided a deque type that can do this
> efficiently since at least 2.4.
>
> As an example of the difference a deque can make, it improves
> perfancestors performance on a Linux repo from 0.50 seconds to 0.36.
>
> diff --git a/mercurial/hbisect.py b/mercurial/hbisect.py
> --- a/mercurial/hbisect.py
> +++ b/mercurial/hbisect.py
> @@ -11,7 +11,7 @@
> import os, error
> from i18n import _
> from node import short, hex
> -import util
> +import collections, util
>
> def bisect(changelog, state):
> """find the next node (if any) for testing during a bisect search.
> @@ -69,10 +69,10 @@
>
> # build children dict
> children = {}
> - visit = [badrev]
> + visit = collections.deque([badrev])
It for sure doesn't matter here at all, and you can call me a nitpicker,
but using a tuple for construction seems a tiny bit faster:
$ python -m timeit -s "import collections" "collections.deque([1])"
1000000 loops, best of 3: 0.402 usec per loop
$ python -m timeit -s "import collections" "collections.deque((1,))"
1000000 loops, best of 3: 0.295 usec per loop
tuple also beats
$ python -m timeit -s "import collections" "collections.deque().append(1)"
1000000 loops, best of 3: 0.304 usec per loop
More information about the Mercurial-devel
mailing list