patch, 5 partsdiff_filespec cleanups and optimizations

I recently came across a repository with a commit containing 100 million paths in its tree. Cleverly, the whole repo fits into a 1.5K packfile (can you guess how it was done?). Not so cleverly, running "diff-tree --root" on that commit uses a large amount of memory. :)

I do not think it is worth optimizing for such a pathological repository. But I was curious how much it would want (it OOM'd on my 64-bit 16G machine). The answer is roughly:

   100,000,000 * (
      8 bytes per pointer to diff_filepair in the diff_queue
    + 32 bytes per diff_filepair struct
    +  2 * (
         96 bytes per diff_filespec struct
       + 12 bytes per filename (in this case)
     )
  )

which is about 25G. Plus malloc overhead. So obviously this example is unreasonable. A more reasonable large case is something like WebKit at ~150K files, doing a diff against the empty tree. That's only 37M.

But while looking at it, I noticed a bunch of cleanups for diff_filespec. With the patches below, sizeof(struct diff_filespec) on my 64-bit machine goes from 96 bytes down to 80. Compiling with "-m32" goes from 64 bytes down to 52.

The first few patches have cleanup value aside from the struct size improvement. The last two are pure optimization. I doubt the optimization is noticeable for any real-life cases, so I don't mind if they get dropped. But they're quite trivial and obvious.

  [1/5]: diff_filespec: reorder dirty_submodule macro definitions
  [2/5]: diff_filespec: drop funcname_pattern_ident field
  [3/5]: diff_filespec: drop xfrm_flags field
  [4/5]: diff_filespec: reorder is_binary field
  [5/5]: diff_filespec: use only 2 bits for is_binary flag

-Peff

diff_filespec has a 2-bit "dirty_submodule" field and defines two flags as macros. Originally these were right next to each other, but a new field was accidentally added in between in commit 4682d85. This patch puts the field and its flags back together.

Using an enum like:

  enum {
	  DIRTY_SUBMODULE_UNTRACKED = 1,
	  DIRTY_SUBMODULE_MODIFIED = 2
  } dirty_submodule;

would be more obvious, but it bloats the structure. Limiting the enum size like:

  } dirty_submodule : 2;

might work, but it is not portable.

Signed-off-by: Jeff King <peff@peff.net>
---
 diffcore.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Jeff King <peff@peff.net> writes:

Interesting.

 - 4682d852 (diff-index.c: "git diff" has no need to read blob from
   the standard input, 2012-06-27) wants to use this rule: all the
   bitfield definitions first, and then whatever macro constants
   next.

 - 25e5e2bf (combine-diff: support format_callback, 2011-08-19),
   wants to use a different rule: a run of (one bitfield definition
   and zero-or-more macro constants to be used in that bitfield).

When they were merged together at d7afe648 (Merge branch 'jc/refactor-diff-stdin', 2012-07-13), these two conflicting philosophies crashed.

That is the commit to be blamed for this mess ;-)

I am of course fine with the end result this patch gives us.

Thanks.

On Fri, Jan 17, 2014 at 10:46:59AM -0800, Junio C Hamano wrote:

That makes sense. I had assumed it was a mis-merge initially, so was surprised to find 4682d85. It just looked like an error to me, but the rule you gave above does at least make sense.

I'm happy with it either way. I almost just pulled the macro definitions, including DIFF_FILE_VALID, out of the struct definition completely. I see the value in having the flags near their bitfield, but it makes the definition a bit harder to read.

Me too, though if you feel like doing it the other way, I'm fine with that, too.

-Peff

Jeff King <peff@peff.net> writes:

Yeah, my thoughts exactly when I did those two conflicting changes. I have a slight preference "Constants go with the fields they are used in" over "fields and macros mixed together is harder to read", so let's use your patch as-is.

This struct field was obsoleted by be58e70 (diff: unify external diff and funcname parsing code, 2008-10-05), but we forgot to remove it.

Signed-off-by: Jeff King <peff@peff.net>
---
8 bytes of our size savings come here...

 diffcore.h | 1 -
 1 file changed, 1 deletion(-)

The only mention of this field in the code is by some debugging code which prints it out (and it will always be zero, since we never touch it otherwise). It was obsoleted very early on by 25d5ea4 ([PATCH] Redo rename/copy detection logic., 2005-05-24).

Signed-off-by: Jeff King <peff@peff.net>
---
No savings here on 64-bit, since this ended up going to padding, but it
is what makes the next patch work.

 diff.c     | 4 ++--
 diffcore.h | 1 -
 2 files changed, 2 insertions(+), 3 deletions(-)

The middle of the diff_filespec struct contains a mixture of ints, shorts, and bit-fields, followed by a pointer. On an x86-64 system with an LP64 or LLP64 data model (i.e., most of them), the integers and flags end up being padded out by 41 bits to put the pointer at an 8-byte boundary.

After the pointer, we have the "int is_binary" field, which is only 32 bits. We end up wasting another 32 bits to pad the struct size up to a multiple of 64 bits.

We can move the is_binary field before the pointer, which lets the compiler store it where we used to have padding. This shrinks the top padding to only 9 bits (from the bit-fields), and eliminates the bottom padding entirely, dropping the struct size from 88 to 80 bytes.

On a 32-bit system, there is no benefit, but nor should there be any harm (we only need 4-byte alignment there, so we were already using only 9 bits of padding).

Signed-off-by: Jeff King <peff@peff.net>
---

 diffcore.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

The is_binary flag needs only three values: -1, 0, and 1. However, we use a whole 32-bit int for it on most systems (both 32- and 64- bit).

Instead, we can mark it to use only 2 bits. On 32-bit systems, this lets it end up as part of the bitfield above (saving 4 bytes). On 64-bit systems, we don't see any change (because the savings end up as padding), but it does leave room for another "free" 32-bit value to be added later.

Signed-off-by: Jeff King <peff@peff.net>
---
I don't typically use bit-sized integers like this for anything but
unsigned integers to be used as flags. My understanding is that using
signed integers is explicitly permitted by the standard. I don't know if
we're guaranteed a 2's-complement representation, but I can't imagine an
implementation providing any range besides -2..1, which is what we need.

 diffcore.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Jeff King <peff@peff.net> writes:

Thanks for a pleasant read.