{"thread":{"id":"32765","subject":"[PATCH/RFC 0/6] commit caching","startedAt":"2013-01-29T09:14:34Z","lastAt":"2013-03-18T12:20:11Z","messageCount":43,"participants":["Jeff King","Michael Haggerty","Junio C Hamano","Duy Nguyen","Shawn Pearce"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"208165","messageId":"20130129091434.GA6975@sigill.intra.peff.net","threadId":"32765","inReplyTo":null,"subject":"[PATCH/RFC 0/6] commit caching","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-01-29T09:14:34Z","receivedAt":"2013-01-29T09:14:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This is the cleaned-up version of the commit caching patches I mentioned\nhere:\n\n http://article.gmane.org/gmane.comp.version-control.git/212329\n\nThe basic idea is to generate a cache file that sits alongside a\npackfile and contains the timestamp, tree, and parents in a more compact\nand easy-to-access format.\n\nThe timings from this one are roughly similar to what I posted earlier.\nUnlike the earlier version, this one keeps the data for a single commit\ntogether for better cache locality (though I don't think it made a big\ndifference in my tests, since my cold-cache timing test ends up touching\nevery commit anyway). The short of it is that for an extra 31M of disk\nspace (~4%), I get a warm-cache speedup for \"git rev-list --all\" of\n~4.2s to ~0.66s.\n\nThe big thing it does not (yet) do is use offsets to reference sha1s, as\nShawn suggested. This would potentially drop the on-disk size from 84\nbytes to 16 bytes per commit (or about 6M total for linux.git).\n\nCoupled with using compression level 0 for trees (which do not compress\nwell at all, and yield only a 2% increase in size when left\nuncompressed), my \"git rev-list --objects --all\" time drops from ~40s to\n~25s. Perf reveals that we're spending most of the remaining time in\nlookup_object. I've spent a fair bit of time trying to optimize that,\nbut with no luck; I think it's fairly close to optimal. The problem is\njust that we call it a very large number of times, since it is the\nmechanism by which we recognize that we have already processed each\nsha1.\n\n [1/6]: csum-file: make sha1write const-correct\n [2/6]: strbuf: add string-chomping functions\n [3/6]: introduce pack metadata cache files\n [4/6]: introduce a commit metapack\n [5/6]: add git-metapack command\n [6/6]: commit: look up commit info in metapack\n\n-Peff\n"},{"id":"208166","messageId":"20130129091530.GA9999@sigill.intra.peff.net","threadId":"32765","inReplyTo":"20130129091434.GA6975@sigill.intra.peff.net","subject":"[PATCH 1/6] csum-file: make sha1write const-correct","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-01-29T09:15:30Z","receivedAt":"2013-01-29T09:15:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We do not modify the buffer we are asked to write; mark it\nwith const so that callers with const buffers do not get\nunnecessary complaints from the compiler.\n\nSigned-off-by: Jeff King \n---\n csum-file.c | 6 +++---\n csum-file.h | 2 +-\n 2 files changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/csum-file.c b/csum-file.c\nindex 53f5375..465971c 100644\n--- a/csum-file.c\n+++ b/csum-file.c\n@@ -11,7 +11,7 @@\n #include \"progress.h\"\n #include \"csum-file.h\"\n \n-static void flush(struct sha1file *f, void *buf, unsigned int count)\n+static void flush(struct sha1file *f, const void *buf, unsigned int count)\n {\n \tif (0 <= f->check_fd && count) {\n \t\tunsigned char check_buffer[8192];\n@@ -86,13 +86,13 @@ int sha1write(struct sha1file *f, void *buf, unsigned int count)\n \treturn fd;\n }\n \n-int sha1write(struct sha1file *f, void *buf, unsigned int count)\n+int sha1write(struct sha1file *f, const void *buf, unsigned int count)\n {\n \twhile (count) {\n \t\tunsigned offset = f->offset;\n \t\tunsigned left = sizeof(f->buffer) - offset;\n \t\tunsigned nr = count > left ? left : count;\n-\t\tvoid *data;\n+\t\tconst void *data;\n \n \t\tif (f->do_crc)\n \t\t\tf->crc32 = crc32(f->crc32, buf, nr);\ndiff --git a/csum-file.h b/csum-file.h\nindex 3b540bd..9dedb03 100644\n--- a/csum-file.h\n+++ b/csum-file.h\n@@ -34,7 +34,7 @@ extern int sha1close(struct sha1file *, unsigned char *, unsigned int);\n extern struct sha1file *sha1fd_check(const char *name);\n extern struct sha1file *sha1fd_throughput(int fd, const char *name, struct progress *tp);\n extern int sha1close(struct sha1file *, unsigned char *, unsigned int);\n-extern int sha1write(struct sha1file *, void *, unsigned int);\n+extern int sha1write(struct sha1file *, const void *, unsigned int);\n extern void sha1flush(struct sha1file *f);\n extern void crc32_begin(struct sha1file *);\n extern uint32_t crc32_end(struct sha1file *);\n-- \n1.8.0.2.16.g72e2fc9\n"},{"id":"208167","messageId":"20130129091540.GB9999@sigill.intra.peff.net","threadId":"32765","inReplyTo":"20130129091434.GA6975@sigill.intra.peff.net","subject":"[PATCH 2/6] strbuf: add string-chomping functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-01-29T09:15:40Z","receivedAt":"2013-01-29T09:15:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Sometimes it is handy to cut a trailing string off the end\nof a strbuf (e.g., a file extension). These helper functions\nmake it a one-liner.\n\nSigned-off-by: Jeff King \n---\n strbuf.c | 11 +++++++++++\n strbuf.h | 2 ++\n 2 files changed, 13 insertions(+)\n\ndiff --git a/strbuf.c b/strbuf.c\nindex 9a373be..8199ced 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -106,6 +106,17 @@ void strbuf_ltrim(struct strbuf *sb)\n \tsb->buf[sb->len] = '\\0';\n }\n \n+void strbuf_chompmem(struct strbuf *sb, const void *data, size_t len)\n+{\n+\tif (sb->len >= len && !memcmp(data, sb->buf + sb->len - len, len))\n+\t\tstrbuf_setlen(sb, sb->len - len);\n+}\n+\n+void strbuf_chompstr(struct strbuf *sb, const char *str)\n+{\n+\tstrbuf_chompmem(sb, str, strlen(str));\n+}\n+\n struct strbuf **strbuf_split_buf(const char *str, size_t slen,\n \t\t\t\t int terminator, int max)\n {\ndiff --git a/strbuf.h b/strbuf.h\nindex ecae4e2..3aeb815 100644\n--- a/strbuf.h\n+++ b/strbuf.h\n@@ -42,6 +42,8 @@ extern void strbuf_ltrim(struct strbuf *);\n extern void strbuf_trim(struct strbuf *);\n extern void strbuf_rtrim(struct strbuf *);\n extern void strbuf_ltrim(struct strbuf *);\n+extern void strbuf_chompmem(struct strbuf *, const void *, size_t);\n+extern void strbuf_chompstr(struct strbuf *, const char *);\n extern int strbuf_cmp(const struct strbuf *, const struct strbuf *);\n \n /*\n-- \n1.8.0.2.16.g72e2fc9\n"},{"id":"208168","messageId":"20130129091555.GC9999@sigill.intra.peff.net","threadId":"32765","inReplyTo":"20130129091434.GA6975@sigill.intra.peff.net","subject":"[PATCH 3/6] introduce pack metadata cache files","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-01-29T09:15:55Z","receivedAt":"2013-01-29T09:15:55Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The on-disk packfile format is nicely compact, but it does\nnot always provide the fastest format for looking up\ninformation. This patch introduces the concept of\n\"metapacks\", optional metadata files which can live\nalongside packs and represent their data in different ways.\nThis can allow space-time tradeoffs in accessing certain\nobject data.\n\nSuch space-time tradeoffs have traditionally gone into the\n.idx file (e.g., the fact that we can quickly find an\nobject's offset in the packfile is due to the index). In\ntheory, cached data could also go into the .idx file.\nHowever, keeping it in a separate file makes backwards\ncompatibility much simpler. Older versions of git can simply\nignore the extra files and use the existing methods for\naccessing object data. This also makes metapacks optional,\nso you can easily tune the space-time tradeoff on a per-repo\nbasis.\n\nTODO: document on-disk format in Documentation/technical\nTODO: document api\n\nSigned-off-by: Jeff King \n---\n Makefile | 2 +\n metapack.c | 158 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n metapack.h | 42 ++++++++++++++++\n 3 files changed, 202 insertions(+)\n create mode 100644 metapack.c\n create mode 100644 metapack.h\n\ndiff --git a/Makefile b/Makefile\nindex 731b6a8..3e4ae1b 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -660,6 +660,7 @@ LIB_H += mergesort.h\n LIB_H += merge-blobs.h\n LIB_H += merge-recursive.h\n LIB_H += mergesort.h\n+LIB_H += metapack.h\n LIB_H += notes-cache.h\n LIB_H += notes-merge.h\n LIB_H += notes.h\n@@ -778,6 +779,7 @@ LIB_OBJS += mergesort.o\n LIB_OBJS += merge-blobs.o\n LIB_OBJS += merge-recursive.o\n LIB_OBJS += mergesort.o\n+LIB_OBJS += metapack.o\n LIB_OBJS += name-hash.o\n LIB_OBJS += notes.o\n LIB_OBJS += notes-cache.o\ndiff --git a/metapack.c b/metapack.c\nnew file mode 100644\nindex 0000000..c859c95\n--- /dev/null\n+++ b/metapack.c\n@@ -0,0 +1,158 @@\n+#include \"cache.h\"\n+#include \"metapack.h\"\n+#include \"csum-file.h\"\n+\n+static struct sha1file *create_meta_tmp(void)\n+{\n+\tchar tmp[PATH_MAX];\n+\tint fd;\n+\n+\tfd = odb_mkstemp(tmp, sizeof(tmp), \"pack/tmp_meta_XXXXXX\");\n+\treturn sha1fd(fd, xstrdup(tmp));\n+}\n+\n+static void write_meta_header(struct metapack_writer *mw, const char *id,\n+\t\t\t uint32_t version)\n+{\n+\tversion = htonl(version);\n+\n+\tsha1write(mw->out, \"META\", 4);\n+\tsha1write(mw->out, \"\\0\\0\\0\\1\", 4);\n+\tsha1write(mw->out, mw->pack->sha1, 20);\n+\tsha1write(mw->out, id, 4);\n+\tsha1write(mw->out, &version, 4);\n+}\n+\n+void metapack_writer_init(struct metapack_writer *mw,\n+\t\t\t const char *pack_idx,\n+\t\t\t const char *name,\n+\t\t\t int version)\n+{\n+\tstruct strbuf path = STRBUF_INIT;\n+\n+\tmemset(mw, 0, sizeof(*mw));\n+\n+\tmw->pack = add_packed_git(pack_idx, strlen(pack_idx), 1);\n+\tif (!mw->pack || open_pack_index(mw->pack))\n+\t\tdie(\"unable to open packfile '%s'\", pack_idx);\n+\n+\tstrbuf_addstr(&path, pack_idx);\n+\tstrbuf_chompstr(&path, \".idx\");\n+\tstrbuf_addch(&path, '.');\n+\tstrbuf_addstr(&path, name);\n+\tmw->path = strbuf_detach(&path, NULL);\n+\n+\tmw->out = create_meta_tmp();\n+\twrite_meta_header(mw, name, version);\n+}\n+\n+void metapack_writer_finish(struct metapack_writer *mw)\n+{\n+\tconst char *tmp = mw->out->name;\n+\n+\tsha1close(mw->out, NULL, CSUM_FSYNC);\n+\tif (rename(tmp, mw->path))\n+\t\tdie_errno(\"unable to rename temporary metapack file\");\n+\n+\tclose_pack_index(mw->pack);\n+\tfree(mw->pack);\n+\tfree(mw->path);\n+\tfree((char *)tmp);\n+}\n+\n+void metapack_writer_add(struct metapack_writer *mw, const void *data, int len)\n+{\n+\tsha1write(mw->out, data, len);\n+}\n+\n+void metapack_writer_add_uint32(struct metapack_writer *mw, uint32_t v)\n+{\n+\tv = htonl(v);\n+\tmetapack_writer_add(mw, &v, 4);\n+}\n+\n+void metapack_writer_foreach(struct metapack_writer *mw,\n+\t\t\t metapack_writer_each_fn cb,\n+\t\t\t void *data)\n+{\n+\tconst unsigned char *sha1;\n+\tuint32_t i = 0;\n+\n+\t/*\n+\t * We'll feed these to the callback in sorted order, since that is the\n+\t * order that they are stored in the .idx file.\n+\t */\n+\twhile ((sha1 = nth_packed_object_sha1(mw->pack, i++)))\n+\t\tcb(mw, sha1, data);\n+}\n+\n+int metapack_init(struct metapack *m,\n+\t\t struct packed_git *pack,\n+\t\t const char *name,\n+\t\t uint32_t *version)\n+{\n+\tstruct strbuf path = STRBUF_INIT;\n+\tint fd;\n+\tstruct stat st;\n+\n+\tmemset(m, 0, sizeof(*m));\n+\n+\tstrbuf_addstr(&path, pack->pack_name);\n+\tstrbuf_chompstr(&path, \".pack\");\n+\tstrbuf_addch(&path, '.');\n+\tstrbuf_addstr(&path, name);\n+\n+\tfd = open(path.buf, O_RDONLY);\n+\tstrbuf_release(&path);\n+\tif (fd < 0)\n+\t\treturn -1;\n+\tif (fstat(fd, &st) < 0) {\n+\t\tclose(fd);\n+\t\treturn -1;\n+\t}\n+\n+\tm->mapped_len = xsize_t(st.st_size);\n+\tm->mapped_buf = xmmap(NULL, m->mapped_len, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tclose(fd);\n+\n+\tm->data = m->mapped_buf;\n+\tm->len = m->mapped_len;\n+\n+\tif (m->len < 8 ||\n+\t memcmp(m->mapped_buf, \"META\", 4) ||\n+\t memcmp(m->mapped_buf + 4, \"\\0\\0\\0\\1\", 4)) {\n+\t\twarning(\"metapack '%s' for '%s' does not have a valid header\",\n+\t\t\tname, pack->pack_name);\n+\t\tmetapack_close(m);\n+\t\treturn -1;\n+\t}\n+\tm->data += 8;\n+\tm->len -= 8;\n+\n+\tif (m->len < 20 || hashcmp(m->data, pack->sha1)) {\n+\t\twarning(\"metapack '%s' for '%s' does not match pack sha1\",\n+\t\t\tname, pack->pack_name);\n+\t\tmetapack_close(m);\n+\t\treturn -1;\n+\t}\n+\tm->data += 20;\n+\tm->len -= 20;\n+\n+\tif (m->len < 8 || memcmp(m->data, name, 4)) {\n+\t\twarning(\"metapack '%s' for '%s' does not have expected header id\",\n+\t\t\tname, pack->pack_name);\n+\t\tmetapack_close(m);\n+\t\treturn -1;\n+\t}\n+\tmemcpy(version, m->data + 4, 4);\n+\t*version = ntohl(*version);\n+\tm->data += 8;\n+\tm->len -= 8;\n+\n+\treturn 0;\n+}\n+\n+void metapack_close(struct metapack *m)\n+{\n+\tmunmap(m->mapped_buf, m->mapped_len);\n+}\ndiff --git a/metapack.h b/metapack.h\nnew file mode 100644\nindex 0000000..6af17fe\n--- /dev/null\n+++ b/metapack.h\n@@ -0,0 +1,42 @@\n+#ifndef METAPACK_H\n+#define METAPACK_H\n+\n+struct packed_git;\n+struct sha1file;\n+\n+struct metapack_writer {\n+\tchar *path;\n+\tstruct packed_git *pack;\n+\tstruct sha1file *out;\n+};\n+\n+void metapack_writer_init(struct metapack_writer *mw,\n+\t\t\t const char *pack_idx,\n+\t\t\t const char *name,\n+\t\t\t int version);\n+void metapack_writer_add(struct metapack_writer *mw, const void *data, int len);\n+void metapack_writer_add_uint32(struct metapack_writer *mw, uint32_t v);\n+void metapack_writer_finish(struct metapack_writer *mw);\n+\n+typedef void (*metapack_writer_each_fn)(struct metapack_writer *,\n+\t\t\t\t\tconst unsigned char *sha1,\n+\t\t\t\t\tvoid *data);\n+void metapack_writer_foreach(struct metapack_writer *mw,\n+\t\t\t metapack_writer_each_fn cb,\n+\t\t\t void *data);\n+\n+struct metapack {\n+\tvoid *mapped_buf;\n+\tsize_t mapped_len;\n+\n+\tvoid *data;\n+\tsize_t len;\n+};\n+\n+int metapack_init(struct metapack *m,\n+\t\t struct packed_git *pack,\n+\t\t const char *name,\n+\t\t uint32_t *version);\n+void metapack_close(struct metapack *m);\n+\n+#endif\n-- \n1.8.0.2.16.g72e2fc9\n"},{"id":"208169","messageId":"20130129091610.GD9999@sigill.intra.peff.net","threadId":"32765","inReplyTo":"20130129091434.GA6975@sigill.intra.peff.net","subject":"[PATCH 4/6] introduce a commit metapack","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-01-29T09:16:11Z","receivedAt":"2013-01-29T09:16:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we are doing a commit traversal that does not need to\nlook at the commit messages themselves (e.g., rev-list,\nmerge-base, etc), we spend a lot of time accessing,\ndecompressing, and parsing the commit objects just to find\nthe parent and timestamp information. We can make a\nspace-time tradeoff by caching that information on disk in a\ncompact, uncompressed format.\n\nTODO: document on-disk format in Documentation/technical\nTODO: document API\n\nSigned-off-by: Jeff King \n---\n Makefile | 2 +\n commit-metapack.c | 175 ++++++++++++++++++++++++++++++++++++++++++++++++++++++\n commit-metapack.h | 12 ++++\n 3 files changed, 189 insertions(+)\n create mode 100644 commit-metapack.c\n create mode 100644 commit-metapack.h\n\ndiff --git a/Makefile b/Makefile\nindex 3e4ae1b..6ca5320 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -619,6 +619,7 @@ LIB_H += column.h\n LIB_H += cache.h\n LIB_H += color.h\n LIB_H += column.h\n+LIB_H += commit-metapack.h\n LIB_H += commit.h\n LIB_H += compat/bswap.h\n LIB_H += compat/cygwin.h\n@@ -730,6 +731,7 @@ LIB_OBJS += combine-diff.o\n LIB_OBJS += color.o\n LIB_OBJS += column.o\n LIB_OBJS += combine-diff.o\n+LIB_OBJS += commit-metapack.o\n LIB_OBJS += commit.o\n LIB_OBJS += compat/obstack.o\n LIB_OBJS += compat/terminal.o\ndiff --git a/commit-metapack.c b/commit-metapack.c\nnew file mode 100644\nindex 0000000..2c19f48\n--- /dev/null\n+++ b/commit-metapack.c\n@@ -0,0 +1,175 @@\n+#include \"cache.h\"\n+#include \"commit-metapack.h\"\n+#include \"metapack.h\"\n+#include \"commit.h\"\n+#include \"sha1-lookup.h\"\n+\n+struct commit_metapack {\n+\tstruct metapack mp;\n+\tuint32_t nr;\n+\tunsigned char *index;\n+\tunsigned char *data;\n+\tstruct commit_metapack *next;\n+};\n+static struct commit_metapack *commit_metapacks;\n+\n+static struct commit_metapack *alloc_commit_metapack(struct packed_git *pack)\n+{\n+\tstruct commit_metapack *it = xcalloc(1, sizeof(*it));\n+\tuint32_t version;\n+\n+\tif (metapack_init(&it->mp, pack, \"commits\", &version) < 0) {\n+\t\tfree(it);\n+\t\treturn NULL;\n+\t}\n+\tif (version != 1) {\n+\t\t/*\n+\t\t * This file comes from a more recent git version. Don't bother\n+\t\t * warning the user, as we'll just fallback to reading the\n+\t\t * commits.\n+\t\t */\n+\t\tmetapack_close(&it->mp);\n+\t\tfree(it);\n+\t\treturn NULL;\n+\t}\n+\n+\tif (it->mp.len < 4) {\n+\t\twarning(\"commit metapack for '%s' is truncated\", pack->pack_name);\n+\t\tmetapack_close(&it->mp);\n+\t\tfree(it);\n+\t\treturn NULL;\n+\t}\n+\tmemcpy(&it->nr, it->mp.data, 4);\n+\tit->nr = ntohl(it->nr);\n+\n+\t/*\n+\t * We need 84 bytes for each entry: sha1(20), date(4), tree(20),\n+\t * parents(40).\n+\t */\n+\tif (it->mp.len < (84 * it->nr + 4)) {\n+\t\twarning(\"commit metapack for '%s' is truncated\", pack->pack_name);\n+\t\tmetapack_close(&it->mp);\n+\t\tfree(it);\n+\t\treturn NULL;\n+\t}\n+\n+\tit->index = it->mp.data + 4;\n+\tit->data = it->index + 20 * it->nr;\n+\n+\treturn it;\n+}\n+\n+static void prepare_commit_metapacks(void)\n+{\n+\tstatic int initialized;\n+\tstruct commit_metapack **tail = &commit_metapacks;\n+\tstruct packed_git *p;\n+\n+\tif (initialized)\n+\t\treturn;\n+\n+\tprepare_packed_git();\n+\tfor (p = packed_git; p; p = p->next) {\n+\t\tstruct commit_metapack *it = alloc_commit_metapack(p);\n+\n+\t\tif (it) {\n+\t\t\t*tail = it;\n+\t\t\ttail = &it->next;\n+\t\t}\n+\t}\n+\n+\tinitialized = 1;\n+}\n+\n+int commit_metapack(unsigned char *sha1,\n+\t\t uint32_t *timestamp,\n+\t\t unsigned char **tree,\n+\t\t unsigned char **parent1,\n+\t\t unsigned char **parent2)\n+{\n+\tstruct commit_metapack *p;\n+\n+\tprepare_commit_metapacks();\n+\tfor (p = commit_metapacks; p; p = p->next) {\n+\t\tunsigned char *data;\n+\t\tint pos = sha1_entry_pos(p->index, 20, 0, 0, p->nr, p->nr, sha1);\n+\t\tif (pos < 0)\n+\t\t\tcontinue;\n+\n+\t\t/* timestamp(4) + tree(20) + parents(40) */\n+\t\tdata = p->data + 64 * pos;\n+\t\t*timestamp = *(uint32_t *)data;\n+\t\t*timestamp = ntohl(*timestamp);\n+\t\tdata += 4;\n+\t\t*tree = data;\n+\t\tdata += 20;\n+\t\t*parent1 = data;\n+\t\tdata += 20;\n+\t\t*parent2 = data;\n+\n+\t\treturn 0;\n+\t}\n+\n+\treturn -1;\n+}\n+\n+static void get_commits(struct metapack_writer *mw,\n+\t\t\tconst unsigned char *sha1,\n+\t\t\tvoid *data)\n+{\n+\tstruct commit_list ***tail = data;\n+\tenum object_type type = sha1_object_info(sha1, NULL);\n+\tstruct commit *c;\n+\n+\tif (type != OBJ_COMMIT)\n+\t\treturn;\n+\n+\tc = lookup_commit(sha1);\n+\tif (!c || parse_commit(c))\n+\t\tdie(\"unable to read commit %s\", sha1_to_hex(sha1));\n+\n+\t/*\n+\t * Our fixed-size parent list cannot represent root commits, nor\n+\t * octopus merges. Just skip those commits, as we can fallback\n+\t * in those rare cases to reading the actual commit object.\n+\t */\n+\tif (!c->parents ||\n+\t (c->parents && c->parents->next && c->parents->next->next))\n+\t\treturn;\n+\n+\t*tail = &commit_list_insert(c, *tail)->next;\n+}\n+\n+void commit_metapack_write(const char *idx)\n+{\n+\tstruct metapack_writer mw;\n+\tstruct commit_list *commits = NULL, *p;\n+\tstruct commit_list **tail = &commits;\n+\tuint32_t nr = 0;\n+\n+\tmetapack_writer_init(&mw, idx, \"commits\", 1);\n+\n+\t/* Figure out how many eligible commits we've got in this pack. */\n+\tmetapack_writer_foreach(&mw, get_commits, &tail);\n+\tfor (p = commits; p; p = p->next)\n+\t\tnr++;\n+\tmetapack_writer_add_uint32(&mw, nr);\n+\n+\t/* Then write an index of commit sha1s */\n+\tfor (p = commits; p; p = p->next)\n+\t\tmetapack_writer_add(&mw, p->item->object.sha1, 20);\n+\n+\t/* Followed by the actual date/tree/parents data */\n+\tfor (p = commits; p; p = p->next) {\n+\t\tstruct commit *c = p->item;\n+\t\tmetapack_writer_add_uint32(&mw, c->date);\n+\t\tmetapack_writer_add(&mw, c->tree->object.sha1, 20);\n+\t\tmetapack_writer_add(&mw, c->parents->item->object.sha1, 20);\n+\t\tmetapack_writer_add(&mw,\n+\t\t\t\t c->parents->next ?\n+\t\t\t\t c->parents->next->item->object.sha1 :\n+\t\t\t\t null_sha1, 20);\n+\t}\n+\n+\tmetapack_writer_finish(&mw);\n+}\ndiff --git a/commit-metapack.h b/commit-metapack.h\nnew file mode 100644\nindex 0000000..4684573\n--- /dev/null\n+++ b/commit-metapack.h\n@@ -0,0 +1,12 @@\n+#ifndef METAPACK_COMMIT_H\n+#define METAPACK_COMMIT_H\n+\n+int commit_metapack(unsigned char *sha1,\n+\t\t uint32_t *timestamp,\n+\t\t unsigned char **tree,\n+\t\t unsigned char **parent1,\n+\t\t unsigned char **parent2);\n+\n+void commit_metapack_write(const char *idx_file);\n+\n+#endif\n-- \n1.8.0.2.16.g72e2fc9\n"},{"id":"208170","messageId":"20130129091630.GE9999@sigill.intra.peff.net","threadId":"32765","inReplyTo":"20130129091434.GA6975@sigill.intra.peff.net","subject":"[PATCH 5/6] add git-metapack command","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-01-29T09:16:31Z","receivedAt":"2013-01-29T09:16:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This is a plumbing command for generating metapack files.\nRight now it understands only the \"commits\" metapack (and\nthere is not yet a reader). Eventually we may want to build\nthis metapack automatically when we generate a new pack.\nLet's be conservative for now, though, and let the idea\nprove itself in practice before turning it on for everyone.\n\nThe commits metapack generated by this command is 84 bytes\nper commit; for linux-2.6.git, this is about 31M.\n\nTODO: documentation\n\nSigned-off-by: Jeff King \n---\n .gitignore | 1 +\n Makefile | 1 +\n builtin.h | 1 +\n builtin/metapack.c | 73 ++++++++++++++++++++++++++++++++++++++++++++++++++++++\n git-repack.sh | 2 +-\n git.c | 1 +\n 6 files changed, 78 insertions(+), 1 deletion(-)\n create mode 100644 builtin/metapack.c\n\ndiff --git a/.gitignore b/.gitignore\nindex 6669bf0..3f67a36 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -93,6 +93,7 @@\n /git-merge-subtree\n /git-mergetool\n /git-mergetool--lib\n+/git-metapack\n /git-mktag\n /git-mktree\n /git-name-rev\ndiff --git a/Makefile b/Makefile\nindex 6ca5320..3899699 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -905,6 +905,7 @@ BUILTIN_OBJS += builtin/merge-tree.o\n BUILTIN_OBJS += builtin/merge-ours.o\n BUILTIN_OBJS += builtin/merge-recursive.o\n BUILTIN_OBJS += builtin/merge-tree.o\n+BUILTIN_OBJS += builtin/metapack.o\n BUILTIN_OBJS += builtin/mktag.o\n BUILTIN_OBJS += builtin/mktree.o\n BUILTIN_OBJS += builtin/mv.o\ndiff --git a/builtin.h b/builtin.h\nindex faef559..30108ab 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -97,6 +97,7 @@ extern int cmd_merge_tree(int argc, const char **argv, const char *prefix);\n extern int cmd_merge_file(int argc, const char **argv, const char *prefix);\n extern int cmd_merge_recursive(int argc, const char **argv, const char *prefix);\n extern int cmd_merge_tree(int argc, const char **argv, const char *prefix);\n+extern int cmd_metapack(int argc, const char **argv, const char *prefix);\n extern int cmd_mktag(int argc, const char **argv, const char *prefix);\n extern int cmd_mktree(int argc, const char **argv, const char *prefix);\n extern int cmd_mv(int argc, const char **argv, const char *prefix);\ndiff --git a/builtin/metapack.c b/builtin/metapack.c\nnew file mode 100644\nindex 0000000..5fee6cf\n--- /dev/null\n+++ b/builtin/metapack.c\n@@ -0,0 +1,73 @@\n+#include \"builtin.h\"\n+#include \"parse-options.h\"\n+#include \"commit-metapack.h\"\n+\n+static const char *metapack_usage[] = {\n+\tN_(\"git metapack [options] \"),\n+\tNULL\n+};\n+\n+#define METAPACK_COMMITS (1<<0)\n+\n+static void metapack_one(const char *idx, int type)\n+{\n+\tif (type & METAPACK_COMMITS)\n+\t\tcommit_metapack_write(idx);\n+}\n+\n+static void metapack_all(int type)\n+{\n+\tstruct strbuf path = STRBUF_INIT;\n+\tsize_t dirlen;\n+\tDIR *dh;\n+\tstruct dirent *de;\n+\n+\tstrbuf_addstr(&path, get_object_directory());\n+\tstrbuf_addstr(&path, \"/pack\");\n+\tdirlen = path.len;\n+\n+\tdh = opendir(path.buf);\n+\tif (!dh)\n+\t\tdie_errno(\"unable to open pack directory '%s'\", path.buf);\n+\twhile ((de = readdir(dh))) {\n+\t\tif (!has_extension(de->d_name, \".idx\"))\n+\t\t\tcontinue;\n+\n+\t\tstrbuf_addch(&path, '/');\n+\t\tstrbuf_addstr(&path, de->d_name);\n+\t\tmetapack_one(path.buf, type);\n+\t\tstrbuf_setlen(&path, dirlen);\n+\t}\n+\n+\tclosedir(dh);\n+\tstrbuf_release(&path);\n+}\n+\n+int cmd_metapack(int argc, const char **argv, const char *prefix)\n+{\n+\tint all = 0;\n+\tint type = 0;\n+\tstruct option opts[] = {\n+\t\tOPT_BOOL(0, \"all\", &all, N_(\"create metapacks for all packs\")),\n+\t\tOPT_BIT(0, \"commits\", &type, N_(\"create commit metapacks\"),\n+\t\t\tMETAPACK_COMMITS),\n+\t\tOPT_END()\n+\t};\n+\n+\targc = parse_options(argc, argv, prefix, opts, metapack_usage, 0);\n+\n+\tif (all && argc)\n+\t\tusage_msg_opt(_(\"pack arguments do not make sense with --all\"),\n+\t\t\t metapack_usage, opts);\n+\tif (!type)\n+\t\tusage_msg_opt(_(\"no metapack type specified\"),\n+\t\t\t metapack_usage, opts);\n+\n+\tif (all)\n+\t\tmetapack_all(type);\n+\telse\n+\t\tfor (; *argv; argv++)\n+\t\t\tmetapack_one(*argv, type);\n+\n+\treturn 0;\n+}\ndiff --git a/git-repack.sh b/git-repack.sh\nindex 7579331..e6a9773 100755\n--- a/git-repack.sh\n+++ b/git-repack.sh\n@@ -180,7 +180,7 @@ then\n \t\t do\n \t\t\tcase \" $fullbases \" in\n \t\t\t*\" $e \"*) ;;\n-\t\t\t*)\trm -f \"$e.pack\" \"$e.idx\" \"$e.keep\" ;;\n+\t\t\t*)\trm -f \"$e.pack\" \"$e.idx\" \"$e.keep\" \"$e.commits\";;\n \t\t\tesac\n \t\t done\n \t\t)\ndiff --git a/git.c b/git.c\nindex b10c18b..f6e5552 100644\n--- a/git.c\n+++ b/git.c\n@@ -365,6 +365,7 @@ static void handle_internal_command(int argc, const char **argv)\n \t\t{ \"merge-recursive-theirs\", cmd_merge_recursive, RUN_SETUP | NEED_WORK_TREE },\n \t\t{ \"merge-subtree\", cmd_merge_recursive, RUN_SETUP | NEED_WORK_TREE },\n \t\t{ \"merge-tree\", cmd_merge_tree, RUN_SETUP },\n+\t\t{ \"metapack\", cmd_metapack, RUN_SETUP },\n \t\t{ \"mktag\", cmd_mktag, RUN_SETUP },\n \t\t{ \"mktree\", cmd_mktree, RUN_SETUP },\n \t\t{ \"mv\", cmd_mv, RUN_SETUP | NEED_WORK_TREE },\n-- \n1.8.0.2.16.g72e2fc9\n"},{"id":"208171","messageId":"20130129091637.GF9999@sigill.intra.peff.net","threadId":"32765","inReplyTo":"20130129091434.GA6975@sigill.intra.peff.net","subject":"[PATCH 6/6] commit: look up commit info in metapack","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-01-29T09:16:37Z","receivedAt":"2013-01-29T09:16:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Now that we have the plumbing in place to generate and read\ncommit metapacks, we can hook them up to parse_commit to\nfill in the traversal information much more quickly.\n\nWe only do so if save_commit_buffer is turned off;\notherwise, the callers will expect to be able to read\ncommit->buffer after parse_commit returns (and since our\ncache obviously does not have that information, we must\nleave it NULL). As callers learn to handle a NULL\ncommit->buffer, we can eventually relax this (while it might\nseem like a useless no-op to use the cache if we are going\nto load the commit anyway, many callers may first filter\nbased on the traversal, and end up loading the commit\nmessage for only a subset of the commits).\n\nWith this patch (and having run \"git metapack --all\n--commits\"), my best-of-five warm-cache \"git rev-list\n--count --all\" traversal of linux-2.6.git drops from 4.219s\nto 0.659s.\n\nSimilarly, cold-cache drops from 13.696s to 4.763s due to\nthe compactness of the cache data (but you are penalized, of\ncourse, if you then want to actually look at the commit\nmessages, since you have not warmed them into the cache).\n\nSigned-off-by: Jeff King \n---\n commit.c | 23 +++++++++++++++++++++++\n 1 file changed, 23 insertions(+)\n\ndiff --git a/commit.c b/commit.c\nindex e8eb0ae..b326201 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -8,6 +8,7 @@\n #include \"notes.h\"\n #include \"gpg-interface.h\"\n #include \"mergesort.h\"\n+#include \"commit-metapack.h\"\n \n static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);\n \n@@ -306,6 +307,24 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n \treturn 0;\n }\n \n+static int parse_commit_metapack(struct commit *item)\n+{\n+\tunsigned char *tree, *p1, *p2;\n+\tuint32_t ts;\n+\n+\tif (commit_metapack(item->object.sha1, &ts, &tree, &p1, &p2) < 0)\n+\t\treturn -1;\n+\n+\titem->date = ts;\n+\titem->tree = lookup_tree(tree);\n+\tcommit_list_insert(lookup_commit(p1), &item->parents);\n+\tif (!is_null_sha1(p2))\n+\t\tcommit_list_insert(lookup_commit(p2), &item->parents->next);\n+\n+\titem->object.parsed = 1;\n+\treturn 0;\n+}\n+\n int parse_commit(struct commit *item)\n {\n \tenum object_type type;\n@@ -317,6 +336,10 @@ int parse_commit(struct commit *item)\n \t\treturn -1;\n \tif (item->object.parsed)\n \t\treturn 0;\n+\n+\tif (!save_commit_buffer && !parse_commit_metapack(item))\n+\t\treturn 0;\n+\n \tbuffer = read_sha1_file(item->object.sha1, &type, &size);\n \tif (!buffer)\n \t\treturn error(\"Could not read %s\",\n-- \n1.8.0.2.16.g72e2fc9\n"},{"id":"208172","messageId":"5107A146.4000309@alum.mit.edu","threadId":"32765","inReplyTo":"20130129091540.GB9999@sigill.intra.peff.net","subject":"Re: [PATCH 2/6] strbuf: add string-chomping functions","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-01-29T10:15:34Z","receivedAt":"2013-01-29T10:15:34Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 01/29/2013 10:15 AM, Jeff King wrote:\n> Sometimes it is handy to cut a trailing string off the end\n> of a strbuf (e.g., a file extension). These helper functions\n> make it a one-liner.\n> \n> Signed-off-by: Jeff King \n> ---\n> strbuf.c | 11 +++++++++++\n> strbuf.h | 2 ++\n> 2 files changed, 13 insertions(+)\n> \n> diff --git a/strbuf.c b/strbuf.c\n> index 9a373be..8199ced 100644\n> --- a/strbuf.c\n> +++ b/strbuf.c\n> @@ -106,6 +106,17 @@ void strbuf_ltrim(struct strbuf *sb)\n> \tsb->buf[sb->len] = '\\0';\n> }\n> \n> +void strbuf_chompmem(struct strbuf *sb, const void *data, size_t len)\n> +{\n> +\tif (sb->len >= len && !memcmp(data, sb->buf + sb->len - len, len))\n> +\t\tstrbuf_setlen(sb, sb->len - len);\n> +}\n> +\n> +void strbuf_chompstr(struct strbuf *sb, const char *str)\n> +{\n> +\tstrbuf_chompmem(sb, str, strlen(str));\n> +}\n> +\n> struct strbuf **strbuf_split_buf(const char *str, size_t slen,\n> \t\t\t\t int terminator, int max)\n> {\n> diff --git a/strbuf.h b/strbuf.h\n> index ecae4e2..3aeb815 100644\n> --- a/strbuf.h\n> +++ b/strbuf.h\n> @@ -42,6 +42,8 @@ extern void strbuf_ltrim(struct strbuf *);\n> extern void strbuf_trim(struct strbuf *);\n> extern void strbuf_rtrim(struct strbuf *);\n> extern void strbuf_ltrim(struct strbuf *);\n> +extern void strbuf_chompmem(struct strbuf *, const void *, size_t);\n> +extern void strbuf_chompstr(struct strbuf *, const char *);\n> extern int strbuf_cmp(const struct strbuf *, const struct strbuf *);\n> \n> /*\n> \n\nIt might be handy to have these functions return true/false based on\nwhether the suffix was actually found.\n\nPlease document the new functions in\nDocumentation/technical/api-strbuf.txt. Personally I would also\nadvocate a \"docstring\" in the header file, but obviously that preference\nis the exception rather than the rule in the git project :-(\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"208173","messageId":"5107A36D.2050307@alum.mit.edu","threadId":"32765","inReplyTo":"20130129091610.GD9999@sigill.intra.peff.net","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-01-29T10:24:45Z","receivedAt":"2013-01-29T10:24:45Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 01/29/2013 10:16 AM, Jeff King wrote:\n> When we are doing a commit traversal that does not need to\n> look at the commit messages themselves (e.g., rev-list,\n> merge-base, etc), we spend a lot of time accessing,\n> decompressing, and parsing the commit objects just to find\n> the parent and timestamp information. We can make a\n> space-time tradeoff by caching that information on disk in a\n> compact, uncompressed format.\n> \n> TODO: document on-disk format in Documentation/technical\n> TODO: document API\n\nWould this be a good place to add the commit generation number that is\nso enthusiastically discussed on the mailing list from time to time?\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"208177","messageId":"20130129111028.GA11055@sigill.intra.peff.net","threadId":"32765","inReplyTo":"5107A146.4000309@alum.mit.edu","subject":"Re: [PATCH 2/6] strbuf: add string-chomping functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-01-29T11:10:29Z","receivedAt":"2013-01-29T11:10:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 29, 2013 at 11:15:34AM +0100, Michael Haggerty wrote:\n\n> > +void strbuf_chompmem(struct strbuf *sb, const void *data, size_t len)\n> > +{\n> > +\tif (sb->len >= len && !memcmp(data, sb->buf + sb->len - len, len))\n> > +\t\tstrbuf_setlen(sb, sb->len - len);\n> > +}\n> > +\n> > +void strbuf_chompstr(struct strbuf *sb, const char *str)\n> > +{\n> > +\tstrbuf_chompmem(sb, str, strlen(str));\n> > +}\n> > +\n> It might be handy to have these functions return true/false based on\n> whether the suffix was actually found.\n\nYeah, that sounds reasonable.\n\n> Please document the new functions in\n> Documentation/technical/api-strbuf.txt. Personally I would also\n> advocate a \"docstring\" in the header file, but obviously that preference\n> is the exception rather than the rule in the git project :-(\n\nWill do. I need to document the metapack functions, too, so I was thinking\nabout experimenting with some inline documentation systems.\n\n-Peff\n"},{"id":"208178","messageId":"20130129111322.GB11055@sigill.intra.peff.net","threadId":"32765","inReplyTo":"5107A36D.2050307@alum.mit.edu","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-01-29T11:13:22Z","receivedAt":"2013-01-29T11:13:22Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 29, 2013 at 11:24:45AM +0100, Michael Haggerty wrote:\n\n> On 01/29/2013 10:16 AM, Jeff King wrote:\n> > When we are doing a commit traversal that does not need to\n> > look at the commit messages themselves (e.g., rev-list,\n> > merge-base, etc), we spend a lot of time accessing,\n> > decompressing, and parsing the commit objects just to find\n> > the parent and timestamp information. We can make a\n> > space-time tradeoff by caching that information on disk in a\n> > compact, uncompressed format.\n> > \n> > TODO: document on-disk format in Documentation/technical\n> > TODO: document API\n> \n> Would this be a good place to add the commit generation number that is\n> so enthusiastically discussed on the mailing list from time to time?\n\nYes, that is one of my goals. We may even be able to just replace the\ntimestamp field in the cache with a generation number. When it gets\npretty-printed we pull it out of the commit message again anyway, so in\ntheory the only use inside \"struct commit\" is for ordering. But I\nhaven't looked at all of the use sites yet to be sure nobody is\ndepending on it being an actual date stamp.\n\n-Peff\n"},{"id":"208198","messageId":"7v622friy7.fsf@alter.siamese.dyndns.org","threadId":"32765","inReplyTo":"20130129091555.GC9999@sigill.intra.peff.net","subject":"Re: [PATCH 3/6] introduce pack metadata cache files","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-01-29T17:35:12Z","receivedAt":"2013-01-29T17:35:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> +static void write_meta_header(struct metapack_writer *mw, const char *id,\n> +\t\t\t uint32_t version)\n> +{\n> +\tversion = htonl(version);\n> +\n> +\tsha1write(mw->out, \"META\", 4);\n> +\tsha1write(mw->out, \"\\0\\0\\0\\1\", 4);\n> +\tsha1write(mw->out, mw->pack->sha1, 20);\n> +\tsha1write(mw->out, id, 4);\n> +\tsha1write(mw->out, &version, 4);\n> +}\n\nIt seems that you are very close to actually having a plumbing that\ncould also do the pack .idx files. Until/unless that can be done, I\nam not sure how much benefit we would be getting from a file format\nthat records a subtype \"id\" and a generic \"META\" type, instead of\njust a single \"id\" as the type ehader. But it is OK to use 8 extra\nbytes if we can potentially gain something later.\n\nShouldn't id be validated with at least something like\n\n\tif (strlen(id) < 3)\n\t\tdie(\"Bad id: %s\", id);\n\nto catch a call\n\n\twrite_meta_header(&mw, \"me\", 47);\n\nthat will stuff 'm', 'e', NUL and the garbage the compiler/linker\ncombo has placed after that constant string in the 4-byte id field?\n\n> +void metapack_writer_init(struct metapack_writer *mw,\n> +\t\t\t const char *pack_idx,\n> +\t\t\t const char *name,\n> +\t\t\t int version)\n> +{\n> +\tstruct strbuf path = STRBUF_INIT;\n> +\n> +\tmemset(mw, 0, sizeof(*mw));\n> +\n> +\tmw->pack = add_packed_git(pack_idx, strlen(pack_idx), 1);\n> +\tif (!mw->pack || open_pack_index(mw->pack))\n> +\t\tdie(\"unable to open packfile '%s'\", pack_idx);\n> +\n> +\tstrbuf_addstr(&path, pack_idx);\n> +\tstrbuf_chompstr(&path, \".idx\");\n> +\tstrbuf_addch(&path, '.');\n> +\tstrbuf_addstr(&path, name);\n\nYour chompstr() does not even validate if the given name ends with\n\".idx\", so this sounds like a glorified way to say\n\n\tstrbuf_splice(&path, path->len - strlen(\"idx\"), strlen(\"idx\"),\n\t\t\t name, strlen(name));\n\nto me.\n\n> +\tmw->path = strbuf_detach(&path, NULL);\n> +\n> +\tmw->out = create_meta_tmp();\n> +\twrite_meta_header(mw, name, version);\n> +}\n> +\n> +void metapack_writer_finish(struct metapack_writer *mw)\n> +{\n> +\tconst char *tmp = mw->out->name;\n> +\n> +\tsha1close(mw->out, NULL, CSUM_FSYNC);\n> +\tif (rename(tmp, mw->path))\n> +\t\tdie_errno(\"unable to rename temporary metapack file\");\n\nWho is responsible for running adjust_shared_perm()? The caller, or\nthis function?\n"},{"id":"208199","messageId":"7vy5fbq48t.fsf@alter.siamese.dyndns.org","threadId":"32765","inReplyTo":"20130129091610.GD9999@sigill.intra.peff.net","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-01-29T17:38:10Z","receivedAt":"2013-01-29T17:38:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> +int commit_metapack(unsigned char *sha1,\n> +\t\t uint32_t *timestamp,\n> +\t\t unsigned char **tree,\n> +\t\t unsigned char **parent1,\n> +\t\t unsigned char **parent2)\n> +{\n> +\tstruct commit_metapack *p;\n> +\n> +\tprepare_commit_metapacks();\n> +\tfor (p = commit_metapacks; p; p = p->next) {\n> +\t\tunsigned char *data;\n> +\t\tint pos = sha1_entry_pos(p->index, 20, 0, 0, p->nr, p->nr, sha1);\n\nThis is a tangent, but isn't it about time to rip out the check for\nGIT_USE_LOOKUP in find_pack_entry_one(), I wonder.\n\n> +\tprepare_commit_metapacks();\n> +\tfor (p = commit_metapacks; p; p = p->next) {\n> +\t\tunsigned char *data;\n> +\t\tint pos = sha1_entry_pos(p->index, 20, 0, 0, p->nr, p->nr, sha1);\n> +\t\tif (pos < 0)\n> +\t\t\tcontinue;\n> +\n> +\t\t/* timestamp(4) + tree(20) + parents(40) */\n> +\t\tdata = p->data + 64 * pos;\n> +\t\t*timestamp = *(uint32_t *)data;\n> +\t\t*timestamp = ntohl(*timestamp);\n> +\t\tdata += 4;\n> +\t\t*tree = data;\n> +\t\tdata += 20;\n> +\t\t*parent1 = data;\n> +\t\tdata += 20;\n> +\t\t*parent2 = data;\n> +\n> +\t\treturn 0;\n> +\t}\n> +\n> +\treturn -1;\n> +}\n\nI am torn on this one.\n\nThese cached properties of a single commit will not change no matter\nwhich pack it appears in, and it feels logically wrong, especially\nwhen you record these object names in the full SHA-1 form, to tie a\n\"commit metapack\" to a pack. Logically there needs only one commit\nmetapack that describes all the commits known to the repository when\nthe metapack was created.\n\nIn order to reduce the disk footprint and I/O cost, the future\ndirection for this mechanism may want to point into an existing\nstore of SHA-1 hashes with a shorter file offset, and the .idx file\ncould be such a store, and in order to move in that direction, you\ncannot avoid tying a metapack to a pack.\n\n> +static void get_commits(struct metapack_writer *mw,\n> +\t\t\tconst unsigned char *sha1,\n> +\t\t\tvoid *data)\n> +{\n> +\tstruct commit_list ***tail = data;\n> +\tenum object_type type = sha1_object_info(sha1, NULL);\n> +\tstruct commit *c;\n> +\n> +\tif (type != OBJ_COMMIT)\n> +\t\treturn;\n> +\n> +\tc = lookup_commit(sha1);\n> +\tif (!c || parse_commit(c))\n> +\t\tdie(\"unable to read commit %s\", sha1_to_hex(sha1));\n> +\n> +\t/*\n> +\t * Our fixed-size parent list cannot represent root commits, nor\n> +\t * octopus merges. Just skip those commits, as we can fallback\n> +\t * in those rare cases to reading the actual commit object.\n> +\t */\n> +\tif (!c->parents ||\n> +\t (c->parents && c->parents->next && c->parents->next->next))\n> +\t\treturn;\n> +\n> +\t*tail = &commit_list_insert(c, *tail)->next;\n> +}\n\nIt feels somewhat wasteful to:\n\n - use commit_list for this, rather than an array of commit\n objects. If you have a rough estimate of the number of commits\n in the pack, you could just preallocate a single array and use\n ALLOC_GROW() on it, no?\n\n - iterate over the .idx file and run sha1_object_info() and\n parse_commit() on many objects in the SHA-1 order. Iterating in\n the way builtin/pack-objects.c::get_object_details() does avoids\n jumping around in existing packfiles, which may be more\n efficient, no?\n\n> +void commit_metapack_write(const char *idx)\n> +{\n> +\tstruct metapack_writer mw;\n> +\tstruct commit_list *commits = NULL, *p;\n> +\tstruct commit_list **tail = &commits;\n> +\tuint32_t nr = 0;\n> +\n> +\tmetapack_writer_init(&mw, idx, \"commits\", 1);\n> +\n> +\t/* Figure out how many eligible commits we've got in this pack. */\n> +\tmetapack_writer_foreach(&mw, get_commits, &tail);\n> +\tfor (p = commits; p; p = p->next)\n> +\t\tnr++;\n"},{"id":"208201","messageId":"7vtxpzq2uv.fsf@alter.siamese.dyndns.org","threadId":"32765","inReplyTo":"7vy5fbq48t.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-01-29T18:08:08Z","receivedAt":"2013-01-29T18:08:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> I am torn on this one.\n>\n> These cached properties of a single commit will not change no matter\n> which pack it appears in, and it feels logically wrong, especially\n> when you record these object names in the full SHA-1 form, to tie a\n> \"commit metapack\" to a pack. Logically there needs only one commit\n> metapack that describes all the commits known to the repository when\n> the metapack was created.\n>\n> In order to reduce the disk footprint and I/O cost, the future\n> direction for this mechanism may want to point into an existing\n> store of SHA-1 hashes with a shorter file offset, and the .idx file\n> could be such a store, and in order to move in that direction, you\n> cannot avoid tying a metapack to a pack.\n\nHave you considered if we can extend the .idx format version 2\nwithout actually having to bump the version number? My quick\nreading of check_packed_git_idx() tells me that we have a gap after\nthe \"large offset table\" that we can place extensions, but I may be\nmistaken. If we indeed can, then perhaps adding a series of\n\n\t4-byte \"id\" header\n 4-byte extension length (or 8-byte)\n ... N-byte worth of extension data ...\n\nfollowed by\n\n\t20-byte SHA-1 checksum of all the extension sections\n\t8-byte file offset to the first extension section\n\nat that gap, immediately before the trailer of the .idx file written\nby git_SHA1_Final(), in a way similar to the index extension is done\nmay give us a natural way to deal with this. The reader can first\nread the offset recorded at the tail, checking if the offset is\nplausible because it may not exist, the check the extension section\nchecksum, to see if the file has extension, or the file just ends\nwith the large offset table and the 28 bytes it tried to were from\nthe entries near the end of the large offset table.\n\nIf that is not worth attempting, perhaps we may still want to store\nthis as an optional extended section and bump the .idx format\nversion.\n\nThen it will be very natural for the extension data that store the\ncommit metainfo to name objects in the pack the .idx file describes\nby the offset in the SHA-1 table.\n\nAs we always say, .idx is a local cache and bumping its version is\nnot a huge headache compared to other longer term storage items.\n"},{"id":"208235","messageId":"CACsJy8Af9g9Tdqr0dXyucq-M2aP5U2HvX3ANSsabqtuX=w4Q0w@mail.gmail.com","threadId":"32765","inReplyTo":"20130129091555.GC9999@sigill.intra.peff.net","subject":"Re: [PATCH 3/6] introduce pack metadata cache files","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-01-30T01:30:57Z","receivedAt":"2013-01-30T01:30:57Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Jan 29, 2013 at 4:15 PM, Jeff King wrote:\n> +static void write_meta_header(struct metapack_writer *mw, const char *id,\n> + uint32_t version)\n> +{\n> + version = htonl(version);\n> +\n> + sha1write(mw->out, \"META\", 4);\n> + sha1write(mw->out, \"\\0\\0\\0\\1\", 4);\n> + sha1write(mw->out, mw->pack->sha1, 20);\n> + sha1write(mw->out, id, 4);\n> + sha1write(mw->out, &version, 4);\n> +}\n\nBecause you go with all-commit-info-in-one-file, perhaps we should\nhave an uint32_t bitmap to describe what info this cache contains? So\nfar we need 4 bits for date, tree, 1st and 2nd parents (yes, I still\nwant to check if storing 1-parent commits only gains us anything on\nsome other repos). When commit count comes, it can take the fifth bit.\nReachability bitmap offsets can take the sixth bit, if we just append\nthe bitmaps at the end of the same file.\n-- \nDuy\n"},{"id":"208238","messageId":"CACsJy8BE3LdxbZzdQXuvEJop23KnnLbCTgPos9CywKV7EY2q9g@mail.gmail.com","threadId":"32765","inReplyTo":"20130129091434.GA6975@sigill.intra.peff.net","subject":"Re: [PATCH/RFC 0/6] commit caching","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-01-30T03:31:43Z","receivedAt":"2013-01-30T03:31:43Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Jan 29, 2013 at 4:14 PM, Jeff King wrote:\n> The timings from this one are roughly similar to what I posted earlier.\n> Unlike the earlier version, this one keeps the data for a single commit\n> together for better cache locality (though I don't think it made a big\n> difference in my tests, since my cold-cache timing test ends up touching\n> every commit anyway). The short of it is that for an extra 31M of disk\n> space (~4%), I get a warm-cache speedup for \"git rev-list --all\" of\n> ~4.2s to ~0.66s.\n\nSome data point on caching 1-parent vs 2-parent commits on webkit\nrepo, 26k commits. With your changes (caching 2-parent commits), the\n.commits file takes 2241600 bytes. \"rev-list --all --quiet\":\n\n0.06user 0.00system 0:00.08elapsed 95%CPU (0avgtext+0avgdata 26288maxresident)k\n0inputs+0outputs (0major+2094minor)pagefaults 0swaps\n\nWith caching 1-parent commits only, the .commits file takes 1707900\nbytes (30% less), the same rev-list command:\n\n0.07user 0.00system 0:00.07elapsed 96%CPU (0avgtext+0avgdata 24144maxresident)k\n0inputs+0outputs (0major+1960minor)pagefaults 0swaps\n\nCompared to the timing without caching at all:\n\n0.72user 0.02system 0:00.76elapsed 98%CPU (0avgtext+0avgdata 108976maxresident)k\n0inputs+0outputs (0major+7272minor)pagefaults 0swaps\n\nThe performance loss in 1-parent case is not significant while disk\nsaving is (although it'll be less impressive after you do Shawn's\nsuggestion not storing SHA-1 directly)\n-- \nDuy\n"},{"id":"208240","messageId":"CACsJy8COCpr_CvQPhBFtVnsKztA3xgo01=zKG4WPcFfCbNTmgw@mail.gmail.com","threadId":"32765","inReplyTo":"20130129091610.GD9999@sigill.intra.peff.net","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-01-30T03:36:10Z","receivedAt":"2013-01-30T03:36:10Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Jan 29, 2013 at 4:16 PM, Jeff King wrote:\n> +int commit_metapack(unsigned char *sha1,\n> + uint32_t *timestamp,\n> + unsigned char **tree,\n> + unsigned char **parent1,\n> + unsigned char **parent2)\n> +{\n\nNit picking. tree, parent1 and parent2 can/should be \"const unsigned char **\".\n-- \nDuy\n"},{"id":"208241","messageId":"5108A8E7.5080308@alum.mit.edu","threadId":"32765","inReplyTo":"20130129111028.GA11055@sigill.intra.peff.net","subject":"Re: [PATCH 2/6] strbuf: add string-chomping functions","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-01-30T05:00:23Z","receivedAt":"2013-01-30T05:00:23Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 01/29/2013 12:10 PM, Jeff King wrote:\n> On Tue, Jan 29, 2013 at 11:15:34AM +0100, Michael Haggerty wrote:\n>> Please document the new functions in\n>> Documentation/technical/api-strbuf.txt. Personally I would also\n>> advocate a \"docstring\" in the header file, but obviously that preference\n>> is the exception rather than the rule in the git project :-(\n> \n> Will do. I need to document the metapack functions, too, so I was thinking\n> about experimenting with some inline documentation systems.\n\nThat would be great; it would make future API documentation much easier\nand therefore (hopefully) more common.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"208243","messageId":"20130130064744.GA11147@sigill.intra.peff.net","threadId":"32765","inReplyTo":"7v622friy7.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/6] introduce pack metadata cache files","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-01-30T06:47:45Z","receivedAt":"2013-01-30T06:47:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 29, 2013 at 09:35:12AM -0800, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > +static void write_meta_header(struct metapack_writer *mw, const char *id,\n> > +\t\t\t uint32_t version)\n> > +{\n> > +\tversion = htonl(version);\n> > +\n> > +\tsha1write(mw->out, \"META\", 4);\n> > +\tsha1write(mw->out, \"\\0\\0\\0\\1\", 4);\n> > +\tsha1write(mw->out, mw->pack->sha1, 20);\n> > +\tsha1write(mw->out, id, 4);\n> > +\tsha1write(mw->out, &version, 4);\n> > +}\n> \n> It seems that you are very close to actually having a plumbing that\n> could also do the pack .idx files. Until/unless that can be done, I\n> am not sure how much benefit we would be getting from a file format\n> that records a subtype \"id\" and a generic \"META\" type, instead of\n> just a single \"id\" as the type ehader. But it is OK to use 8 extra\n> bytes if we can potentially gain something later.\n\nYeah, I considered going that route. I had initially envisioned having a\ngeneric META file type that provided some services (like fixed-size\nrecords), and then having individual subtypes below that. But as I\nsimplified the design, the META format became pretty much pointless. I\nleft it in as the 8 bytes are not really a big problem, and it means we\ncan treat metapacks generically in some cases without necessarily\nknowing what is in them. But I don't have a specific use case in mind,\nso perhaps it is just useless and confusing. I don't mind simplifying.\n\n> Shouldn't id be validated with at least something like\n> \n> \tif (strlen(id) < 3)\n> \t\tdie(\"Bad id: %s\", id);\n> \n> to catch a call\n> \n> \twrite_meta_header(&mw, \"me\", 47);\n> \n> that will stuff 'm', 'e', NUL and the garbage the compiler/linker\n> combo has placed after that constant string in the 4-byte id field?\n\nYes, the id does need to be at least 4 bytes. Since the id is intended\nto be a static string, I had planned to just document the requirement in\nthe API documentation. I don't mind putting in a run-time check. I had\noriginally had a separate \"id\" parameter that could be \"char id[4]\", but\nfound that it was just redundant with the \"name\" parameter: you ended up\npassing (\"commit\", \"CMIT\") or similar.\n\n> > +\tstrbuf_addstr(&path, pack_idx);\n> > +\tstrbuf_chompstr(&path, \".idx\");\n> > +\tstrbuf_addch(&path, '.');\n> > +\tstrbuf_addstr(&path, name);\n> \n> Your chompstr() does not even validate if the given name ends with\n> \".idx\",\n\nYeah, my intent was that it would be liberal in its input (i.e., take\njust \"pack-*\"). E.g., you can run \"git metapack pack/pack-XXXX\".\n\n> so this sounds like a glorified way to say\n> \n> \tstrbuf_splice(&path, path->len - strlen(\"idx\"), strlen(\"idx\"),\n> \t\t\t name, strlen(name));\n> \n> to me.\n\nYup, though my version handles edge cases by not chomping (e.g., what\ndoes splice do when path->len is less than 3?).\n\n> > +void metapack_writer_finish(struct metapack_writer *mw)\n> > +{\n> > +\tconst char *tmp = mw->out->name;\n> > +\n> > +\tsha1close(mw->out, NULL, CSUM_FSYNC);\n> > +\tif (rename(tmp, mw->path))\n> > +\t\tdie_errno(\"unable to rename temporary metapack file\");\n> \n> Who is responsible for running adjust_shared_perm()? The caller, or\n> this function?\n\nI didn't think about it at all, but it seems pretty obvious to me that\nthis function should do so. Thanks for pointing it out.\n\n-Peff\n"},{"id":"208244","messageId":"20130130065036.GB11147@sigill.intra.peff.net","threadId":"32765","inReplyTo":"CACsJy8Af9g9Tdqr0dXyucq-M2aP5U2HvX3ANSsabqtuX=w4Q0w@mail.gmail.com","subject":"Re: [PATCH 3/6] introduce pack metadata cache files","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-01-30T06:50:36Z","receivedAt":"2013-01-30T06:50:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 30, 2013 at 08:30:57AM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> On Tue, Jan 29, 2013 at 4:15 PM, Jeff King wrote:\n> > +static void write_meta_header(struct metapack_writer *mw, const char *id,\n> > + uint32_t version)\n> > +{\n> > + version = htonl(version);\n> > +\n> > + sha1write(mw->out, \"META\", 4);\n> > + sha1write(mw->out, \"\\0\\0\\0\\1\", 4);\n> > + sha1write(mw->out, mw->pack->sha1, 20);\n> > + sha1write(mw->out, id, 4);\n> > + sha1write(mw->out, &version, 4);\n> > +}\n> \n> Because you go with all-commit-info-in-one-file, perhaps we should\n> have an uint32_t bitmap to describe what info this cache contains? So\n> far we need 4 bits for date, tree, 1st and 2nd parents (yes, I still\n> want to check if storing 1-parent commits only gains us anything on\n> some other repos). When commit count comes, it can take the fifth bit.\n> Reachability bitmap offsets can take the sixth bit, if we just append\n> the bitmaps at the end of the same file.\n\nI thought about having some programmatic self-describing header like\nthat. But it makes the implementation much harder to verify, and it is\nnot like there is much point in picking and choosing those bits. My plan\nwas to do a combination of:\n\n 1. Put truly optional bits into a separate metapack (e.g.,\n reachability bitmaps).\n\n 2. When something becomes obviously obsolete (e.g., we move to\n generation numbers instead of timestamps in commits), bump the\n version number.\n\n-Peff\n"},{"id":"208246","messageId":"20130130070734.GC11147@sigill.intra.peff.net","threadId":"32765","inReplyTo":"7vy5fbq48t.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-01-30T07:07:34Z","receivedAt":"2013-01-30T07:07:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 29, 2013 at 09:38:10AM -0800, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > +int commit_metapack(unsigned char *sha1,\n> > +\t\t uint32_t *timestamp,\n> > +\t\t unsigned char **tree,\n> > +\t\t unsigned char **parent1,\n> > +\t\t unsigned char **parent2)\n> > +{\n> > +\tstruct commit_metapack *p;\n> > +\n> > +\tprepare_commit_metapacks();\n> > +\tfor (p = commit_metapacks; p; p = p->next) {\n> > +\t\tunsigned char *data;\n> > +\t\tint pos = sha1_entry_pos(p->index, 20, 0, 0, p->nr, p->nr, sha1);\n> \n> This is a tangent, but isn't it about time to rip out the check for\n> GIT_USE_LOOKUP in find_pack_entry_one(), I wonder.\n\nRip it out and always use sha1_entry_pos, or rip it out and never use\nit? I have never been able to measure any speedup from it; I just use it\nhere to avoid rewriting the binary search myself. I do not think there\nis any disadvantage to using it, so I'd be in favor of just\nstandardizing on it for any sha1 binary searches.\n\n> These cached properties of a single commit will not change no matter\n> which pack it appears in, and it feels logically wrong, especially\n> when you record these object names in the full SHA-1 form, to tie a\n> \"commit metapack\" to a pack. Logically there needs only one commit\n> metapack that describes all the commits known to the repository when\n> the metapack was created.\n\nTrue. I had originally envisioned it as tied to the packfile to help\nmanage the lifecycle. You know you need to generate a metapack for some\nobjects when they get packed, and you know you can throw it away when\nthe associated pack goes away. And it means you can verify the integrity\nof the metapack by matching it to a particular packfile.\n\nHowever, if you just have a commit cache, you can always blow the whole\nthing away and regenerate it for all objects in the repo. It does not\nhave tied to a pack (you do end up doing some extra work at regeneration\nwhen you are not doing a full repack, but it is really not enough to\nworry about).\n\n> In order to reduce the disk footprint and I/O cost, the future\n> direction for this mechanism may want to point into an existing\n> store of SHA-1 hashes with a shorter file offset, and the .idx file\n> could be such a store, and in order to move in that direction, you\n> cannot avoid tying a metapack to a pack.\n\nYes. That was not one of my original goals for the commit cache, but I\ndo think it's a useful direction to go in. And reachability bitmaps\n(which would eventually be their own metapacks) would generally want to\nbe per-pack, too, for the same reason.\n\n> > +\t*tail = &commit_list_insert(c, *tail)->next;\n> > +}\n> \n> It feels somewhat wasteful to:\n> \n> - use commit_list for this, rather than an array of commit\n> objects. If you have a rough estimate of the number of commits\n> in the pack, you could just preallocate a single array and use\n> ALLOC_GROW() on it, no?\n\nWe don't have a rough estimate, but yes, we could just use an array and\ntrust ALLOC_GROW to be reasonable. The use of commit_list did not have a\nparticular reason other than that it was simple (an array means stuffing\nthe array pointer and the nr and alloc counts into a struct to get to\nthe callback). The performance of writing the cache is dominated by\naccessing the objects themselves, anyway. I don't mind changing it,\nthough, if you think it's clearer as an array.\n\n> - iterate over the .idx file and run sha1_object_info() and\n> parse_commit() on many objects in the SHA-1 order. Iterating in\n> the way builtin/pack-objects.c::get_object_details() does avoids\n> jumping around in existing packfiles, which may be more\n> efficient, no?\n\nProbably, though generating the complete commit cache for linux-2.6.git\ntakes only about 7 seconds on my machine. I wasn't too concerned with\noptimizing generation, since it will typically be dwarfed by repacking\ncosts. It might make more of a difference for doing a metapack on all\nobjects (e.g., reachability bitmaps).\n\nThe reason I do it in .idx order is that it feeds the callback in sorted\norder, so a writer could in theory just use that output as-is (and my\ninitial version did that, as it wrote separate metapacks for each\nelement). This version now puts all data elements together (for cache\nlocality), and builds the in-memory list so we do not have to re-do\nsha1_object_info repeatedly. So it could very easily just generate the\nlist in pack order and sort it at the end.\n\nI'll look into that for the next version.\n\n-Peff\n"},{"id":"208247","messageId":"20130130071209.GD11147@sigill.intra.peff.net","threadId":"32765","inReplyTo":"7vtxpzq2uv.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-01-30T07:12:09Z","receivedAt":"2013-01-30T07:12:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 29, 2013 at 10:08:08AM -0800, Junio C Hamano wrote:\n\n> > In order to reduce the disk footprint and I/O cost, the future\n> > direction for this mechanism may want to point into an existing\n> > store of SHA-1 hashes with a shorter file offset, and the .idx file\n> > could be such a store, and in order to move in that direction, you\n> > cannot avoid tying a metapack to a pack.\n> \n> Have you considered if we can extend the .idx format version 2\n> without actually having to bump the version number? My quick\n> reading of check_packed_git_idx() tells me that we have a gap after\n> the \"large offset table\" that we can place extensions, but I may be\n> mistaken. If we indeed can, then perhaps adding a series of\n> \n> \t4-byte \"id\" header\n> 4-byte extension length (or 8-byte)\n> ... N-byte worth of extension data ...\n> \n> followed by\n> \n> \t20-byte SHA-1 checksum of all the extension sections\n> \t8-byte file offset to the first extension section\n\nI considered it, but didn't look into it closely. My feeling was that it\nadded extra complexity, without adding any real advantage that a\nseparate file would not.\n\n>From this:\n\n> Then it will be very natural for the extension data that store the\n> commit metainfo to name objects in the pack the .idx file describes\n> by the offset in the SHA-1 table.\n\nI guess your argument is that putting it all in the same file makes it\nmore natural for there to be a data dependency.\n\n> As we always say, .idx is a local cache and bumping its version is\n> not a huge headache compared to other longer term storage items.\n\nTrue, but it is even less headache if the file is totally separate and\noptional.\n\n-Peff\n"},{"id":"293751","messageId":"20130130071248.GE11147@sigill.intra.peff.net","threadId":"32765","inReplyTo":"CACsJy8COCpr_CvQPhBFtVnsKztA3xgo01=zKG4WPcFfCbNTmgw@mail.gmail.com","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-01-30T07:12:48Z","receivedAt":"2013-01-30T07:12:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 30, 2013 at 10:36:10AM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> On Tue, Jan 29, 2013 at 4:16 PM, Jeff King wrote:\n> > +int commit_metapack(unsigned char *sha1,\n> > + uint32_t *timestamp,\n> > + unsigned char **tree,\n> > + unsigned char **parent1,\n> > + unsigned char **parent2)\n> > +{\n> \n> Nit picking. tree, parent1 and parent2 can/should be \"const unsigned char **\".\n\nThanks, I'll fix it in the next version.\n\n"},{"id":"208248","messageId":"7vk3qvm962.fsf@alter.siamese.dyndns.org","threadId":"32765","inReplyTo":"20130130071209.GD11147@sigill.intra.peff.net","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-01-30T07:17:41Z","receivedAt":"2013-01-30T07:17:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"> True, but it is even less headache if the file is totally separate and\n> optional.\n\nOnce you start thinking about using an offset to some list of SHA-1,\nperhaps? A section inside the same file can never go out of sync.\nAlso a longer-term advantage is that you can teach index-pack to do\nthis.\n"},{"id":"208249","messageId":"20130130071839.GF11147@sigill.intra.peff.net","threadId":"32765","inReplyTo":"CACsJy8BE3LdxbZzdQXuvEJop23KnnLbCTgPos9CywKV7EY2q9g@mail.gmail.com","subject":"Re: [PATCH/RFC 0/6] commit caching","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-01-30T07:18:39Z","receivedAt":"2013-01-30T07:18:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 30, 2013 at 10:31:43AM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> On Tue, Jan 29, 2013 at 4:14 PM, Jeff King wrote:\n> > The timings from this one are roughly similar to what I posted earlier.\n> > Unlike the earlier version, this one keeps the data for a single commit\n> > together for better cache locality (though I don't think it made a big\n> > difference in my tests, since my cold-cache timing test ends up touching\n> > every commit anyway). The short of it is that for an extra 31M of disk\n> > space (~4%), I get a warm-cache speedup for \"git rev-list --all\" of\n> > ~4.2s to ~0.66s.\n> \n> Some data point on caching 1-parent vs 2-parent commits on webkit\n> repo, 26k commits. With your changes (caching 2-parent commits), the\n> .commits file takes 2241600 bytes. \"rev-list --all --quiet\":\n\nHmm. My webkit repo has zero merges in it (though it is the older\nsvn-based one). What percentage of the one you have are merges? How does\nyour 1-parent cache perform on something like git.git, where about 25%\nof all commits are merges?\n\n> The performance loss in 1-parent case is not significant while disk\n> saving is (although it'll be less impressive after you do Shawn's\n> suggestion not storing SHA-1 directly)\n\nYeah, I think moving to offsets instead of sha1s is going to be a big\nenough win that it won't matter anymore.\n\n-Peff\n"},{"id":"208253","messageId":"CACsJy8BEyha1QdQmRH9o-h_3JLPmMemoc4ucSaQ_nrOMzQ64AQ@mail.gmail.com","threadId":"32765","inReplyTo":"20130130071839.GF11147@sigill.intra.peff.net","subject":"Re: [PATCH/RFC 0/6] commit caching","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-01-30T08:32:44Z","receivedAt":"2013-01-30T08:32:44Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Jan 30, 2013 at 2:18 PM, Jeff King wrote:\n> On Wed, Jan 30, 2013 at 10:31:43AM +0700, Nguyen Thai Ngoc Duy wrote:\n>\n>> On Tue, Jan 29, 2013 at 4:14 PM, Jeff King wrote:\n>> > The timings from this one are roughly similar to what I posted earlier.\n>> > Unlike the earlier version, this one keeps the data for a single commit\n>> > together for better cache locality (though I don't think it made a big\n>> > difference in my tests, since my cold-cache timing test ends up touching\n>> > every commit anyway). The short of it is that for an extra 31M of disk\n>> > space (~4%), I get a warm-cache speedup for \"git rev-list --all\" of\n>> > ~4.2s to ~0.66s.\n>>\n>> Some data point on caching 1-parent vs 2-parent commits on webkit\n>> repo, 26k commits. With your changes (caching 2-parent commits), the\n>> .commits file takes 2241600 bytes. \"rev-list --all --quiet\":\n>\n> Hmm. My webkit repo has zero merges in it (though it is the older\n> svn-based one). What percentage of the one you have are merges? How does\n> your 1-parent cache perform on something like git.git, where about 25%\n> of all commits are merges?\n\ngit.git performs worse with 1-parent cache. But the point is it should\nbe customizable.\n\n>> The performance loss in 1-parent case is not significant while disk\n>> saving is (although it'll be less impressive after you do Shawn's\n>> suggestion not storing SHA-1 directly)\n>\n> Yeah, I think moving to offsets instead of sha1s is going to be a big\n> enough win that it won't matter anymore.\n\nYeah, if we use uint32_t instead of sha-1, the cache is just about\n400k 2 parents for webkit, 312k for 1 parent. The total size is so\nsmall that reduction does not really matter anymore.\n-- \nDuy\n"},{"id":"208263","messageId":"20130130135607.GA23154@lanh","threadId":"32765","inReplyTo":"20130129091610.GD9999@sigill.intra.peff.net","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-01-30T13:56:07Z","receivedAt":"2013-01-30T13:56:07Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Jan 29, 2013 at 04:16:11AM -0500, Jeff King wrote:\n> When we are doing a commit traversal that does not need to\n> look at the commit messages themselves (e.g., rev-list,\n> merge-base, etc), we spend a lot of time accessing,\n> decompressing, and parsing the commit objects just to find\n> the parent and timestamp information. We can make a\n> space-time tradeoff by caching that information on disk in a\n> compact, uncompressed format.\n\nAnd this is a (messy) patch on top that avoids storing SHA-1\ndirectly. On my linux-2.6.git (575 MB pack, 73 MB index), .commits\nfile is 5.2 MB and 27 MB with and without my patch respectively. Nice\nshrinkage.\n\nHowever, performance seems to suffer too. Maybe I do more lookups than\nnecessary, I don't know. I should probably measure the cost of\nrevindex separately.\n\ngit rev-list --all --quiet on vanilla git:\n\nreal 0m3.645s\nuser 0m3.556s\nsys 0m0.080s\n\ncommit cache without my patch:\n\nreal 0m0.723s\nuser 0m0.677s\nsys 0m0.045s\n\nand with my patch:\n\nreal 0m1.338s\nuser 0m1.259s\nsys 0m0.075s\n\n\nAnother point, but not really important at this stage, I think we have\nmemory leak somewhere (lookup_commit??). It used up to 800 MB RES on\nlinux-2.6.git while generating the cache.\n\n-- 8< --\ndiff --git a/cache.h b/cache.h\nindex 1f96f65..8048d5b 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1069,6 +1069,7 @@ extern struct packed_git *add_packed_git(const char *, int, int);\n extern const unsigned char *nth_packed_object_sha1(struct packed_git *, uint32_t);\n extern off_t nth_packed_object_offset(const struct packed_git *, uint32_t);\n extern off_t find_pack_entry_one(const unsigned char *, struct packed_git *);\n+extern int find_pack_entry_pos(const unsigned char *, struct packed_git *);\n extern int is_pack_valid(struct packed_git *);\n extern void *unpack_entry(struct packed_git *, off_t, enum object_type *, unsigned long *);\n extern unsigned long unpack_object_header_buffer(const unsigned char *buf, unsigned long len, enum object_type *type, unsigned long *sizep);\ndiff --git a/commit-metapack.c b/commit-metapack.c\nindex 2c19f48..55f7ea9 100644\n--- a/commit-metapack.c\n+++ b/commit-metapack.c\n@@ -3,11 +3,12 @@\n #include \"metapack.h\"\n #include \"commit.h\"\n #include \"sha1-lookup.h\"\n+#include \"pack-revindex.h\"\n \n struct commit_metapack {\n \tstruct metapack mp;\n-\tuint32_t nr;\n-\tunsigned char *index;\n+\tstruct packed_git *pack;\n+\tuint32_t first, last;\n \tunsigned char *data;\n \tstruct commit_metapack *next;\n };\n@@ -16,7 +17,7 @@ static struct commit_metapack *commit_metapacks;\n static struct commit_metapack *alloc_commit_metapack(struct packed_git *pack)\n {\n \tstruct commit_metapack *it = xcalloc(1, sizeof(*it));\n-\tuint32_t version;\n+\tuint32_t version, nr;\n \n \tif (metapack_init(&it->mp, pack, \"commits\", &version) < 0) {\n \t\tfree(it);\n@@ -39,22 +40,25 @@ static struct commit_metapack *alloc_commit_metapack(struct packed_git *pack)\n \t\tfree(it);\n \t\treturn NULL;\n \t}\n-\tmemcpy(&it->nr, it->mp.data, 4);\n-\tit->nr = ntohl(it->nr);\n+\tmemcpy(&it->first, it->mp.data, 4);\n+\tit->first = ntohl(it->first);\n+\tmemcpy(&it->last, it->mp.data + 4, 4);\n+\tit->last = ntohl(it->last);\n+\tnr = it->last - it->first + 1;\n+\tit->pack = pack;\n \n \t/*\n-\t * We need 84 bytes for each entry: sha1(20), date(4), tree(20),\n-\t * parents(40).\n+\t * We need 16 bytes for each entry: date(4), tree index(4),\n+\t * parent indexes(8).\n \t */\n-\tif (it->mp.len < (84 * it->nr + 4)) {\n+\tif (it->mp.len < (16 * nr + 8)) {\n \t\twarning(\"commit metapack for '%s' is truncated\", pack->pack_name);\n \t\tmetapack_close(&it->mp);\n \t\tfree(it);\n \t\treturn NULL;\n \t}\n \n-\tit->index = it->mp.data + 4;\n-\tit->data = it->index + 20 * it->nr;\n+\tit->data = it->mp.data + 8;\n \n \treturn it;\n }\n@@ -81,31 +85,61 @@ static void prepare_commit_metapacks(void)\n \tinitialized = 1;\n }\n \n+static const unsigned char *idx_to_sha1(struct packed_git *p,\n+\t\t\t\t\tuint32_t nth)\n+{\n+\tstruct revindex_entry *revindex = get_revindex(p);\n+\tif (!revindex)\n+\t\treturn NULL;\n+\treturn nth_packed_object_sha1(p, revindex[nth].nr);\n+}\n+\n int commit_metapack(unsigned char *sha1,\n \t\t uint32_t *timestamp,\n-\t\t unsigned char **tree,\n-\t\t unsigned char **parent1,\n-\t\t unsigned char **parent2)\n+\t\t const unsigned char **tree,\n+\t\t const unsigned char **parent1,\n+\t\t const unsigned char **parent2)\n {\n \tstruct commit_metapack *p;\n \n \tprepare_commit_metapacks();\n \tfor (p = commit_metapacks; p; p = p->next) {\n \t\tunsigned char *data;\n-\t\tint pos = sha1_entry_pos(p->index, 20, 0, 0, p->nr, p->nr, sha1);\n-\t\tif (pos < 0)\n+\t\tuint32_t p1, p2;\n+\t\tstruct revindex_entry *re, *base;\n+\t\toff_t off;\n+\t\tuint32_t pos;\n+\n+\t\tbase = get_revindex(p->pack);\n+\t\toff = find_pack_entry_one(sha1, p->pack);\n+\t\tif (!off)\n+\t\t\tcontinue;\n+\t\tre = find_pack_revindex(p->pack, off);\n+\t\tif (!re)\n+\t\t\tcontinue;\n+\t\tpos = re - base;\n+\t\tif (pos < p->first || pos > p->last)\n \t\t\tcontinue;\n \n \t\t/* timestamp(4) + tree(20) + parents(40) */\n-\t\tdata = p->data + 64 * pos;\n+\t\tdata = p->data + 16 * (pos - p->first);\n \t\t*timestamp = *(uint32_t *)data;\n \t\t*timestamp = ntohl(*timestamp);\n+\t\tif (!*timestamp)\n+\t\t\treturn -1;\n \t\tdata += 4;\n-\t\t*tree = data;\n-\t\tdata += 20;\n-\t\t*parent1 = data;\n-\t\tdata += 20;\n-\t\t*parent2 = data;\n+\t\t*tree = idx_to_sha1(p->pack, ntohl(*(uint32_t*)data));\n+\t\tdata += 4;\n+\t\tp1 = ntohl(*(uint32_t*)data);\n+\t\t*parent1 = idx_to_sha1(p->pack, p1);\n+\t\tdata += 4;\n+\t\tp2 = ntohl(*(uint32_t*)data);\n+\t\tif (p1 == p2)\n+\t\t\t*parent2 = null_sha1;\n+\t\telse\n+\t\t\t*parent2 = idx_to_sha1(p->pack, p2);\n+\t\tif (!*tree || !*parent1 || !*parent2)\n+\t\t\treturn -1;\n \n \t\treturn 0;\n \t}\n@@ -113,63 +147,114 @@ int commit_metapack(unsigned char *sha1,\n \treturn -1;\n }\n \n-static void get_commits(struct metapack_writer *mw,\n-\t\t\tconst unsigned char *sha1,\n-\t\t\tvoid *data)\n+static int get_commits(struct metapack_writer *mw,\n+\t\t uint32_t nth,\n+\t\t int dry_run)\n {\n-\tstruct commit_list ***tail = data;\n+\tconst unsigned char *sha1 = nth_packed_object_sha1(mw->pack, nth);\n \tenum object_type type = sha1_object_info(sha1, NULL);\n \tstruct commit *c;\n+\tstruct revindex_entry *revindex, *ridx;\n+\tint pt, p1, p2 = -1;\n \n-\tif (type != OBJ_COMMIT)\n-\t\treturn;\n+\tif (type != OBJ_COMMIT) {\n+\t\tif (dry_run)\n+\t\t\treturn -1;\n+\t\tmetapack_writer_add_uint32(mw, 0); /* date */\n+\t\tmetapack_writer_add_uint32(mw, 0); /* tree */\n+\t\tmetapack_writer_add_uint32(mw, 0); /* 1st parent */\n+\t\tmetapack_writer_add_uint32(mw, 0); /* 2nd tree */\n+\t\treturn 0;\n+\t}\n \n \tc = lookup_commit(sha1);\n \tif (!c || parse_commit(c))\n \t\tdie(\"unable to read commit %s\", sha1_to_hex(sha1));\n \n+\tif (c->buffer) {\n+\t\tfree(c->buffer);\n+\t\tc->buffer = NULL;\n+\t}\n+\n \t/*\n \t * Our fixed-size parent list cannot represent root commits, nor\n \t * octopus merges. Just skip those commits, as we can fallback\n \t * in those rare cases to reading the actual commit object.\n \t */\n \tif (!c->parents ||\n-\t (c->parents && c->parents->next && c->parents->next->next))\n-\t\treturn;\n+\t (c->parents && c->parents->next && c->parents->next->next) ||\n+\t /* edge commits are out too */\n+\t (pt = find_pack_entry_pos(c->tree->object.sha1, mw->pack)) == -1 ||\n+\t (p1 = find_pack_entry_pos(c->parents->item->object.sha1, mw->pack)) == -1 ||\n+\t (c->parents->next &&\n+\t (p2 = find_pack_entry_pos(c->parents->next->item->object.sha1, mw->pack)) == -1) ||\n+\t /*\n+\t * we set the 2nd parent the same as 1st parent as an\n+\t * indication that 2nd parent does not exist. Normal\n+\t * commits should never have two same parents, but just in\n+\t * case..\n+\t */\n+\t p1 == p2 ||\n+\t /* zero date is reserved to say this is not a valid entry */\n+\t c->date == 0) {\n+\t\tif (dry_run)\n+\t\t\treturn -1;\n+\t\tmetapack_writer_add_uint32(mw, 0); /* date */\n+\t\tmetapack_writer_add_uint32(mw, 0); /* tree */\n+\t\tmetapack_writer_add_uint32(mw, 0); /* 1st parent */\n+\t\tmetapack_writer_add_uint32(mw, 0); /* 2nd tree */\n+\t\treturn 0;\n+\t}\n+\n+\tif (dry_run)\n+\t\treturn 0;\n+\n+\trevindex = get_revindex(mw->pack);\n \n-\t*tail = &commit_list_insert(c, *tail)->next;\n+\tmetapack_writer_add_uint32(mw, c->date);\n+\tridx = find_pack_revindex(mw->pack,\n+\t\t\t\t nth_packed_object_offset(mw->pack, pt));\n+\tmetapack_writer_add_uint32(mw, ridx - revindex);\n+\tridx = find_pack_revindex(mw->pack,\n+\t\t\t\t nth_packed_object_offset(mw->pack, p1));\n+\tmetapack_writer_add_uint32(mw, ridx - revindex);\n+\tif (p2 != -1)\n+\t\tridx = find_pack_revindex(mw->pack,\n+\t\t\t\t\t nth_packed_object_offset(mw->pack, p2));\n+\tmetapack_writer_add_uint32(mw, ridx - revindex);\n+\treturn 0;\n }\n \n void commit_metapack_write(const char *idx)\n {\n \tstruct metapack_writer mw;\n-\tstruct commit_list *commits = NULL, *p;\n-\tstruct commit_list **tail = &commits;\n-\tuint32_t nr = 0;\n+\tuint32_t i, first = 0xffffffff, last = 0;\n+\tstruct revindex_entry *revidx;\n \n \tmetapack_writer_init(&mw, idx, \"commits\", 1);\n \n-\t/* Figure out how many eligible commits we've got in this pack. */\n-\tmetapack_writer_foreach(&mw, get_commits, &tail);\n-\tfor (p = commits; p; p = p->next)\n-\t\tnr++;\n-\tmetapack_writer_add_uint32(&mw, nr);\n+\tpacked_git = mw.pack;\n+\trevidx = get_revindex(mw.pack);\n \n-\t/* Then write an index of commit sha1s */\n-\tfor (p = commits; p; p = p->next)\n-\t\tmetapack_writer_add(&mw, p->item->object.sha1, 20);\n+\t/*\n+\t * Figure out how many eligible commits we've got in this pack.\n+\t */\n+\tfor (i = 0; i < mw.pack->num_objects; i++) {\n+\t\tint ret = get_commits(&mw, revidx[i].nr, 1);\n+\t\tif (ret == -1)\t/* not cached */\n+\t\t\tcontinue;\n+\t\tif (i < first)\n+\t\t\tfirst = i;\n+\t\tif (i > last)\n+\t\t\tlast = i;\n+\t}\n+\n+\tmetapack_writer_add_uint32(&mw, first);\n+\tmetapack_writer_add_uint32(&mw, last);\n \n \t/* Followed by the actual date/tree/parents data */\n-\tfor (p = commits; p; p = p->next) {\n-\t\tstruct commit *c = p->item;\n-\t\tmetapack_writer_add_uint32(&mw, c->date);\n-\t\tmetapack_writer_add(&mw, c->tree->object.sha1, 20);\n-\t\tmetapack_writer_add(&mw, c->parents->item->object.sha1, 20);\n-\t\tmetapack_writer_add(&mw,\n-\t\t\t\t c->parents->next ?\n-\t\t\t\t c->parents->next->item->object.sha1 :\n-\t\t\t\t null_sha1, 20);\n-\t}\n+\tfor (i = first; i <= last; i++)\n+\t\tget_commits(&mw, revidx[i].nr, 0);\n \n \tmetapack_writer_finish(&mw);\n }\ndiff --git a/commit-metapack.h b/commit-metapack.h\nindex 4684573..caf85be 100644\n--- a/commit-metapack.h\n+++ b/commit-metapack.h\n@@ -3,9 +3,9 @@\n \n int commit_metapack(unsigned char *sha1,\n \t\t uint32_t *timestamp,\n-\t\t unsigned char **tree,\n-\t\t unsigned char **parent1,\n-\t\t unsigned char **parent2);\n+\t\t const unsigned char **tree,\n+\t\t const unsigned char **parent1,\n+\t\t const unsigned char **parent2);\n \n void commit_metapack_write(const char *idx_file);\n \ndiff --git a/pack-revindex.c b/pack-revindex.c\nindex 77a0465..d58dd02 100644\n--- a/pack-revindex.c\n+++ b/pack-revindex.c\n@@ -111,12 +111,10 @@ static void create_pack_revindex(struct pack_revindex *rix)\n \tqsort(rix->revindex, num_ent, sizeof(*rix->revindex), cmp_offset);\n }\n \n-struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs)\n+struct revindex_entry *get_revindex(struct packed_git *p)\n {\n \tint num;\n-\tint lo, hi;\n \tstruct pack_revindex *rix;\n-\tstruct revindex_entry *revindex;\n \n \tif (!pack_revindex_hashsz)\n \t\tinit_pack_revindex();\n@@ -127,7 +125,13 @@ struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs)\n \trix = &pack_revindex[num];\n \tif (!rix->revindex)\n \t\tcreate_pack_revindex(rix);\n-\trevindex = rix->revindex;\n+\treturn rix->revindex;\n+}\n+\n+struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs)\n+{\n+\tint lo, hi;\n+\tstruct revindex_entry *revindex = get_revindex(p);\n \n \tlo = 0;\n \thi = p->num_objects + 1;\ndiff --git a/pack-revindex.h b/pack-revindex.h\nindex 8d5027a..cea85db 100644\n--- a/pack-revindex.h\n+++ b/pack-revindex.h\n@@ -6,6 +6,7 @@ struct revindex_entry {\n \tunsigned int nr;\n };\n \n+struct revindex_entry *get_revindex(struct packed_git *p);\n struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs);\n void discard_revindex(void);\n \ndiff --git a/sha1_file.c b/sha1_file.c\nindex 40b2329..1acab8c 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1978,8 +1978,8 @@ off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)\n \t}\n }\n \n-off_t find_pack_entry_one(const unsigned char *sha1,\n-\t\t\t\t struct packed_git *p)\n+int find_pack_entry_pos(const unsigned char *sha1,\n+\t\t\tstruct packed_git *p)\n {\n \tconst uint32_t *level1_ofs = p->index_data;\n \tconst unsigned char *index = p->index_data;\n@@ -1992,7 +1992,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \n \tif (!index) {\n \t\tif (open_pack_index(p))\n-\t\t\treturn 0;\n+\t\t\treturn -1;\n \t\tlevel1_ofs = p->index_data;\n \t\tindex = p->index_data;\n \t}\n@@ -2019,9 +2019,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \tif (use_lookup) {\n \t\tint pos = sha1_entry_pos(index, stride, 0,\n \t\t\t\t\t lo, hi, p->num_objects, sha1);\n-\t\tif (pos < 0)\n-\t\t\treturn 0;\n-\t\treturn nth_packed_object_offset(p, pos);\n+\t\treturn pos;\n \t}\n \n \tdo {\n@@ -2032,15 +2030,24 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \t\t\tprintf(\"lo %u hi %u rg %u mi %u\\n\",\n \t\t\t lo, hi, hi - lo, mi);\n \t\tif (!cmp)\n-\t\t\treturn nth_packed_object_offset(p, mi);\n+\t\t\treturn mi;\n \t\tif (cmp > 0)\n \t\t\thi = mi;\n \t\telse\n \t\t\tlo = mi+1;\n \t} while (lo < hi);\n-\treturn 0;\n+\treturn -1;\n }\n \n+off_t find_pack_entry_one(const unsigned char *sha1,\n+\t\t\t\t struct packed_git *p)\n+{\n+\tint pos = find_pack_entry_pos(sha1, p);\n+\tif (pos < 0)\n+\t\treturn 0;\n+\telse\n+\t\treturn nth_packed_object_offset(p, pos);\n+}\n int is_pack_valid(struct packed_git *p)\n {\n \t/* An already open pack is known to be valid. */\n-- \n1.8.1.1.459.g5970e58\n\n-- 8< --\n"},{"id":"208266","messageId":"CACsJy8Bqg6knVtddwaGSqtiXzVDgbO1JjbFOPMbF_RqrxM2rFQ@mail.gmail.com","threadId":"32765","inReplyTo":"20130130135607.GA23154@lanh","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-01-30T14:16:29Z","receivedAt":"2013-01-30T14:16:29Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Jan 30, 2013 at 8:56 PM, Duy Nguyen wrote:\n> However, performance seems to suffer too. Maybe I do more lookups than\n> necessary, I don't know.\n\nYes, I should have stored the position in the sha-1 <-> offset map\ninstead of the position of the object in .pack file. Even so,\nperformance does not improve.\n\n> I should probably measure the cost of revindex separately.\n\nAnd the cost of create_pack_revindex() is 0.6 sec :-(\n\nPerhaps we could store abbrev sha-1 instead of full sha-1. Nice\nspace/time trade-off.\n-- \nDuy\n"},{"id":"208270","messageId":"7vboc6mzpf.fsf@alter.siamese.dyndns.org","threadId":"32765","inReplyTo":"20130130071209.GD11147@sigill.intra.peff.net","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-01-30T15:56:44Z","receivedAt":"2013-01-30T15:56:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n>>From this:\n>\n>> Then it will be very natural for the extension data that store the\n>> commit metainfo to name objects in the pack the .idx file describes\n>> by the offset in the SHA-1 table.\n>\n> I guess your argument is that putting it all in the same file makes it\n> more natural for there to be a data dependency.\n\nIt is more about the \"I am torn on this one\" I mentioned earlier.\n\nIt would be more \"logical\" if this weren't tied to a particular\npack, as the properties of a commit you record in this series do not\ndepend on which pack the commit is in, and such a repository-global\nfile by definition cannot be inside anybody's .idx.\n\nBut if we split the information into separate pieces and store one\npiece per .idx for implementation reasons, it is crazy not to at\nleast consider it a longer term goal to put it inside .idx file.\n\nOf course, it is more convenient to store this kind of things in a\nseparate file while experimenting and improving the mechanism, but I\ndo not think we want to see each packfile in a repository comes with\n47 auxiliary files with different suffixes 5 years down the road.\n"},{"id":"208351","messageId":"20130131110656.GA28093@lanh","threadId":"32765","inReplyTo":"CACsJy8Bqg6knVtddwaGSqtiXzVDgbO1JjbFOPMbF_RqrxM2rFQ@mail.gmail.com","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-01-31T11:06:56Z","receivedAt":"2013-01-31T11:06:56Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Jan 30, 2013 at 09:16:29PM +0700, Duy Nguyen wrote:\n> Perhaps we could store abbrev sha-1 instead of full sha-1. Nice\n> space/time trade-off.\n\nFollowing the on-disk format experiment yesterday, I changed the\nformat to:\n\n - a list a _short_ SHA-1 of cached commits\n - a list of cache entries, each (5 uint32_t) consists of:\n - uint32_t for the index in .idx sha-1 table to get full SHA-1 of\n the commit\n - uint32_t for timestamp\n - uint32_t for tree, 1st and 2nd parents for the index in .idx\n table\n\nThe length of SHA-1 is chosen to be able to unambiguously identify any\ncached commits. Full SHA-1 check is done after to catch false\npositives. For linux-2.6, SHA-1 length is 6 bytes, git and many\nmoderate-sized projects are 4 bytes. So it's 26 bytes per commit for\nlinux-2.6.git, or 8MB .commits file. Not as good as revindex approach\n(5.5MB) but way better than the current one (27MB). And still good\nenough for caching 2 parents unconditionally.\n\nPerformance seems to improve a tiny bit, probably because of more\ncompact search space: 0.6s with my patch vs 0.7s without (vs 3.4s\nwithout cache).\n\n-- 8< --\ndiff --git a/cache.h b/cache.h\nindex 1f96f65..8048d5b 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1069,6 +1069,7 @@ extern struct packed_git *add_packed_git(const char *, int, int);\n extern const unsigned char *nth_packed_object_sha1(struct packed_git *, uint32_t);\n extern off_t nth_packed_object_offset(const struct packed_git *, uint32_t);\n extern off_t find_pack_entry_one(const unsigned char *, struct packed_git *);\n+extern int find_pack_entry_pos(const unsigned char *, struct packed_git *);\n extern int is_pack_valid(struct packed_git *);\n extern void *unpack_entry(struct packed_git *, off_t, enum object_type *, unsigned long *);\n extern unsigned long unpack_object_header_buffer(const unsigned char *buf, unsigned long len, enum object_type *type, unsigned long *sizep);\ndiff --git a/commit-metapack.c b/commit-metapack.c\nindex 2c19f48..c984b8e 100644\n--- a/commit-metapack.c\n+++ b/commit-metapack.c\n@@ -4,11 +4,21 @@\n #include \"commit.h\"\n #include \"sha1-lookup.h\"\n \n+struct commit_entry {\n+\tuint32_t commit;\t/* nth_packed_object_sha1 to get own SHA-1 */\n+\tuint32_t timestamp;\n+\tuint32_t tree;\t\t/* nth_packed_object_sha1 to get tree SHA-1 */\n+\tuint32_t parent1; /* nth_packed_object_sha1 to get 1st parent SHA-1 */\n+\tuint32_t parent2; /* nth_packed_object_sha1 to get 2nd parent SHA-1 */\n+};\n+\n struct commit_metapack {\n \tstruct metapack mp;\n \tuint32_t nr;\n+\tuint32_t abbrev_len;\n+\tstruct packed_git *pack;\n \tunsigned char *index;\n-\tunsigned char *data;\n+\tstruct commit_entry *data;\n \tstruct commit_metapack *next;\n };\n static struct commit_metapack *commit_metapacks;\n@@ -41,20 +51,23 @@ static struct commit_metapack *alloc_commit_metapack(struct packed_git *pack)\n \t}\n \tmemcpy(&it->nr, it->mp.data, 4);\n \tit->nr = ntohl(it->nr);\n+\tmemcpy(&it->abbrev_len, it->mp.data + 4, 4);\n+\tit->abbrev_len = ntohl(it->abbrev_len);\n+\tit->pack = pack;\n \n \t/*\n-\t * We need 84 bytes for each entry: sha1(20), date(4), tree(20),\n-\t * parents(40).\n+\t * We need 20+abbrev_len bytes for each entry: abbrev sha-1,\n+\t * date(4), tree index(4), parent indexes(8).\n \t */\n-\tif (it->mp.len < (84 * it->nr + 4)) {\n+\tif (it->mp.len < ((sizeof(*it->data) + it->abbrev_len) * it->nr + 8)) {\n \t\twarning(\"commit metapack for '%s' is truncated\", pack->pack_name);\n \t\tmetapack_close(&it->mp);\n \t\tfree(it);\n \t\treturn NULL;\n \t}\n \n-\tit->index = it->mp.data + 4;\n-\tit->data = it->index + 20 * it->nr;\n+\tit->index = it->mp.data + 8;\n+\tit->data = (struct commit_entry*)(it->index + it->abbrev_len * it->nr);\n \n \treturn it;\n }\n@@ -83,29 +96,51 @@ static void prepare_commit_metapacks(void)\n \n int commit_metapack(unsigned char *sha1,\n \t\t uint32_t *timestamp,\n-\t\t unsigned char **tree,\n-\t\t unsigned char **parent1,\n-\t\t unsigned char **parent2)\n+\t\t const unsigned char **tree,\n+\t\t const unsigned char **parent1,\n+\t\t const unsigned char **parent2)\n {\n \tstruct commit_metapack *p;\n \n \tprepare_commit_metapacks();\n \tfor (p = commit_metapacks; p; p = p->next) {\n-\t\tunsigned char *data;\n-\t\tint pos = sha1_entry_pos(p->index, 20, 0, 0, p->nr, p->nr, sha1);\n+\t\tstruct commit_entry *data;\n+\t\tuint32_t p1, p2;\n+\t\tunsigned lo, hi, mi;\n+\t\tint pos;\n+\n+\t\t/* sha1_entry_pos does not work with abbreviated sha-1 */\n+\t\tlo = 0;\n+\t\thi = p->nr;\n+\t\tpos = -1;\n+\t\tdo {\n+\t\t\tunsigned mi = (lo + hi) / 2;\n+\t\t\tint cmp = memcmp(p->index + mi * p->abbrev_len, sha1, p->abbrev_len);\n+\n+\t\t\tif (!cmp) {\n+\t\t\t\tpos = mi;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (cmp > 0)\n+\t\t\t\thi = mi;\n+\t\t\telse\n+\t\t\t\tlo = mi+1;\n+\t\t} while (lo < hi);\n \t\tif (pos < 0)\n \t\t\tcontinue;\n \n-\t\t/* timestamp(4) + tree(20) + parents(40) */\n-\t\tdata = p->data + 64 * pos;\n-\t\t*timestamp = *(uint32_t *)data;\n-\t\t*timestamp = ntohl(*timestamp);\n-\t\tdata += 4;\n-\t\t*tree = data;\n-\t\tdata += 20;\n-\t\t*parent1 = data;\n-\t\tdata += 20;\n-\t\t*parent2 = data;\n+\t\tdata = p->data + pos;\n+\n+\t\t/* full sha-1 check again */\n+\t\tif (hashcmp(nth_packed_object_sha1(p->pack, ntohl(data->commit)), sha1))\n+\t\t\tcontinue;\n+\n+\t\t*timestamp = ntohl(data->timestamp);\n+\t\t*tree = nth_packed_object_sha1(p->pack, ntohl(data->tree));\n+\t\tp1 = ntohl(data->parent1);\n+\t\t*parent1 = nth_packed_object_sha1(p->pack, p1);\n+\t\tp2 = ntohl(data->parent2);\n+\t\t*parent2 = p1 == p2 ? null_sha1 : nth_packed_object_sha1(p->pack, p2);\n \n \t\treturn 0;\n \t}\n@@ -113,13 +148,20 @@ int commit_metapack(unsigned char *sha1,\n \treturn -1;\n }\n \n+struct write_cb {\n+\tstruct commit_list **tail;\n+\tint abbrev_len;\n+\tconst unsigned char *last_sha1;\n+};\n+\n static void get_commits(struct metapack_writer *mw,\n \t\t\tconst unsigned char *sha1,\n \t\t\tvoid *data)\n {\n-\tstruct commit_list ***tail = data;\n+\tstruct write_cb *write_cb = (struct write_cb *)data;\n \tenum object_type type = sha1_object_info(sha1, NULL);\n \tstruct commit *c;\n+\tint p1, p2;\n \n \tif (type != OBJ_COMMIT)\n \t\treturn;\n@@ -128,47 +170,95 @@ static void get_commits(struct metapack_writer *mw,\n \tif (!c || parse_commit(c))\n \t\tdie(\"unable to read commit %s\", sha1_to_hex(sha1));\n \n+\tif (c->buffer) {\n+\t\tfree(c->buffer);\n+\t\tc->buffer = NULL;\n+\t}\n+\n \t/*\n \t * Our fixed-size parent list cannot represent root commits, nor\n \t * octopus merges. Just skip those commits, as we can fallback\n \t * in those rare cases to reading the actual commit object.\n \t */\n \tif (!c->parents ||\n-\t (c->parents && c->parents->next && c->parents->next->next))\n+\t (c->parents && c->parents->next && c->parents->next->next) ||\n+\t /* edge commits are out too */\n+\t find_pack_entry_pos(c->tree->object.sha1, mw->pack) == -1 ||\n+\t (p1 = find_pack_entry_pos(c->parents->item->object.sha1, mw->pack)) == -1 ||\n+\t (c->parents->next &&\n+\t (p2 = find_pack_entry_pos(c->parents->next->item->object.sha1, mw->pack)) == -1) ||\n+\t /*\n+\t * we set the 2nd parent the same as 1st parent as an\n+\t * indication that 2nd parent does not exist. Normal\n+\t * commits should never have two same parents, but just in\n+\t * case..\n+\t */\n+\t p1 == p2)\n \t\treturn;\n \n-\t*tail = &commit_list_insert(c, *tail)->next;\n+\t/*\n+\t * Make sure we store the abbr sha-1 long enough to\n+\t * unambiguously identify any cached commits in the pack.\n+\t */\n+\twhile (write_cb->abbrev_len < 20 &&\n+\t write_cb->last_sha1 &&\n+\t !memcmp(write_cb->last_sha1, sha1, write_cb->abbrev_len))\n+\t\twrite_cb->abbrev_len++;\n+\t/*\n+\t * A bit sensitive to metapack_writer_foreach. \"sha1\" must not\n+\t * be changed even after this function exits.\n+\t */\n+\twrite_cb->last_sha1 = sha1;\n+\n+\twrite_cb->tail = &commit_list_insert(c, write_cb->tail)->next;\n }\n \n void commit_metapack_write(const char *idx)\n {\n \tstruct metapack_writer mw;\n \tstruct commit_list *commits = NULL, *p;\n-\tstruct commit_list **tail = &commits;\n+\tstruct write_cb write_cb;\n \tuint32_t nr = 0;\n \n \tmetapack_writer_init(&mw, idx, \"commits\", 1);\n \n+\twrite_cb.tail = &commits;\n+\twrite_cb.abbrev_len = 1;\n+\twrite_cb.last_sha1 = NULL;\n+\n \t/* Figure out how many eligible commits we've got in this pack. */\n-\tmetapack_writer_foreach(&mw, get_commits, &tail);\n+\tmetapack_writer_foreach(&mw, get_commits, &write_cb);\n \tfor (p = commits; p; p = p->next)\n \t\tnr++;\n+\n \tmetapack_writer_add_uint32(&mw, nr);\n+\tmetapack_writer_add_uint32(&mw, write_cb.abbrev_len);\n \n \t/* Then write an index of commit sha1s */\n \tfor (p = commits; p; p = p->next)\n-\t\tmetapack_writer_add(&mw, p->item->object.sha1, 20);\n+\t\tmetapack_writer_add(&mw, p->item->object.sha1, write_cb.abbrev_len);\n \n \t/* Followed by the actual date/tree/parents data */\n \tfor (p = commits; p; p = p->next) {\n \t\tstruct commit *c = p->item;\n+\t\tint pos;\n+\n+\t\tpos = find_pack_entry_pos(c->object.sha1, mw.pack);\n+\t\tmetapack_writer_add_uint32(&mw, pos);\n+\n \t\tmetapack_writer_add_uint32(&mw, c->date);\n-\t\tmetapack_writer_add(&mw, c->tree->object.sha1, 20);\n-\t\tmetapack_writer_add(&mw, c->parents->item->object.sha1, 20);\n-\t\tmetapack_writer_add(&mw,\n-\t\t\t\t c->parents->next ?\n-\t\t\t\t c->parents->next->item->object.sha1 :\n-\t\t\t\t null_sha1, 20);\n+\n+\t\tpos = find_pack_entry_pos(c->tree->object.sha1, mw.pack);\n+\t\tmetapack_writer_add_uint32(&mw, pos);\n+\n+\t\tpos = find_pack_entry_pos(c->parents->item->object.sha1, mw.pack);\n+\t\tmetapack_writer_add_uint32(&mw, pos);\n+\n+\t\tif (c->parents->next) {\n+\t\t\tstruct object *o = &c->parents->next->item->object;\n+\t\t\tpos = find_pack_entry_pos(o->sha1, mw.pack);\n+\t\t}\n+\t\tmetapack_writer_add_uint32(&mw, pos);\n \t}\n \n \tmetapack_writer_finish(&mw);\ndiff --git a/commit-metapack.h b/commit-metapack.h\nindex 4684573..caf85be 100644\n--- a/commit-metapack.h\n+++ b/commit-metapack.h\n@@ -3,9 +3,9 @@\n \n int commit_metapack(unsigned char *sha1,\n \t\t uint32_t *timestamp,\n-\t\t unsigned char **tree,\n-\t\t unsigned char **parent1,\n-\t\t unsigned char **parent2);\n+\t\t const unsigned char **tree,\n+\t\t const unsigned char **parent1,\n+\t\t const unsigned char **parent2);\n \n void commit_metapack_write(const char *idx_file);\n \ndiff --git a/sha1_file.c b/sha1_file.c\nindex 40b2329..1acab8c 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1978,8 +1978,8 @@ off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)\n \t}\n }\n \n-off_t find_pack_entry_one(const unsigned char *sha1,\n-\t\t\t\t struct packed_git *p)\n+int find_pack_entry_pos(const unsigned char *sha1,\n+\t\t\tstruct packed_git *p)\n {\n \tconst uint32_t *level1_ofs = p->index_data;\n \tconst unsigned char *index = p->index_data;\n@@ -1992,7 +1992,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \n \tif (!index) {\n \t\tif (open_pack_index(p))\n-\t\t\treturn 0;\n+\t\t\treturn -1;\n \t\tlevel1_ofs = p->index_data;\n \t\tindex = p->index_data;\n \t}\n@@ -2019,9 +2019,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \tif (use_lookup) {\n \t\tint pos = sha1_entry_pos(index, stride, 0,\n \t\t\t\t\t lo, hi, p->num_objects, sha1);\n-\t\tif (pos < 0)\n-\t\t\treturn 0;\n-\t\treturn nth_packed_object_offset(p, pos);\n+\t\treturn pos;\n \t}\n \n \tdo {\n@@ -2032,15 +2030,24 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \t\t\tprintf(\"lo %u hi %u rg %u mi %u\\n\",\n \t\t\t lo, hi, hi - lo, mi);\n \t\tif (!cmp)\n-\t\t\treturn nth_packed_object_offset(p, mi);\n+\t\t\treturn mi;\n \t\tif (cmp > 0)\n \t\t\thi = mi;\n \t\telse\n \t\t\tlo = mi+1;\n \t} while (lo < hi);\n-\treturn 0;\n+\treturn -1;\n }\n \n+off_t find_pack_entry_one(const unsigned char *sha1,\n+\t\t\t\t struct packed_git *p)\n+{\n+\tint pos = find_pack_entry_pos(sha1, p);\n+\tif (pos < 0)\n+\t\treturn 0;\n+\telse\n+\t\treturn nth_packed_object_offset(p, pos);\n+}\n int is_pack_valid(struct packed_git *p)\n {\n \t/* An already open pack is known to be valid. */\n-- 8< --\n"},{"id":"208366","messageId":"CAJo=hJv0aqLpitnRJ6WKdPCETT6YgX5Njpv44DAYUg_KALhf=g@mail.gmail.com","threadId":"32765","inReplyTo":"7vboc6mzpf.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2013-01-31T17:03:26Z","receivedAt":"2013-01-31T17:03:26Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Wed, Jan 30, 2013 at 7:56 AM, Junio C Hamano wrote:\n> Jeff King writes:\n>\n>>>From this:\n>>\n>>> Then it will be very natural for the extension data that store the\n>>> commit metainfo to name objects in the pack the .idx file describes\n>>> by the offset in the SHA-1 table.\n>>\n>> I guess your argument is that putting it all in the same file makes it\n>> more natural for there to be a data dependency.\n>\n> It is more about the \"I am torn on this one\" I mentioned earlier.\n>\n> It would be more \"logical\" if this weren't tied to a particular\n> pack, as the properties of a commit you record in this series do not\n> depend on which pack the commit is in, and such a repository-global\n> file by definition cannot be inside anybody's .idx.\n>\n> But if we split the information into separate pieces and store one\n> piece per .idx for implementation reasons, it is crazy not to at\n> least consider it a longer term goal to put it inside .idx file.\n>\n> Of course, it is more convenient to store this kind of things in a\n> separate file while experimenting and improving the mechanism, but I\n> do not think we want to see each packfile in a repository comes with\n> 47 auxiliary files with different suffixes 5 years down the road.\n\nArrrrgggh.\n\nRight now we are in the middle of refactoring the JGit reachability\nbitmap implementation to store it into a separate file and get it out\nof the .idx file. This work is nearly completed. So this thread is\ngreat timing. :-)\n\nI think Junio is right about not wanting 47 different tiny auxiliary\nfiles for a single pack. We are unlikely to create that many, but\nright now there are proposals floating around for at least 2 new\nauxiliary files (commit cache and reachability bitmaps). So its not\nimpossible that another will be discovered in the future.\n\nJunio may be right about the hole in the index file for git-core. I\nhaven't checked the JGit implementation, but I suspect it does not\nhave this hole. IIRC JGit consumes the index sections and then expects\nthe pack trailer SHA-1 to be present immediately after the last table.\nThis happens because JGit doesn't use mmap() to load the index, it\nstreams the file into memory and does some reformatting on the tables\nto make search faster.\n\nIf we are going to change the index to support extension sections and\nI have to modify JGit to grok this new format, it needs to be index v3\nnot index v2. If we are making index v3 we should just put index v3 on\nthe end of the pack file.\n"},{"id":"208368","messageId":"CAJo=hJtTYZg+1+RZVfEGTgOGzqxQbN1CLYWrvUp+WHKGxGwHMQ@mail.gmail.com","threadId":"32765","inReplyTo":"20130129091434.GA6975@sigill.intra.peff.net","subject":"Re: [PATCH/RFC 0/6] commit caching","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2013-01-31T17:14:26Z","receivedAt":"2013-01-31T17:14:26Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Tue, Jan 29, 2013 at 1:14 AM, Jeff King wrote:\n> This is the cleaned-up version of the commit caching patches I mentioned\n> here:\n>\n> http://article.gmane.org/gmane.comp.version-control.git/212329\n...\n> The short of it is that for an extra 31M of disk\n> space (~4%), I get a warm-cache speedup for \"git rev-list --all\" of\n> ~4.2s to ~0.66s.\n\nI have to admit, this is a nice gain. I don't think users often dig\nthrough all commits to the root but I can see how this might improve\ngit log with a path filter.\n\n> Coupled with using compression level 0 for trees (which do not compress\n> well at all, and yield only a 2% increase in size when left\n> uncompressed), my \"git rev-list --objects --all\" time drops from ~40s to\n> ~25s.\n\nThis uhm.... is nice?\n\nBut consider reachability bitmaps. ~40s to ~80ms. :-)\n\n> Perf reveals that we're spending most of the remaining time in\n> lookup_object. I've spent a fair bit of time trying to optimize that,\n> but with no luck; I think it's fairly close to optimal. The problem is\n> just that we call it a very large number of times, since it is the\n> mechanism by which we recognize that we have already processed each\n> sha1.\n\nYup. I have also futzed with the one in JGit for quite a while now. I\npull some tricks there like making it a 2 level directory to reduce\nthe need to find a contiguous array of 8M entries when processing the\nLinux kernel, and I try to preallocate the first level table based on\nthe number of objects in pack-*.idx files. But the bottleneck is\nbasically the cache lookups and hits, these happen like 100M times on\n2M objects, because its every link in nearly every tree.\n\nReachability bitmaps basically let you skip this. So they go fast. But\nI have another that you could try.\n\nIf we modified pack-objects' delta compressor for tree objects to only\ngenerate delta instructions at tree record boundaries, a delta-encoded\ntree can be processed without inflating the full content of that tree.\nBecause of the way deltas are created, \"most\" tree deltas should have\ntheir delta base scanned by the object traversal before the delta is\nconsidered. This means the tree delta just needs to consider the much\nsmaller records that are inserted into the base. We know these are\ndifferent SHA-1s than what was there before, so they are more likely\nto be new to the lookup_object table.\n\nSo the --objects traversal algorithm can change to get the delta base\nSHA-1 and raw tree delta from the pack storage. Perform a\nlookup_object on the base to see if it has been scanned. If it has,\njust scan the delta insert instructions. If the base has not yet been\nscanned, inflate the tree to its normal format and scan the entire\ntree.\n\nThis is an approximation of what Nico and I were talking about doing\nfor pack v4. But doesn't require a file format change. :-)\n"},{"id":"208458","messageId":"20130201091130.GB30644@sigill.intra.peff.net","threadId":"32765","inReplyTo":"CAJo=hJtTYZg+1+RZVfEGTgOGzqxQbN1CLYWrvUp+WHKGxGwHMQ@mail.gmail.com","subject":"Re: [PATCH/RFC 0/6] commit caching","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-02-01T09:11:30Z","receivedAt":"2013-02-01T09:11:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 31, 2013 at 09:14:26AM -0800, Shawn O. Pearce wrote:\n\n> On Tue, Jan 29, 2013 at 1:14 AM, Jeff King wrote:\n> > This is the cleaned-up version of the commit caching patches I mentioned\n> > here:\n> >\n> > http://article.gmane.org/gmane.comp.version-control.git/212329\n> ...\n> > The short of it is that for an extra 31M of disk\n> > space (~4%), I get a warm-cache speedup for \"git rev-list --all\" of\n> > ~4.2s to ~0.66s.\n> \n> I have to admit, this is a nice gain. I don't think users often dig\n> through all commits to the root but I can see how this might improve\n> git log with a path filter.\n\nIt doesn't just help digging to the roots. It should speed up most\ntraversals. So merge-bases, --contains, etc, would all be better. I\nsuspect we could also make --topo-order startup a lot faster, too.\n\nIt also helps \"rev-list --objects --all\", though obviously not by as\nlarge a percentage. And since the main use of that is reachability\nbitmaps, the improvements aren't as exciting there.\n\n> > Coupled with using compression level 0 for trees (which do not compress\n> > well at all, and yield only a 2% increase in size when left\n> > uncompressed), my \"git rev-list --objects --all\" time drops from ~40s to\n> > ~25s.\n> \n> This uhm.... is nice?\n> \n> But consider reachability bitmaps. ~40s to ~80ms. :-)\n\nYeah, yeah. I'm working my way up to it. :)\n\nI wanted to see first how good we could get with a more generic\napproach. I think this work may still have value even with reachability\nbitmaps, as it will help regular traversals as well as tree access for\npathspec limiting.\n\nAt this point I'm convinced that my 25s is about the best we will do for\nreachability analysis with a graph traversal. The repeated hashcmps to\nsee that we've visited each node are starting to dominate. So the next\nobvious step is to try reachability bitmaps. I was hoping to iron out\nthe \"pack metadata goes here\" issues with the commit cache stuff,\nthough, as the actual cache implementation is quite simple (whereas the\nbitmap stuff is more on the complex side, but can build on the same\nmetadata base).\n\n> Yup. I have also futzed with the one in JGit for quite a while now. I\n> pull some tricks there like making it a 2 level directory to reduce\n> the need to find a contiguous array of 8M entries when processing the\n> Linux kernel, and I try to preallocate the first level table based on\n> the number of objects in pack-*.idx files. But the bottleneck is\n> basically the cache lookups and hits, these happen like 100M times on\n> 2M objects, because its every link in nearly every tree.\n\nRight. I tried some multi-level tricks (and even a radix trie), but I\ncouldn't get anything to beat the simple-and-stupid single hash table\nwith linear probing.\n\n> If we modified pack-objects' delta compressor for tree objects to only\n> generate delta instructions at tree record boundaries, a delta-encoded\n> tree can be processed without inflating the full content of that tree.\n> Because of the way deltas are created, \"most\" tree deltas should have\n> their delta base scanned by the object traversal before the delta is\n> considered. This means the tree delta just needs to consider the much\n> smaller records that are inserted into the base. We know these are\n> different SHA-1s than what was there before, so they are more likely\n> to be new to the lookup_object table.\n\nSo sort of a magic shortcut tree diff you get while accessing the\nobject. Neat idea.\n\n> So the --objects traversal algorithm can change to get the delta base\n> SHA-1 and raw tree delta from the pack storage. Perform a\n> lookup_object on the base to see if it has been scanned. If it has,\n> just scan the delta insert instructions. If the base has not yet been\n> scanned, inflate the tree to its normal format and scan the entire\n> tree.\n\nThis would not perform well if we hit the deltas before the bases. In\ngeneral, though, our \"use the larger as the base\" heuristic should mean\nthat our traversal hits the bases first.\n\n> This is an approximation of what Nico and I were talking about doing\n> for pack v4. But doesn't require a file format change. :-)\n\nYeah. It just needs to be very careful that the deltas it is looking at\nall fall on record boundaries, since we might get deltas generated by\nother versions of git. Can we necessarily identify that case for sure,\nthough? I imagine a tree delta like that would look something like:\n\n delete bytes 100-120\n add 20 bytes at offset 100: \\x12\\x34\\x56...\n\nWithout looking at the base object, and without knowing whether the\ndelta was generated by our particular implementation, how can we be sure\nthis is a sha1 replacement and not the renaming of part of a file? Or\nare you proposing some flag in the packfile to indicate \"yes, this tree\nreally was delta'd only at record boundaries\"?\n\nIt could be a big win, but it does seem quite complex and error-prone.\nAnd it only helps with reachability, not regular traversals, so it's not\nvery generic. Which makes me think the bitmap route is a much better way\nto go.\n\n-Peff\n"},{"id":"208461","messageId":"20130201092105.GD30644@sigill.intra.peff.net","threadId":"32765","inReplyTo":"7vk3qvm962.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-02-01T09:21:05Z","receivedAt":"2013-02-01T09:21:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 29, 2013 at 11:17:41PM -0800, Junio C Hamano wrote:\n\n> > True, but it is even less headache if the file is totally separate and\n> > optional.\n> \n> Once you start thinking about using an offset to some list of SHA-1,\n> perhaps? A section inside the same file can never go out of sync.\n\nYes, having a data dependency is important. It is unavoidable to have a\ndependency on the packfile, though (and that is why the index and the\nmetapacks embed the sha1 of the packfile). If the offsets used are\npackfile offsets, then that is sufficient.\n\nIf the offsets are from the index, then yes, putting it in the same file\nis one way to keep them tied together. Another way is to do the same\nsha1 verification, except to embed the sha1 of the index in the\nmetapack.\n\nSo I certainly consider putting the dependency-handling to be a point in\nfavor of the same file, but I'd weight it against other points (headache\nof bumping index version, performance of both types, etc).\n\n> Also a longer-term advantage is that you can teach index-pack to do\n> this.\n\nI think that is roughly the same amount of difficulty to do whether they\nare in the same file or not.\n\n-Peff\n"},{"id":"208462","messageId":"20130201094237.GE30644@sigill.intra.peff.net","threadId":"32765","inReplyTo":"CAJo=hJv0aqLpitnRJ6WKdPCETT6YgX5Njpv44DAYUg_KALhf=g@mail.gmail.com","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-02-01T09:42:41Z","receivedAt":"2013-02-01T09:42:41Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 31, 2013 at 09:03:26AM -0800, Shawn O. Pearce wrote:\n\n> > Of course, it is more convenient to store this kind of things in a\n> > separate file while experimenting and improving the mechanism, but I\n> > do not think we want to see each packfile in a repository comes with\n> > 47 auxiliary files with different suffixes 5 years down the road.\n> \n> Arrrrgggh.\n> \n> Right now we are in the middle of refactoring the JGit reachability\n> bitmap implementation to store it into a separate file and get it out\n> of the .idx file. This work is nearly completed. So this thread is\n> great timing. :-)\n> \n> I think Junio is right about not wanting 47 different tiny auxiliary\n> files for a single pack. We are unlikely to create that many, but\n> right now there are proposals floating around for at least 2 new\n> auxiliary files (commit cache and reachability bitmaps). So its not\n> impossible that another will be discovered in the future.\n\nWhy don't we want 47 files (or even 3)? If it makes the implementation\nmore flexible or simple without sacrificing performance, I don't see a\nproblem. The filesystem is there to organize our data; we do not cram\nall of our files into one just to save a few inodes.\n\nWe _do_ cram our data into packfiles and packed-refs when we can save\nO(n) inodes. But if we are talking about a handful of extra files that\nwe must readdir() over while preparing the objects/pack directory, I\ndon't think that is the same thing.\n\nThe data dependency issues (can the files get out of sync? How common is\nit? Can we detect it?) and performance issues are more interesting to\nme. With respect to the latter, here's specifically what I'm thinking\nof. Let's imagine we have an extension for reachability bitmaps that\ntakes up an extra 10MB. When we mmap the .idx file, do we always mmap\nthe extra bytes? What's the performance impact of the extra mmap? I\nrecall on some non-Linux systems it can be quite expensive. For most git\ncommands which are not going to do a reachability analysis, this is a\nloss.\n\nI don't know if this is an issue big enough to care about or not. But I\nthink it's worth benchmarking and including in the decision.\n\n> Junio may be right about the hole in the index file for git-core. I\n> haven't checked the JGit implementation, but I suspect it does not\n> have this hole. IIRC JGit consumes the index sections and then expects\n> the pack trailer SHA-1 to be present immediately after the last table.\n> This happens because JGit doesn't use mmap() to load the index, it\n> streams the file into memory and does some reformatting on the tables\n> to make search faster.\n\nYeah, looking at the PackIndexV2 implementation, it counts the 64-bit\noffsets from the first table, calculates the size of the large offset\ntable, reads past it, and then expects the pack checksum. So let's\nassume we would have to bump to v3 to implement it inside the .idx file.\n\n> If we are going to change the index to support extension sections and\n> I have to modify JGit to grok this new format, it needs to be index v3\n> not index v2. If we are making index v3 we should just put index v3 on\n> the end of the pack file.\n\nI'm not sure what you mean by your last sentence here.\n\n-Peff\n"},{"id":"208464","messageId":"20130201100002.GF30644@sigill.intra.peff.net","threadId":"32765","inReplyTo":"20130130135607.GA23154@lanh","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-02-01T10:00:02Z","receivedAt":"2013-02-01T10:00:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 30, 2013 at 08:56:07PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> Another point, but not really important at this stage, I think we have\n> memory leak somewhere (lookup_commit??). It used up to 800 MB RES on\n> linux-2.6.git while generating the cache.\n\nWe generate (and then leak!) the linked list in commit_metapack_write.\nThat may be the culprit.\n\n-Peff\n"},{"id":"208465","messageId":"20130201101503.GG30644@sigill.intra.peff.net","threadId":"32765","inReplyTo":"20130131110656.GA28093@lanh","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-02-01T10:15:03Z","receivedAt":"2013-02-01T10:15:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 31, 2013 at 06:06:56PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> On Wed, Jan 30, 2013 at 09:16:29PM +0700, Duy Nguyen wrote:\n> > Perhaps we could store abbrev sha-1 instead of full sha-1. Nice\n> > space/time trade-off.\n> \n> Following the on-disk format experiment yesterday, I changed the\n> format to:\n> \n> - a list a _short_ SHA-1 of cached commits\n> - a list of cache entries, each (5 uint32_t) consists of:\n> - uint32_t for the index in .idx sha-1 table to get full SHA-1 of\n> the commit\n> - uint32_t for timestamp\n> - uint32_t for tree, 1st and 2nd parents for the index in .idx\n> table\n\nThanks for working on this, as it was the next step I was going to take. :)\n\nThe short-sha1 is a clever idea. Looks like it saves us on the order of\n4MB for linux-2.6 (versus the full 20-byte sha1). Not as big as the\nsavings we get from dropping the other 3 sha1's to uint32_t, but still\nnot bad.\n\nI guess the next steps in iterating on this would be:\n\n 1. splitting out the refactoring here into separate patches\n\n 2. squashing the cleaned-up bits into my patch 4/6\n\n 3. deciding whether this should go into a separate file or as part of\n index v3. Your offsets depend on the .idx file having a sorted sha1\n list. That is not likely to change, but it would still be nice to\n make sure they cannot get out of sync. I'm still curious what the\n performance impact is for mmap-ing N versus N+8MB.\n\n> The length of SHA-1 is chosen to be able to unambiguously identify any\n> cached commits. Full SHA-1 check is done after to catch false\n> positives.\n\nJust to be clear, these false positives come because the abbreviation is\nunambiguous within the packfile, but we might be looking for a commit\nthat is not even in our pack, right?\n\n-Peff\n"},{"id":"208468","messageId":"20130201104010.GH30644@sigill.intra.peff.net","threadId":"32765","inReplyTo":"20130131110656.GA28093@lanh","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-02-01T10:40:10Z","receivedAt":"2013-02-01T10:40:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 31, 2013 at 06:06:56PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> On Wed, Jan 30, 2013 at 09:16:29PM +0700, Duy Nguyen wrote:\n> > Perhaps we could store abbrev sha-1 instead of full sha-1. Nice\n> > space/time trade-off.\n> \n> Following the on-disk format experiment yesterday, I changed the\n> format to:\n> \n> - a list a _short_ SHA-1 of cached commits\n> - a list of cache entries, each (5 uint32_t) consists of:\n> - uint32_t for the index in .idx sha-1 table to get full SHA-1 of\n> the commit\n> - uint32_t for timestamp\n> - uint32_t for tree, 1st and 2nd parents for the index in .idx\n> table\n\nBTW, I needed the minor fixups below to silence some warnings from your\npatch. Here are the cold and warm cache timings I got, as compared to\nstock git and my implementation:\n\n Pack | Cold Revs | Warm Revs\n-------+--------------+------------\n stock | 12.54 | 4.14\n me | 4.76 (-62%) | 0.66 (-84%)\n duy | 4.36 (-65%) | 0.55 (-86%)\n\nNot surprising; yours is just a bit faster in terms of CPU, and even\ngains a little more in the cold cache case. Nice. Of course that is just\ngravy on top of the smaller disk usage, too. :)\n\n---\ndiff --git a/commit-metapack.c b/commit-metapack.c\nindex c984b8e..78fd961 100644\n--- a/commit-metapack.c\n+++ b/commit-metapack.c\n@@ -106,7 +106,7 @@ int commit_metapack(unsigned char *sha1,\n \tfor (p = commit_metapacks; p; p = p->next) {\n \t\tstruct commit_entry *data;\n \t\tuint32_t p1, p2;\n-\t\tunsigned lo, hi, mi;\n+\t\tunsigned lo, hi;\n \t\tint pos;\n \n \t\t/* sha1_entry_pos does not work with abbreviated sha-1 */\n@@ -161,7 +161,7 @@ static void get_commits(struct metapack_writer *mw,\n \tstruct write_cb *write_cb = (struct write_cb *)data;\n \tenum object_type type = sha1_object_info(sha1, NULL);\n \tstruct commit *c;\n-\tint p1, p2;\n+\tint p1 = -1, p2 = -1;\n \n \tif (type != OBJ_COMMIT)\n \t\treturn;\ndiff --git a/commit.c b/commit.c\nindex b326201..5b776f8 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -309,7 +309,7 @@ static int parse_commit_metapack(struct commit *item)\n \n static int parse_commit_metapack(struct commit *item)\n {\n-\tunsigned char *tree, *p1, *p2;\n+\tconst unsigned char *tree, *p1, *p2;\n \tuint32_t ts;\n \n \tif (commit_metapack(item->object.sha1, &ts, &tree, &p1, &p2) < 0)\n"},{"id":"208520","messageId":"CACsJy8COq-A2KJ8rNCxB23s4SMYA4Gqpr53NzqMv=i=sswV_0Q@mail.gmail.com","threadId":"32765","inReplyTo":"20130201101503.GG30644@sigill.intra.peff.net","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-02-02T09:49:17Z","receivedAt":"2013-02-02T09:49:17Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Feb 1, 2013 at 5:15 PM, Jeff King wrote:\n> The short-sha1 is a clever idea. Looks like it saves us on the order of\n> 4MB for linux-2.6 (versus the full 20-byte sha1). Not as big as the\n> savings we get from dropping the other 3 sha1's to uint32_t, but still\n> not bad.\n\nWe could save another 4 bytes per commit by using 3 bytes for storing\n.idx offsets. linux-2.6 only has 3M objects. It'll take many years for\nbig projects to reach 16M objects and need the fourth byte in\nuint32_t.\n\n\n> I guess the next steps in iterating on this would be:\n>\n> 1. splitting out the refactoring here into separate patches\n>\n> 2. squashing the cleaned-up bits into my patch 4/6\n>\n> 3. deciding whether this should go into a separate file or as part of\n> index v3. Your offsets depend on the .idx file having a sorted sha1\n> list. That is not likely to change, but it would still be nice to\n> make sure they cannot get out of sync. I'm still curious what the\n> performance impact is for mmap-ing N versus N+8MB.\n\n4. Print some cache statistics in \"count-objects -v\"\n\n\n>> The length of SHA-1 is chosen to be able to unambiguously identify any\n>> cached commits. Full SHA-1 check is done after to catch false\n>> positives.\n>\n> Just to be clear, these false positives come because the abbreviation is\n> unambiguous within the packfile, but we might be looking for a commit\n> that is not even in our pack, right?\n\nIt may even be ambiguous within the pack, say an octopus (i.e. not\ncached) commit that shares the same sha-1 prefix with one of the\ncached commits.\n-- \nDuy\n"},{"id":"208521","messageId":"CAJo=hJtBFoBXa0rmyo+oLwGa-7zPPAYXQ6nv33h2rFLyjbHKZA@mail.gmail.com","threadId":"32765","inReplyTo":"20130201091130.GB30644@sigill.intra.peff.net","subject":"Re: [PATCH/RFC 0/6] commit caching","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2013-02-02T10:04:51Z","receivedAt":"2013-02-02T10:04:51Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Fri, Feb 1, 2013 at 1:11 AM, Jeff King wrote:\n> On Thu, Jan 31, 2013 at 09:14:26AM -0800, Shawn O. Pearce wrote:\n>\n>> On Tue, Jan 29, 2013 at 1:14 AM, Jeff King wrote:\n>> > Coupled with using compression level 0 for trees (which do not compress\n>> > well at all, and yield only a 2% increase in size when left\n>> > uncompressed), my \"git rev-list --objects --all\" time drops from ~40s to\n>> > ~25s.\n>>\n>> This uhm.... is nice?\n>>\n>> But consider reachability bitmaps. ~40s to ~80ms. :-)\n>\n> Yeah, yeah. I'm working my way up to it. :)\n\n:-)\n\n> At this point I'm convinced that my 25s is about the best we will do for\n> reachability analysis with a graph traversal. The repeated hashcmps to\n> see that we've visited each node are starting to dominate. So the next\n> obvious step is to try reachability bitmaps.\n\nYea, its hard to make a big N go fast when you still have a big N...\n\n> I was hoping to iron out\n> the \"pack metadata goes here\" issues with the commit cache stuff,\n> though, as the actual cache implementation is quite simple (whereas the\n> bitmap stuff is more on the complex side, but can build on the same\n> metadata base).\n\nJunio and I were talking about putting these in an index v3, below the\ncurrent tables where he thought there was a hole in v2. I am inclined\nto agree with his comment elsewhere that we don't want 50 auxiliary\nfiles next to a pack in 5 years.\n\nBut if we go that route I also suggested we append the index below the\npack file itself, so its a single file, and that we rename the file to\nbe SHA1(all-bits) not SHA1(sorted-object-list). Both steps make it\nmuch safer to perform git gc on Windows while the repository is being\naccessed.\n\n>> Yup. I have also futzed with the one in JGit for quite a while now. I\n>> pull some tricks there like making it a 2 level directory to reduce\n>> the need to find a contiguous array of 8M entries when processing the\n>> Linux kernel, and I try to preallocate the first level table based on\n>> the number of objects in pack-*.idx files. But the bottleneck is\n>> basically the cache lookups and hits, these happen like 100M times on\n>> 2M objects, because its every link in nearly every tree.\n>\n> Right. I tried some multi-level tricks (and even a radix trie), but I\n> couldn't get anything to beat the simple-and-stupid single hash table\n> with linear probing.\n\nO(1) lookup is hard for big N. Lets go shopping^Wcoding instead.\n\n>> If we modified pack-objects' delta compressor for tree objects to only\n>> generate delta instructions at tree record boundaries, a delta-encoded\n>> tree can be processed without inflating the full content of that tree.\n>> Because of the way deltas are created, \"most\" tree deltas should have\n>> their delta base scanned by the object traversal before the delta is\n>> considered. This means the tree delta just needs to consider the much\n>> smaller records that are inserted into the base. We know these are\n>> different SHA-1s than what was there before, so they are more likely\n>> to be new to the lookup_object table.\n>\n> So sort of a magic shortcut tree diff you get while accessing the\n> object. Neat idea.\n\nYes, exactly.\n\n>> So the --objects traversal algorithm can change to get the delta base\n>> SHA-1 and raw tree delta from the pack storage. Perform a\n>> lookup_object on the base to see if it has been scanned. If it has,\n>> just scan the delta insert instructions. If the base has not yet been\n>> scanned, inflate the tree to its normal format and scan the entire\n>> tree.\n>\n> This would not perform well if we hit the deltas before the bases. In\n> general, though, our \"use the larger as the base\" heuristic should mean\n> that our traversal hits the bases first.\n\nIt won't perform worse than the current code. And its actually the\ntime heuristic that should kick in here for trees. Most trees are\nroughly the same size, or are only slightly bigger because a new\nsource file was added. More recent trees should appear earlier in the\ndelta window and be suitable candidates for older trees. So we should\nget a large percentage of trees covered by this trick.\n\n>> This is an approximation of what Nico and I were talking about doing\n>> for pack v4. But doesn't require a file format change. :-)\n>\n> Yeah. It just needs to be very careful that the deltas it is looking at\n> all fall on record boundaries, since we might get deltas generated by\n> other versions of git. Can we necessarily identify that case for sure,\n> though? I imagine a tree delta like that would look something like:\n>\n> delete bytes 100-120\n> add 20 bytes at offset 100: \\x12\\x34\\x56...\n\nOf course we can't know without some flag. I assumed it was obvious we\nwould need to tag the pack somehow with extra metadata to say \"every\ntree delta in this pack is on a record boundary\". That does make delta\nreuse more complex as a tree delta can only be reused if it is coming\nfrom a pack that has the same promise about record boundaries.\nOtherwise the delta must be regenerated during packing.\n\n> Without looking at the base object, and without knowing whether the\n> delta was generated by our particular implementation, how can we be sure\n> this is a sha1 replacement and not the renaming of part of a file? Or\n> are you proposing some flag in the packfile to indicate \"yes, this tree\n> really was delta'd only at record boundaries\"?\n\nYes, some sort of flag would be required on the pack. :-\\\n\n> It could be a big win, but it does seem quite complex and error-prone.\n\nIt is complex. But it seems so simple on the Internet...\n\n> And it only helps with reachability, not regular traversals, so it's not\n> very generic.\n\nIt should also help with path filter traversals. If we require the\ndeltas to be only at tree record boundaries then the mode and path\nwill be part of the delta, even if it is unmodified from the base\ntree. A path filter can avoid scanning the base sections if its\nalready seen that base tree before. This could be a substantial\nreduction in the number of tree records a path filter needs to examine\nto get a `git log -- path` or `git blame path` completed.\n\n> Which makes me think the bitmap route is a much better way\n> to go.\n\nBitmaps discard a lot of useful data in favor of being really freaking\nsmall. Colby was toying around with some other allocations of bitmaps\ntoday. I think he managed to bitmap basically every commit in the\nLinux kernel history since September... and its only 3M of data to\nstore on disk / cache in RAM. Very useful for serving fetch requests\nto clients that are at varying points in history, but not so good for\ndoing things like new delta compression or path limited history\ntraversal.\n\n\n\nWhat if we built a bitmap for each path? Linux kernel history is\n~41.5k paths. If the packer constructs a bitmap for each path that\nsets a commit's bit if the path is impacted in that commit, you can do\nsome incredibly fast path traversal operations. Naive implementation\nwould cost around 1.7G of disk, but I wonder how well that set of maps\nmight compress.\n\n\n"},{"id":"208524","messageId":"7vfw1ebo8i.fsf@alter.siamese.dyndns.org","threadId":"32765","inReplyTo":"20130201094237.GE30644@sigill.intra.peff.net","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-02-02T17:49:01Z","receivedAt":"2013-02-02T17:49:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Thu, Jan 31, 2013 at 09:03:26AM -0800, Shawn O. Pearce wrote:\n> ...\n>> If we are going to change the index to support extension sections and\n>> I have to modify JGit to grok this new format, it needs to be index v3\n>> not index v2. If we are making index v3 we should just put index v3 on\n>> the end of the pack file.\n>\n> I'm not sure what you mean by your last sentence here.\n\nI am not Shawn, but here is a summary of what I think I discussed\nwith him in person, lest I forget.\n\nYou could imagine that a new pack system (from pack-objects,\nindex-pack down to read_packed_sha1() call) that works with a\npackfile that\n\n * is a single file, whose name is pack-$SHA1.$sfx (where $sfx\n is something other than 'pack', perhaps);\n\n * has the pack data stream, including the concluding checksum of\n the stream contents at the end, at the beginning of the file; and\n\n * has the index v3 data blob appended to the pack data stream.\n\nThe pack data is streamed over the wire exactly the same way,\ninteroperating with existing software. When receiving, the new\nindex-pack can read such a pack stream and add index at the end.\nWhen re-indexing an existing pack (think: upgrading existing\npackfiles from the current system), the index-pack can read from the\npackfile and do what it does currently (notably, it knows where the\npack stream ends and can stop reading at that point, so even if you\nfeed the new pack to it, it will stop at the end of the pack data,\nignoring the index v3 already at the end of the input).\n\nOne potential advantage of using a single file, instead of the\nprimary .pack file with 3 (or 47) auxiliary files, is that it lets\nyou repack without having to deal with this sequence, which happens\ncurrently when you repack:\n\n * create a new .pack file and the corresponding auxiliary files\n under temporary filename;\n\n * move existing pack files that describe the same set of objects\n away;\n\n * rename these new files, one at a time, to their final name,\n making sure that you rename .idx the last, because that happens\n to be the key to the pack aware programs.\n\nInstead you can rename only one thing (the new one) to the final\nname (possibly atomically replacing the existing one). With the\ncurrent system, when you need to replace a pack with a new pack with\nthe same packname (e.g. you repack everything with a better pack\nparameter in a repository that has everything packed into one),\nthere is a very small window other concurrent users will not find\nthe object data between the time when you rename the old ones away\nand the time when you move the new ones in. The hairly logic\nbetween \"Ok we have prepared all new packfiles\" and \"End of pack\nreplacement\" can be done with a single rename(2) of the new packfile\n(which contains everything) to the final name, which atomically\nreplaces the old one.\n\nThis will become even safer if we picked $SHA1 (the name of the\npackfile) to represent the hash of the whole thing, not the hash of\nthe sorted object names in the pack, as that will let us know there\nis no need to even \"replace\" the files.\n"},{"id":"211517","messageId":"CACsJy8CPXFhUYz2f1wuxJvqwknJr5VFNFrs3b_4pS14cxf=3Wg@mail.gmail.com","threadId":"32765","inReplyTo":"20130131110656.GA28093@lanh","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-17T13:21:13Z","receivedAt":"2013-03-17T13:21:13Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Jan 31, 2013 at 6:06 PM, Duy Nguyen wrote:\n> On Wed, Jan 30, 2013 at 09:16:29PM +0700, Duy Nguyen wrote:\n>> Perhaps we could store abbrev sha-1 instead of full sha-1. Nice\n>> space/time trade-off.\n>\n> Following the on-disk format experiment yesterday, I changed the\n> format to:\n>\n> - a list a _short_ SHA-1 of cached commits\n> ..\n>\n> The length of SHA-1 is chosen to be able to unambiguously identify any\n> cached commits. Full SHA-1 check is done after to catch false\n> positives. For linux-2.6, SHA-1 length is 6 bytes, git and many\n> moderate-sized projects are 4 bytes.\n\nAnd if we are going to create index v3, the same trick could be used\nfor the sha-1 table in the index. We use the short sha-1 table for\nbinary search and put the rest of sha-1 in a following table (just\nlike file offset table). The advantage is a denser search space, about\n1/4-1/3 the size of full sha-1 table.\n-- \nDuy\n"},{"id":"211561","messageId":"20130318122011.GE14789@sigill.intra.peff.net","threadId":"32765","inReplyTo":"CACsJy8CPXFhUYz2f1wuxJvqwknJr5VFNFrs3b_4pS14cxf=3Wg@mail.gmail.com","subject":"Re: [PATCH 4/6] introduce a commit metapack","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-18T12:20:11Z","receivedAt":"2013-03-18T12:20:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Mar 17, 2013 at 08:21:13PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> On Thu, Jan 31, 2013 at 6:06 PM, Duy Nguyen wrote:\n> > On Wed, Jan 30, 2013 at 09:16:29PM +0700, Duy Nguyen wrote:\n> >> Perhaps we could store abbrev sha-1 instead of full sha-1. Nice\n> >> space/time trade-off.\n> >\n> > Following the on-disk format experiment yesterday, I changed the\n> > format to:\n> >\n> > - a list a _short_ SHA-1 of cached commits\n> > ..\n> >\n> > The length of SHA-1 is chosen to be able to unambiguously identify any\n> > cached commits. Full SHA-1 check is done after to catch false\n> > positives. For linux-2.6, SHA-1 length is 6 bytes, git and many\n> > moderate-sized projects are 4 bytes.\n> \n> And if we are going to create index v3, the same trick could be used\n> for the sha-1 table in the index. We use the short sha-1 table for\n> binary search and put the rest of sha-1 in a following table (just\n> like file offset table). The advantage is a denser search space, about\n> 1/4-1/3 the size of full sha-1 table.\n\nYou can make it even smaller at some (potential) run-time cost.\n\nKeep in mind you are just repeating information that is in the full sha1\nlist in the index. So you could store a fixed-size offset into that list\n(e.g., 32-bit), and then instead of comparing sha1s during a binary\nsearch, you would dereference the offset to the real sha1s and compare\nthose.\n\nThe run-time cost is not any worse in a big-O sense, but your cache\nlocality is much worse (you hit a second random page for each sha1\ncomparison), which might be noticeable. You'd have to benchmark to see\nhow big an impact.\n\n-Peff\n"}]}