From: Martin Pieuchot <mpi@openbsd.org>
Subject: Re: faster history traversal for 'got blame'
To: gameoftrees@openbsd.org
Date: Tue, 7 Jan 2020 11:28:28 +0100

On 06/01/20(Mon) 17:57, Stefan Sperling wrote:
> This non-trivial patch adds history traversal support to got-read-pack.
> The goal is to speed up 'got blame'.
>
> Commits which do not change the blamed file do not need to be sent
> to the main process. Instead got-read-pack can send a list of commit
> IDs it has already traversed, followed by the final commit it found.
> This is sufficient for the commit graph to detect duplicates during
> traversal. And it saves a lot of syscalls for going back and forth
> over the imsg pipe to request individual commits.
>
> The cost is that we duplicate some code in got-read-pack in order
> to detect changed trees in that process. It does not use the same
> data structures as the main process so this code cannot be shared.
>
> This feature is restricted to first-parent traversal which means
> only 'got blame' and 'got log -f' will use this new code.
> And obviously it will only help with packed repositories.
> Run 'git repack -a' first if in doubt.
>
> Numbers from a DEBUG="-O2" build on a Matebook X (i5-7200U, NVME SSD):
>
> Before:
> $ for i in 1 2 3; do time got blame sys/kern/kern_tc.c >/dev/null; done
>     0m25.09s real     0m22.08s user     0m06.33s system
>     0m24.79s real     0m20.20s user     0m07.51s system
>     0m23.05s real     0m20.77s user     0m05.82s system
>
> After:
> $ for i in 1 2 3; do time got blame sys/kern/kern_tc.c >/dev/null; done
>     0m14.30s real     0m13.25s user     0m00.81s system
>     0m14.04s real     0m13.22s user     0m00.77s system
>     0m13.69s real     0m12.87s user     0m00.84s system
>
> This could probably be faster if we also added a cache of parsed
> tree objects to got-read-pack, but the diff is already large enough.
> And I haven't been super careful about avoiding unnecessary malloc
> and free calls since I wanted to focus on getting correctly working
> code for now.
>
> But it's already an improvement.
>
> Any comments or tests? OK?

'tog blame' is definitively faster with this.  But still unbearably slow
(understand unusable) compared to 'tig blame'.

So I confirm the improvement.  Thanks :o)

Before applying the diff:

	$ time got blame kern/kern_synch.c  > /dev/null
	    0m47.82s real     0m40.38s user     0m12.72s system

After:

	$ time got blame kern/kern_synch.c  > /dev/null
	    0m34.26s real     0m31.13s user     0m03.02s system

Comparing with tig-2.4.1:

	$ time git blame kern/kern_synch.c > /dev/null
	    0m09.42s real     0m08.59s user     0m00.60s system


Not sure if reducing malloc/free and caching could help you reduce user
time by a factor of 2 or 3, but that would be awesome :o)