fast-import's gfi_unpack_entry causes too many munmap/mmap cycles

fast-import's gfi_unpack_entry causes too many munmap/mmap cycles

[Mike Hommey]

Hi,

I think I've mentioned this issue in the past, and fixed one case of
munmap/mmap cycle in fast-import. I've found more cases where this can
happen, and while on Linux, it's not a problem, on OSX, it leads to
catastrophic performance, when the import is massive.

One part of the problem is that gfi_unpack_entry just assumes that as
long as the pack was touched since last access, it _has_ to close all
windows and remap the pack. Afaict, when the requested entry is in the
range of what was previously mapped, there is no reason to do this, and
the following patch would help:

diff --git a/fast-import.c b/fast-import.c
index 75f7748..91fa2a1 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -1294,7 +1294,8 @@ static void *gfi_unpack_entry(
 {
        enum object_type type;
        struct packed_git *p = all_packs[oe->pack_id];
-       if (p == pack_data && p->pack_size < (pack_size + 20)) {
+       if (p == pack_data && oe->idx.offset >= (p->pack_size - 20) &&
+           p->pack_size < (pack_size + 20)) {
                /* The object is stored in the packfile we are writing to
                 * and we have modified it since the last time we scanned
                 * back to read a previously written object.  If an old

Now, the problem is that this doesn't help with use cases like the
following:
- create commit A.
- get its tree with `ls :mark ""`

In that case, since the tree was (very likely) created by committing,
the entry is located beyond the open window for the pack.

There is some kind of work around for that particular use case: get the
tree *during* the commit, with `ls ""` after all the
filemodify/filedelete entries, and before the newline that finishes the
commit. Unfortunately, in that case, store_tree does its job twice (once
for the ls, and once when committing for real), and that leads to
significant overhead.

And even if I am okay with that overhead, I still hit the problem again
when using that tree later with `M 040000 $sha1 ` in the next commit,
because that does a load_tree() for the tree sha1, after a commit having
occurred, which touched the pack, bringing me back to square one (the
sad part being that it does so while the tree_content for the tree in
question is already in memory).

Now, while each individual case could be improved to avoid
gfi_unpack_entry, it seems to me it would be better to make
gfi_unpack_entry better somehow. I wonder if there's not a better way
than having it close and reopen windows all the time for recent objects.
Can't the pack be pre-allocated and mapped by window-size fragments, for
example? (Would that maybe not work properly on all platforms?)

Mike

PS: And if I could find a work around that does work with existing
releases of git, that would be great. The root of all my pain is that I
have tree deltas between consecutive commits, when the commits are not
necessarily parent/child. e.g. for a commit history like

A --- B
 \
  \-- C

I have:
- diff between null-tree and A
- diff between A and B
- diff between B and C

Which means for C, I *need* to create a commit without a `from`, and
initialize its tree with `M 040000 sha-1-of-B's-tree `.

Re: fast-import's gfi_unpack_entry causes too many munmap/mmap cycles

[Mike Hommey]

On Sat, Apr 16, 2016 at 06:18:39PM +0900, Mike Hommey wrote:
> Now, while each individual case could be improved to avoid
> gfi_unpack_entry, it seems to me it would be better to make
> gfi_unpack_entry better somehow.

Come to think of it, there are cases that might still be worth fixing.
Like avoiding load_tree() altogether when doing `M 040000 $sha1 ` when
there is no other filemodify/filedelete following.

Mike

Re: fast-import's gfi_unpack_entry causes too many munmap/mmap cycles

[Mike Hommey]

On Sat, Apr 16, 2016 at 06:18:39PM +0900, Mike Hommey wrote:
> And even if I am okay with that overhead, I still hit the problem again
> when using that tree later with `M 040000 $sha1 ` in the next commit,
> because that does a load_tree() for the tree sha1, after a commit having
> occurred, which touched the pack, bringing me back to square one (the
> sad part being that it does so while the tree_content for the tree in
> question is already in memory).

So, interestingly, the load_tree() doesn't happen when using `from
0000000000000000000000000000000000000000\nmerge :mark` for the commit.

That is, with:
  commit refs/foo
  committer <foo@foo> 0 +0
  data 0

  M 040000 bff3a42ecae0e7c8f707d328f9432c1ffe9644b0 ""

load_tree is called. And with:
  commit refs/foo
  committer <foo@foo> 0 +0
  data 0

  from 0000000000000000000000000000000000000000
  merge :mark_of_parent
  M 040000 bff3a42ecae0e7c8f707d328f9432c1ffe9644b0 ""

it's not called.

So I think I got myself a workaround...

> A --- B
>  \
>   \-- C
> 
> I have:
> - diff between null-tree and A
> - diff between A and B
> - diff between B and C

I should be able to do:

- start the commit command for A
- before finishing it, `ls ""`
- then apply the diff for B and `ls ""`
- then apply the diff for C and `ls ""`
- then `deleteall`
- then `M 040000 sha1_from_first_ls ` and finally finish A
- create the commit for B with `from
  0000000000000000000000000000000000000000\nmerge :mark` and `M 040000
  sha1_from_second_ls`
- likewise for C

... and avoid gfi_unpack_entry.

Mike

Re: fast-import's gfi_unpack_entry causes too many munmap/mmap cycles

[Mike Hommey]

On Sat, Apr 16, 2016 at 08:04:03PM +0900, Mike Hommey wrote:
> So I think I got myself a workaround...
> 
> > A --- B
> >  \
> >   \-- C
> > 
> > I have:
> > - diff between null-tree and A
> > - diff between A and B
> > - diff between B and C
> 
> I should be able to do:
> 
> - start the commit command for A
> - before finishing it, `ls ""`
> - then apply the diff for B and `ls ""`
> - then apply the diff for C and `ls ""`
> - then `deleteall`
> - then `M 040000 sha1_from_first_ls ` and finally finish A
> - create the commit for B with `from
>   0000000000000000000000000000000000000000\nmerge :mark` and `M 040000
>   sha1_from_second_ls`
> - likewise for C
> 
> ... and avoid gfi_unpack_entry.

And it works... as an avoidance of gfi_unpack_entry... but it has its
own problem: somehow the store_tree() that happens for each of those
`ls ""` commands is storing *all* trees. Even the ones that haven't
changed. In terms of a minimalistic fast-import script:

With:
  commit refs/FOO
  committer <foo@foo> 0 +0
  data 0

  M 644 inline a/a
  data 1
  a

  commit refs/FOO
  committer <foo@foo> 0 +0
  data 0

  M 644 inline b/b
  data 1
  b

store_tree is called for:
- b39954843ff6e09ec3aa2b942938c30c6bd1629e
- 2c3b59f77afa6fea6c1a380eeb0cb1eb292515b5
- 51e58bf6ce558dd384bbf9d493f9a376f3bcb089
- a97dda9f3a819113b3b239b9a62edece27136080

With:
  commit refs/FOO
  committer <foo@foo> 0 +0
  data 0

  M 644 inline a/a
  data 1
  a
  ls ""
  M 644 inline b/b
  data 1
  b

store_tree is called for:
- b39954843ff6e09ec3aa2b942938c30c6bd1629e
- 2c3b59f77afa6fea6c1a380eeb0cb1eb292515b5
- b39954843ff6e09ec3aa2b942938c30c6bd1629e
- 51e58bf6ce558dd384bbf9d493f9a376f3bcb089
- a97dda9f3a819113b3b239b9a62edece27136080

Note how b39954843ff6e09ec3aa2b942938c30c6bd1629e is being stored twice
(it's the tree for a/).

So in the scenario I'm testing, which has many more trees, I'm trading
29k gfi_unpack_entry calls and 230k store_tree calls for 1.96M
store_tree calls. On even larger trees, I'm not sure that wouldn't make
things even worse than they already are with gfi_unpack_entry.

Mike

Re: fast-import's gfi_unpack_entry causes too many munmap/mmap cycles

[Mike Hommey]

On Sun, Apr 17, 2016 at 09:54:43AM +0900, Mike Hommey wrote:
> On Sat, Apr 16, 2016 at 08:04:03PM +0900, Mike Hommey wrote:
> > So I think I got myself a workaround...
> > 
> > > A --- B
> > >  \
> > >   \-- C
> > > 
> > > I have:
> > > - diff between null-tree and A
> > > - diff between A and B
> > > - diff between B and C
> > 
> > I should be able to do:
> > 
> > - start the commit command for A
> > - before finishing it, `ls ""`
> > - then apply the diff for B and `ls ""`
> > - then apply the diff for C and `ls ""`
> > - then `deleteall`
> > - then `M 040000 sha1_from_first_ls ` and finally finish A
> > - create the commit for B with `from
> >   0000000000000000000000000000000000000000\nmerge :mark` and `M 040000
> >   sha1_from_second_ls`
> > - likewise for C
> > 
> > ... and avoid gfi_unpack_entry.
> 
> And it works... as an avoidance of gfi_unpack_entry... but it has its
> own problem: somehow the store_tree() that happens for each of those
> `ls ""` commands is storing *all* trees. Even the ones that haven't
> changed. In terms of a minimalistic fast-import script:
> 
> With:
>   commit refs/FOO
>   committer <foo@foo> 0 +0
>   data 0
> 
>   M 644 inline a/a
>   data 1
>   a
> 
>   commit refs/FOO
>   committer <foo@foo> 0 +0
>   data 0
> 
>   M 644 inline b/b
>   data 1
>   b
> 
> store_tree is called for:
> - b39954843ff6e09ec3aa2b942938c30c6bd1629e
> - 2c3b59f77afa6fea6c1a380eeb0cb1eb292515b5
> - 51e58bf6ce558dd384bbf9d493f9a376f3bcb089
> - a97dda9f3a819113b3b239b9a62edece27136080
> 
> With:
>   commit refs/FOO
>   committer <foo@foo> 0 +0
>   data 0
> 
>   M 644 inline a/a
>   data 1
>   a
>   ls ""
>   M 644 inline b/b
>   data 1
>   b
> 
> store_tree is called for:
> - b39954843ff6e09ec3aa2b942938c30c6bd1629e
> - 2c3b59f77afa6fea6c1a380eeb0cb1eb292515b5
> - b39954843ff6e09ec3aa2b942938c30c6bd1629e
> - 51e58bf6ce558dd384bbf9d493f9a376f3bcb089
> - a97dda9f3a819113b3b239b9a62edece27136080
> 
> Note how b39954843ff6e09ec3aa2b942938c30c6bd1629e is being stored twice
> (it's the tree for a/).

And that happens because tree_content_get returns a duplicate of the
tree, so when parse_ls does a store_tree, it does it on a duplicate, not
on the tree itself. So all the work done by store_tree through parse_ls
is thrown away.

Mike