{"thread":{"id":"34369","subject":"[RFC/PATCH 0/4] cat-file --batch-disk-sizes","startedAt":"2013-07-07T10:01:34Z","lastAt":"2013-07-11T21:12:04Z","messageCount":52,"participants":["Jeff King","Junio C Hamano","brian m. carlson","Shawn Pearce","Duy Nguyen","Ramkumar Ramachandra","Brandon Casey","Eric Sunshine"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"222732","messageId":"20130707100133.GA18717@sigill.intra.peff.net","threadId":"34369","inReplyTo":null,"subject":"[RFC/PATCH 0/4] cat-file --batch-disk-sizes","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-07T10:01:34Z","receivedAt":"2013-07-07T10:01:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When I work with alternates repositories that have the objects for many\nindividual forks inter-mixed, one of the questions I want to ask git is\nhow much space particular forks are taking up in the object database.\nThis is easy enough to script with `rev-list --objects $fork1 --not\n$fork2`, as long as you can convert the object names into their on-disk\nsizes.\n\nUnfortunately, it's hard to get the on-disk object sizes for packs. You\ncan do it directly with `verify-pack -v`, which is incredibly slow. Or\nyou can sort and subtract offsets from the output of `show-index` (i.e.,\nthe same thing the pack-revindex code does internally). Instead, this\npatch series exposes the revindex-generated sizes on the command line.\n\nThe fourth patch does not need to be built on top of this series, but\nthe early parts provide a convenient way to measure the revindex code.\n\n [1/4]: zero-initialize object_info structs\n [2/4]: teach sha1_object_info_extended a \"disk_size\" query\n [3/4]: cat-file: add --batch-disk-sizes option\n [4/4]: pack-revindex: radix-sort the revindex\n\n-Peff\n"},{"id":"222734","messageId":"20130707100329.GA19143@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130707100133.GA18717@sigill.intra.peff.net","subject":"[PATCH 1/4] zero-initialize object_info structs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-07T10:03:29Z","receivedAt":"2013-07-07T10:03:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The sha1_object_info_extended function expects the caller to\nprovide a \"struct object_info\" which contains pointers to\n\"query\" items that will be filled in. The purpose of\nproviding pointers rather than storing the response directly\nin the struct is so that callers can choose not to incur the\nexpense in finding particular fields that they do not care\nabout.\n\nRight now the only query item is \"sizep\", and all callers\nset it explicitly to choose whether or not to query it; they\ncan then leave the rest of the struct uninitialized.\n\nHowever, as we add new query items, each caller will have to\nbe updated to explicitly turn off the new ones (by setting\nthem to NULL). Instead, let's teach each caller to\nzero-initialize the struct, so that they do not have to\nlearn about each new query item added.\n\nSigned-off-by: Jeff King \n---\nObviously I plan to add a new query type in the next patch, but this\ninitialization is probably a reasonable thing to be doing anyway.\n\n sha1_file.c | 2 +-\n streaming.c | 2 +-\n 2 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 0af19c0..de06a97 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2428,7 +2428,7 @@ int sha1_object_info(const unsigned char *sha1, unsigned long *sizep)\n \n int sha1_object_info(const unsigned char *sha1, unsigned long *sizep)\n {\n-\tstruct object_info oi;\n+\tstruct object_info oi = {0};\n \n \toi.sizep = sizep;\n \treturn sha1_object_info_extended(sha1, &oi);\ndiff --git a/streaming.c b/streaming.c\nindex cabcd9d..cac282f 100644\n--- a/streaming.c\n+++ b/streaming.c\n@@ -135,7 +135,7 @@ struct git_istream *open_istream(const unsigned char *sha1,\n \t\t\t\t struct stream_filter *filter)\n {\n \tstruct git_istream *st;\n-\tstruct object_info oi;\n+\tstruct object_info oi = {0};\n \tconst unsigned char *real = lookup_replace_object(sha1);\n \tenum input_source src = istream_source(real, type, &oi);\n \n-- \n1.8.3.rc3.24.gec82cb9\n"},{"id":"222735","messageId":"20130707100400.GB19143@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130707100133.GA18717@sigill.intra.peff.net","subject":"[PATCH 2/4] teach sha1_object_info_extended a \"disk_size\" query","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-07T10:04:00Z","receivedAt":"2013-07-07T10:04:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Using sha1_object_info_extended, a caller can find out the\ntype of an object, its size, and information about where it\nis stored. In addition to the object's \"true\" size, it can\nalso be useful to know the size that the object takes on\ndisk (e.g., to generate statistics about which refs consume\nspace).\n\nThis patch adds a \"disk_sizep\" field to \"struct object_info\",\nand fills it in during sha1_object_info_extended if it is\nnon-NULL.\n\nSigned-off-by: Jeff King \n---\n cache.h | 1 +\n sha1_file.c | 20 ++++++++++++++++----\n 2 files changed, 17 insertions(+), 4 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex dd0fb33..2d06169 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1130,6 +1130,7 @@ struct object_info {\n struct object_info {\n \t/* Request */\n \tunsigned long *sizep;\n+\tunsigned long *disk_sizep;\n \n \t/* Response */\n \tenum {\ndiff --git a/sha1_file.c b/sha1_file.c\nindex de06a97..4c2365f 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1697,7 +1697,8 @@ static int packed_object_info(struct packed_git *p, off_t obj_offset,\n #define POI_STACK_PREALLOC 64\n \n static int packed_object_info(struct packed_git *p, off_t obj_offset,\n-\t\t\t unsigned long *sizep, int *rtype)\n+\t\t\t unsigned long *sizep, int *rtype,\n+\t\t\t unsigned long *disk_sizep)\n {\n \tstruct pack_window *w_curs = NULL;\n \tunsigned long size;\n@@ -1731,6 +1732,11 @@ static int packed_object_info(struct packed_git *p, off_t obj_offset,\n \t\t}\n \t}\n \n+\tif (disk_sizep) {\n+\t\tstruct revindex_entry *revidx = find_pack_revindex(p, obj_offset);\n+\t\t*disk_sizep = revidx[1].offset - obj_offset;\n+\t}\n+\n \twhile (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {\n \t\toff_t base_offset;\n \t\t/* Push the object we're going to leave behind */\n@@ -2357,7 +2363,8 @@ struct packed_git *find_sha1_pack(const unsigned char *sha1,\n \n }\n \n-static int sha1_loose_object_info(const unsigned char *sha1, unsigned long *sizep)\n+static int sha1_loose_object_info(const unsigned char *sha1, unsigned long *sizep,\n+\t\t\t\t unsigned long *disk_sizep)\n {\n \tint status;\n \tunsigned long mapsize, size;\n@@ -2368,6 +2375,8 @@ static int sha1_loose_object_info(const unsigned char *sha1, unsigned long *size\n \tmap = map_sha1_file(sha1, &mapsize);\n \tif (!map)\n \t\treturn -1;\n+\tif (disk_sizep)\n+\t\t*disk_sizep = mapsize;\n \tif (unpack_sha1_header(&stream, map, mapsize, hdr, sizeof(hdr)) < 0)\n \t\tstatus = error(\"unable to unpack %s header\",\n \t\t\t sha1_to_hex(sha1));\n@@ -2391,13 +2400,15 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi)\n \tif (co) {\n \t\tif (oi->sizep)\n \t\t\t*(oi->sizep) = co->size;\n+\t\tif (oi->disk_sizep)\n+\t\t\t*(oi->disk_sizep) = 0;\n \t\toi->whence = OI_CACHED;\n \t\treturn co->type;\n \t}\n \n \tif (!find_pack_entry(sha1, &e)) {\n \t\t/* Most likely it's a loose object. */\n-\t\tstatus = sha1_loose_object_info(sha1, oi->sizep);\n+\t\tstatus = sha1_loose_object_info(sha1, oi->sizep, oi->disk_sizep);\n \t\tif (status >= 0) {\n \t\t\toi->whence = OI_LOOSE;\n \t\t\treturn status;\n@@ -2409,7 +2420,8 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi)\n \t\t\treturn status;\n \t}\n \n-\tstatus = packed_object_info(e.p, e.offset, oi->sizep, &rtype);\n+\tstatus = packed_object_info(e.p, e.offset, oi->sizep, &rtype,\n+\t\t\t\t oi->disk_sizep);\n \tif (status < 0) {\n \t\tmark_bad_packed_object(e.p, sha1);\n \t\tstatus = sha1_object_info_extended(sha1, oi);\n-- \n1.8.3.rc3.24.gec82cb9\n"},{"id":"222736","messageId":"20130707100949.GC19143@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130707100133.GA18717@sigill.intra.peff.net","subject":"[PATCH 3/4] cat-file: add --batch-disk-sizes option","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-07T10:09:49Z","receivedAt":"2013-07-07T10:09:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This option is just like --batch-check, but shows the\non-disk size rather than the true object size. In other\nwords, it makes the \"disk_size\" query of sha1_object_info_extended\navailable via the command-line.\n\nThis can be used for rough attribution of disk usage to\nparticular refs, though see the caveats in the\ndocumentation.\n\nThis patch does not include any tests, as the exact numbers\nreturned are volatile and subject to zlib and packing\ndecisions.\n\nSigned-off-by: Jeff King \n---\nI sort of tacked this onto the --batch-check format by replacing the\n\"real\" object size with the on-disk size when this option is used. I'm\nopen to suggestions. Two other things I considered were:\n\n 1. Having the option simply output an extra field with the on-disk\n size. But then you are paying for the true object size lookup, even\n if you don't necessarily care.\n\n 2. Simply outputting the disk-size and object name. For my purposes, I\n do not care about the object type, and finding the type takes non-trivial\n resources (we have to walk delta chains to find the true type).\n\nPerhaps we need\n\n git cat-file --batch-format=\"%(disk-size) %(object)\"\n\nor similar.\n\n Documentation/git-cat-file.txt | 16 ++++++++++++++++\n builtin/cat-file.c | 9 +++++++++\n 2 files changed, 25 insertions(+)\n\ndiff --git a/Documentation/git-cat-file.txt b/Documentation/git-cat-file.txt\nindex 30d585a..d4af1fc 100644\n--- a/Documentation/git-cat-file.txt\n+++ b/Documentation/git-cat-file.txt\n@@ -65,6 +65,22 @@ OPTIONS\n \tPrint the SHA-1, type, and size of each object provided on stdin. May not\n \tbe combined with any other options or arguments.\n \n+--batch-disk-sizes::\n+\tLike `--batch-check`, but print the on-disk size of each object\n+\t(including zlib and delta compression) rather than the object's\n+\ttrue size. May not be combined with any other options or\n+\targuments.\n++\n+NOTE: The on-disk size reported is accurate, but care should be taken in\n+drawing conclusions about which refs or objects are responsible for disk\n+usage. The size of a packed non-delta object be much larger than the\n+size of objects which delta against it, but the choice of which object\n+is the base and which is the delta is arbitrary and is subject to change\n+during a repack. Note also that multiple copies of an object may be\n+present in the object database; in this case, it is undefined which\n+copy's size will be reported.\n+\n+\n OUTPUT\n ------\n If '-t' is specified, one of the .\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 045cee7..5112c64 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -15,6 +15,7 @@\n \n #define BATCH 1\n #define BATCH_CHECK 2\n+#define BATCH_DISK_SIZES 3\n \n static int cat_one_file(int opt, const char *exp_type, const char *obj_name)\n {\n@@ -135,6 +136,11 @@ static int batch_one_object(const char *obj_name, int print_contents)\n \n \tif (print_contents == BATCH)\n \t\tcontents = read_sha1_file(sha1, &type, &size);\n+\telse if (print_contents == BATCH_DISK_SIZES) {\n+\t\tstruct object_info oi = {0};\n+\t\toi.disk_sizep = &size;\n+\t\ttype = sha1_object_info_extended(sha1, &oi);\n+\t}\n \telse\n \t\ttype = sha1_object_info(sha1, &size);\n \n@@ -206,6 +212,9 @@ int cmd_cat_file(int argc, const char **argv, const char *prefix)\n \t\tOPT_SET_INT(0, \"batch-check\", &batch,\n \t\t\t N_(\"show info about objects fed from the standard input\"),\n \t\t\t BATCH_CHECK),\n+\t\tOPT_SET_INT(0, \"batch-disk-sizes\", &batch,\n+\t\t\t N_(\"show on-disk size of objects fed from standard input\"),\n+\t\t\t BATCH_DISK_SIZES),\n \t\tOPT_END()\n \t};\n \n-- \n1.8.3.rc3.24.gec82cb9\n"},{"id":"222737","messageId":"20130707101438.GD19143@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130707100133.GA18717@sigill.intra.peff.net","subject":"[PATCH 4/4] pack-revindex: radix-sort the revindex","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-07T10:14:39Z","receivedAt":"2013-07-07T10:14:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The pack revindex stores the offsets of the objects in the\npack in sorted order, allowing us to easily find the on-disk\nsize of each object. To compute it, we populate an array\nwith the offsets from the sha1-sorted idx file, and then use\nqsort to order it by offsets.\n\nThat does O(n log n) offset comparisons, and profiling shows\nthat we spend most of our time in cmp_offset. However, since\nwe are sorting on a simple off_t, we can use numeric sorts\nthat perform better. A radix sort can run in O(k*n), where k\nis the number of \"digits\" in our number. For a 64-bit off_t,\nusing 16-bit \"digits\" gives us k=4.\n\nOn the linux.git repo, with about 3M objects to sort, this\nyields a 400% speedup. Here are the best-of-five numbers for\nrunning \"echo HEAD | git cat-file --batch-disk-size\", which\nis dominated by time spent building the pack revindex:\n\n before after\n real 0m0.834s 0m0.204s\n user 0m0.788s 0m0.164s\n sys 0m0.040s 0m0.036s\n\nOn a smaller repo, the radix sort would not be\nas impressive (and could even be worse), as we are trading\nthe log(n) factor for the k=4 of the radix sort. However,\neven on git.git, with 173K objects, it shows some\nimprovement:\n\n before after\n real 0m0.046s 0m0.017s\n user 0m0.036s 0m0.012s\n sys 0m0.008s 0m0.000s\n\nSigned-off-by: Jeff King \n---\nI think there are probably still two potential issues here:\n\n 1. My while() loop termination probably has issues when we have to use\n all 64 bits to represent the pack offset (not likely, but...)\n\n 2. We put \"int pos[65536]\" on the stack. This is a little big, but is\n probably OK, as I think the usual small stack problems we have seen\n are always in threaded code. But it would not be a big deal to heap\n allocate it (it would happen once per radix step, which is only 4\n times for the whole sort).\n\n pack-revindex.c | 77 +++++++++++++++++++++++++++++++++++++++++++++++++++++----\n 1 file changed, 72 insertions(+), 5 deletions(-)\n\ndiff --git a/pack-revindex.c b/pack-revindex.c\nindex 77a0465..d2adf36 100644\n--- a/pack-revindex.c\n+++ b/pack-revindex.c\n@@ -59,11 +59,78 @@ static int cmp_offset(const void *a_, const void *b_)\n \t/* revindex elements are lazily initialized */\n }\n \n-static int cmp_offset(const void *a_, const void *b_)\n+/*\n+ * This is a least-significant-digit radix sort using a 16-bit \"digit\".\n+ */\n+static void sort_revindex(struct revindex_entry *entries, int n, off_t max)\n {\n-\tconst struct revindex_entry *a = a_;\n-\tconst struct revindex_entry *b = b_;\n-\treturn (a->offset < b->offset) ? -1 : (a->offset > b->offset) ? 1 : 0;\n+\t/*\n+\t * We need O(n) temporary storage, so we sort back and forth between\n+\t * the real array and our tmp storage. To keep them straight, we always\n+\t * sort from \"a\" into buckets in \"b\".\n+\t */\n+\tstruct revindex_entry *tmp = xcalloc(n, sizeof(*tmp));\n+\tstruct revindex_entry *a = entries, *b = tmp;\n+\tint digits = 0;\n+\n+\t/*\n+\t * We want to know the bucket that a[i] will go into when we are using\n+\t * the digit that is N bits from the (least significant) end.\n+\t */\n+#define BUCKET_FOR(a, i, digits) ((a[i].offset >> digits) & 0xffff)\n+\n+\twhile (max / (((off_t)1) << digits)) {\n+\t\tstruct revindex_entry *swap;\n+\t\tint i;\n+\t\tint pos[65536] = {0};\n+\n+\t\t/*\n+\t\t * We want pos[i] to store the index of the last element that\n+\t\t * will go in bucket \"i\" (actually one past the last element).\n+\t\t * To do this, we first count the items that will go in each\n+\t\t * bucket, which gives us a relative offset from the last\n+\t\t * bucket. We can then cumulatively add the index from the\n+\t\t * previous bucket to get the true index.\n+\t\t */\n+\t\tfor (i = 0; i < n; i++)\n+\t\t\tpos[BUCKET_FOR(a, i, digits)]++;\n+\t\tfor (i = 1; i < ARRAY_SIZE(pos); i++)\n+\t\t\tpos[i] += pos[i-1];\n+\n+\t\t/*\n+\t\t * Now we can drop the elements into their correct buckets (in\n+\t\t * our temporary array). We iterate the pos counter backwards\n+\t\t * to avoid using an extra index to count up. And since we are\n+\t\t * going backwards there, we must also go backwards through the\n+\t\t * array itself, to keep the sort stable.\n+\t\t */\n+\t\tfor (i = n - 1; i >= 0; i--)\n+\t\t\tb[--pos[BUCKET_FOR(a, i, digits)]] = a[i];\n+\n+\t\t/*\n+\t\t * Now \"b\" contains the most sorted list, so we swap \"a\" and\n+\t\t * \"b\" for the next iteration.\n+\t\t */\n+\t\tswap = a;\n+\t\ta = b;\n+\t\tb = swap;\n+\n+\t\t/* And bump our digits for the next round. */\n+\t\tdigits += 16;\n+\t}\n+\n+\t/*\n+\t * If we ended with our data in the original array, great. If not,\n+\t * we have to move it back from the temporary storage.\n+\t */\n+\tif (a != entries) {\n+\t\tint i;\n+\t\tfor (i = 0; i < n; i++)\n+\t\t\tentries[i] = tmp[i];\n+\t}\n+\tfree(tmp);\n+\n+#undef BUCKET_FOR\n }\n \n /*\n@@ -108,7 +175,7 @@ static void create_pack_revindex(struct pack_revindex *rix)\n \t */\n \trix->revindex[num_ent].offset = p->pack_size - 20;\n \trix->revindex[num_ent].nr = -1;\n-\tqsort(rix->revindex, num_ent, sizeof(*rix->revindex), cmp_offset);\n+\tsort_revindex(rix->revindex, num_ent, p->pack_size);\n }\n \n struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs)\n-- \n1.8.3.rc3.24.gec82cb9\n"},{"id":"222753","messageId":"7vy59i46lh.fsf@alter.siamese.dyndns.org","threadId":"34369","inReplyTo":"20130707100329.GA19143@sigill.intra.peff.net","subject":"Re: [PATCH 1/4] zero-initialize object_info structs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-07-07T17:34:18Z","receivedAt":"2013-07-07T17:34:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Obviously I plan to add a new query type in the next patch, but this\n> initialization is probably a reasonable thing to be doing anyway.\n\nYes. Thanks.\n\n>\n> sha1_file.c | 2 +-\n> streaming.c | 2 +-\n> 2 files changed, 2 insertions(+), 2 deletions(-)\n>\n> diff --git a/sha1_file.c b/sha1_file.c\n> index 0af19c0..de06a97 100644\n> --- a/sha1_file.c\n> +++ b/sha1_file.c\n> @@ -2428,7 +2428,7 @@ int sha1_object_info(const unsigned char *sha1, unsigned long *sizep)\n> \n> int sha1_object_info(const unsigned char *sha1, unsigned long *sizep)\n> {\n> -\tstruct object_info oi;\n> +\tstruct object_info oi = {0};\n> \n> \toi.sizep = sizep;\n> \treturn sha1_object_info_extended(sha1, &oi);\n> diff --git a/streaming.c b/streaming.c\n> index cabcd9d..cac282f 100644\n> --- a/streaming.c\n> +++ b/streaming.c\n> @@ -135,7 +135,7 @@ struct git_istream *open_istream(const unsigned char *sha1,\n> \t\t\t\t struct stream_filter *filter)\n> {\n> \tstruct git_istream *st;\n> -\tstruct object_info oi;\n> +\tstruct object_info oi = {0};\n> \tconst unsigned char *real = lookup_replace_object(sha1);\n> \tenum input_source src = istream_source(real, type, &oi);\n"},{"id":"222755","messageId":"7vtxk645vp.fsf@alter.siamese.dyndns.org","threadId":"34369","inReplyTo":"20130707100949.GC19143@sigill.intra.peff.net","subject":"Re: [PATCH 3/4] cat-file: add --batch-disk-sizes option","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-07-07T17:49:46Z","receivedAt":"2013-07-07T17:49:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Perhaps we need\n>\n> git cat-file --batch-format=\"%(disk-size) %(object)\"\n>\n> or similar.\n\nI agree with your reasoning. It may be simpler to give an interface\nto ask for which pieces of info, e.g. --batch-cols=size,disksize,\nwithout giving the readers a flexible \"format\".\n\n> +NOTE: The on-disk size reported is accurate, but care should be taken in\n> +drawing conclusions about which refs or objects are responsible for disk\n> +usage. The size of a packed non-delta object be much larger than the\n> +size of objects which delta against it, but the choice of which object\n> +is the base and which is the delta is arbitrary and is subject to change\n> +during a repack. Note also that multiple copies of an object may be\n> +present in the object database; in this case, it is undefined which\n> +copy's size will be reported.\n\nThis is a good note to leave to the readers. I was wondering how\nvalid to accuse that B is taking a lot of space compared to C when\nyou have three objects A, B and C (in decreasing order of on-disk\nfootprint) when A is huge and C is a small delta against A and B is\nindependent. The role of A and C in their delta chain could easily\nbe swapped during the next full repack and then C will appear a lot\nlarger than B.\n\nIt might be interesting to measure the total disk footprint of an\nentire delta \"family\" (the objects that delta against the same\nbase). You may find out that hello.c with a manageable size have\nvery many revisions and overall have a larger on-disk footprint than\na single copy of unchanging help.mov clip used in the documentation\ndoes, which may be an interesting observation to make.\n"},{"id":"222765","messageId":"20130707181925.GA20085@sigill.intra.peff.net","threadId":"34369","inReplyTo":"7vtxk645vp.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/4] cat-file: add --batch-disk-sizes option","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-07T18:19:25Z","receivedAt":"2013-07-07T18:19:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jul 07, 2013 at 10:49:46AM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > Perhaps we need\n> >\n> > git cat-file --batch-format=\"%(disk-size) %(object)\"\n> >\n> > or similar.\n> \n> I agree with your reasoning. It may be simpler to give an interface\n> to ask for which pieces of info, e.g. --batch-cols=size,disksize,\n> without giving the readers a flexible \"format\".\n\nYeah, that is probably a lot more sane. That would be sufficient for my\nuse, I doubt anyone really wants the full format, and it would be easy\nto add it later if we are wrong. It would also be easy to add other\nitems from the sha1_object_info_extended list, too (e.g.,\nloose/cached/packed).\n\nI'll do that in my re-roll.\n\n> > +NOTE: The on-disk size reported is accurate, but care should be taken in\n> > +drawing conclusions about which refs or objects are responsible for disk\n> > +usage. [...]\n> \n> This is a good note to leave to the readers. I was wondering how\n> valid to accuse that B is taking a lot of space compared to C when\n> you have three objects A, B and C (in decreasing order of on-disk\n> footprint) when A is huge and C is a small delta against A and B is\n> independent. The role of A and C in their delta chain could easily\n> be swapped during the next full repack and then C will appear a lot\n> larger than B.\n\nYeah. I exercise a lot of human analysis when I use this tool myself.\nWhat I am usually looking for is that somebody has forked a 100M repo,\nand then dumped 2G of extra data on top. Those cases are not all that\nhard to spot, and would not usually change too much in a repack.\n\n> It might be interesting to measure the total disk footprint of an\n> entire delta \"family\" (the objects that delta against the same\n> base). You may find out that hello.c with a manageable size have\n> very many revisions and overall have a larger on-disk footprint than\n> a single copy of unchanging help.mov clip used in the documentation\n> does, which may be an interesting observation to make.\n\nYeah, that is an interesting stat, though I have not had a need for it\nmyself. Certainly you could do:\n\n git rev-list --objects --all |\n grep ' hello.c$' |\n cut -d' ' -f1 |\n git cat-file --batch-disk-sizes\n\nto see hello.c's size. But I cannot think offhand of a way to get the\nlist of objects that are in a delta chain together (potentially crossing\npath boundaries), short of parsing verfiy-pack output myself. I think it\nis orthogonal to this patch, though. This exposes more information about\nobjects themselves; it would be up to another patch to help discover and\nnarrow the list of interesting objects.\n\n-Peff\n"},{"id":"222777","messageId":"20130707211538.GB6478@vauxhall.crustytoothpaste.net","threadId":"34369","inReplyTo":"20130707100949.GC19143@sigill.intra.peff.net","subject":"Re: [PATCH 3/4] cat-file: add --batch-disk-sizes option","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2013-07-07T21:15:41Z","receivedAt":"2013-07-07T21:15:41Z","isPatch":true,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On Sun, Jul 07, 2013 at 06:09:49AM -0400, Jeff King wrote:\n> +NOTE: The on-disk size reported is accurate, but care should be taken in\n> +drawing conclusions about which refs or objects are responsible for disk\n> +usage. The size of a packed non-delta object be much larger than the\n\nYou probably meant \"may be\" here. ^\n\n-- \nbrian m. carlson / brian with sandals: Houston, Texas, US\n+1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only\nOpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187\n"},{"id":"222789","messageId":"CAJo=hJugvqBEQwPYcttNH+R8xUKxy1uDm5EjiWaye-wEuTxk-w@mail.gmail.com","threadId":"34369","inReplyTo":"20130707101438.GD19143@sigill.intra.peff.net","subject":"Re: [PATCH 4/4] pack-revindex: radix-sort the revindex","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2013-07-07T23:52:23Z","receivedAt":"2013-07-07T23:52:23Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sun, Jul 7, 2013 at 3:14 AM, Jeff King wrote:\n> The pack revindex stores the offsets of the objects in the\n> pack in sorted order, allowing us to easily find the on-disk\n> size of each object. To compute it, we populate an array\n> with the offsets from the sha1-sorted idx file, and then use\n> qsort to order it by offsets.\n>\n> That does O(n log n) offset comparisons, and profiling shows\n> that we spend most of our time in cmp_offset. However, since\n> we are sorting on a simple off_t, we can use numeric sorts\n> that perform better. A radix sort can run in O(k*n), where k\n> is the number of \"digits\" in our number. For a 64-bit off_t,\n> using 16-bit \"digits\" gives us k=4.\n\nDid you try the simple bucket sort Colby now uses in JGit?\n\nThe sort is pretty simple:\n\n bucket_size = pack_length / object_count;\n buckets[] = malloc(object_count * sizeof(int));\n\n foreach obj in idx:\n push_chain(buckets[obj.offset / bucket_size], obj.idx_nth);\n\n foreach bucket:\n insertion sort by offset\n\nhttps://eclipse.googlesource.com/jgit/jgit/+/master/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackReverseIndex.java\n\nWe observed on linux.git that most buckets have an average number of\nobjects. IIRC the bucket_size was ~201 bytes and most buckets had very\nfew objects each. For lookups we keep the bucket_size parameter and a\nbucket index table. This arrangement uses 8 bytes per object in the\nreverse index, making it very memory efficient. Searches are typically\nbelow O(log N) time because each bucket has On Sun, Jul 7, 2013 at 3:14 AM, Jeff King wrote:\n> > The pack revindex stores the offsets of the objects in the\n> > pack in sorted order, allowing us to easily find the on-disk\n> > size of each object. To compute it, we populate an array\n> > with the offsets from the sha1-sorted idx file, and then use\n> > qsort to order it by offsets.\n> >\n> > That does O(n log n) offset comparisons, and profiling shows\n> > that we spend most of our time in cmp_offset. However, since\n> > we are sorting on a simple off_t, we can use numeric sorts\n> > that perform better. A radix sort can run in O(k*n), where k\n> > is the number of \"digits\" in our number. For a 64-bit off_t,\n> > using 16-bit \"digits\" gives us k=4.\n> \n> Did you try the simple bucket sort Colby now uses in JGit?\n> \n> The sort is pretty simple:\n> \n> bucket_size = pack_length / object_count;\n> buckets[] = malloc(object_count * sizeof(int));\n> \n> foreach obj in idx:\n> push_chain(buckets[obj.offset / bucket_size], obj.idx_nth);\n> \n> foreach bucket:\n> insertion sort by offset\n\nI did do something similar (though I flattened my buckets into a single\nlist afterwards), but I ended up closer to 700ms (down from 830ms, but\nwith the radix sort around 200ms). It's entirely possible I screwed up\nsomething in the implementation (the bucket insertion can be done in a\nlot of different ways, many of which are terrible), but I didn't keep a\ncopy of that attempt. If you try it and have better numbers, I'd be\nhappy to see them.\n\n> We observed on linux.git that most buckets have an average number of\n> objects. IIRC the bucket_size was ~201 bytes and most buckets had very\n> few objects each. For lookups we keep the bucket_size parameter and a\n> bucket index table. This arrangement uses 8 bytes per object in the\n> reverse index, making it very memory efficient. Searches are typically\n> below O(log N) time because each bucket has wrote:\n> Jeff King writes:\n>\n>> Perhaps we need\n>>\n>> git cat-file --batch-format=\"%(disk-size) %(object)\"\n>>\n>> or similar.\n\nThis is what I wanted to do with the in for-each-ref's pretty\nformatting [1]. I used to hack cat-file --batch to extract info I\nneeded for experimenting with various pack index extensions. If you\nare not in hurry, maybe we can introduce something similar to your\nsyntax, but applicable for all for-each-ref, branch and log family.\nRam, are you still interested in the awesome branch series?\n\n> I agree with your reasoning. It may be simpler to give an interface\n> to ask for which pieces of info, e.g. --batch-cols=size,disksize,\n> without giving the readers a flexible \"format\".\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/227057/focus=227223\n--\nDuy\n"},{"id":"222812","messageId":"CALkWK0ktNK49zBM4tD8fpNN3VMan7DegfWRtDcOEgTyEbSK9Uw@mail.gmail.com","threadId":"34369","inReplyTo":"CACsJy8A8ZO3DL8Vr=S1G-3yiJz3WaZ-7jV_eA+v6rPAWrd9NAw@mail.gmail.com","subject":"Re: [PATCH 3/4] cat-file: add --batch-disk-sizes option","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-07-08T12:00:21Z","receivedAt":"2013-07-08T12:00:21Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Duy Nguyen wrote:\n> Ram, are you still interested in the awesome branch series?\n\nYep, but it got stalled due to lack of reviewer-interest :/\n\nI'm a bit under the weather at the moment, but it's good to see that\nyou're back: let's finish this soon.\n\n>>> Perhaps we need\n>>>\n>>> git cat-file --batch-format=\"%(disk-size) %(object)\"\n>>>\n>>> or similar.\n>\n> This is what I wanted to do with the in for-each-ref's pretty\n> formatting [1]. I used to hack cat-file --batch to extract info I\n> needed for experimenting with various pack index extensions. If you\n> are not in hurry, maybe we can introduce something similar to your\n> syntax, but applicable for all for-each-ref, branch and log family.\n\nI'm still quite confused about this \"grand plan\". We have short\ncommit-specific format specifiers that don't work with refs, among\nseveral other quirks in [1]. I personally think we should absolutely\nstay away from short format-specifiers (like %H, %f, %e; we'll soon\nrun out of letters, and nobody can tell what they are without the\ndocumentation anyway) for the new options, and just start adding new\nlong-form ones as and when they are necessary. I think refname:short,\nupstream:track, upstream:trackshort are very sensible choices, and\nthat we should continue along that line. I'm fine with\nformat-specifiers having meanings only in certain contexts as long as\nwe document it properly (how can we possibly get %(refname) to mean\nsomething sensible in cat-file?).\n\nAs far as this series is concerned, I think Peff can implement %H and\n%(object:[disk-]size) locally without worrying about code-sharing or\nwaiting for us. Then, after the for-each-ref-pretty thing matures, we\ncan just replace the code underneath.\n"},{"id":"222819","messageId":"CACsJy8Dffc2WgtDyUS2g2gmDWG_rTxs389fHcj0ztm6pdJddjQ@mail.gmail.com","threadId":"34369","inReplyTo":"CALkWK0ktNK49zBM4tD8fpNN3VMan7DegfWRtDcOEgTyEbSK9Uw@mail.gmail.com","subject":"Re: [PATCH 3/4] cat-file: add --batch-disk-sizes option","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-07-08T13:13:18Z","receivedAt":"2013-07-08T13:13:18Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Jul 8, 2013 at 7:00 PM, Ramkumar Ramachandra wrote:\n>> This is what I wanted to do with the in for-each-ref's pretty\n>> formatting [1]. I used to hack cat-file --batch to extract info I\n>> needed for experimenting with various pack index extensions. If you\n>> are not in hurry, maybe we can introduce something similar to your\n>> syntax, but applicable for all for-each-ref, branch and log family.\n>\n> I'm still quite confused about this \"grand plan\". We have short\n> commit-specific format specifiers that don't work with refs, among\n> several other quirks in [1]. I personally think we should absolutely\n> stay away from short format-specifiers (like %H, %f, %e; we'll soon\n> run out of letters, and nobody can tell what they are without the\n> documentation anyway) for the new options, and just start adding new\n> long-form ones as and when they are necessary. I think refname:short,\n> upstream:track, upstream:trackshort are very sensible choices, and\n> that we should continue along that line. I'm fine with\n> format-specifiers having meanings only in certain contexts as long as\n> we document it properly (how can we possibly get %(refname) to mean\n> something sensible in cat-file?).\n\nThe short/long naming is the least I worry about. We could add long\nnames to pretty specifiers. The thing about the last attempt is, you\nadd some extra things on top elsewhere, but format_commit_item code\nmay need to be aware of those changes, which are not obvious when\nsombody just focuses on format_commit_item. Having all specifiers in\none place would be better (hence no hooks, no callbacks) because we\nget a full picture. And yes we need to deal with specifers that make\nno sense in certain context.\n\nAll that makes changes bigger, but when format_commit_item (now just\n\"format_item\") knows how to deal with all kinds of objects and refs,\nit becomes a small declaration language to extract things out of git.\nYou can use it for pretty printing or mass extraction in the case of\n\"cat-file --batch\". \"cat-file --batch\" is just some bonus on top,\nmostly to exercise that we do it right.\n\n> As far as this series is concerned, I think Peff can implement %H and\n> %(object:[disk-]size) locally without worrying about code-sharing or\n> waiting for us. Then, after the for-each-ref-pretty thing matures, we\n> can just replace the code underneath.\n\nThere's also syntax sharing. I don't think each command should have\nits own syntax. f-e-r already has %(objectsize). If we plan to have a\ncommon syntax, perhaps %(disk-size) should be %(objectsize:disk) or\nsomething. Adding formatting to cat-file --batch from scratch could be\nanother big chunk of code (that also comes with bugs, usually) and may\nor may not be compatible with the common syntax because of some\noversight. --batch-cols=... or --batch-disk-size would be simpler, but\nwe might never be able to remove that code.\n--\nDuy\n"},{"id":"222823","messageId":"CALkWK0k0xiNFaFmqL2t4ba2g+HSrQ8kU+W_HvnSMcMYY8VgJyg@mail.gmail.com","threadId":"34369","inReplyTo":"CACsJy8Dffc2WgtDyUS2g2gmDWG_rTxs389fHcj0ztm6pdJddjQ@mail.gmail.com","subject":"Re: [PATCH 3/4] cat-file: add --batch-disk-sizes option","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-07-08T13:37:01Z","receivedAt":"2013-07-08T13:37:01Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Duy Nguyen wrote:\n> The short/long naming is the least I worry about. We could add long\n> names to pretty specifiers. The thing about the last attempt is, you\n> add some extra things on top elsewhere, but format_commit_item code\n> may need to be aware of those changes, which are not obvious when\n> sombody just focuses on format_commit_item. Having all specifiers in\n> one place would be better (hence no hooks, no callbacks) because we\n> get a full picture. And yes we need to deal with specifers that make\n> no sense in certain context.\n\nYeah, it would certainly be nice to have all the format-specifiers\nthat one unified parser acts on, but isn't this just a matter of\nrefactoring? Shouldn't we be starting with cheap callbacks, get\nthings working, and guard against regressions in the refactoring phase\nfirst? How else do you propose to start out?\n\n> There's also syntax sharing. I don't think each command should have\n> its own syntax. f-e-r already has %(objectsize). If we plan to have a\n> common syntax, perhaps %(disk-size) should be %(objectsize:disk) or\n> something.\n\nOfcourse. I didn't notice %(objectsize); %(objectsize[:disk]) is a\nfine suggestion.\n\n> Adding formatting to cat-file --batch from scratch could be\n> another big chunk of code (that also comes with bugs, usually) and may\n> or may not be compatible with the common syntax because of some\n> oversight.\n\nOh, I'm proposing that Peff implements just %H and\n%(objectsize[:disk]) for _now_, because that's what he wants. It\nshould be a tiny 20-line parser that's easy to swap out.\n\n> --batch-cols=... or --batch-disk-size would be simpler, but\n> we might never be able to remove that code.\n\nAgreed. The approach paints us into a design-corner, and must\ntherefore be avoided.\n"},{"id":"222838","messageId":"CAJo=hJt0R43TtGaSEegkC+aZvUJ7FAPFYzZ8fq-Tx1Pzp6Zi-A@mail.gmail.com","threadId":"34369","inReplyTo":"20130708075712.GC25072@sigill.intra.peff.net","subject":"Re: [PATCH 4/4] pack-revindex: radix-sort the revindex","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2013-07-08T15:38:44Z","receivedAt":"2013-07-08T15:38:44Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Jul 8, 2013 at 12:57 AM, Jeff King wrote:\n> On Sun, Jul 07, 2013 at 04:52:23PM -0700, Shawn O. Pearce wrote:\n>\n>> On Sun, Jul 7, 2013 at 3:14 AM, Jeff King wrote:\n>> > The pack revindex stores the offsets of the objects in the\n>> > pack in sorted order, allowing us to easily find the on-disk\n>> > size of each object. To compute it, we populate an array\n>> > with the offsets from the sha1-sorted idx file, and then use\n>> > qsort to order it by offsets.\n>> >\n>> > That does O(n log n) offset comparisons, and profiling shows\n>> > that we spend most of our time in cmp_offset. However, since\n>> > we are sorting on a simple off_t, we can use numeric sorts\n>> > that perform better. A radix sort can run in O(k*n), where k\n>> > is the number of \"digits\" in our number. For a 64-bit off_t,\n>> > using 16-bit \"digits\" gives us k=4.\n>>\n>> Did you try the simple bucket sort Colby now uses in JGit?\n>>\n>> The sort is pretty simple:\n>>\n>> bucket_size = pack_length / object_count;\n>> buckets[] = malloc(object_count * sizeof(int));\n>>\n>> foreach obj in idx:\n>> push_chain(buckets[obj.offset / bucket_size], obj.idx_nth);\n>>\n>> foreach bucket:\n>> insertion sort by offset\n>\n> I did do something similar (though I flattened my buckets into a single\n> list afterwards), but I ended up closer to 700ms (down from 830ms, but\n> with the radix sort around 200ms). It's entirely possible I screwed up\n> something in the implementation (the bucket insertion can be done in a\n> lot of different ways, many of which are terrible), but I didn't keep a\n> copy of that attempt. If you try it and have better numbers, I'd be\n> happy to see them.\n\nColby's sort in Java is coming in around 450ms for linux.git, so\nsounds like your implementation was doing something suboptimal.\n\nBut as I thought about it this morning, a radix sort for most pack\nfiles should run with k=2 and take only O(2*N) time. It is a very\nefficient sort for the data. Colby and I didn't even try a radix sort,\nand I suspect it would out-perform the bucket sort we do now.\n\n>> We observed on linux.git that most buckets have an average number of\n>> objects. IIRC the bucket_size was ~201 bytes and most buckets had very\n>> few objects each. For lookups we keep the bucket_size parameter and a\n>> bucket index table. This arrangement uses 8 bytes per object in the\n>> reverse index, making it very memory efficient. Searches are typically\n>> below O(log N) time because each bucket has \n> I didn't measure lookups at all; I was focused on time to build the\n> index. So if there were benefits there that make up for a longer setup\n> time, I wouldn't have measured them (of course, we also care about the\n> case with few lookups, so it would be a tradeoff).\n\nWe didn't measure lookup times either. Colby did compute a histogram\nof bucket sizes and showed nearly all buckets were significantly\nsmaller than log N, so lookups are You could also leave\n> each bucket unsorted and only lazily sort it when a lookup hits the\n> bucket, which might help that case (I didn't look to see if you do that\n> in JGit).\n\nWe didn't do that in JGit, the sort is done at initialization. But\ngiven the remark I just made about clones doing only a few lookups we\nmay want to defer the sort. IIRC the sort is about half of our\ninitialization cost.\n"},{"id":"222846","messageId":"7v61wl0zv1.fsf@alter.siamese.dyndns.org","threadId":"34369","inReplyTo":"CACsJy8Dffc2WgtDyUS2g2gmDWG_rTxs389fHcj0ztm6pdJddjQ@mail.gmail.com","subject":"Re: [PATCH 3/4] cat-file: add --batch-disk-sizes option","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-07-08T16:40:18Z","receivedAt":"2013-07-08T16:40:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen writes:\n\n> There's also syntax sharing. I don't think each command should have\n> its own syntax. f-e-r already has %(objectsize). If we plan to have a\n> common syntax, perhaps %(disk-size) should be %(objectsize:disk) or\n> something. Adding formatting to cat-file --batch from scratch could be\n> another big chunk of code (that also comes with bugs, usually) and may\n> or may not be compatible with the common syntax because of some\n> oversight. --batch-cols=... or --batch-disk-size would be simpler, but\n> we might never be able to remove that code.\n\nTrue, but cat-file being a low-level plumbing, I actually am not all\nthat convinced that it should even know the custom formatting.\nConfigurability and customizability may look always good, but that\nis true only until one realizes that they come with associated cost.\n"},{"id":"222860","messageId":"CA+sFfMfQcnx+OGNd+v7NJC5zSXg2OR1QiLyRSqDjXD0zb4mvtA@mail.gmail.com","threadId":"34369","inReplyTo":"20130707101438.GD19143@sigill.intra.peff.net","subject":"Re: [PATCH 4/4] pack-revindex: radix-sort the revindex","fromName":"Brandon Casey","fromEmail":"drafnel@gmail.com","sentAt":"2013-07-08T20:50:41Z","receivedAt":"2013-07-08T20:50:41Z","isPatch":true,"sender":{"key":"drafnel@gmail.com","avatar":"https://avatars.githubusercontent.com/u/921167?v=4"},"body":"On Sun, Jul 7, 2013 at 3:14 AM, Jeff King wrote:\n> The pack revindex stores the offsets of the objects in the\n> pack in sorted order, allowing us to easily find the on-disk\n> size of each object. To compute it, we populate an array\n> with the offsets from the sha1-sorted idx file, and then use\n> qsort to order it by offsets.\n>\n> That does O(n log n) offset comparisons, and profiling shows\n> that we spend most of our time in cmp_offset. However, since\n> we are sorting on a simple off_t, we can use numeric sorts\n> that perform better. A radix sort can run in O(k*n), where k\n> is the number of \"digits\" in our number. For a 64-bit off_t,\n> using 16-bit \"digits\" gives us k=4.\n>\n> On the linux.git repo, with about 3M objects to sort, this\n> yields a 400% speedup. Here are the best-of-five numbers for\n> running \"echo HEAD | git cat-file --batch-disk-size\", which\n> is dominated by time spent building the pack revindex:\n>\n> before after\n> real 0m0.834s 0m0.204s\n> user 0m0.788s 0m0.164s\n> sys 0m0.040s 0m0.036s\n>\n> On a smaller repo, the radix sort would not be\n> as impressive (and could even be worse), as we are trading\n> the log(n) factor for the k=4 of the radix sort. However,\n> even on git.git, with 173K objects, it shows some\n> improvement:\n>\n> before after\n> real 0m0.046s 0m0.017s\n> user 0m0.036s 0m0.012s\n> sys 0m0.008s 0m0.000s\n>\n> Signed-off-by: Jeff King \n> ---\n> I think there are probably still two potential issues here:\n>\n> 1. My while() loop termination probably has issues when we have to use\n> all 64 bits to represent the pack offset (not likely, but...)\n>\n> 2. We put \"int pos[65536]\" on the stack. This is a little big, but is\n> probably OK, as I think the usual small stack problems we have seen\n> are always in threaded code. But it would not be a big deal to heap\n> allocate it (it would happen once per radix step, which is only 4\n> times for the whole sort).\n>\n> pack-revindex.c | 77 +++++++++++++++++++++++++++++++++++++++++++++++++++++----\n> 1 file changed, 72 insertions(+), 5 deletions(-)\n>\n> diff --git a/pack-revindex.c b/pack-revindex.c\n> index 77a0465..d2adf36 100644\n> --- a/pack-revindex.c\n> +++ b/pack-revindex.c\n> @@ -59,11 +59,78 @@ static int cmp_offset(const void *a_, const void *b_)\n> /* revindex elements are lazily initialized */\n> }\n>\n> -static int cmp_offset(const void *a_, const void *b_)\n> +/*\n> + * This is a least-significant-digit radix sort using a 16-bit \"digit\".\n> + */\n> +static void sort_revindex(struct revindex_entry *entries, int n, off_t max)\n\nIf 'n' is the number of objects in the pack, shouldn't it be unsigned?\n\nThe data type for struct packed_git.num_objects is uint32_t. Looks\nlike create_pack_revindex uses the wrong datatype when it captures\nnum_objects in the int num_ent and passes it to sort_revindex. So, it\nlooks like that function needs to be updated too.\n\n> {\n> - const struct revindex_entry *a = a_;\n> - const struct revindex_entry *b = b_;\n> - return (a->offset < b->offset) ? -1 : (a->offset > b->offset) ? 1 : 0;\n> + /*\n> + * We need O(n) temporary storage, so we sort back and forth between\n> + * the real array and our tmp storage. To keep them straight, we always\n> + * sort from \"a\" into buckets in \"b\".\n> + */\n> + struct revindex_entry *tmp = xcalloc(n, sizeof(*tmp));\n> + struct revindex_entry *a = entries, *b = tmp;\n> + int digits = 0;\n> +\n> + /*\n> + * We want to know the bucket that a[i] will go into when we are using\n> + * the digit that is N bits from the (least significant) end.\n> + */\n> +#define BUCKET_FOR(a, i, digits) ((a[i].offset >> digits) & 0xffff)\n> +\n> + while (max / (((off_t)1) << digits)) {\n\nIs there any reason this shouldn't be simplified to just:\n\n while (max >> digits) {\n\nI glanced briefly at the assembly and it appears that gcc does\nactually emit a divide instruction to accomplish this, which I think\nwe can avoid by just rearranging the operation.\n\n> + struct revindex_entry *swap;\n> + int i;\n> + int pos[65536] = {0};\n> +\n> + /*\n> + * We want pos[i] to store the index of the last element that\n> + * will go in bucket \"i\" (actually one past the last element).\n> + * To do this, we first count the items that will go in each\n> + * bucket, which gives us a relative offset from the last\n> + * bucket. We can then cumulatively add the index from the\n> + * previous bucket to get the true index.\n> + */\n> + for (i = 0; i < n; i++)\n> + pos[BUCKET_FOR(a, i, digits)]++;\n> + for (i = 1; i < ARRAY_SIZE(pos); i++)\n> + pos[i] += pos[i-1];\n> +\n> + /*\n> + * Now we can drop the elements into their correct buckets (in\n> + * our temporary array). We iterate the pos counter backwards\n> + * to avoid using an extra index to count up. And since we are\n> + * going backwards there, we must also go backwards through the\n> + * array itself, to keep the sort stable.\n> + */\n> + for (i = n - 1; i >= 0; i--)\n> + b[--pos[BUCKET_FOR(a, i, digits)]] = a[i];\n> +\n> + /*\n> + * Now \"b\" contains the most sorted list, so we swap \"a\" and\n> + * \"b\" for the next iteration.\n> + */\n> + swap = a;\n> + a = b;\n> + b = swap;\n> +\n> + /* And bump our digits for the next round. */\n> + digits += 16;\n> + }\n> +\n> + /*\n> + * If we ended with our data in the original array, great. If not,\n> + * we have to move it back from the temporary storage.\n> + */\n> + if (a != entries) {\n> + int i;\n> + for (i = 0; i < n; i++)\n> + entries[i] = tmp[i];\n\nI think I recall that somebody investigated whether a for loop like\nyou have above was faster for copying structures than memcpy. I\nforget whether it was conclusive. Did you happen to compare them?\n\n\n\n-Brandon\n"},{"id":"222863","messageId":"CA+sFfMfHYkLc1rAnMKWGiGtH9kOC11D9CqpAsFXpeE_VBY0otA@mail.gmail.com","threadId":"34369","inReplyTo":"CA+sFfMfQcnx+OGNd+v7NJC5zSXg2OR1QiLyRSqDjXD0zb4mvtA@mail.gmail.com","subject":"Re: [PATCH 4/4] pack-revindex: radix-sort the revindex","fromName":"Brandon Casey","fromEmail":"drafnel@gmail.com","sentAt":"2013-07-08T21:35:10Z","receivedAt":"2013-07-08T21:35:10Z","isPatch":true,"sender":{"key":"drafnel@gmail.com","avatar":"https://avatars.githubusercontent.com/u/921167?v=4"},"body":"On Mon, Jul 8, 2013 at 1:50 PM, Brandon Casey wrote:\n> On Sun, Jul 7, 2013 at 3:14 AM, Jeff King wrote:\n\n>> diff --git a/pack-revindex.c b/pack-revindex.c\n>> index 77a0465..d2adf36 100644\n>> --- a/pack-revindex.c\n>> +++ b/pack-revindex.c\n>> @@ -59,11 +59,78 @@ static int cmp_offset(const void *a_, const void *b_)\n>> /* revindex elements are lazily initialized */\n>> }\n>>\n>> -static int cmp_offset(const void *a_, const void *b_)\n>> +/*\n>> + * This is a least-significant-digit radix sort using a 16-bit \"digit\".\n>> + */\n>> +static void sort_revindex(struct revindex_entry *entries, int n, off_t max)\n>\n> If 'n' is the number of objects in the pack, shouldn't it be unsigned?\n>\n> The data type for struct packed_git.num_objects is uint32_t. Looks\n> like create_pack_revindex uses the wrong datatype when it captures\n> num_objects in the int num_ent and passes it to sort_revindex. So, it\n> looks like that function needs to be updated too.\n\nHmm. It seems more than just create_pack_revindex holds num_objects\nin a signed int. Don't we support 4G objects in packs?\n\nfind_pack_revindex uses a signed int for the index variables in its\nbinary search which means it will fail when num_objects >= 2^31.\n\n-Brandon\n"},{"id":"222871","messageId":"CACsJy8B0E-jM+HHuhJD0fdZL2rat3ctDbSrCPo990WPnDA17RQ@mail.gmail.com","threadId":"34369","inReplyTo":"CALkWK0k0xiNFaFmqL2t4ba2g+HSrQ8kU+W_HvnSMcMYY8VgJyg@mail.gmail.com","subject":"Re: [PATCH 3/4] cat-file: add --batch-disk-sizes option","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-07-09T02:55:31Z","receivedAt":"2013-07-09T02:55:31Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Jul 8, 2013 at 8:37 PM, Ramkumar Ramachandra wrote:\n> Duy Nguyen wrote:\n>> The short/long naming is the least I worry about. We could add long\n>> names to pretty specifiers. The thing about the last attempt is, you\n>> add some extra things on top elsewhere, but format_commit_item code\n>> may need to be aware of those changes, which are not obvious when\n>> sombody just focuses on format_commit_item. Having all specifiers in\n>> one place would be better (hence no hooks, no callbacks) because we\n>> get a full picture. And yes we need to deal with specifers that make\n>> no sense in certain context.\n>\n> Yeah, it would certainly be nice to have all the format-specifiers\n> that one unified parser acts on, but isn't this just a matter of\n> refactoring? Shouldn't we be starting with cheap callbacks, get\n> things working, and guard against regressions in the refactoring phase\n> first? How else do you propose to start out?\n\nI prefer a series merged to master is a complete change. If\nrefactoring is needed, it should be done as part of the series as\nwell. Two reasons:\n - We might overlook something. The best way to avoid missing is\nfinish and verify it.\n - A promise to do things later could happen really late, or never\nhappens. As you are sastisfied with the functionality you have less\nmotivation to clean the code. Meanwhile the maintainer takes extra\nmaintenance cost.\n--\nDuy\n"},{"id":"222896","messageId":"CALkWK0=+B2C-0jmJL-mJHAio1H-dAacdV2Sr+HXpQTwehTD-xg@mail.gmail.com","threadId":"34369","inReplyTo":"CACsJy8B0E-jM+HHuhJD0fdZL2rat3ctDbSrCPo990WPnDA17RQ@mail.gmail.com","subject":"Re: [PATCH 3/4] cat-file: add --batch-disk-sizes option","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-07-09T10:32:31Z","receivedAt":"2013-07-09T10:32:31Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Duy Nguyen wrote:\n> - We might overlook something. The best way to avoid missing is\n> finish and verify it.\n> - A promise to do things later could happen really late, or never\n> happens. As you are sastisfied with the functionality you have less\n> motivation to clean the code. Meanwhile the maintainer takes extra\n> maintenance cost.\n\nI know. You know what my counter-argument looks like already:\n\nA promise to deliver a perfect series sometime in the future risks\nnever reaching that perfection, and stalling everyone else's work.\nEven if we do manage to complete that perfect series, there is no\nguarantee that we'll get sufficient reviewer-interest or traction for\nmerge. You think people are more likely to look at a 50-part series\nthan a 15-part series?\n\nEither way, I'm not interested in arguing: for now, I'll repost the\nold 15-part series and try to get some reviews. Start writing code,\nand let's finish this thing.\n"},{"id":"223003","messageId":"20130710105244.GA9724@sigill.intra.peff.net","threadId":"34369","inReplyTo":"CA+sFfMfQcnx+OGNd+v7NJC5zSXg2OR1QiLyRSqDjXD0zb4mvtA@mail.gmail.com","subject":"Re: [PATCH 4/4] pack-revindex: radix-sort the revindex","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T10:52:44Z","receivedAt":"2013-07-10T10:52:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 08, 2013 at 01:50:41PM -0700, Brandon Casey wrote:\n\n> > +static void sort_revindex(struct revindex_entry *entries, int n, off_t max)\n> \n> If 'n' is the number of objects in the pack, shouldn't it be unsigned?\n\nYes. I inherited that bug from the rest of the revindex code.\n\n> The data type for struct packed_git.num_objects is uint32_t. Looks\n> like create_pack_revindex uses the wrong datatype when it captures\n> num_objects in the int num_ent and passes it to sort_revindex. So, it\n> looks like that function needs to be updated too.\n\nYep. And the binary search in find_pack_revindex, too (which even has an\ninteger overflow!). I'll add a patch to my series to fix it (and switch\nmine).\n\n> > + while (max / (((off_t)1) << digits)) {\n> \n> Is there any reason this shouldn't be simplified to just:\n> \n> while (max >> digits) {\n\nNo, yours is much more readable. In case you are wondering how I ended\nup with that monstrosity, I originally did not keep the \"digits\" field\nas a number of bits, but rather a running total that bit-shifted 16 bits\neach time through the loop. I'll change it in the re-roll.\n\n> I glanced briefly at the assembly and it appears that gcc does\n> actually emit a divide instruction to accomplish this, which I think\n> we can avoid by just rearranging the operation.\n\nYep, although it almost certainly doesn't matter. We hit that loop\ncondition check at most 5 times for a 64-bit integer. I'm more concerned\nwith readability.\n\n> > + if (a != entries) {\n> > + int i;\n> > + for (i = 0; i < n; i++)\n> > + entries[i] = tmp[i];\n> \n> I think I recall that somebody investigated whether a for loop like\n> you have above was faster for copying structures than memcpy. I\n> forget whether it was conclusive. Did you happen to compare them?\n\nIt was me, actually, but the comparison was for memcmp rather than an\nopen-coded loop. And the conclusion was that memcmp is way faster on\nglibc 2.13 and higher.\n\nI think memcpy probably is going to be faster (especially in recent\nversions of glibc), given the size of the array (the other memcmp\ndiscussion was for 20-byte hashes, where the function call and setup\ntime was much more relevant).\n\nBut I don't think this was even timed at all in my tests. Since we go\nback-and-forth between the original array and the tmp storage, we have a\n\"50%\" chance of not needing to swap back anyway. So for packfiles up to\n64K, we do the swap (but they are not that interesting to measure), and\nthen from 64K to 4G, we do not.\n\nNote that we also use struct assignment in the sort itself to drop\nelements into their buckets. That could potentially use memcpy, though I\nwould expect the compiler to generate pretty decent instructions for\nsuch a small struct.\n\n-Peff\n"},{"id":"223004","messageId":"20130710105729.GB9724@sigill.intra.peff.net","threadId":"34369","inReplyTo":"CA+sFfMfHYkLc1rAnMKWGiGtH9kOC11D9CqpAsFXpeE_VBY0otA@mail.gmail.com","subject":"Re: [PATCH 4/4] pack-revindex: radix-sort the revindex","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T10:57:30Z","receivedAt":"2013-07-10T10:57:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 08, 2013 at 02:35:10PM -0700, Brandon Casey wrote:\n\n> > If 'n' is the number of objects in the pack, shouldn't it be unsigned?\n> >\n> > The data type for struct packed_git.num_objects is uint32_t. Looks\n> > like create_pack_revindex uses the wrong datatype when it captures\n> > num_objects in the int num_ent and passes it to sort_revindex. So, it\n> > looks like that function needs to be updated too.\n> \n> Hmm. It seems more than just create_pack_revindex holds num_objects\n> in a signed int. Don't we support 4G objects in packs?\n> \n> find_pack_revindex uses a signed int for the index variables in its\n> binary search which means it will fail when num_objects >= 2^31.\n\nYes, I didn't make a test case, but I suspect it is just completely\nbroken at that scale. But nobody hits it because having 2^31 objects is\nsomewhat insane (we are still only in the 2^22 range for the kernel, and\nmost large repos I've seen have large objects, but not necessarily more\nof them). So if development keeps up, the kernel should hit the bug in\nanother few thousand years. :)\n\n-Peff\n"},{"id":"223005","messageId":"20130710105750.GC9724@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130707211538.GB6478@vauxhall.crustytoothpaste.net","subject":"Re: [PATCH 3/4] cat-file: add --batch-disk-sizes option","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T10:57:50Z","receivedAt":"2013-07-10T10:57:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jul 07, 2013 at 09:15:41PM +0000, brian m. carlson wrote:\n\n> On Sun, Jul 07, 2013 at 06:09:49AM -0400, Jeff King wrote:\n> > +NOTE: The on-disk size reported is accurate, but care should be taken in\n> > +drawing conclusions about which refs or objects are responsible for disk\n> > +usage. The size of a packed non-delta object be much larger than the\n> \n> You probably meant \"may be\" here. ^\n\nThanks, fixed in my re-roll.\n\n-Peff\n"},{"id":"223007","messageId":"20130710110402.GD9724@sigill.intra.peff.net","threadId":"34369","inReplyTo":"7vtxk645vp.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/4] cat-file: add --batch-disk-sizes option","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T11:04:04Z","receivedAt":"2013-07-10T11:04:04Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jul 07, 2013 at 10:49:46AM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > Perhaps we need\n> >\n> > git cat-file --batch-format=\"%(disk-size) %(object)\"\n> >\n> > or similar.\n> \n> I agree with your reasoning. It may be simpler to give an interface\n> to ask for which pieces of info, e.g. --batch-cols=size,disksize,\n> without giving the readers a flexible \"format\".\n\nI started on this, and it turned out not to really be any simpler. In\nparticular there is the question of whether\n\n git cat-file --batch-cols=size,type\n\nis different from\n\n git cat-file --batch-cols=type,size\n\nIf so, then you are basically implementing the equivalent of a macro\nformat anyway (you have to parse it left to right to know the order).\nAnd if not, you end up translating the column list into a bit-field, and\nthe boilerplate for adding a new item is about the same as for a macro\nformat.\n\nSo I went ahead with the full formats for my re-roll. It turned out\npretty reasonable, I think.\n\n-Peff\n"},{"id":"223008","messageId":"20130710111652.GE9724@sigill.intra.peff.net","threadId":"34369","inReplyTo":"CALkWK0k0xiNFaFmqL2t4ba2g+HSrQ8kU+W_HvnSMcMYY8VgJyg@mail.gmail.com","subject":"Re: [PATCH 3/4] cat-file: add --batch-disk-sizes option","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T11:16:52Z","receivedAt":"2013-07-10T11:16:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 08, 2013 at 07:07:01PM +0530, Ramkumar Ramachandra wrote:\n\n> > There's also syntax sharing. I don't think each command should have\n> > its own syntax. f-e-r already has %(objectsize). If we plan to have a\n> > common syntax, perhaps %(disk-size) should be %(objectsize:disk) or\n> > something.\n> \n> Ofcourse. I didn't notice %(objectsize); %(objectsize[:disk]) is a\n> fine suggestion.\n> \n> > Adding formatting to cat-file --batch from scratch could be\n> > another big chunk of code (that also comes with bugs, usually) and may\n> > or may not be compatible with the common syntax because of some\n> > oversight.\n> \n> Oh, I'm proposing that Peff implements just %H and\n> %(objectsize[:disk]) for _now_, because that's what he wants. It\n> should be a tiny 20-line parser that's easy to swap out.\n\nI went with %(objectname), %(objectsize), and %(objectsize:disk). The\nformer match for-each-ref, and the latter extends it in a natural-ish\nway (though it is arguable whether \"foo:modifier\" should mean \"do\nsomething with the foo value\" or \"this is like foo, but not quite\"). In\nthe long run, I would like to see long names for each atom, with short\naliases (so \"%H\" and \"%h\" for \"%(objectname) and \"%(objectname:short)\",\navailable everywhere).\n\nBut I think it is OK to start without the aliases, and then pick them up\nas the implementations and interfaces are unified. IOW, it is OK to say\n\"cat-file has not learned about %H yet\", and later add it; we cannot\nteach it \"%H\" now and then change our minds later.\n\n> > --batch-cols=... or --batch-disk-size would be simpler, but\n> > we might never be able to remove that code.\n> \n> Agreed. The approach paints us into a design-corner, and must\n> therefore be avoided.\n\nI would say it is worth one of the other routes if it turned out to be\ndramatically simpler. But having just done the work to add formats for\ncat-file, it is really not too bad. It lacks some of the niceties of the\nother formatters (e.g., colors), but again, we can always add them in\nlater as the implementations unify.\n\n-Peff\n"},{"id":"223009","messageId":"20130710113447.GA20113@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130707100133.GA18717@sigill.intra.peff.net","subject":"[PATCHv2 00/10] cat-file formats/on-disk sizes","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T11:34:47Z","receivedAt":"2013-07-10T11:34:47Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Here's a re-roll of the cat-file --batch-disk-sizes series.\n\nThe main change is that it replaces the --batch-disk-sizes option with a\nformat string for --batch-check, syntactically modeled after the\nfor-each-ref format string.\n\n [01/10]: zero-initialize object_info structs\n [02/10]: teach sha1_object_info_extended a \"disk_size\" query\n\nThese two are the same as before.\n\n [03/10]: t1006: modernize output comparisons\n\nNew. Cleanup since I add some related tests later on.\n\n [04/10]: cat-file: teach --batch to stream blob objects\n\nNew. I think this is a sane thing to be doing, and it helps reorganize\nthe code for later changes. But note the performance caveat in the\ncommit message.\n\n [05/10]: cat-file: refactor --batch option parsing\n [06/10]: cat-file: add --batch-check=\n\nThese ones add the formatting code.\n\n [07/10]: cat-file: add %(objectsize:disk) format atom\n\nAnd this is the format analog of my original 3/4.\n\n [08/10]: cat-file: split --batch input lines on whitespace\n\nNew. This makes certain types of analysis simpler when you pipe\n\"rev-list --objects\" into \"cat-file --batch-check\", because you can\nretain the object paths through the pipe.\n\n [09/10]: pack-revindex: use unsigned to store number of objects\n\nNew. Addresses the 2^31 bug that Brandon noticed.\n\n [10/10]: pack-revindex: radix-sort the revindex\n\n>From the old 4/4, but with cleanups and addressing comments from the\nlist (details along with the patch).\n\n-Peff\n"},{"id":"223010","messageId":"20130710113526.GA21963@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130710113447.GA20113@sigill.intra.peff.net","subject":"[PATCH 01/10] zero-initialize object_info structs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T11:35:26Z","receivedAt":"2013-07-10T11:35:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The sha1_object_info_extended function expects the caller to\nprovide a \"struct object_info\" which contains pointers to\n\"query\" items that will be filled in. The purpose of\nproviding pointers rather than storing the response directly\nin the struct is so that callers can choose not to incur the\nexpense in finding particular fields that they do not care\nabout.\n\nRight now the only query item is \"sizep\", and all callers\nset it explicitly to choose whether or not to query it; they\ncan then leave the rest of the struct uninitialized.\n\nHowever, as we add new query items, each caller will have to\nbe updated to explicitly turn off the new ones (by setting\nthem to NULL). Instead, let's teach each caller to\nzero-initialize the struct, so that they do not have to\nlearn about each new query item added.\n\nSigned-off-by: Jeff King \n---\n sha1_file.c | 2 +-\n streaming.c | 2 +-\n 2 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 0af19c0..de06a97 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2428,7 +2428,7 @@ int sha1_object_info(const unsigned char *sha1, unsigned long *sizep)\n \n int sha1_object_info(const unsigned char *sha1, unsigned long *sizep)\n {\n-\tstruct object_info oi;\n+\tstruct object_info oi = {0};\n \n \toi.sizep = sizep;\n \treturn sha1_object_info_extended(sha1, &oi);\ndiff --git a/streaming.c b/streaming.c\nindex cabcd9d..cac282f 100644\n--- a/streaming.c\n+++ b/streaming.c\n@@ -135,7 +135,7 @@ struct git_istream *open_istream(const unsigned char *sha1,\n \t\t\t\t struct stream_filter *filter)\n {\n \tstruct git_istream *st;\n-\tstruct object_info oi;\n+\tstruct object_info oi = {0};\n \tconst unsigned char *real = lookup_replace_object(sha1);\n \tenum input_source src = istream_source(real, type, &oi);\n \n-- \n1.8.3.rc3.24.gec82cb9\n"},{"id":"223011","messageId":"20130710113538.GB21963@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130710113447.GA20113@sigill.intra.peff.net","subject":"[PATCH 02/10] teach sha1_object_info_extended a \"disk_size\" query","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T11:35:39Z","receivedAt":"2013-07-10T11:35:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Using sha1_object_info_extended, a caller can find out the\ntype of an object, its size, and information about where it\nis stored. In addition to the object's \"true\" size, it can\nalso be useful to know the size that the object takes on\ndisk (e.g., to generate statistics about which refs consume\nspace).\n\nThis patch adds a \"disk_sizep\" field to \"struct object_info\",\nand fills it in during sha1_object_info_extended if it is\nnon-NULL.\n\nSigned-off-by: Jeff King \n---\n cache.h | 1 +\n sha1_file.c | 20 ++++++++++++++++----\n 2 files changed, 17 insertions(+), 4 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex dd0fb33..2d06169 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1130,6 +1130,7 @@ struct object_info {\n struct object_info {\n \t/* Request */\n \tunsigned long *sizep;\n+\tunsigned long *disk_sizep;\n \n \t/* Response */\n \tenum {\ndiff --git a/sha1_file.c b/sha1_file.c\nindex de06a97..4c2365f 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1697,7 +1697,8 @@ static int packed_object_info(struct packed_git *p, off_t obj_offset,\n #define POI_STACK_PREALLOC 64\n \n static int packed_object_info(struct packed_git *p, off_t obj_offset,\n-\t\t\t unsigned long *sizep, int *rtype)\n+\t\t\t unsigned long *sizep, int *rtype,\n+\t\t\t unsigned long *disk_sizep)\n {\n \tstruct pack_window *w_curs = NULL;\n \tunsigned long size;\n@@ -1731,6 +1732,11 @@ static int packed_object_info(struct packed_git *p, off_t obj_offset,\n \t\t}\n \t}\n \n+\tif (disk_sizep) {\n+\t\tstruct revindex_entry *revidx = find_pack_revindex(p, obj_offset);\n+\t\t*disk_sizep = revidx[1].offset - obj_offset;\n+\t}\n+\n \twhile (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {\n \t\toff_t base_offset;\n \t\t/* Push the object we're going to leave behind */\n@@ -2357,7 +2363,8 @@ struct packed_git *find_sha1_pack(const unsigned char *sha1,\n \n }\n \n-static int sha1_loose_object_info(const unsigned char *sha1, unsigned long *sizep)\n+static int sha1_loose_object_info(const unsigned char *sha1, unsigned long *sizep,\n+\t\t\t\t unsigned long *disk_sizep)\n {\n \tint status;\n \tunsigned long mapsize, size;\n@@ -2368,6 +2375,8 @@ static int sha1_loose_object_info(const unsigned char *sha1, unsigned long *size\n \tmap = map_sha1_file(sha1, &mapsize);\n \tif (!map)\n \t\treturn -1;\n+\tif (disk_sizep)\n+\t\t*disk_sizep = mapsize;\n \tif (unpack_sha1_header(&stream, map, mapsize, hdr, sizeof(hdr)) < 0)\n \t\tstatus = error(\"unable to unpack %s header\",\n \t\t\t sha1_to_hex(sha1));\n@@ -2391,13 +2400,15 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi)\n \tif (co) {\n \t\tif (oi->sizep)\n \t\t\t*(oi->sizep) = co->size;\n+\t\tif (oi->disk_sizep)\n+\t\t\t*(oi->disk_sizep) = 0;\n \t\toi->whence = OI_CACHED;\n \t\treturn co->type;\n \t}\n \n \tif (!find_pack_entry(sha1, &e)) {\n \t\t/* Most likely it's a loose object. */\n-\t\tstatus = sha1_loose_object_info(sha1, oi->sizep);\n+\t\tstatus = sha1_loose_object_info(sha1, oi->sizep, oi->disk_sizep);\n \t\tif (status >= 0) {\n \t\t\toi->whence = OI_LOOSE;\n \t\t\treturn status;\n@@ -2409,7 +2420,8 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi)\n \t\t\treturn status;\n \t}\n \n-\tstatus = packed_object_info(e.p, e.offset, oi->sizep, &rtype);\n+\tstatus = packed_object_info(e.p, e.offset, oi->sizep, &rtype,\n+\t\t\t\t oi->disk_sizep);\n \tif (status < 0) {\n \t\tmark_bad_packed_object(e.p, sha1);\n \t\tstatus = sha1_object_info_extended(sha1, oi);\n-- \n1.8.3.rc3.24.gec82cb9\n"},{"id":"223012","messageId":"20130710113642.GC21963@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130710113447.GA20113@sigill.intra.peff.net","subject":"[PATCH 03/10] t1006: modernize output comparisons","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T11:36:43Z","receivedAt":"2013-07-10T11:36:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"In modern tests, we typically put output into a file and\ncompare it with test_cmp. This is nicer than just comparing\nvia \"test\", and much shorter than comparing via \"test\" and\nprinting a custom message.\n\nSigned-off-by: Jeff King \n---\nI didn't do the whole file, just the ones of a particular style close to\nwhat I was touching.\n\n t/t1006-cat-file.sh | 61 ++++++++++++++++-------------------------------------\n 1 file changed, 18 insertions(+), 43 deletions(-)\n\ndiff --git a/t/t1006-cat-file.sh b/t/t1006-cat-file.sh\nindex 9cc5c6b..c2f2503 100755\n--- a/t/t1006-cat-file.sh\n+++ b/t/t1006-cat-file.sh\n@@ -36,66 +36,41 @@ $content\"\n '\n \n test_expect_success \"Type of $type is correct\" '\n- test $type = \"$(git cat-file -t $sha1)\"\n+\techo $type >expect &&\n+\tgit cat-file -t $sha1 >actual &&\n+\ttest_cmp expect actual\n '\n \n test_expect_success \"Size of $type is correct\" '\n- test $size = \"$(git cat-file -s $sha1)\"\n+\techo $size >expect &&\n+\tgit cat-file -s $sha1 >actual &&\n+\ttest_cmp expect actual\n '\n \n test -z \"$content\" ||\n test_expect_success \"Content of $type is correct\" '\n-\texpect=\"$(maybe_remove_timestamp \"$content\" $no_ts)\"\n-\tactual=\"$(maybe_remove_timestamp \"$(git cat-file $type $sha1)\" $no_ts)\"\n-\n- if test \"z$expect\" = \"z$actual\"\n-\tthen\n-\t\t: happy\n-\telse\n-\t\techo \"Oops: expected $expect\"\n-\t\techo \"but got $actual\"\n-\t\tfalse\n- fi\n+\tmaybe_remove_timestamp \"$content\" $no_ts >expect &&\n+\tmaybe_remove_timestamp \"$(git cat-file $type $sha1)\" $no_ts >actual &&\n+\ttest_cmp expect actual\n '\n \n test_expect_success \"Pretty content of $type is correct\" '\n-\texpect=\"$(maybe_remove_timestamp \"$pretty_content\" $no_ts)\"\n-\tactual=\"$(maybe_remove_timestamp \"$(git cat-file -p $sha1)\" $no_ts)\"\n- if test \"z$expect\" = \"z$actual\"\n-\tthen\n-\t\t: happy\n-\telse\n-\t\techo \"Oops: expected $expect\"\n-\t\techo \"but got $actual\"\n-\t\tfalse\n- fi\n+\tmaybe_remove_timestamp \"$pretty_content\" $no_ts >expect &&\n+\tmaybe_remove_timestamp \"$(git cat-file -p $sha1)\" $no_ts >actual &&\n+\ttest_cmp expect actual\n '\n \n test -z \"$content\" ||\n test_expect_success \"--batch output of $type is correct\" '\n-\texpect=\"$(maybe_remove_timestamp \"$batch_output\" $no_ts)\"\n-\tactual=\"$(maybe_remove_timestamp \"$(echo $sha1 | git cat-file --batch)\" $no_ts)\"\n- if test \"z$expect\" = \"z$actual\"\n-\tthen\n-\t\t: happy\n-\telse\n-\t\techo \"Oops: expected $expect\"\n-\t\techo \"but got $actual\"\n-\t\tfalse\n- fi\n+\tmaybe_remove_timestamp \"$batch_output\" $no_ts >expect &&\n+\tmaybe_remove_timestamp \"$(echo $sha1 | git cat-file --batch)\" $no_ts >actual &&\n+\ttest_cmp expect actual\n '\n \n test_expect_success \"--batch-check output of $type is correct\" '\n-\texpect=\"$sha1 $type $size\"\n-\tactual=\"$(echo_without_newline $sha1 | git cat-file --batch-check)\"\n- if test \"z$expect\" = \"z$actual\"\n-\tthen\n-\t\t: happy\n-\telse\n-\t\techo \"Oops: expected $expect\"\n-\t\techo \"but got $actual\"\n-\t\tfalse\n- fi\n+\techo \"$sha1 $type $size\" >expect &&\n+\techo_without_newline $sha1 | git cat-file --batch-check >actual &&\n+\ttest_cmp expect actual\n '\n }\n \n-- \n1.8.3.rc3.24.gec82cb9\n"},{"id":"223013","messageId":"20130710113824.GD21963@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130710113447.GA20113@sigill.intra.peff.net","subject":"[PATCH 04/10] cat-file: teach --batch to stream blob objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T11:38:24Z","receivedAt":"2013-07-10T11:38:24Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The regular \"git cat-file -p\" and \"git cat-file blob\" code\npaths already learned to stream large blobs. Let's do the\nsame here.\n\nNote that this means we look up the type and size before\nmaking a decision of whether to load the object into memory\nor stream (just like the \"-p\" code path does). That can lead\nto extra work, but it should be dwarfed by the cost of\nactually accessing the object itself. In my measurements,\nthere was a 1-2% slowdown when using \"--batch\" on a large\nnumber of objects.\n\nSigned-off-by: Jeff King \n---\n builtin/cat-file.c | 41 ++++++++++++++++++++++++++++-------------\n 1 file changed, 28 insertions(+), 13 deletions(-)\n\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 045cee7..70dd8c8 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -117,12 +117,36 @@ static int batch_one_object(const char *obj_name, int print_contents)\n \treturn 0;\n }\n \n+static void print_object_or_die(int fd, const unsigned char *sha1,\n+\t\t\t\tenum object_type type, unsigned long size)\n+{\n+\tif (type == OBJ_BLOB) {\n+\t\tif (stream_blob_to_fd(fd, sha1, NULL, 0) < 0)\n+\t\t\tdie(\"unable to stream %s to stdout\", sha1_to_hex(sha1));\n+\t}\n+\telse {\n+\t\tenum object_type rtype;\n+\t\tunsigned long rsize;\n+\t\tvoid *contents;\n+\n+\t\tcontents = read_sha1_file(sha1, &rtype, &rsize);\n+\t\tif (!contents)\n+\t\t\tdie(\"object %s disappeared\", sha1_to_hex(sha1));\n+\t\tif (rtype != type)\n+\t\t\tdie(\"object %s changed type!?\", sha1_to_hex(sha1));\n+\t\tif (rsize != size)\n+\t\t\tdie(\"object %s change size!?\", sha1_to_hex(sha1));\n+\n+\t\twrite_or_die(fd, contents, size);\n+\t\tfree(contents);\n+\t}\n+}\n+\n static int batch_one_object(const char *obj_name, int print_contents)\n {\n \tunsigned char sha1[20];\n \tenum object_type type = 0;\n \tunsigned long size;\n-\tvoid *contents = NULL;\n \n \tif (!obj_name)\n \t return 1;\n@@ -133,16 +157,10 @@ static int batch_one_object(const char *obj_name, int print_contents)\n \t\treturn 0;\n \t}\n \n-\tif (print_contents == BATCH)\n-\t\tcontents = read_sha1_file(sha1, &type, &size);\n-\telse\n-\t\ttype = sha1_object_info(sha1, &size);\n-\n+\ttype = sha1_object_info(sha1, &size);\n \tif (type <= 0) {\n \t\tprintf(\"%s missing\\n\", obj_name);\n \t\tfflush(stdout);\n-\t\tif (print_contents == BATCH)\n-\t\t\tfree(contents);\n \t\treturn 0;\n \t}\n \n@@ -150,12 +168,9 @@ static int batch_one_object(const char *obj_name, int print_contents)\n \tfflush(stdout);\n \n \tif (print_contents == BATCH) {\n-\t\twrite_or_die(1, contents, size);\n-\t\tprintf(\"\\n\");\n-\t\tfflush(stdout);\n-\t\tfree(contents);\n+\t\tprint_object_or_die(1, sha1, type, size);\n+\t\twrite_or_die(1, \"\\n\", 1);\n \t}\n-\n \treturn 0;\n }\n \n-- \n1.8.3.rc3.24.gec82cb9\n"},{"id":"223014","messageId":"20130710113858.GE21963@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130710113447.GA20113@sigill.intra.peff.net","subject":"[PATCH 05/10] cat-file: refactor --batch option parsing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T11:38:58Z","receivedAt":"2013-07-10T11:38:58Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We currently use an int to tell us whether --batch parsing\nis on, and if so, whether we should print the full object\ncontents. Let's instead factor this into a struct, filled in\nby callback, which will make further batch-related options\neasy to add.\n\nSigned-off-by: Jeff King \n---\n builtin/cat-file.c | 56 ++++++++++++++++++++++++++++++++++++------------------\n 1 file changed, 38 insertions(+), 18 deletions(-)\n\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 70dd8c8..5254fe8 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -13,9 +13,6 @@\n #include \"userdiff.h\"\n #include \"streaming.h\"\n \n-#define BATCH 1\n-#define BATCH_CHECK 2\n-\n static int cat_one_file(int opt, const char *exp_type, const char *obj_name)\n {\n \tunsigned char sha1[20];\n@@ -142,7 +139,12 @@ static void print_object_or_die(int fd, const unsigned char *sha1,\n \t}\n }\n \n-static int batch_one_object(const char *obj_name, int print_contents)\n+struct batch_options {\n+\tint enabled;\n+\tint print_contents;\n+};\n+\n+static int batch_one_object(const char *obj_name, struct batch_options *opt)\n {\n \tunsigned char sha1[20];\n \tenum object_type type = 0;\n@@ -167,19 +169,19 @@ static int batch_objects(int print_contents)\n \tprintf(\"%s %s %lu\\n\", sha1_to_hex(sha1), typename(type), size);\n \tfflush(stdout);\n \n-\tif (print_contents == BATCH) {\n+\tif (opt->print_contents) {\n \t\tprint_object_or_die(1, sha1, type, size);\n \t\twrite_or_die(1, \"\\n\", 1);\n \t}\n \treturn 0;\n }\n \n-static int batch_objects(int print_contents)\n+static int batch_objects(struct batch_options *opt)\n {\n \tstruct strbuf buf = STRBUF_INIT;\n \n \twhile (strbuf_getline(&buf, stdin, '\\n') != EOF) {\n-\t\tint error = batch_one_object(buf.buf, print_contents);\n+\t\tint error = batch_one_object(buf.buf, opt);\n \t\tif (error)\n \t\t\treturn error;\n \t}\n@@ -201,10 +203,28 @@ int cmd_cat_file(int argc, const char **argv, const char *prefix)\n \treturn git_default_config(var, value, cb);\n }\n \n+static int batch_option_callback(const struct option *opt,\n+\t\t\t\t const char *arg,\n+\t\t\t\t int unset)\n+{\n+\tstruct batch_options *bo = opt->value;\n+\n+\tif (unset) {\n+\t\tmemset(bo, 0, sizeof(*bo));\n+\t\treturn 0;\n+\t}\n+\n+\tbo->enabled = 1;\n+\tbo->print_contents = !strcmp(opt->long_name, \"batch\");\n+\n+\treturn 0;\n+}\n+\n int cmd_cat_file(int argc, const char **argv, const char *prefix)\n {\n-\tint opt = 0, batch = 0;\n+\tint opt = 0;\n \tconst char *exp_type = NULL, *obj_name = NULL;\n+\tstruct batch_options batch = {0};\n \n \tconst struct option options[] = {\n \t\tOPT_GROUP(N_(\" can be one of: blob, tree, commit, tag\")),\n@@ -215,12 +235,12 @@ int cmd_cat_file(int argc, const char **argv, const char *prefix)\n \t\tOPT_SET_INT('p', NULL, &opt, N_(\"pretty-print object's content\"), 'p'),\n \t\tOPT_SET_INT(0, \"textconv\", &opt,\n \t\t\t N_(\"for blob objects, run textconv on object's content\"), 'c'),\n-\t\tOPT_SET_INT(0, \"batch\", &batch,\n-\t\t\t N_(\"show info and content of objects fed from the standard input\"),\n-\t\t\t BATCH),\n-\t\tOPT_SET_INT(0, \"batch-check\", &batch,\n-\t\t\t N_(\"show info about objects fed from the standard input\"),\n-\t\t\t BATCH_CHECK),\n+\t\t{ OPTION_CALLBACK, 0, \"batch\", &batch, NULL,\n+\t\t\tN_(\"show info and content of objects fed from the standard input\"),\n+\t\t\tPARSE_OPT_NOARG, batch_option_callback },\n+\t\t{ OPTION_CALLBACK, 0, \"batch-check\", &batch, NULL,\n+\t\t\tN_(\"show info about objects fed from the standard input\"),\n+\t\t\tPARSE_OPT_NOARG, batch_option_callback },\n \t\tOPT_END()\n \t};\n \n@@ -237,19 +257,19 @@ int cmd_cat_file(int argc, const char **argv, const char *prefix)\n \t\telse\n \t\t\tusage_with_options(cat_file_usage, options);\n \t}\n-\tif (!opt && !batch) {\n+\tif (!opt && !batch.enabled) {\n \t\tif (argc == 2) {\n \t\t\texp_type = argv[0];\n \t\t\tobj_name = argv[1];\n \t\t} else\n \t\t\tusage_with_options(cat_file_usage, options);\n \t}\n-\tif (batch && (opt || argc)) {\n+\tif (batch.enabled && (opt || argc)) {\n \t\tusage_with_options(cat_file_usage, options);\n \t}\n \n-\tif (batch)\n-\t\treturn batch_objects(batch);\n+\tif (batch.enabled)\n+\t\treturn batch_objects(&batch);\n \n \treturn cat_one_file(opt, exp_type, obj_name);\n }\n-- \n1.8.3.rc3.24.gec82cb9\n"},{"id":"223015","messageId":"20130710114546.GF21963@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130710113447.GA20113@sigill.intra.peff.net","subject":"[PATCH 06/10] cat-file: add --batch-check=","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T11:45:47Z","receivedAt":"2013-07-10T11:45:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The `cat-file --batch-check` command can be used to quickly\nget information about a large number of objects. However, it\nprovides a fixed set of information.\n\nThis patch adds an optional option to --batch-check\nto allow a caller to specify which items they are interested\nin, and in which order to output them. This is not very\nexciting for now, since we provide the same limited set that\nyou could already get. However, it opens the door to adding\nnew format items in the future without breaking backwards\ncompatibility (or forcing callers to pay the cost to\ncalculate uninteresting items).\n\nSince the --batch option shares code with --batch-check, it\nreceives the same feature, though it is less likely to be of\ninterest there.\n\nThe format atom names are chosen to match their counterparts\nin for-each-ref. Though we do not (yet) share any code with\nfor-each-ref's formatter, this keeps the interface as\nconsistent as possible, and may help later on if the\nimplementations are unified.\n\nSigned-off-by: Jeff King \n---\nIf the 1% slowdown in the streaming blob patch is too much, the simplest\nthing would be to have this formatting apply only to --batch-check, and\nlet --batch follow its own simpler code path. I doubt anybody really\ncares about having custom formats for --batch, as it is less about\nanalysis and more about getting enough information to recreate the\nobjects.\n\nAlso note that there is no %(contents) atom that one could use to\nemulate --batch via --batch-check. I don't see much point, and it would\nmean we would not want to build the formatting on strbuf_expand (because\nwe don't want to copy a large blob into the strbuf). We can add it later\nif somebody finds an actual use.\n\n Documentation/git-cat-file.txt | 55 ++++++++++++++++-----\n builtin/cat-file.c | 107 +++++++++++++++++++++++++++++++++++------\n t/t1006-cat-file.sh | 6 +++\n 3 files changed, 142 insertions(+), 26 deletions(-)\n\ndiff --git a/Documentation/git-cat-file.txt b/Documentation/git-cat-file.txt\nindex 30d585a..dd5d6e4 100644\n--- a/Documentation/git-cat-file.txt\n+++ b/Documentation/git-cat-file.txt\n@@ -58,12 +58,16 @@ OPTIONS\n \tto apply the filter to the content recorded in the index at .\n \n --batch::\n-\tPrint the SHA-1, type, size, and contents of each object provided on\n-\tstdin. May not be combined with any other options or arguments.\n+--batch=::\n+\tPrint object information and contents for each object provided\n+\ton stdin. May not be combined with any other options or arguments.\n+\tSee the section `BATCH OUTPUT` below for details.\n \n --batch-check::\n-\tPrint the SHA-1, type, and size of each object provided on stdin. May not\n-\tbe combined with any other options or arguments.\n+--batch-check=::\n+\tPrint object information for each object provided on stdin. May\n+\tnot be combined with any other options or arguments. See the\n+\tsection `BATCH OUTPUT` below for details.\n \n OUTPUT\n ------\n@@ -78,23 +82,52 @@ each object specified on stdin:\n If is specified, the raw (though uncompressed) contents of the \n will be returned.\n \n-If '--batch' is specified, output of the following form is printed for each\n-object specified on stdin:\n+BATCH OUTPUT\n+------------\n+\n+If `--batch` or `--batch-check` is given, `cat-file` will read objects\n+from stdin, one per line, and print information about them.\n+\n+Each line is considered as a whole object name, and is parsed as if\n+given to linkgit:git-rev-parse[1].\n+\n+You can specify the information shown for each object by using a custom\n+``. The `` is copied literally to stdout for each\n+object, with placeholders of the form `%(atom)` expanded, followed by a\n+newline. The available atoms are:\n+\n+`objectname`::\n+\tThe sha1 hash of the object.\n+\n+`objecttype`::\n+\tThe type of of the object (the same as `cat-file -t` reports).\n+\n+`objectsize`::\n+\tThe size, in bytes, of the object (the same as `cat-file -s`\n+\treports).\n+\n+If no format is specified, the default format is `%(objectname)\n+%(objecttype) %(objectsize)`.\n+\n+If `--batch` is specified, the object information is followed by the\n+object contents (consisting of `%(objectsize)` bytes), followed by a\n+newline.\n+\n+For example, `--batch` without a custom format would produce:\n \n ------------\n SP SP LF\n LF\n ------------\n \n-If '--batch-check' is specified, output of the following form is printed for\n-each object specified on stdin:\n+Whereas `--batch-check='%(objectname) %(objecttype)'` would produce:\n \n ------------\n- SP SP LF\n+ SP LF\n ------------\n \n-For both '--batch' and '--batch-check', output of the following form is printed\n-for each object specified on stdin that does not exist in the repository:\n+If a name is specified on stdin that cannot be resolved to an object in\n+the repository, then `cat-file` will ignore any custom format and print:\n \n ------------\n SP missing LF\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 5254fe8..b43a0c5 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -114,6 +114,66 @@ static int cat_one_file(int opt, const char *exp_type, const char *obj_name)\n \treturn 0;\n }\n \n+struct expand_data {\n+\tunsigned char sha1[20];\n+\tenum object_type type;\n+\tunsigned long size;\n+\n+\t/*\n+\t * If mark_query is true, we do not expand anything, but rather\n+\t * just mark the object_info with items we wish to query.\n+\t */\n+\tint mark_query;\n+\n+\t/*\n+\t * After a mark_query run, this object_info is set up to be\n+\t * passed to sha1_object_info_extended. It will point to the data\n+\t * elements above, so you can retrieve the response from there.\n+\t */\n+\tstruct object_info info;\n+};\n+\n+static int is_atom(const char *atom, const char *s, int slen)\n+{\n+\tint alen = strlen(atom);\n+\treturn alen == slen && !memcmp(atom, s, alen);\n+}\n+\n+static void expand_atom(struct strbuf *sb, const char *atom, int len,\n+\t\t\tvoid *vdata)\n+{\n+\tstruct expand_data *data = vdata;\n+\n+\tif (is_atom(\"objectname\", atom, len)) {\n+\t\tif (!data->mark_query)\n+\t\t\tstrbuf_addstr(sb, sha1_to_hex(data->sha1));\n+\t} else if (is_atom(\"objecttype\", atom, len)) {\n+\t\tif (!data->mark_query)\n+\t\t\tstrbuf_addstr(sb, typename(data->type));\n+\t} else if (is_atom(\"objectsize\", atom, len)) {\n+\t\tif (data->mark_query)\n+\t\t\tdata->info.sizep = &data->size;\n+\t\telse\n+\t\t\tstrbuf_addf(sb, \"%lu\", data->size);\n+\t} else\n+\t\tdie(\"unknown format element: %.*s\", len, atom);\n+}\n+\n+static size_t expand_format(struct strbuf *sb, const char *start, void *data)\n+{\n+\tconst char *end;\n+\n+\tif (*start != '(')\n+\t\treturn 0;\n+\tend = strchr(start + 1, ')');\n+\tif (!end)\n+\t\tdie(\"format element '%s' does not end in ')'\", start);\n+\n+\texpand_atom(sb, start + 1, end - start - 1, data);\n+\n+\treturn end - start + 1;\n+}\n+\n static void print_object_or_die(int fd, const unsigned char *sha1,\n \t\t\t\tenum object_type type, unsigned long size)\n {\n@@ -142,35 +202,37 @@ static int batch_one_object(const char *obj_name, struct batch_options *opt)\n struct batch_options {\n \tint enabled;\n \tint print_contents;\n+\tconst char *format;\n };\n \n-static int batch_one_object(const char *obj_name, struct batch_options *opt)\n+static int batch_one_object(const char *obj_name, struct batch_options *opt,\n+\t\t\t struct expand_data *data)\n {\n-\tunsigned char sha1[20];\n-\tenum object_type type = 0;\n-\tunsigned long size;\n+\tstruct strbuf buf = STRBUF_INIT;\n \n \tif (!obj_name)\n \t return 1;\n \n-\tif (get_sha1(obj_name, sha1)) {\n+\tif (get_sha1(obj_name, data->sha1)) {\n \t\tprintf(\"%s missing\\n\", obj_name);\n \t\tfflush(stdout);\n \t\treturn 0;\n \t}\n \n-\ttype = sha1_object_info(sha1, &size);\n-\tif (type <= 0) {\n+\tdata->type = sha1_object_info_extended(data->sha1, &data->info);\n+\tif (data->type <= 0) {\n \t\tprintf(\"%s missing\\n\", obj_name);\n \t\tfflush(stdout);\n \t\treturn 0;\n \t}\n \n-\tprintf(\"%s %s %lu\\n\", sha1_to_hex(sha1), typename(type), size);\n-\tfflush(stdout);\n+\tstrbuf_expand(&buf, opt->format, expand_format, data);\n+\tstrbuf_addch(&buf, '\\n');\n+\twrite_or_die(1, buf.buf, buf.len);\n+\tstrbuf_release(&buf);\n \n \tif (opt->print_contents) {\n-\t\tprint_object_or_die(1, sha1, type, size);\n+\t\tprint_object_or_die(1, data->sha1, data->type, data->size);\n \t\twrite_or_die(1, \"\\n\", 1);\n \t}\n \treturn 0;\n@@ -179,9 +241,23 @@ static int batch_objects(struct batch_options *opt)\n static int batch_objects(struct batch_options *opt)\n {\n \tstruct strbuf buf = STRBUF_INIT;\n+\tstruct expand_data data;\n+\n+\tif (!opt->format)\n+\t\topt->format = \"%(objectname) %(objecttype) %(objectsize)\";\n+\n+\t/*\n+\t * Expand once with our special mark_query flag, which will prime the\n+\t * object_info to be handed to sha1_object_info_extended for each\n+\t * object.\n+\t */\n+\tmemset(&data, 0, sizeof(data));\n+\tdata.mark_query = 1;\n+\tstrbuf_expand(&buf, opt->format, expand_format, &data);\n+\tdata.mark_query = 0;\n \n \twhile (strbuf_getline(&buf, stdin, '\\n') != EOF) {\n-\t\tint error = batch_one_object(buf.buf, opt);\n+\t\tint error = batch_one_object(buf.buf, opt, &data);\n \t\tif (error)\n \t\t\treturn error;\n \t}\n@@ -216,6 +292,7 @@ static int batch_option_callback(const struct option *opt,\n \n \tbo->enabled = 1;\n \tbo->print_contents = !strcmp(opt->long_name, \"batch\");\n+\tbo->format = arg;\n \n \treturn 0;\n }\n@@ -235,12 +312,12 @@ int cmd_cat_file(int argc, const char **argv, const char *prefix)\n \t\tOPT_SET_INT('p', NULL, &opt, N_(\"pretty-print object's content\"), 'p'),\n \t\tOPT_SET_INT(0, \"textconv\", &opt,\n \t\t\t N_(\"for blob objects, run textconv on object's content\"), 'c'),\n-\t\t{ OPTION_CALLBACK, 0, \"batch\", &batch, NULL,\n+\t\t{ OPTION_CALLBACK, 0, \"batch\", &batch, \"format\",\n \t\t\tN_(\"show info and content of objects fed from the standard input\"),\n-\t\t\tPARSE_OPT_NOARG, batch_option_callback },\n-\t\t{ OPTION_CALLBACK, 0, \"batch-check\", &batch, NULL,\n+\t\t\tPARSE_OPT_OPTARG, batch_option_callback },\n+\t\t{ OPTION_CALLBACK, 0, \"batch-check\", &batch, \"format\",\n \t\t\tN_(\"show info about objects fed from the standard input\"),\n-\t\t\tPARSE_OPT_NOARG, batch_option_callback },\n+\t\t\tPARSE_OPT_OPTARG, batch_option_callback },\n \t\tOPT_END()\n \t};\n \ndiff --git a/t/t1006-cat-file.sh b/t/t1006-cat-file.sh\nindex c2f2503..4e911fb 100755\n--- a/t/t1006-cat-file.sh\n+++ b/t/t1006-cat-file.sh\n@@ -72,6 +72,12 @@ $content\"\n \techo_without_newline $sha1 | git cat-file --batch-check >actual &&\n \ttest_cmp expect actual\n '\n+\n+ test_expect_success \"custom --batch-check format\" '\n+\techo \"$type $sha1\" >expect &&\n+\techo $sha1 | git cat-file --batch-check=\"%(objecttype) %(objectname)\" >actual &&\n+\ttest_cmp expect actual\n+ '\n }\n \n hello_content=\"Hello World\"\n-- \n1.8.3.rc3.24.gec82cb9\n"},{"id":"223016","messageId":"20130710114625.GG21963@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130710113447.GA20113@sigill.intra.peff.net","subject":"[PATCH 07/10] cat-file: add %(objectsize:disk) format atom","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T11:46:25Z","receivedAt":"2013-07-10T11:46:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This atom is just like %(objectsize), except that it shows\nthe on-disk size of the object rather than the object's true\nsize. In other words, it makes the \"disk_size\" query of\nsha1_object_info_extended available via the command-line.\n\nThis can be used for rough attribution of disk usage to\nparticular refs, though see the caveats in the\ndocumentation.\n\nThis patch does not include any tests, as the exact numbers\nreturned are volatile and subject to zlib and packing\ndecisions. We cannot even reliably guarantee that the\non-disk size is smaller than the object content (though in\ngeneral this should be the case for non-trivial objects).\n\nSigned-off-by: Jeff King \n---\n Documentation/git-cat-file.txt | 18 ++++++++++++++++++\n builtin/cat-file.c | 6 ++++++\n 2 files changed, 24 insertions(+)\n\ndiff --git a/Documentation/git-cat-file.txt b/Documentation/git-cat-file.txt\nindex dd5d6e4..06bdc43 100644\n--- a/Documentation/git-cat-file.txt\n+++ b/Documentation/git-cat-file.txt\n@@ -106,6 +106,10 @@ newline. The available atoms are:\n \tThe size, in bytes, of the object (the same as `cat-file -s`\n \treports).\n \n+`objectsize:disk`::\n+\tThe size, in bytes, that the object takes up on disk. See the\n+\tnote about on-disk sizes in the `CAVEATS` section below.\n+\n If no format is specified, the default format is `%(objectname)\n %(objecttype) %(objectsize)`.\n \n@@ -133,6 +137,20 @@ the repository, then `cat-file` will ignore any custom format and print:\n SP missing LF\n ------------\n \n+\n+CAVEATS\n+-------\n+\n+Note that the sizes of objects on disk are reported accurately, but care\n+should be taken in drawing conclusions about which refs or objects are\n+responsible for disk usage. The size of a packed non-delta object may be\n+much larger than the size of objects which delta against it, but the\n+choice of which object is the base and which is the delta is arbitrary\n+and is subject to change during a repack. Note also that multiple copies\n+of an object may be present in the object database; in this case, it is\n+undefined which copy's size will be reported.\n+\n+\n GIT\n ---\n Part of the linkgit:git[1] suite\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex b43a0c5..11fa8c0 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -118,6 +118,7 @@ struct expand_data {\n \tunsigned char sha1[20];\n \tenum object_type type;\n \tunsigned long size;\n+\tunsigned long disk_size;\n \n \t/*\n \t * If mark_query is true, we do not expand anything, but rather\n@@ -155,6 +156,11 @@ static void expand_atom(struct strbuf *sb, const char *atom, int len,\n \t\t\tdata->info.sizep = &data->size;\n \t\telse\n \t\t\tstrbuf_addf(sb, \"%lu\", data->size);\n+\t} else if (is_atom(\"objectsize:disk\", atom, len)) {\n+\t\tif (data->mark_query)\n+\t\t\tdata->info.disk_sizep = &data->disk_size;\n+\t\telse\n+\t\t\tstrbuf_addf(sb, \"%lu\", data->disk_size);\n \t} else\n \t\tdie(\"unknown format element: %.*s\", len, atom);\n }\n-- \n1.8.3.rc3.24.gec82cb9\n"},{"id":"223017","messageId":"20130710114828.GH21963@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130710113447.GA20113@sigill.intra.peff.net","subject":"[PATCH 08/10] cat-file: split --batch input lines on whitespace","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T11:48:28Z","receivedAt":"2013-07-10T11:48:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"If we get an input line to --batch or --batch-check that\nlooks like \"HEAD foo bar\", we will currently feed the whole\nthing to get_sha1(). This means that to use --batch-check\nwith `rev-list --objects`, one must pre-process the input,\nlike:\n\n git rev-list --objects HEAD |\n cut -d' ' -f1 |\n git cat-file --batch-check\n\nBesides being more typing and slightly less efficient to\ninvoke `cut`, the result loses information: we no longer\nknow which path each object was found at.\n\nThis patch teaches cat-file to split input lines at the\nfirst whitespace. Everything to the left of the whitespace\nis considered an object name, and everything to the right is\nmade available as the %(text) atom. So you can now do:\n\n git rev-list --objects HEAD |\n git cat-file --batch-check='%(objectsize) %(text)'\n\nto collect object sizes at particular paths.\n\nEven if %(text) is not used, we always do the whitespace\nsplit (which means you can simply eliminate the `cut`\ncommand from the first example above).\n\nThis whitespace split is backwards compatible for any\nreasonable input. Object names cannot contain spaces, so any\ninput with spaces would have resulted in a \"missing\" line.\nThe only input hurt is if somebody really expected input of\nthe form \"HEAD is a fine-looking ref!\" to fail; it will now\nparse HEAD, and make \"is a fine-looking ref!\" available as\n%(text).\n\nSigned-off-by: Jeff King \n---\nI have often found myself cross-referencing object sha1s with rev-list\n--objects output in order to find out which paths are bloating\nrepository size. You can do it manually, or by post-processing the\noutput of cat-file with \"join\", but it is way more efficient to simply\nnot lose the information in the first place.\n\n Documentation/git-cat-file.txt | 10 ++++++++--\n builtin/cat-file.c | 20 +++++++++++++++++++-\n t/t1006-cat-file.sh | 7 +++++++\n 3 files changed, 34 insertions(+), 3 deletions(-)\n\ndiff --git a/Documentation/git-cat-file.txt b/Documentation/git-cat-file.txt\nindex 06bdc43..6b0b2de 100644\n--- a/Documentation/git-cat-file.txt\n+++ b/Documentation/git-cat-file.txt\n@@ -88,8 +88,10 @@ from stdin, one per line, and print information about them.\n If `--batch` or `--batch-check` is given, `cat-file` will read objects\n from stdin, one per line, and print information about them.\n \n-Each line is considered as a whole object name, and is parsed as if\n-given to linkgit:git-rev-parse[1].\n+Each line is split at the first whitespace boundary. All characters\n+before that whitespace are considered as a whole object name, and are\n+parsed as if given to linkgit:git-rev-parse[1]. Characters after that\n+whitespace can be accessed using the `%(text)` atom (see below).\n \n You can specify the information shown for each object by using a custom\n ``. The `` is copied literally to stdout for each\n@@ -110,6 +112,10 @@ newline. The available atoms are:\n \tThe size, in bytes, that the object takes up on disk. See the\n \tnote about on-disk sizes in the `CAVEATS` section below.\n \n+`text`::\n+\tThe text (if any) found after the first run of whitespace on the\n+\tinput line.\n+\n If no format is specified, the default format is `%(objectname)\n %(objecttype) %(objectsize)`.\n \ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 11fa8c0..36f8159 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -119,6 +119,7 @@ struct expand_data {\n \tenum object_type type;\n \tunsigned long size;\n \tunsigned long disk_size;\n+\tconst char *text;\n \n \t/*\n \t * If mark_query is true, we do not expand anything, but rather\n@@ -161,6 +162,9 @@ static void expand_atom(struct strbuf *sb, const char *atom, int len,\n \t\t\tdata->info.disk_sizep = &data->disk_size;\n \t\telse\n \t\t\tstrbuf_addf(sb, \"%lu\", data->disk_size);\n+\t} else if (is_atom(\"text\", atom, len)) {\n+\t\tif (!data->mark_query && data->text)\n+\t\t\tstrbuf_addstr(sb, data->text);\n \t} else\n \t\tdie(\"unknown format element: %.*s\", len, atom);\n }\n@@ -263,7 +267,21 @@ static int batch_objects(struct batch_options *opt)\n \tdata.mark_query = 0;\n \n \twhile (strbuf_getline(&buf, stdin, '\\n') != EOF) {\n-\t\tint error = batch_one_object(buf.buf, opt, &data);\n+\t\tchar *p;\n+\t\tint error;\n+\n+\t\t/*\n+\t\t * Split at first whitespace, tying off the beginning of the\n+\t\t * string and saving the remainder (or NULL) in data.text.\n+\t\t */\n+\t\tp = strpbrk(buf.buf, \" \\t\");\n+\t\tif (p) {\n+\t\t\twhile (*p && strchr(\" \\t\", *p))\n+\t\t\t\t*p++ = '\\0';\n+\t\t}\n+\t\tdata.text = p;\n+\n+\t\terror = batch_one_object(buf.buf, opt, &data);\n \t\tif (error)\n \t\t\treturn error;\n \t}\ndiff --git a/t/t1006-cat-file.sh b/t/t1006-cat-file.sh\nindex 4e911fb..315da6f 100755\n--- a/t/t1006-cat-file.sh\n+++ b/t/t1006-cat-file.sh\n@@ -78,6 +78,13 @@ $content\"\n \techo $sha1 | git cat-file --batch-check=\"%(objecttype) %(objectname)\" >actual &&\n \ttest_cmp expect actual\n '\n+\n+ test_expect_success '--batch-check with %(text)' '\n+\techo \"$type this is some extra content\" >expect &&\n+\techo \"$sha1 this is some extra content\" |\n+\t\tgit cat-file --batch-check=\"%(objecttype) %(text)\" >actual &&\n+\ttest_cmp expect actual\n+ '\n }\n \n hello_content=\"Hello World\"\n-- \n1.8.3.rc3.24.gec82cb9\n"},{"id":"223018","messageId":"20130710115026.GI21963@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130710113447.GA20113@sigill.intra.peff.net","subject":"[PATCH 09/10] pack-revindex: use unsigned to store number of objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T11:50:26Z","receivedAt":"2013-07-10T11:50:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"A packfile may have up to 2^32-1 objects in it, so the\n\"right\" data type to use is uint32_t. We currently use a\nsigned int, which means that we may behave incorrectly for\npackfiles with more than 2^31-1 objects on 32-bit systems.\n\nNobody has noticed because having 2^31 objects is pretty\ninsane. The linux.git repo has on the order of 2^22 objects,\nwhich is hundreds of times smaller than necessary to trigger\nthe bug.\n\nLet's bump this up to an \"unsigned\". On 32-bit systems, this\ngives us the correct data-type, and on 64-bit systems, it is\nprobably more efficient to use the native \"unsigned\" than a\ntrue uint32_t.\n\nWhile we're at it, we can fix the binary search not to\noverflow in such a case if our unsigned is 32 bits.\n\nSigned-off-by: Jeff King \n---\nI didn't look farther in the pack code to see if we have other\nproblematic instances. So there may be others lurking, but these ones\nwere close to the area I was working in.\n\n pack-revindex.c | 8 ++++----\n 1 file changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/pack-revindex.c b/pack-revindex.c\nindex 77a0465..1aa9754 100644\n--- a/pack-revindex.c\n+++ b/pack-revindex.c\n@@ -72,8 +72,8 @@ static void create_pack_revindex(struct pack_revindex *rix)\n static void create_pack_revindex(struct pack_revindex *rix)\n {\n \tstruct packed_git *p = rix->p;\n-\tint num_ent = p->num_objects;\n-\tint i;\n+\tunsigned num_ent = p->num_objects;\n+\tunsigned i;\n \tconst char *index = p->index_data;\n \n \trix->revindex = xmalloc(sizeof(*rix->revindex) * (num_ent + 1));\n@@ -114,7 +114,7 @@ struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs)\n struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs)\n {\n \tint num;\n-\tint lo, hi;\n+\tunsigned lo, hi;\n \tstruct pack_revindex *rix;\n \tstruct revindex_entry *revindex;\n \n@@ -132,7 +132,7 @@ struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs)\n \tlo = 0;\n \thi = p->num_objects + 1;\n \tdo {\n-\t\tint mi = (lo + hi) / 2;\n+\t\tunsigned mi = lo + (hi - lo) / 2;\n \t\tif (revindex[mi].offset == ofs) {\n \t\t\treturn revindex + mi;\n \t\t} else if (ofs < revindex[mi].offset)\n-- \n1.8.3.rc3.24.gec82cb9\n"},{"id":"223019","messageId":"20130710115557.GJ21963@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130710113447.GA20113@sigill.intra.peff.net","subject":"[PATCH 10/10] pack-revindex: radix-sort the revindex","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T11:55:57Z","receivedAt":"2013-07-10T11:55:57Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The pack revindex stores the offsets of the objects in the\npack in sorted order, allowing us to easily find the on-disk\nsize of each object. To compute it, we populate an array\nwith the offsets from the sha1-sorted idx file, and then use\nqsort to order it by offsets.\n\nThat does O(n log n) offset comparisons, and profiling shows\nthat we spend most of our time in cmp_offset. However, since\nwe are sorting on a simple off_t, we can use numeric sorts\nthat perform better. A radix sort can run in O(k*n), where k\nis the number of \"digits\" in our number. For a 64-bit off_t,\nusing 16-bit \"digits\" gives us k=4.\n\nOn the linux.git repo, with about 3M objects to sort, this\nyields a 400% speedup. Here are the best-of-five numbers for\nrunning \"echo HEAD | git cat-file --batch-disk-size\", which\nis dominated by time spent building the pack revindex:\n\n before after\n real 0m0.834s 0m0.204s\n user 0m0.788s 0m0.164s\n sys 0m0.040s 0m0.036s\n\nOn a smaller repo, the radix sort would not be\nas impressive (and could even be worse), as we are trading\nthe log(n) factor for the k=4 of the radix sort. However,\neven on git.git, with 173K objects, it shows some\nimprovement:\n\n before after\n real 0m0.046s 0m0.017s\n user 0m0.036s 0m0.012s\n sys 0m0.008s 0m0.000s\n\nSigned-off-by: Jeff King \n---\nI changed a few things from the original, including:\n\n 1. We take an \"unsigned\" number of objects to match the fix in the\n last patch.\n\n 2. The 16-bit \"digit\" size is factored out to a single place, which\n avoids magic numbers and repeating ourselves.\n\n 3. The \"digits\" variable is renamed to \"bits\", which is more accurate.\n\n 4. The outer loop condition uses the simpler \"while (max >> bits)\".\n\n 5. We use memcpy instead of an open-coded loop to copy the whole array\n at the end. The individual bucket-assignment is still done by\n struct assignment. I haven't timed if memcpy would make a\n difference there.\n\n 6. The 64K*sizeof(int) \"pos\" array is now heap-allocated, in case\n there are platforms with a small stack.\n\nI re-ran my timings to make sure none of the above impacted them; it\nturned out the same.\n\n pack-revindex.c | 84 +++++++++++++++++++++++++++++++++++++++++++++++++++++----\n 1 file changed, 79 insertions(+), 5 deletions(-)\n\ndiff --git a/pack-revindex.c b/pack-revindex.c\nindex 1aa9754..9365bc2 100644\n--- a/pack-revindex.c\n+++ b/pack-revindex.c\n@@ -59,11 +59,85 @@ static int cmp_offset(const void *a_, const void *b_)\n \t/* revindex elements are lazily initialized */\n }\n \n-static int cmp_offset(const void *a_, const void *b_)\n+/*\n+ * This is a least-significant-digit radix sort.\n+ */\n+static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)\n {\n-\tconst struct revindex_entry *a = a_;\n-\tconst struct revindex_entry *b = b_;\n-\treturn (a->offset < b->offset) ? -1 : (a->offset > b->offset) ? 1 : 0;\n+\t/*\n+\t * We use a \"digit\" size of 16 bits. That keeps our memory\n+\t * usage reasonable, and we can generally (for a 4G or smaller\n+\t * packfile) quit after two rounds of radix-sorting.\n+\t */\n+#define DIGIT_SIZE (16)\n+#define BUCKETS (1 << DIGIT_SIZE)\n+\t/*\n+\t * We want to know the bucket that a[i] will go into when we are using\n+\t * the digit that is N bits from the (least significant) end.\n+\t */\n+#define BUCKET_FOR(a, i, bits) (((a)[(i)].offset >> (bits)) & (BUCKETS-1))\n+\n+\t/*\n+\t * We need O(n) temporary storage, so we sort back and forth between\n+\t * the real array and our tmp storage. To keep them straight, we always\n+\t * sort from \"a\" into buckets in \"b\".\n+\t */\n+\tstruct revindex_entry *tmp = xcalloc(n, sizeof(*tmp));\n+\tstruct revindex_entry *a = entries, *b = tmp;\n+\tint bits = 0;\n+\tunsigned *pos = xmalloc(BUCKETS * sizeof(*pos));\n+\n+\twhile (max >> bits) {\n+\t\tstruct revindex_entry *swap;\n+\t\tint i;\n+\n+\t\tmemset(pos, 0, BUCKETS * sizeof(*pos));\n+\n+\t\t/*\n+\t\t * We want pos[i] to store the index of the last element that\n+\t\t * will go in bucket \"i\" (actually one past the last element).\n+\t\t * To do this, we first count the items that will go in each\n+\t\t * bucket, which gives us a relative offset from the last\n+\t\t * bucket. We can then cumulatively add the index from the\n+\t\t * previous bucket to get the true index.\n+\t\t */\n+\t\tfor (i = 0; i < n; i++)\n+\t\t\tpos[BUCKET_FOR(a, i, bits)]++;\n+\t\tfor (i = 1; i < BUCKETS; i++)\n+\t\t\tpos[i] += pos[i-1];\n+\n+\t\t/*\n+\t\t * Now we can drop the elements into their correct buckets (in\n+\t\t * our temporary array). We iterate the pos counter backwards\n+\t\t * to avoid using an extra index to count up. And since we are\n+\t\t * going backwards there, we must also go backwards through the\n+\t\t * array itself, to keep the sort stable.\n+\t\t */\n+\t\tfor (i = n - 1; i >= 0; i--)\n+\t\t\tb[--pos[BUCKET_FOR(a, i, bits)]] = a[i];\n+\n+\t\t/*\n+\t\t * Now \"b\" contains the most sorted list, so we swap \"a\" and\n+\t\t * \"b\" for the next iteration.\n+\t\t */\n+\t\tswap = a;\n+\t\ta = b;\n+\t\tb = swap;\n+\n+\t\t/* And bump our bits for the next round. */\n+\t\tbits += DIGIT_SIZE;\n+\t}\n+\n+\t/*\n+\t * If we ended with our data in the original array, great. If not,\n+\t * we have to move it back from the temporary storage.\n+\t */\n+\tif (a != entries)\n+\t\tmemcpy(entries, tmp, n * sizeof(*entries));\n+\tfree(tmp);\n+\tfree(pos);\n+\n+#undef BUCKET_FOR\n }\n \n /*\n@@ -108,7 +182,7 @@ static void create_pack_revindex(struct pack_revindex *rix)\n \t */\n \trix->revindex[num_ent].offset = p->pack_size - 20;\n \trix->revindex[num_ent].nr = -1;\n-\tqsort(rix->revindex, num_ent, sizeof(*rix->revindex), cmp_offset);\n+\tsort_revindex(rix->revindex, num_ent, p->pack_size);\n }\n \n struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs)\n-- \n1.8.3.rc3.24.gec82cb9\n"},{"id":"223020","messageId":"CAPig+cRSTPGioLXdkzWtsqneM8KTNvFoONZJXFKNy_T=-VioNA@mail.gmail.com","threadId":"34369","inReplyTo":"20130710114546.GF21963@sigill.intra.peff.net","subject":"Re: [PATCH 06/10] cat-file: add --batch-check=","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2013-07-10T11:57:33Z","receivedAt":"2013-07-10T11:57:33Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Wed, Jul 10, 2013 at 7:45 AM, Jeff King wrote:\n> The `cat-file --batch-check` command can be used to quickly\n> get information about a large number of objects. However, it\n> provides a fixed set of information.\n>\n> This patch adds an optional option to --batch-check\n> to allow a caller to specify which items they are interested\n> in, and in which order to output them. This is not very\n> exciting for now, since we provide the same limited set that\n> you could already get. However, it opens the door to adding\n> new format items in the future without breaking backwards\n> compatibility (or forcing callers to pay the cost to\n> calculate uninteresting items).\n>\n> The format atom names are chosen to match their counterparts\n> in for-each-ref. Though we do not (yet) share any code with\n> for-each-ref's formatter, this keeps the interface as\n> consistent as possible, and may help later on if the\n> implementations are unified.\n>\n> Signed-off-by: Jeff King \n> diff --git a/Documentation/git-cat-file.txt b/Documentation/git-cat-file.txt\n> index 30d585a..dd5d6e4 100644\n> --- a/Documentation/git-cat-file.txt\n> +++ b/Documentation/git-cat-file.txt\n> @@ -78,23 +82,52 @@ each object specified on stdin:\n> If is specified, the raw (though uncompressed) contents of the \n> will be returned.\n>\n> -If '--batch' is specified, output of the following form is printed for each\n> -object specified on stdin:\n> +BATCH OUTPUT\n> +------------\n> +\n> +You can specify the information shown for each object by using a custom\n> +``. The `` is copied literally to stdout for each\n> +object, with placeholders of the form `%(atom)` expanded, followed by a\n> +newline. The available atoms are:\n> +\n> +`objectname`::\n> + The sha1 hash of the object.\n\nFor consistency with (d5fa1f1; The name of the hash function is\n\"SHA-1\", not \"SHA1\"):\n\ns/sha1/SHA-1/\n\n> +\n> +`objecttype`::\n> + The type of of the object (the same as `cat-file -t` reports).\n> +\n> +`objectsize`::\n> + The size, in bytes, of the object (the same as `cat-file -s`\n> + reports).\n> +\n> +If no format is specified, the default format is `%(objectname)\n> +%(objecttype) %(objectsize)`.\n> +\n> +If `--batch` is specified, the object information is followed by the\n> +object contents (consisting of `%(objectsize)` bytes), followed by a\n> +newline.\n"},{"id":"223021","messageId":"20130710120029.GA20519@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130710115557.GJ21963@sigill.intra.peff.net","subject":"Re: [PATCH 10/10] pack-revindex: radix-sort the revindex","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-10T12:00:29Z","receivedAt":"2013-07-10T12:00:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 10, 2013 at 07:55:57AM -0400, Jeff King wrote:\n\n> 5. We use memcpy instead of an open-coded loop to copy the whole array\n> at the end. The individual bucket-assignment is still done by\n> struct assignment. I haven't timed if memcpy would make a\n> difference there.\n\nI just timed this, and I can't measure any difference. I think the\nstruct assignment is the more readable option, and I do not think any\ncompilers should have trouble with it. But if they do, we can switch it\nfor a memcpy.\n\n-Peff\n"},{"id":"223022","messageId":"CALkWK0=_6-RN2dHrhMdKu8nTyj1iwVe388Y57pOac17xhbqn5Q@mail.gmail.com","threadId":"34369","inReplyTo":"20130710115557.GJ21963@sigill.intra.peff.net","subject":"Re: [PATCH 10/10] pack-revindex: radix-sort the revindex","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-07-10T13:17:49Z","receivedAt":"2013-07-10T13:17:49Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Jeff King wrote:\n> That does O(n log n) offset comparisons, and profiling shows\n> that we spend most of our time in cmp_offset. However, since\n> we are sorting on a simple off_t, we can use numeric sorts\n> that perform better. A radix sort can run in O(k*n), where k\n> is the number of \"digits\" in our number. For a 64-bit off_t,\n> using 16-bit \"digits\" gives us k=4.\n\nWait, isn't off_t a signed data type? Did you account for that in\nyour algorithm?\n\n> On the linux.git repo, with about 3M objects to sort, this\n> yields a 400% speedup. Here are the best-of-five numbers for\n> running \"echo HEAD | git cat-file --batch-disk-size\", which\n> is dominated by time spent building the pack revindex:\n\nOkay.\n\n> diff --git a/pack-revindex.c b/pack-revindex.c\n> index 1aa9754..9365bc2 100644\n> --- a/pack-revindex.c\n> +++ b/pack-revindex.c\n> @@ -59,11 +59,85 @@ static int cmp_offset(const void *a_, const void *b_)\n> /* revindex elements are lazily initialized */\n> }\n>\n> -static int cmp_offset(const void *a_, const void *b_)\n> +/*\n> + * This is a least-significant-digit radix sort.\n> + */\n\nAny particular reason for choosing LSD, and not MSD?\n\n> +#define DIGIT_SIZE (16)\n> +#define BUCKETS (1 << DIGIT_SIZE)\n\nOkay, NUMBER_OF_BUCKETS = 2^RADIX, and you choose a hex radix. Is\noff_t guaranteed to be fixed-length though? I thought only the ones\nin stdint.h were guaranteed to be fixed-length?\n\n> + /*\n> + * We want to know the bucket that a[i] will go into when we are using\n> + * the digit that is N bits from the (least significant) end.\n> + */\n> +#define BUCKET_FOR(a, i, bits) (((a)[(i)].offset >> (bits)) & (BUCKETS-1))\n\nOuch! This is unreadable. Just write an inline function instead? A\n% would've been easier on the eyes, but you chose base-16.\n\n> + /*\n> + * We need O(n) temporary storage, so we sort back and forth between\n> + * the real array and our tmp storage. To keep them straight, we always\n> + * sort from \"a\" into buckets in \"b\".\n> + */\n> + struct revindex_entry *tmp = xcalloc(n, sizeof(*tmp));\n\nShouldn't this be sizeof (struct revindex_entry), since tmp hasn't\nbeen declared yet? Also, s/n/revindex_nr/, and something more\nappropriate for tmp?\n\n> + struct revindex_entry *a = entries, *b = tmp;\n\nIt's starting to look like you have something against descriptive names ;)\n\n> + int bits = 0;\n> + unsigned *pos = xmalloc(BUCKETS * sizeof(*pos));\n\nsizeof(unsigned int), for clarity, if not anything else. You picked\nmalloc over calloc here, because you didn't want to incur the extra\ncost of zero-initializing the memory? Also, pos is the actual buckets\narray, I presume (hence unsigned, because there can't be a negative\nnumber of keys in any bucket)?\n\n> + while (max >> bits) {\n\nNo clue what max is. Looked at the caller and figured out that it's\nthe pack-size, although I'm still clueless about why it's appearing\nhere.\n\n> + struct revindex_entry *swap;\n> + int i;\n> +\n> + memset(pos, 0, BUCKETS * sizeof(*pos));\n\nAh, so that's why you used malloc there. Wait, shouldn't this be\nmemset(pos, 0, sizeof(*pos))?\n\n> + for (i = 0; i < n; i++)\n> + pos[BUCKET_FOR(a, i, bits)]++;\n\nOkay, so you know how many numbers are in each bucket.\n\n> + for (i = 1; i < BUCKETS; i++)\n> + pos[i] += pos[i-1];\n\nCumulative sums; right.\n\n> + for (i = n - 1; i >= 0; i--)\n> + b[--pos[BUCKET_FOR(a, i, bits)]] = a[i];\n\nClassical queue. You could've gone for something more complex, but I\ndon't think it would have been worth the extra complexity.\n\n> + swap = a;\n> + a = b;\n> + b = swap;\n\nWait a minute: why don't you just throw away b? You're going to\nrebuild the queue in the next iteration anyway, no? a is what is\nbeing sorted.\n\n> + /* And bump our bits for the next round. */\n> + bits += DIGIT_SIZE;\n\nI'd have gone for a nice for-loop.\n\n> + /*\n> + * If we ended with our data in the original array, great. If not,\n> + * we have to move it back from the temporary storage.\n> + */\n> + if (a != entries)\n> + memcpy(entries, tmp, n * sizeof(*entries));\n\nHow could a be different from entries? It has no memory allocated for\nitself, no? Why did you even create a, and not directly operate on\nentries?\n\n> + free(tmp);\n> + free(pos);\n\nOverall, I found it quite confusing :(\n\n> +#undef BUCKET_FOR\n\nWhy not DIGIT_SIZE and BUCKETS too, while at it?\n"},{"id":"223023","messageId":"CALkWK0=RtB2ddpGhZO0RAjzQXNfxHBE47bnp6KaVFz=Hicj8sw@mail.gmail.com","threadId":"34369","inReplyTo":"20130710114546.GF21963@sigill.intra.peff.net","subject":"Re: [PATCH 06/10] cat-file: add --batch-check=","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-07-10T14:51:15Z","receivedAt":"2013-07-10T14:51:15Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Jeff King wrote:\n> +If `--batch` or `--batch-check` is given, `cat-file` will read objects\n> +from stdin, one per line, and print information about them.\n> +\n> +You can specify the information shown for each object by using a custom\n> +``. The `` is copied literally to stdout for each\n> +object, with placeholders of the form `%(atom)` expanded, followed by a\n> +newline. The available atoms are:\n> +\n> +If no format is specified, the default format is `%(objectname)\n> +%(objecttype) %(objectsize)`.\n> +\n> +If `--batch` is specified, the object information is followed by the\n> +object contents (consisting of `%(objectsize)` bytes), followed by a\n> +newline.\n\nI find this slightly hideous, and would have expected an\n%(objectcontents) or similar.\n\nPerhaps --batch-check should become a non-configurable alias for\n--batch=\"%(objectname) %(objecttype) %(objectsize)\", and let --batch\ndefault to the format \"%(objectname) %(objecttype) %(objectsize)\n%(objectcontents)\".\n\nI'm frankly okay with not having --pretty, and making the output in\nthe non-batch mode non-configurable (does anyone care?).\n"},{"id":"223025","messageId":"CALkWK0mGMZPWowZ0ULNuGKD8w2Q=kN0nEGaOkuWoYKmzD5zGrw@mail.gmail.com","threadId":"34369","inReplyTo":"20130710114828.GH21963@sigill.intra.peff.net","subject":"Re: [PATCH 08/10] cat-file: split --batch input lines on whitespace","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-07-10T15:29:51Z","receivedAt":"2013-07-10T15:29:51Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Jeff King wrote:\n> git rev-list --objects HEAD |\n> git cat-file --batch-check='%(objectsize) %(text)'\n\nIf anything, I would have expected %(rest), not %(text). This atom is\nspecific to commands that accept input via stdin (i.e. not log, f-e-r,\nbranch, or anything else I can think of).\n\nAlso, this makes me wonder if %(field:0), %(field:1), and probably\n%(field:@) are good ideas. Even if we go down that road, I don't\nthink %(rest) is a problem per-se.\n"},{"id":"223027","messageId":"CA+sFfMeL1a1cQXj+3OXvp5hxLXz8Qc70U_+MMg4LOHcvuH4wcw@mail.gmail.com","threadId":"34369","inReplyTo":"20130710115557.GJ21963@sigill.intra.peff.net","subject":"Re: [PATCH 10/10] pack-revindex: radix-sort the revindex","fromName":"Brandon Casey","fromEmail":"drafnel@gmail.com","sentAt":"2013-07-10T17:10:16Z","receivedAt":"2013-07-10T17:10:16Z","isPatch":true,"sender":{"key":"drafnel@gmail.com","avatar":"https://avatars.githubusercontent.com/u/921167?v=4"},"body":"On Wed, Jul 10, 2013 at 4:55 AM, Jeff King wrote:\n> The pack revindex stores the offsets of the objects in the\n> pack in sorted order, allowing us to easily find the on-disk\n> size of each object. To compute it, we populate an array\n> with the offsets from the sha1-sorted idx file, and then use\n> qsort to order it by offsets.\n>\n> That does O(n log n) offset comparisons, and profiling shows\n> that we spend most of our time in cmp_offset. However, since\n> we are sorting on a simple off_t, we can use numeric sorts\n> that perform better. A radix sort can run in O(k*n), where k\n> is the number of \"digits\" in our number. For a 64-bit off_t,\n> using 16-bit \"digits\" gives us k=4.\n>\n> On the linux.git repo, with about 3M objects to sort, this\n> yields a 400% speedup. Here are the best-of-five numbers for\n> running \"echo HEAD | git cat-file --batch-disk-size\", which\n> is dominated by time spent building the pack revindex:\n>\n> before after\n> real 0m0.834s 0m0.204s\n> user 0m0.788s 0m0.164s\n> sys 0m0.040s 0m0.036s\n>\n> On a smaller repo, the radix sort would not be\n> as impressive (and could even be worse), as we are trading\n> the log(n) factor for the k=4 of the radix sort. However,\n> even on git.git, with 173K objects, it shows some\n> improvement:\n>\n> before after\n> real 0m0.046s 0m0.017s\n> user 0m0.036s 0m0.012s\n> sys 0m0.008s 0m0.000s\n\nk should only be 2 for git.git. I haven't packed in a while, but I\nthink it should all fit within 4G. :) The pathological case would be\na pack file with very few very very large objects, large enough to\npush the pack size over the 2^48 threshold so we'd have to do all four\nradixes.\n\nIt's probably worth mentioning here and/or in the code that k is\ndependent on the pack file size and that we can jump out early for\nsmall pack files. That's my favorite part of this code by the way. :)\n\n> Signed-off-by: Jeff King \n> ---\n> I changed a few things from the original, including:\n>\n> 1. We take an \"unsigned\" number of objects to match the fix in the\n> last patch.\n>\n> 2. The 16-bit \"digit\" size is factored out to a single place, which\n> avoids magic numbers and repeating ourselves.\n>\n> 3. The \"digits\" variable is renamed to \"bits\", which is more accurate.\n>\n> 4. The outer loop condition uses the simpler \"while (max >> bits)\".\n>\n> 5. We use memcpy instead of an open-coded loop to copy the whole array\n> at the end. The individual bucket-assignment is still done by\n> struct assignment. I haven't timed if memcpy would make a\n> difference there.\n>\n> 6. The 64K*sizeof(int) \"pos\" array is now heap-allocated, in case\n> there are platforms with a small stack.\n>\n> I re-ran my timings to make sure none of the above impacted them; it\n> turned out the same.\n>\n> pack-revindex.c | 84 +++++++++++++++++++++++++++++++++++++++++++++++++++++----\n> 1 file changed, 79 insertions(+), 5 deletions(-)\n>\n> diff --git a/pack-revindex.c b/pack-revindex.c\n> index 1aa9754..9365bc2 100644\n> --- a/pack-revindex.c\n> +++ b/pack-revindex.c\n> @@ -59,11 +59,85 @@ static int cmp_offset(const void *a_, const void *b_)\n> /* revindex elements are lazily initialized */\n> }\n>\n> -static int cmp_offset(const void *a_, const void *b_)\n> +/*\n> + * This is a least-significant-digit radix sort.\n> + */\n> +static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)\n> {\n> - const struct revindex_entry *a = a_;\n> - const struct revindex_entry *b = b_;\n> - return (a->offset < b->offset) ? -1 : (a->offset > b->offset) ? 1 : 0;\n> + /*\n> + * We use a \"digit\" size of 16 bits. That keeps our memory\n> + * usage reasonable, and we can generally (for a 4G or smaller\n> + * packfile) quit after two rounds of radix-sorting.\n> + */\n> +#define DIGIT_SIZE (16)\n> +#define BUCKETS (1 << DIGIT_SIZE)\n> + /*\n> + * We want to know the bucket that a[i] will go into when we are using\n> + * the digit that is N bits from the (least significant) end.\n> + */\n> +#define BUCKET_FOR(a, i, bits) (((a)[(i)].offset >> (bits)) & (BUCKETS-1))\n> +\n> + /*\n> + * We need O(n) temporary storage, so we sort back and forth between\n> + * the real array and our tmp storage. To keep them straight, we always\n> + * sort from \"a\" into buckets in \"b\".\n> + */\n> + struct revindex_entry *tmp = xcalloc(n, sizeof(*tmp));\n\nDidn't notice it the first time I read this, but do we really need\ncalloc here? Or will malloc do?\n\n> + struct revindex_entry *a = entries, *b = tmp;\n> + int bits = 0;\n> + unsigned *pos = xmalloc(BUCKETS * sizeof(*pos));\n> +\n> + while (max >> bits) {\n> + struct revindex_entry *swap;\n> + int i;\n\nYou forgot to make i unsigned. See below too...\n\n> +\n> + memset(pos, 0, BUCKETS * sizeof(*pos));\n> +\n> + /*\n> + * We want pos[i] to store the index of the last element that\n> + * will go in bucket \"i\" (actually one past the last element).\n> + * To do this, we first count the items that will go in each\n> + * bucket, which gives us a relative offset from the last\n> + * bucket. We can then cumulatively add the index from the\n> + * previous bucket to get the true index.\n> + */\n> + for (i = 0; i < n; i++)\n> + pos[BUCKET_FOR(a, i, bits)]++;\n> + for (i = 1; i < BUCKETS; i++)\n> + pos[i] += pos[i-1];\n> +\n> + /*\n> + * Now we can drop the elements into their correct buckets (in\n> + * our temporary array). We iterate the pos counter backwards\n> + * to avoid using an extra index to count up. And since we are\n> + * going backwards there, we must also go backwards through the\n> + * array itself, to keep the sort stable.\n> + */\n> + for (i = n - 1; i >= 0; i--)\n> + b[--pos[BUCKET_FOR(a, i, bits)]] = a[i];\n\n...which is why the above loop still works.\n\n> +\n> + /*\n> + * Now \"b\" contains the most sorted list, so we swap \"a\" and\n> + * \"b\" for the next iteration.\n> + */\n> + swap = a;\n> + a = b;\n> + b = swap;\n> +\n> + /* And bump our bits for the next round. */\n> + bits += DIGIT_SIZE;\n> + }\n> +\n> + /*\n> + * If we ended with our data in the original array, great. If not,\n> + * we have to move it back from the temporary storage.\n> + */\n> + if (a != entries)\n> + memcpy(entries, tmp, n * sizeof(*entries));\n> + free(tmp);\n> + free(pos);\n> +\n> +#undef BUCKET_FOR\n> }\n>\n> /*\n> @@ -108,7 +182,7 @@ static void create_pack_revindex(struct pack_revindex *rix)\n> */\n> rix->revindex[num_ent].offset = p->pack_size - 20;\n> rix->revindex[num_ent].nr = -1;\n> - qsort(rix->revindex, num_ent, sizeof(*rix->revindex), cmp_offset);\n> + sort_revindex(rix->revindex, num_ent, p->pack_size);\n> }\n>\n> struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs)\n> --\n> 1.8.3.rc3.24.gec82cb9\n"},{"id":"223050","messageId":"20130711110332.GA6015@sigill.intra.peff.net","threadId":"34369","inReplyTo":"CALkWK0=_6-RN2dHrhMdKu8nTyj1iwVe388Y57pOac17xhbqn5Q@mail.gmail.com","subject":"Re: [PATCH 10/10] pack-revindex: radix-sort the revindex","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-11T11:03:33Z","receivedAt":"2013-07-11T11:03:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 10, 2013 at 06:47:49PM +0530, Ramkumar Ramachandra wrote:\n\n> > For a 64-bit off_t, using 16-bit \"digits\" gives us k=4.\n> \n> Wait, isn't off_t a signed data type? Did you account for that in\n> your algorithm?\n\nIt is signed, but the values we are storing in the revindex are all\npositive file offsets. Right-shifting a positive signed type is\nexplicitly allowed in C.\n\n> > -static int cmp_offset(const void *a_, const void *b_)\n> > +/*\n> > + * This is a least-significant-digit radix sort.\n> > + */\n> \n> Any particular reason for choosing LSD, and not MSD?\n\nSimplicity. An MSD implementation should have the same algorithmic\ncomplexity and in theory, one can do MSD in-place. I'm happy enough with\nthe speedup here, but if you want to take a stab at beating my times\nwith MSD, please feel free.\n\nThe other \"usual\" downside of MSD is that it is typically not stable,\nbut we don't care about that here. We know that our sort keys are\nunique.\n\n> > +#define DIGIT_SIZE (16)\n> > +#define BUCKETS (1 << DIGIT_SIZE)\n> \n> Okay, NUMBER_OF_BUCKETS = 2^RADIX, and you choose a hex radix. Is\n> off_t guaranteed to be fixed-length though? I thought only the ones\n> in stdint.h were guaranteed to be fixed-length?\n\nI'm not sure what you mean by fixed-length. If you mean does it have the\nsame size on every platform, then no. It will typically be 32-bit on\nplatforms without largefile support, and 64-bit elsewhere. But it\nshouldn't matter. We'll first sort the entries by the lower 16 bits, and\nthen if we have more bits, by the next 16 bits, and so on. We quit when\nthe maximum value to sort (which we know ahead of time from the size of\nthe packfile) is smaller than the 16-bits we are on. So we don't need to\nknow the exact size of off_t, only the maximum value in our list (which\nmust, by definition, be smaller than what can be represented by off_t).\n\n> > + /*\n> > + * We want to know the bucket that a[i] will go into when we are using\n> > + * the digit that is N bits from the (least significant) end.\n> > + */\n> > +#define BUCKET_FOR(a, i, bits) (((a)[(i)].offset >> (bits)) & (BUCKETS-1))\n> \n> Ouch! This is unreadable. Just write an inline function instead? A\n> % would've been easier on the eyes, but you chose base-16.\n\nI specifically avoided an inline function because they are subject to\ncompiler settings. This isn't just \"it would be a bit faster if this got\ninlined, and OK otherwise\" but \"this would be horribly slow if not\ninlined\".\n\nI'm also not sure that\n\n static inline unsigned bucket_for(const struct revindex *a,\n unsigned i,\n unsigned bits)\n {\n return a[i].offset >> bits & (BUCKETS-1);\n }\n\nis actually any more readable.\n\nI'm not sure what you mean by base-16. No matter the radix digit size,\nas long as it is an integral number of bits, we can mask it off, which\nis more efficient than modulo. A good compiler should see that it\nis a constant and convert it to a bit-mask, but I'm not sure I agree\nthat modular arithmetic is more readable. This is fundamentally a\nbit-twiddling operation, as we are shifting and masking.\n\nI tried to explain it in the comment; suggestions to improve that are\nwelcome.\n\n> > + /*\n> > + * We need O(n) temporary storage, so we sort back and forth between\n> > + * the real array and our tmp storage. To keep them straight, we always\n> > + * sort from \"a\" into buckets in \"b\".\n> > + */\n> > + struct revindex_entry *tmp = xcalloc(n, sizeof(*tmp));\n> \n> Shouldn't this be sizeof (struct revindex_entry), since tmp hasn't\n> been declared yet?\n\nNo, the variable is declared (but uninitialized) in its initializer.\nDespite its syntax, sizeof() is not a function and does not care about\nthe state of the variable, only its type.\n\n> Also, s/n/revindex_nr/, and something more appropriate for tmp?\n\nWhat name would you suggest be be more appropriate for tmp?\n\n> > + int bits = 0;\n> > + unsigned *pos = xmalloc(BUCKETS * sizeof(*pos));\n> \n> sizeof(unsigned int), for clarity, if not anything else.\n\nI disagree; in general, I prefer using sizeof(*var) rather than\nsizeof(type), because it avoids repeating ourselves, and there is no\ncompile-time check that you have gotten it right.\n\nIn the initializer it is less important, because the type is right\nthere. But when you are later doing:\n\n memset(pos, 0, BUCKETS * sizeof(*pos));\n\nthis is much more robust. If somebody changes the type of pos, the\nmemset line does not need changed. If you used sizeof(unsigned), then\nthe code is now buggy (and the compiler cannot notice).\n\n> You picked malloc over calloc here, because you didn't want to incur\n> the extra cost of zero-initializing the memory?\n\nYes. We have to zero-initialize in each loop, so there is no point\nspending the extra effort on calloc.\n\nWe could also xcalloc inside each loop iteration, but since we need the\nsame-size allocation each time, I hoisted the malloc out of the loop.\n\n> Also, pos is the actual buckets array, I presume (hence unsigned,\n> because there can't be a negative number of keys in any bucket)?\n\nExactly. I called it \"pos\" rather than \"buckets\" because the goal is to\nget the start-position of each bucket (as explained in the comment in\nthe loop).\n\n> > + while (max >> bits) {\n> \n> No clue what max is. Looked at the caller and figured out that it's\n> the pack-size, although I'm still clueless about why it's appearing\n> here.\n\nIt's larger than the largest sort key in the array. On an LSD radix\nsort, we can stop sorting when we are looking at a radix digit whose\nvalue is larger than the max, because we know all of the entries will\nsimply have \"0\" in that digit.\n\nSo even if off_t is 64-bit, we can quit after the 32nd bit (i.e., k=2)\nif the packfile is smaller than 4G.\n\nAn MSD radix sort could do the same trick, but would obviously skip the\nzero digits at the beginning rather than the end.\n\n> > + struct revindex_entry *swap;\n> > + int i;\n> > +\n> > + memset(pos, 0, BUCKETS * sizeof(*pos));\n> \n> Ah, so that's why you used malloc there. Wait, shouldn't this be\n> memset(pos, 0, sizeof(*pos))?\n\nNo, that would zero only the first entry of the array. We allocated\nBUCKETS * sizeof(*pos) bytes, and we want to zero them all.\n\n> > + swap = a;\n> > + a = b;\n> > + b = swap;\n> \n> Wait a minute: why don't you just throw away b? You're going to\n> rebuild the queue in the next iteration anyway, no? a is what is\n> being sorted.\n\nFor each iteration, we need to sort into temporary storage. So you can\ndo it like:\n\n 1. sort entries into tmp\n\n 2. copy tmp back into entries\n\n 3. bump radix digit and goto 1\n\nBut you can eliminate the copy in step 2 if you instead go back and\nforth, like:\n\n 1. sort entries into tmp\n\n 2. bump radix digit\n\n 3. sort tmp into entries\n\n ...etc\n\nTo do that in a loop, we need an alias for \"the thing we are sorting\nfrom\" and \"the thing we are sorting to\". Hence the \"a\" and \"b\" pointers.\nPerhaps these comments make more sense now:\n\n+ /*\n+ * We need O(n) temporary storage, so we sort back and forth between\n+ * the real array and our tmp storage. To keep them straight, we always\n+ * sort from \"a\" into buckets in \"b\".\n+ */\n+ struct revindex_entry *tmp = xcalloc(n, sizeof(*tmp));\n+ struct revindex_entry *a = entries, *b = tmp;\n[...]\n+ /*\n+ * Now \"b\" contains the most sorted list, so we swap \"a\" and\n+ * \"b\" for the next iteration.\n+ */\n\n> > + /* And bump our bits for the next round. */\n> > + bits += DIGIT_SIZE;\n> \n> I'd have gone for a nice for-loop.\n\nYeah, that would look like:\n\n for (bits = 0; max >> bits; bits += DIGIT_SIZE) {\n ...\n }\n\nI don't really find one more readable than the other.\n\n> > + /*\n> > + * If we ended with our data in the original array, great. If not,\n> > + * we have to move it back from the temporary storage.\n> > + */\n> > + if (a != entries)\n> > + memcpy(entries, tmp, n * sizeof(*entries));\n> \n> How could a be different from entries? It has no memory allocated for\n> itself, no? Why did you even create a, and not directly operate on\n> entries?\n\nSee the back-and-forth explanation above.\n\n> > + free(tmp);\n> > + free(pos);\n> \n> Overall, I found it quite confusing :(\n\nClearly. It was confusing to write (especially because there are a\nnumber of optimizations, and because radix sort is not well known, at\nleast to me), which is why I tried to comment profusely. It seems quite\na few of them didn't help, as the answers to your questions were there.\nIf you have suggestions for improvement to the comments, I'm all ears.\n\n> > +#undef BUCKET_FOR\n> \n> Why not DIGIT_SIZE and BUCKETS too, while at it?\n\nI forgot. I added them later (they were originally magic numbers in the\ncode). Will add.\n\n-Peff\n"},{"id":"223051","messageId":"20130711111705.GB6015@sigill.intra.peff.net","threadId":"34369","inReplyTo":"CA+sFfMeL1a1cQXj+3OXvp5hxLXz8Qc70U_+MMg4LOHcvuH4wcw@mail.gmail.com","subject":"Re: [PATCH 10/10] pack-revindex: radix-sort the revindex","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-11T11:17:15Z","receivedAt":"2013-07-11T11:17:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 10, 2013 at 10:10:16AM -0700, Brandon Casey wrote:\n\n> > On the linux.git repo, with about 3M objects to sort, this\n> > yields a 400% speedup. Here are the best-of-five numbers for\n> > running \"echo HEAD | git cat-file --batch-disk-size\", which\n> > is dominated by time spent building the pack revindex:\n> >\n> > before after\n> > real 0m0.834s 0m0.204s\n> > user 0m0.788s 0m0.164s\n> > sys 0m0.040s 0m0.036s\n> >\n> > On a smaller repo, the radix sort would not be\n> > as impressive (and could even be worse), as we are trading\n> > the log(n) factor for the k=4 of the radix sort. However,\n> > even on git.git, with 173K objects, it shows some\n> > improvement:\n> >\n> > before after\n> > real 0m0.046s 0m0.017s\n> > user 0m0.036s 0m0.012s\n> > sys 0m0.008s 0m0.000s\n> \n> k should only be 2 for git.git. I haven't packed in a while, but I\n> think it should all fit within 4G. :) The pathological case would be\n> a pack file with very few very very large objects, large enough to\n> push the pack size over the 2^48 threshold so we'd have to do all four\n> radixes.\n\nYeah, even linux.git fits into k=2. And that does more or less explain\nthe numbers in both cases.\n\nFor git.git, With 173K objects, log(n) is ~18, so regular sort is 18n.\nWith a radix sort of k=2, which has a constant factor of 2 (you can see\nby looking at the code that we go through the list twice per radix), we\nhave 4n. So there should be a 4.5x speedup. We don't quite get that,\nwhich is probably due to the extra bookkeeping on the buckets.\n\nFor linux.git, with 3M objects, log(n) is ~22, so the speedup we hope\nfor is 5.5x. We end up with 4x.\n\n> It's probably worth mentioning here and/or in the code that k is\n> dependent on the pack file size and that we can jump out early for\n> small pack files. That's my favorite part of this code by the way. :)\n\nYeah, I agree it is probably worth mentioning along with the numbers; it\nis where half of our speedup is coming from. I think the \"max >> bits\"\nloop condition deserves to be commented, too. I'll add that.\n\nAlso note that my commit message still refers to \"--batch-disk-size\"\nwhich does not exist anymore. :) I didn't update the timings in the\ncommit message for my re-roll, but I did confirm that they are the same.\n\n> > + /*\n> > + * We need O(n) temporary storage, so we sort back and forth between\n> > + * the real array and our tmp storage. To keep them straight, we always\n> > + * sort from \"a\" into buckets in \"b\".\n> > + */\n> > + struct revindex_entry *tmp = xcalloc(n, sizeof(*tmp));\n> \n> Didn't notice it the first time I read this, but do we really need\n> calloc here? Or will malloc do?\n\nNo, a malloc should be fine. I doubt it matters much, but there's no\nreason not to go the cheap route.\n\n> > + struct revindex_entry *a = entries, *b = tmp;\n> > + int bits = 0;\n> > + unsigned *pos = xmalloc(BUCKETS * sizeof(*pos));\n> > +\n> > + while (max >> bits) {\n> > + struct revindex_entry *swap;\n> > + int i;\n> \n> You forgot to make i unsigned. See below too...\n\nOops. Thanks for catching.\n\n> > + /*\n> > + * Now we can drop the elements into their correct buckets (in\n> > + * our temporary array). We iterate the pos counter backwards\n> > + * to avoid using an extra index to count up. And since we are\n> > + * going backwards there, we must also go backwards through the\n> > + * array itself, to keep the sort stable.\n> > + */\n> > + for (i = n - 1; i >= 0; i--)\n> > + b[--pos[BUCKET_FOR(a, i, bits)]] = a[i];\n> \n> ...which is why the above loop still works.\n\nSince we are iterating by ones, I guess I can just compare to UINT_MAX.\n\n-Peff\n"},{"id":"223052","messageId":"20130711112413.GC6015@sigill.intra.peff.net","threadId":"34369","inReplyTo":"CALkWK0=RtB2ddpGhZO0RAjzQXNfxHBE47bnp6KaVFz=Hicj8sw@mail.gmail.com","subject":"Re: [PATCH 06/10] cat-file: add --batch-check=","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-11T11:24:13Z","receivedAt":"2013-07-11T11:24:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 10, 2013 at 08:21:15PM +0530, Ramkumar Ramachandra wrote:\n\n> Jeff King wrote:\n> > +If `--batch` or `--batch-check` is given, `cat-file` will read objects\n> > +from stdin, one per line, and print information about them.\n> > +\n> > +You can specify the information shown for each object by using a custom\n> > +``. The `` is copied literally to stdout for each\n> > +object, with placeholders of the form `%(atom)` expanded, followed by a\n> > +newline. The available atoms are:\n> > +\n> > +If no format is specified, the default format is `%(objectname)\n> > +%(objecttype) %(objectsize)`.\n> > +\n> > +If `--batch` is specified, the object information is followed by the\n> > +object contents (consisting of `%(objectsize)` bytes), followed by a\n> > +newline.\n> \n> I find this slightly hideous, and would have expected an\n> %(objectcontents) or similar.\n\nI looked into doing that, but it makes the code significantly more\ncomplicated, assuming you do not want to copy the full object contents\nin memory. You cannot use strbuf_expand, and you need to worry about\nbuffering/flushing more (you do not want to write() each individual\nitem, but if you are using printf(), you need to flush before using the\nunbuffered streaming interface).\n\nMy thinking was to leave it until somebody actually wants it, at which\npoint they can do the necessary refactoring (and hopefully this would be\npart of unifying it with other format-parsers).\n\nIf we were designing from scratch and this was the difference between\nhaving \"--batch-check\" and \"--batch\", or having a single \"--batch\", I'd\ncare more about doing %(objectcontents) right away. But because we must\nsupport the historical --batch/--batch-check distinction anyway, I don't\nthink this is any worse.\n\n-Peff\n"},{"id":"223057","messageId":"20130711113653.GD6015@sigill.intra.peff.net","threadId":"34369","inReplyTo":"CALkWK0mGMZPWowZ0ULNuGKD8w2Q=kN0nEGaOkuWoYKmzD5zGrw@mail.gmail.com","subject":"Re: [PATCH 08/10] cat-file: split --batch input lines on whitespace","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-11T11:36:53Z","receivedAt":"2013-07-11T11:36:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 10, 2013 at 08:59:51PM +0530, Ramkumar Ramachandra wrote:\n\n> Jeff King wrote:\n> > git rev-list --objects HEAD |\n> > git cat-file --batch-check='%(objectsize) %(text)'\n> \n> If anything, I would have expected %(rest), not %(text). This atom is\n> specific to commands that accept input via stdin (i.e. not log, f-e-r,\n> branch, or anything else I can think of).\n\nI considered %(rest) as well. I don't have a strong preference.\n\n> Also, this makes me wonder if %(field:0), %(field:1), and probably\n> %(field:@) are good ideas. Even if we go down that road, I don't\n> think %(rest) is a problem per-se.\n\nI don't have a use for them, and even if we want to add them later, you\nwould still want to support %(rest) for when the user wants to take the\nrest of the line verbatim without caring about field-splitting.\n\nTo be honest, I do not see %(field) as all that useful. If you want to\ngo about rearranging or selecting fields, that is what \"cut\" (or \"awk\")\nis for. Having fields means you need to specify field separators, and\nhow runs of separators are treated. Other tools already do this.\n\nSo it would (at best) save you from an extra cut invocation, whereas\n%(rest) gets you out of doing something much more difficult. Without it,\ninformation is lost from your pipeline (so you have to have tee to a\nseparate pipeline, and then reassemble the pieces).\n\n-Peff\n"},{"id":"223062","messageId":"20130711121600.GA18710@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130710115557.GJ21963@sigill.intra.peff.net","subject":"[PATCHv3 10/10] pack-revindex: radix-sort the revindex","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-11T12:16:00Z","receivedAt":"2013-07-11T12:16:00Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":" Here's an update of the radix-sort patch. It fixes the \"unsigned\" issue\n Brandon pointed out, along with a few other comment/naming/style fixes.\n I also updated the commit message with more explanation of the\n timings.\n \n The interdiff is:\n \n diff --git a/pack-revindex.c b/pack-revindex.c\n index 9365bc2..b4d2b35 100644\n --- a/pack-revindex.c\n +++ b/pack-revindex.c\n @@ -61,6 +61,10 @@ static void init_pack_revindex(void)\n \n /*\n * This is a least-significant-digit radix sort.\n + *\n + * It sorts each of the \"n\" items in \"entries\" by its offset field. The \"max\"\n + * parameter must be at least as large as the largest offset in the array,\n + * and lets us quit the sort early.\n */\n static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)\n {\n @@ -78,18 +82,25 @@ static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)\n #define BUCKET_FOR(a, i, bits) (((a)[(i)].offset >> (bits)) & (BUCKETS-1))\n \n \t/*\n -\t * We need O(n) temporary storage, so we sort back and forth between\n -\t * the real array and our tmp storage. To keep them straight, we always\n -\t * sort from \"a\" into buckets in \"b\".\n +\t * We need O(n) temporary storage. Rather than do an extra copy of the\n +\t * partial results into \"entries\", we sort back and forth between the\n +\t * real array and temporary storage. In each iteration of the loop, we\n +\t * keep track of them with alias pointers, always sorting from \"from\"\n +\t * to \"to\".\n \t */\n -\tstruct revindex_entry *tmp = xcalloc(n, sizeof(*tmp));\n -\tstruct revindex_entry *a = entries, *b = tmp;\n -\tint bits = 0;\n +\tstruct revindex_entry *tmp = xmalloc(n * sizeof(*tmp));\n +\tstruct revindex_entry *from = entries, *to = tmp;\n +\tint bits;\n \tunsigned *pos = xmalloc(BUCKETS * sizeof(*pos));\n \n -\twhile (max >> bits) {\n +\t/*\n +\t * If (max >> bits) is zero, then we know that the radix digit we are\n +\t * on (and any higher) will be zero for all entries, and our loop will\n +\t * be a no-op, as everybody lands in the same zero-th bucket.\n +\t */\n +\tfor (bits = 0; max >> bits; bits += DIGIT_SIZE) {\n \t\tstruct revindex_entry *swap;\n -\t\tint i;\n +\t\tunsigned i;\n \n \t\tmemset(pos, 0, BUCKETS * sizeof(*pos));\n \n @@ -102,7 +113,7 @@ static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)\n \t\t * previous bucket to get the true index.\n \t\t */\n \t\tfor (i = 0; i < n; i++)\n -\t\t\tpos[BUCKET_FOR(a, i, bits)]++;\n +\t\t\tpos[BUCKET_FOR(from, i, bits)]++;\n \t\tfor (i = 1; i < BUCKETS; i++)\n \t\t\tpos[i] += pos[i-1];\n \n @@ -112,32 +123,37 @@ static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)\n \t\t * to avoid using an extra index to count up. And since we are\n \t\t * going backwards there, we must also go backwards through the\n \t\t * array itself, to keep the sort stable.\n +\t\t *\n +\t\t * Note that we use an unsigned iterator to make sure we can\n +\t\t * handle 2^32-1 objects, even on a 32-bit system. But this\n +\t\t * means we cannot use the more obvious \"i >= 0\" loop condition\n +\t\t * for counting backwards, and must instead check for\n +\t\t * wrap-around with UINT_MAX.\n \t\t */\n -\t\tfor (i = n - 1; i >= 0; i--)\n -\t\t\tb[--pos[BUCKET_FOR(a, i, bits)]] = a[i];\n +\t\tfor (i = n - 1; i != UINT_MAX; i--)\n +\t\t\tto[--pos[BUCKET_FOR(from, i, bits)]] = from[i];\n \n \t\t/*\n -\t\t * Now \"b\" contains the most sorted list, so we swap \"a\" and\n -\t\t * \"b\" for the next iteration.\n +\t\t * Now \"to\" contains the most sorted list, so we swap \"from\" and\n +\t\t * \"to\" for the next iteration.\n \t\t */\n -\t\tswap = a;\n -\t\ta = b;\n -\t\tb = swap;\n -\n -\t\t/* And bump our bits for the next round. */\n -\t\tbits += DIGIT_SIZE;\n +\t\tswap = from;\n +\t\tfrom = to;\n +\t\tto = swap;\n \t}\n \n \t/*\n \t * If we ended with our data in the original array, great. If not,\n \t * we have to move it back from the temporary storage.\n \t */\n -\tif (a != entries)\n +\tif (from != entries)\n \t\tmemcpy(entries, tmp, n * sizeof(*entries));\n \tfree(tmp);\n \tfree(pos);\n \n #undef BUCKET_FOR\n +#undef BUCKETS\n +#undef DIGIT_SIZE\n }\n \n /*\n\n-- >8 --\nSubject: [PATCH] pack-revindex: radix-sort the revindex\n\nThe pack revindex stores the offsets of the objects in the\npack in sorted order, allowing us to easily find the on-disk\nsize of each object. To compute it, we populate an array\nwith the offsets from the sha1-sorted idx file, and then use\nqsort to order it by offsets.\n\nThat does O(n log n) offset comparisons, and profiling shows\nthat we spend most of our time in cmp_offset. However, since\nwe are sorting on a simple off_t, we can use numeric sorts\nthat perform better. A radix sort can run in O(k*n), where k\nis the number of \"digits\" in our number. For a 64-bit off_t,\nusing 16-bit \"digits\" gives us k=4.\n\nOn the linux.git repo, with about 3M objects to sort, this\nyields a 400% speedup. Here are the best-of-five numbers for\nrunning\n\n echo HEAD | git cat-file --batch-check=\"%(objectsize:disk)\n\non a fully packed repository, which is dominated by time\nspent building the pack revindex:\n\n before after\n real 0m0.834s 0m0.204s\n user 0m0.788s 0m0.164s\n sys 0m0.040s 0m0.036s\n\nThis matches our algorithmic expectations. log(3M) is ~21.5,\nso a traditional sort is ~21.5n. Our radix sort runs in k*n,\nwhere k is the number of radix digits. In the worst case,\nthis is k=4 for a 64-bit off_t, but we can quit early when\nthe largest value to be sorted is smaller. For any\nrepository under 4G, k=2. Our algorithm makes two passes\nover the list per radix digit, so we end up with 4n. That\nshould yield ~5.3x speedup. We see 4x here; the difference\nis probably due to the extra bucket book-keeping the radix\nsort has to do.\n\nOn a smaller repo, the difference is less impressive, as\nlog(n) is smaller. For git.git, with 173K objects (but still\nk=2), we see a 2.7x improvement:\n\n before after\n real 0m0.046s 0m0.017s\n user 0m0.036s 0m0.012s\n sys 0m0.008s 0m0.000s\n\nOn even tinier repos (e.g., a few hundred objects), the\nspeedup goes away entirely, as the small advantage of the\nradix sort gets erased by the book-keeping costs (and at\nthose sizes, the cost to generate the the rev-index gets\nlost in the noise anyway).\n\nSigned-off-by: Jeff King \n---\n pack-revindex.c | 100 +++++++++++++++++++++++++++++++++++++++++++++++++++++---\n 1 file changed, 95 insertions(+), 5 deletions(-)\n\ndiff --git a/pack-revindex.c b/pack-revindex.c\nindex 1aa9754..b4d2b35 100644\n--- a/pack-revindex.c\n+++ b/pack-revindex.c\n@@ -59,11 +59,101 @@ static int cmp_offset(const void *a_, const void *b_)\n \t/* revindex elements are lazily initialized */\n }\n \n-static int cmp_offset(const void *a_, const void *b_)\n+/*\n+ * This is a least-significant-digit radix sort.\n+ *\n+ * It sorts each of the \"n\" items in \"entries\" by its offset field. The \"max\"\n+ * parameter must be at least as large as the largest offset in the array,\n+ * and lets us quit the sort early.\n+ */\n+static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)\n {\n-\tconst struct revindex_entry *a = a_;\n-\tconst struct revindex_entry *b = b_;\n-\treturn (a->offset < b->offset) ? -1 : (a->offset > b->offset) ? 1 : 0;\n+\t/*\n+\t * We use a \"digit\" size of 16 bits. That keeps our memory\n+\t * usage reasonable, and we can generally (for a 4G or smaller\n+\t * packfile) quit after two rounds of radix-sorting.\n+\t */\n+#define DIGIT_SIZE (16)\n+#define BUCKETS (1 << DIGIT_SIZE)\n+\t/*\n+\t * We want to know the bucket that a[i] will go into when we are using\n+\t * the digit that is N bits from the (least significant) end.\n+\t */\n+#define BUCKET_FOR(a, i, bits) (((a)[(i)].offset >> (bits)) & (BUCKETS-1))\n+\n+\t/*\n+\t * We need O(n) temporary storage. Rather than do an extra copy of the\n+\t * partial results into \"entries\", we sort back and forth between the\n+\t * real array and temporary storage. In each iteration of the loop, we\n+\t * keep track of them with alias pointers, always sorting from \"from\"\n+\t * to \"to\".\n+\t */\n+\tstruct revindex_entry *tmp = xmalloc(n * sizeof(*tmp));\n+\tstruct revindex_entry *from = entries, *to = tmp;\n+\tint bits;\n+\tunsigned *pos = xmalloc(BUCKETS * sizeof(*pos));\n+\n+\t/*\n+\t * If (max >> bits) is zero, then we know that the radix digit we are\n+\t * on (and any higher) will be zero for all entries, and our loop will\n+\t * be a no-op, as everybody lands in the same zero-th bucket.\n+\t */\n+\tfor (bits = 0; max >> bits; bits += DIGIT_SIZE) {\n+\t\tstruct revindex_entry *swap;\n+\t\tunsigned i;\n+\n+\t\tmemset(pos, 0, BUCKETS * sizeof(*pos));\n+\n+\t\t/*\n+\t\t * We want pos[i] to store the index of the last element that\n+\t\t * will go in bucket \"i\" (actually one past the last element).\n+\t\t * To do this, we first count the items that will go in each\n+\t\t * bucket, which gives us a relative offset from the last\n+\t\t * bucket. We can then cumulatively add the index from the\n+\t\t * previous bucket to get the true index.\n+\t\t */\n+\t\tfor (i = 0; i < n; i++)\n+\t\t\tpos[BUCKET_FOR(from, i, bits)]++;\n+\t\tfor (i = 1; i < BUCKETS; i++)\n+\t\t\tpos[i] += pos[i-1];\n+\n+\t\t/*\n+\t\t * Now we can drop the elements into their correct buckets (in\n+\t\t * our temporary array). We iterate the pos counter backwards\n+\t\t * to avoid using an extra index to count up. And since we are\n+\t\t * going backwards there, we must also go backwards through the\n+\t\t * array itself, to keep the sort stable.\n+\t\t *\n+\t\t * Note that we use an unsigned iterator to make sure we can\n+\t\t * handle 2^32-1 objects, even on a 32-bit system. But this\n+\t\t * means we cannot use the more obvious \"i >= 0\" loop condition\n+\t\t * for counting backwards, and must instead check for\n+\t\t * wrap-around with UINT_MAX.\n+\t\t */\n+\t\tfor (i = n - 1; i != UINT_MAX; i--)\n+\t\t\tto[--pos[BUCKET_FOR(from, i, bits)]] = from[i];\n+\n+\t\t/*\n+\t\t * Now \"to\" contains the most sorted list, so we swap \"from\" and\n+\t\t * \"to\" for the next iteration.\n+\t\t */\n+\t\tswap = from;\n+\t\tfrom = to;\n+\t\tto = swap;\n+\t}\n+\n+\t/*\n+\t * If we ended with our data in the original array, great. If not,\n+\t * we have to move it back from the temporary storage.\n+\t */\n+\tif (from != entries)\n+\t\tmemcpy(entries, tmp, n * sizeof(*entries));\n+\tfree(tmp);\n+\tfree(pos);\n+\n+#undef BUCKET_FOR\n+#undef BUCKETS\n+#undef DIGIT_SIZE\n }\n \n /*\n@@ -108,7 +198,7 @@ static void create_pack_revindex(struct pack_revindex *rix)\n \t */\n \trix->revindex[num_ent].offset = p->pack_size - 20;\n \trix->revindex[num_ent].nr = -1;\n-\tqsort(rix->revindex, num_ent, sizeof(*rix->revindex), cmp_offset);\n+\tsort_revindex(rix->revindex, num_ent, p->pack_size);\n }\n \n struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs)\n-- \n1.8.3.rc3.24.gec82cb9\n"},{"id":"223080","messageId":"7vhag1rr5a.fsf@alter.siamese.dyndns.org","threadId":"34369","inReplyTo":"20130710110402.GD9724@sigill.intra.peff.net","subject":"Re: [PATCH 3/4] cat-file: add --batch-disk-sizes option","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-07-11T16:35:29Z","receivedAt":"2013-07-11T16:35:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I started on this, and it turned out not to really be any simpler....\n> So I went ahead with the full formats for my re-roll. It turned out\n> pretty reasonable, I think.\n\nThanks.\n"},{"id":"223088","messageId":"7vvc4hq9hs.fsf@alter.siamese.dyndns.org","threadId":"34369","inReplyTo":"20130711113653.GD6015@sigill.intra.peff.net","subject":"Re: [PATCH 08/10] cat-file: split --batch input lines on whitespace","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-07-11T17:42:07Z","receivedAt":"2013-07-11T17:42:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Wed, Jul 10, 2013 at 08:59:51PM +0530, Ramkumar Ramachandra wrote:\n>\n>> Jeff King wrote:\n>> > git rev-list --objects HEAD |\n>> > git cat-file --batch-check='%(objectsize) %(text)'\n>> \n>> If anything, I would have expected %(rest), not %(text). This atom is\n>> specific to commands that accept input via stdin (i.e. not log, f-e-r,\n>> branch, or anything else I can think of).\n>\n> I considered %(rest) as well. I don't have a strong preference.\n>\n>> Also, this makes me wonder if %(field:0), %(field:1), and probably\n>> %(field:@) are good ideas. Even if we go down that road, I don't\n>> think %(rest) is a problem per-se.\n>\n> I don't have a use for them, and even if we want to add them later, you\n> would still want to support %(rest) for when the user wants to take the\n> rest of the line verbatim without caring about field-splitting.\n>\n> To be honest, I do not see %(field) as all that useful. If you want to\n> go about rearranging or selecting fields, that is what \"cut\" (or \"awk\")\n> is for. Having fields means you need to specify field separators, and\n> how runs of separators are treated. Other tools already do this.\n\nVery true, and more importantly, you cannot still say \"my input\nobject name is at field N, not at the beginning\", so that makes it\ndoubly dubious how %(field:$n) would be any useful.\n\n> So it would (at best) save you from an extra cut invocation, whereas\n> %(rest) gets you out of doing something much more difficult. Without it,\n> information is lost from your pipeline (so you have to have tee to a\n> separate pipeline, and then reassemble the pieces).\n"},{"id":"223094","messageId":"20130711204559.GA11399@sigill.intra.peff.net","threadId":"34369","inReplyTo":"20130711113653.GD6015@sigill.intra.peff.net","subject":"[PATCHv3 08/10] cat-file: split --batch input lines on whitespace","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-11T20:45:59Z","receivedAt":"2013-07-11T20:45:59Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jul 11, 2013 at 07:36:53AM -0400, Jeff King wrote:\n\n> On Wed, Jul 10, 2013 at 08:59:51PM +0530, Ramkumar Ramachandra wrote:\n> \n> > Jeff King wrote:\n> > > git rev-list --objects HEAD |\n> > > git cat-file --batch-check='%(objectsize) %(text)'\n> > \n> > If anything, I would have expected %(rest), not %(text). This atom is\n> > specific to commands that accept input via stdin (i.e. not log, f-e-r,\n> > branch, or anything else I can think of).\n> \n> I considered %(rest) as well. I don't have a strong preference.\n\nHere is the patch re-rolled with s/text/rest/.\n\nJunio, that makes this and 10/10 the only \"v3\" updates. Let me know if\nit would be simpler to just resend the whole series.\n\n-- >8 --\nSubject: [PATCH] cat-file: split --batch input lines on whitespace\n\nIf we get an input line to --batch or --batch-check that\nlooks like \"HEAD foo bar\", we will currently feed the whole\nthing to get_sha1(). This means that to use --batch-check\nwith `rev-list --objects`, one must pre-process the input,\nlike:\n\n git rev-list --objects HEAD |\n cut -d' ' -f1 |\n git cat-file --batch-check\n\nBesides being more typing and slightly less efficient to\ninvoke `cut`, the result loses information: we no longer\nknow which path each object was found at.\n\nThis patch teaches cat-file to split input lines at the\nfirst whitespace. Everything to the left of the whitespace\nis considered an object name, and everything to the right is\nmade available as the %(reset) atom. So you can now do:\n\n git rev-list --objects HEAD |\n git cat-file --batch-check='%(objectsize) %(rest)'\n\nto collect object sizes at particular paths.\n\nEven if %(rest) is not used, we always do the whitespace\nsplit (which means you can simply eliminate the `cut`\ncommand from the first example above).\n\nThis whitespace split is backwards compatible for any\nreasonable input. Object names cannot contain spaces, so any\ninput with spaces would have resulted in a \"missing\" line.\nThe only input hurt is if somebody really expected input of\nthe form \"HEAD is a fine-looking ref!\" to fail; it will now\nparse HEAD, and make \"is a fine-looking ref!\" available as\n%(rest).\n\nSigned-off-by: Jeff King \n---\n Documentation/git-cat-file.txt | 10 ++++++++--\n builtin/cat-file.c | 20 +++++++++++++++++++-\n t/t1006-cat-file.sh | 7 +++++++\n 3 files changed, 34 insertions(+), 3 deletions(-)\n\ndiff --git a/Documentation/git-cat-file.txt b/Documentation/git-cat-file.txt\nindex 06bdc43..68691d4 100644\n--- a/Documentation/git-cat-file.txt\n+++ b/Documentation/git-cat-file.txt\n@@ -88,8 +88,10 @@ from stdin, one per line, and print information about them.\n If `--batch` or `--batch-check` is given, `cat-file` will read objects\n from stdin, one per line, and print information about them.\n \n-Each line is considered as a whole object name, and is parsed as if\n-given to linkgit:git-rev-parse[1].\n+Each line is split at the first whitespace boundary. All characters\n+before that whitespace are considered as a whole object name, and are\n+parsed as if given to linkgit:git-rev-parse[1]. Characters after that\n+whitespace can be accessed using the `%(rest)` atom (see below).\n \n You can specify the information shown for each object by using a custom\n ``. The `` is copied literally to stdout for each\n@@ -110,6 +112,10 @@ newline. The available atoms are:\n \tThe size, in bytes, that the object takes up on disk. See the\n \tnote about on-disk sizes in the `CAVEATS` section below.\n \n+`rest`::\n+\tThe text (if any) found after the first run of whitespace on the\n+\tinput line (i.e., the \"rest\" of the line).\n+\n If no format is specified, the default format is `%(objectname)\n %(objecttype) %(objectsize)`.\n \ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 11fa8c0..0e64b41 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -119,6 +119,7 @@ struct expand_data {\n \tenum object_type type;\n \tunsigned long size;\n \tunsigned long disk_size;\n+\tconst char *rest;\n \n \t/*\n \t * If mark_query is true, we do not expand anything, but rather\n@@ -161,6 +162,9 @@ static void expand_atom(struct strbuf *sb, const char *atom, int len,\n \t\t\tdata->info.disk_sizep = &data->disk_size;\n \t\telse\n \t\t\tstrbuf_addf(sb, \"%lu\", data->disk_size);\n+\t} else if (is_atom(\"rest\", atom, len)) {\n+\t\tif (!data->mark_query && data->rest)\n+\t\t\tstrbuf_addstr(sb, data->rest);\n \t} else\n \t\tdie(\"unknown format element: %.*s\", len, atom);\n }\n@@ -263,7 +267,21 @@ static int batch_objects(struct batch_options *opt)\n \tdata.mark_query = 0;\n \n \twhile (strbuf_getline(&buf, stdin, '\\n') != EOF) {\n-\t\tint error = batch_one_object(buf.buf, opt, &data);\n+\t\tchar *p;\n+\t\tint error;\n+\n+\t\t/*\n+\t\t * Split at first whitespace, tying off the beginning of the\n+\t\t * string and saving the remainder (or NULL) in data.rest.\n+\t\t */\n+\t\tp = strpbrk(buf.buf, \" \\t\");\n+\t\tif (p) {\n+\t\t\twhile (*p && strchr(\" \\t\", *p))\n+\t\t\t\t*p++ = '\\0';\n+\t\t}\n+\t\tdata.rest = p;\n+\n+\t\terror = batch_one_object(buf.buf, opt, &data);\n \t\tif (error)\n \t\t\treturn error;\n \t}\ndiff --git a/t/t1006-cat-file.sh b/t/t1006-cat-file.sh\nindex 4e911fb..d499d02 100755\n--- a/t/t1006-cat-file.sh\n+++ b/t/t1006-cat-file.sh\n@@ -78,6 +78,13 @@ $content\"\n \techo $sha1 | git cat-file --batch-check=\"%(objecttype) %(objectname)\" >actual &&\n \ttest_cmp expect actual\n '\n+\n+ test_expect_success '--batch-check with %(rest)' '\n+\techo \"$type this is some extra content\" >expect &&\n+\techo \"$sha1 this is some extra content\" |\n+\t\tgit cat-file --batch-check=\"%(objecttype) %(rest)\" >actual &&\n+\ttest_cmp expect actual\n+ '\n }\n \n hello_content=\"Hello World\"\n-- \n1.8.3.rc3.24.gec82cb9\n"},{"id":"223096","messageId":"CA+sFfMeTBb6Eu6cQ4LHrTxLwA-pL573ey2SMCb16TzBP00WrqQ@mail.gmail.com","threadId":"34369","inReplyTo":"20130711121600.GA18710@sigill.intra.peff.net","subject":"Re: [PATCHv3 10/10] pack-revindex: radix-sort the revindex","fromName":"Brandon Casey","fromEmail":"drafnel@gmail.com","sentAt":"2013-07-11T21:12:04Z","receivedAt":"2013-07-11T21:12:04Z","isPatch":false,"sender":{"key":"drafnel@gmail.com","avatar":"https://avatars.githubusercontent.com/u/921167?v=4"},"body":"On Thu, Jul 11, 2013 at 5:16 AM, Jeff King wrote:\n> Here's an update of the radix-sort patch. It fixes the \"unsigned\" issue\n> Brandon pointed out, along with a few other comment/naming/style fixes.\n> I also updated the commit message with more explanation of the\n> timings.\n\nVery nice.\n\nFor what it's worth:\n\nReviewed-by: Brandon Casey \n\n\n\n> The interdiff is:\n>\n> diff --git a/pack-revindex.c b/pack-revindex.c\n> index 9365bc2..b4d2b35 100644\n> --- a/pack-revindex.c\n> +++ b/pack-revindex.c\n> @@ -61,6 +61,10 @@ static void init_pack_revindex(void)\n>\n> /*\n> * This is a least-significant-digit radix sort.\n> + *\n> + * It sorts each of the \"n\" items in \"entries\" by its offset field. The \"max\"\n> + * parameter must be at least as large as the largest offset in the array,\n> + * and lets us quit the sort early.\n> */\n> static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)\n> {\n> @@ -78,18 +82,25 @@ static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)\n> #define BUCKET_FOR(a, i, bits) (((a)[(i)].offset >> (bits)) & (BUCKETS-1))\n>\n> /*\n> - * We need O(n) temporary storage, so we sort back and forth between\n> - * the real array and our tmp storage. To keep them straight, we always\n> - * sort from \"a\" into buckets in \"b\".\n> + * We need O(n) temporary storage. Rather than do an extra copy of the\n> + * partial results into \"entries\", we sort back and forth between the\n> + * real array and temporary storage. In each iteration of the loop, we\n> + * keep track of them with alias pointers, always sorting from \"from\"\n> + * to \"to\".\n> */\n> - struct revindex_entry *tmp = xcalloc(n, sizeof(*tmp));\n> - struct revindex_entry *a = entries, *b = tmp;\n> - int bits = 0;\n> + struct revindex_entry *tmp = xmalloc(n * sizeof(*tmp));\n> + struct revindex_entry *from = entries, *to = tmp;\n> + int bits;\n> unsigned *pos = xmalloc(BUCKETS * sizeof(*pos));\n>\n> - while (max >> bits) {\n> + /*\n> + * If (max >> bits) is zero, then we know that the radix digit we are\n> + * on (and any higher) will be zero for all entries, and our loop will\n> + * be a no-op, as everybody lands in the same zero-th bucket.\n> + */\n> + for (bits = 0; max >> bits; bits += DIGIT_SIZE) {\n> struct revindex_entry *swap;\n> - int i;\n> + unsigned i;\n>\n> memset(pos, 0, BUCKETS * sizeof(*pos));\n>\n> @@ -102,7 +113,7 @@ static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)\n> * previous bucket to get the true index.\n> */\n> for (i = 0; i < n; i++)\n> - pos[BUCKET_FOR(a, i, bits)]++;\n> + pos[BUCKET_FOR(from, i, bits)]++;\n> for (i = 1; i < BUCKETS; i++)\n> pos[i] += pos[i-1];\n>\n> @@ -112,32 +123,37 @@ static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)\n> * to avoid using an extra index to count up. And since we are\n> * going backwards there, we must also go backwards through the\n> * array itself, to keep the sort stable.\n> + *\n> + * Note that we use an unsigned iterator to make sure we can\n> + * handle 2^32-1 objects, even on a 32-bit system. But this\n> + * means we cannot use the more obvious \"i >= 0\" loop condition\n> + * for counting backwards, and must instead check for\n> + * wrap-around with UINT_MAX.\n> */\n> - for (i = n - 1; i >= 0; i--)\n> - b[--pos[BUCKET_FOR(a, i, bits)]] = a[i];\n> + for (i = n - 1; i != UINT_MAX; i--)\n> + to[--pos[BUCKET_FOR(from, i, bits)]] = from[i];\n>\n> /*\n> - * Now \"b\" contains the most sorted list, so we swap \"a\" and\n> - * \"b\" for the next iteration.\n> + * Now \"to\" contains the most sorted list, so we swap \"from\" and\n> + * \"to\" for the next iteration.\n> */\n> - swap = a;\n> - a = b;\n> - b = swap;\n> -\n> - /* And bump our bits for the next round. */\n> - bits += DIGIT_SIZE;\n> + swap = from;\n> + from = to;\n> + to = swap;\n> }\n>\n> /*\n> * If we ended with our data in the original array, great. If not,\n> * we have to move it back from the temporary storage.\n> */\n> - if (a != entries)\n> + if (from != entries)\n> memcpy(entries, tmp, n * sizeof(*entries));\n> free(tmp);\n> free(pos);\n>\n> #undef BUCKET_FOR\n> +#undef BUCKETS\n> +#undef DIGIT_SIZE\n> }\n>\n> /*\n>\n> -- >8 --\n> Subject: [PATCH] pack-revindex: radix-sort the revindex\n>\n> The pack revindex stores the offsets of the objects in the\n> pack in sorted order, allowing us to easily find the on-disk\n> size of each object. To compute it, we populate an array\n> with the offsets from the sha1-sorted idx file, and then use\n> qsort to order it by offsets.\n>\n> That does O(n log n) offset comparisons, and profiling shows\n> that we spend most of our time in cmp_offset. However, since\n> we are sorting on a simple off_t, we can use numeric sorts\n> that perform better. A radix sort can run in O(k*n), where k\n> is the number of \"digits\" in our number. For a 64-bit off_t,\n> using 16-bit \"digits\" gives us k=4.\n>\n> On the linux.git repo, with about 3M objects to sort, this\n> yields a 400% speedup. Here are the best-of-five numbers for\n> running\n>\n> echo HEAD | git cat-file --batch-check=\"%(objectsize:disk)\n>\n> on a fully packed repository, which is dominated by time\n> spent building the pack revindex:\n>\n> before after\n> real 0m0.834s 0m0.204s\n> user 0m0.788s 0m0.164s\n> sys 0m0.040s 0m0.036s\n>\n> This matches our algorithmic expectations. log(3M) is ~21.5,\n> so a traditional sort is ~21.5n. Our radix sort runs in k*n,\n> where k is the number of radix digits. In the worst case,\n> this is k=4 for a 64-bit off_t, but we can quit early when\n> the largest value to be sorted is smaller. For any\n> repository under 4G, k=2. Our algorithm makes two passes\n> over the list per radix digit, so we end up with 4n. That\n> should yield ~5.3x speedup. We see 4x here; the difference\n> is probably due to the extra bucket book-keeping the radix\n> sort has to do.\n>\n> On a smaller repo, the difference is less impressive, as\n> log(n) is smaller. For git.git, with 173K objects (but still\n> k=2), we see a 2.7x improvement:\n>\n> before after\n> real 0m0.046s 0m0.017s\n> user 0m0.036s 0m0.012s\n> sys 0m0.008s 0m0.000s\n>\n> On even tinier repos (e.g., a few hundred objects), the\n> speedup goes away entirely, as the small advantage of the\n> radix sort gets erased by the book-keeping costs (and at\n> those sizes, the cost to generate the the rev-index gets\n> lost in the noise anyway).\n>\n> Signed-off-by: Jeff King \n> ---\n> pack-revindex.c | 100 +++++++++++++++++++++++++++++++++++++++++++++++++++++---\n> 1 file changed, 95 insertions(+), 5 deletions(-)\n>\n> diff --git a/pack-revindex.c b/pack-revindex.c\n> index 1aa9754..b4d2b35 100644\n> --- a/pack-revindex.c\n> +++ b/pack-revindex.c\n> @@ -59,11 +59,101 @@ static int cmp_offset(const void *a_, const void *b_)\n> /* revindex elements are lazily initialized */\n> }\n>\n> -static int cmp_offset(const void *a_, const void *b_)\n> +/*\n> + * This is a least-significant-digit radix sort.\n> + *\n> + * It sorts each of the \"n\" items in \"entries\" by its offset field. The \"max\"\n> + * parameter must be at least as large as the largest offset in the array,\n> + * and lets us quit the sort early.\n> + */\n> +static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)\n> {\n> - const struct revindex_entry *a = a_;\n> - const struct revindex_entry *b = b_;\n> - return (a->offset < b->offset) ? -1 : (a->offset > b->offset) ? 1 : 0;\n> + /*\n> + * We use a \"digit\" size of 16 bits. That keeps our memory\n> + * usage reasonable, and we can generally (for a 4G or smaller\n> + * packfile) quit after two rounds of radix-sorting.\n> + */\n> +#define DIGIT_SIZE (16)\n> +#define BUCKETS (1 << DIGIT_SIZE)\n> + /*\n> + * We want to know the bucket that a[i] will go into when we are using\n> + * the digit that is N bits from the (least significant) end.\n> + */\n> +#define BUCKET_FOR(a, i, bits) (((a)[(i)].offset >> (bits)) & (BUCKETS-1))\n> +\n> + /*\n> + * We need O(n) temporary storage. Rather than do an extra copy of the\n> + * partial results into \"entries\", we sort back and forth between the\n> + * real array and temporary storage. In each iteration of the loop, we\n> + * keep track of them with alias pointers, always sorting from \"from\"\n> + * to \"to\".\n> + */\n> + struct revindex_entry *tmp = xmalloc(n * sizeof(*tmp));\n> + struct revindex_entry *from = entries, *to = tmp;\n> + int bits;\n> + unsigned *pos = xmalloc(BUCKETS * sizeof(*pos));\n> +\n> + /*\n> + * If (max >> bits) is zero, then we know that the radix digit we are\n> + * on (and any higher) will be zero for all entries, and our loop will\n> + * be a no-op, as everybody lands in the same zero-th bucket.\n> + */\n> + for (bits = 0; max >> bits; bits += DIGIT_SIZE) {\n> + struct revindex_entry *swap;\n> + unsigned i;\n> +\n> + memset(pos, 0, BUCKETS * sizeof(*pos));\n> +\n> + /*\n> + * We want pos[i] to store the index of the last element that\n> + * will go in bucket \"i\" (actually one past the last element).\n> + * To do this, we first count the items that will go in each\n> + * bucket, which gives us a relative offset from the last\n> + * bucket. We can then cumulatively add the index from the\n> + * previous bucket to get the true index.\n> + */\n> + for (i = 0; i < n; i++)\n> + pos[BUCKET_FOR(from, i, bits)]++;\n> + for (i = 1; i < BUCKETS; i++)\n> + pos[i] += pos[i-1];\n> +\n> + /*\n> + * Now we can drop the elements into their correct buckets (in\n> + * our temporary array). We iterate the pos counter backwards\n> + * to avoid using an extra index to count up. And since we are\n> + * going backwards there, we must also go backwards through the\n> + * array itself, to keep the sort stable.\n> + *\n> + * Note that we use an unsigned iterator to make sure we can\n> + * handle 2^32-1 objects, even on a 32-bit system. But this\n> + * means we cannot use the more obvious \"i >= 0\" loop condition\n> + * for counting backwards, and must instead check for\n> + * wrap-around with UINT_MAX.\n> + */\n> + for (i = n - 1; i != UINT_MAX; i--)\n> + to[--pos[BUCKET_FOR(from, i, bits)]] = from[i];\n> +\n> + /*\n> + * Now \"to\" contains the most sorted list, so we swap \"from\" and\n> + * \"to\" for the next iteration.\n> + */\n> + swap = from;\n> + from = to;\n> + to = swap;\n> + }\n> +\n> + /*\n> + * If we ended with our data in the original array, great. If not,\n> + * we have to move it back from the temporary storage.\n> + */\n> + if (from != entries)\n> + memcpy(entries, tmp, n * sizeof(*entries));\n> + free(tmp);\n> + free(pos);\n> +\n> +#undef BUCKET_FOR\n> +#undef BUCKETS\n> +#undef DIGIT_SIZE\n> }\n>\n> /*\n> @@ -108,7 +198,7 @@ static void create_pack_revindex(struct pack_revindex *rix)\n> */\n> rix->revindex[num_ent].offset = p->pack_size - 20;\n> rix->revindex[num_ent].nr = -1;\n> - qsort(rix->revindex, num_ent, sizeof(*rix->revindex), cmp_offset);\n> + sort_revindex(rix->revindex, num_ent, p->pack_size);\n> }\n>\n> struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs)\n> --\n> 1.8.3.rc3.24.gec82cb9\n>\n"}]}