[PATCH] scmutil: speed up revrange

[Bryan O'Sullivan]

# HG changeset patch
# User Bryan O'Sullivan <bryano at fb.com>
# Date 1334030483 25200
# Node ID 92585a4bb230ebae012480ae5163cfd44362a028
# Parent  335f75e60efcd8a885a03692443785bb8eba9ad3
scmutil: speed up revrange

This improves the performance of "hg log -l1" from 0.21 seconds to
0.07 on a Linux kernel tree.

Ideally we could use xrange instead of range on the most common
path, and thus avoid a ton of allocation, but xrange doesn't support
slice-based indexing.

diff -r 335f75e60efc -r 92585a4bb230 mercurial/scmutil.py
--- a/mercurial/scmutil.py	Mon Apr 09 17:22:45 2012 -0700
+++ b/mercurial/scmutil.py	Mon Apr 09 21:01:23 2012 -0700
@@ -540,11 +540,17 @@
                 start = revfix(repo, start, 0)
                 end = revfix(repo, end, len(repo) - 1)
                 step = start > end and -1 or 1
-                for rev in xrange(start, end + step, step):
-                    if rev in seen:
-                        continue
-                    seen.add(rev)
-                    l.append(rev)
+                if not seen and not l:
+                    # by far the most common path
+                    l = range(start, end + step, step)
+                    continue
+                newrevs = set(xrange(start, end + step, step))
+                if seen:
+                    newrevs.difference_update(seen)
+                    seen.union(newrevs)
+                else:
+                    seen = newrevs
+                l.extend(sorted(newrevs, reverse=start > end))
                 continue
             elif spec and spec in repo: # single unquoted rev
                 rev = revfix(repo, spec, None)