[PATCH/RFC 0/6] commit caching

This is the cleaned-up version of the commit caching patches I mentioned
here:

  http://article.gmane.org/gmane.comp.version-control.git/212329

The basic idea is to generate a cache file that sits alongside a
packfile and contains the timestamp, tree, and parents in a more compact
and easy-to-access format.

The timings from this one are roughly similar to what I posted earlier.
Unlike the earlier version, this one keeps the data for a single commit
together for better cache locality (though I don't think it made a big
difference in my tests, since my cold-cache timing test ends up touching
every commit anyway).  The short of it is that for an extra 31M of disk
space (~4%), I get a warm-cache speedup for "git rev-list --all" of
~4.2s to ~0.66s.

The big thing it does not (yet) do is use offsets to reference sha1s, as
Shawn suggested.  This would potentially drop the on-disk size from 84
bytes to 16 bytes per commit (or about 6M total for linux.git).

Coupled with using compression level 0 for trees (which do not compress
well at all, and yield only a 2% increase in size when left
uncompressed), my "git rev-list --objects --all" time drops from ~40s to
~25s. Perf reveals that we're spending most of the remaining time in
lookup_object. I've spent a fair bit of time trying to optimize that,
but with no luck; I think it's fairly close to optimal. The problem is
just that we call it a very large number of times, since it is the
mechanism by which we recognize that we have already processed each
sha1.

  [1/6]: csum-file: make sha1write const-correct
  [2/6]: strbuf: add string-chomping functions
  [3/6]: introduce pack metadata cache files
  [4/6]: introduce a commit metapack
  [5/6]: add git-metapack command
  [6/6]: commit: look up commit info in metapack

-Peff

We do not modify the buffer we are asked to write; mark it
with const so that callers with const buffers do not get
unnecessary complaints from the compiler.

Signed-off-by: Jeff King <redacted>
---
 csum-file.c | 6 +++---
 csum-file.h | 2 +-
 2 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/csum-file.c b/csum-file.c
index 53f5375..465971c 100644
--- a/csum-file.c
+++ b/csum-file.c

@@ -11,7 +11,7 @@
 #include "progress.h"
 #include "csum-file.h"
 
-static void flush(struct sha1file *f, void *buf, unsigned int count)
+static void flush(struct sha1file *f, const void *buf, unsigned int count)
 {
 	if (0 <= f->check_fd && count)  {
 		unsigned char check_buffer[8192];

@@ -86,13 +86,13 @@ int sha1write(struct sha1file *f, void *buf, unsigned int count)
 	return fd;
 }
 
-int sha1write(struct sha1file *f, void *buf, unsigned int count)
+int sha1write(struct sha1file *f, const void *buf, unsigned int count)
 {
 	while (count) {
 		unsigned offset = f->offset;
 		unsigned left = sizeof(f->buffer) - offset;
 		unsigned nr = count > left ? left : count;
-		void *data;
+		const void *data;
 
 		if (f->do_crc)
 			f->crc32 = crc32(f->crc32, buf, nr);

diff --git a/csum-file.h b/csum-file.h
index 3b540bd..9dedb03 100644
--- a/csum-file.h
+++ b/csum-file.h

@@ -34,7 +34,7 @@ extern int sha1close(struct sha1file *, unsigned char *, unsigned int);
 extern struct sha1file *sha1fd_check(const char *name);
 extern struct sha1file *sha1fd_throughput(int fd, const char *name, struct progress *tp);
 extern int sha1close(struct sha1file *, unsigned char *, unsigned int);
-extern int sha1write(struct sha1file *, void *, unsigned int);
+extern int sha1write(struct sha1file *, const void *, unsigned int);
 extern void sha1flush(struct sha1file *f);
 extern void crc32_begin(struct sha1file *);
 extern uint32_t crc32_end(struct sha1file *);

-- 
1.8.0.2.16.g72e2fc9

Sometimes it is handy to cut a trailing string off the end
of a strbuf (e.g., a file extension). These helper functions
make it a one-liner.

Signed-off-by: Jeff King <redacted>
---
 strbuf.c | 11 +++++++++++
 strbuf.h |  2 ++
 2 files changed, 13 insertions(+)

diff --git a/strbuf.c b/strbuf.c
index 9a373be..8199ced 100644
--- a/strbuf.c
+++ b/strbuf.c

@@ -106,6 +106,17 @@ void strbuf_ltrim(struct strbuf *sb)
 	sb->buf[sb->len] = '\0';
 }
 
+void strbuf_chompmem(struct strbuf *sb, const void *data, size_t len)
+{
+	if (sb->len >= len && !memcmp(data, sb->buf + sb->len - len, len))
+		strbuf_setlen(sb, sb->len - len);
+}
+
+void strbuf_chompstr(struct strbuf *sb, const char *str)
+{
+	strbuf_chompmem(sb, str, strlen(str));
+}
+
 struct strbuf **strbuf_split_buf(const char *str, size_t slen,
 				 int terminator, int max)
 {

diff --git a/strbuf.h b/strbuf.h
index ecae4e2..3aeb815 100644
--- a/strbuf.h
+++ b/strbuf.h

@@ -42,6 +42,8 @@ extern void strbuf_ltrim(struct strbuf *);
 extern void strbuf_trim(struct strbuf *);
 extern void strbuf_rtrim(struct strbuf *);
 extern void strbuf_ltrim(struct strbuf *);
+extern void strbuf_chompmem(struct strbuf *, const void *, size_t);
+extern void strbuf_chompstr(struct strbuf *, const char *);
 extern int strbuf_cmp(const struct strbuf *, const struct strbuf *);
 
 /*

-- 
1.8.0.2.16.g72e2fc9

The on-disk packfile format is nicely compact, but it does
not always provide the fastest format for looking up
information. This patch introduces the concept of
"metapacks", optional metadata files which can live
alongside packs and represent their data in different ways.
This can allow space-time tradeoffs in accessing certain
object data.

Such space-time tradeoffs have traditionally gone into the
.idx file (e.g., the fact that we can quickly find an
object's offset in the packfile is due to the index). In
theory, cached data could also go into the .idx file.
However, keeping it in a separate file makes backwards
compatibility much simpler. Older versions of git can simply
ignore the extra files and use the existing methods for
accessing object data. This also makes metapacks optional,
so you can easily tune the space-time tradeoff on a per-repo
basis.

TODO: document on-disk format in Documentation/technical
TODO: document api

Signed-off-by: Jeff King <redacted>
---
 Makefile   |   2 +
 metapack.c | 158 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 metapack.h |  42 ++++++++++++++++
 3 files changed, 202 insertions(+)
 create mode 100644 metapack.c
 create mode 100644 metapack.h

diff --git a/Makefile b/Makefile
index 731b6a8..3e4ae1b 100644
--- a/Makefile
+++ b/Makefile

@@ -660,6 +660,7 @@ LIB_H += mergesort.h
 LIB_H += merge-blobs.h
 LIB_H += merge-recursive.h
 LIB_H += mergesort.h
+LIB_H += metapack.h
 LIB_H += notes-cache.h
 LIB_H += notes-merge.h
 LIB_H += notes.h

@@ -778,6 +779,7 @@ LIB_OBJS += mergesort.o
 LIB_OBJS += merge-blobs.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += mergesort.o
+LIB_OBJS += metapack.o
 LIB_OBJS += name-hash.o
 LIB_OBJS += notes.o
 LIB_OBJS += notes-cache.o

diff --git a/metapack.c b/metapack.c
new file mode 100644
index 0000000..c859c95
--- /dev/null
+++ b/metapack.c

@@ -0,0 +1,158 @@
+#include "cache.h"
+#include "metapack.h"
+#include "csum-file.h"
+
+static struct sha1file *create_meta_tmp(void)
+{
+	char tmp[PATH_MAX];
+	int fd;
+
+	fd = odb_mkstemp(tmp, sizeof(tmp), "pack/tmp_meta_XXXXXX");
+	return sha1fd(fd, xstrdup(tmp));
+}
+
+static void write_meta_header(struct metapack_writer *mw, const char *id,
+			      uint32_t version)
+{
+	version = htonl(version);
+
+	sha1write(mw->out, "META", 4);
+	sha1write(mw->out, "\0\0\0\1", 4);
+	sha1write(mw->out, mw->pack->sha1, 20);
+	sha1write(mw->out, id, 4);
+	sha1write(mw->out, &version, 4);
+}
+
+void metapack_writer_init(struct metapack_writer *mw,
+			  const char *pack_idx,
+			  const char *name,
+			  int version)
+{
+	struct strbuf path = STRBUF_INIT;
+
+	memset(mw, 0, sizeof(*mw));
+
+	mw->pack = add_packed_git(pack_idx, strlen(pack_idx), 1);
+	if (!mw->pack || open_pack_index(mw->pack))
+		die("unable to open packfile '%s'", pack_idx);
+
+	strbuf_addstr(&path, pack_idx);
+	strbuf_chompstr(&path, ".idx");
+	strbuf_addch(&path, '.');
+	strbuf_addstr(&path, name);
+	mw->path = strbuf_detach(&path, NULL);
+
+	mw->out = create_meta_tmp();
+	write_meta_header(mw, name, version);
+}
+
+void metapack_writer_finish(struct metapack_writer *mw)
+{
+	const char *tmp = mw->out->name;
+
+	sha1close(mw->out, NULL, CSUM_FSYNC);
+	if (rename(tmp, mw->path))
+		die_errno("unable to rename temporary metapack file");
+
+	close_pack_index(mw->pack);
+	free(mw->pack);
+	free(mw->path);
+	free((char *)tmp);
+}
+
+void metapack_writer_add(struct metapack_writer *mw, const void *data, int len)
+{
+	sha1write(mw->out, data, len);
+}
+
+void metapack_writer_add_uint32(struct metapack_writer *mw, uint32_t v)
+{
+	v = htonl(v);
+	metapack_writer_add(mw, &v, 4);
+}
+
+void metapack_writer_foreach(struct metapack_writer *mw,
+			     metapack_writer_each_fn cb,
+			     void *data)
+{
+	const unsigned char *sha1;
+	uint32_t i = 0;
+
+	/*
+	 * We'll feed these to the callback in sorted order, since that is the
+	 * order that they are stored in the .idx file.
+	 */
+	while ((sha1 = nth_packed_object_sha1(mw->pack, i++)))
+		cb(mw, sha1, data);
+}
+
+int metapack_init(struct metapack *m,
+		  struct packed_git *pack,
+		  const char *name,
+		  uint32_t *version)
+{
+	struct strbuf path = STRBUF_INIT;
+	int fd;
+	struct stat st;
+
+	memset(m, 0, sizeof(*m));
+
+	strbuf_addstr(&path, pack->pack_name);
+	strbuf_chompstr(&path, ".pack");
+	strbuf_addch(&path, '.');
+	strbuf_addstr(&path, name);
+
+	fd = open(path.buf, O_RDONLY);
+	strbuf_release(&path);
+	if (fd < 0)
+		return -1;
+	if (fstat(fd, &st) < 0) {
+		close(fd);
+		return -1;
+	}
+
+	m->mapped_len = xsize_t(st.st_size);
+	m->mapped_buf = xmmap(NULL, m->mapped_len, PROT_READ, MAP_PRIVATE, fd, 0);
+	close(fd);
+
+	m->data = m->mapped_buf;
+	m->len = m->mapped_len;
+
+	if (m->len < 8 ||
+	    memcmp(m->mapped_buf, "META", 4) ||
+	    memcmp(m->mapped_buf + 4, "\0\0\0\1", 4)) {
+		warning("metapack '%s' for '%s' does not have a valid header",
+			name, pack->pack_name);
+		metapack_close(m);
+		return -1;
+	}
+	m->data += 8;
+	m->len -= 8;
+
+	if (m->len < 20 || hashcmp(m->data, pack->sha1)) {
+		warning("metapack '%s' for '%s' does not match pack sha1",
+			name, pack->pack_name);
+		metapack_close(m);
+		return -1;
+	}
+	m->data += 20;
+	m->len -= 20;
+
+	if (m->len < 8 || memcmp(m->data, name, 4)) {
+		warning("metapack '%s' for '%s' does not have expected header id",
+			name, pack->pack_name);
+		metapack_close(m);
+		return -1;
+	}
+	memcpy(version, m->data + 4, 4);
+	*version = ntohl(*version);
+	m->data += 8;
+	m->len -= 8;
+
+	return 0;
+}
+
+void metapack_close(struct metapack *m)
+{
+	munmap(m->mapped_buf, m->mapped_len);
+}

diff --git a/metapack.h b/metapack.h
new file mode 100644
index 0000000..6af17fe
--- /dev/null
+++ b/metapack.h

@@ -0,0 +1,42 @@
+#ifndef METAPACK_H
+#define METAPACK_H
+
+struct packed_git;
+struct sha1file;
+
+struct metapack_writer {
+	char *path;
+	struct packed_git *pack;
+	struct sha1file *out;
+};
+
+void metapack_writer_init(struct metapack_writer *mw,
+			  const char *pack_idx,
+			  const char *name,
+			  int version);
+void metapack_writer_add(struct metapack_writer *mw, const void *data, int len);
+void metapack_writer_add_uint32(struct metapack_writer *mw, uint32_t v);
+void metapack_writer_finish(struct metapack_writer *mw);
+
+typedef void (*metapack_writer_each_fn)(struct metapack_writer *,
+					const unsigned char *sha1,
+					void *data);
+void metapack_writer_foreach(struct metapack_writer *mw,
+			     metapack_writer_each_fn cb,
+			     void *data);
+
+struct metapack {
+	void *mapped_buf;
+	size_t mapped_len;
+
+	void *data;
+	size_t len;
+};
+
+int metapack_init(struct metapack *m,
+		  struct packed_git *pack,
+		  const char *name,
+		  uint32_t *version);
+void metapack_close(struct metapack *m);
+
+#endif

-- 
1.8.0.2.16.g72e2fc9

When we are doing a commit traversal that does not need to
look at the commit messages themselves (e.g., rev-list,
merge-base, etc), we spend a lot of time accessing,
decompressing, and parsing the commit objects just to find
the parent and timestamp information. We can make a
space-time tradeoff by caching that information on disk in a
compact, uncompressed format.

TODO: document on-disk format in Documentation/technical
TODO: document API

Signed-off-by: Jeff King <redacted>
---
 Makefile          |   2 +
 commit-metapack.c | 175 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 commit-metapack.h |  12 ++++
 3 files changed, 189 insertions(+)
 create mode 100644 commit-metapack.c
 create mode 100644 commit-metapack.h

diff --git a/Makefile b/Makefile
index 3e4ae1b..6ca5320 100644
--- a/Makefile
+++ b/Makefile

@@ -619,6 +619,7 @@ LIB_H += column.h
 LIB_H += cache.h
 LIB_H += color.h
 LIB_H += column.h
+LIB_H += commit-metapack.h
 LIB_H += commit.h
 LIB_H += compat/bswap.h
 LIB_H += compat/cygwin.h

@@ -730,6 +731,7 @@ LIB_OBJS += combine-diff.o
 LIB_OBJS += color.o
 LIB_OBJS += column.o
 LIB_OBJS += combine-diff.o
+LIB_OBJS += commit-metapack.o
 LIB_OBJS += commit.o
 LIB_OBJS += compat/obstack.o
 LIB_OBJS += compat/terminal.o

diff --git a/commit-metapack.c b/commit-metapack.c
new file mode 100644
index 0000000..2c19f48
--- /dev/null
+++ b/commit-metapack.c

@@ -0,0 +1,175 @@
+#include "cache.h"
+#include "commit-metapack.h"
+#include "metapack.h"
+#include "commit.h"
+#include "sha1-lookup.h"
+
+struct commit_metapack {
+	struct metapack mp;
+	uint32_t nr;
+	unsigned char *index;
+	unsigned char *data;
+	struct commit_metapack *next;
+};
+static struct commit_metapack *commit_metapacks;
+
+static struct commit_metapack *alloc_commit_metapack(struct packed_git *pack)
+{
+	struct commit_metapack *it = xcalloc(1, sizeof(*it));
+	uint32_t version;
+
+	if (metapack_init(&it->mp, pack, "commits", &version) < 0) {
+		free(it);
+		return NULL;
+	}
+	if (version != 1) {
+		/*
+		 * This file comes from a more recent git version. Don't bother
+		 * warning the user, as we'll just fallback to reading the
+		 * commits.
+		 */
+		metapack_close(&it->mp);
+		free(it);
+		return NULL;
+	}
+
+	if (it->mp.len < 4) {
+		warning("commit metapack for '%s' is truncated", pack->pack_name);
+		metapack_close(&it->mp);
+		free(it);
+		return NULL;
+	}
+	memcpy(&it->nr, it->mp.data, 4);
+	it->nr = ntohl(it->nr);
+
+	/*
+	 * We need 84 bytes for each entry: sha1(20), date(4), tree(20),
+	 * parents(40).
+	 */
+	if (it->mp.len < (84 * it->nr + 4)) {
+		warning("commit metapack for '%s' is truncated", pack->pack_name);
+		metapack_close(&it->mp);
+		free(it);
+		return NULL;
+	}
+
+	it->index = it->mp.data + 4;
+	it->data = it->index + 20 * it->nr;
+
+	return it;
+}
+
+static void prepare_commit_metapacks(void)
+{
+	static int initialized;
+	struct commit_metapack **tail = &commit_metapacks;
+	struct packed_git *p;
+
+	if (initialized)
+		return;
+
+	prepare_packed_git();
+	for (p = packed_git; p; p = p->next) {
+		struct commit_metapack *it = alloc_commit_metapack(p);
+
+		if (it) {
+			*tail = it;
+			tail = &it->next;
+		}
+	}
+
+	initialized = 1;
+}
+
+int commit_metapack(unsigned char *sha1,
+		    uint32_t *timestamp,
+		    unsigned char **tree,
+		    unsigned char **parent1,
+		    unsigned char **parent2)
+{
+	struct commit_metapack *p;
+
+	prepare_commit_metapacks();
+	for (p = commit_metapacks; p; p = p->next) {
+		unsigned char *data;
+		int pos = sha1_entry_pos(p->index, 20, 0, 0, p->nr, p->nr, sha1);
+		if (pos < 0)
+			continue;
+
+		/* timestamp(4) + tree(20) + parents(40) */
+		data = p->data + 64 * pos;
+		*timestamp = *(uint32_t *)data;
+		*timestamp = ntohl(*timestamp);
+		data += 4;
+		*tree = data;
+		data += 20;
+		*parent1 = data;
+		data += 20;
+		*parent2 = data;
+
+		return 0;
+	}
+
+	return -1;
+}
+
+static void get_commits(struct metapack_writer *mw,
+			const unsigned char *sha1,
+			void *data)
+{
+	struct commit_list ***tail = data;
+	enum object_type type = sha1_object_info(sha1, NULL);
+	struct commit *c;
+
+	if (type != OBJ_COMMIT)
+		return;
+
+	c = lookup_commit(sha1);
+	if (!c || parse_commit(c))
+		die("unable to read commit %s", sha1_to_hex(sha1));
+
+	/*
+	 * Our fixed-size parent list cannot represent root commits, nor
+	 * octopus merges. Just skip those commits, as we can fallback
+	 * in those rare cases to reading the actual commit object.
+	 */
+	if (!c->parents ||
+	    (c->parents && c->parents->next && c->parents->next->next))
+		return;
+
+	*tail = &commit_list_insert(c, *tail)->next;
+}
+
+void commit_metapack_write(const char *idx)
+{
+	struct metapack_writer mw;
+	struct commit_list *commits = NULL, *p;
+	struct commit_list **tail = &commits;
+	uint32_t nr = 0;
+
+	metapack_writer_init(&mw, idx, "commits", 1);
+
+	/* Figure out how many eligible commits we've got in this pack. */
+	metapack_writer_foreach(&mw, get_commits, &tail);
+	for (p = commits; p; p = p->next)
+		nr++;
+	metapack_writer_add_uint32(&mw, nr);
+
+	/* Then write an index of commit sha1s */
+	for (p = commits; p; p = p->next)
+		metapack_writer_add(&mw, p->item->object.sha1, 20);
+
+	/* Followed by the actual date/tree/parents data */
+	for (p = commits; p; p = p->next) {
+		struct commit *c = p->item;
+		metapack_writer_add_uint32(&mw, c->date);
+		metapack_writer_add(&mw, c->tree->object.sha1, 20);
+		metapack_writer_add(&mw, c->parents->item->object.sha1, 20);
+		metapack_writer_add(&mw,
+				    c->parents->next ?
+				    c->parents->next->item->object.sha1 :
+				    null_sha1, 20);
+	}
+
+	metapack_writer_finish(&mw);
+}

diff --git a/commit-metapack.h b/commit-metapack.h
new file mode 100644
index 0000000..4684573
--- /dev/null
+++ b/commit-metapack.h

@@ -0,0 +1,12 @@
+#ifndef METAPACK_COMMIT_H
+#define METAPACK_COMMIT_H
+
+int commit_metapack(unsigned char *sha1,
+		    uint32_t *timestamp,
+		    unsigned char **tree,
+		    unsigned char **parent1,
+		    unsigned char **parent2);
+
+void commit_metapack_write(const char *idx_file);
+
+#endif

-- 
1.8.0.2.16.g72e2fc9

This is a plumbing command for generating metapack files.
Right now it understands only the "commits" metapack (and
there is not yet a reader). Eventually we may want to build
this metapack automatically when we generate a new pack.
Let's be conservative for now, though, and let the idea
prove itself in practice before turning it on for everyone.

The commits metapack generated by this command is 84 bytes
per commit; for linux-2.6.git, this is about 31M.

TODO: documentation

Signed-off-by: Jeff King <redacted>
---
 .gitignore         |  1 +
 Makefile           |  1 +
 builtin.h          |  1 +
 builtin/metapack.c | 73 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 git-repack.sh      |  2 +-
 git.c              |  1 +
 6 files changed, 78 insertions(+), 1 deletion(-)
 create mode 100644 builtin/metapack.c

diff --git a/.gitignore b/.gitignore
index 6669bf0..3f67a36 100644
--- a/.gitignore
+++ b/.gitignore

@@ -93,6 +93,7 @@
 /git-merge-subtree
 /git-mergetool
 /git-mergetool--lib
+/git-metapack
 /git-mktag
 /git-mktree
 /git-name-rev

diff --git a/Makefile b/Makefile
index 6ca5320..3899699 100644
--- a/Makefile
+++ b/Makefile

@@ -905,6 +905,7 @@ BUILTIN_OBJS += builtin/merge-tree.o
 BUILTIN_OBJS += builtin/merge-ours.o
 BUILTIN_OBJS += builtin/merge-recursive.o
 BUILTIN_OBJS += builtin/merge-tree.o
+BUILTIN_OBJS += builtin/metapack.o
 BUILTIN_OBJS += builtin/mktag.o
 BUILTIN_OBJS += builtin/mktree.o
 BUILTIN_OBJS += builtin/mv.o

diff --git a/builtin.h b/builtin.h
index faef559..30108ab 100644
--- a/builtin.h
+++ b/builtin.h

@@ -97,6 +97,7 @@ extern int cmd_merge_tree(int argc, const char **argv, const char *prefix);
 extern int cmd_merge_file(int argc, const char **argv, const char *prefix);
 extern int cmd_merge_recursive(int argc, const char **argv, const char *prefix);
 extern int cmd_merge_tree(int argc, const char **argv, const char *prefix);
+extern int cmd_metapack(int argc, const char **argv, const char *prefix);
 extern int cmd_mktag(int argc, const char **argv, const char *prefix);
 extern int cmd_mktree(int argc, const char **argv, const char *prefix);
 extern int cmd_mv(int argc, const char **argv, const char *prefix);

diff --git a/builtin/metapack.c b/builtin/metapack.c
new file mode 100644
index 0000000..5fee6cf
--- /dev/null
+++ b/builtin/metapack.c

@@ -0,0 +1,73 @@
+#include "builtin.h"
+#include "parse-options.h"
+#include "commit-metapack.h"
+
+static const char *metapack_usage[] = {
+	N_("git metapack [options] <packindex...>"),
+	NULL
+};
+
+#define METAPACK_COMMITS (1<<0)
+
+static void metapack_one(const char *idx, int type)
+{
+	if (type & METAPACK_COMMITS)
+		commit_metapack_write(idx);
+}
+
+static void metapack_all(int type)
+{
+	struct strbuf path = STRBUF_INIT;
+	size_t dirlen;
+	DIR *dh;
+	struct dirent *de;
+
+	strbuf_addstr(&path, get_object_directory());
+	strbuf_addstr(&path, "/pack");
+	dirlen = path.len;
+
+	dh = opendir(path.buf);
+	if (!dh)
+		die_errno("unable to open pack directory '%s'", path.buf);
+	while ((de = readdir(dh))) {
+		if (!has_extension(de->d_name, ".idx"))
+			continue;
+
+		strbuf_addch(&path, '/');
+		strbuf_addstr(&path, de->d_name);
+		metapack_one(path.buf, type);
+		strbuf_setlen(&path, dirlen);
+	}
+
+	closedir(dh);
+	strbuf_release(&path);
+}
+
+int cmd_metapack(int argc, const char **argv, const char *prefix)
+{
+	int all = 0;
+	int type = 0;
+	struct option opts[] = {
+		OPT_BOOL(0, "all", &all, N_("create metapacks for all packs")),
+		OPT_BIT(0, "commits", &type, N_("create commit metapacks"),
+			METAPACK_COMMITS),
+		OPT_END()
+	};
+
+	argc = parse_options(argc, argv, prefix, opts, metapack_usage, 0);
+
+	if (all && argc)
+		usage_msg_opt(_("pack arguments do not make sense with --all"),
+			      metapack_usage, opts);
+	if (!type)
+		usage_msg_opt(_("no metapack type specified"),
+			      metapack_usage, opts);
+
+	if (all)
+		metapack_all(type);
+	else
+		for (; *argv; argv++)
+			metapack_one(*argv, type);
+
+	return 0;
+}

diff --git a/git-repack.sh b/git-repack.sh
index 7579331..e6a9773 100755
--- a/git-repack.sh
+++ b/git-repack.sh

@@ -180,7 +180,7 @@ then
 		  do
 			case " $fullbases " in
 			*" $e "*) ;;
-			*)	rm -f "$e.pack" "$e.idx" "$e.keep" ;;
+			*)	rm -f "$e.pack" "$e.idx" "$e.keep" "$e.commits";;
 			esac
 		  done
 		)

diff --git a/git.c b/git.c
index b10c18b..f6e5552 100644
--- a/git.c
+++ b/git.c

@@ -365,6 +365,7 @@ static void handle_internal_command(int argc, const char **argv)
 		{ "merge-recursive-theirs", cmd_merge_recursive, RUN_SETUP | NEED_WORK_TREE },
 		{ "merge-subtree", cmd_merge_recursive, RUN_SETUP | NEED_WORK_TREE },
 		{ "merge-tree", cmd_merge_tree, RUN_SETUP },
+		{ "metapack", cmd_metapack, RUN_SETUP },
 		{ "mktag", cmd_mktag, RUN_SETUP },
 		{ "mktree", cmd_mktree, RUN_SETUP },
 		{ "mv", cmd_mv, RUN_SETUP | NEED_WORK_TREE },

-- 
1.8.0.2.16.g72e2fc9

Now that we have the plumbing in place to generate and read
commit metapacks, we can hook them up to parse_commit to
fill in the traversal information much more quickly.

We only do so if save_commit_buffer is turned off;
otherwise, the callers will expect to be able to read
commit->buffer after parse_commit returns (and since our
cache obviously does not have that information, we must
leave it NULL). As callers learn to handle a NULL
commit->buffer, we can eventually relax this (while it might
seem like a useless no-op to use the cache if we are going
to load the commit anyway, many callers may first filter
based on the traversal, and end up loading the commit
message for only a subset of the commits).

With this patch (and having run "git metapack --all
--commits"), my best-of-five warm-cache "git rev-list
--count --all" traversal of linux-2.6.git drops from 4.219s
to 0.659s.

Similarly, cold-cache drops from 13.696s to 4.763s due to
the compactness of the cache data (but you are penalized, of
course, if you then want to actually look at the commit
messages, since you have not warmed them into the cache).

Signed-off-by: Jeff King <redacted>
---
 commit.c | 23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

diff --git a/commit.c b/commit.c
index e8eb0ae..b326201 100644
--- a/commit.c
+++ b/commit.c

@@ -8,6 +8,7 @@
 #include "notes.h"
 #include "gpg-interface.h"
 #include "mergesort.h"
+#include "commit-metapack.h"
 
 static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);
 

@@ -306,6 +307,24 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s
 	return 0;
 }
 
+static int parse_commit_metapack(struct commit *item)
+{
+	unsigned char *tree, *p1, *p2;
+	uint32_t ts;
+
+	if (commit_metapack(item->object.sha1, &ts, &tree, &p1, &p2) < 0)
+		return -1;
+
+	item->date = ts;
+	item->tree = lookup_tree(tree);
+	commit_list_insert(lookup_commit(p1), &item->parents);
+	if (!is_null_sha1(p2))
+		commit_list_insert(lookup_commit(p2), &item->parents->next);
+
+	item->object.parsed = 1;
+	return 0;
+}
+
 int parse_commit(struct commit *item)
 {
 	enum object_type type;

@@ -317,6 +336,10 @@ int parse_commit(struct commit *item)
 		return -1;
 	if (item->object.parsed)
 		return 0;
+
+	if (!save_commit_buffer && !parse_commit_metapack(item))
+		return 0;
+
 	buffer = read_sha1_file(item->object.sha1, &type, &size);
 	if (!buffer)
 		return error("Could not read %s",

-- 
1.8.0.2.16.g72e2fc9

On 01/29/2013 10:15 AM, Jeff King wrote:

It might be handy to have these functions return true/false based on
whether the suffix was actually found.

Please document the new functions in
Documentation/technical/api-strbuf.txt.  Personally I would also
advocate a "docstring" in the header file, but obviously that preference
is the exception rather than the rule in the git project :-(

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

On 01/29/2013 10:16 AM, Jeff King wrote:

When we are doing a commit traversal that does not need to
look at the commit messages themselves (e.g., rev-list,
merge-base, etc), we spend a lot of time accessing,
decompressing, and parsing the commit objects just to find
the parent and timestamp information. We can make a
space-time tradeoff by caching that information on disk in a
compact, uncompressed format.

TODO: document on-disk format in Documentation/technical
TODO: document API

Would this be a good place to add the commit generation number that is
so enthusiastically discussed on the mailing list from time to time?

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

On Tue, Jan 29, 2013 at 11:15:34AM +0100, Michael Haggerty wrote:

quoted

+void strbuf_chompmem(struct strbuf *sb, const void *data, size_t len)
+{
+	if (sb->len >= len && !memcmp(data, sb->buf + sb->len - len, len))
+		strbuf_setlen(sb, sb->len - len);
+}
+
+void strbuf_chompstr(struct strbuf *sb, const char *str)
+{
+	strbuf_chompmem(sb, str, strlen(str));
+}
+

It might be handy to have these functions return true/false based on
whether the suffix was actually found.

Yeah, that sounds reasonable.

Please document the new functions in
Documentation/technical/api-strbuf.txt.  Personally I would also
advocate a "docstring" in the header file, but obviously that preference
is the exception rather than the rule in the git project :-(

Will do. I need to document the metapack functions, too, so I was thinking
about experimenting with some inline documentation systems.

-Peff

On Tue, Jan 29, 2013 at 11:24:45AM +0100, Michael Haggerty wrote:

On 01/29/2013 10:16 AM, Jeff King wrote:

quoted

When we are doing a commit traversal that does not need to
look at the commit messages themselves (e.g., rev-list,
merge-base, etc), we spend a lot of time accessing,
decompressing, and parsing the commit objects just to find
the parent and timestamp information. We can make a
space-time tradeoff by caching that information on disk in a
compact, uncompressed format.

TODO: document on-disk format in Documentation/technical
TODO: document API

Would this be a good place to add the commit generation number that is
so enthusiastically discussed on the mailing list from time to time?

Yes, that is one of my goals. We may even be able to just replace the
timestamp field in the cache with a generation number. When it gets
pretty-printed we pull it out of the commit message again anyway, so in
theory the only use inside "struct commit" is for ordering. But I
haven't looked at all of the use sites yet to be sure nobody is
depending on it being an actual date stamp.

-Peff

Jeff King [off-list ref] writes:

+static void write_meta_header(struct metapack_writer *mw, const char *id,
+			      uint32_t version)
+{
+	version = htonl(version);
+
+	sha1write(mw->out, "META", 4);
+	sha1write(mw->out, "\0\0\0\1", 4);
+	sha1write(mw->out, mw->pack->sha1, 20);
+	sha1write(mw->out, id, 4);
+	sha1write(mw->out, &version, 4);
+}

It seems that you are very close to actually having a plumbing that
could also do the pack .idx files.  Until/unless that can be done, I
am not sure how much benefit we would be getting from a file format
that records a subtype "id" and a generic "META" type, instead of
just a single "id" as the type ehader.  But it is OK to use 8 extra
bytes if we can potentially gain something later.

Shouldn't id be validated with at least something like

	if (strlen(id) < 3)
		die("Bad id: %s", id);

to catch a call

	write_meta_header(&mw, "me", 47);

that will stuff 'm', 'e', NUL and the garbage the compiler/linker
combo has placed after that constant string in the 4-byte id field?

+void metapack_writer_init(struct metapack_writer *mw,
+			  const char *pack_idx,
+			  const char *name,
+			  int version)
+{
+	struct strbuf path = STRBUF_INIT;
+
+	memset(mw, 0, sizeof(*mw));
+
+	mw->pack = add_packed_git(pack_idx, strlen(pack_idx), 1);
+	if (!mw->pack || open_pack_index(mw->pack))
+		die("unable to open packfile '%s'", pack_idx);
+
+	strbuf_addstr(&path, pack_idx);
+	strbuf_chompstr(&path, ".idx");
+	strbuf_addch(&path, '.');
+	strbuf_addstr(&path, name);

Your chompstr() does not even validate if the given name ends with
".idx", so this sounds like a glorified way to say

	strbuf_splice(&path, path->len - strlen("idx"), strlen("idx"),
			 name, strlen(name));

to me.

+	mw->path = strbuf_detach(&path, NULL);
+
+	mw->out = create_meta_tmp();
+	write_meta_header(mw, name, version);
+}
+
+void metapack_writer_finish(struct metapack_writer *mw)
+{
+	const char *tmp = mw->out->name;
+
+	sha1close(mw->out, NULL, CSUM_FSYNC);
+	if (rename(tmp, mw->path))
+		die_errno("unable to rename temporary metapack file");

Who is responsible for running adjust_shared_perm()?  The caller, or
this function?

Jeff King [off-list ref] writes:

+int commit_metapack(unsigned char *sha1,
+		    uint32_t *timestamp,
+		    unsigned char **tree,
+		    unsigned char **parent1,
+		    unsigned char **parent2)
+{
+	struct commit_metapack *p;
+
+	prepare_commit_metapacks();
+	for (p = commit_metapacks; p; p = p->next) {
+		unsigned char *data;
+		int pos = sha1_entry_pos(p->index, 20, 0, 0, p->nr, p->nr, sha1);

This is a tangent, but isn't it about time to rip out the check for
GIT_USE_LOOKUP in find_pack_entry_one(), I wonder.

+	prepare_commit_metapacks();
+	for (p = commit_metapacks; p; p = p->next) {
+		unsigned char *data;
+		int pos = sha1_entry_pos(p->index, 20, 0, 0, p->nr, p->nr, sha1);
+		if (pos < 0)
+			continue;
+
+		/* timestamp(4) + tree(20) + parents(40) */
+		data = p->data + 64 * pos;
+		*timestamp = *(uint32_t *)data;
+		*timestamp = ntohl(*timestamp);
+		data += 4;
+		*tree = data;
+		data += 20;
+		*parent1 = data;
+		data += 20;
+		*parent2 = data;
+
+		return 0;
+	}
+
+	return -1;
+}

I am torn on this one.

These cached properties of a single commit will not change no matter
which pack it appears in, and it feels logically wrong, especially
when you record these object names in the full SHA-1 form, to tie a
"commit metapack" to a pack.  Logically there needs only one commit
metapack that describes all the commits known to the repository when
the metapack was created.

In order to reduce the disk footprint and I/O cost, the future
direction for this mechanism may want to point into an existing
store of SHA-1 hashes with a shorter file offset, and the .idx file
could be such a store, and in order to move in that direction, you
cannot avoid tying a metapack to a pack.

+static void get_commits(struct metapack_writer *mw,
+			const unsigned char *sha1,
+			void *data)
+{
+	struct commit_list ***tail = data;
+	enum object_type type = sha1_object_info(sha1, NULL);
+	struct commit *c;
+
+	if (type != OBJ_COMMIT)
+		return;
+
+	c = lookup_commit(sha1);
+	if (!c || parse_commit(c))
+		die("unable to read commit %s", sha1_to_hex(sha1));
+
+	/*
+	 * Our fixed-size parent list cannot represent root commits, nor
+	 * octopus merges. Just skip those commits, as we can fallback
+	 * in those rare cases to reading the actual commit object.
+	 */
+	if (!c->parents ||
+	    (c->parents && c->parents->next && c->parents->next->next))
+		return;
+
+	*tail = &commit_list_insert(c, *tail)->next;
+}

It feels somewhat wasteful to:

 - use commit_list for this, rather than an array of commit
   objects.  If you have a rough estimate of the number of commits
   in the pack, you could just preallocate a single array and use
   ALLOC_GROW() on it, no?

 - iterate over the .idx file and run sha1_object_info() and
   parse_commit() on many objects in the SHA-1 order.  Iterating in
   the way builtin/pack-objects.c::get_object_details() does avoids
   jumping around in existing packfiles, which may be more
   efficient, no?

+void commit_metapack_write(const char *idx)
+{
+	struct metapack_writer mw;
+	struct commit_list *commits = NULL, *p;
+	struct commit_list **tail = &commits;
+	uint32_t nr = 0;
+
+	metapack_writer_init(&mw, idx, "commits", 1);
+
+	/* Figure out how many eligible commits we've got in this pack. */
+	metapack_writer_foreach(&mw, get_commits, &tail);
+	for (p = commits; p; p = p->next)
+		nr++;

On Tue, Jan 29, 2013 at 4:15 PM, Jeff King [off-list ref] wrote:

+static void write_meta_header(struct metapack_writer *mw, const char *id,
+                             uint32_t version)
+{
+       version = htonl(version);
+
+       sha1write(mw->out, "META", 4);
+       sha1write(mw->out, "\0\0\0\1", 4);
+       sha1write(mw->out, mw->pack->sha1, 20);
+       sha1write(mw->out, id, 4);
+       sha1write(mw->out, &version, 4);
+}

Because you go with all-commit-info-in-one-file, perhaps we should
have an uint32_t bitmap to describe what info this cache contains? So
far we need 4 bits for date, tree, 1st and 2nd parents (yes, I still
want to check if storing 1-parent commits only gains us anything on
some other repos). When commit count comes, it can take the fifth bit.
Reachability bitmap offsets can take the sixth bit, if we just append
the bitmaps at the end of the same file.
-- 
Duy

On Tue, Jan 29, 2013 at 4:14 PM, Jeff King [off-list ref] wrote:

The timings from this one are roughly similar to what I posted earlier.
Unlike the earlier version, this one keeps the data for a single commit
together for better cache locality (though I don't think it made a big
difference in my tests, since my cold-cache timing test ends up touching
every commit anyway).  The short of it is that for an extra 31M of disk
space (~4%), I get a warm-cache speedup for "git rev-list --all" of
~4.2s to ~0.66s.

Some data point on caching 1-parent vs 2-parent commits on webkit
repo, 26k commits. With your changes (caching 2-parent commits), the
.commits file takes 2241600 bytes. "rev-list --all --quiet":

0.06user 0.00system 0:00.08elapsed 95%CPU (0avgtext+0avgdata 26288maxresident)k
0inputs+0outputs (0major+2094minor)pagefaults 0swaps

With caching 1-parent commits only, the .commits file takes 1707900
bytes (30% less), the same rev-list command:

0.07user 0.00system 0:00.07elapsed 96%CPU (0avgtext+0avgdata 24144maxresident)k
0inputs+0outputs (0major+1960minor)pagefaults 0swaps

Compared to the timing without caching at all:

0.72user 0.02system 0:00.76elapsed 98%CPU (0avgtext+0avgdata 108976maxresident)k
0inputs+0outputs (0major+7272minor)pagefaults 0swaps

The performance loss in 1-parent case is not significant while disk
saving is (although it'll be less impressive after you do Shawn's
suggestion not storing SHA-1 directly)
-- 
Duy

On Tue, Jan 29, 2013 at 4:16 PM, Jeff King [off-list ref] wrote:

+int commit_metapack(unsigned char *sha1,
+                   uint32_t *timestamp,
+                   unsigned char **tree,
+                   unsigned char **parent1,
+                   unsigned char **parent2)
+{

Nit picking. tree, parent1 and parent2 can/should be "const unsigned char **".
-- 
Duy

On 01/29/2013 12:10 PM, Jeff King wrote:

On Tue, Jan 29, 2013 at 11:15:34AM +0100, Michael Haggerty wrote:

quoted

Please document the new functions in
Documentation/technical/api-strbuf.txt.  Personally I would also
advocate a "docstring" in the header file, but obviously that preference
is the exception rather than the rule in the git project :-(

Will do. I need to document the metapack functions, too, so I was thinking
about experimenting with some inline documentation systems.

That would be great; it would make future API documentation much easier
and therefore (hopefully) more common.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

On Tue, Jan 29, 2013 at 09:35:12AM -0800, Junio C Hamano wrote:

Jeff King [off-list ref] writes:

quoted

+static void write_meta_header(struct metapack_writer *mw, const char *id,
+			      uint32_t version)
+{
+	version = htonl(version);
+
+	sha1write(mw->out, "META", 4);
+	sha1write(mw->out, "\0\0\0\1", 4);
+	sha1write(mw->out, mw->pack->sha1, 20);
+	sha1write(mw->out, id, 4);
+	sha1write(mw->out, &version, 4);
+}

It seems that you are very close to actually having a plumbing that
could also do the pack .idx files.  Until/unless that can be done, I
am not sure how much benefit we would be getting from a file format
that records a subtype "id" and a generic "META" type, instead of
just a single "id" as the type ehader.  But it is OK to use 8 extra
bytes if we can potentially gain something later.

Yeah, I considered going that route. I had initially envisioned having a
generic META file type that provided some services (like fixed-size
records), and then having individual subtypes below that. But as I
simplified the design, the META format became pretty much pointless. I
left it in as the 8 bytes are not really a big problem, and it means we
can treat metapacks generically in some cases without necessarily
knowing what is in them. But I don't have a specific use case in mind,
so perhaps it is just useless and confusing. I don't mind simplifying.

Shouldn't id be validated with at least something like

	if (strlen(id) < 3)
		die("Bad id: %s", id);

to catch a call

	write_meta_header(&mw, "me", 47);

that will stuff 'm', 'e', NUL and the garbage the compiler/linker
combo has placed after that constant string in the 4-byte id field?

Yes, the id does need to be at least 4 bytes. Since the id is intended
to be a static string, I had planned to just document the requirement in
the API documentation. I don't mind putting in a run-time check. I had
originally had a separate "id" parameter that could be "char id[4]", but
found that it was just redundant with the "name" parameter: you ended up
passing ("commit", "CMIT") or similar.

quoted

+	strbuf_addstr(&path, pack_idx);
+	strbuf_chompstr(&path, ".idx");
+	strbuf_addch(&path, '.');
+	strbuf_addstr(&path, name);

Your chompstr() does not even validate if the given name ends with
".idx",

Yeah, my intent was that it would be liberal in its input (i.e., take
just "pack-*"). E.g., you can run "git metapack pack/pack-XXXX".

so this sounds like a glorified way to say

	strbuf_splice(&path, path->len - strlen("idx"), strlen("idx"),
			 name, strlen(name));

to me.

Yup, though my version handles edge cases by not chomping (e.g., what
does splice do when path->len is less than 3?).

quoted

+void metapack_writer_finish(struct metapack_writer *mw)
+{
+	const char *tmp = mw->out->name;
+
+	sha1close(mw->out, NULL, CSUM_FSYNC);
+	if (rename(tmp, mw->path))
+		die_errno("unable to rename temporary metapack file");

Who is responsible for running adjust_shared_perm()?  The caller, or
this function?

I didn't think about it at all, but it seems pretty obvious to me that
this function should do so. Thanks for pointing it out.

-Peff

On Wed, Jan 30, 2013 at 08:30:57AM +0700, Nguyen Thai Ngoc Duy wrote:

On Tue, Jan 29, 2013 at 4:15 PM, Jeff King [off-list ref] wrote:

quoted

+static void write_meta_header(struct metapack_writer *mw, const char *id,
+                             uint32_t version)
+{
+       version = htonl(version);
+
+       sha1write(mw->out, "META", 4);
+       sha1write(mw->out, "\0\0\0\1", 4);
+       sha1write(mw->out, mw->pack->sha1, 20);
+       sha1write(mw->out, id, 4);
+       sha1write(mw->out, &version, 4);
+}

Because you go with all-commit-info-in-one-file, perhaps we should
have an uint32_t bitmap to describe what info this cache contains?  So
far we need 4 bits for date, tree, 1st and 2nd parents (yes, I still
want to check if storing 1-parent commits only gains us anything on
some other repos). When commit count comes, it can take the fifth bit.
Reachability bitmap offsets can take the sixth bit, if we just append
the bitmaps at the end of the same file.

I thought about having some programmatic self-describing header like
that. But it makes the implementation much harder to verify, and it is
not like there is much point in picking and choosing those bits. My plan
was to do a combination of:

  1. Put truly optional bits into a separate metapack (e.g.,
     reachability bitmaps).

  2. When something becomes obviously obsolete (e.g., we move to
     generation numbers instead of timestamps in commits), bump the
     version number.

-Peff

On Tue, Jan 29, 2013 at 09:38:10AM -0800, Junio C Hamano wrote:

Jeff King [off-list ref] writes:

quoted

+int commit_metapack(unsigned char *sha1,
+		    uint32_t *timestamp,
+		    unsigned char **tree,
+		    unsigned char **parent1,
+		    unsigned char **parent2)
+{
+	struct commit_metapack *p;
+
+	prepare_commit_metapacks();
+	for (p = commit_metapacks; p; p = p->next) {
+		unsigned char *data;
+		int pos = sha1_entry_pos(p->index, 20, 0, 0, p->nr, p->nr, sha1);

This is a tangent, but isn't it about time to rip out the check for
GIT_USE_LOOKUP in find_pack_entry_one(), I wonder.

Rip it out and always use sha1_entry_pos, or rip it out and never use
it? I have never been able to measure any speedup from it; I just use it
here to avoid rewriting the binary search myself. I do not think there
is any disadvantage to using it, so I'd be in favor of just
standardizing on it for any sha1 binary searches.

These cached properties of a single commit will not change no matter
which pack it appears in, and it feels logically wrong, especially
when you record these object names in the full SHA-1 form, to tie a
"commit metapack" to a pack.  Logically there needs only one commit
metapack that describes all the commits known to the repository when
the metapack was created.

True. I had originally envisioned it as tied to the packfile to help
manage the lifecycle. You know you need to generate a metapack for some
objects when they get packed, and you know you can throw it away when
the associated pack goes away. And it means you can verify the integrity
of the metapack by matching it to a particular packfile.

However, if you just have a commit cache, you can always blow the whole
thing away and regenerate it for all objects in the repo. It does not
have tied to a pack (you do end up doing some extra work at regeneration
when you are not doing a full repack, but it is really not enough to
worry about).

In order to reduce the disk footprint and I/O cost, the future
direction for this mechanism may want to point into an existing
store of SHA-1 hashes with a shorter file offset, and the .idx file
could be such a store, and in order to move in that direction, you
cannot avoid tying a metapack to a pack.

Yes. That was not one of my original goals for the commit cache, but I
do think it's a useful direction to go in. And reachability bitmaps
(which would eventually be their own metapacks) would generally want to
be per-pack, too, for the same reason.

quoted

+	*tail = &commit_list_insert(c, *tail)->next;
+}

It feels somewhat wasteful to:

 - use commit_list for this, rather than an array of commit
   objects.  If you have a rough estimate of the number of commits
   in the pack, you could just preallocate a single array and use
   ALLOC_GROW() on it, no?

We don't have a rough estimate, but yes, we could just use an array and
trust ALLOC_GROW to be reasonable. The use of commit_list did not have a
particular reason other than that it was simple (an array means stuffing
the array pointer and the nr and alloc counts into a struct to get to
the callback). The performance of writing the cache is dominated by
accessing the objects themselves, anyway. I don't mind changing it,
though, if you think it's clearer as an array.

 - iterate over the .idx file and run sha1_object_info() and
   parse_commit() on many objects in the SHA-1 order.  Iterating in
   the way builtin/pack-objects.c::get_object_details() does avoids
   jumping around in existing packfiles, which may be more
   efficient, no?

Probably, though generating the complete commit cache for linux-2.6.git
takes only about 7 seconds on my machine. I wasn't too concerned with
optimizing generation, since it will typically be dwarfed by repacking
costs. It might make more of a difference for doing a metapack on all
objects (e.g., reachability bitmaps).

The reason I do it in .idx order is that it feeds the callback in sorted
order, so a writer could in theory just use that output as-is (and my
initial version did that, as it wrote separate metapacks for each
element). This version now puts all data elements together (for cache
locality), and builds the in-memory list so we do not have to re-do
sha1_object_info repeatedly. So it could very easily just generate the
list in pack order and sort it at the end.

I'll look into that for the next version.

-Peff

On Wed, Jan 30, 2013 at 10:31:43AM +0700, Nguyen Thai Ngoc Duy wrote:

On Tue, Jan 29, 2013 at 4:14 PM, Jeff King [off-list ref] wrote:

quoted

The timings from this one are roughly similar to what I posted earlier.
Unlike the earlier version, this one keeps the data for a single commit
together for better cache locality (though I don't think it made a big
difference in my tests, since my cold-cache timing test ends up touching
every commit anyway).  The short of it is that for an extra 31M of disk
space (~4%), I get a warm-cache speedup for "git rev-list --all" of
~4.2s to ~0.66s.

Some data point on caching 1-parent vs 2-parent commits on webkit
repo, 26k commits. With your changes (caching 2-parent commits), the
.commits file takes 2241600 bytes. "rev-list --all --quiet":

Hmm. My webkit repo has zero merges in it (though it is the older
svn-based one). What percentage of the one you have are merges? How does
your 1-parent cache perform on something like git.git, where about 25%
of all commits are merges?

The performance loss in 1-parent case is not significant while disk
saving is (although it'll be less impressive after you do Shawn's
suggestion not storing SHA-1 directly)

Yeah, I think moving to offsets instead of sha1s is going to be a big
enough win that it won't matter anymore.

-Peff

On Wed, Jan 30, 2013 at 2:18 PM, Jeff King [off-list ref] wrote:

On Wed, Jan 30, 2013 at 10:31:43AM +0700, Nguyen Thai Ngoc Duy wrote:

quoted

On Tue, Jan 29, 2013 at 4:14 PM, Jeff King [off-list ref] wrote:

quoted

The timings from this one are roughly similar to what I posted earlier.
Unlike the earlier version, this one keeps the data for a single commit
together for better cache locality (though I don't think it made a big
difference in my tests, since my cold-cache timing test ends up touching
every commit anyway).  The short of it is that for an extra 31M of disk
space (~4%), I get a warm-cache speedup for "git rev-list --all" of
~4.2s to ~0.66s.

Some data point on caching 1-parent vs 2-parent commits on webkit
repo, 26k commits. With your changes (caching 2-parent commits), the
.commits file takes 2241600 bytes. "rev-list --all --quiet":

Hmm. My webkit repo has zero merges in it (though it is the older
svn-based one). What percentage of the one you have are merges? How does
your 1-parent cache perform on something like git.git, where about 25%
of all commits are merges?

git.git performs worse with 1-parent cache. But the point is it should
be customizable.

quoted

The performance loss in 1-parent case is not significant while disk
saving is (although it'll be less impressive after you do Shawn's
suggestion not storing SHA-1 directly)

Yeah, I think moving to offsets instead of sha1s is going to be a big
enough win that it won't matter anymore.

Yeah, if we use uint32_t instead of sha-1, the cache is just about
400k 2 parents for webkit, 312k for 1 parent. The total size is so
small that reduction does not really matter anymore.
-- 
Duy

On Tue, Jan 29, 2013 at 04:16:11AM -0500, Jeff King wrote:

When we are doing a commit traversal that does not need to
look at the commit messages themselves (e.g., rev-list,
merge-base, etc), we spend a lot of time accessing,
decompressing, and parsing the commit objects just to find
the parent and timestamp information. We can make a
space-time tradeoff by caching that information on disk in a
compact, uncompressed format.

And this is a (messy) patch on top that avoids storing SHA-1
directly. On my linux-2.6.git (575 MB pack, 73 MB index), .commits
file is 5.2 MB and 27 MB with and without my patch respectively. Nice
shrinkage.

However, performance seems to suffer too. Maybe I do more lookups than
necessary, I don't know. I should probably measure the cost of
revindex separately.

git rev-list --all --quiet on vanilla git:

real    0m3.645s
user    0m3.556s
sys     0m0.080s

commit cache without my patch:

real    0m0.723s
user    0m0.677s
sys     0m0.045s

and with my patch:

real    0m1.338s
user    0m1.259s
sys     0m0.075s


Another point, but not really important at this stage, I think we have
memory leak somewhere (lookup_commit??). It used up to 800 MB RES on
linux-2.6.git while generating the cache.

-- 8< --

diff --git a/cache.h b/cache.h
index 1f96f65..8048d5b 100644
--- a/cache.h
+++ b/cache.h

@@ -1069,6 +1069,7 @@ extern struct packed_git *add_packed_git(const char *, int, int);
 extern const unsigned char *nth_packed_object_sha1(struct packed_git *, uint32_t);
 extern off_t nth_packed_object_offset(const struct packed_git *, uint32_t);
 extern off_t find_pack_entry_one(const unsigned char *, struct packed_git *);
+extern int find_pack_entry_pos(const unsigned char *, struct packed_git *);
 extern int is_pack_valid(struct packed_git *);
 extern void *unpack_entry(struct packed_git *, off_t, enum object_type *, unsigned long *);
 extern unsigned long unpack_object_header_buffer(const unsigned char *buf, unsigned long len, enum object_type *type, unsigned long *sizep);

diff --git a/commit-metapack.c b/commit-metapack.c
index 2c19f48..55f7ea9 100644
--- a/commit-metapack.c
+++ b/commit-metapack.c

@@ -3,11 +3,12 @@
 #include "metapack.h"
 #include "commit.h"
 #include "sha1-lookup.h"
+#include "pack-revindex.h"
 
 struct commit_metapack {
 	struct metapack mp;
-	uint32_t nr;
-	unsigned char *index;
+	struct packed_git *pack;
+	uint32_t first, last;
 	unsigned char *data;
 	struct commit_metapack *next;
 };

@@ -16,7 +17,7 @@ static struct commit_metapack *commit_metapacks;
 static struct commit_metapack *alloc_commit_metapack(struct packed_git *pack)
 {
 	struct commit_metapack *it = xcalloc(1, sizeof(*it));
-	uint32_t version;
+	uint32_t version, nr;
 
 	if (metapack_init(&it->mp, pack, "commits", &version) < 0) {
 		free(it);

@@ -39,22 +40,25 @@ static struct commit_metapack *alloc_commit_metapack(struct packed_git *pack)
 		free(it);
 		return NULL;
 	}
-	memcpy(&it->nr, it->mp.data, 4);
-	it->nr = ntohl(it->nr);
+	memcpy(&it->first, it->mp.data, 4);
+	it->first = ntohl(it->first);
+	memcpy(&it->last, it->mp.data + 4, 4);
+	it->last = ntohl(it->last);
+	nr = it->last - it->first + 1;
+	it->pack = pack;
 
 	/*
-	 * We need 84 bytes for each entry: sha1(20), date(4), tree(20),
-	 * parents(40).
+	 * We need 16 bytes for each entry: date(4), tree index(4),
+	 * parent indexes(8).
 	 */
-	if (it->mp.len < (84 * it->nr + 4)) {
+	if (it->mp.len < (16 * nr + 8)) {
 		warning("commit metapack for '%s' is truncated", pack->pack_name);
 		metapack_close(&it->mp);
 		free(it);
 		return NULL;
 	}
 
-	it->index = it->mp.data + 4;
-	it->data = it->index + 20 * it->nr;
+	it->data = it->mp.data + 8;
 
 	return it;
 }

@@ -81,31 +85,61 @@ static void prepare_commit_metapacks(void)
 	initialized = 1;
 }
 
+static const unsigned char *idx_to_sha1(struct packed_git *p,
+					uint32_t nth)
+{
+	struct revindex_entry *revindex = get_revindex(p);
+	if (!revindex)
+		return NULL;
+	return nth_packed_object_sha1(p, revindex[nth].nr);
+}
+
 int commit_metapack(unsigned char *sha1,
 		    uint32_t *timestamp,
-		    unsigned char **tree,
-		    unsigned char **parent1,
-		    unsigned char **parent2)
+		    const unsigned char **tree,
+		    const unsigned char **parent1,
+		    const unsigned char **parent2)
 {
 	struct commit_metapack *p;
 
 	prepare_commit_metapacks();
 	for (p = commit_metapacks; p; p = p->next) {
 		unsigned char *data;
-		int pos = sha1_entry_pos(p->index, 20, 0, 0, p->nr, p->nr, sha1);
-		if (pos < 0)
+		uint32_t p1, p2;
+		struct revindex_entry *re, *base;
+		off_t off;
+		uint32_t pos;
+
+		base = get_revindex(p->pack);
+		off = find_pack_entry_one(sha1, p->pack);
+		if (!off)
+			continue;
+		re = find_pack_revindex(p->pack, off);
+		if (!re)
+			continue;
+		pos = re - base;
+		if (pos < p->first || pos > p->last)
 			continue;
 
 		/* timestamp(4) + tree(20) + parents(40) */
-		data = p->data + 64 * pos;
+		data = p->data + 16 * (pos - p->first);
 		*timestamp = *(uint32_t *)data;
 		*timestamp = ntohl(*timestamp);
+		if (!*timestamp)
+			return -1;
 		data += 4;
-		*tree = data;
-		data += 20;
-		*parent1 = data;
-		data += 20;
-		*parent2 = data;
+		*tree = idx_to_sha1(p->pack, ntohl(*(uint32_t*)data));
+		data += 4;
+		p1 = ntohl(*(uint32_t*)data);
+		*parent1 = idx_to_sha1(p->pack, p1);
+		data += 4;
+		p2 = ntohl(*(uint32_t*)data);
+		if (p1 == p2)
+			*parent2 = null_sha1;
+		else
+			*parent2 = idx_to_sha1(p->pack, p2);
+		if (!*tree || !*parent1 || !*parent2)
+			return -1;
 
 		return 0;
 	}