Re: [PATCH 1/2] pack-objects: break out of want_object loop early

Jeff King [off-list ref] writes:

I got side-tracked by adding a t/perf test to show off the improvement.
It's rather tricky to get right and takes a long time to run. I _think_
I have it now, but am waiting for results. :)

Well, then I'd stop here and wait for the reroll to requeue.

Thanks.

On Tue, Jul 26, 2016 at 02:38:28PM -0700, Junio C Hamano wrote:

Jeff King [off-list ref] writes:

quoted

I got side-tracked by adding a t/perf test to show off the improvement.
It's rather tricky to get right and takes a long time to run. I _think_
I have it now, but am waiting for results. :)

Well, then I'd stop here and wait for the reroll to requeue.

So I hoped to follow up with my little perf-testing patch last night,
but the rabbit hole goes deeper. :)

It turns out that I could not replicate my earlier results using a perf
script like the one below. The problem is that it heavily depends on the
ordering of your packs. The early-break does not do any good if you
mostly end up finding your objects in the final pack in the list. And
that is the exact situation my perf script creates: imagine you had a
big repository, then 1000 pushes came in, and then you tried to run "git
repack". We sort reverse-chronologically, so the big pack is at the end,
and most lookups have to go through the entire pack list to get there.

In the normal object-lookup paths, we cache the last_found_pack and
check it first, but this loop has no equivalent (and until now it
wouldn't have helped much, because we generally had to walk the whole
list anyway).

I knew this was a potential issue and even had experimented this back
when the original patches were written, but in my experiments then it
didn't help much. That makes sense, though; any case that _was_ improved
by the first two patches would not benefit from reordering the pack
lookups, because that meant it was finding the objects early in the
search (or else the first two patches would have helped not at all).

And I think the particular case I was experimenting on back then was not
a normal "oops, we had some pushes and forgot to run gc". It was more
bizarre, and had several packs that had most of the objects duplicated.

So I think this is an area worth looking into; a series of small
incremental packs on top of a large one is what I would expect to be
the most common case, and the first two patches don't handle it well.

I tried a hacky version of the last_found_pack trick, and it does cut
the counting phase in half for my perf test. But no patch yet. One is
just that doing it cleanly is a little tricky. But two is that I've
wondered if we can do even better with a most-recently-used cache
instead of the last_pack_found hack. So I'm trying to implement and
measure that (both for this loop, and to see if it does better in
find_pack_entry).

Perf script below is just for a sneak peek at what I'm trying to
measure.

-Peff

-- >8 --
#!/bin/sh

test_description='performance with large numbers of packs'
. ./perf-lib.sh

test_perf_large_repo

# Pretend we just have a single branch and no reflogs, and that everything is
# in objects/pack; that makes our fake pack-building in the next step much
# simpler.
test_expect_success 'simplify reachability' '
	tip=$(git rev-parse --verify HEAD) &&
	git for-each-ref --format="option no-deref%0adelete %(refname)" |
	git update-ref --stdin &&
	rm -rf .git/logs &&
	git update-ref refs/heads/master $tip &&
	git symbolic-ref HEAD refs/heads/master &&
	git repack -ad
'

# A real many-pack situation would probably come from having a lot of pushes
# over time. We don't know how big each push would be, but we can fake it by
# just walking the first-parent chain and having each commit be its own "push".
# This isn't _entirely_ accurate, as real pushes would have some duplicate
# objects due to thin-pack fixing, but it's a reasonable approximation.
#
# And then all of the rest of the objects can go in a single packfile that
# represents the state before any of those pushes (actually, we'll generate
# that first because in such a setup it would be the oldest pack, and we sort
# the packs by reverse mtime inside git).
#
# We prepare this in a staging area, because we need to install our baseline
# set of packs for each iteration of the perf test (which unfortunately counts
# against their times, but is a limitation of the perf framework).
test_expect_success 'create a large number of packs' '
	mkdir staging &&

	pushes() {
		git rev-list --first-parent -1000 HEAD
	} &&
	pack() {
		git pack-objects --revs --delta-base-offset staging/pack
	} &&

	bottom=$(pushes | tail -n 1) &&
	echo "$bottom^" | pack &&

	pushes |
	while read rev
	do
		printf "%s\n^%s^" $rev $rev | pack ||
			return 1
	done &&

	setup_many_packs () {
		rm -f .git/objects/pack/* &&
		cp staging/* .git/objects/pack/
	} &&
	setup_many_packs
'

test_perf 'rev-list' '
	git rev-list --objects --all
'

test_perf 'full repack' '
	setup_many_packs &&
	git repack -ad
'

test_done

On Wed, Jul 27, 2016 at 2:13 PM, Jeff King [off-list ref] wrote:

... But two is that I've
wondered if we can do even better with a most-recently-used cache
instead of the last_pack_found hack. So I'm trying to implement and
measure that (both for this loop, and to see if it does better in
find_pack_entry).

It is always delightful to hear a well constructed description of a
thought process. Thanks.

One thing that made me wonder was what would happen to the
last_found that is static to has_sha1_pack_kept_or_nonlocal()
funciton, when we invalidate the packed_git list, but within the
context of pack-objects it is not likely?

On Wed, Jul 27, 2016 at 02:28:32PM -0700, Junio C Hamano wrote:

On Wed, Jul 27, 2016 at 2:13 PM, Jeff King [off-list ref] wrote:

quoted

... But two is that I've
wondered if we can do even better with a most-recently-used cache
instead of the last_pack_found hack. So I'm trying to implement and
measure that (both for this loop, and to see if it does better in
find_pack_entry).

It is always delightful to hear a well constructed description of a
thought process. Thanks.

One thing that made me wonder was what would happen to the
last_found that is static to has_sha1_pack_kept_or_nonlocal()
funciton, when we invalidate the packed_git list, but within the
context of pack-objects it is not likely?

I wondered that, too, and that's part of what I'm working on. :)

We leave the old packed_git structs in place when we re-read the pack
directory. That works because either we have them already opened (so
even though they're gone, we can still access them, and that's why we
_must_ keep the structs in place), or we will call is_pack_valid() and
notice that it went away (and quietly skip to checking the next pack).

There is one place where we do free the packed_git, but I actually think
we can stop doing so. Here's what I'm planning as part of my series:


-- >8 --
Subject: [PATCH] sha1_file: drop free_pack_by_name

The point of this function is to drop an entry from the
"packed_git" cache that points to a file we might be
overwriting, because our contents may not be the same (and
hence the only caller was pack-objects as it moved a
temporary packfile into place).

In older versions of git, this could happen because the
names of packfiles were derived from the set of objects they
contained, not the actual bits on disk. But since 1190a1a
(pack-objects: name pack files after trailer hash,
2013-12-05), the name reflects the actual bits on disk, and
any two packfiles with the same name can be used
interchangeably.

Dropping this function not only saves a few lines of code,
it makes the lifetime of "struct packed_git" much easier to
reason about: namely, we now do not ever free these structs.

Signed-off-by: Jeff King <redacted>
---
I won't be surprised if this fixes some obscure bug, because there may
be parts of the code that store a pointer to our packed_git that could
be invalidated (I'm certain the bitmap code does). But perhaps it
doesn't matter because it's rare for this function to trigger at all.

 cache.h      |  1 -
 pack-write.c |  1 -
 sha1_file.c  | 30 ------------------------------
 3 files changed, 32 deletions(-)

diff --git a/cache.h b/cache.h
index 3855ddf..57ef726 100644
--- a/cache.h
+++ b/cache.h

@@ -1416,7 +1416,6 @@ extern unsigned char *use_pack(struct packed_git *, struct pack_window **, off_t
 extern void close_pack_windows(struct packed_git *);
 extern void close_all_packs(void);
 extern void unuse_pack(struct pack_window **);
-extern void free_pack_by_name(const char *);
 extern void clear_delta_base_cache(void);
 extern struct packed_git *add_packed_git(const char *path, size_t path_len, int local);
 

diff --git a/pack-write.c b/pack-write.c
index 33293ce..ea0b788 100644
--- a/pack-write.c
+++ b/pack-write.c

@@ -354,7 +354,6 @@ void finish_tmp_packfile(struct strbuf *name_buffer,
 		die_errno("unable to make temporary index file readable");
 
 	strbuf_addf(name_buffer, "%s.pack", sha1_to_hex(sha1));
-	free_pack_by_name(name_buffer->buf);
 
 	if (rename(pack_tmp_name, name_buffer->buf))
 		die_errno("unable to rename temporary pack file");

diff --git a/sha1_file.c b/sha1_file.c
index d5e1121..e045d2f 100644
--- a/sha1_file.c
+++ b/sha1_file.c

@@ -891,36 +891,6 @@ void close_pack_index(struct packed_git *p)
 	}
 }
 
-/*
- * This is used by git-repack in case a newly created pack happens to
- * contain the same set of objects as an existing one.  In that case
- * the resulting file might be different even if its name would be the
- * same.  It is best to close any reference to the old pack before it is
- * replaced on disk.  Of course no index pointers or windows for given pack
- * must subsist at this point.  If ever objects from this pack are requested
- * again, the new version of the pack will be reinitialized through
- * reprepare_packed_git().
- */
-void free_pack_by_name(const char *pack_name)
-{
-	struct packed_git *p, **pp = &packed_git;
-
-	while (*pp) {
-		p = *pp;
-		if (strcmp(pack_name, p->pack_name) == 0) {
-			clear_delta_base_cache();
-			close_pack(p);
-			free(p->bad_object_sha1);
-			*pp = p->next;
-			if (last_found_pack == p)
-				last_found_pack = NULL;
-			free(p);
-			return;
-		}
-		pp = &p->next;
-	}
-}
-
 static unsigned int get_max_fd_limit(void)
 {
 #ifdef RLIMIT_NOFILE

-- 
2.9.2.607.g98dce7b