{"thread":{"id":"37000","subject":"[PATCH 0/8] use merge-base for tag --contains","startedAt":"2014-06-25T23:34:30Z","lastAt":"2014-07-01T19:14:08Z","messageCount":26,"participants":["Jeff King","Torsten Bögershausen","Junio C Hamano","Eric Sunshine"],"isPatch":true,"patchVersion":1,"patchTotal":8},"messages":[{"id":"244993","messageId":"20140625233429.GA20457@sigill.intra.peff.net","threadId":"37000","inReplyTo":null,"subject":"[PATCH 0/8] use merge-base for tag --contains","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-06-25T23:34:30Z","receivedAt":"2014-06-25T23:34:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Once upon a time we checked \"tag --contains\" by doing N merge-base\ntraversals, one per tag. That turned out to be really slow.\n\nLater, I added a single traversal in ffc4b80 (tag: speed up --contains\ncalculation, 2011-06-11) that works in a depth-first way. That's fast\nfor the common case of tags spread throughout history, but slow when all\nof the tags are close to the searched-for commit (which would be more\nlikely with branches, since they advance). That, plus the general\nhacky-ness of the implementation, prevented it from being used for \"git\nbranch\" or in other places.\n\nOver a year ago, Junio and I worked on the commit-slab code. The\noriginal point of it[1] was to be able to do a merge-base traversal like\nthis, where we kept one bit per tip in each commit (so that we know not\nonly what the merge base is, but _which_ tip hit each commit). So now I\nfinally got around to it. :)\n\nTimings are in the final patch, but the short of it is: it's about as\nfast as the depth-first code for the normal tag case (tags spread out\nthrough history), but way faster for the branch-like case (tags close to\nthe commit).\n\nThis series stops short of moving \"git branch\" over to it. My next goal\nonce this is solid is to factor the logic out so that \"tag -l\", \"branch\n-l\", and \"for-each-ref\" all use the same code. I got stuck on that\nearlier because I just couldn't justify sharing the tag-contains\nimplementation with the others.\n\n [1/8]: tag: allow --sort with -n\n [2/8]: tag: factor out decision to stream tags\n [3/8]: paint_down_to_common: use prio_queue\n [4/8]: add functions for memory-efficient bitmaps\n [5/8]: string-list: add pos to iterator callback\n [6/8]: commit: provide a fast multi-tip contains function\n [7/8]: tag: use commit_contains\n [8/8]: perf: add tests for tag --contains\n\n-Peff\n\n[1] http://article.gmane.org/gmane.comp.version-control.git/220545\n"},{"id":"244994","messageId":"20140625233505.GA23146@sigill.intra.peff.net","threadId":"37000","inReplyTo":"20140625233429.GA20457@sigill.intra.peff.net","subject":"[PATCH 1/8] tag: allow --sort with -n","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-06-25T23:35:06Z","receivedAt":"2014-06-25T23:35:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we are listing tags, we print each one as it is\nprocessed by for_each_ref. We can't do that with --sort, of\ncourse, as we need to see the whole list to sort. For the\n--sort code path, we store each tag in a string_list, and\nthen print them all at the end.\n\nThis interacts badly with \"-n\", which needs not only the\nname of the tag, but also the object itself. We simply\npunted on handling this, and disallowed the combination.\n\nThis patch remedies that by storing the sha1 of each object\nin the \"util\" field of the string list. We can then factor\nout the printing to a helper function and call that function\neither when we first see each tag, or after we have sorted.\n\nSigned-off-by: Jeff King \n---\n builtin/tag.c | 42 +++++++++++++++++++++++++-----------------\n cache.h | 7 +++++++\n t/t7004-tag.sh | 18 ++++++++++++++++++\n 3 files changed, 50 insertions(+), 17 deletions(-)\n\ndiff --git a/builtin/tag.c b/builtin/tag.c\nindex c6e8a71..2adfc3d 100644\n--- a/builtin/tag.c\n+++ b/builtin/tag.c\n@@ -213,6 +213,18 @@ free_return:\n \tfree(buf);\n }\n \n+static void print_tag(const char *refname, const unsigned char *sha1,\n+\t\t int lines)\n+{\n+\t\tif (!lines)\n+\t\t\tprintf(\"%s\\n\", refname);\n+\t\telse {\n+\t\t\tprintf(\"%-15s \", refname);\n+\t\t\tshow_tag_lines(sha1, lines);\n+\t\t\tputchar('\\n');\n+\t\t}\n+}\n+\n static int show_reference(const char *refname, const unsigned char *sha1,\n \t\t\t int flag, void *cb_data)\n {\n@@ -232,16 +244,10 @@ static int show_reference(const char *refname, const unsigned char *sha1,\n \t\tif (points_at.nr && !match_points_at(refname, sha1))\n \t\t\treturn 0;\n \n-\t\tif (!filter->lines) {\n-\t\t\tif (filter->sort)\n-\t\t\t\tstring_list_append(&filter->tags, refname);\n-\t\t\telse\n-\t\t\t\tprintf(\"%s\\n\", refname);\n-\t\t\treturn 0;\n-\t\t}\n-\t\tprintf(\"%-15s \", refname);\n-\t\tshow_tag_lines(sha1, filter->lines);\n-\t\tputchar('\\n');\n+\t\tif (filter->sort)\n+\t\t\tstring_list_append(&filter->tags, refname)->util = hashdup(sha1);\n+\t\telse\n+\t\t\tprint_tag(refname, sha1, filter->lines);\n \t}\n \n \treturn 0;\n@@ -273,12 +279,16 @@ static int list_tags(const char **patterns, int lines,\n \t\t\tqsort(filter.tags.items, filter.tags.nr,\n \t\t\t sizeof(struct string_list_item), sort_by_version);\n \t\tif (sort & REVERSE_SORT)\n-\t\t\tfor (i = filter.tags.nr - 1; i >= 0; i--)\n-\t\t\t\tprintf(\"%s\\n\", filter.tags.items[i].string);\n+\t\t\tfor (i = filter.tags.nr - 1; i >= 0; i--) {\n+\t\t\t\tstruct string_list_item *it = &filter.tags.items[i];\n+\t\t\t\tprint_tag(it->string, it->util, lines);\n+\t\t\t}\n \t\telse\n-\t\t\tfor (i = 0; i < filter.tags.nr; i++)\n-\t\t\t\tprintf(\"%s\\n\", filter.tags.items[i].string);\n-\t\tstring_list_clear(&filter.tags, 0);\n+\t\t\tfor (i = 0; i < filter.tags.nr; i++) {\n+\t\t\t\tstruct string_list_item *it = &filter.tags.items[i];\n+\t\t\t\tprint_tag(it->string, it->util, lines);\n+\t\t\t}\n+\t\tstring_list_clear(&filter.tags, 1);\n \t}\n \treturn 0;\n }\n@@ -634,8 +644,6 @@ int cmd_tag(int argc, const char **argv, const char *prefix)\n \t\t\tcopts.padding = 2;\n \t\t\trun_column_filter(colopts, &copts);\n \t\t}\n-\t\tif (lines != -1 && sort)\n-\t\t\tdie(_(\"--sort and -n are incompatible\"));\n \t\tret = list_tags(argv, lines == -1 ? 0 : lines, with_commit, sort);\n \t\tif (column_active(colopts))\n \t\t\tstop_column_filter();\ndiff --git a/cache.h b/cache.h\nindex df65231..74bf163 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -738,6 +738,13 @@ static inline void hashclr(unsigned char *hash)\n \tmemset(hash, 0, 20);\n }\n \n+static inline unsigned char *hashdup(const unsigned char *hash)\n+{\n+\tunsigned char *ret = xmalloc(20);\n+\thashcpy(ret, hash);\n+\treturn ret;\n+}\n+\n #define EMPTY_TREE_SHA1_HEX \\\n \t\"4b825dc642cb6eb9a060e54bf8d69288fbee4904\"\n #define EMPTY_TREE_SHA1_BIN_LITERAL \\\ndiff --git a/t/t7004-tag.sh b/t/t7004-tag.sh\nindex e4ab0f5..279b932 100755\n--- a/t/t7004-tag.sh\n+++ b/t/t7004-tag.sh\n@@ -1423,6 +1423,24 @@ EOF\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'sorting works with -n' '\n+\tcat >msg <<-\\EOF &&\n+\tmultiline\n+\ttag\n+\tmessage\n+\tEOF\n+\tgit tag -F msg foo-long &&\n+\tgit tag -l --sort=-refname -n2 \"foo*\" >actual &&\n+\tcat >expect <<-\\EOF &&\n+\tfoo1.6 Merge branch '\\''master'\\'' into stable\n+\tfoo1.3 Merge branch '\\''master'\\'' into stable\n+\tfoo1.10 Merge branch '\\''master'\\'' into stable\n+\tfoo-long multiline\n+\t tag\n+\tEOF\n+\ttest_cmp expect actual\n+'\n+\n run_with_limited_stack () {\n \t(ulimit -s 64 && \"$@\")\n }\n-- \n2.0.0.566.gfe3e6b2\n"},{"id":"244995","messageId":"20140625233524.GB23146@sigill.intra.peff.net","threadId":"37000","inReplyTo":"20140625233429.GA20457@sigill.intra.peff.net","subject":"[PATCH 2/8] tag: factor out decision to stream tags","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-06-25T23:35:24Z","receivedAt":"2014-06-25T23:35:24Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Right now we stream tags if we are not sorting. If we are\nsorting, we save them in a list and print them at the end.\nLet's abstract this decision into a function to make it\neasier to add more cases where we use the list.\n\nSigned-off-by: Jeff King \n---\n builtin/tag.c | 15 ++++++++++-----\n 1 file changed, 10 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/tag.c b/builtin/tag.c\nindex 2adfc3d..3ef2fab 100644\n--- a/builtin/tag.c\n+++ b/builtin/tag.c\n@@ -225,6 +225,11 @@ static void print_tag(const char *refname, const unsigned char *sha1,\n \t\t}\n }\n \n+static int filter_can_stream(struct tag_filter *filter)\n+{\n+\treturn !filter->sort;\n+}\n+\n static int show_reference(const char *refname, const unsigned char *sha1,\n \t\t\t int flag, void *cb_data)\n {\n@@ -244,7 +249,7 @@ static int show_reference(const char *refname, const unsigned char *sha1,\n \t\tif (points_at.nr && !match_points_at(refname, sha1))\n \t\t\treturn 0;\n \n-\t\tif (filter->sort)\n+\t\tif (!filter_can_stream(filter))\n \t\t\tstring_list_append(&filter->tags, refname)->util = hashdup(sha1);\n \t\telse\n \t\t\tprint_tag(refname, sha1, filter->lines);\n@@ -273,11 +278,11 @@ static int list_tags(const char **patterns, int lines,\n \tfilter.tags.strdup_strings = 1;\n \n \tfor_each_tag_ref(show_reference, (void *) &filter);\n-\tif (sort) {\n+\tif ((sort & SORT_MASK) == VERCMP_SORT)\n+\t\tqsort(filter.tags.items, filter.tags.nr,\n+\t\t sizeof(struct string_list_item), sort_by_version);\n+\tif (!filter_can_stream(&filter)) {\n \t\tint i;\n-\t\tif ((sort & SORT_MASK) == VERCMP_SORT)\n-\t\t\tqsort(filter.tags.items, filter.tags.nr,\n-\t\t\t sizeof(struct string_list_item), sort_by_version);\n \t\tif (sort & REVERSE_SORT)\n \t\t\tfor (i = filter.tags.nr - 1; i >= 0; i--) {\n \t\t\t\tstruct string_list_item *it = &filter.tags.items[i];\n-- \n2.0.0.566.gfe3e6b2\n"},{"id":"244996","messageId":"20140625233952.GC23146@sigill.intra.peff.net","threadId":"37000","inReplyTo":"20140625233429.GA20457@sigill.intra.peff.net","subject":"[PATCH 3/8] paint_down_to_common: use prio_queue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-06-25T23:39:52Z","receivedAt":"2014-06-25T23:39:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we are traversing to find merge bases, we keep our\nusual commit_list of commits to process, sorted by their\ncommit timestamp. As we add each parent to the list, we have\nto spend \"O(width of history)\" to do the insertion, where\nthe width of history is the number of simultaneous lines of\ndevelopment.\n\nIf we instead use a heap-based priority queue, we can do\nthese insertions in \"O(log width)\" time. This provides minor\nspeedups to merge-base calculations (timings in linux.git,\nwarm cache, best-of-five):\n\n [before]\n $ git merge-base HEAD v2.6.12\n real 0m3.251s\n user 0m3.148s\n sys 0m0.104s\n\n [after]\n $ git merge-base HEAD v2.6.12\n real 0m3.234s\n user 0m3.108s\n sys 0m0.128s\n\nThat's only an 0.5% speedup, but it does help protect us\nagainst pathological cases.\n\nThe downside is that our priority queue is not stable, which\nmeans that commits with the same timestamp may not come out\nin the order we put them in. You can see this in the test\nupdate in t6024. That test does a recursive merge across a\nset of commits that all have the same timestamp. For the\nvirtual ancestor, the test currently ends up with blob like\nthis:\n\n <<<<<<< Temporary merge branch 1\n <<<<<<< Temporary merge branch 1\n C\n =======\n B\n >>>>>>> Temporary merge branch 2\n =======\n A\n >>>>>>> Temporary merge branch 2\n\nbut with this patch, the positions of B and A are swapped.\nThis is probably fine, as the order is an internal\nimplementation detail anyway (it would _not_ be fine if we\nwere using a priority queue for \"git log\" traversal, which\nshould show commits in parent order).\n\nWhile we are munging the \"interesting\" function, we also\ntake the opportunity to give it a more descriptive name, and\nconvert the return value to an int (we returned the first\ninteresting commit, but nobody ever looked at it).\n\nSigned-off-by: Jeff King \n---\nThis one is not strictly required for the series; it's just that I'm\nadding what is essentially a clone of paint_down_to_common later in the\nseries. I wanted to use the priority queue there, too, so I looked into\nusing it here.\n\nI'm slightly hesitant because of the stability thing mentioned above. I\n_think_ it's probably fine. But we could also implement a\nstable_prio_queue on top of the existing prio_queue if we're concerned\n(and that may be something we want to do anyway, because \"git log\" would\nwant that if it switched to a priority queue).\n\nI had no recollection while writing this patch, but after searching the\nlist for \"stable priority queue\", I realized that Junio and I discussed\nit quite extensively a few years ago:\n\n http://thread.gmane.org/gmane.comp.version-control.git/204386/focus=204534\n\nI think the conclusion there is that what this patch does is acceptable.\n\n commit.c | 42 +++++++++++++++++++-----------------------\n t/t6024-recursive-merge.sh | 2 +-\n 2 files changed, 20 insertions(+), 24 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 881be3b..445b679 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -729,45 +729,41 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \n static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);\n \n-static struct commit *interesting(struct commit_list *list)\n+static int queue_has_nonstale(struct prio_queue *queue)\n {\n-\twhile (list) {\n-\t\tstruct commit *commit = list->item;\n-\t\tlist = list->next;\n-\t\tif (commit->object.flags & STALE)\n-\t\t\tcontinue;\n-\t\treturn commit;\n+\tint i;\n+\tfor (i = 0; i < queue->nr; i++) {\n+\t\tstruct commit *commit = queue->array[i];\n+\t\tif (!(commit->object.flags & STALE))\n+\t\t\treturn 1;\n \t}\n-\treturn NULL;\n+\treturn 0;\n }\n \n /* all input commits in one and twos[] must have been parsed! */\n static struct commit_list *paint_down_to_common(struct commit *one, int n, struct commit **twos)\n {\n-\tstruct commit_list *list = NULL;\n+\tstruct prio_queue queue = { compare_commits_by_commit_date };\n \tstruct commit_list *result = NULL;\n \tint i;\n \n \tone->object.flags |= PARENT1;\n-\tcommit_list_insert_by_date(one, &list);\n-\tif (!n)\n-\t\treturn list;\n+\tif (!n) {\n+\t\tcommit_list_append(one, &result);\n+\t\treturn result;\n+\t}\n+\tprio_queue_put(&queue, one);\n+\n \tfor (i = 0; i < n; i++) {\n \t\ttwos[i]->object.flags |= PARENT2;\n-\t\tcommit_list_insert_by_date(twos[i], &list);\n+\t\tprio_queue_put(&queue, twos[i]);\n \t}\n \n-\twhile (interesting(list)) {\n-\t\tstruct commit *commit;\n+\twhile (queue_has_nonstale(&queue)) {\n+\t\tstruct commit *commit = prio_queue_get(&queue);\n \t\tstruct commit_list *parents;\n-\t\tstruct commit_list *next;\n \t\tint flags;\n \n-\t\tcommit = list->item;\n-\t\tnext = list->next;\n-\t\tfree(list);\n-\t\tlist = next;\n-\n \t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n \t\tif (flags == (PARENT1 | PARENT2)) {\n \t\t\tif (!(commit->object.flags & RESULT)) {\n@@ -786,11 +782,11 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n, struc\n \t\t\tif (parse_commit(p))\n \t\t\t\treturn NULL;\n \t\t\tp->object.flags |= flags;\n-\t\t\tcommit_list_insert_by_date(p, &list);\n+\t\t\tprio_queue_put(&queue, p);\n \t\t}\n \t}\n \n-\tfree_commit_list(list);\n+\tclear_prio_queue(&queue);\n \treturn result;\n }\n \ndiff --git a/t/t6024-recursive-merge.sh b/t/t6024-recursive-merge.sh\nindex 755d30c..c3c634f 100755\n--- a/t/t6024-recursive-merge.sh\n+++ b/t/t6024-recursive-merge.sh\n@@ -76,7 +76,7 @@ test_expect_success \"result contains a conflict\" \"test_cmp expect a1\"\n \n git ls-files --stage > out\n cat > expect << EOF\n-100644 439cc46de773d8a83c77799b7cc9191c128bfcff 1\ta1\n+100644 222cbac87715ba85080f8b1463833bb3cfb3b9e0 1\ta1\n 100644 cf84443e49e1b366fac938711ddf4be2d4d1d9e9 2\ta1\n 100644 fd7923529855d0b274795ae3349c5e0438333979 3\ta1\n EOF\n-- \n2.0.0.566.gfe3e6b2\n"},{"id":"244997","messageId":"20140625234000.GD23146@sigill.intra.peff.net","threadId":"37000","inReplyTo":"20140625233429.GA20457@sigill.intra.peff.net","subject":"[PATCH 4/8] add functions for memory-efficient bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-06-25T23:40:01Z","receivedAt":"2014-06-25T23:40:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We already have a nice-to-use bitmap implementation in\newah/bitmap.c. It pretends to be infinitely long when asking\nfor a bit (and just returns 0 for bits that haven't been\nallocated or set), and dynamically resizes as appropriate\nwhen you set bits.\n\nThe cost to this is that each bitmap must store its own\npointer and length, using up to 16 bytes per bitmap on top\nof the actual bit storage. This is a lot of storage (not to\nmention an extra level of pointer indirection) if you are\ngoing to store one bitmap per commit in a traversal.\n\nThese functions provide an alternative bitmap implementation\nthat can be used when you have a large number of fixed-size\nbitmaps. See the documentation in the header file for\ndetails and examples.\n\nSigned-off-by: Jeff King \n---\n Makefile | 1 +\n bitset.h | 113 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 114 insertions(+)\n create mode 100644 bitset.h\n\ndiff --git a/Makefile b/Makefile\nindex 07ea105..8158fd2 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -633,6 +633,7 @@ LIB_H += archive.h\n LIB_H += argv-array.h\n LIB_H += attr.h\n LIB_H += bisect.h\n+LIB_H += bitset.h\n LIB_H += blob.h\n LIB_H += branch.h\n LIB_H += builtin.h\ndiff --git a/bitset.h b/bitset.h\nnew file mode 100644\nindex 0000000..5fbc956\n--- /dev/null\n+++ b/bitset.h\n@@ -0,0 +1,113 @@\n+#ifndef BITSET_H\n+#define BITSET_H\n+\n+/*\n+ * This header file provides functions for operating on an array of unsigned\n+ * characters as a bitmap. There is zero per-bitset storage overhead beyond the\n+ * actual number of stored bits (modulo some padding). This is efficient, but\n+ * makes the API harder to use. In particular, each bitset does not know how\n+ * long it is. It is the caller's responsibility to:\n+ *\n+ * 1. Never ask to get or set a bit outside of the allocated range.\n+ *\n+ * 2. Provide the allocated range to any functions which operate\n+ * on the whole bitset (e.g., bitset_or).\n+ *\n+ * 3. Always feed bitsets of the same size to functions which require it\n+ * (e.g., bitset_or).\n+ *\n+ * It is mostly intended to be used with commit-slabs to store N bits per\n+ * commit. Here's an example:\n+ *\n+ * define_commit_slab(bit_slab, unsigned char);\n+ *\n+ * ... assume we want to store nr bits per commit ...\n+ * struct bit_slab bits;\n+ * init_bit_slab_with_stride(&bits, bitset_sizeof(nr));\n+ *\n+ * ... set a bit (make sure 10 < nr!) ...\n+ * bitset_set(bit_slab_at(&bits, commit), 10);\n+ *\n+ * ... or get a bit ...\n+ * if (bitset_get(bit_slab_at(&bits, commit), 5))\n+ *\n+ * ... propagate bits to a parent commit ...\n+ * bitset_or(bit_slab_at(&bits, parent),\n+ *\t bit_slab_at(&bits, commit),\n+ *\t nr);\n+ */\n+\n+/*\n+ * Return the number of unsigned chars required to store num_bits bits.\n+ *\n+ * This is mostly used internally by the bitset functions, but you may need it\n+ * when allocating the bitset. Example:\n+ *\n+ * bits = xcalloc(1, bitset_sizeof(nr));\n+ */\n+static inline int bitset_sizeof(int num_bits)\n+{\n+\treturn (num_bits + CHAR_BIT - 1) / CHAR_BIT;\n+}\n+\n+/*\n+ * Set the bit at position \"n\". \"n\" is counted from zero, and must be\n+ * smaller than the num_bits given to bitset_sizeof when allocating the bitset.\n+ */\n+static inline void bitset_set(unsigned char *bits, int n)\n+{\n+\tbits[n / CHAR_BIT] |= 1 << (n % CHAR_BIT);\n+}\n+\n+/*\n+ * Return the bit at position \"n\" (see bitset_set for a description of \"n\").\n+ */\n+static inline int bitset_get(unsigned char *bits, int n)\n+{\n+\treturn !!(bits[n / CHAR_BIT] & (1 << (n % CHAR_BIT)));\n+}\n+\n+/*\n+ * Return true iff the bitsets contain the same bits. Each bitset should be the\n+ * same size, and should have been allocated using bitset_sizeof(max).\n+ *\n+ * Note that it is not safe to check partial equality by providing a smaller\n+ * \"max\" (we assume any bits beyond \"max\" up to the next CHAR_BIT boundary are\n+ * zeroed padding).\n+ */\n+static inline int bitset_equal(unsigned char *a, unsigned char *b, int max)\n+{\n+\tint i;\n+\tfor (i = bitset_sizeof(max); i > 0; i--)\n+\t\tif (*a++ != *b++)\n+\t\t\treturn 0;\n+\treturn 1;\n+}\n+\n+/*\n+ * Bitwise-or the bitsets in \"dst\" and \"src\", and store the result in \"dst\".\n+ *\n+ * See bitset_equal for the definition of \"max\".\n+ */\n+static inline void bitset_or(unsigned char *dst, const unsigned char *src, int max)\n+{\n+\tint i;\n+\tfor (i = bitset_sizeof(max); i > 0; i--)\n+\t\t*dst++ |= *src++;\n+}\n+\n+/*\n+ * Returns true iff the bitset contains all zeroes.\n+ *\n+ * See bitset_equal for the definition of \"max\".\n+ */\n+static inline int bitset_empty(const unsigned char *bits, int max)\n+{\n+\tint i;\n+\tfor (i = bitset_sizeof(max); i > 0; i--, bits++)\n+\t\tif (*bits)\n+\t\t\treturn 0;\n+\treturn 1;\n+}\n+\n+#endif /* BITSET_H */\n-- \n2.0.0.566.gfe3e6b2\n"},{"id":"244998","messageId":"20140625234252.GE23146@sigill.intra.peff.net","threadId":"37000","inReplyTo":"20140625233429.GA20457@sigill.intra.peff.net","subject":"[PATCH 5/8] string-list: add pos to iterator callback","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-06-25T23:42:52Z","receivedAt":"2014-06-25T23:42:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we are running a string-list foreach or filter, the\ncallback function sees only the string_list_item, along with\na void* data pointer provided by the caller. This is\nsufficient for most purposes.\n\nHowever, it can also be useful to know the position of the\nitem within the string (for example, if the data pointer\npoints to a secondary array in which each element\ncorresponds to part of the string list). We can help this\nuse case by providing the position to each callback.\n\nSigned-off-by: Jeff King \n---\nThe diff here is noisy, and I expect in the long run that the one caller\nI add to builtin/tag.c later in the series will eventually stop using\nstring_list entirely (in favor of a custom struct), which may leave us\nwith no callers that actually use the new field.\n\nI do think the logic above is sound, though, and it's a potentially\nuseful thing. There may be other sites that avoid the for_each wrapper\nin favor of iterating themselves simply _because_ they needed to know\nthe position (I would just do the same here, except that my new caller\nwants to use filter_string_list, which is a little more complicated).\n\n builtin/clone.c | 2 +-\n builtin/remote.c | 12 ++++++------\n notes.c | 1 +\n setup.c | 1 +\n string-list.c | 6 +++---\n string-list.h | 9 +++++++--\n test-path-utils.c | 2 +-\n test-string-list.c | 2 +-\n 8 files changed, 21 insertions(+), 14 deletions(-)\n\ndiff --git a/builtin/clone.c b/builtin/clone.c\nindex b12989d..89d0709 100644\n--- a/builtin/clone.c\n+++ b/builtin/clone.c\n@@ -227,7 +227,7 @@ static void strip_trailing_slashes(char *dir)\n \t*end = '\\0';\n }\n \n-static int add_one_reference(struct string_list_item *item, void *cb_data)\n+static int add_one_reference(struct string_list_item *item, int pos, void *cb_data)\n {\n \tchar *ref_git;\n \tconst char *repo;\ndiff --git a/builtin/remote.c b/builtin/remote.c\nindex c9102e8..bea0b58 100644\n--- a/builtin/remote.c\n+++ b/builtin/remote.c\n@@ -925,7 +925,7 @@ struct show_info {\n \tint any_rebase;\n };\n \n-static int add_remote_to_show_info(struct string_list_item *item, void *cb_data)\n+static int add_remote_to_show_info(struct string_list_item *item, int pos, void *cb_data)\n {\n \tstruct show_info *info = cb_data;\n \tint n = strlen(item->string);\n@@ -935,7 +935,7 @@ static int add_remote_to_show_info(struct string_list_item *item, void *cb_data)\n \treturn 0;\n }\n \n-static int show_remote_info_item(struct string_list_item *item, void *cb_data)\n+static int show_remote_info_item(struct string_list_item *item, int pos, void *cb_data)\n {\n \tstruct show_info *info = cb_data;\n \tstruct ref_states *states = info->states;\n@@ -962,7 +962,7 @@ static int show_remote_info_item(struct string_list_item *item, void *cb_data)\n \treturn 0;\n }\n \n-static int add_local_to_show_info(struct string_list_item *branch_item, void *cb_data)\n+static int add_local_to_show_info(struct string_list_item *branch_item, int pos, void *cb_data)\n {\n \tstruct show_info *show_info = cb_data;\n \tstruct ref_states *states = show_info->states;\n@@ -984,7 +984,7 @@ static int add_local_to_show_info(struct string_list_item *branch_item, void *cb\n \treturn 0;\n }\n \n-static int show_local_info_item(struct string_list_item *item, void *cb_data)\n+static int show_local_info_item(struct string_list_item *item, int pos, void *cb_data)\n {\n \tstruct show_info *show_info = cb_data;\n \tstruct branch_info *branch_info = item->util;\n@@ -1016,7 +1016,7 @@ static int show_local_info_item(struct string_list_item *item, void *cb_data)\n \treturn 0;\n }\n \n-static int add_push_to_show_info(struct string_list_item *push_item, void *cb_data)\n+static int add_push_to_show_info(struct string_list_item *push_item, int pos, void *cb_data)\n {\n \tstruct show_info *show_info = cb_data;\n \tstruct push_info *push_info = push_item->util;\n@@ -1045,7 +1045,7 @@ static int cmp_string_with_push(const void *va, const void *vb)\n \treturn cmp ? cmp : strcmp(a_push->dest, b_push->dest);\n }\n \n-static int show_push_info_item(struct string_list_item *item, void *cb_data)\n+static int show_push_info_item(struct string_list_item *item, int pos, void *cb_data)\n {\n \tstruct show_info *show_info = cb_data;\n \tstruct push_info *push_info = item->util;\ndiff --git a/notes.c b/notes.c\nindex 5fe691d..f7a84f9 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -881,6 +881,7 @@ static int string_list_add_note_lines(struct string_list *list,\n }\n \n static int string_list_join_lines_helper(struct string_list_item *item,\n+\t\t\t\t\t int pos,\n \t\t\t\t\t void *cb_data)\n {\n \tstruct strbuf *buf = cb_data;\ndiff --git a/setup.c b/setup.c\nindex 0a22f8b..0fe92fe 100644\n--- a/setup.c\n+++ b/setup.c\n@@ -586,6 +586,7 @@ static dev_t get_device_or_die(const char *path, const char *prefix, int prefix_\n * subsequent entries.\n */\n static int canonicalize_ceiling_entry(struct string_list_item *item,\n+\t\t\t\t int pos,\n \t\t\t\t void *cb_data)\n {\n \tint *empty_entry_found = cb_data;\ndiff --git a/string-list.c b/string-list.c\nindex aabb25e..85e1e41 100644\n--- a/string-list.c\n+++ b/string-list.c\n@@ -116,7 +116,7 @@ int for_each_string_list(struct string_list *list,\n {\n \tint i, ret = 0;\n \tfor (i = 0; i < list->nr; i++)\n-\t\tif ((ret = fn(&list->items[i], cb_data)))\n+\t\tif ((ret = fn(&list->items[i], i, cb_data)))\n \t\t\tbreak;\n \treturn ret;\n }\n@@ -126,7 +126,7 @@ void filter_string_list(struct string_list *list, int free_util,\n {\n \tint src, dst = 0;\n \tfor (src = 0; src < list->nr; src++) {\n-\t\tif (want(&list->items[src], cb_data)) {\n+\t\tif (want(&list->items[src], src, cb_data)) {\n \t\t\tlist->items[dst++] = list->items[src];\n \t\t} else {\n \t\t\tif (list->strdup_strings)\n@@ -138,7 +138,7 @@ void filter_string_list(struct string_list *list, int free_util,\n \tlist->nr = dst;\n }\n \n-static int item_is_not_empty(struct string_list_item *item, void *unused)\n+static int item_is_not_empty(struct string_list_item *item, int pos, void *unused)\n {\n \treturn *item->string != '\\0';\n }\ndiff --git a/string-list.h b/string-list.h\nindex dd5e294..3318076 100644\n--- a/string-list.h\n+++ b/string-list.h\n@@ -26,8 +26,13 @@ void string_list_clear(struct string_list *list, int free_util);\n typedef void (*string_list_clear_func_t)(void *p, const char *str);\n void string_list_clear_func(struct string_list *list, string_list_clear_func_t clearfunc);\n \n-/* Use this function or the macro below to iterate over each item */\n-typedef int (*string_list_each_func_t)(struct string_list_item *, void *);\n+/*\n+ * Use this function or the macro below to iterate over each item. Each item\n+ * is passed as the first argument to an invocation of the callback. The second\n+ * argument, \"pos\", is the numeric position of the first argument within the\n+ * list (_not_ an offset from the first item).\n+ */\n+typedef int (*string_list_each_func_t)(struct string_list_item *, int pos, void *);\n int for_each_string_list(struct string_list *list,\n \t\t\t string_list_each_func_t, void *cb_data);\n #define for_each_string_list_item(item,list) \\\ndiff --git a/test-path-utils.c b/test-path-utils.c\nindex 3dd3744..f3c584b 100644\n--- a/test-path-utils.c\n+++ b/test-path-utils.c\n@@ -6,7 +6,7 @@\n * GIT_CEILING_DIRECTORIES. If the path is unusable for some reason,\n * die with an explanation.\n */\n-static int normalize_ceiling_entry(struct string_list_item *item, void *unused)\n+static int normalize_ceiling_entry(struct string_list_item *item, int pos, void *unused)\n {\n \tconst char *ceil = item->string;\n \tint len = strlen(ceil);\ndiff --git a/test-string-list.c b/test-string-list.c\nindex 14bdf9d..85d9893 100644\n--- a/test-string-list.c\n+++ b/test-string-list.c\n@@ -35,7 +35,7 @@ static void write_list_compact(const struct string_list *list)\n \t}\n }\n \n-static int prefix_cb(struct string_list_item *item, void *cb_data)\n+static int prefix_cb(struct string_list_item *item, int pos, void *cb_data)\n {\n \tconst char *prefix = (const char *)cb_data;\n \treturn starts_with(item->string, prefix);\n-- \n2.0.0.566.gfe3e6b2\n"},{"id":"244999","messageId":"20140625234730.GF23146@sigill.intra.peff.net","threadId":"37000","inReplyTo":"20140625233429.GA20457@sigill.intra.peff.net","subject":"[PATCH 6/8] commit: provide a fast multi-tip contains function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-06-25T23:47:30Z","receivedAt":"2014-06-25T23:47:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When commands like \"git branch --contains\" want to know\nwhich branches contain a particular commit, they run a\nseries of merge-base calculations, one per branch. This can\nbe very slow if you have a large number of branches.\n\nWe made \"tag --contains\" faster in ffc4b80 (tag: speed up\n--contains calculation, 2011-06-11) by switching to a\ndifferent algorithm that caches intermediate \"contains\"\ninformation from each tag we check. The downside of the new\nalgorithm is that it moves depth-first through the graph. So\nit tends to go all the way to the roots, even if the\ncontained commit is near the top of history. That works OK\nfor tags, because repositories tend to have tags near the\nroots anyway (e.g., a v0.1 or similar). The number of\ncommits we look at increased a little bit, but since we\navoid traversing over the same parts of history repeatedly,\nit was a huge net win.\n\nFor \"branch --contains\", it is less clear that this is a\nwin. Most branches stay up to date, so we can bound a search\nfor a recent commit when we hit the merge base between the\ncommit and the branches.\n\nThe ideal would be to use the merge-base-style breadth-first\ntraversal, but to perform a single traversal for all tips.\nThe problem is that we need one bit of storage per tip in\neach commit, and \"struct commit\" has only a fixed number of\nbits. We can solve that by using a process similar to\npaint_down_to_common, but instead of storing PARENT1 and\nPARENT2 flags, using a commit slab to store one bit per tip.\n\nSigned-off-by: Jeff King \n---\nThis is the interesting commit, and I'd really love some eyes on the\nlogic. It's basically paint_down_to_common but with the PARENT1 and\nPARENT2 flags replaced with larger bitfields.\n\nI haven't quite convinced myself that the stale logic in the middle is\nright. The origin paint_down function checks \"PARENT1 | PARENT2\" to see\nif we found a merge base (even though PARENT2 may represent many tips).\nHere I check whether we have _any_ \"left\" parent flag and _any_ \"right\"\nparent flag. I'm not sure if I actually need to be finding the merge\nbase of _all_ of the commits. I don't think so, and I can't find a case\nwhere this doesn't work, but perhaps I am not being imaginative enough.\n\n commit.c | 102 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n commit.h | 17 +++++++++++\n 2 files changed, 119 insertions(+)\n\ndiff --git a/commit.c b/commit.c\nindex 445b679..66e0def 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -11,6 +11,7 @@\n #include \"commit-slab.h\"\n #include \"prio-queue.h\"\n #include \"sha1-lookup.h\"\n+#include \"bitset.h\"\n \n static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);\n \n@@ -1040,6 +1041,107 @@ struct commit_list *reduce_heads(struct commit_list *heads)\n \treturn result;\n }\n \n+define_commit_slab(bit_slab, unsigned char);\n+\n+static int init_contains_bits(const struct commit_list *commits,\n+\t\t\t struct bit_slab *bits,\n+\t\t\t struct prio_queue *queue)\n+{\n+\tint i, nr = commit_list_count(commits);\n+\n+\tinit_bit_slab_with_stride(bits, bitset_sizeof(nr));\n+\tfor (i = 0; i < nr; i++, commits = commits->next) {\n+\t\tstruct commit *c = commits->item;\n+\n+\t\tprio_queue_put(queue, c);\n+\t\tbitset_set(bit_slab_at(bits, c), i);\n+\t}\n+\n+\treturn nr;\n+}\n+\n+static int queue_has_nonstale_bits(struct prio_queue *queue, struct bit_slab *stale)\n+{\n+\tint i;\n+\tfor (i = 0; i < queue->nr; i++) {\n+\t\tstruct commit *commit = queue->array[i];\n+\t\tif (!*bit_slab_at(stale, commit))\n+\t\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n+static void fill_contains_result(unsigned char *result, int nr,\n+\t\t\t\t struct bit_slab *bits,\n+\t\t\t\t const struct commit_list *other_side)\n+{\n+\tconst struct commit_list *c;\n+\n+\tmemset(result, 0, nr);\n+\tfor (c = other_side; c; c = c->next) {\n+\t\tunsigned char *c_bits = bit_slab_at(bits, c->item);\n+\t\tint i;\n+\n+\t\tfor (i = 0; i < nr; i++)\n+\t\t\tresult[i] |= bitset_get(c_bits, i);\n+\t}\n+}\n+\n+void commit_contains(const struct commit_list *left,\n+\t\t const struct commit_list *right,\n+\t\t unsigned char *left_contains,\n+\t\t unsigned char *right_contains)\n+{\n+\tstruct prio_queue queue = { compare_commits_by_commit_date };\n+\tstruct bit_slab left_bits, right_bits, stale_bits;\n+\tint left_nr, right_nr;\n+\n+\tleft_nr = init_contains_bits(left, &left_bits, &queue);\n+\tright_nr = init_contains_bits(right, &right_bits, &queue);\n+\tinit_bit_slab(&stale_bits);\n+\n+\twhile (queue_has_nonstale_bits(&queue, &stale_bits)) {\n+\t\tstruct commit *commit = prio_queue_get(&queue);\n+\t\tstruct commit_list *parents;\n+\t\tunsigned char *c_left, *c_right, *c_stale;\n+\n+\t\tc_left = bit_slab_at(&left_bits, commit);\n+\t\tc_right = bit_slab_at(&right_bits, commit);\n+\t\tc_stale = bit_slab_at(&stale_bits, commit);\n+\n+\t\tif (!bitset_empty(c_left, left_nr) &&\n+\t\t !bitset_empty(c_right, right_nr))\n+\t\t\t*c_stale = 1;\n+\n+\t\tfor (parents = commit->parents; parents; parents = parents->next) {\n+\t\t\tstruct commit *p = parents->item;\n+\t\t\tunsigned char *p_left = bit_slab_at(&left_bits, p),\n+\t\t\t\t *p_right = bit_slab_at(&right_bits, p);\n+\n+\t\t\tif (bitset_equal(c_left, p_left, left_nr) &&\n+\t\t\t bitset_equal(c_right, p_right, right_nr))\n+\t\t\t\tcontinue;\n+\t\t\tif (parse_commit(p))\n+\t\t\t\tdie(\"unable to parse commit\");\n+\t\t\tbitset_or(p_left, c_left, left_nr);\n+\t\t\tbitset_or(p_right, c_right, right_nr);\n+\t\t\t*bit_slab_at(&stale_bits, p) |= *c_stale;\n+\t\t\tprio_queue_put(&queue, p);\n+\t\t}\n+\t}\n+\n+\tif (left_contains)\n+\t\tfill_contains_result(left_contains, left_nr, &left_bits, right);\n+\tif (right_contains)\n+\t\tfill_contains_result(right_contains, right_nr, &right_bits, left);\n+\n+\tclear_prio_queue(&queue);\n+\tclear_bit_slab(&left_bits);\n+\tclear_bit_slab(&right_bits);\n+\tclear_bit_slab(&stale_bits);\n+}\n+\n+\n static const char gpg_sig_header[] = \"gpgsig\";\n static const int gpg_sig_header_len = sizeof(gpg_sig_header) - 1;\n \ndiff --git a/commit.h b/commit.h\nindex a9f177b..d3a142a 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -307,4 +307,21 @@ int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused)\n LAST_ARG_MUST_BE_NULL\n extern int run_commit_hook(int editor_is_used, const char *index_file, const char *name, ...);\n \n+/*\n+ * Calculate which commits in left contain commits in right, and vice versa.\n+ *\n+ * The left_contains result, if non-NULL, must point to an array of unsigned\n+ * char with as many elements as there are items in the \"left\" commit_list.\n+ * When the function completes, the nth char in left_contains will be non-zero\n+ * iff the nth commit in the \"left\" list contains at least one commit from the\n+ * \"right\" list.\n+ *\n+ * The right_contains result works in the same way, but with left and right\n+ * swapped.\n+ */\n+void commit_contains(const struct commit_list *left,\n+\t\t const struct commit_list *right,\n+\t\t unsigned char *left_contains,\n+\t\t unsigned char *right_contains);\n+\n #endif /* COMMIT_H */\n-- \n2.0.0.566.gfe3e6b2\n"},{"id":"245000","messageId":"20140625234921.GG23146@sigill.intra.peff.net","threadId":"37000","inReplyTo":"20140625233429.GA20457@sigill.intra.peff.net","subject":"[PATCH 7/8] tag: use commit_contains","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-06-25T23:49:21Z","receivedAt":"2014-06-25T23:49:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The newly added commit_contains function should do a better\njob than our custom depth-first traversal. It should be the\nsame speed when going close to the roots, but much faster\nwhen all tags are close to the searched-for commit (this\nusually isn't the case, but could be if you limit the tags\nwith a pattern).\n\nIt also cleans up some of the more egregious pitfalls of the\noriginal implementation, including an abuse of the\nUNINTERESTING and TMP_MARK flags, an utterly confusing\ncalling convention (it silently caches the bits between\ncalls, with no checks that our \"with_commit\" was the same\nfor each call), and a failure to clean up after itself\n(tainting any further traversals).\n\nSigned-off-by: Jeff King \n---\nThe code to use the new contains function ends up disappointingly longer\nthan I would have hoped, but it has to massage our string_list of tag\nnames into a list of commits, and then massage the output back into a\nfiltered string list. It's not too bad, though. And as I mentioned, I\nhope to eventually factor this out to share with for-each-ref and\nbranch.\n\n builtin/tag.c | 161 +++++++++++++++++-----------------------------------------\n 1 file changed, 48 insertions(+), 113 deletions(-)\n\ndiff --git a/builtin/tag.c b/builtin/tag.c\nindex 3ef2fab..f17192c 100644\n--- a/builtin/tag.c\n+++ b/builtin/tag.c\n@@ -72,108 +72,6 @@ static const unsigned char *match_points_at(const char *refname,\n \treturn NULL;\n }\n \n-static int in_commit_list(const struct commit_list *want, struct commit *c)\n-{\n-\tfor (; want; want = want->next)\n-\t\tif (!hashcmp(want->item->object.sha1, c->object.sha1))\n-\t\t\treturn 1;\n-\treturn 0;\n-}\n-\n-enum contains_result {\n-\tCONTAINS_UNKNOWN = -1,\n-\tCONTAINS_NO = 0,\n-\tCONTAINS_YES = 1,\n-};\n-\n-/*\n- * Test whether the candidate or one of its parents is contained in the list.\n- * Do not recurse to find out, though, but return -1 if inconclusive.\n- */\n-static enum contains_result contains_test(struct commit *candidate,\n-\t\t\t const struct commit_list *want)\n-{\n-\t/* was it previously marked as containing a want commit? */\n-\tif (candidate->object.flags & TMP_MARK)\n-\t\treturn 1;\n-\t/* or marked as not possibly containing a want commit? */\n-\tif (candidate->object.flags & UNINTERESTING)\n-\t\treturn 0;\n-\t/* or are we it? */\n-\tif (in_commit_list(want, candidate)) {\n-\t\tcandidate->object.flags |= TMP_MARK;\n-\t\treturn 1;\n-\t}\n-\n-\tif (parse_commit(candidate) < 0)\n-\t\treturn 0;\n-\n-\treturn -1;\n-}\n-\n-/*\n- * Mimicking the real stack, this stack lives on the heap, avoiding stack\n- * overflows.\n- *\n- * At each recursion step, the stack items points to the commits whose\n- * ancestors are to be inspected.\n- */\n-struct stack {\n-\tint nr, alloc;\n-\tstruct stack_entry {\n-\t\tstruct commit *commit;\n-\t\tstruct commit_list *parents;\n-\t} *stack;\n-};\n-\n-static void push_to_stack(struct commit *candidate, struct stack *stack)\n-{\n-\tint index = stack->nr++;\n-\tALLOC_GROW(stack->stack, stack->nr, stack->alloc);\n-\tstack->stack[index].commit = candidate;\n-\tstack->stack[index].parents = candidate->parents;\n-}\n-\n-static enum contains_result contains(struct commit *candidate,\n-\t\tconst struct commit_list *want)\n-{\n-\tstruct stack stack = { 0, 0, NULL };\n-\tint result = contains_test(candidate, want);\n-\n-\tif (result != CONTAINS_UNKNOWN)\n-\t\treturn result;\n-\n-\tpush_to_stack(candidate, &stack);\n-\twhile (stack.nr) {\n-\t\tstruct stack_entry *entry = &stack.stack[stack.nr - 1];\n-\t\tstruct commit *commit = entry->commit;\n-\t\tstruct commit_list *parents = entry->parents;\n-\n-\t\tif (!parents) {\n-\t\t\tcommit->object.flags |= UNINTERESTING;\n-\t\t\tstack.nr--;\n-\t\t}\n-\t\t/*\n-\t\t * If we just popped the stack, parents->item has been marked,\n-\t\t * therefore contains_test will return a meaningful 0 or 1.\n-\t\t */\n-\t\telse switch (contains_test(parents->item, want)) {\n-\t\tcase CONTAINS_YES:\n-\t\t\tcommit->object.flags |= TMP_MARK;\n-\t\t\tstack.nr--;\n-\t\t\tbreak;\n-\t\tcase CONTAINS_NO:\n-\t\t\tentry->parents = parents->next;\n-\t\t\tbreak;\n-\t\tcase CONTAINS_UNKNOWN:\n-\t\t\tpush_to_stack(parents->item, &stack);\n-\t\t\tbreak;\n-\t\t}\n-\t}\n-\tfree(stack.stack);\n-\treturn contains_test(candidate, want);\n-}\n-\n static void show_tag_lines(const unsigned char *sha1, int lines)\n {\n \tint i;\n@@ -227,7 +125,7 @@ static void print_tag(const char *refname, const unsigned char *sha1,\n \n static int filter_can_stream(struct tag_filter *filter)\n {\n-\treturn !filter->sort;\n+\treturn !filter->sort && !filter->with_commit;\n }\n \n static int show_reference(const char *refname, const unsigned char *sha1,\n@@ -236,16 +134,6 @@ static int show_reference(const char *refname, const unsigned char *sha1,\n \tstruct tag_filter *filter = cb_data;\n \n \tif (match_pattern(filter->patterns, refname)) {\n-\t\tif (filter->with_commit) {\n-\t\t\tstruct commit *commit;\n-\n-\t\t\tcommit = lookup_commit_reference_gently(sha1, 1);\n-\t\t\tif (!commit)\n-\t\t\t\treturn 0;\n-\t\t\tif (!contains(commit, filter->with_commit))\n-\t\t\t\treturn 0;\n-\t\t}\n-\n \t\tif (points_at.nr && !match_points_at(refname, sha1))\n \t\t\treturn 0;\n \n@@ -258,6 +146,46 @@ static int show_reference(const char *refname, const unsigned char *sha1,\n \treturn 0;\n }\n \n+static int util_is_not_null(struct string_list_item *it, int pos, void *data)\n+{\n+\treturn !!it->util;\n+}\n+\n+static int matches_contains(struct string_list_item *it, int pos, void *data)\n+{\n+\tunsigned char *contains = data;\n+\treturn contains[pos];\n+}\n+\n+static void limit_by_contains(struct string_list *tags, struct commit_list *with)\n+{\n+\tstruct commit_list *tag_commits = NULL, **tail = &tag_commits;\n+\tunsigned char *result;\n+\tint i;\n+\n+\tfor (i = 0; i < tags->nr; i++) {\n+\t\tstruct string_list_item *it = &tags->items[i];\n+\t\tstruct commit *c = lookup_commit_reference_gently(it->util, 1);\n+\t\tif (c)\n+\t\t\ttail = commit_list_append(c, tail);\n+\t\telse {\n+\t\t\tfree(it->util);\n+\t\t\tit->util = NULL;\n+\t\t}\n+\t}\n+\tfilter_string_list(tags, 0, util_is_not_null, NULL);\n+\n+\tif (!tags->nr)\n+\t\treturn;\n+\n+\tresult = xmalloc(tags->nr);\n+\tcommit_contains(with, tag_commits, NULL, result);\n+\tfilter_string_list(tags, 1, matches_contains, result);\n+\n+\tfree(result);\n+\tfree_commit_list(tag_commits);\n+}\n+\n static int sort_by_version(const void *a_, const void *b_)\n {\n \tconst struct string_list_item *a = a_;\n@@ -278,9 +206,16 @@ static int list_tags(const char **patterns, int lines,\n \tfilter.tags.strdup_strings = 1;\n \n \tfor_each_tag_ref(show_reference, (void *) &filter);\n+\tif (with_commit)\n+\t\tlimit_by_contains(&filter.tags, with_commit);\n \tif ((sort & SORT_MASK) == VERCMP_SORT)\n \t\tqsort(filter.tags.items, filter.tags.nr,\n \t\t sizeof(struct string_list_item), sort_by_version);\n+\tif (sort) {\n+\t\tif ((sort & SORT_MASK) == VERCMP_SORT)\n+\t\t\tqsort(filter.tags.items, filter.tags.nr,\n+\t\t\t sizeof(struct string_list_item), sort_by_version);\n+\t}\n \tif (!filter_can_stream(&filter)) {\n \t\tint i;\n \t\tif (sort & REVERSE_SORT)\n-- \n2.0.0.566.gfe3e6b2\n"},{"id":"245001","messageId":"20140625235335.GH23146@sigill.intra.peff.net","threadId":"37000","inReplyTo":"20140625233429.GA20457@sigill.intra.peff.net","subject":"[PATCH 8/8] perf: add tests for tag --contains","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-06-25T23:53:35Z","receivedAt":"2014-06-25T23:53:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"These tests can demonstrate the changes in \"tag --contains\"\nspeed over time. The interesting points in history are:\n\n - pre-ffc4b80, where we used a series of N merge-base\n traversals\n\n - ffc4b80 up to the current master, where we moved to a\n single depth-first traversal\n\n - the previous commit, where we moved from depth-first to\n a multi-tip merge-base\n\nThe interesting cases to measure are:\n\n - checking which tags contain a recent commit (we use\n HEAD~100 here)\n\n - checking which tags contain a very ancient commit (we\n use the last commit output by rev-list)\n\n - checking which tags contain a commit in the middle (we\n use HEAD~5000, which goes back 5 years in git.git)\n\n - all of the above, but instead of looking at all commits,\n considering only recent ones (we pick the most recent\n tag by its tagger date)\n\nHere are the timings for git.git:\n\n Test ffc4b80^ origin/master HEAD\n ----------------------------------------------------------------------------------------------------\n 7000.3: contains recent/all 1.97(1.96+0.01) 0.26(0.25+0.00) -86.8% 0.27(0.26+0.00) -86.3%\n 7000.4: contains recent/v2.0.1 0.08(0.08+0.00) 0.25(0.24+0.01) +212.5% 0.02(0.02+0.00) -75.0%\n 7000.5: contains old/all 0.90(0.89+0.00) 0.18(0.17+0.00) -80.0% 0.27(0.26+0.00) -70.0%\n 7000.6: contains old/v2.0.1 0.25(0.23+0.02) 0.03(0.03+0.00) -88.0% 0.25(0.24+0.00) +0.0%\n 7000.7: contains ancient/all 1.98(1.97+0.01) 0.26(0.24+0.01) -86.9% 0.28(0.25+0.02) -85.9%\n 7000.8: contains ancient/v2.0.1 1.95(1.94+0.00) 0.26(0.24+0.01) -86.7% 0.27(0.26+0.00) -86.2%\n\nYou can see that ffc4b80 vastly improved the normal case of\nchecking all tags. This is because we avoid walking over the\nsame parts of history over and over. However, when looking\nonly for a recent tag (v2.0.1 in these tests), it sometimes\nperforms much worse than the original. This is not\nsurprising. For a merge-base solution, we can quit when we\nhit history shared between the contained commit and the tag.\nFor ffc4b80's depth-first approach, we typically go all the\nway to the roots before backtracking. For the ancient/v2.0.1\ncase, that's not a big deal, because the merge base requires\nus doing that anyway. But for recent/v2.0.1, the merge-base\nanswer should involve only recent history.\n\nThe new traversal code performs about as well as the\ndepth-first code in the normal case, but fixes the\nregression in the recent/v2.0.1 case.\n\nSigned-off-by: Jeff King \n---\nThere are still two things about the timings that puzzle me a bit.\n\nOne is that the old/all case gets slower moving from the depth-first\ntraversal to the merge-base one. I think this is simply because the\ndepth-first one may get \"lucky\" sometimes, and hit the commit we are\nlooking for on the way down. So its average case is somewhat better than\nits worst case (and I would not be surprised if my choice of HEAD~5000\nhelps it, because it follows first parents first).\n\nThe second question is why ffc4b80^ is so much slower on the v2.0.1\ntests than the new code. They should both be doing a single merge-base\ntraversal, and I'd expect them to take about the same amount of time\n(for that matter, ancient/v2.0.1 should take the same amount of time as\nthe depth-first code, since they all basically have to read all of the\ncommits once). My guess is that there's some other speedup that has\nhappened in the years between ffc4b80 and now.\n\n t/perf/p7000-tag-contains.sh | 30 ++++++++++++++++++++++++++++++\n 1 file changed, 30 insertions(+)\n create mode 100755 t/perf/p7000-tag-contains.sh\n\ndiff --git a/t/perf/p7000-tag-contains.sh b/t/perf/p7000-tag-contains.sh\nnew file mode 100755\nindex 0000000..846f106\n--- /dev/null\n+++ b/t/perf/p7000-tag-contains.sh\n@@ -0,0 +1,30 @@\n+#!/bin/sh\n+\n+test_description='speed of tag --contains lookups'\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+\n+test_expect_success 'find reference points' '\n+\trecent=$(git rev-parse HEAD~100) &&\n+\told=$(git rev-parse HEAD~5000) &&\n+\tancient=$(git rev-list | tail -n 1)\n+'\n+\n+test_expect_success 'find most recent tag' '\n+\ttag=$(git for-each-ref --sort=-taggerdate \\\n+\t\t\t --format=\"%(refname:short)\" \\\n+\t\t\t refs/tags |\n+\t head -n 1)\n+'\n+\n+for distance in recent old ancient; do\n+\tcontains=$(eval echo \\$$distance)\n+\tfor match in \"\" \"$tag\"; do\n+\t\ttest_perf \"contains $distance/${match:-all}\" \"\n+\t\t\tgit tag -l --contains $contains $match\n+\t\t\"\n+\tdone\n+done\n+\n+test_done\n-- \n2.0.0.566.gfe3e6b2\n"},{"id":"245002","messageId":"20140626000129.GA25028@sigill.intra.peff.net","threadId":"37000","inReplyTo":"20140625235335.GH23146@sigill.intra.peff.net","subject":"Re: [PATCH 8/8] perf: add tests for tag --contains","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-06-26T00:01:29Z","receivedAt":"2014-06-26T00:01:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 25, 2014 at 07:53:35PM -0400, Jeff King wrote:\n\n> There are still two things about the timings that puzzle me a bit.\n\n\n\nThis certainly isn't helping:\n\n> +test_expect_success 'find reference points' '\n> +\trecent=$(git rev-parse HEAD~100) &&\n> +\told=$(git rev-parse HEAD~5000) &&\n> +\tancient=$(git rev-list | tail -n 1)\n> +'\n\n$ancient will always be empty, as rev-list needs a \"HEAD\" argument.\n\nI also think HEAD~100 is probably _too_ recent, as it is not enough to\nmatch any tags at all right now.\n\nSo with this patch:\n\ndiff --git a/t/perf/p7000-tag-contains.sh b/t/perf/p7000-tag-contains.sh\nindex 846f106..8294d41 100755\n--- a/t/perf/p7000-tag-contains.sh\n+++ b/t/perf/p7000-tag-contains.sh\n@@ -6,9 +6,9 @@ test_description='speed of tag --contains lookups'\n test_perf_default_repo\n \n test_expect_success 'find reference points' '\n-\trecent=$(git rev-parse HEAD~100) &&\n+\trecent=$(git rev-parse HEAD~200) &&\n \told=$(git rev-parse HEAD~5000) &&\n-\tancient=$(git rev-list | tail -n 1)\n+\tancient=$(git rev-list HEAD | tail -n 1)\n '\n \n test_expect_success 'find most recent tag' '\n\nI get:\n\n Test ffc4b80^ origin/master HEAD \n ----------------------------------------------------------------------------------------------------\n 7000.3: contains recent/all 1.99(1.97+0.01) 0.25(0.24+0.00) -87.4% 0.27(0.26+0.00) -86.4%\n 7000.4: contains recent/v2.0.1 0.03(0.03+0.00) 0.00(0.00+0.00) -100.0% 0.03(0.02+0.00) +0.0% \n 7000.5: contains old/all 0.90(0.89+0.00) 0.18(0.17+0.00) -80.0% 0.27(0.26+0.00) -70.0%\n 7000.6: contains old/v2.0.1 0.25(0.24+0.00) 0.03(0.03+0.00) -88.0% 0.25(0.24+0.00) +0.0% \n 7000.7: contains ancient/all 0.82(0.80+0.01) 0.13(0.12+0.00) -84.1% 0.27(0.26+0.01) -67.1%\n 7000.8: contains ancient/v2.0.1 0.26(0.26+0.00) 0.09(0.08+0.00) -65.4% 0.25(0.24+0.00) -3.8% \n\nwhich looks about right.\n\n-Peff\n"},{"id":"245003","messageId":"20140626000405.GB25028@sigill.intra.peff.net","threadId":"37000","inReplyTo":"20140626000129.GA25028@sigill.intra.peff.net","subject":"Re: [PATCH 8/8] perf: add tests for tag --contains","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-06-26T00:04:05Z","receivedAt":"2014-06-26T00:04:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 25, 2014 at 08:01:29PM -0400, Jeff King wrote:\n\n> I get:\n> \n> Test ffc4b80^ origin/master HEAD \n> ----------------------------------------------------------------------------------------------------\n> 7000.3: contains recent/all 1.99(1.97+0.01) 0.25(0.24+0.00) -87.4% 0.27(0.26+0.00) -86.4%\n> 7000.4: contains recent/v2.0.1 0.03(0.03+0.00) 0.00(0.00+0.00) -100.0% 0.03(0.02+0.00) +0.0% \n> 7000.5: contains old/all 0.90(0.89+0.00) 0.18(0.17+0.00) -80.0% 0.27(0.26+0.00) -70.0%\n> 7000.6: contains old/v2.0.1 0.25(0.24+0.00) 0.03(0.03+0.00) -88.0% 0.25(0.24+0.00) +0.0% \n> 7000.7: contains ancient/all 0.82(0.80+0.01) 0.13(0.12+0.00) -84.1% 0.27(0.26+0.01) -67.1%\n> 7000.8: contains ancient/v2.0.1 0.26(0.26+0.00) 0.09(0.08+0.00) -65.4% 0.25(0.24+0.00) -3.8% \n> \n> which looks about right.\n\nOh, hmph. The \"bad\" case in recent/v2.0.1 for origin/master goes away\nthen. Because we get \"lucky\" again, and the depth-first one does not\nhave to go all the way to the roots. So it's probably a better example\nto use the original HEAD~100, which isn't actually in v2.0.1.\n\n-Peff\n"},{"id":"245005","messageId":"53AB9039.8040809@web.de","threadId":"37000","inReplyTo":"20140625234000.GD23146@sigill.intra.peff.net","subject":"Re: [PATCH 4/8] add functions for memory-efficient bitmaps","fromName":"Torsten Bögershausen","fromEmail":"tboegi@web.de","sentAt":"2014-06-26T03:15:05Z","receivedAt":"2014-06-26T03:15:05Z","isPatch":true,"sender":{"key":"tboegi@web.de","avatar":"https://avatars.githubusercontent.com/u/7138363?v=4"},"body":"On 2014-06-26 01.40, Jeff King wrote:\n[]\n\n> + */\n> +static inline int bitset_sizeof(int num_bits)\n> +{\n> +\treturn (num_bits + CHAR_BIT - 1) / CHAR_BIT;\n> +}\nJust a general question about the usage of \"int\" here (and at other places):\nIs there a special reason for new code to allow num_bits to be negative ?\n\nTo my knowledge all the size_t definitions these days are positive,\nbecause a size can not be negative.\n\nAs a reader of the code I always wonder if there is a special meaning with\nnegative values, (as the result of read() to indicate an error) but there isn't.\n\nShould we use\n\"unsigned\" here ?\nor \"unsigned int\" ?\nor \"size_t\" (Which may use 64 bits, which feels like a overkill)\n"},{"id":"245019","messageId":"20140626155119.GA10402@sigill.intra.peff.net","threadId":"37000","inReplyTo":"53AB9039.8040809@web.de","subject":"Re: [PATCH 4/8] add functions for memory-efficient bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-06-26T15:51:19Z","receivedAt":"2014-06-26T15:51:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 26, 2014 at 05:15:05AM +0200, Torsten Bögershausen wrote:\n\n> > + */\n> > +static inline int bitset_sizeof(int num_bits)\n> > +{\n> > +\treturn (num_bits + CHAR_BIT - 1) / CHAR_BIT;\n> > +}\n> Just a general question about the usage of \"int\" here (and at other places):\n> Is there a special reason for new code to allow num_bits to be negative ?\n\nNo. I usually choose \"int\" when the word size is not likely to matter\n(i.e., we do not expect it to overflow a 32-bit integer, nor to have so\nmany that I need to be careful not to waste space).\n\nProbably \"unsigned int\" would be a more descriptive choice.\n\nIt may also help the compiler optimize better. Assuming CHAR_BIT is 8\n(i.e., most everywhere), we get:\n\n (num_bits + 7) / 8\n\nPresumably the compiler implements the division with a right-shift.\nMarking num_bits as unsigned should let us do just a logical shift,\nwithout worrying about the sign. And indeed, here are the signed and\nunsigned versions produced by \"gcc -S -O2\" (for an equivalent\nnon-inlined function):\n\n [signed]\n leal 14(%rdi), %edx\n movl %edi, %eax\n addl $7, %eax\n cmovs %edx, %eax\n sarl $3, %eax\n ret\n\n [unsigned]\n leal 7(%rdi), %eax\n shrl $3, %eax\n ret\n\nMuch simpler, though see below for practical considerations.\n\n> To my knowledge all the size_t definitions these days are positive,\n> because a size can not be negative.\n\nsize_t is perhaps a reasonable choice for the return value, given the name\n\"sizeof\". But if you really care about using the whole range of bits there, you\nneed a data type for num_bits that is CHAR_BIT times larger.\n\n> Should we use\n> \"unsigned\" here ?\n> or \"unsigned int\" ?\n\nYes, I think so. Both are the same to the compiler. I have a vague\nrecollection that we prefer one over the other, but grepping seems to\nfind many examples of each in our code.\n\nI'm squashing in the patch below. I couldn't measure any speed\nimprovement. I'm guessing because the functions are all inlined, which\nmeans we likely get away with calculating bitset_sizeof once outside of\nour loop. I think the result is still more obvious to read, though.\n\n-Peff\n\n---\ndiff --git a/bitset.h b/bitset.h\nindex 5fbc956..268545b 100644\n--- a/bitset.h\n+++ b/bitset.h\n@@ -45,7 +45,7 @@\n *\n * bits = xcalloc(1, bitset_sizeof(nr));\n */\n-static inline int bitset_sizeof(int num_bits)\n+static inline unsigned bitset_sizeof(unsigned num_bits)\n {\n \treturn (num_bits + CHAR_BIT - 1) / CHAR_BIT;\n }\n@@ -54,7 +54,7 @@ static inline int bitset_sizeof(int num_bits)\n * Set the bit at position \"n\". \"n\" is counted from zero, and must be\n * smaller than the num_bits given to bitset_sizeof when allocating the bitset.\n */\n-static inline void bitset_set(unsigned char *bits, int n)\n+static inline void bitset_set(unsigned char *bits, unsigned n)\n {\n \tbits[n / CHAR_BIT] |= 1 << (n % CHAR_BIT);\n }\n@@ -62,7 +62,7 @@ static inline void bitset_set(unsigned char *bits, int n)\n /*\n * Return the bit at position \"n\" (see bitset_set for a description of \"n\").\n */\n-static inline int bitset_get(unsigned char *bits, int n)\n+static inline unsigned bitset_get(unsigned char *bits, unsigned n)\n {\n \treturn !!(bits[n / CHAR_BIT] & (1 << (n % CHAR_BIT)));\n }\n@@ -75,9 +75,10 @@ static inline int bitset_get(unsigned char *bits, int n)\n * \"max\" (we assume any bits beyond \"max\" up to the next CHAR_BIT boundary are\n * zeroed padding).\n */\n-static inline int bitset_equal(unsigned char *a, unsigned char *b, int max)\n+static inline int bitset_equal(unsigned char *a, unsigned char *b,\n+\t\t\t unsigned max)\n {\n-\tint i;\n+\tunsigned i;\n \tfor (i = bitset_sizeof(max); i > 0; i--)\n \t\tif (*a++ != *b++)\n \t\t\treturn 0;\n@@ -89,9 +90,10 @@ static inline int bitset_equal(unsigned char *a, unsigned char *b, int max)\n *\n * See bitset_equal for the definition of \"max\".\n */\n-static inline void bitset_or(unsigned char *dst, const unsigned char *src, int max)\n+static inline void bitset_or(unsigned char *dst, const unsigned char *src,\n+\t\t\t unsigned max)\n {\n-\tint i;\n+\tunsigned i;\n \tfor (i = bitset_sizeof(max); i > 0; i--)\n \t\t*dst++ |= *src++;\n }\n@@ -101,9 +103,9 @@ static inline void bitset_or(unsigned char *dst, const unsigned char *src, int m\n *\n * See bitset_equal for the definition of \"max\".\n */\n-static inline int bitset_empty(const unsigned char *bits, int max)\n+static inline int bitset_empty(const unsigned char *bits, unsigned max)\n {\n-\tint i;\n+\tunsigned i;\n \tfor (i = bitset_sizeof(max); i > 0; i--, bits++)\n \t\tif (*bits)\n \t\t\treturn 0;\n"},{"id":"245033","messageId":"xmqqtx774i1r.fsf@gitster.dls.corp.google.com","threadId":"37000","inReplyTo":"20140625234730.GF23146@sigill.intra.peff.net","subject":"Re: [PATCH 6/8] commit: provide a fast multi-tip contains function","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-06-26T18:55:28Z","receivedAt":"2014-06-26T18:55:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I haven't quite convinced myself that the stale logic in the middle is\n> right. The origin paint_down function checks \"PARENT1 | PARENT2\" to see\n> if we found a merge base (even though PARENT2 may represent many tips).\n> Here I check whether we have _any_ \"left\" parent flag and _any_ \"right\"\n> parent flag. I'm not sure if I actually need to be finding the merge\n> base of _all_ of the commits.\n\nIn the one-each-on-two-side case (i.e. the original algorithm), it\nis \"any commit we will encounter by digging further down from a\nSTALE one will all be reachable from a newer merge base (e.g. the\ncommit that caused it to be marked as STALE originally). It will\nnever be a useful merge base, so let's mark it as STALE. Even if a\nfuture traversal that comes from sideways (i.e. not passing the\ncommit that caused it to be marked as STALE) reach this STALE one,\ndigging further from there won't give us anything new.\"\n\nIf you see a commit can be reached from L1 and R2, the only thing\nyou know is that its parents can also be reached from L1 and R2, but\nit does not tell you if it is reachable from other tips, e.g. L2 or\nR1. When a traversal reaches such a node from sideways, trying to\npaint it with L2 for example, you do need to continue digging.\n\nI think the traversal optimization based on the STALE bit is merely\na halfway optimization to cull obvious duplicates. See how\nget_merge_bases_many() needs to clean up redundant ones in the\nresult of merge_bases_many(), the latter of which does use the STALE\nbit to remove obvious duplicates, in order to make sure it won't\ninclude a commit in the result that can be reached from another\ncommit in the result, without having to resort to the SLOP trick.\n\nBecause your end-goal is to tell if Ln is reachable from Rm (for\nnumber of n's and m's), coming up with the independent/non-redundant\nset of merge-bases is not necessary, I think. I suspect that you do\nnot need the STALE half-optimization in the first place.\n\nThe only time you can say \"Ah, we've seen this one and no need to\ndig further\" is when you are propagating a colour C and the parent\nin question is already painted in C (it is OK to be painted as\nreachable from more tips), I would think, so shouldn't the loop be\nmore like, after painting each tip and placing it in the queue:\n\n * Dequeue one, check the L/R bits in it and call that C\n\n * Iterate over its parents P:\n\n * check the L/R bits in P and call that Cp.\n\n * If Cp is already a superset of C, there is no point putting P\n to the queue to be processed.\n\n * If Cp is not a superset of C, then update L/R bits in P to mark\n it reachable from tips represented by C and put P to the queue.\n\nuntil you ran out of queue?\n\n\n\n\n> +void commit_contains(const struct commit_list *left,\n> +\t\t const struct commit_list *right,\n> +\t\t unsigned char *left_contains,\n> +\t\t unsigned char *right_contains)\n> +{\n> +\tstruct prio_queue queue = { compare_commits_by_commit_date };\n> +\tstruct bit_slab left_bits, right_bits, stale_bits;\n> +\tint left_nr, right_nr;\n> +\n> +\tleft_nr = init_contains_bits(left, &left_bits, &queue);\n> +\tright_nr = init_contains_bits(right, &right_bits, &queue);\n> +\tinit_bit_slab(&stale_bits);\n> +\n> +\twhile (queue_has_nonstale_bits(&queue, &stale_bits)) {\n> +\t\tstruct commit *commit = prio_queue_get(&queue);\n> +\t\tstruct commit_list *parents;\n> +\t\tunsigned char *c_left, *c_right, *c_stale;\n> +\n> +\t\tc_left = bit_slab_at(&left_bits, commit);\n> +\t\tc_right = bit_slab_at(&right_bits, commit);\n> +\t\tc_stale = bit_slab_at(&stale_bits, commit);\n> +\n> +\t\tif (!bitset_empty(c_left, left_nr) &&\n> +\t\t !bitset_empty(c_right, right_nr))\n> +\t\t\t*c_stale = 1;\n\nHmph, is this one-char-a bit?\n"},{"id":"245037","messageId":"xmqqha374gx3.fsf@gitster.dls.corp.google.com","threadId":"37000","inReplyTo":"xmqqtx774i1r.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 6/8] commit: provide a fast multi-tip contains function","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-06-26T19:19:52Z","receivedAt":"2014-06-26T19:19:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> The only time you can say \"Ah, we've seen this one and no need to\n> dig further\" is when you are propagating a colour C and the parent\n> in question is already painted in C (it is OK to be painted as\n> reachable from more tips), I would think, so shouldn't the loop be\n> more like, after painting each tip and placing it in the queue:\n>\n> * Dequeue one, check the L/R bits in it and call that C\n>\n> * Iterate over its parents P:\n>\n> * check the L/R bits in P and call that Cp.\n>\n> * If Cp is already a superset of C, there is no point putting P\n> to the queue to be processed.\n>\n> * If Cp is not a superset of C, then update L/R bits in P to mark\n> it reachable from tips represented by C and put P to the queue.\n>\n> until you ran out of queue?\n\nActually that will cause you to dig down to the root, so it won't be\nnice.\n\nIf you are trying to do \"branch --with $commit\", what you would want\nis not exactly \"paint-down-to-common(all branches, $commit)\", but\nsomething that paints down to $commit from all branches, with an\noptimization that cuts off the traversal at a commit that is\nreachable from $commit. If a traversal from branch B reached such a\ncommit that is reachable from $commit, you can stop the traversal\nbecause propagating the bit for B further down to its parents will\nnot reach the $commit you are interested in.\n\nSo the termination condition for this a single Left (I'll use Left\nfor $commit and Right for \"all branches\") case is \"if a commit is\nalready painted as reachable from $commit, do not propagate bits\nfurther down\".\n\nWhat does it mean to look for \"branch --with $commit1 $commit2\"\n(i.e. more than one in the Left set)? If we are trying to see which\nbranches reach _both_ of these commits, then replace the ablve with\n\"if a commit is already painted as reachable from both $commit{1,2},\nthen painting it with any branch bits is futile---its parents will\nnever reach either $commit1 nor $commit2\", so the additional\ntermination condition will be \"If left bits are full, then stop\".\n\nI do not know how you can optimize the traversal if you are trying\nto see which branches reach at least one of these commits, though.\n"},{"id":"245039","messageId":"xmqqd2dv4gms.fsf@gitster.dls.corp.google.com","threadId":"37000","inReplyTo":"xmqqha374gx3.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 6/8] commit: provide a fast multi-tip contains function","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-06-26T19:26:03Z","receivedAt":"2014-06-26T19:26:03Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> What does it mean to look for \"branch --with $commit1 $commit2\"\n> (i.e. more than one in the Left set)? If we are trying to see which\n> branches reach _both_ of these commits, then replace the ablve with\n> \"if a commit is already painted as reachable from both $commit{1,2},\n> then painting it with any branch bits is futile---its parents will\n> never reach either $commit1 nor $commit2\", so the additional\n> termination condition will be \"If left bits are full, then stop\".\n>\n> I do not know how you can optimize the traversal if you are trying\n> to see which branches reach at least one of these commits, though.\n\nBy the way, don't we do 80% of this already in show-branch?\n"},{"id":"245152","messageId":"CAPig+cSc=A=+PR7oF43yeLpcd4n=Bd1KU1AHPfMKXEu5wAF4Ug@mail.gmail.com","threadId":"37000","inReplyTo":"20140625234000.GD23146@sigill.intra.peff.net","subject":"Re: [PATCH 4/8] add functions for memory-efficient bitmaps","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2014-06-29T07:41:37Z","receivedAt":"2014-06-29T07:41:37Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Wed, Jun 25, 2014 at 7:40 PM, Jeff King wrote:\n> We already have a nice-to-use bitmap implementation in\n> ewah/bitmap.c. It pretends to be infinitely long when asking\n> for a bit (and just returns 0 for bits that haven't been\n> allocated or set), and dynamically resizes as appropriate\n> when you set bits.\n>\n> The cost to this is that each bitmap must store its own\n> pointer and length, using up to 16 bytes per bitmap on top\n> of the actual bit storage. This is a lot of storage (not to\n> mention an extra level of pointer indirection) if you are\n> going to store one bitmap per commit in a traversal.\n>\n> These functions provide an alternative bitmap implementation\n> that can be used when you have a large number of fixed-size\n> bitmaps. See the documentation in the header file for\n> details and examples.\n>\n> Signed-off-by: Jeff King \n> ---\n> diff --git a/bitset.h b/bitset.h\n> new file mode 100644\n> index 0000000..5fbc956\n> --- /dev/null\n> +++ b/bitset.h\n> @@ -0,0 +1,113 @@\n> +#ifndef BITSET_H\n> +#define BITSET_H\n> +\n> + * Return the number of unsigned chars required to store num_bits bits.\n> + *\n> + * This is mostly used internally by the bitset functions, but you may need it\n> + * when allocating the bitset. Example:\n> + *\n> + * bits = xcalloc(1, bitset_sizeof(nr));\n> + */\n> +static inline int bitset_sizeof(int num_bits)\n> +{\n> + return (num_bits + CHAR_BIT - 1) / CHAR_BIT;\n> +}\n> +\n> +/*\n> + * Set the bit at position \"n\". \"n\" is counted from zero, and must be\n> + * smaller than the num_bits given to bitset_sizeof when allocating the bitset.\n> + */\n> +static inline void bitset_set(unsigned char *bits, int n)\n> +{\n> + bits[n / CHAR_BIT] |= 1 << (n % CHAR_BIT);\n> +}\n\nIs it intentional or an oversight that there is no way to clear a bit\nin the set?\n\n> +/*\n> + * Return the bit at position \"n\" (see bitset_set for a description of \"n\").\n> + */\n> +static inline int bitset_get(unsigned char *bits, int n)\n> +{\n> + return !!(bits[n / CHAR_BIT] & (1 << (n % CHAR_BIT)));\n> +}\n> +\n> +/*\n> + * Return true iff the bitsets contain the same bits. Each bitset should be the\n> + * same size, and should have been allocated using bitset_sizeof(max).\n> + *\n> + * Note that it is not safe to check partial equality by providing a smaller\n> + * \"max\" (we assume any bits beyond \"max\" up to the next CHAR_BIT boundary are\n> + * zeroed padding).\n> + */\n> +static inline int bitset_equal(unsigned char *a, unsigned char *b, int max)\n> +{\n> + int i;\n> + for (i = bitset_sizeof(max); i > 0; i--)\n> + if (*a++ != *b++)\n> + return 0;\n> + return 1;\n> +}\n> +\n> +/*\n> + * Bitwise-or the bitsets in \"dst\" and \"src\", and store the result in \"dst\".\n> + *\n> + * See bitset_equal for the definition of \"max\".\n> + */\n> +static inline void bitset_or(unsigned char *dst, const unsigned char *src, int max)\n> +{\n> + int i;\n> + for (i = bitset_sizeof(max); i > 0; i--)\n> + *dst++ |= *src++;\n> +}\n> +\n> +/*\n> + * Returns true iff the bitset contains all zeroes.\n> + *\n> + * See bitset_equal for the definition of \"max\".\n> + */\n> +static inline int bitset_empty(const unsigned char *bits, int max)\n> +{\n> + int i;\n> + for (i = bitset_sizeof(max); i > 0; i--, bits++)\n> + if (*bits)\n> + return 0;\n> + return 1;\n> +}\n> +\n> +#endif /* BITSET_H */\n> --\n> 2.0.0.566.gfe3e6b2\n"},{"id":"245207","messageId":"20140630170732.GA16747@sigill.intra.peff.net","threadId":"37000","inReplyTo":"CAPig+cSc=A=+PR7oF43yeLpcd4n=Bd1KU1AHPfMKXEu5wAF4Ug@mail.gmail.com","subject":"Re: [PATCH 4/8] add functions for memory-efficient bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-06-30T17:07:32Z","receivedAt":"2014-06-30T17:07:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jun 29, 2014 at 03:41:37AM -0400, Eric Sunshine wrote:\n\n> > +static inline void bitset_set(unsigned char *bits, int n)\n> > +{\n> > + bits[n / CHAR_BIT] |= 1 << (n % CHAR_BIT);\n> > +}\n> \n> Is it intentional or an oversight that there is no way to clear a bit\n> in the set?\n\nIntentional in the sense that I had no need for it in my series, and I\ndidn't think about it. I doubt many callers would want it, since commit\ntraversals tend to propagate bits through the graph, and then clean them\nup all at once. And the right way to clean up slabbed data like this is\nto just clear the slab.\n\nOf course somebody may use the code for something besides commit\ntraversals. But I'd rather avoid adding dead code on the off chance that\nsomebody uses it later (and then gets to find out whether it even works\nor not!).\n\n-Peff\n"},{"id":"245236","messageId":"xmqqionhxd3a.fsf@gitster.dls.corp.google.com","threadId":"37000","inReplyTo":"20140625233952.GC23146@sigill.intra.peff.net","subject":"Re: [PATCH 3/8] paint_down_to_common: use prio_queue","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-07-01T16:23:21Z","receivedAt":"2014-07-01T16:23:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> The downside is that our priority queue is not stable, which\n> means that commits with the same timestamp may not come out\n> in the order we put them in. You can see this in the test\n> update in t6024. That test does a recursive merge across a\n> set of commits that all have the same timestamp. For the\n> virtual ancestor, the test currently ends up with blob like\n> this:\n>\n> <<<<<<< Temporary merge branch 1\n> <<<<<<< Temporary merge branch 1\n> C\n> =======\n> B\n> >>>>>>> Temporary merge branch 2\n> =======\n> A\n> >>>>>>> Temporary merge branch 2\n>\n> but with this patch, the positions of B and A are swapped.\n> This is probably fine, as the order is an internal\n> implementation detail anyway (it would _not_ be fine if we\n> were using a priority queue for \"git log\" traversal, which\n> should show commits in parent order).\n\nInteresting that the queue is not \"stable\", but the test can still\nrely on a fixed output. While I tend to agree that for the purpose\nof this code path, the order is an internal implementation detail,\nbut I wonder if it would benefit us a lot if we taught prio-queue to\nbe optionally more \"stable\", which would allow us to use it in other\ncode paths that care. If we really wanted to, I would imagine that\nwe could keep the \"insertion counter\" in the elements of the queue\nto make the result stable (i.e. the \"void **array\" would become\nsomething like \"struct { int insertion_ctr; void *thing; } *array\").\n\n> I'm slightly hesitant because of the stability thing mentioned above. I\n> _think_ it's probably fine. But we could also implement a\n> stable_prio_queue on top of the existing prio_queue if we're concerned\n> (and that may be something we want to do anyway, because \"git log\" would\n> want that if it switched to a priority queue).\n\nHeh, I should have read the below-three-dashs commentary before\ncommenting (I often start working from the commit messages in \"git\nlog\" and then go back to the original thread).\n"},{"id":"245238","messageId":"xmqqegy5xbiu.fsf@gitster.dls.corp.google.com","threadId":"37000","inReplyTo":"20140630170732.GA16747@sigill.intra.peff.net","subject":"Re: [PATCH 4/8] add functions for memory-efficient bitmaps","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-07-01T16:57:13Z","receivedAt":"2014-07-01T16:57:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Sun, Jun 29, 2014 at 03:41:37AM -0400, Eric Sunshine wrote:\n>\n>> > +static inline void bitset_set(unsigned char *bits, int n)\n>> > +{\n>> > + bits[n / CHAR_BIT] |= 1 << (n % CHAR_BIT);\n>> > +}\n>> \n>> Is it intentional or an oversight that there is no way to clear a bit\n>> in the set?\n>\n> Intentional in the sense that I had no need for it in my series, and I\n> didn't think about it. I doubt many callers would want it, since commit\n> traversals tend to propagate bits through the graph, and then clean them\n> up all at once. And the right way to clean up slabbed data like this is\n> to just clear the slab.\n>\n> Of course somebody may use the code for something besides commit\n> traversals. But I'd rather avoid adding dead code on the off chance that\n> somebody uses it later (and then gets to find out whether it even works\n> or not!).\n\nAnother thing I noticed was that the definition of and the\ncommentary on bitset_equal() and bitset_empty() sounded somewhat\n\"undecided\". These functions take \"max\" that is deliberately named\ndifferently from \"num_bits\" (the width of the bitsets involved),\ninviting to use them for testing only earlier bits in the bitset as\nlong as the caller understands the caveat, but the caveat requires\nthat the partial bitset to test must be byte-aligned, which makes it\nnot very useful in practice, which means we probably do not want\nthem to be used for any \"max\" other than \"num_bits\".\n\nThey probably would want either:\n\n * be made to truly honor max < num_bits case, by special casing the\n last byte that has max-th bit, to officially allow them to be\n used for partial bitset test; or\n\n * take \"num_bits\", not \"max\", to clarify that callers must use them\n only on the full bitset.\n\nIn either case, there needs another item in the \"caller's responsibility\"\nlist at the beginning of bitset.h:\n\n 4. Ensure that padding bits at the end of the bitset array are\n initialized to 0.\n\nIn the description of bitset_sizeof(), the comment hints it by using\nxcalloc() in the example, but a careless user may be tempted to\nimplement bitset_clr() and then do:\n\n int i;\n unsigned char *bits = malloc(bitset_sizeof(nr));\n for (i = 0; i < nr; i++)\n \tbitset_clr(bits, i);\n\tassert(bitset_empty(bits, nr));\n\nand the implementation of bitset_empty(), even if we rename\ns/max/num_bits/, will choke if (nr % CHAR_BIT) and malloc() gave us\nnon-zero bit in the padding.\n\nFor the sake of simplicity, I am inclined to vote for not allowing\ntheir use on a partial-sub-bitset.\n"},{"id":"245241","messageId":"20140701171051.GA7282@sigill.intra.peff.net","threadId":"37000","inReplyTo":"xmqqionhxd3a.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 3/8] paint_down_to_common: use prio_queue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-07-01T17:10:51Z","receivedAt":"2014-07-01T17:10:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 01, 2014 at 09:23:21AM -0700, Junio C Hamano wrote:\n\n> > but with this patch, the positions of B and A are swapped.\n> > This is probably fine, as the order is an internal\n> > implementation detail anyway (it would _not_ be fine if we\n> > were using a priority queue for \"git log\" traversal, which\n> > should show commits in parent order).\n> \n> Interesting that the queue is not \"stable\", but the test can still\n> rely on a fixed output.\n\nI think it is deterministic for a particular sequence of inserts/pops,\nbut not stable with respect to insertion order.\n\n> While I tend to agree that for the purpose\n> of this code path, the order is an internal implementation detail,\n> but I wonder if it would benefit us a lot if we taught prio-queue to\n> be optionally more \"stable\", which would allow us to use it in other\n> code paths that care. If we really wanted to, I would imagine that\n> we could keep the \"insertion counter\" in the elements of the queue\n> to make the result stable (i.e. the \"void **array\" would become\n> something like \"struct { int insertion_ctr; void *thing; } *array\").\n\nYeah, I think the reasons to be stable are:\n\n 1. To be on the safe side for operations like this where it\n _shouldn't_ matter, but perhaps there are hidden dependencies we\n don't know of.\n\n 2. To make it easier for later callers to use prio-queue for cases\n where it does matter (and I think \"git log\" is one of these).\n\nIf we can do it without a big performance loss (and I don't see any\nreason it should be any worse than a slight bump to the constant-factor\nof the logarithmic operations), it probably makes sense to.\n\nI'll take a look at it (in fact, I already implemented something like it\nonce long ago in the thread I linked to earlier). My sense of taste says\nit should be a stable_prio_queue implemented on top of prio_queue (i.e.,\nstoring pointers to the struct you mention above). That means you can\nstill use the unstable one if you want the (presumably minor)\nperformance benefit, and it keeps the logic nice and tidy.\n\nBut given that we have implemented prio_queue using void pointers, I\nthink it would introduce an extra pointer per item and an extra layer of\nindirection on each access. So maybe it is better to just build it in.\n\nThe low-cost alternative is to implement prio_queue to hold items of\narbitrary size. I'm not sure if that is the worth the complexity and\nmaintenance cost.\n\n> Heh, I should have read the below-three-dashs commentary before\n> commenting (I often start working from the commit messages in \"git\n> log\" and then go back to the original thread).\n\nI always wonder how people read those. I tend to write them as if people\nhave (just) read the commit message, but not yet read the patch.\n\n-Peff\n\nPS Thanks for your earlier comments on the actual commit-slab painting\n algorithm. Responding to those is taking more thinking, and I haven't\n gotten to it yet, but it's on my agenda.\n"},{"id":"245242","messageId":"20140701171759.GB7282@sigill.intra.peff.net","threadId":"37000","inReplyTo":"xmqqegy5xbiu.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 4/8] add functions for memory-efficient bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-07-01T17:18:00Z","receivedAt":"2014-07-01T17:18:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 01, 2014 at 09:57:13AM -0700, Junio C Hamano wrote:\n\n> Another thing I noticed was that the definition of and the\n> commentary on bitset_equal() and bitset_empty() sounded somewhat\n> \"undecided\". These functions take \"max\" that is deliberately named\n> differently from \"num_bits\" (the width of the bitsets involved),\n> inviting to use them for testing only earlier bits in the bitset as\n> long as the caller understands the caveat, but the caveat requires\n> that the partial bitset to test must be byte-aligned, which makes it\n> not very useful in practice, which means we probably do not want\n> them to be used for any \"max\" other than \"num_bits\".\n\nYeah, I added that comment because I found \"max\" to be confusing, but\ncouldn't think of a better name. I'm not sure why \"num_bits\" did not\noccur to me, as that makes it completely obvious.\n\n> * take \"num_bits\", not \"max\", to clarify that callers must use them\n> only on the full bitset.\n\nThis seems like the right solution to me. Handling partially aligned\nbytes adds to the complexity and may hurt performance (in fact, I think\nbitset_equal could actually just call memcmp, which I should fix).\nThat's fine if callers care about that feature, but I actually don't\nanticipate any that do.\n\nBy the way, I chose \"unsigned char\" as the storage format somewhat\narbitrarily. Performance might be better with \"unsigned int\" or even\n\"unsigned long\". It means potentially wasting more space, but not more\nthan one word (minus a byte) per commit (so about 3MB on linux.git).\nI'll try to do some timings to see if it's worth doing.\n\n> In either case, there needs another item in the \"caller's responsibility\"\n> list at the beginning of bitset.h:\n> \n> 4. Ensure that padding bits at the end of the bitset array are\n> initialized to 0.\n\nAgreed. That is definitely a requirement I had in mind, but I didn't\nthink to write it down.\n\nI'll fix both points in the re-roll.\n\n-Peff\n"},{"id":"245245","messageId":"xmqq1tu5x9ao.fsf@gitster.dls.corp.google.com","threadId":"37000","inReplyTo":"20140625234252.GE23146@sigill.intra.peff.net","subject":"Re: [PATCH 5/8] string-list: add pos to iterator callback","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-07-01T17:45:19Z","receivedAt":"2014-07-01T17:45:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> When we are running a string-list foreach or filter, the\n> callback function sees only the string_list_item, along with\n> a void* data pointer provided by the caller. This is\n> sufficient for most purposes.\n>\n> However, it can also be useful to know the position of the\n> item within the string (for example, if the data pointer\n\ns/the string/&-list/ (or s/&/&_list/).\n\n> points to a secondary array in which each element\n> corresponds to part of the string list). We can help this\n> use case by providing the position to each callback.\n>\n> Signed-off-by: Jeff King \n> ---\n> The diff here is noisy, and I expect in the long run that the one caller\n> I add to builtin/tag.c later in the series will eventually stop using\n> string_list entirely (in favor of a custom struct), which may leave us\n> with no callers that actually use the new field.\n>\n> I do think the logic above is sound, though, and it's a potentially\n> useful thing. There may be other sites that avoid the for_each wrapper\n> in favor of iterating themselves simply _because_ they needed to know\n> the position (I would just do the same here, except that my new caller\n> wants to use filter_string_list, which is a little more complicated).\n\nWhile I can buy that some callers would want to learn the pos in the\nlist, I am not sure if this is a good direction to go. Primarily, I\nam having trouble sifting between \"want\" and \"need\".\n\nHow often do callers want to do this? If only narrow specialized\ncallers want this, is it unreasonable to ask them to add a \"int ctr\"\nin their cb_data and use \"pos = ((struct theirs *)cb_data)->ctr++\"\nin their callback instead?\n"},{"id":"245247","messageId":"xmqqwqbxvtaa.fsf@gitster.dls.corp.google.com","threadId":"37000","inReplyTo":"xmqqha374gx3.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 6/8] commit: provide a fast multi-tip contains function","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-07-01T18:16:29Z","receivedAt":"2014-07-01T18:16:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> If you are trying to do \"branch --with $commit\", what you would want\n> is not exactly \"paint-down-to-common(all branches, $commit)\", but\n> something that paints down to $commit from all branches, with an\n> optimization that cuts off the traversal at a commit that is\n> reachable from $commit. If a traversal from branch B reached such a\n> commit that is reachable from $commit, you can stop the traversal\n> because propagating the bit for B further down to its parents will\n> not reach the $commit you are interested in.\n\nI forgot about the other direction, i.e. \"branch --merged $commit\".\nSince I do \"git branch --no-merged pu\" fairly often, I care about\nits performance ;-)\n\nWe paint $commit as Left, and tips of all the branches as Right. We\ntry to paint down from $commit but the traversal cannot terminate if\nit reaches a commit that is reachable from one Right ref---we may\nfind that we can reach more Right refs by following its ancestor.\nWe can stop when we paint Right bits fully, of course, but I wonder\nif we can do better than that.\n\nSuppose we just painted a commit with L and Rn bit (i.e. the commit\nis a common ancestor of the $commit and one branch). We know that\ntraversing down from there will never reach the tip of the branch\nwhose color is Rn (otherwise we will have a cycle from that commit\nback to the tip of the branch), so if the reason we are continuing\nthe traversal is to prove that the tip of the branch Rn is reachable\n(or unreachable) from $commit, there is no reason to continue\ndigging from there. Can we exploit that to terminate the traversal\nearlier?\n\nWhen we encounter a new commit that is painted with L bit and some\nbut not necessarily all R bits, we propagate the bits and check the\nR bits. Some of the commits in Right set that correspond to R bits\nmay have been painted in L (i.e. we found branches that are merged\nto $commit), and digging further from this commit will not give us\nany new information. Other commits are not painted in L (i.e. we do\nnot yet know if $commit merges these branches), so we may need to\nkeep digging. So perhaps we can stop if a commit is painted in L\nand also has all the R bits that correspond to Right commits that\nare not yet proven reachable from $commit (i.e. not painted in L)?\n"},{"id":"245248","messageId":"20140701190037.GA15828@sigill.intra.peff.net","threadId":"37000","inReplyTo":"xmqq1tu5x9ao.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 5/8] string-list: add pos to iterator callback","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-07-01T19:00:37Z","receivedAt":"2014-07-01T19:00:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 01, 2014 at 10:45:19AM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > When we are running a string-list foreach or filter, the\n> > callback function sees only the string_list_item, along with\n> > a void* data pointer provided by the caller. This is\n> > sufficient for most purposes.\n> >\n> > However, it can also be useful to know the position of the\n> > item within the string (for example, if the data pointer\n> \n> s/the string/&-list/ (or s/&/&_list/).\n\nThanks, yeah.\n\n> While I can buy that some callers would want to learn the pos in the\n> list, I am not sure if this is a good direction to go. Primarily, I\n> am having trouble sifting between \"want\" and \"need\".\n> \n> How often do callers want to do this? If only narrow specialized\n> callers want this, is it unreasonable to ask them to add a \"int ctr\"\n> in their cb_data and use \"pos = ((struct theirs *)cb_data)->ctr++\"\n> in their callback instead?\n\nNot all that often, I suppose (I only add one caller in this series). I\njust found it a little hack-ish to force callers to keep their own\ncounter when we already have it (especially because it is not too hard\nto get it wrong, for example by forgetting to increment the counter in\none code path of the callback).\n\nHere's what the caller would look like without \"pos\" (done as a patch on\ntop of the series, so pos is still there, but no longer used).\n\ndiff --git a/builtin/tag.c b/builtin/tag.c\nindex f17192c..dc6f105 100644\n--- a/builtin/tag.c\n+++ b/builtin/tag.c\n@@ -151,14 +151,20 @@ static int util_is_not_null(struct string_list_item *it, int pos, void *data)\n \treturn !!it->util;\n }\n \n-static int matches_contains(struct string_list_item *it, int pos, void *data)\n+struct contains_callback_data {\n+\tint ctr;\n+\tunsigned char *contains;\n+};\n+\n+static int matches_contains(struct string_list_item *it, int pos, void *vdata)\n {\n-\tunsigned char *contains = data;\n-\treturn contains[pos];\n+\tstruct contains_callback_data *data = vdata;\n+\treturn data->contains[data->ctr++];\n }\n \n static void limit_by_contains(struct string_list *tags, struct commit_list *with)\n {\n+\tstruct contains_callback_data cbdata;\n \tstruct commit_list *tag_commits = NULL, **tail = &tag_commits;\n \tunsigned char *result;\n \tint i;\n@@ -180,7 +186,10 @@ static void limit_by_contains(struct string_list *tags, struct commit_list *with\n \n \tresult = xmalloc(tags->nr);\n \tcommit_contains(with, tag_commits, NULL, result);\n-\tfilter_string_list(tags, 1, matches_contains, result);\n+\n+\tcbdata.ctr = 0;\n+\tcbdata.contains = result;\n+\tfilter_string_list(tags, 1, matches_contains, &cbdata);\n \n \tfree(result);\n \tfree_commit_list(tag_commits);\n\nSo I think it's a small change in a lot of places rather than a kind of\nugly change in one spot.\n\nAll that being said, I think the real issue here is that I want more\nthan a string list (I am already using the util field for the sha1, but\nthis code would be potentially simpler if I could also store the commit\nobject). In the long run I hope to factor out a ref-listing API that can\nbe used by tag, branch, and for-each-ref. And then this string-list code\nwould go away in favor of a more expansive struct. So it may not be\nworth worrying about keeping it too clean.\n\n-Peff\n"},{"id":"245249","messageId":"xmqqoax8x56n.fsf@gitster.dls.corp.google.com","threadId":"37000","inReplyTo":"xmqqwqbxvtaa.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 6/8] commit: provide a fast multi-tip contains function","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-07-01T19:14:08Z","receivedAt":"2014-07-01T19:14:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> I forgot about the other direction, i.e. \"branch --merged $commit\".\n> Since I do \"git branch --no-merged pu\" fairly often, I care about\n> its performance ;-)\n>\n> We paint $commit as Left, and tips of all the branches as Right. We\n> try to paint down from $commit but the traversal cannot terminate if\n> it reaches a commit that is reachable from one Right ref---we may\n> find that we can reach more Right refs by following its ancestor.\n> We can stop when we paint Right bits fully, of course, but I wonder\n> if we can do better than that.\n>\n> Suppose we just painted a commit with L and Rn bit (i.e. the commit\n> is a common ancestor of the $commit and one branch). We know that\n> traversing down from there will never reach the tip of the branch\n> whose color is Rn (otherwise we will have a cycle from that commit\n> back to the tip of the branch), so if the reason we are continuing\n> the traversal is to prove that the tip of the branch Rn is reachable\n> (or unreachable) from $commit, there is no reason to continue\n> digging from there. Can we exploit that to terminate the traversal\n> earlier?\n\nI forgot to mention this case because with \"branch --no-merged pu\"\nit never happens, but another clue we can terminate traversal earier\nwith is when $commit is found to be an ancestor of some Right\ncommits. Then we can start ignoring Rn bits for these Right commits\nthat can reach the Left one, as we know they can never be reached\nfrom the Left. That is, the last sentence in the paragraph ...\n\n> When we encounter a new commit that is painted with L bit and some\n> but not necessarily all R bits, we propagate the bits and check the\n> R bits. Some of the commits in Right set that correspond to R bits\n> may have been painted in L (i.e. we found branches that are merged\n> to $commit), and digging further from this commit will not give us\n> any new information. Other commits are not painted in L (i.e. we do\n> not yet know if $commit merges these branches), so we may need to\n> keep digging. So perhaps we can stop if a commit is painted in L\n> and also has all the R bits that correspond to Right commits that\n> are not yet proven reachable from $commit (i.e. not painted in L)?\n\n... will be more like \"ignore Rn bits for Right commits that are\npainted in L (i.e. they are reachable from L) or the Left commit is\npainted with (i.e. they reach L)\".\n"}]}