[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