##// END OF EJS Templates
util: lower water mark when removing nodes after cost limit reached...
util: lower water mark when removing nodes after cost limit reached See the inline comment for the reasoning here. This is a pretty common strategy for garbage collectors, other cache-like primtives. The performance impact is substantial: $ hg perflrucachedict --size 4 --gets 1000000 --sets 1000000 --mixed 1000000 --costlimit 100 ! inserts w/ cost limit ! wall 1.659181 comb 1.650000 user 1.650000 sys 0.000000 (best of 7) ! wall 1.722122 comb 1.720000 user 1.720000 sys 0.000000 (best of 6) ! mixed w/ cost limit ! wall 1.139955 comb 1.140000 user 1.140000 sys 0.000000 (best of 9) ! wall 1.182513 comb 1.180000 user 1.180000 sys 0.000000 (best of 9) $ hg perflrucachedict --size 1000 --gets 1000000 --sets 1000000 --mixed 1000000 --costlimit 10000 ! inserts ! wall 0.679546 comb 0.680000 user 0.680000 sys 0.000000 (best of 15) ! sets ! wall 0.825147 comb 0.830000 user 0.830000 sys 0.000000 (best of 13) ! inserts w/ cost limit ! wall 25.105273 comb 25.080000 user 25.080000 sys 0.000000 (best of 3) ! wall 1.724397 comb 1.720000 user 1.720000 sys 0.000000 (best of 6) ! mixed ! wall 0.807096 comb 0.810000 user 0.810000 sys 0.000000 (best of 13) ! mixed w/ cost limit ! wall 12.104470 comb 12.070000 user 12.070000 sys 0.000000 (best of 3) ! wall 1.190563 comb 1.190000 user 1.190000 sys 0.000000 (best of 9) $ hg perflrucachedict --size 1000 --gets 1000000 --sets 1000000 --mixed 1000000 --costlimit 10000 --mixedgetfreq 90 ! inserts ! wall 0.711177 comb 0.710000 user 0.710000 sys 0.000000 (best of 14) ! sets ! wall 0.846992 comb 0.850000 user 0.850000 sys 0.000000 (best of 12) ! inserts w/ cost limit ! wall 25.963028 comb 25.960000 user 25.960000 sys 0.000000 (best of 3) ! wall 2.184311 comb 2.180000 user 2.180000 sys 0.000000 (best of 5) ! mixed ! wall 0.728256 comb 0.730000 user 0.730000 sys 0.000000 (best of 14) ! mixed w/ cost limit ! wall 3.174256 comb 3.170000 user 3.170000 sys 0.000000 (best of 4) ! wall 0.773186 comb 0.770000 user 0.770000 sys 0.000000 (best of 13) $ hg perflrucachedict --size 100000 --gets 1000000 --sets 1000000 --mixed 1000000 --mixedgetfreq 90 --costlimit 5000000 ! gets ! wall 1.191368 comb 1.190000 user 1.190000 sys 0.000000 (best of 9) ! wall 1.195304 comb 1.190000 user 1.190000 sys 0.000000 (best of 9) ! inserts ! wall 0.950995 comb 0.950000 user 0.950000 sys 0.000000 (best of 11) ! inserts w/ cost limit ! wall 1.589732 comb 1.590000 user 1.590000 sys 0.000000 (best of 7) ! sets ! wall 1.094941 comb 1.100000 user 1.090000 sys 0.010000 (best of 9) ! mixed ! wall 0.936420 comb 0.940000 user 0.930000 sys 0.010000 (best of 10) ! mixed w/ cost limit ! wall 0.882780 comb 0.870000 user 0.870000 sys 0.000000 (best of 11) This puts us ~2x slower than caches without cost accounting. And for read-heavy workloads (the prime use cases for caches), performance is nearly identical. In the worst case (pure write workloads with cost accounting enabled), we're looking at ~1.5us per insert on large caches. That seems "fast enough." Differential Revision: https://phab.mercurial-scm.org/D4505

File last commit:

r38806:e7aa113b default
r39606:f296c0b3 default
Show More
diffhelper.py
78 lines | 2.2 KiB | text/x-python | PythonLexer
# diffhelper.py - helper routines for patch
#
# Copyright 2009 Matt Mackall <mpm@selenic.com> and others
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.
from __future__ import absolute_import
from .i18n import _
from . import (
error,
pycompat,
)
def addlines(fp, hunk, lena, lenb, a, b):
"""Read lines from fp into the hunk
The hunk is parsed into two arrays, a and b. a gets the old state of
the text, b gets the new state. The control char from the hunk is saved
when inserting into a, but not b (for performance while deleting files.)
"""
while True:
todoa = lena - len(a)
todob = lenb - len(b)
num = max(todoa, todob)
if num == 0:
break
for i in pycompat.xrange(num):
s = fp.readline()
if not s:
raise error.ParseError(_('incomplete hunk'))
if s == "\\ No newline at end of file\n":
fixnewline(hunk, a, b)
continue
if s == '\n' or s == '\r\n':
# Some patches may be missing the control char
# on empty lines. Supply a leading space.
s = ' ' + s
hunk.append(s)
if s.startswith('+'):
b.append(s[1:])
elif s.startswith('-'):
a.append(s)
else:
b.append(s[1:])
a.append(s)
def fixnewline(hunk, a, b):
"""Fix up the last lines of a and b when the patch has no newline at EOF"""
l = hunk[-1]
# tolerate CRLF in last line
if l.endswith('\r\n'):
hline = l[:-2]
else:
hline = l[:-1]
if hline.startswith((' ', '+')):
b[-1] = hline[1:]
if hline.startswith((' ', '-')):
a[-1] = hline
hunk[-1] = hline
def testhunk(a, b, bstart):
"""Compare the lines in a with the lines in b
a is assumed to have a control char at the start of each line, this char
is ignored in the compare.
"""
alen = len(a)
blen = len(b)
if alen > blen - bstart or bstart < 0:
return False
for i in pycompat.xrange(alen):
if a[i][1:] != b[i + bstart]:
return False
return True