merge-slicing: explain an alternative implementation in a comments
It has a better time complexity so a C implementation would likely out perform
the current implementation
--- a/hgext3rd/evolve/stablerange.py Fri Mar 24 06:36:12 2017 +0100
+++ b/hgext3rd/evolve/stablerange.py Fri Mar 24 06:24:02 2017 +0100
@@ -424,9 +424,9 @@
# revision we needs
result.append((bottomrevs[-1], rangeid[1]))
else:
- bheads = set(bottomrevs)
parentrevs = cl.parentrevs
parents = self._parents
+ bheads = set(bottomrevs)
du = bheads.difference_update
reachableroots = repo.changelog.reachableroots
for r in bottomrevs:
@@ -442,6 +442,31 @@
start = self.depthrev(repo, h) - len(hrevs)
entry = (h, start)
result.append(entry)
+
+ # Talking about python code being slow, the following code is an
+ # alternative implementation.
+ #
+ # It complexity is better since is does a single traversal on the
+ # bottomset. However since it is all python it end up being
+ # slower.
+ # I'm keeping it here as an inspiration for a future C version
+ # branches = []
+ # for current in reversed(bottomrevs):
+ # ps = parents(current, parentrevs)
+ # found = False
+ # for brevs, bexpect in branches:
+ # if current in bexpect:
+ # found = True
+ # brevs.append(current)
+ # bexpect.discard(current)
+ # bexpect.update(ps)
+ # if not found:
+ # branches.append(([current], set(ps)))
+ # for revs, __ in reversed(branches):
+ # head = revs[0]
+ # index = self.depthrev(repo, head) - len(revs)
+ # result.append((head, index))
+
# top part is trivial
top = (rangeid[0], globalindex)
result.append(top)