Re: [PATCH 2/2] fsck: use oidset for skiplist
- From
René Scharfe <l.s.r@web.de>
- Date
- Aug 25, 2018, 18:49 UTC
- Message-ID
- <113aa2d7-6f66-8d03-dda4-7337cda9b2df@web.de>
- In-Reply-To
- <87lg9csv2u.fsf@evledraar.gmail.com>
Am 11.08.2018 um 18:54 schrieb Ævar Arnfjörð Bjarmason:
Show 27 quoted lines
> > 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