fast-import deltas

Hi,

I am currently prototyping a "native" mercurial remote handler for git, and it seems silly for git to compute deltas itself when I'm getting deltas from the mercurial remote itself, albeit in a different form.

Would adding a fast-import command to handle deltas be considered useful for git? If so, what kind of format would be suitable?

Cheers,

Mike

On Tue, Apr 01, 2014 at 07:25:54PM +0900, Mike Hommey wrote:

For my own curiosity, how does this differ from what is in contrib/remote-helpers/git-remote-hg?

It breaks fast-import's "lowest common denominator" data model that is just passing commits and their contents over the stream. But we already do that in other cases for the sake of performance. I think the important thing is that the alternate formats are optional and enabled by the caller with command-line options.

That being said, I foresee a few complications:

  1. Git needs to know the sha1 of the full object. So unless the
     generating script knows that ahead of time, git has to expand the
     delta immediately anyway (this could still be a win if we end up
     using a good delta from elsewhere rather than doing our own delta
     search, but I suspect it's not so big a win as if we can just blit
     the delta straight to disk).

  2. Git does not store on-disk deltas between objects that are not in
     the same packfile. So you'd only be able to delta against an object
     that came in the same stream (or you'd have to "fix" the packfile
     on disk by adding an extra copy of the delta base, but that
     probably eliminates any savings).

As for format, I believe that git is basically xdelta under the hood, so you'd want either that or something that can be trivially converted to it.

-Peff

On Tue, Apr 01, 2014 at 07:45:03AM -0400, Jeff King wrote:

contrib/remote-helpers/git-remote-hg does a local mercurial clone before doing the git conversion. While this is not really a problem for most mercurial projects, it tends to be slow with big ones, like the firefox source code. What I'm aiming at is something that can talk directly to a remote mercurial server.

Good point. That could quickly become a problem with long delta chains.

Arguably, this would make the most difference on initial clone of big projects, or large incremental updates (like, after a few weeks), which would use a single pack anyways.

It seems to me fast-import keeps a kind of human readable format for its protocol, i wonder if xdelta format would fit the bill. That being said, I also wonder if i shouldn't just try to write a pack on my own...

Cheers,

Mike

On Tue, Apr 01, 2014 at 10:07:03PM +0900, Mike Hommey wrote:

Ah, that makes sense. Thanks for explaining.

Yeah. The nice thing is that this can be an opportunistic optimization. If the delta base is part of the same output stream, then send the delta. Otherwise, you can always fall back to reconstructing and sending the full object yourself.

The fast-import commands are human readable, but the blob contents are included inline. I don't see how sending a binary delta is any worse than sending a literal binary blob over the stream.

-Peff

On Tue, Apr 01, 2014 at 09:15:12AM -0400, Jeff King wrote:

OTOH, the xdelta format is not exactly straightforward to produce, with the variable length encoding of integers. Not exactly hard, but when everything else in fast-import is straightforward, one has to wonder.

Mike

Mike Hommey <mh@glandium.org> writes:

Unless you already have your change in the xdelta on hand, or the format your foreign change is in gives sufficient information to produce a corresponding xdelta without looking at the content that your foreign change applies to, it is silly to try to convert your foreign change into xdelta and feed it to fast-import.

What constitutes "sufficient" information? The xdelta format is a series of instructions that lets you:

 - copy N bytes from offset in the source material to the
   destination; or
 - copy these N literal bytes to the destination.

to an existing piece of content, identified by the object name of the "source material", to produce a result of "applying delta".

As an example, think about the case where you have *,v files used by RCS (and CVS). The "foreign changes" given to you by that format is a series of instructions that roughly corresponds to an "ed" script. Insert these lines at the line number L, delete N lines from line number K, etc. In order to convert such a change into xdelta, you would need to know what these line numbers correspond to byte offset in the original file. You also may want to know what the Git object name for the original is, although in the fast-import stream you might be able to get away by using the object mark facility.

Assuming that you do have and are willing to read the original file, you have three possible (and one impractical) approaches:

 - Apply the foreign changes to the original file yourself (as that
   is the foreign system you are interested in, you know how to do
   that much better than Git does), and produce xdelta between the
   original and the result using only the original and the result.

 - Apply the foreign changes to the original file yourself, and feed
   the resulting content to fast-import in full, letting fast-import
   convert into the format Git understands.

 - Interpret the foreign changes, using the original file as a
   reference, to convert it into xdelta.

 - Teach fast-import how to interpret various formats that are used
   to express foreign changes, and feed that.

In the first approach, this "given the original and the result, produce xdelta between them" can be reused by other people's system. You may be able to borrow diff-delta.c from us under our licensing terms.

The second is the most straightforward; eventual deltification will happen when the resulting repository is repacked and uses the same code from diff-delta.c.

The third would be "*,v expresses the source location and length in terms of lines, so look at the original to convert these into byte offset and byte length xdelta wants", which I would think is silly.

And the last one is a maintenance nightmare I do not think we would want to touch with a ten-foot pole.

In short, the most practical solution would be to reconstitute a full object and feed that to fast-import, unless you already have xdelta or you can turn your foreign change into xdelta without ever looking at the original.

Junio C Hamano wrote:

[...]

This (when importing from Subversion) was the motivation for introducing fast-import's cat-blob command, for what it's worth.

[...]

If your delta format happens to be similar enough to xdelta, then streaming in deltas in xdelta format does sound like a neat trick.

Maybe it would be useful to provide a micro-library that creates and validates xdelta opcodes for fast-import frontends to use.

Jonathan

On Tue, Apr 01, 2014 at 10:14:02AM -0700, Junio C Hamano wrote:

The patch format I'm getting from mercurial boils down to:
  - replace N bytes from offset in the source material with the given
    M bytes.
Which can easily be converted to xdelta without looking at the original.

Mike

Mike Hommey <mh@glandium.org> writes:

If that is the case, and if you can identify the original in a way fast-import can understand, it might be interesting [*1*] to add support for accepting <base object, xdelta> pair in place of blob data, as Jonathan already hinted earlier.

It would not be sufficient for the receiving fast-import to store the delta data to its output---it needs to make sure that the base object is stored in the same output file as well, but that should not be too complicated.

[Footnote]

*1* I am still not sure how useful the feature would be outside slurping from Hg and Git---for obvious reasons, though. As long as the change is to a cleanly isolated codepath, it would be OK, I guess.

On Tue, Apr 01, 2014 at 03:32:49PM -0700, Junio C Hamano wrote:

That's why I started the thread by asking if there would be some interest for this feature. I'm not even sure it would be entirely beneficial to my usecase, just a hunch.

Mike

On 01.04.2014, at 15:15, Jeff King <peff@peff.net> wrote:

Hm, myself, I am not quite convinced. Yes, there is an overhead, but it is one-time (well, the space overhead is not, but Mike only mentioned time, not space). I wonder if it is really worth the effort to start yet another project on this... Moreover, I don't see a fundamental reason why one could not modify git-remote-hg to work this way. At least optionally - myself, I would strongly prefer the current way, as translating between git and hg 100% round trip clean is provably impossible [1].

Thing is, there are by now more than half a dozen projects of this kind. In my impression, all do the low hanging fruit, some go slightly beyond that, but *none* solves all the tough parts and itty-gritty details...

Just to mention a few of the problems that are usually ignored, even though they have real world impact:

- the concept of Mercurial branches has no counterpart in git, making all kinds of translations hard. As a consequence, many translators ignore hg branches completely (e.g. hg-git -- at least it used to do that, not sure whether that changed) or handle them only partially (e.g. contrib/remote-helpers/git-remote-hg: It does not deal with multiple heads or with closed branches)
(this can cause sever issues with git-remote-hg, by the way, with dangling refs, which, when pruned by an auto-gc, can wipe your fast-import marks file, causing major pain...)

- in the other direction, git branches most closely correspond to hg bookmarks. But what if a hg repository has both a branch "foo" and a bookmark "foo"? git-remote-hg partially deals with that (by mapping the hg bookmark "foo" to the git branch "foo", and mapping the hg branch "foo" to the git branch "branches/foo"), but this still has issues (besides being annoying for users, it clearly still not avoids ref name conflicts)

- git and hg also allow different characters sets in branch and bookmark names

- in hg you can simultaneously have things called "foo" and "foo/bar". In git, you can't.

There is plenty more. Of course, some of this might just be impossible [1] to handle nicely. But I find it kind of sad that everybody seems to prefer to start yet another solution, then leave it as 80%, instead of trying to improve upon existing work :-(.

By the way, to get back to the speed bottleneck: We found that by far the slowest part in importing large repositories like the Mozilla one was not the initial cloning of the hg repository (althoug that could sometimes take ages) but rather an unfortunate mismatch between the hg and git storage approach. When creating a fast-import stream, the normal way to go about that is to import things commit by commit. But if you do that, then extracting file data from Mercurial and its revlog data format easily can degenerate into the worst case quadratic runtime :-/. Now, if one know that one is going to import the whole repository anyway, one could do better by first exporting all file revisions, generating many blobs and their marks, and keeping these in memory, *then* exporting the commits, reverting to these blob marks. 

However, this stops being a great idea once you are working in incremental mode. That said, it certainly would make sense to investigate this possibility (regardless of whether one uses a local hg clone or directly talks to the remote repository); at least in theory, even if one only uses this approach during the initial import, it should be a strict improvement over the current situation.

In closing, I should mention that the problems caused by translating between hg and git concepts are by far not the only ones; the fast-import interface itself still has limitations that make some things annoying. E.g. when a remote is renamed, the remote handler does not know that, which can lead to awkward situations that right now may require some trickery to resolve correctly, if it is possible at all. Or if a user manually removed a commit that a remote-helper previously referenced in a marks file, and that remote helper than uses that marks file, fast-import just dies, complaining about the invalid mark. As a result, every proper remote helper basically would need to fully parse and verify those marks files, detect "broken" marks, and deal with that -- there is no way to benefit from the existing mark verification code in fast-import right now.

Please don't get me wrong. I don't want to whine, and I hope I can contribute to solving some of these issues at some point (though lack of time is a nasty issue). In the meantime, I'd love if other people were interested in improving one of the existing solutions to the problem (such as git-remote-hg, gitifyhg or hg-git), instead of creating yet another half-way solution... :-)

Cheers, Max

[1] That is, unless you are willing to use a custom server, such as Kiln Harmony <http://blog.fogcreek.com/kiln-harmony-internals-the-basics/>. But that is cheating, as this is not a real round-trip conversion; rather, you keep a git and a hg repository in perfect sync all the time and present them as a single entity to the outside world.

On Wed, Apr 02, 2014 at 01:29:13AM +0200, Max Horn wrote:

I didn't mention it, but it definitely is a factor. As for the performance factor, it certainly is more than a one-time overhead.

The way git-remote-hg works is fundamentally different to how one can directly get and push stuff to a remote mercurial server. As such, there is not much value in the current git-remote-hg code for that purpose. Also, I'm currently prototyping something to see whether what I think should work really works. Starting from the current git-remote-hg code would add useless constraints to the prototype.

Mike

Mike Hommey wrote:

That is why you would modify it; so it does what you want, and instead of using remote-helper's import/export, it would use fetch/push.

Either way, I say you should hack Git and do as many changes as you want, and once you have some numbers, it would be clearer what approach should be the ideal one, how much is the benefit, and then we could discuss if it's worth the modifications in Git needed.