Mercurial > hg
comparison mercurial/hg.py @ 644:6ebe118280bd
Performance enhancements for manifest.add()
# HG changeset patch
# User mason@suse.com
Performance enhancements for manifest.add()
Improve manifest.add performance by using bisect to insert/remove
changed items into the manifest list. This also generates the
manifest delta directly based on the changes being made.
author | mason@suse.com |
---|---|
date | Wed, 06 Jul 2005 22:28:35 -0800 |
parents | 31cebba881a0 |
children | 342927da4f4c |
comparison
equal
deleted
inserted
replaced
643:c9e159bb9a3d | 644:6ebe118280bd |
---|---|
9 import util | 9 import util |
10 from revlog import * | 10 from revlog import * |
11 from demandload import * | 11 from demandload import * |
12 demandload(globals(), "re lock urllib urllib2 transaction time socket") | 12 demandload(globals(), "re lock urllib urllib2 transaction time socket") |
13 demandload(globals(), "tempfile httprangereader bdiff") | 13 demandload(globals(), "tempfile httprangereader bdiff") |
14 demandload(globals(), "bisect") | |
14 | 15 |
15 class filelog(revlog): | 16 class filelog(revlog): |
16 def __init__(self, opener, path): | 17 def __init__(self, opener, path): |
17 revlog.__init__(self, opener, | 18 revlog.__init__(self, opener, |
18 os.path.join("data", path + ".i"), | 19 os.path.join("data", path + ".i"), |
122 return mdiff.textdiff(a, b) | 123 return mdiff.textdiff(a, b) |
123 return d | 124 return d |
124 else: | 125 else: |
125 return mdiff.textdiff(a, b) | 126 return mdiff.textdiff(a, b) |
126 | 127 |
127 def add(self, map, flags, transaction, link, p1=None, p2=None): | 128 def add(self, map, flags, transaction, link, p1=None, p2=None,changed=None): |
128 files = map.keys() | 129 # directly generate the mdiff delta from the data collected during |
129 files.sort() | 130 # the bisect loop below |
130 | 131 def gendelta(delta): |
131 self.addlist = ["%s\000%s%s\n" % | 132 i = 0 |
132 (f, hex(map[f]), flags[f] and "x" or '') | 133 result = [] |
133 for f in files] | 134 while i < len(delta): |
135 start = delta[i][2] | |
136 end = delta[i][3] | |
137 l = delta[i][4] | |
138 if l == None: | |
139 l = "" | |
140 while i < len(delta) - 1 and start <= delta[i+1][2] and end >= delta[i+1][2]: | |
141 if delta[i+1][3] > end: | |
142 end = delta[i+1][3] | |
143 if delta[i+1][4]: | |
144 l += delta[i+1][4] | |
145 i += 1 | |
146 result.append(struct.pack(">lll", start, end, len(l)) + l) | |
147 i += 1 | |
148 return result | |
149 | |
150 # apply the changes collected during the bisect loop to our addlist | |
151 def addlistdelta(addlist, delta): | |
152 # apply the deltas to the addlist. start from the bottom up | |
153 # so changes to the offsets don't mess things up. | |
154 i = len(delta) | |
155 while i > 0: | |
156 i -= 1 | |
157 start = delta[i][0] | |
158 end = delta[i][1] | |
159 if delta[i][4]: | |
160 addlist[start:end] = [delta[i][4]] | |
161 else: | |
162 del addlist[start:end] | |
163 return addlist | |
164 | |
165 # calculate the byte offset of the start of each line in the | |
166 # manifest | |
167 def calcoffsets(addlist): | |
168 offsets = [0] * (len(addlist) + 1) | |
169 offset = 0 | |
170 i = 0 | |
171 while i < len(addlist): | |
172 offsets[i] = offset | |
173 offset += len(addlist[i]) | |
174 i += 1 | |
175 offsets[i] = offset | |
176 return offsets | |
177 | |
178 # if we're using the listcache, make sure it is valid and | |
179 # parented by the same node we're diffing against | |
180 if not changed or not self.listcache or not p1 or self.mapcache[0] != p1: | |
181 files = map.keys() | |
182 files.sort() | |
183 | |
184 self.addlist = ["%s\000%s%s\n" % | |
185 (f, hex(map[f]), flags[f] and "x" or '') | |
186 for f in files] | |
187 cachedelta = None | |
188 else: | |
189 addlist = self.listcache[1] | |
190 | |
191 # find the starting offset for each line in the add list | |
192 offsets = calcoffsets(addlist) | |
193 | |
194 # combine the changed lists into one list for sorting | |
195 work = [[x, 0] for x in changed[0]] | |
196 work[len(work):] = [[x, 1] for x in changed[1]] | |
197 work.sort() | |
198 | |
199 delta = [] | |
200 bs = 0 | |
201 | |
202 for w in work: | |
203 f = w[0] | |
204 # bs will either be the index of the item or the insertion point | |
205 bs = bisect.bisect(addlist, f, bs) | |
206 if bs < len(addlist): | |
207 fn = addlist[bs][:addlist[bs].index('\0')] | |
208 else: | |
209 fn = None | |
210 if w[1] == 0: | |
211 l = "%s\000%s%s\n" % (f, hex(map[f]), flags[f] and "x" or '') | |
212 else: | |
213 l = None | |
214 start = bs | |
215 if fn != f: | |
216 # item not found, insert a new one | |
217 end = bs | |
218 if w[1] == 1: | |
219 sys.stderr.write("failed to remove %s from manifest" % f) | |
220 sys.exit(1) | |
221 else: | |
222 # item is found, replace/delete the existing line | |
223 end = bs + 1 | |
224 delta.append([start, end, offsets[start], offsets[end], l]) | |
225 | |
226 self.addlist = addlistdelta(addlist, delta) | |
227 if self.mapcache[0] == self.tip(): | |
228 cachedelta = "".join(gendelta(delta)) | |
229 else: | |
230 cachedelta = None | |
231 | |
134 text = "".join(self.addlist) | 232 text = "".join(self.addlist) |
135 | 233 if cachedelta and mdiff.patch(self.listcache[0], cachedelta) != text: |
136 n = self.addrevision(text, transaction, link, p1, p2) | 234 sys.stderr.write("manifest delta failure") |
235 sys.exit(1) | |
236 n = self.addrevision(text, transaction, link, p1, p2, cachedelta) | |
137 self.mapcache = (n, map, flags) | 237 self.mapcache = (n, map, flags) |
138 self.listcache = (text, self.addlist) | 238 self.listcache = (text, self.addlist) |
139 self.addlist = None | 239 self.addlist = None |
140 | 240 |
141 return n | 241 return n |
667 # update manifest | 767 # update manifest |
668 m1.update(new) | 768 m1.update(new) |
669 for f in remove: | 769 for f in remove: |
670 if f in m1: | 770 if f in m1: |
671 del m1[f] | 771 del m1[f] |
672 mn = self.manifest.add(m1, mf1, tr, linkrev, c1[0], c2[0]) | 772 mn = self.manifest.add(m1, mf1, tr, linkrev, c1[0], c2[0], (new,remove)) |
673 | 773 |
674 # add changeset | 774 # add changeset |
675 new = new.keys() | 775 new = new.keys() |
676 new.sort() | 776 new.sort() |
677 | 777 |