fast-import deltas

fast-import deltas

[Mike Hommey]

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

Re: fast-import deltas

[Jeff King]

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

> I am currently prototyping a "native" mercurial remote handler for git,

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

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

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

Re: fast-import deltas

[Mike Hommey]

On Tue, Apr 01, 2014 at 07:45:03AM -0400, Jeff King wrote:
> On Tue, Apr 01, 2014 at 07:25:54PM +0900, Mike Hommey wrote:
> 
> > I am currently prototyping a "native" mercurial remote handler for git,
> 
> For my own curiosity, how does this differ from what is in
> contrib/remote-helpers/git-remote-hg?

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.

> > Would adding a fast-import command to handle deltas be considered useful
> > for git? If so, what kind of format would be suitable?
> 
> 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).

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

>   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).

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.

> 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.

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

Re: fast-import deltas

[Jeff King]

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

> > For my own curiosity, how does this differ from what is in
> > contrib/remote-helpers/git-remote-hg?
> 
> 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.

Ah, that makes sense. Thanks for explaining.

> >   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).
> 
> 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.

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.

> 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...

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

Re: fast-import deltas

[Mike Hommey]

On Tue, Apr 01, 2014 at 09:15:12AM -0400, Jeff King wrote:
> > 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...
> 
> 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.

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

Re: fast-import deltas

[Junio C Hamano]

Mike Hommey <mh@glandium.org> writes:

> On Tue, Apr 01, 2014 at 09:15:12AM -0400, Jeff King wrote:
>> > 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...
>> 
>> 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.
>
> 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.

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.

Re: fast-import deltas

[Jonathan Nieder]

Junio C Hamano wrote:

> 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, and feed
>    the resulting content to fast-import in full, letting fast-import
>    convert into the format Git understands.

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

[...]
> 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.

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

Re: fast-import deltas

[Mike Hommey]

On Tue, Apr 01, 2014 at 10:14:02AM -0700, Junio C Hamano wrote:
> Mike Hommey <mh@glandium.org> writes:
> 
> > On Tue, Apr 01, 2014 at 09:15:12AM -0400, Jeff King wrote:
> >> > 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...
> >> 
> >> 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.
> >
> > 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.
> 
> 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".

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

Re: fast-import deltas

[Junio C Hamano]

Mike Hommey <mh@glandium.org> writes:

> On Tue, Apr 01, 2014 at 10:14:02AM -0700, Junio C Hamano wrote:
> ...
>> 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.
>
> 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.

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.

Re: fast-import deltas

[Mike Hommey]

On Tue, Apr 01, 2014 at 03:32:49PM -0700, Junio C Hamano wrote:
> [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.

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

Re: fast-import deltas

[Max Horn]

[-- Attachment #1: Type: text/plain, Size: 5722 bytes --]


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

> On Tue, Apr 01, 2014 at 10:07:03PM +0900, Mike Hommey wrote:
> 
>>> For my own curiosity, how does this differ from what is in
>>> contrib/remote-helpers/git-remote-hg?
>> 
>> 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.
> 
> Ah, that makes sense. Thanks for explaining.


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.

[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 235 bytes --]

Re: fast-import deltas

[Mike Hommey]

On Wed, Apr 02, 2014 at 01:29:13AM +0200, Max Horn wrote:
> 
> On 01.04.2014, at 15:15, Jeff King <peff@peff.net> wrote:
> 
> > On Tue, Apr 01, 2014 at 10:07:03PM +0900, Mike Hommey wrote:
> > 
> >>> For my own curiosity, how does this differ from what is in
> >>> contrib/remote-helpers/git-remote-hg?
> >> 
> >> 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.
> > 
> > Ah, that makes sense. Thanks for explaining.
> 
> 
> 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 didn't mention it, but it definitely is a factor. As for the
performance factor, it certainly is more than a one-time overhead.

> 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.

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

Re: fast-import deltas

[Felipe Contreras]

Mike Hommey wrote:
> On Wed, Apr 02, 2014 at 01:29:13AM +0200, Max Horn wrote:
> > 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.
> 
> The way git-remote-hg works is fundamentally different to how one can
> directly get and push stuff to a remote mercurial server.

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.

-- 
Felipe Contreras