Re: [PATCH 2/2] fsck: use oidset for skiplist

["René Scharfe" <l.s.r@web.de>]

Am 11.08.2018 um 18:54 schrieb Ævar Arnfjörð Bjarmason:
> 
> On Sat, Aug 11 2018, René Scharfe wrote:
> 
>> Object IDs to skip are stored in a shared static oid_array.  Lookups do
>> a binary search on the sorted array.  The code checks if the object IDs
>> are already in the correct order while loading and skips sorting in that
>> case.
> 
> I think this change makes sense, but it's missing an update to the
> relevant documentation in Documentation/config.txt:
> 
>     fsck.skipList::
>     	The path to a sorted list of object names (i.e. one SHA-1 per
>     	line) that are known to be broken in a non-fatal way and should
>     	be ignored. This feature is useful when an established project
>     	should be accepted despite early commits containing errors that
>     	can be safely ignored such as invalid committer email addresses.
>     	Note: corrupt objects cannot be skipped with this setting.
> 
> Also, while I use the skipList feature it's for something on the order
> of 10-100 objects, so whatever algorithm the lookup uses isn't going to
> matter, but I think it's interesting to describe the trade-off in the
> commit message.
> 
> I.e. what if I have 100K objects listed in the skipList, is it only
> going to be read lazily during fsck if there's an issue, or on every
> object etc? What's the difference in performance?

The list is loaded once up-front and a lookup is done for each
reportable issue and .gitmodules file.  Repositories without them
won't be affected at all.

100K bad objects sounds a bit extreme, but a fast-import can create
such a repository relatively quickly.  Here are the numbers with and
without the two patches:

Test                                            origin/master     HEAD
----------------------------------------------------------------------------------------
1450.3: fsck with 0 skipped bad commits         0.84(0.78+0.05)   0.83(0.80+0.03) -1.2%
1450.5: fsck with 1 skipped bad commits         0.84(0.77+0.07)   0.84(0.79+0.05) +0.0%
1450.7: fsck with 10 skipped bad commits        0.86(0.81+0.05)   0.84(0.78+0.06) -2.3%
1450.9: fsck with 100 skipped bad commits       0.85(0.78+0.07)   0.84(0.78+0.05) -1.2%
1450.11: fsck with 1000 skipped bad commits     0.85(0.80+0.05)   0.84(0.79+0.05) -1.2%
1450.13: fsck with 10000 skipped bad commits    0.85(0.78+0.07)   0.82(0.75+0.06) -3.5%
1450.15: fsck with 100000 skipped bad commits   0.73(0.64+0.09)   0.64(0.62+0.02) -12.3%

They look the same for most sizes, but with all 100000 bad objects in
the skiplist the oidset wins decisively.  Dialing it up a notch:

Test                                             origin/master     HEAD
-----------------------------------------------------------------------------------------
1450.3: fsck with 0 skipped bad commits          8.61(7.94+0.66)   8.72(8.14+0.58) +1.3%
1450.5: fsck with 1 skipped bad commits          8.51(7.87+0.63)   8.53(7.93+0.60) +0.2%
1450.7: fsck with 10 skipped bad commits         8.56(7.98+0.57)   8.54(7.91+0.63) -0.2%
1450.9: fsck with 100 skipped bad commits        8.65(8.00+0.65)   8.47(7.93+0.53) -2.1%
1450.11: fsck with 1000 skipped bad commits      8.69(8.16+0.53)   8.49(8.00+0.49) -2.3%
1450.13: fsck with 10000 skipped bad commits     8.69(8.13+0.56)   8.50(7.93+0.56) -2.2%
1450.15: fsck with 100000 skipped bad commits    8.78(8.18+0.60)   8.36(7.85+0.50) -4.8%
1450.17: fsck with 1000000 skipped bad commits   7.83(7.07+0.76)   6.55(6.42+0.12) -16.3%

So it looks like successful lookups are faster in the oidset and
the oid_array is quicker with just a handful of entries.

A L1 cache line of 64 bytes holds 3 consecutive SHA1 hashes, which
might explain it.

Here's the perf test code:

---
 t/perf/p1450-fsck.sh | 40 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 40 insertions(+)
 create mode 100755 t/perf/p1450-fsck.sh

diff --git a/t/perf/p1450-fsck.sh b/t/perf/p1450-fsck.sh
new file mode 100755
index 0000000000..7c89690777
--- /dev/null
+++ b/t/perf/p1450-fsck.sh
@@ -0,0 +1,40 @@
+#!/bin/sh
+
+test_description='Test fsck skipList performance'
+
+. ./perf-lib.sh
+
+test_perf_fresh_repo
+
+n=100000
+
+test_expect_success "setup $n bad commits" '
+	for i in $(test_seq 1 $n)
+	do
+		echo "commit refs/heads/master" &&
+		echo "committer C <c@example.com> 1234567890 +0000" &&
+		echo "data <<EOF" &&
+		echo "$i.Q." &&
+		echo "EOF"
+	done | q_to_nul | git fast-import
+'
+
+skip=0
+while test $skip -le $n
+do
+	test_expect_success "create skipList for $skip bad commits" '
+		git log --format=%H --max-count=$skip |
+		sort >skiplist
+	'
+
+	test_perf "fsck with $skip skipped bad commits"	'
+		git -c fsck.skipList=skiplist fsck
+	'
+
+	case $skip in
+	0) skip=1 ;;
+	*) skip=${skip}0 ;;
+	esac
+done
+
+test_done
-- 
2.18.0