From: Junio C Hamano <hidden> Date: 2021-09-29 04:08:05
Jeff King [off-list ref] writes:
Side note: The pretend_object_file() approach is actually even better,
because we know the object is fake. So it does not confuse
write_object_file()'s "do we already have this object" freshening
check.
I suspect it could even be made faster than the tmp_objdir approach.
From our perspective, these objects really are tempfiles. So we could
write them as such, not worrying about things like fsyncing them,
naming them into place, etc. We could just write them out, then mmap
the results, and put the pointers into cached_objects (currently it
insists on malloc-ing a copy of the input buffer, but that seems like
an easy extension to add).
In fact, I think you could get away with just _one_ tempfile per
merge. Open up one tempfile. Write out all of the objects you want to
"store" into it in sequence, and record the lseek() offsets before and
after for each object. Then mmap the whole result, and stuff the
appropriate pointers (based on arithmetic with the offsets) into the
cached_objects list.
Cute. The remerge diff code path creates a full tree that records
the mechanical merge result. By hooking into the lowest layer of
write_object() interface, we'd serialize all objects in such a tree
in the order they are computed (bottom up from the leaf level, I'd
presume) into a single flat file ;-)
From: Jeff King <hidden> Date: 2021-09-30 07:33:56
On Tue, Sep 28, 2021 at 09:08:00PM -0700, Junio C Hamano wrote:
Jeff King [off-list ref] writes:
quoted
Side note: The pretend_object_file() approach is actually even better,
because we know the object is fake. So it does not confuse
write_object_file()'s "do we already have this object" freshening
check.
I suspect it could even be made faster than the tmp_objdir approach.
From our perspective, these objects really are tempfiles. So we could
write them as such, not worrying about things like fsyncing them,
naming them into place, etc. We could just write them out, then mmap
the results, and put the pointers into cached_objects (currently it
insists on malloc-ing a copy of the input buffer, but that seems like
an easy extension to add).
In fact, I think you could get away with just _one_ tempfile per
merge. Open up one tempfile. Write out all of the objects you want to
"store" into it in sequence, and record the lseek() offsets before and
after for each object. Then mmap the whole result, and stuff the
appropriate pointers (based on arithmetic with the offsets) into the
cached_objects list.
Cute. The remerge diff code path creates a full tree that records
the mechanical merge result. By hooking into the lowest layer of
write_object() interface, we'd serialize all objects in such a tree
in the order they are computed (bottom up from the leaf level, I'd
presume) into a single flat file ;-)
I do still like this approach, but just two possible gotchas I was
thinking of:
- This side-steps all of our usual code for getting object data into
memory. In general, I'd expect this content to not be too enormous,
but it _could_ be if there are many / large blobs in the result. So
we may end up with large maps. Probably not a big deal on modern
64-bit systems. Maybe an issue on 32-bit systems, just because of
virtual address space.
Likewise, we do support systems with NO_MMAP. They'd work here, but
it would probably mean putting all that object data into the heap. I
could live with that, given how rare such systems are these days, and
that it only matters if you're using --remerge-diff with big blobs.
- I wonder to what degree --remerge-diff benefits from omitting writes
for objects we already have. I.e., if you are writing out a whole
tree representing the conflicted state, then you don't want to write
all of the trees that aren't interesting. Hopefully the code is
already figuring out which paths the merge even touched, and ignoring
the rest. It probably benefits performance-wise from
write_object_file() deciding to skip some object writes, as well
(e.g., for resolutions which the final tree already took, as they'd
be in the merge commit). The whole pretend-we-have-this-object thing
may want to likewise make sure we don't write out objects that we
already have in the real odb.
-Peff
On Tue, Sep 28, 2021 at 09:08:00PM -0700, Junio C Hamano wrote:
quoted
Jeff King [off-list ref] writes:
quoted
Side note: The pretend_object_file() approach is actually even better,
because we know the object is fake. So it does not confuse
write_object_file()'s "do we already have this object" freshening
check.
I suspect it could even be made faster than the tmp_objdir approach.
From our perspective, these objects really are tempfiles. So we could
write them as such, not worrying about things like fsyncing them,
naming them into place, etc. We could just write them out, then mmap
the results, and put the pointers into cached_objects (currently it
insists on malloc-ing a copy of the input buffer, but that seems like
an easy extension to add).
In fact, I think you could get away with just _one_ tempfile per
merge. Open up one tempfile. Write out all of the objects you want to
"store" into it in sequence, and record the lseek() offsets before and
after for each object. Then mmap the whole result, and stuff the
appropriate pointers (based on arithmetic with the offsets) into the
cached_objects list.
Cute. The remerge diff code path creates a full tree that records
the mechanical merge result. By hooking into the lowest layer of
write_object() interface, we'd serialize all objects in such a tree
in the order they are computed (bottom up from the leaf level, I'd
presume) into a single flat file ;-)
I do still like this approach, but just two possible gotchas I was
thinking of:
- This side-steps all of our usual code for getting object data into
memory. In general, I'd expect this content to not be too enormous,
but it _could_ be if there are many / large blobs in the result. So
we may end up with large maps. Probably not a big deal on modern
64-bit systems. Maybe an issue on 32-bit systems, just because of
virtual address space.
Likewise, we do support systems with NO_MMAP. They'd work here, but
it would probably mean putting all that object data into the heap. I
could live with that, given how rare such systems are these days, and
that it only matters if you're using --remerge-diff with big blobs.
- I wonder to what degree --remerge-diff benefits from omitting writes
for objects we already have. I.e., if you are writing out a whole
tree representing the conflicted state, then you don't want to write
all of the trees that aren't interesting. Hopefully the code is
already figuring out which paths the merge even touched, and ignoring
the rest. It probably benefits performance-wise from
write_object_file() deciding to skip some object writes, as well
(e.g., for resolutions which the final tree already took, as they'd
be in the merge commit). The whole pretend-we-have-this-object thing
may want to likewise make sure we don't write out objects that we
already have in the real odb.
I haven't benchmarked since my core.checkCollisions RFC patch[1]
resulted in the somewhat related loose object cache patch from you, and
not with something like the midx, but just a note that on some setups
just writing things out is faster than exhaustively checking if we
absolutely need to write things out.
I also wonder how much if anything writing out the one file v.s. lots of
loose objects is worthwhile on systems where we could write out those
loose objects on a ramdisk, which is commonly available on e.g. Linux
distros these days out of the box. If you care about performance but not
about your transitory data using a ramdisk is generally much better than
any other potential I/O optimization.
Finally, and I don't mean to throw a monkey wrench into this whole
discussion, so take this as a random musing: I wonder how much faster
this thing could be on its second run if instead of avoiding writing to
the store & cleaning up, it just wrote to the store, and then wrote
another object keyed on the git version and any revision paramaters
etc., and then pretty much just had to do a "git cat-file -p <that-obj>"
to present the result to the user :)
I suppose that would be throwing a lot more work at an eventual "git gc"
than we ever do now, so maybe it's a bit crazy, but I think it might be
an interesting direction in general to (ab)use either the primary or
some secondary store in the .git dir as a semi-permanent cache of
resolved queries from the likes of "git log".
1. https://lore.kernel.org/git/20181028225023.26427-5-avarab@gmail.com/
From: Jeff King <hidden> Date: 2021-09-30 21:00:24
On Thu, Sep 30, 2021 at 03:16:19PM +0200, Ævar Arnfjörð Bjarmason wrote:
I also wonder how much if anything writing out the one file v.s. lots of
loose objects is worthwhile on systems where we could write out those
loose objects on a ramdisk, which is commonly available on e.g. Linux
distros these days out of the box. If you care about performance but not
about your transitory data using a ramdisk is generally much better than
any other potential I/O optimization.
I'd think in general we won't be using a ramdisk, because tmp_objdir is
putting its directory inside $GIT_DIR/objects. It doesn't _have_ to, but
using a ramdisk works against its original purpose (which was to store
potentially quite a lot of data from an incoming push, and to be able to
rename it cheaply into its final resting place).
It would probably not be too hard to provide a flag that indicates the
intended use, though (and then we decide where to create the temporary
directory based on that).
Finally, and I don't mean to throw a monkey wrench into this whole
discussion, so take this as a random musing: I wonder how much faster
this thing could be on its second run if instead of avoiding writing to
the store & cleaning up, it just wrote to the store, and then wrote
another object keyed on the git version and any revision paramaters
etc., and then pretty much just had to do a "git cat-file -p <that-obj>"
to present the result to the user :)
I suppose that would be throwing a lot more work at an eventual "git gc"
than we ever do now, so maybe it's a bit crazy, but I think it might be
an interesting direction in general to (ab)use either the primary or
some secondary store in the .git dir as a semi-permanent cache of
resolved queries from the likes of "git log".
I don't think it's crazy to just write the objects to the main object
store. We already generate cruft objects for some other operations
(Junio asked elsewhere in the thread about virtual trees for recursive
merges; I don't know the answer offhand, but I'd guess we do there).
They do get cleaned up eventually.
I'm not sure it helps performance much by itself. In a merge (or even
just writing a tree out from the index), by the time you realize you
already have the object, you've done most of the work to generate it.
I think what you're describing is to make some kind of cache structure
on top. That might be sensible (and indeed, the index already does this
with the cachetree extension). But it can also easily come later if the
objects are just in the regular odb.
-Peff
On Thu, Sep 30, 2021 at 6:31 AM Ævar Arnfjörð Bjarmason
[off-list ref] wrote:
On Thu, Sep 30 2021, Jeff King wrote:
quoted
On Tue, Sep 28, 2021 at 09:08:00PM -0700, Junio C Hamano wrote:
quoted
Jeff King [off-list ref] writes:
quoted
Side note: The pretend_object_file() approach is actually even better,
because we know the object is fake. So it does not confuse
write_object_file()'s "do we already have this object" freshening
check.
I suspect it could even be made faster than the tmp_objdir approach.
From our perspective, these objects really are tempfiles. So we could
write them as such, not worrying about things like fsyncing them,
naming them into place, etc. We could just write them out, then mmap
the results, and put the pointers into cached_objects (currently it
insists on malloc-ing a copy of the input buffer, but that seems like
an easy extension to add).
In fact, I think you could get away with just _one_ tempfile per
merge. Open up one tempfile. Write out all of the objects you want to
"store" into it in sequence, and record the lseek() offsets before and
after for each object. Then mmap the whole result, and stuff the
appropriate pointers (based on arithmetic with the offsets) into the
cached_objects list.
Cute. The remerge diff code path creates a full tree that records
the mechanical merge result. By hooking into the lowest layer of
write_object() interface, we'd serialize all objects in such a tree
in the order they are computed (bottom up from the leaf level, I'd
presume) into a single flat file ;-)
I do still like this approach, but just two possible gotchas I was
thinking of:
- This side-steps all of our usual code for getting object data into
memory. In general, I'd expect this content to not be too enormous,
but it _could_ be if there are many / large blobs in the result. So
we may end up with large maps. Probably not a big deal on modern
64-bit systems. Maybe an issue on 32-bit systems, just because of
virtual address space.
Likewise, we do support systems with NO_MMAP. They'd work here, but
it would probably mean putting all that object data into the heap. I
could live with that, given how rare such systems are these days, and
that it only matters if you're using --remerge-diff with big blobs.
- I wonder to what degree --remerge-diff benefits from omitting writes
for objects we already have. I.e., if you are writing out a whole
tree representing the conflicted state, then you don't want to write
all of the trees that aren't interesting. Hopefully the code is
already figuring out which paths the merge even touched, and ignoring
the rest. It probably benefits performance-wise from
write_object_file() deciding to skip some object writes, as well
(e.g., for resolutions which the final tree already took, as they'd
be in the merge commit). The whole pretend-we-have-this-object thing
may want to likewise make sure we don't write out objects that we
already have in the real odb.
I haven't benchmarked since my core.checkCollisions RFC patch[1]
resulted in the somewhat related loose object cache patch from you, and
not with something like the midx, but just a note that on some setups
just writing things out is faster than exhaustively checking if we
absolutely need to write things out.
I also wonder how much if anything writing out the one file v.s. lots of
loose objects is worthwhile on systems where we could write out those
loose objects on a ramdisk, which is commonly available on e.g. Linux
distros these days out of the box. If you care about performance but not
about your transitory data using a ramdisk is generally much better than
any other potential I/O optimization.
Finally, and I don't mean to throw a monkey wrench into this whole
discussion, so take this as a random musing: I wonder how much faster
this thing could be on its second run if instead of avoiding writing to
the store & cleaning up, it just wrote to the store, and then wrote
It'd be _much_ slower. My first implementation in fact did that; it
just wrote objects to the store, left them there, and didn't bother to
do any auto-gcs. It slowed down quite a bit as it ran. Adding
auto-gc's during the run were really slow too. But stepping back,
gc'ing objects that I already knew were garbage seemed like a waste;
why not just prune them pre-emptively? To do so, though, I'd have to
track all the individual objects I added to make sure I didn't prune
something else. Following that idea and a few different attempts
eventually led me to the discovery of tmp_objdir.
In case it's not clear to you why just writing all the objects to the
normal store and leaving them there slows things down so much...
Let's say 1 in 10 merges had originally needed some kind of conflict
resolution (either in the outer merge or in the inner merge for the
virtual merge bases), meaning that 9 out of 10 merges traversed by
--remerge-diff don't write any objects. Now for each merge for which
--remerge-diff does need to create conflicted blobs and new trees,
let's say it writes on average 3 blobs and 7 trees. (I don't know the
real average numbers, it could well be ~5 total, but ~10 seems a
realistic first order approximation and it makes the math easy.)
Then, if we keep all objects we write, then `git log --remerge-diff`
on a history with 100,000 merge commits, will have added 100,000 loose
objects by the time it finishes. That means that all diff and merge
operations slow down considerably as it runs due to all the extra
loose objects.
another object keyed on the git version and any revision paramaters
etc., and then pretty much just had to do a "git cat-file -p <that-obj>"
to present the result to the user :)
So caching the full `git log ...` output, based on a hash of the
command line flags, and then merely re-showing it later? And having
that output be invalidated as soon as any head advances? Or are you
thinking of caching the output per-commit based on a hash of the other
command line flags...potentially slowing non-log operations down with
the huge number of loose objects?
I suppose that would be throwing a lot more work at an eventual "git gc"
than we ever do now, so maybe it's a bit crazy, but I think it might be
an interesting direction in general to (ab)use either the primary or
some secondary store in the .git dir as a semi-permanent cache of
resolved queries from the likes of "git log".
If you do per-commit caching, and the user scrolls through enough
output (not hard to do, just searching the output for some string
often is enough), that "eventual" git-gc will be the very next git
operation. If you cache the entire output, it'll be invalidated
pretty quickly. So I don't see how this works. Or am I
misunderstanding something you're suggesting here?
On Thu, Sep 30, 2021 at 12:33 AM Jeff King [off-list ref] wrote:
On Tue, Sep 28, 2021 at 09:08:00PM -0700, Junio C Hamano wrote:
quoted
Jeff King [off-list ref] writes:
quoted
Side note: The pretend_object_file() approach is actually even better,
because we know the object is fake. So it does not confuse
write_object_file()'s "do we already have this object" freshening
check.
I suspect it could even be made faster than the tmp_objdir approach.
From our perspective, these objects really are tempfiles. So we could
write them as such, not worrying about things like fsyncing them,
naming them into place, etc. We could just write them out, then mmap
the results, and put the pointers into cached_objects (currently it
insists on malloc-ing a copy of the input buffer, but that seems like
an easy extension to add).
In fact, I think you could get away with just _one_ tempfile per
merge. Open up one tempfile. Write out all of the objects you want to
"store" into it in sequence, and record the lseek() offsets before and
after for each object. Then mmap the whole result, and stuff the
appropriate pointers (based on arithmetic with the offsets) into the
cached_objects list.
Cute. The remerge diff code path creates a full tree that records
the mechanical merge result. By hooking into the lowest layer of
write_object() interface, we'd serialize all objects in such a tree
in the order they are computed (bottom up from the leaf level, I'd
presume) into a single flat file ;-)
I do still like this approach, but just two possible gotchas I was
thinking of:
- This side-steps all of our usual code for getting object data into
memory. In general, I'd expect this content to not be too enormous,
but it _could_ be if there are many / large blobs in the result. So
we may end up with large maps. Probably not a big deal on modern
64-bit systems. Maybe an issue on 32-bit systems, just because of
virtual address space.
Likewise, we do support systems with NO_MMAP. They'd work here, but
it would probably mean putting all that object data into the heap. I
could live with that, given how rare such systems are these days, and
that it only matters if you're using --remerge-diff with big blobs.
Um, I'm starting to get uncomfortable with this pretend_object stuff.
Part of the reason that merge-ort isn't truly "in memory" despite
attempting to do exactly that, was because for large enough repos with
enough files modified on both sides, I wasn't comfortable assuming
that all new files from three-way content merges and all new trees fit
into memory. I'm sure we'd be fine with current-day linux kernel
sized repos. No big deal. In fact, most merges probably don't add
more than a few dozen new files. But for microsoft-sized repos, and
with repos tending to grow over time, more so when the tools
themselves scale nicely (which we've all been working on enabling),
makes me worry there might be enough new objects within a single merge
(especially given the recursive inner merges) that we might need to
worry about this.
- I wonder to what degree --remerge-diff benefits from omitting writes
for objects we already have. I.e., if you are writing out a whole
tree representing the conflicted state, then you don't want to write
all of the trees that aren't interesting. Hopefully the code is
already figuring out which paths the merge even touched, and ignoring
the rest.
Not only do you want to avoid writing all of the trees that aren't
interesting, you also want to avoid traversing into them in the first
place and avoid doing trivial file merges for each entry underneath.
Sadly, merge-recursive did anyway. Because renames and directory
renames can sometimes throw a big wrench in the desire to avoid
traversing into such directories. Figuring out how to avoid it was
kind of tricky, but merge-ort definitely handles this when it can
safely do so; see the cover letter for my trivial directory resolution
series[1].
[1] https://lore.kernel.org/git/pull.988.v4.git.1626841444.gitgitgadget@gmail.com/
It probably benefits performance-wise from
write_object_file() deciding to skip some object writes, as well
(e.g., for resolutions which the final tree already took, as they'd
be in the merge commit).
Yes, it will also benefit from that, but the much bigger side is
avoiding needlessly recursing into directories unchanged on (at least)
one side.
The whole pretend-we-have-this-object thing
may want to likewise make sure we don't write out objects that we
already have in the real odb.
Right, so I'd have to copy the relevant logic from write_object_file()
-- I think that means instead of write_object_file()'s calls to
freshen_packed_object() and freshen_loose_object() that I instead call
find_pack_entry() and make has_loose_object() in object-file.c not be
static and then call it. Does that sound right?
Of course, that's assuming we're okay with this pretend_object thing,
which I'm starting to worry about.
From: Jeff King <hidden> Date: 2021-10-01 05:27:47
On Thu, Sep 30, 2021 at 09:26:37PM -0700, Elijah Newren wrote:
quoted
- This side-steps all of our usual code for getting object data into
memory. In general, I'd expect this content to not be too enormous,
but it _could_ be if there are many / large blobs in the result. So
we may end up with large maps. Probably not a big deal on modern
64-bit systems. Maybe an issue on 32-bit systems, just because of
virtual address space.
Likewise, we do support systems with NO_MMAP. They'd work here, but
it would probably mean putting all that object data into the heap. I
could live with that, given how rare such systems are these days, and
that it only matters if you're using --remerge-diff with big blobs.
Um, I'm starting to get uncomfortable with this pretend_object stuff.
Part of the reason that merge-ort isn't truly "in memory" despite
attempting to do exactly that, was because for large enough repos with
enough files modified on both sides, I wasn't comfortable assuming
that all new files from three-way content merges and all new trees fit
into memory. I'm sure we'd be fine with current-day linux kernel
sized repos. No big deal. In fact, most merges probably don't add
more than a few dozen new files. But for microsoft-sized repos, and
with repos tending to grow over time, more so when the tools
themselves scale nicely (which we've all been working on enabling),
makes me worry there might be enough new objects within a single merge
(especially given the recursive inner merges) that we might need to
worry about this.
I do think we need to consider that the content might be larger than
will comfortably fit in memory. But the point of using mmap is that we
don't have to care. The OS is taking care of it for us (just like it
would in regular object files).
The question is just whether we're comfortable assuming that mmap
exists if you're working on such a large repository. I'd guess that big
repos are pretty painful with out it (and again, I'm not even clear
which systems Git runs on even lack mmap these days). So IMHO this isn't
really a blocker for going in this direction.
quoted
The whole pretend-we-have-this-object thing
may want to likewise make sure we don't write out objects that we
already have in the real odb.
Right, so I'd have to copy the relevant logic from write_object_file()
-- I think that means instead of write_object_file()'s calls to
freshen_packed_object() and freshen_loose_object() that I instead call
find_pack_entry() and make has_loose_object() in object-file.c not be
static and then call it. Does that sound right?
Yes. You _could_ call the same freshening functions, but I think since
we know that our objects are throw-away anyway, we do not even need to
perform that freshening operation. I think just has_object_file() would
be sufficient for your needs.
-Peff
On Thu, Sep 30, 2021 at 6:31 AM Ævar Arnfjörð Bjarmason
[off-list ref] wrote:
quoted
On Thu, Sep 30 2021, Jeff King wrote:
quoted
On Tue, Sep 28, 2021 at 09:08:00PM -0700, Junio C Hamano wrote:
quoted
Jeff King [off-list ref] writes:
quoted
Side note: The pretend_object_file() approach is actually even better,
because we know the object is fake. So it does not confuse
write_object_file()'s "do we already have this object" freshening
check.
I suspect it could even be made faster than the tmp_objdir approach.
From our perspective, these objects really are tempfiles. So we could
write them as such, not worrying about things like fsyncing them,
naming them into place, etc. We could just write them out, then mmap
the results, and put the pointers into cached_objects (currently it
insists on malloc-ing a copy of the input buffer, but that seems like
an easy extension to add).
In fact, I think you could get away with just _one_ tempfile per
merge. Open up one tempfile. Write out all of the objects you want to
"store" into it in sequence, and record the lseek() offsets before and
after for each object. Then mmap the whole result, and stuff the
appropriate pointers (based on arithmetic with the offsets) into the
cached_objects list.
Cute. The remerge diff code path creates a full tree that records
the mechanical merge result. By hooking into the lowest layer of
write_object() interface, we'd serialize all objects in such a tree
in the order they are computed (bottom up from the leaf level, I'd
presume) into a single flat file ;-)
I do still like this approach, but just two possible gotchas I was
thinking of:
- This side-steps all of our usual code for getting object data into
memory. In general, I'd expect this content to not be too enormous,
but it _could_ be if there are many / large blobs in the result. So
we may end up with large maps. Probably not a big deal on modern
64-bit systems. Maybe an issue on 32-bit systems, just because of
virtual address space.
Likewise, we do support systems with NO_MMAP. They'd work here, but
it would probably mean putting all that object data into the heap. I
could live with that, given how rare such systems are these days, and
that it only matters if you're using --remerge-diff with big blobs.
- I wonder to what degree --remerge-diff benefits from omitting writes
for objects we already have. I.e., if you are writing out a whole
tree representing the conflicted state, then you don't want to write
all of the trees that aren't interesting. Hopefully the code is
already figuring out which paths the merge even touched, and ignoring
the rest. It probably benefits performance-wise from
write_object_file() deciding to skip some object writes, as well
(e.g., for resolutions which the final tree already took, as they'd
be in the merge commit). The whole pretend-we-have-this-object thing
may want to likewise make sure we don't write out objects that we
already have in the real odb.
I haven't benchmarked since my core.checkCollisions RFC patch[1]
resulted in the somewhat related loose object cache patch from you, and
not with something like the midx, but just a note that on some setups
just writing things out is faster than exhaustively checking if we
absolutely need to write things out.
I also wonder how much if anything writing out the one file v.s. lots of
loose objects is worthwhile on systems where we could write out those
loose objects on a ramdisk, which is commonly available on e.g. Linux
distros these days out of the box. If you care about performance but not
about your transitory data using a ramdisk is generally much better than
any other potential I/O optimization.
Finally, and I don't mean to throw a monkey wrench into this whole
discussion, so take this as a random musing: I wonder how much faster
this thing could be on its second run if instead of avoiding writing to
the store & cleaning up, it just wrote to the store, and then wrote
It'd be _much_ slower. My first implementation in fact did that; it
just wrote objects to the store, left them there, and didn't bother to
do any auto-gcs. It slowed down quite a bit as it ran. Adding
auto-gc's during the run were really slow too. But stepping back,
gc'ing objects that I already knew were garbage seemed like a waste;
why not just prune them pre-emptively? To do so, though, I'd have to
track all the individual objects I added to make sure I didn't prune
something else. Following that idea and a few different attempts
eventually led me to the discovery of tmp_objdir.
In case it's not clear to you why just writing all the objects to the
normal store and leaving them there slows things down so much...
Let's say 1 in 10 merges had originally needed some kind of conflict
resolution (either in the outer merge or in the inner merge for the
virtual merge bases), meaning that 9 out of 10 merges traversed by
--remerge-diff don't write any objects. Now for each merge for which
--remerge-diff does need to create conflicted blobs and new trees,
let's say it writes on average 3 blobs and 7 trees. (I don't know the
real average numbers, it could well be ~5 total, but ~10 seems a
realistic first order approximation and it makes the math easy.)
Then, if we keep all objects we write, then `git log --remerge-diff`
on a history with 100,000 merge commits, will have added 100,000 loose
objects by the time it finishes. That means that all diff and merge
operations slow down considerably as it runs due to all the extra
loose objects.
...
quoted
another object keyed on the git version and any revision paramaters
etc., and then pretty much just had to do a "git cat-file -p <that-obj>"
to present the result to the user :)
So caching the full `git log ...` output, based on a hash of the
command line flags, and then merely re-showing it later? And having
that output be invalidated as soon as any head advances? Or are you
thinking of caching the output per-commit based on a hash of the other
command line flags...potentially slowing non-log operations down with
the huge number of loose objects?
Yeah I meant caching the full 'git log' output. Anyway, I think what you
said above about number of loose objects clearly makes that a stupid
suggestion on my part.
FWIW I meant that more as a "maybe in the future we can ..." musing than
anything for this series. I.e. in general I've often wanted say the
second run of a 'git log -G<rx>"' to be faster than it is, which could
use such on-the-fly caching.
But if we had such caching then something like --remerge-diff would need
to (from my understanding of what you're saying) need both this
temporary staging area for objects and perhaps to cache the output in
the main (or some cache) store. I.e. they're orthagonal.
quoted
I suppose that would be throwing a lot more work at an eventual "git gc"
than we ever do now, so maybe it's a bit crazy, but I think it might be
an interesting direction in general to (ab)use either the primary or
some secondary store in the .git dir as a semi-permanent cache of
resolved queries from the likes of "git log".
If you do per-commit caching, and the user scrolls through enough
output (not hard to do, just searching the output for some string
often is enough), that "eventual" git-gc will be the very next git
operation. If you cache the entire output, it'll be invalidated
pretty quickly. So I don't see how this works. Or am I
misunderstanding something you're suggesting here?
With the caveat above that I think this is all a pretty stupid
suggestion on my part:
Just on the narrow aspect of how "git gc" behaves in that scenario: We'd
keep those objects around for 2 weeks by default, or whatever you have
gc.pruneExpire set to.
So such a setup would certainly cause lots of pathological issues (see
my [1] for one), but I don't think over-eager expiry of loose objects
would be one.
I'm not sure but are you referring to "invalidated pretty quickly"
because it would go over the gc.auto limit? If so that's now how it
works in this scenario, see [2]. I.e. it's moderated by the
gc.pruneExpire setting.
1. https://lore.kernel.org/git/87fu6bmr0j.fsf@evledraar.gmail.com/
2. https://lore.kernel.org/git/87inc89j38.fsf@evledraar.gmail.com/
On Thu, Sep 30, 2021 at 09:26:37PM -0700, Elijah Newren wrote:
quoted
quoted
- This side-steps all of our usual code for getting object data into
memory. In general, I'd expect this content to not be too enormous,
but it _could_ be if there are many / large blobs in the result. So
we may end up with large maps. Probably not a big deal on modern
64-bit systems. Maybe an issue on 32-bit systems, just because of
virtual address space.
Likewise, we do support systems with NO_MMAP. They'd work here, but
it would probably mean putting all that object data into the heap. I
could live with that, given how rare such systems are these days, and
that it only matters if you're using --remerge-diff with big blobs.
Um, I'm starting to get uncomfortable with this pretend_object stuff.
Part of the reason that merge-ort isn't truly "in memory" despite
attempting to do exactly that, was because for large enough repos with
enough files modified on both sides, I wasn't comfortable assuming
that all new files from three-way content merges and all new trees fit
into memory. I'm sure we'd be fine with current-day linux kernel
sized repos. No big deal. In fact, most merges probably don't add
more than a few dozen new files. But for microsoft-sized repos, and
with repos tending to grow over time, more so when the tools
themselves scale nicely (which we've all been working on enabling),
makes me worry there might be enough new objects within a single merge
(especially given the recursive inner merges) that we might need to
worry about this.
I do think we need to consider that the content might be larger than
will comfortably fit in memory. But the point of using mmap is that we
don't have to care. The OS is taking care of it for us (just like it
would in regular object files).
The question is just whether we're comfortable assuming that mmap
exists if you're working on such a large repository. I'd guess that big
repos are pretty painful with out it (and again, I'm not even clear
which systems Git runs on even lack mmap these days). So IMHO this isn't
really a blocker for going in this direction.
On the not a blocker: Even without mmap() such a user also has the out
of increasing the size of their swap/page file.
And generally I agree that it's fair for us to say that if you've got
such outsized performance needs you're going to need something more than
the lowest common denominator git can be ported to.
I also wouldn't be surprised if in that scenario we'd run faster if we
were using memory (and no mmap) than if we tried to fallback to the FS,
i.e. your suggestion of replacing N loose objects with one file with
index offsets is basically what the OS would be doing for you as it
pages out memory it can't fit in RAM to disk.
On Fri, Oct 1, 2021 at 12:41 AM Ævar Arnfjörð Bjarmason
[off-list ref] wrote:
On Thu, Sep 30 2021, Elijah Newren wrote:
quoted
On Thu, Sep 30, 2021 at 6:31 AM Ævar Arnfjörð Bjarmason
[off-list ref] wrote:
quoted
On Thu, Sep 30 2021, Jeff King wrote:
quoted
On Tue, Sep 28, 2021 at 09:08:00PM -0700, Junio C Hamano wrote:
quoted
Jeff King [off-list ref] writes:
quoted
Side note: The pretend_object_file() approach is actually even better,
because we know the object is fake. So it does not confuse
write_object_file()'s "do we already have this object" freshening
check.
I suspect it could even be made faster than the tmp_objdir approach.
From our perspective, these objects really are tempfiles. So we could
write them as such, not worrying about things like fsyncing them,
naming them into place, etc. We could just write them out, then mmap
the results, and put the pointers into cached_objects (currently it
insists on malloc-ing a copy of the input buffer, but that seems like
an easy extension to add).
In fact, I think you could get away with just _one_ tempfile per
merge. Open up one tempfile. Write out all of the objects you want to
"store" into it in sequence, and record the lseek() offsets before and
after for each object. Then mmap the whole result, and stuff the
appropriate pointers (based on arithmetic with the offsets) into the
cached_objects list.
Cute. The remerge diff code path creates a full tree that records
the mechanical merge result. By hooking into the lowest layer of
write_object() interface, we'd serialize all objects in such a tree
in the order they are computed (bottom up from the leaf level, I'd
presume) into a single flat file ;-)
I do still like this approach, but just two possible gotchas I was
thinking of:
- This side-steps all of our usual code for getting object data into
memory. In general, I'd expect this content to not be too enormous,
but it _could_ be if there are many / large blobs in the result. So
we may end up with large maps. Probably not a big deal on modern
64-bit systems. Maybe an issue on 32-bit systems, just because of
virtual address space.
Likewise, we do support systems with NO_MMAP. They'd work here, but
it would probably mean putting all that object data into the heap. I
could live with that, given how rare such systems are these days, and
that it only matters if you're using --remerge-diff with big blobs.
- I wonder to what degree --remerge-diff benefits from omitting writes
for objects we already have. I.e., if you are writing out a whole
tree representing the conflicted state, then you don't want to write
all of the trees that aren't interesting. Hopefully the code is
already figuring out which paths the merge even touched, and ignoring
the rest. It probably benefits performance-wise from
write_object_file() deciding to skip some object writes, as well
(e.g., for resolutions which the final tree already took, as they'd
be in the merge commit). The whole pretend-we-have-this-object thing
may want to likewise make sure we don't write out objects that we
already have in the real odb.
I haven't benchmarked since my core.checkCollisions RFC patch[1]
resulted in the somewhat related loose object cache patch from you, and
not with something like the midx, but just a note that on some setups
just writing things out is faster than exhaustively checking if we
absolutely need to write things out.
I also wonder how much if anything writing out the one file v.s. lots of
loose objects is worthwhile on systems where we could write out those
loose objects on a ramdisk, which is commonly available on e.g. Linux
distros these days out of the box. If you care about performance but not
about your transitory data using a ramdisk is generally much better than
any other potential I/O optimization.
Finally, and I don't mean to throw a monkey wrench into this whole
discussion, so take this as a random musing: I wonder how much faster
this thing could be on its second run if instead of avoiding writing to
the store & cleaning up, it just wrote to the store, and then wrote
It'd be _much_ slower. My first implementation in fact did that; it
just wrote objects to the store, left them there, and didn't bother to
do any auto-gcs. It slowed down quite a bit as it ran. Adding
auto-gc's during the run were really slow too. But stepping back,
gc'ing objects that I already knew were garbage seemed like a waste;
why not just prune them pre-emptively? To do so, though, I'd have to
track all the individual objects I added to make sure I didn't prune
something else. Following that idea and a few different attempts
eventually led me to the discovery of tmp_objdir.
In case it's not clear to you why just writing all the objects to the
normal store and leaving them there slows things down so much...
Let's say 1 in 10 merges had originally needed some kind of conflict
resolution (either in the outer merge or in the inner merge for the
virtual merge bases), meaning that 9 out of 10 merges traversed by
--remerge-diff don't write any objects. Now for each merge for which
--remerge-diff does need to create conflicted blobs and new trees,
let's say it writes on average 3 blobs and 7 trees. (I don't know the
real average numbers, it could well be ~5 total, but ~10 seems a
realistic first order approximation and it makes the math easy.)
Then, if we keep all objects we write, then `git log --remerge-diff`
on a history with 100,000 merge commits, will have added 100,000 loose
objects by the time it finishes. That means that all diff and merge
operations slow down considerably as it runs due to all the extra
loose objects.
...
quoted
quoted
another object keyed on the git version and any revision paramaters
etc., and then pretty much just had to do a "git cat-file -p <that-obj>"
to present the result to the user :)
So caching the full `git log ...` output, based on a hash of the
command line flags, and then merely re-showing it later? And having
that output be invalidated as soon as any head advances? Or are you
thinking of caching the output per-commit based on a hash of the other
command line flags...potentially slowing non-log operations down with
the huge number of loose objects?
Yeah I meant caching the full 'git log' output. Anyway, I think what you
said above about number of loose objects clearly makes that a stupid
suggestion on my part.
Most my ideas for merge-ort were stupid. I didn't know until I tried
them, and then I just discarded them and only showed off the good
ideas. :-)
Brainstorming new ways of doing things is a useful exercise, I think.
FWIW I meant that more as a "maybe in the future we can ..." musing than
anything for this series. I.e. in general I've often wanted say the
second run of a 'git log -G<rx>"' to be faster than it is, which could
use such on-the-fly caching.
But if we had such caching then something like --remerge-diff would need
to (from my understanding of what you're saying) need both this
temporary staging area for objects and perhaps to cache the output in
the main (or some cache) store. I.e. they're orthagonal.
quoted
quoted
I suppose that would be throwing a lot more work at an eventual "git gc"
than we ever do now, so maybe it's a bit crazy, but I think it might be
an interesting direction in general to (ab)use either the primary or
some secondary store in the .git dir as a semi-permanent cache of
resolved queries from the likes of "git log".
If you do per-commit caching, and the user scrolls through enough
output (not hard to do, just searching the output for some string
often is enough), that "eventual" git-gc will be the very next git
operation. If you cache the entire output, it'll be invalidated
pretty quickly. So I don't see how this works. Or am I
misunderstanding something you're suggesting here?
With the caveat above that I think this is all a pretty stupid
suggestion on my part:
Just on the narrow aspect of how "git gc" behaves in that scenario: We'd
keep those objects around for 2 weeks by default, or whatever you have
gc.pruneExpire set to.
So such a setup would certainly cause lots of pathological issues (see
my [1] for one), but I don't think over-eager expiry of loose objects
would be one.
I'm not sure but are you referring to "invalidated pretty quickly"
because it would go over the gc.auto limit? If so that's now how it
works in this scenario, see [2]. I.e. it's moderated by the
gc.pruneExpire setting.
By "invalidated pretty quickly" I meant that if the user ran "git log
--all" and you cached the entire output in a single cache file, then
as soon as any ref is updated, that cached output is invalid because
"git log --all" should now show different output than before.
It seems to be a case of pick your poison: either (a) cache output per
commit so that it can be re-used, and suffer from extreme numbers of
loose objects, OR (b) cache the entire output to avoid the large
number of loose objects, resulting in the cache only being useful if
the user passed the _exact_ same arguments and revisions to git-log --
and also having the cache become stale as soon as any involved ref is
updated.