Mercurial > public > mercurial-scm > hg

comparison mercurial/util.py @ 16803:107a3270a24a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
cleanup: use the deque type where appropriate There have been quite a few places where we pop elements off the front of a list. This can turn O(n) algorithms into something more like O(n**2). Python has provided a deque type that can do this efficiently since at least 2.4. As an example of the difference a deque can make, it improves perfancestors performance on a Linux repo from 0.50 seconds to 0.36.
author Bryan O'Sullivan <bryano@fb.com>
date Tue, 15 May 2012 10:46:23 -0700
parents e406b9656da3
children cafd8a8fb713
comparison
equal deleted inserted replaced
16802:7e5d94381cd1 16803:107a3270a24a
12 This contains helper routines that are independent of the SCM core and 12 This contains helper routines that are independent of the SCM core and
13 hide platform-specific details from the core. 13 hide platform-specific details from the core.
14 """ 14 """
15 15
16 from i18n import _ 16 from i18n import _
17 import error, osutil, encoding 17 import error, osutil, encoding, collections
18 import errno, re, shutil, sys, tempfile, traceback 18 import errno, re, shutil, sys, tempfile, traceback
19 import os, time, datetime, calendar, textwrap, signal 19 import os, time, datetime, calendar, textwrap, signal
20 import imp, socket, urllib 20 import imp, socket, urllib
21 21
22 if os.name == 'nt': 22 if os.name == 'nt':
203 return f 203 return f
204 204
205 def lrucachefunc(func): 205 def lrucachefunc(func):
206 '''cache most recent results of function calls''' 206 '''cache most recent results of function calls'''
207 cache = {} 207 cache = {}
208 order = [] 208 order = collections.deque()
209 if func.func_code.co_argcount == 1: 209 if func.func_code.co_argcount == 1:
210 def f(arg): 210 def f(arg):
211 if arg not in cache: 211 if arg not in cache:
212 if len(cache) > 20: 212 if len(cache) > 20:
213 del cache[order.pop(0)] 213 del cache[order.popleft()]
214 cache[arg] = func(arg) 214 cache[arg] = func(arg)
215 else: 215 else:
216 order.remove(arg) 216 order.remove(arg)
217 order.append(arg) 217 order.append(arg)
218 return cache[arg] 218 return cache[arg]
219 else: 219 else:
220 def f(*args): 220 def f(*args):
221 if args not in cache: 221 if args not in cache:
222 if len(cache) > 20: 222 if len(cache) > 20:
223 del cache[order.pop(0)] 223 del cache[order.popleft()]
224 cache[args] = func(*args) 224 cache[args] = func(*args)
225 else: 225 else:
226 order.remove(args) 226 order.remove(args)
227 order.append(args) 227 order.append(args)
228 return cache[args] 228 return cache[args]
863 def read(self, l): 863 def read(self, l):
864 """Read L bytes of data from the iterator of chunks of data. 864 """Read L bytes of data from the iterator of chunks of data.
865 Returns less than L bytes if the iterator runs dry.""" 865 Returns less than L bytes if the iterator runs dry."""
866 left = l 866 left = l
867 buf = '' 867 buf = ''
868 queue = self._queue 868 queue = collections.deque(self._queue)
869 while left > 0: 869 while left > 0:
870 # refill the queue 870 # refill the queue
871 if not queue: 871 if not queue:
872 target = 2**18 872 target = 2**18
873 for chunk in self.iter: 873 for chunk in self.iter:
876 if target <= 0: 876 if target <= 0:
877 break 877 break
878 if not queue: 878 if not queue:
879 break 879 break
880 880
881 chunk = queue.pop(0) 881 chunk = queue.popleft()
882 left -= len(chunk) 882 left -= len(chunk)
883 if left < 0: 883 if left < 0:
884 queue.insert(0, chunk[left:]) 884 queue.appendleft(chunk[left:])
885 buf += chunk[:left] 885 buf += chunk[:left]
886 else: 886 else:
887 buf += chunk 887 buf += chunk
888 self._queue = list(queue)
888 889
889 return buf 890 return buf
890 891
891 def filechunkiter(f, size=65536, limit=None): 892 def filechunkiter(f, size=65536, limit=None):
892 """Create a generator that produces the data in the file size 893 """Create a generator that produces the data in the file size