tests/test-cache-abuse.t

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

Enable obsolete markers

  $ cat >> $HGRCPATH << EOF
  > [experimental]
  > evolution.createmarkers=True
  > [phases]
  > publish=False
  > EOF

Build a repo with some cacheable bits:

  $ hg init a
  $ cd a

  $ echo a > a
  $ hg ci -qAm0
  $ hg tag t1
  $ hg book -i bk1

  $ hg branch -q b2
  $ hg ci -Am1
  $ hg tag t2

  $ echo dumb > dumb
  $ hg ci -qAmdumb
  $ hg debugobsolete b1174d11b69e63cb0c5726621a43c859f0858d7f
  obsoleted 1 changesets

  $ hg phase -pr t1
  $ hg phase -fsr t2

Make a helper function to check cache damage invariants:

- command output shouldn't change
- cache should be present after first use
- corruption/repair should be silent (no exceptions or warnings)
- cache should survive deletion, overwrite, and append
- unreadable / unwriteable caches should be ignored
- cache should be rebuilt after corruption

  $ damage() {
  >  CMD=$1
  >  CACHE=.hg/cache/$2
  >  CLEAN=$3
  >  hg $CMD > before
  >  test -f $CACHE || echo "not present"
  >  echo bad > $CACHE
  >  test -z "$CLEAN" || $CLEAN
  >  hg $CMD > after
  >  "$RUNTESTDIR/pdiff" before after || echo "*** overwrite corruption"
  >  echo corruption >> $CACHE
  >  test -z "$CLEAN" || $CLEAN
  >  hg $CMD > after
  >  "$RUNTESTDIR/pdiff" before after || echo "*** append corruption"
  >  rm $CACHE
  >  mkdir $CACHE
  >  test -z "$CLEAN" || $CLEAN
  >  hg $CMD > after
  >  "$RUNTESTDIR/pdiff" before after || echo "*** read-only corruption"
  >  test -d $CACHE || echo "*** directory clobbered"
  >  rmdir $CACHE
  >  test -z "$CLEAN" || $CLEAN
  >  hg $CMD > after
  >  "$RUNTESTDIR/pdiff" before after || echo "*** missing corruption"
  >  test -f $CACHE || echo "not rebuilt"
  > }

Beat up tags caches:

  $ damage "tags --hidden" tags2
  $ damage tags tags2-visible
  $ damage "tag -f t3" hgtagsfnodes1
  1 new orphan changesets
  1 new orphan changesets
  1 new orphan changesets
  1 new orphan changesets
  1 new orphan changesets

Beat up branch caches:

  $ damage branches branch2-base "rm .hg/cache/branch2-[vs]*"
  $ damage branches branch2-served "rm .hg/cache/branch2-[bv]*"
  $ damage branches branch2-visible
  $ damage "log -r branch(.)" rbc-names-v1
  $ damage "log -r branch(default)" rbc-names-v1
  $ damage "log -r branch(b2)" rbc-revs-v1

We currently can't detect an rbc cache with unknown names:

  $ damage "log -qr branch(b2)" rbc-names-v1
  --- before	* (glob)
  +++ after	* (glob)
  @@ -1,8 +?,0 @@ (glob)
  -2:5fb7d38b9dc4
  -3:60b597ffdafa
  -4:b1174d11b69e
  -5:6354685872c0
  -6:5ebc725f1bef
  -7:7b76eec2f273
  -8:ef3428d9d644
  -9:ba7a936bc03c
  *** append corruption