{"thread":{"id":"35678","subject":"[PATCH 0/5] diff_filespec cleanups and optimizations","startedAt":"2014-01-17T01:18:45Z","lastAt":"2014-01-17T23:50:50Z","messageCount":10,"participants":["Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"233241","messageId":"20140117011844.GA6870@sigill.intra.peff.net","threadId":"35678","inReplyTo":null,"subject":"[PATCH 0/5] diff_filespec cleanups and optimizations","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-17T01:18:45Z","receivedAt":"2014-01-17T01:18:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"I recently came across a repository with a commit containing 100 million\npaths in its tree. Cleverly, the whole repo fits into a 1.5K packfile\n(can you guess how it was done?). Not so cleverly, running \"diff-tree\n--root\" on that commit uses a large amount of memory. :)\n\nI do not think it is worth optimizing for such a pathological\nrepository. But I was curious how much it would want (it OOM'd on my\n64-bit 16G machine). The answer is roughly:\n\n 100,000,000 * (\n 8 bytes per pointer to diff_filepair in the diff_queue\n + 32 bytes per diff_filepair struct\n + 2 * (\n 96 bytes per diff_filespec struct\n + 12 bytes per filename (in this case)\n )\n )\n\nwhich is about 25G. Plus malloc overhead. So obviously this example is\nunreasonable. A more reasonable large case is something like WebKit at\n~150K files, doing a diff against the empty tree. That's only 37M.\n\nBut while looking at it, I noticed a bunch of cleanups for\ndiff_filespec. With the patches below, sizeof(struct diff_filespec) on\nmy 64-bit machine goes from 96 bytes down to 80. Compiling with \"-m32\"\ngoes from 64 bytes down to 52.\n\nThe first few patches have cleanup value aside from the struct size\nimprovement. The last two are pure optimization. I doubt the\noptimization is noticeable for any real-life cases, so I don't mind if\nthey get dropped. But they're quite trivial and obvious.\n\n [1/5]: diff_filespec: reorder dirty_submodule macro definitions\n [2/5]: diff_filespec: drop funcname_pattern_ident field\n [3/5]: diff_filespec: drop xfrm_flags field\n [4/5]: diff_filespec: reorder is_binary field\n [5/5]: diff_filespec: use only 2 bits for is_binary flag\n\n-Peff\n"},{"id":"233242","messageId":"20140117011945.GA7249@sigill.intra.peff.net","threadId":"35678","inReplyTo":"20140117011844.GA6870@sigill.intra.peff.net","subject":"[PATCH 1/5] diff_filespec: reorder dirty_submodule macro definitions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-17T01:19:46Z","receivedAt":"2014-01-17T01:19:46Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"diff_filespec has a 2-bit \"dirty_submodule\" field and\ndefines two flags as macros. Originally these were right\nnext to each other, but a new field was accidentally added\nin between in commit 4682d85. This patch puts the field and\nits flags back together.\n\nUsing an enum like:\n\n enum {\n\t DIRTY_SUBMODULE_UNTRACKED = 1,\n\t DIRTY_SUBMODULE_MODIFIED = 2\n } dirty_submodule;\n\nwould be more obvious, but it bloats the structure. Limiting\nthe enum size like:\n\n } dirty_submodule : 2;\n\nmight work, but it is not portable.\n\nSigned-off-by: Jeff King \n---\n diffcore.h | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/diffcore.h b/diffcore.h\nindex 1c16c85..f822f9e 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -43,9 +43,9 @@ struct diff_filespec {\n \tunsigned should_free : 1; /* data should be free()'ed */\n \tunsigned should_munmap : 1; /* data should be munmap()'ed */\n \tunsigned dirty_submodule : 2; /* For submodules: its work tree is dirty */\n-\tunsigned is_stdin : 1;\n #define DIRTY_SUBMODULE_UNTRACKED 1\n #define DIRTY_SUBMODULE_MODIFIED 2\n+\tunsigned is_stdin : 1;\n \tunsigned has_more_entries : 1; /* only appear in combined diff */\n \tstruct userdiff_driver *driver;\n \t/* data should be considered \"binary\"; -1 means \"don't know yet\" */\n-- \n1.8.5.2.500.g8060133\n"},{"id":"233243","messageId":"20140117012011.GB7249@sigill.intra.peff.net","threadId":"35678","inReplyTo":"20140117011844.GA6870@sigill.intra.peff.net","subject":"[PATCH 2/5] diff_filespec: drop funcname_pattern_ident field","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-17T01:20:11Z","receivedAt":"2014-01-17T01:20:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This struct field was obsoleted by be58e70 (diff: unify\nexternal diff and funcname parsing code, 2008-10-05), but we\nforgot to remove it.\n\nSigned-off-by: Jeff King \n---\n8 bytes of our size savings come here...\n\n diffcore.h | 1 -\n 1 file changed, 1 deletion(-)\n\ndiff --git a/diffcore.h b/diffcore.h\nindex f822f9e..92e4d48 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -29,7 +29,6 @@ struct diff_filespec {\n \tchar *path;\n \tvoid *data;\n \tvoid *cnt_data;\n-\tconst char *funcname_pattern_ident;\n \tunsigned long size;\n \tint count; /* Reference count */\n \tint xfrm_flags;\t\t /* for use by the xfrm */\n-- \n1.8.5.2.500.g8060133\n"},{"id":"233244","messageId":"20140117012158.GC7249@sigill.intra.peff.net","threadId":"35678","inReplyTo":"20140117011844.GA6870@sigill.intra.peff.net","subject":"[PATCH 3/5] diff_filespec: drop xfrm_flags field","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-17T01:21:59Z","receivedAt":"2014-01-17T01:21:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The only mention of this field in the code is by some\ndebugging code which prints it out (and it will always be\nzero, since we never touch it otherwise). It was obsoleted\nvery early on by 25d5ea4 ([PATCH] Redo rename/copy detection\nlogic., 2005-05-24).\n\nSigned-off-by: Jeff King \n---\nNo savings here on 64-bit, since this ended up going to padding, but it\nis what makes the next patch work.\n\n diff.c | 4 ++--\n diffcore.h | 1 -\n 2 files changed, 2 insertions(+), 3 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex 6b4cd0e..8e4a6a9 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -4139,9 +4139,9 @@ void diff_debug_filespec(struct diff_filespec *s, int x, const char *one)\n \t\tDIFF_FILE_VALID(s) ? \"valid\" : \"invalid\",\n \t\ts->mode,\n \t\ts->sha1_valid ? sha1_to_hex(s->sha1) : \"\");\n-\tfprintf(stderr, \"queue[%d] %s size %lu flags %d\\n\",\n+\tfprintf(stderr, \"queue[%d] %s size %lu\\n\",\n \t\tx, one ? one : \"\",\n-\t\ts->size, s->xfrm_flags);\n+\t\ts->size);\n }\n \n void diff_debug_filepair(const struct diff_filepair *p, int i)\ndiff --git a/diffcore.h b/diffcore.h\nindex 92e4d48..22993e1 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -31,7 +31,6 @@ struct diff_filespec {\n \tvoid *cnt_data;\n \tunsigned long size;\n \tint count; /* Reference count */\n-\tint xfrm_flags;\t\t /* for use by the xfrm */\n \tint rename_used; /* Count of rename users */\n \tunsigned short mode;\t /* file mode */\n \tunsigned sha1_valid : 1; /* if true, use sha1 and trust mode;\n-- \n1.8.5.2.500.g8060133\n"},{"id":"233245","messageId":"20140117012255.GD7249@sigill.intra.peff.net","threadId":"35678","inReplyTo":"20140117011844.GA6870@sigill.intra.peff.net","subject":"[PATCH 4/5] diff_filespec: reorder is_binary field","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-17T01:22:56Z","receivedAt":"2014-01-17T01:22:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The middle of the diff_filespec struct contains a mixture of\nints, shorts, and bit-fields, followed by a pointer. On an\nx86-64 system with an LP64 or LLP64 data model (i.e., most\nof them), the integers and flags end up being padded out by\n41 bits to put the pointer at an 8-byte boundary.\n\nAfter the pointer, we have the \"int is_binary\" field, which\nis only 32 bits. We end up wasting another 32 bits to pad\nthe struct size up to a multiple of 64 bits.\n\nWe can move the is_binary field before the pointer, which\nlets the compiler store it where we used to have padding.\nThis shrinks the top padding to only 9 bits (from the\nbit-fields), and eliminates the bottom padding entirely,\ndropping the struct size from 88 to 80 bytes.\n\nOn a 32-bit system, there is no benefit, but nor should\nthere be any harm (we only need 4-byte alignment there, so\nwe were already using only 9 bits of padding).\n\nSigned-off-by: Jeff King \n---\n\n diffcore.h | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/diffcore.h b/diffcore.h\nindex 22993e1..d911bf0 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -45,9 +45,9 @@ struct diff_filespec {\n #define DIRTY_SUBMODULE_MODIFIED 2\n \tunsigned is_stdin : 1;\n \tunsigned has_more_entries : 1; /* only appear in combined diff */\n-\tstruct userdiff_driver *driver;\n \t/* data should be considered \"binary\"; -1 means \"don't know yet\" */\n \tint is_binary;\n+\tstruct userdiff_driver *driver;\n };\n \n extern struct diff_filespec *alloc_filespec(const char *);\n-- \n1.8.5.2.500.g8060133\n"},{"id":"233246","messageId":"20140117012540.GE7249@sigill.intra.peff.net","threadId":"35678","inReplyTo":"20140117011844.GA6870@sigill.intra.peff.net","subject":"[PATCH 5/5] diff_filespec: use only 2 bits for is_binary flag","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-17T01:25:40Z","receivedAt":"2014-01-17T01:25:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The is_binary flag needs only three values: -1, 0, and 1.\nHowever, we use a whole 32-bit int for it on most systems\n(both 32- and 64- bit).\n\nInstead, we can mark it to use only 2 bits. On 32-bit\nsystems, this lets it end up as part of the bitfield above\n(saving 4 bytes). On 64-bit systems, we don't see any change\n(because the savings end up as padding), but it does leave\nroom for another \"free\" 32-bit value to be added later.\n\nSigned-off-by: Jeff King \n---\nI don't typically use bit-sized integers like this for anything but\nunsigned integers to be used as flags. My understanding is that using\nsigned integers is explicitly permitted by the standard. I don't know if\nwe're guaranteed a 2's-complement representation, but I can't imagine an\nimplementation providing any range besides -2..1, which is what we need.\n\n diffcore.h | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/diffcore.h b/diffcore.h\nindex d911bf0..79de8cf 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -46,7 +46,7 @@ struct diff_filespec {\n \tunsigned is_stdin : 1;\n \tunsigned has_more_entries : 1; /* only appear in combined diff */\n \t/* data should be considered \"binary\"; -1 means \"don't know yet\" */\n-\tint is_binary;\n+\tint is_binary : 2;\n \tstruct userdiff_driver *driver;\n };\n \n-- \n1.8.5.2.500.g8060133\n"},{"id":"233297","messageId":"xmqqha92xx7g.fsf@gitster.dls.corp.google.com","threadId":"35678","inReplyTo":"20140117011945.GA7249@sigill.intra.peff.net","subject":"Re: [PATCH 1/5] diff_filespec: reorder dirty_submodule macro definitions","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-01-17T18:46:59Z","receivedAt":"2014-01-17T18:46:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> diff_filespec has a 2-bit \"dirty_submodule\" field and\n> defines two flags as macros. Originally these were right\n> next to each other, but a new field was accidentally added\n> in between in commit 4682d85.\n\nInteresting.\n\n - 4682d852 (diff-index.c: \"git diff\" has no need to read blob from\n the standard input, 2012-06-27) wants to use this rule: all the\n bitfield definitions first, and then whatever macro constants\n next.\n\n - 25e5e2bf (combine-diff: support format_callback, 2011-08-19),\n wants to use a different rule: a run of (one bitfield definition\n and zero-or-more macro constants to be used in that bitfield).\n\nWhen they were merged together at d7afe648 (Merge branch\n'jc/refactor-diff-stdin', 2012-07-13), these two conflicting\nphilosophies crashed.\n\nThat is the commit to be blamed for this mess ;-)\n\nI am of course fine with the end result this patch gives us.\n\nThanks.\n\n> This patch puts the field and\n> its flags back together.\n>\n> Using an enum like:\n>\n> enum {\n> \t DIRTY_SUBMODULE_UNTRACKED = 1,\n> \t DIRTY_SUBMODULE_MODIFIED = 2\n> } dirty_submodule;\n>\n> would be more obvious, but it bloats the structure. Limiting\n> the enum size like:\n>\n> } dirty_submodule : 2;\n>\n> might work, but it is not portable.\n>\n> Signed-off-by: Jeff King \n> ---\n> diffcore.h | 2 +-\n> 1 file changed, 1 insertion(+), 1 deletion(-)\n>\n> diff --git a/diffcore.h b/diffcore.h\n> index 1c16c85..f822f9e 100644\n> --- a/diffcore.h\n> +++ b/diffcore.h\n> @@ -43,9 +43,9 @@ struct diff_filespec {\n> \tunsigned should_free : 1; /* data should be free()'ed */\n> \tunsigned should_munmap : 1; /* data should be munmap()'ed */\n> \tunsigned dirty_submodule : 2; /* For submodules: its work tree is dirty */\n> -\tunsigned is_stdin : 1;\n> #define DIRTY_SUBMODULE_UNTRACKED 1\n> #define DIRTY_SUBMODULE_MODIFIED 2\n> +\tunsigned is_stdin : 1;\n> \tunsigned has_more_entries : 1; /* only appear in combined diff */\n> \tstruct userdiff_driver *driver;\n> \t/* data should be considered \"binary\"; -1 means \"don't know yet\" */\n"},{"id":"233298","messageId":"xmqqd2jqxx2x.fsf@gitster.dls.corp.google.com","threadId":"35678","inReplyTo":"20140117011844.GA6870@sigill.intra.peff.net","subject":"Re: [PATCH 0/5] diff_filespec cleanups and optimizations","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-01-17T18:49:42Z","receivedAt":"2014-01-17T18:49:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> But while looking at it, I noticed a bunch of cleanups for\n> diff_filespec. With the patches below, sizeof(struct diff_filespec) on\n> my 64-bit machine goes from 96 bytes down to 80. Compiling with \"-m32\"\n> goes from 64 bytes down to 52.\n>\n> The first few patches have cleanup value aside from the struct size\n> improvement. The last two are pure optimization. I doubt the\n> optimization is noticeable for any real-life cases, so I don't mind if\n> they get dropped. But they're quite trivial and obvious.\n\nThanks for a pleasant read.\n"},{"id":"233308","messageId":"20140117194724.GA775@sigill.intra.peff.net","threadId":"35678","inReplyTo":"xmqqha92xx7g.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 1/5] diff_filespec: reorder dirty_submodule macro definitions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-17T19:47:25Z","receivedAt":"2014-01-17T19:47:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jan 17, 2014 at 10:46:59AM -0800, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > diff_filespec has a 2-bit \"dirty_submodule\" field and\n> > defines two flags as macros. Originally these were right\n> > next to each other, but a new field was accidentally added\n> > in between in commit 4682d85.\n> \n> Interesting.\n> \n> - 4682d852 (diff-index.c: \"git diff\" has no need to read blob from\n> the standard input, 2012-06-27) wants to use this rule: all the\n> bitfield definitions first, and then whatever macro constants\n> next.\n> \n> - 25e5e2bf (combine-diff: support format_callback, 2011-08-19),\n> wants to use a different rule: a run of (one bitfield definition\n> and zero-or-more macro constants to be used in that bitfield).\n> \n> When they were merged together at d7afe648 (Merge branch\n> 'jc/refactor-diff-stdin', 2012-07-13), these two conflicting\n> philosophies crashed.\n> \n> That is the commit to be blamed for this mess ;-)\n\nThat makes sense. I had assumed it was a mis-merge initially, so was\nsurprised to find 4682d85. It just looked like an error to me, but the\nrule you gave above does at least make sense.\n\nI'm happy with it either way. I almost just pulled the macro\ndefinitions, including DIFF_FILE_VALID, out of the struct definition\ncompletely. I see the value in having the flags near their bitfield, but\nit makes the definition a bit harder to read.\n\n> I am of course fine with the end result this patch gives us.\n\nMe too, though if you feel like doing it the other way, I'm fine with\nthat, too.\n\n-Peff\n"},{"id":"233329","messageId":"xmqq1u06w4kl.fsf@gitster.dls.corp.google.com","threadId":"35678","inReplyTo":"20140117194724.GA775@sigill.intra.peff.net","subject":"Re: [PATCH 1/5] diff_filespec: reorder dirty_submodule macro definitions","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-01-17T23:50:50Z","receivedAt":"2014-01-17T23:50:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I'm happy with it either way. I almost just pulled the macro\n> definitions, including DIFF_FILE_VALID, out of the struct definition\n> completely. I see the value in having the flags near their bitfield, but\n> it makes the definition a bit harder to read.\n\nYeah, my thoughts exactly when I did those two conflicting changes.\nI have a slight preference \"Constants go with the fields they are\nused in\" over \"fields and macros mixed together is harder to read\",\nso let's use your patch as-is.\n"}]}