Merge lp:~mwhudson/loggerhead/less-stupid-whole-history-redundancy into lp:loggerhead

[Michael Hudson-Doyle]

[Michael Hudson-Doyle (mwhudson)]

Hi Paul,

This branches cuts down on the amount of things that the wholehistorycache hangs on to -- it turns out that all of the things loggerhead needs from the wholehistorycache can be quickly (about 0.1s for a launchpad branch) be derived from the merge sorted revision graph + some other bits.

There should be no observable change in behavior, apart from lower memory consumption when you browse many different branches.

Some of the code that uses the whole history data has become even more inscrutable, not sure how bad that is...

Cheers,
mwh

[Paul Hummer (rockstar)]

Michael-

  So, these changes are all an improvement, and I only have a few small
comments for the sake of readability in the future. Otherwise, let's land
this, just in time for a new Launchpad rollout.

 vote approve
 status approved

> === modified file 'loggerhead/history.py'
> --- loggerhead/history.py 2009-04-24 00:00:03 +0000
> +++ loggerhead/history.py 2009-04-24 03:44:30 +0000
> @@ -199,14 +199,25 @@
>
> self.last_revid = branch.last_revision()
>
> - whole_history_data = whole_history_data_cache.get(self.last_revid)
> - if whole_history_data is None:
> + cached_whole_history_data = whole_history_data_cache.get(self.last_revid)
> + if cached_whole_history_data is None:
> whole_history_data = compute_whole_history_data(branch)
> - whole_history_data_cache[self.last_revid] = whole_history_data
> -
> - (self._revision_graph, self._full_history, self._revision_info,
> - self._revno_revid, self._merge_sort, self._where_merged,
> - ) = whole_history_data
> + (self._rev_info, self._rev_indices) = whole_history_data
> + whole_history_data_cache[self.last_revid] = whole_history_data[0]
> + self._full_history = []
> + self._revno_revid = {}
> + for ((_, revid, _, revno_str, _), _, _) in self._rev_info:
> + self._revno_revid[revno_str] = revid
> + self._full_history.append(revid)
> + else:
> + self._rev_info = cached_whole_history_data
> + self._full_history = []
> + self._revno_revid = {}
> + self._rev_indices = {}
> + for ((seq, revid, _, revno_str, _), _, _) in self._rev_info:
> + self._rev_indices[revid] = seq
> + self._revno_revid[revno_str] = revid
> + self._full_history.append(revid)
>
> def use_file_cache(self, cache):
> self._file_change_cache = cache

So, the biggest issues I've had with the wholehistory is that the data
structures we're using here aren't obvious. Maybe the a comment or a docstring
would be more helpful. When I was working on wholehistory, I had to attach pdb
and examine the data structures myself. Since we're creating new
datastructures, could we add some in-code documentation to it?

> @@ -219,12 +230,12 @@
> return self._branch.get_config()
>
> def get_revno(self, revid):
> - if revid not in self._revision_info:
> + if revid not in self._rev_indices:
> # ghost parent?
> return 'unknown'
> - (seq, revid, merge_depth,
> - revno_str, end_of_merge) = self._revision_info[revid]
> - return revno_str
> + seq = self._rev_indices[revid]
> + revno = self._rev_info[seq][0][3]
> + return revno
>
> def get_revids_from(self, revid_list, start_revid):
> """

self._rev_info[seq][0][3] is a great example of mysterious data structures.
This seems magic to me.

--
Paul Hummer
http://theironlion.net
1024/862FF08F C921 E962 58F8 5547 6723 0E8C 1C4D 8AC5 862F F08F

review: Approve

=== modified file 'loggerhead/history.py'
--- loggerhead/history.py	2009-04-24 00:00:03 +0000
+++ loggerhead/history.py	2009-04-24 03:44:30 +0000
@@ -199,14 +199,25 @@
 
         self.last_revid = branch.last_revision()
 
-        whole_history_data = whole_history_data_cache.get(self.last_revid)
-        if whole_history_data is None:
+        cached_whole_history_data = whole_history_data_cache.get(self.last_revid)
+        if cached_whole_history_data is None:
             whole_history_data = compute_whole_history_data(branch)
-            whole_history_data_cache[self.last_revid] = whole_history_data
-
-        (self._revision_graph, self._full_history, self._revision_info,
-         self._revno_revid, self._merge_sort, self._where_merged,
-         ) = whole_history_data
+            (self._rev_info, self._rev_indices) = whole_history_data
+            whole_history_data_cache[self.last_revid] = whole_history_data[0]
+            self._full_history = []
+            self._revno_revid = {}
+            for ((_, revid, _, revno_str, _), _, _) in self._rev_info:
+                self._revno_revid[revno_str] = revid
+                self._full_history.append(revid)
+        else:
+            self._rev_info = cached_whole_history_data
+            self._full_history = []
+            self._revno_revid = {}
+            self._rev_indices = {}
+            for ((seq, revid, _, revno_str, _), _, _) in self._rev_info:
+                self._rev_indices[revid] = seq
+                self._revno_revid[revno_str] = revid
+                self._full_history.append(revid)
 
     def use_file_cache(self, cache):
         self._file_change_cache = cache
@@ -219,12 +230,12 @@
         return self._branch.get_config()
 
     def get_revno(self, revid):
-        if revid not in self._revision_info:
+        if revid not in self._rev_indices:
             # ghost parent?
             return 'unknown'
-        (seq, revid, merge_depth,
-         revno_str, end_of_merge) = self._revision_info[revid]
-        return revno_str
+        seq = self._rev_indices[revid]
+        revno = self._rev_info[seq][0][3]
+        return revno
 
     def get_revids_from(self, revid_list, start_revid):
         """
@@ -238,10 +249,11 @@
 
         def introduced_revisions(revid):
             r = set([revid])
-            seq, revid, md, revno, end_of_merge = self._revision_info[revid]
+            seq = self._rev_indices[revid]
+            md = self._rev_info[seq][0][2]
             i = seq + 1
-            while i < len(self._merge_sort) and self._merge_sort[i][2] > md:
-                r.add(self._merge_sort[i][1])
+            while i < len(self._rev_info) and self._rev_info[i][0][2] > md:
+                r.add(self._rev_info[i][0][1])
                 i += 1
             return r
         while 1:
@@ -249,7 +261,7 @@
                 return
             if introduced_revisions(revid) & revid_set:
                 yield revid
-            parents = self._revision_graph[revid]
+            parents = self._rev_info[self._rev_indices[revid]][2]
             if len(parents) == 0:
                 return
             revid = parents[0]
@@ -466,10 +478,10 @@
 
         merge_point = []
         while True:
-            children = self._where_merged.get(revid, ())
+            children = self._rev_info[self._rev_indices[revid]][1]
             nexts = []
             for child in children:
-                child_parents = self._revision_graph[child]
+                child_parents = self._rev_info[self._rev_indices[child]][2]
                 if child_parents[0] == revid:
                     nexts.append(child)
                 else:

=== modified file 'loggerhead/wholehistory.py'
--- loggerhead/wholehistory.py	2009-04-24 00:00:03 +0000
+++ loggerhead/wholehistory.py	2009-04-24 03:12:28 +0000
@@ -50,32 +50,32 @@
 
     _revision_graph = _strip_NULL_ghosts(parent_map)
     _full_history = []
-    _revision_info = {}
-    _revno_revid = {}
+
+    _rev_info = []
+    _rev_indices = {}
+
     if is_null(last_revid):
         _merge_sort = []
     else:
         _merge_sort = merge_sort(
             _revision_graph, last_revid, generate_revno=True)
 
-    for (seq, revid, merge_depth, revno, end_of_merge) in _merge_sort:
+    for info in _merge_sort:
+        seq, revid, merge_depth, revno, end_of_merge = info
         _full_history.append(revid)
         revno_str = '.'.join(str(n) for n in revno)
-        _revno_revid[revno_str] = revid
-        _revision_info[revid] = (
-            seq, revid, merge_depth, revno_str, end_of_merge)
-
-    _where_merged = {}
+        parents = _revision_graph[revid]
+        _rev_indices[revid] = len(_rev_info)
+        _rev_info.append([(seq, revid, merge_depth, revno_str, end_of_merge), (), parents])
 
     for revid in _revision_graph.keys():
-        if _revision_info[revid][2] == 0:
+        if _rev_info[_rev_indices[revid]][0][2] == 0:
             continue
         for parent in _revision_graph[revid]:
-            c = _where_merged.setdefault(parent, ())
-            if revid not in c:
-                _where_merged[parent] = c + (revid,)
+            c = _rev_info[_rev_indices[parent]]
+            if revid not in c[1]:
+                c[1] = c[1] + (revid,)
 
     log.info('built revision graph cache: %r secs' % (time.time() - z))
 
-    return (_revision_graph, _full_history, _revision_info,
-            _revno_revid, _merge_sort, _where_merged)
+    return (_rev_info, _rev_indices)