Patchwork [4,of,7] dagop: just compare with the last value to deduplicate input of revancestors()

login
register
mail settings
Submitter Yuya Nishihara
Date June 22, 2017, 3:52 p.m.
Message ID <3b2bded55cfab4dd1307.1498146737@mimosa>
Download mbox | patch
Permalink /patch/21615/
State Accepted
Headers show

Comments

Yuya Nishihara - June 22, 2017, 3:52 p.m.
# HG changeset patch
# User Yuya Nishihara <yuya@tcha.org>
# Date 1497743949 -32400
#      Sun Jun 18 08:59:09 2017 +0900
# Node ID 3b2bded55cfab4dd13079cbf1d0354c1462d5c18
# Parent  d6cdc30de037445140bf2e0f8c7f7a1d2b6bc7ac
dagop: just compare with the last value to deduplicate input of revancestors()

Since we're using a max heap, the current rev should be a duplicate only
if it equals to the previous one. We don't have to maintain the whole seen
set.

  # reverse(ancestors(tip)) using hg repo
  0) 0.086420
  1) 0.081051

Patch

diff --git a/mercurial/dagop.py b/mercurial/dagop.py
--- a/mercurial/dagop.py
+++ b/mercurial/dagop.py
@@ -37,15 +37,15 @@  def _genrevancestors(repo, revs, followf
     if inputrev is not None:
         heapq.heappush(pendingheap, -inputrev)
 
-    seen = set()
+    lastrev = None
     while pendingheap:
         currev = -heapq.heappop(pendingheap)
         if currev == inputrev:
             inputrev = next(irevs, None)
             if inputrev is not None:
                 heapq.heappush(pendingheap, -inputrev)
-        if currev not in seen:
-            seen.add(currev)
+        if currev != lastrev:
+            lastrev = currev
             yield currev
             try:
                 for prev in cl.parentrevs(currev)[:cut]: