Today's invention: pvecs

[Matt Mackall]

On Sun, 2012-03-11 at 12:42 +0100, Antoine Pitrou wrote:
> On Sat, 10 Mar 2012 18:56:17 -0600
> Matt Mackall <mpm at selenic.com> wrote:
> > +- at large distances (a few thousand changesets), things break down
> 
> Wouldn't that be better if you chose a slightly larger depth?

Yes, but that trades off against the ability to distinguish local
nonlinear relationships (and bytes are convenient to work with). But it
is worth noting that this is a tunable. Making the whole thing a single
bucket gives you just distance from root (with WAY too much resolution).
Making every bucket one bit wide gives you a large radius where you can
distinguish changeset histories well, but you can't really measure
larger distances well.

In fact, there are a bunch of hybrids here that are interesting. I'm
tinkering with a scheme that uses ~24 bits for depth/clock and the
remaining bits for local Hamming distance measurement. How this works
with merges and detecting parallel branches still leaves a bunch of
questions though.

I'm not sure what scheme we'll end up with, but I think the interesting
point here is that it is indeed possible to build a useful DAG
fingerprint.

> > +                    # mix in base node for other roots
> > +                    pvc[n] = r[0].node() + c.node() + "0" * 16
> 
> Why did you choose "0" instead of e.g. "\0" ?

It's easier to find wrap-around bugs if you start in the middle
somewhere.

-- 
Mathematics is the supreme nostalgia of our time.