Patchwork [2,of,4] revset: make addset able to chain more than two unordered iterators

login
register
mail settings
Submitter Yuya Nishihara
Date May 19, 2015, 12:18 p.m.
Message ID <990823292a267aeaecf7.1432037899@mimosa>
Download mbox | patch
Permalink /patch/9167/
State Changes Requested
Delegated to: Pierre-Yves David
Headers show

Comments

Yuya Nishihara - May 19, 2015, 12:18 p.m.
# HG changeset patch
# User Yuya Nishihara <yuya@tcha.org>
# Date 1431756377 -32400
#      Sat May 16 15:06:17 2015 +0900
# Node ID 990823292a267aeaecf73f0e9912781d0b40eeb1
# Parent  e71e42ed67100df4d69386ba8e8ce7f0767638db
revset: make addset able to chain more than two unordered iterators

This can reduce the stack depth of chained OR operations from O(n) to O(1)
for unordered iteration.

0) 1ef96a3b8b89
1) drop redundant filteredset from right-hand side set of "or" operation
2) unnested OR ops (this series)

revset #0: 0:1099 + 1000:2099 + 2000:3099 + 3000:4099 + 4000:5099
0) wall 0.014229 comb 0.020000 user 0.020000 sys 0.000000 (best of 193)
1) wall 0.005280 comb 0.000000 user 0.000000 sys 0.000000 (best of 516)
2) wall 0.005025 comb 0.010000 user 0.010000 sys 0.000000 (best of 555)

Patch

diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -3106,12 +3106,17 @@  class addset(abstractsmartset):
             if self._genlist:
                 return iter(self._genlist)
             def arbitraryordergen():
-                for r in self._r1:
+                rs = self._subsets[0]
+                for r in rs:
                     yield r
-                inr1 = self._r1.__contains__
-                for r in self._r2:
-                    if not inr1(r):
-                        yield r
+                seen = rs
+                inseen = seen.__contains__
+                for rs in self._subsets[1:]:
+                    for r in rs:
+                        if not inseen(r):
+                            yield r
+                    seen += rs
+                    inseen = seen.__contains__
             return arbitraryordergen()
         # try to use our own fast iterator if it exists
         self._trysetasclist()