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
$ cat >> $HGRCPATH << EOF
> [ui]
> logtemplate="{rev}:{node|short} {desc} [{tags}]\n"
> EOF
$ hg init legacy-lookup
$ cd legacy-lookup
$ echo a > a
$ hg add a
$ hg commit -m 'first'
$ echo aa > a
$ hg commit -m 'second'
$ hg log -G
@ 1:43114e71eddd second [tip]
|
o 0:a87874c6ec31 first []
Create a tag that looks like a revset
$ hg tag 'rev(0)'
$ hg log -G
@ 2:fb616635b18f Added tag rev(0) for changeset 43114e71eddd [tip]
|
o 1:43114e71eddd second [rev(0)]
|
o 0:a87874c6ec31 first []
See how various things are resolved
-----------------------------------
Revision numbers
$ hg log -r '0'
0:a87874c6ec31 first []
$ hg log -r '1'
1:43114e71eddd second [rev(0)]
"rev(x)" form (the one conflicting with the tags)
(resolved as a label)
$ hg log -r 'rev(0)'
1:43114e71eddd second [rev(0)]
$ hg log -r 'rev(1)'
1:43114e71eddd second [rev(0)]
same within a simple revspec
(still resolved as the label)
$ hg log -r ':rev(0)'
0:a87874c6ec31 first []
1:43114e71eddd second [rev(0)]
$ hg log -r 'rev(0):'
1:43114e71eddd second [rev(0)]
2:fb616635b18f Added tag rev(0) for changeset 43114e71eddd [tip]
within a more advances revset
(still resolved as the label)
$ hg log -r 'rev(0) and branch(default)'
0:a87874c6ec31 first []
with explicit revset resolution
(still resolved as the label)
$ hg log -r 'revset(rev(0))'
0:a87874c6ec31 first []
some of the above with quote to force its resolution as a label
$ hg log -r ':"rev(0)"'
0:a87874c6ec31 first []
1:43114e71eddd second [rev(0)]
$ hg log -r '"rev(0)":'
1:43114e71eddd second [rev(0)]
2:fb616635b18f Added tag rev(0) for changeset 43114e71eddd [tip]
$ hg log -r '"rev(0)" and branch(default)'
1:43114e71eddd second [rev(0)]
confusing bits within parents
$ hg log -r '(rev(0))'
0:a87874c6ec31 first []
$ hg log -r '( rev(0))'
0:a87874c6ec31 first []
$ hg log -r '("rev(0)")'
1:43114e71eddd second [rev(0)]
Test label with quote in them.
$ hg tag '"foo"'
$ hg log -r '"foo"'
2:fb616635b18f Added tag rev(0) for changeset 43114e71eddd ["foo"]
$ hg log -r '("foo")'
abort: unknown revision 'foo'!
[255]
$ hg log -r 'revset("foo")'
abort: unknown revision 'foo'!
[255]
$ hg log -r '("\"foo\"")'
2:fb616635b18f Added tag rev(0) for changeset 43114e71eddd ["foo"]
$ hg log -r 'revset("\"foo\"")'
2:fb616635b18f Added tag rev(0) for changeset 43114e71eddd ["foo"]
Test label with dash in them.
$ hg tag 'foo-bar'
$ hg log -r 'foo-bar'
3:a50aae922707 Added tag "foo" for changeset fb616635b18f [foo-bar]
$ hg log -r '(foo-bar)'
3:a50aae922707 Added tag "foo" for changeset fb616635b18f [foo-bar]
$ hg log -r '"foo-bar"'
3:a50aae922707 Added tag "foo" for changeset fb616635b18f [foo-bar]
$ hg log -r '("foo-bar")'
3:a50aae922707 Added tag "foo" for changeset fb616635b18f [foo-bar]
Test label with + in them.
$ hg tag 'foo+bar'
$ hg log -r 'foo+bar'
4:bbf52b87b370 Added tag foo-bar for changeset a50aae922707 [foo+bar]
$ hg log -r '(foo+bar)'
abort: unknown revision 'foo'!
[255]
$ hg log -r 'revset(foo+bar)'
abort: unknown revision 'foo'!
[255]
$ hg log -r '"foo+bar"'
4:bbf52b87b370 Added tag foo-bar for changeset a50aae922707 [foo+bar]
$ hg log -r '("foo+bar")'
4:bbf52b87b370 Added tag foo-bar for changeset a50aae922707 [foo+bar]
Test tag with numeric version number.
$ hg tag '1.2'
$ hg log -r '1.2'
5:ff42fde8edbb Added tag foo+bar for changeset bbf52b87b370 [1.2]
$ hg log -r '(1.2)'
5:ff42fde8edbb Added tag foo+bar for changeset bbf52b87b370 [1.2]
$ hg log -r 'revset(1.2)'
5:ff42fde8edbb Added tag foo+bar for changeset bbf52b87b370 [1.2]
$ hg log -r '"1.2"'
5:ff42fde8edbb Added tag foo+bar for changeset bbf52b87b370 [1.2]
$ hg log -r '("1.2")'
5:ff42fde8edbb Added tag foo+bar for changeset bbf52b87b370 [1.2]
$ hg log -r '::"1.2"'
0:a87874c6ec31 first []
1:43114e71eddd second [rev(0)]
2:fb616635b18f Added tag rev(0) for changeset 43114e71eddd ["foo"]
3:a50aae922707 Added tag "foo" for changeset fb616635b18f [foo-bar]
4:bbf52b87b370 Added tag foo-bar for changeset a50aae922707 [foo+bar]
5:ff42fde8edbb Added tag foo+bar for changeset bbf52b87b370 [1.2]
$ hg log -r '::1.2'
0:a87874c6ec31 first []
1:43114e71eddd second [rev(0)]
2:fb616635b18f Added tag rev(0) for changeset 43114e71eddd ["foo"]
3:a50aae922707 Added tag "foo" for changeset fb616635b18f [foo-bar]
4:bbf52b87b370 Added tag foo-bar for changeset a50aae922707 [foo+bar]
5:ff42fde8edbb Added tag foo+bar for changeset bbf52b87b370 [1.2]
Test tag with parenthesis (but not a valid revset)
$ hg tag 'release_4.1(candidate1)'
$ hg log -r 'release_4.1(candidate1)'
6:db72e24fe069 Added tag 1.2 for changeset ff42fde8edbb [release_4.1(candidate1)]
$ hg log -r '(release_4.1(candidate1))'
hg: parse error: unknown identifier: release_4.1
[255]
$ hg log -r 'revset(release_4.1(candidate1))'
hg: parse error: unknown identifier: release_4.1
[255]
$ hg log -r '"release_4.1(candidate1)"'
6:db72e24fe069 Added tag 1.2 for changeset ff42fde8edbb [release_4.1(candidate1)]
$ hg log -r '("release_4.1(candidate1)")'
6:db72e24fe069 Added tag 1.2 for changeset ff42fde8edbb [release_4.1(candidate1)]
$ hg log -r '::"release_4.1(candidate1)"'
0:a87874c6ec31 first []
1:43114e71eddd second [rev(0)]
2:fb616635b18f Added tag rev(0) for changeset 43114e71eddd ["foo"]
3:a50aae922707 Added tag "foo" for changeset fb616635b18f [foo-bar]
4:bbf52b87b370 Added tag foo-bar for changeset a50aae922707 [foo+bar]
5:ff42fde8edbb Added tag foo+bar for changeset bbf52b87b370 [1.2]
6:db72e24fe069 Added tag 1.2 for changeset ff42fde8edbb [release_4.1(candidate1)]
$ hg log -r '::release_4.1(candidate1)'
hg: parse error: unknown identifier: release_4.1
[255]
Test tag with parenthesis and other function like char
$ hg tag 'release_4.1(arch=x86,arm)'
$ hg log -r 'release_4.1(arch=x86,arm)'
7:b29b25d7d687 Added tag release_4.1(candidate1) for changeset db72e24fe069 [release_4.1(arch=x86,arm)]
$ hg log -r '(release_4.1(arch=x86,arm))'
hg: parse error: unknown identifier: release_4.1
[255]
$ hg log -r 'revset(release_4.1(arch=x86,arm))'
hg: parse error: unknown identifier: release_4.1
[255]
$ hg log -r '"release_4.1(arch=x86,arm)"'
7:b29b25d7d687 Added tag release_4.1(candidate1) for changeset db72e24fe069 [release_4.1(arch=x86,arm)]
$ hg log -r '("release_4.1(arch=x86,arm)")'
7:b29b25d7d687 Added tag release_4.1(candidate1) for changeset db72e24fe069 [release_4.1(arch=x86,arm)]
$ hg log -r '::"release_4.1(arch=x86,arm)"'
0:a87874c6ec31 first []
1:43114e71eddd second [rev(0)]
2:fb616635b18f Added tag rev(0) for changeset 43114e71eddd ["foo"]
3:a50aae922707 Added tag "foo" for changeset fb616635b18f [foo-bar]
4:bbf52b87b370 Added tag foo-bar for changeset a50aae922707 [foo+bar]
5:ff42fde8edbb Added tag foo+bar for changeset bbf52b87b370 [1.2]
6:db72e24fe069 Added tag 1.2 for changeset ff42fde8edbb [release_4.1(candidate1)]
7:b29b25d7d687 Added tag release_4.1(candidate1) for changeset db72e24fe069 [release_4.1(arch=x86,arm)]
$ hg log -r '::release_4.1(arch=x86,arm)'
hg: parse error: unknown identifier: release_4.1
[255]
Test tag conflicting with revset function
$ hg tag 'secret(team=foo,project=bar)'
$ hg log -r 'secret(team=foo,project=bar)'
8:6b2e2d4ea455 Added tag release_4.1(arch=x86,arm) for changeset b29b25d7d687 [secret(team=foo,project=bar)]
$ hg log -r '(secret(team=foo,project=bar))'
hg: parse error: secret takes no arguments
[255]
$ hg log -r 'revset(secret(team=foo,project=bar))'
hg: parse error: secret takes no arguments
[255]
$ hg log -r '"secret(team=foo,project=bar)"'
8:6b2e2d4ea455 Added tag release_4.1(arch=x86,arm) for changeset b29b25d7d687 [secret(team=foo,project=bar)]
$ hg log -r '("secret(team=foo,project=bar)")'
8:6b2e2d4ea455 Added tag release_4.1(arch=x86,arm) for changeset b29b25d7d687 [secret(team=foo,project=bar)]
$ hg log -r '::"secret(team=foo,project=bar)"'
0:a87874c6ec31 first []
1:43114e71eddd second [rev(0)]
2:fb616635b18f Added tag rev(0) for changeset 43114e71eddd ["foo"]
3:a50aae922707 Added tag "foo" for changeset fb616635b18f [foo-bar]
4:bbf52b87b370 Added tag foo-bar for changeset a50aae922707 [foo+bar]
5:ff42fde8edbb Added tag foo+bar for changeset bbf52b87b370 [1.2]
6:db72e24fe069 Added tag 1.2 for changeset ff42fde8edbb [release_4.1(candidate1)]
7:b29b25d7d687 Added tag release_4.1(candidate1) for changeset db72e24fe069 [release_4.1(arch=x86,arm)]
8:6b2e2d4ea455 Added tag release_4.1(arch=x86,arm) for changeset b29b25d7d687 [secret(team=foo,project=bar)]
$ hg log -r '::secret(team=foo,project=bar)'
hg: parse error: secret takes no arguments
[255]
Test tag with space
$ hg tag 'my little version'
$ hg log -r 'my little version'
9:269192bf8fc3 Added tag secret(team=foo,project=bar) for changeset 6b2e2d4ea455 [my little version]
$ hg log -r '(my little version)'
hg: parse error at 4: unexpected token: symbol
((my little version)
^ here)
[255]
$ hg log -r 'revset(my little version)'
hg: parse error at 10: unexpected token: symbol
(revset(my little version)
^ here)
[255]
$ hg log -r '"my little version"'
9:269192bf8fc3 Added tag secret(team=foo,project=bar) for changeset 6b2e2d4ea455 [my little version]
$ hg log -r '("my little version")'
9:269192bf8fc3 Added tag secret(team=foo,project=bar) for changeset 6b2e2d4ea455 [my little version]
$ hg log -r '::"my little version"'
0:a87874c6ec31 first []
1:43114e71eddd second [rev(0)]
2:fb616635b18f Added tag rev(0) for changeset 43114e71eddd ["foo"]
3:a50aae922707 Added tag "foo" for changeset fb616635b18f [foo-bar]
4:bbf52b87b370 Added tag foo-bar for changeset a50aae922707 [foo+bar]
5:ff42fde8edbb Added tag foo+bar for changeset bbf52b87b370 [1.2]
6:db72e24fe069 Added tag 1.2 for changeset ff42fde8edbb [release_4.1(candidate1)]
7:b29b25d7d687 Added tag release_4.1(candidate1) for changeset db72e24fe069 [release_4.1(arch=x86,arm)]
8:6b2e2d4ea455 Added tag release_4.1(arch=x86,arm) for changeset b29b25d7d687 [secret(team=foo,project=bar)]
9:269192bf8fc3 Added tag secret(team=foo,project=bar) for changeset 6b2e2d4ea455 [my little version]
$ hg log -r '::my little version'
hg: parse error at 5: invalid token
(::my little version
^ here)
[255]