Re: [ANNOUNCE] Example Cogito Addon - cogito-bundle

From: Aaron Bentley <aaron.bentley@utoronto.ca>
Date: Oct 20, 2006, 20:29 UTC
Message-ID: <4539318D.9040004@utoronto.ca>
In-Reply-To: <Pine.LNX.4.64.0610201231570.3962@g5.osdl.org>

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Linus Torvalds wrote:

Show 21 quoted lines

> 
> On Fri, 20 Oct 2006, Aaron Bentley wrote:
> 
>>Linus Torvalds wrote:
>>
>>>Git goes one step further: it _really_ doesn't matter about how you got to 
>>>a certain state. Absolutely _none_ of what the commits in between the 
>>>final stages and the common ancestor matter in the least. The only thing 
>>>that matters is what the states at the end-point are.
>>
>>That's interesting, because I've always thought one of the strengths of
>>file-ids was that you only had to worry about end-points, not how you
>>got there.
>>
>>How do you handle renames without looking at the history?
> 
> 
> You first handle all the non-renames that just merge on their own.
> If you were to use one hundredth of a second per file regardless of file, 
> a stupid per-file merge would take 210 seconds, which is just 
> unacceptable. So you really don't want to do that.

Agreed. We start by comparing BASE and OTHER, so all those comparisons are in-memory operations that don't hit disk. Only for files where BASE and OTHER differ do we even examine the THIS version.

We can do a do-nothing kernel merge in < 20 seconds, and that's comparing every single file in the tree. In Python. I was aiming for less than 10 seconds, but didn't quite hit it.

> So recursive basically generates the matrix of similarity for the 
> new/deleted files, and tries to match them up, and there you have your 
> renames - without ever looking at the history of how you ended up where 
> you are.

So in the simple case, you compare unmatched THIS, OTHER and BASE files to find the renames?

Show 6 quoted lines

>   I don't know if people appreciate how good it is to do a merge of two 
>   21000-file branches in less than a second. It didn't have any renames, 
>   and it only had a single well-defined common parent, but not only is 
>   that the common case, being that fast for the simple case is what 
>   _allows_ you to do well on the complex cases too, because it's what gets 
>   rid of all the files you should _not_ worry about ]

Well, I certainly appreciate that. I've never worried about the speed of text merge algorithms, because you rarely merge very many files. The key is making the tree merge fast.

Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFFOTGN0F+nu1YWqI0RAii+AJ0eduC3bYya5Ao8vm1EpBb38tJP4ACeJRYe 9/D+ahDRJa87NTryc7j3C+U= =plWA -----END PGP SIGNATURE-----