Mercurial > hg
annotate mercurial/pvec.py @ 16719:e7bf09acd410
localrepo: add branchtip() method for faster single-branch lookups
For the PyPy repo with 744 branches and 843 branch heads, this brings
hg log -r default over NFS from:
CallCount Recursive Total(ms) Inline(ms) module:lineno(function)
3249 0 1.3222 1.3222 <open>
3244 0 0.6211 0.6211 <method 'close' of 'file' objects>
3243 0 0.0800 0.0800 <method 'read' of 'file' objects>
3241 0 0.0660 0.0660 <method 'seek' of 'file' objects>
3905 0 0.0476 0.0476 <zlib.decompress>
3281 0 2.6756 0.0472 mercurial.changelog:182(read)
+3281 0 2.5256 0.0453 +mercurial.revlog:881(revision)
+3276 0 0.0389 0.0196 +mercurial.changelog:28(decodeextra)
+6562 0 0.0123 0.0123 +<method 'split' of 'str' objects>
+6562 0 0.0408 0.0073 +mercurial.encoding:61(tolocal)
+3281 0 0.0054 0.0054 +<method 'index' of 'str' objects>
3241 0 2.2464 0.0456 mercurial.revlog:818(_loadchunk)
+3241 0 0.6205 0.6205 +<method 'close' of 'file' objects>
+3241 0 0.0765 0.0765 +<method 'read' of 'file' objects>
+3241 0 0.0660 0.0660 +<method 'seek' of 'file' objects>
+3241 0 1.4209 0.0135 +mercurial.store:374(__call__)
+3241 0 0.0122 0.0107 +mercurial.revlog:810(_addchunk)
3281 0 2.5256 0.0453 mercurial.revlog:881(revision)
+3280 0 0.0175 0.0175 +mercurial.revlog:305(rev)
+3281 0 2.2819 0.0119 +mercurial.revlog:847(_chunkraw)
+3281 0 0.0603 0.0083 +mercurial.revlog:945(_checkhash)
+3281 0 0.0051 0.0051 +mercurial.revlog:349(flags)
+3281 0 0.0040 0.0040 +<mercurial.mpatch.patches>
13682 0 0.0479 0.0248 <method 'decode' of 'str' objects>
+7418 0 0.0228 0.0076 +encodings.utf_8:15(decode)
+1 0 0.0003 0.0000 +encodings:71(search_function)
3248 0 1.3995 0.0246 mercurial.scmutil:218(__call__)
+3248 0 1.3222 1.3222 +<open>
+3248 0 0.0235 0.0184 +os.path:80(split)
+3248 0 0.0084 0.0068 +mercurial.scmutil:92(__call__)
Time: real 2.750 secs (user 0.680+0.000 sys 0.360+0.000)
down to:
CallCount Recursive Total(ms) Inline(ms) module:lineno(function)
55 31 0.0197 0.0163 <__import__>
+1 0 0.0006 0.0002 +mercurial.context:8(<module>)
+1 0 0.0042 0.0001 +mercurial.revlog:12(<module>)
+1 0 0.0002 0.0001 +mercurial.match:8(<module>)
+1 0 0.0003 0.0001 +mercurial.dirstate:7(<module>)
+1 0 0.0057 0.0001 +mercurial.changelog:8(<module>)
1 0 0.0117 0.0032 mercurial.localrepo:525(_readbranchcache)
+844 0 0.0015 0.0015 +<binascii.unhexlify>
+845 0 0.0010 0.0010 +<method 'split' of 'str' objects>
+843 0 0.0045 0.0009 +mercurial.encoding:61(tolocal)
+843 0 0.0004 0.0004 +<method 'setdefault' of 'dict' objects>
+1 0 0.0003 0.0003 +<method 'close' of 'file' objects>
3 0 0.0029 0.0029 <method 'read' of 'file' objects>
9 0 0.0018 0.0018 <open>
990 0 0.0017 0.0017 <binascii.unhexlify>
53 0 0.0016 0.0016 mercurial.demandimport:43(__init__)
862 0 0.0015 0.0015 <_codecs.utf_8_decode>
862 0 0.0037 0.0014 <method 'decode' of 'str' objects>
+862 0 0.0023 0.0008 +encodings.utf_8:15(decode)
981 0 0.0011 0.0011 <method 'split' of 'str' objects>
861 0 0.0046 0.0009 mercurial.encoding:61(tolocal)
+861 0 0.0037 0.0014 +<method 'decode' of 'str' objects>
862 0 0.0023 0.0008 encodings.utf_8:15(decode)
+862 0 0.0015 0.0015 +<_codecs.utf_8_decode>
4 0 0.0008 0.0008 <method 'close' of 'file' objects>
179 154 0.0202 0.0004 mercurial.demandimport:83(__getattribute__)
+36 11 0.0199 0.0003 +mercurial.demandimport:55(_load)
+72 0 0.0001 0.0001 +mercurial.demandimport:83(__getattribute__)
+36 0 0.0000 0.0000 +<getattr>
1 0 0.0015 0.0004 mercurial.tags:148(_readtagcache)
Time: real 0.060 secs (user 0.030+0.000 sys 0.010+0.000)
author | Brodie Rao <brodie@sf.io> |
---|---|
date | Sun, 13 May 2012 14:04:04 +0200 |
parents | 0d175ac527c1 |
children | e7cfe3587ea4 |
rev | line source |
---|---|
16249 | 1 # pvec.py - probabilistic vector clocks for Mercurial |
2 # | |
3 # Copyright 2012 Matt Mackall <mpm@selenic.com> | |
4 # | |
5 # This software may be used and distributed according to the terms of the | |
6 # GNU General Public License version 2 or any later version. | |
7 | |
8 ''' | |
9 A "pvec" is a changeset property based on the theory of vector clocks | |
10 that can be compared to discover relatedness without consulting a | |
11 graph. This can be useful for tasks like determining how a | |
12 disconnected patch relates to a repository. | |
13 | |
14 Currently a pvec consist of 448 bits, of which 24 are 'depth' and the | |
15 remainder are a bit vector. It is represented as a 70-character base85 | |
16 string. | |
17 | |
18 Construction: | |
19 | |
20 - a root changeset has a depth of 0 and a bit vector based on its hash | |
21 - a normal commit has a changeset where depth is increased by one and | |
22 one bit vector bit is flipped based on its hash | |
23 - a merge changeset pvec is constructed by copying changes from one pvec into | |
24 the other to balance its depth | |
25 | |
26 Properties: | |
27 | |
28 - for linear changes, difference in depth is always <= hamming distance | |
29 - otherwise, changes are probably divergent | |
30 - when hamming distance is < 200, we can reliably detect when pvecs are near | |
31 | |
32 Issues: | |
33 | |
34 - hamming distance ceases to work over distances of ~ 200 | |
35 - detecting divergence is less accurate when the common ancestor is very close | |
36 to either revision or total distance is high | |
37 - this could probably be improved by modeling the relation between | |
38 delta and hdist | |
39 | |
40 Uses: | |
41 | |
42 - a patch pvec can be used to locate the nearest available common ancestor for | |
43 resolving conflicts | |
44 - ordering of patches can be established without a DAG | |
45 - two head pvecs can be compared to determine whether push/pull/merge is needed | |
46 and approximately how many changesets are involved | |
47 - can be used to find a heuristic divergence measure between changesets on | |
48 different branches | |
49 ''' | |
50 | |
51 import base85, util | |
52 from node import nullrev | |
53 | |
54 _size = 448 # 70 chars b85-encoded | |
55 _bytes = _size / 8 | |
56 _depthbits = 24 | |
57 _depthbytes = _depthbits / 8 | |
58 _vecbytes = _bytes - _depthbytes | |
59 _vecbits = _vecbytes * 8 | |
60 _radius = (_vecbits - 30) / 2 # high probability vecs are related | |
61 | |
62 def _bin(bs): | |
63 '''convert a bytestring to a long''' | |
64 v = 0 | |
65 for b in bs: | |
66 v = v * 256 + ord(b) | |
67 return v | |
68 | |
69 def _str(v, l): | |
70 bs = "" | |
71 for p in xrange(l): | |
72 bs = chr(v & 255) + bs | |
73 v >>= 8 | |
74 return bs | |
75 | |
76 def _split(b): | |
77 '''depth and bitvec''' | |
78 return _bin(b[:_depthbytes]), _bin(b[_depthbytes:]) | |
79 | |
80 def _join(depth, bitvec): | |
81 return _str(depth, _depthbytes) + _str(bitvec, _vecbytes) | |
82 | |
83 def _hweight(x): | |
84 c = 0 | |
85 while x: | |
86 if x & 1: | |
87 c += 1 | |
88 x >>= 1 | |
89 return c | |
90 _htab = [_hweight(x) for x in xrange(256)] | |
91 | |
92 def _hamming(a, b): | |
93 '''find the hamming distance between two longs''' | |
94 d = a ^ b | |
95 c = 0 | |
96 while d: | |
97 c += _htab[d & 0xff] | |
98 d >>= 8 | |
99 return c | |
100 | |
101 def _mergevec(x, y, c): | |
102 # Ideally, this function would be x ^ y ^ ancestor, but finding | |
103 # ancestors is a nuisance. So instead we find the minimal number | |
104 # of changes to balance the depth and hamming distance | |
105 | |
106 d1, v1 = x | |
107 d2, v2 = y | |
108 if d1 < d2: | |
109 d1, d2, v1, v2 = d2, d1, v2, v1 | |
110 | |
111 hdist = _hamming(v1, v2) | |
112 ddist = d1 - d2 | |
113 v = v1 | |
114 m = v1 ^ v2 # mask of different bits | |
115 i = 1 | |
116 | |
117 if hdist > ddist: | |
118 # if delta = 10 and hdist = 100, then we need to go up 55 steps | |
119 # to the ancestor and down 45 | |
120 changes = (hdist - ddist + 1) / 2 | |
121 else: | |
122 # must make at least one change | |
123 changes = 1 | |
124 depth = d1 + changes | |
125 | |
126 # copy changes from v2 | |
127 if m: | |
128 while changes: | |
129 if m & i: | |
130 v ^= i | |
131 changes -= 1 | |
132 i <<= 1 | |
133 else: | |
134 v = _flipbit(v, c) | |
135 | |
136 return depth, v | |
137 | |
138 def _flipbit(v, node): | |
139 # converting bit strings to longs is slow | |
140 bit = (hash(node) & 0xffffffff) % _vecbits | |
141 return v ^ (1<<bit) | |
142 | |
143 def ctxpvec(ctx): | |
144 '''construct a pvec for ctx while filling in the cache''' | |
145 r = ctx._repo | |
146 if not util.safehasattr(r, "_pveccache"): | |
147 r._pveccache = {} | |
148 pvc = r._pveccache | |
149 if ctx.rev() not in pvc: | |
150 cl = r.changelog | |
151 for n in xrange(ctx.rev() + 1): | |
152 if n not in pvc: | |
153 node = cl.node(n) | |
154 p1, p2 = cl.parentrevs(n) | |
155 if p1 == nullrev: | |
156 # start with a 'random' vector at root | |
157 pvc[n] = (0, _bin((node * 3)[:_vecbytes])) | |
158 elif p2 == nullrev: | |
159 d, v = pvc[p1] | |
160 pvc[n] = (d + 1, _flipbit(v, node)) | |
161 else: | |
162 pvc[n] = _mergevec(pvc[p1], pvc[p2], node) | |
163 bs = _join(*pvc[ctx.rev()]) | |
164 return pvec(base85.b85encode(bs)) | |
165 | |
166 class pvec(object): | |
167 def __init__(self, hashorctx): | |
168 if isinstance(hashorctx, str): | |
169 self._bs = hashorctx | |
170 self._depth, self._vec = _split(base85.b85decode(hashorctx)) | |
171 else: | |
172 self._vec = ctxpvec(ctx) | |
173 | |
174 def __str__(self): | |
175 return self._bs | |
176 | |
177 def __eq__(self, b): | |
178 return self._vec == b._vec and self._depth == b._depth | |
179 | |
180 def __lt__(self, b): | |
181 delta = b._depth - self._depth | |
182 if delta < 0: | |
183 return False # always correct | |
184 if _hamming(self._vec, b._vec) > delta: | |
185 return False | |
186 return True | |
187 | |
188 def __gt__(self, b): | |
189 return b < self | |
190 | |
191 def __or__(self, b): | |
192 delta = abs(b._depth - self._depth) | |
193 if _hamming(self._vec, b._vec) <= delta: | |
194 return False | |
195 return True | |
196 | |
197 def __sub__(self, b): | |
198 if self | b: | |
199 raise ValueError("concurrent pvecs") | |
200 return self._depth - b._depth | |
201 | |
202 def distance(self, b): | |
203 d = abs(b._depth - self._depth) | |
204 h = _hamming(self._vec, b._vec) | |
205 return max(d, h) | |
206 | |
207 def near(self, b): | |
208 dist = abs(b.depth - self._depth) | |
209 if dist > _radius or _hamming(self._vec, b._vec) > _radius: | |
210 return False |