Mercurial 0.3 vs git benchmarks

Mercurial 0.3 vs git benchmarks

[Matt Mackall]

This is to announce an updated version of Mercurial. Mercurial is a
scalable, fast, distributed SCM that works in a model similar to BK
and Monotone. It has functional clone/branch and pull/merge support
and a working first pass implementation of network pull. It's also
extremely small and hackable: it's about 1000 lines of code.

 http://selenic.com/mercurial/

Here are the results of checking in the first 12 releases of Linux 2.6
into empty repositories for Mercurial v0.3 (hg) and git-pasky-0.7.
This is on my 512M Pentium M laptop. Times are in seconds.

                 user         system       real        du -sh
ver    files   hg    git    hg    git    hg    git    hg   git

2.6.0  15007 19.949 35.526 3.171 2.264 25.138 87.994 145M   89M
2.6.1    998  5.906  4.018 0.573 0.464 10.267  5.937 146M   99M
2.6.2   2370  9.696 13.051 0.752 0.652 12.970 15.167 150M  117M
2.6.3   1906 10.528 11.509 0.816 0.639 18.406 14.318 152M  135M
2.6.4   3185 11.140  7.380 0.997 0.731 15.265 12.412 156M  158M
2.6.5   2261 10.961  6.939 0.843 0.640 20.564  8.522 158M  177M
2.6.6   2642 11.803 10.043 0.870 0.678 22.360 11.515 162M  197M
2.6.7   3772 18.411 15.243 1.189 0.915 32.397 21.498 165M  227M
2.6.8   4604 20.922 16.054 1.406 1.041 39.622 25.056 172M  262M
2.6.9   4712 19.306 12.145 1.421 1.102 35.663 24.958 179M  297M
2.6.10  5384 23.022 18.154 1.393 1.182 40.947 32.085 186M  338M
2.6.11  5662 27.211 19.138 1.791 1.253 42.605 31.902 193M  379M

tar of .hg/   108175360
tar of .git/  209385920

Full-tree change status (no changes):
hg:  real 0.799s  user 0.607s  sys 0.167s
git: real 0.124s  user 0.051s  sys 0.051s

Check-out time (2.6.0):
hg:  real 34.084s  user 4.069s  sys 2.024s
git: real 30.487s  user 2.393s  sys 1.007s

Full-tree working dir diff (2.6.0 base with 2.6.1 in working dir):
hg:  real 4.920s  user 4.629s  sys 0.260s
git: real 3.531s  user 1.869s  sys 0.862s
(this needed an update-cache --refresh on top of git commit, which
took another: real 2m52.764s  user 2.833s  sys 1.008s)

Merge from 2.6.0 to 2.6.1:
hg:  real 15.507s  user 6.175s  sys 0.442s
git: haven't quite figured this one out yet

Some notes:

- hg has a separate index file for each file checked in, which is why
  the initial check-in is larger
- this also means it touches twice as many files, typically
- neither hg nor git quite fit in cache on my 512M laptop (nor does a
  kernel compile), but the extra indexing makes hg's wall times a bit longer
- hg does a form of delta compression, so each checkin requires
  retrieving a previous version, checking its hash, doing a diff,
  compressing it, and checking in the result
- hg is written in pure Python

Despite the above, it compares pretty well to git in speed and is
quite a bit better in terms of storage space. By reducing the zlib
compression level, it could probably win across the board.

The size numbers will get dramatically more unbalanced with more
history - a conversion of the history in BK to git is expected to take
over 3G, which Mercurial may actually take less space due to storing
compressed binary forward-only deltas.

While disk may be cheap, network bandwidth is not. Given that the
common case usage of git will be to do network pulls, it will find
most of its speed wasted on waiting for the network. Mercurial will
almost certainly win here for typical developer usage as it can do
efficient delta communication (though it currently doesn't attempt any
pipelining so suffers a bit in round trips).

More discussion about Mercurial's design can be found here:

 http://selenic.com/mercurial/notes.txt

-- 
Mathematics is the supreme nostalgia of our time.

Re: Mercurial 0.3 vs git benchmarks

[Daniel Phillips]

On Monday 25 April 2005 20:41, Matt Mackall wrote:
> Despite the above, it compares pretty well to git in speed and is
> quite a bit better in terms of storage space. By reducing the zlib
> compression level, it could probably win across the board.

Hi Matt,

Congratulations on an impressive demo!  How about actually checking the 
compression vs wall clock theory?  And I probably don't have to mention 
psyco...

Regards,

Daniel

Re: Mercurial 0.3 vs git benchmarks

[Linus Torvalds]

On Mon, 25 Apr 2005, Matt Mackall wrote:
>
> Here are the results of checking in the first 12 releases of Linux 2.6
> into empty repositories for Mercurial v0.3 (hg) and git-pasky-0.7.
> This is on my 512M Pentium M laptop. Times are in seconds.
> 
>                  user         system       real        du -sh
> ver    files   hg    git    hg    git    hg    git    hg   git
> 
> 2.6.0  15007 19.949 35.526 3.171 2.264 25.138 87.994 145M   89M
> 2.6.1    998  5.906  4.018 0.573 0.464 10.267  5.937 146M   99M
> 2.6.2   2370  9.696 13.051 0.752 0.652 12.970 15.167 150M  117M
> 2.6.3   1906 10.528 11.509 0.816 0.639 18.406 14.318 152M  135M
> 2.6.4   3185 11.140  7.380 0.997 0.731 15.265 12.412 156M  158M
> 2.6.5   2261 10.961  6.939 0.843 0.640 20.564  8.522 158M  177M
> 2.6.6   2642 11.803 10.043 0.870 0.678 22.360 11.515 162M  197M
> 2.6.7   3772 18.411 15.243 1.189 0.915 32.397 21.498 165M  227M
> 2.6.8   4604 20.922 16.054 1.406 1.041 39.622 25.056 172M  262M
> 2.6.9   4712 19.306 12.145 1.421 1.102 35.663 24.958 179M  297M
> 2.6.10  5384 23.022 18.154 1.393 1.182 40.947 32.085 186M  338M
> 2.6.11  5662 27.211 19.138 1.791 1.253 42.605 31.902 193M  379M

That time in checking things in is worrisome.

"git" is basically linear in the size of the patch, which is what I want,
since most patches I work with are a couple of files at most. The patches
you are checking in are huge - I never actually work with a change that is
as big as a whole release. I work with changes that are five files or
something.

"hg" seems to basically slow down the more patches you have applied. It's 
hard to tell from the limited test set, but look at "user" time. It seems 
to increase from 6 seconds to 27 seconds.

To make an interesting benchmark, try applying the first 200 patches in 
the current git kernel archive. Can you do them three per second? THAT is 
the thing you should optimize for, not checking in huge changes.

If you're checking in a change to 1000+ files, you're doing something
wrong.

> Full-tree working dir diff (2.6.0 base with 2.6.1 in working dir):
> hg:  real 4.920s  user 4.629s  sys 0.260s
> git: real 3.531s  user 1.869s  sys 0.862s
> (this needed an update-cache --refresh on top of git commit, which
> took another: real 2m52.764s  user 2.833s  sys 1.008s)

You're doing something wrong with git here. Why would you need to update 
your cache?

			Linus

Re: Mercurial 0.3 vs git benchmarks

[Mike Taht]

Linus Torvalds wrote:
 > On Mon, 25 Apr 2005, Matt Mackall wrote:
 >
 >>Here are the results of checking in the first 12 releases of Linux 2.6
 >>into empty repositories for Mercurial v0.3 (hg) and git-pasky-0.7.
 >>This is on my 512M Pentium M laptop. Times are in seconds.

One difference is probably - mercurial appears to be using zlib's 
*default* compression of 6....

using zlib compression of 9 really impacts git...

as per http://www.gelato.unsw.edu.au/archives/git/0504/1988.html

 >On a 700MHz p3, UDMA33, freebsd 5.3, ffs (soft updates) I get:

 >compressor | levels (size, time to compress, time to uncompress)
 >-----------+-------------------------------------------------------------------
 >gzip       | 9 (28M, 1:19, 30), 6 (28M, 31.7, 30), 3 (30M, 26.1,28.7)
 >           | 1 (31M, 23.6, 29.8)
 >bzip2      | 9 (27M, 2:14, 37.4) 6 (27M, 2:11, 38.8) 3 (27M, 2:10,38.3)
 >lzop       | 9 (32M, 2:15, 35.4) 7 (32M, 57.9, 40.3) 3 (39M, 36.0,44.4)

as per setting GIT_COMPRESSION 3 rather than Z_BEST_COMPRESSION

http://www.gelato.unsw.edu.au/archives/git/0504/1478.html


>>
>>                 user         system       real        du -sh
>>ver    files   hg    git    hg    git    hg    git    hg   git
>>
>>2.6.0  15007 19.949 35.526 3.171 2.264 25.138 87.994 145M   89M
>>2.6.1    998  5.906  4.018 0.573 0.464 10.267  5.937 146M   99M
>>2.6.2   2370  9.696 13.051 0.752 0.652 12.970 15.167 150M  117M
>>2.6.3   1906 10.528 11.509 0.816 0.639 18.406 14.318 152M  135M
>>2.6.4   3185 11.140  7.380 0.997 0.731 15.265 12.412 156M  158M
>>2.6.5   2261 10.961  6.939 0.843 0.640 20.564  8.522 158M  177M
>>2.6.6   2642 11.803 10.043 0.870 0.678 22.360 11.515 162M  197M
>>2.6.7   3772 18.411 15.243 1.189 0.915 32.397 21.498 165M  227M
>>2.6.8   4604 20.922 16.054 1.406 1.041 39.622 25.056 172M  262M
>>2.6.9   4712 19.306 12.145 1.421 1.102 35.663 24.958 179M  297M
>>2.6.10  5384 23.022 18.154 1.393 1.182 40.947 32.085 186M  338M
>>2.6.11  5662 27.211 19.138 1.791 1.253 42.605 31.902 193M  379M


-- 

Mike Taht


   "Imagination is more important than knowledge.
	-- Albert Einstein"

Re: Mercurial 0.3 vs git benchmarks

[Linus Torvalds]

On Mon, 25 Apr 2005, Mike Taht wrote:
> 
> One difference is probably - mercurial appears to be using zlib's 
> *default* compression of 6....
> 
> using zlib compression of 9 really impacts git...

I agree that it will hurt for big changes, but since I really do believe 
that most changes are just a couple of files, I don't believe it matters 
for those. 

I forget what the exact numbers were, but I did some timings on plain
"gzip", and it basically said that doing gzip on a medium-sized file was
not that different for -6 and -9. Why? Because most of the overhead was
elsewhere ;)

Oh, well, I just re-created some numbers. This wasn't exactly what I did 
last time I tested it, but it's conceptually the same thing:

	torvalds@ppc970:~> time gzip -9 < v2.6/linux/kernel/sched.c > /dev/null 
	real    0m0.018s
	user    0m0.018s
	sys     0m0.000s

	torvalds@ppc970:~> time gzip -6 < v2.6/linux/kernel/sched.c > /dev/null 
	real    0m0.015s
	user    0m0.013s
	sys     0m0.001s

ie there's a 0.003 second difference, which is certainly noticeable, and
would be hugely noticeable if you did a lot of these. But in my world-view
(which is what git is optimized for), the common case is that you usually
end up compressing maybe five-ten files, so the _compression_ overhead is
not that huge compared to all the other stuff.

But yes, testing git on big changes will test exactly the things that git
isn't optimized for. I think git will normally hold up pretty well (ie it
will still beat anything that isn't designed for speed, and will be
comparable to things that _are_), but it's not what I'm interested in
optimizing for.

That said - these days we can trivially change over to a "zlib -6" 
compression, and nothing should ever notice. So if somebody wants to 
test it, it should be fairly easy to just compare side-by-side: the 
results should be identical.

The easiest test-case is Andrew's 198-patch patch-bomb on linux-kernel a 
few weeks ago: they all apply cleanly to 2.6.12-rc2 (in order), and you 
can use my "dotest" script to automate the test..

			Linus

Re: Mercurial 0.3 vs git benchmarks

[Linus Torvalds]

On Mon, 25 Apr 2005, Linus Torvalds wrote:
> 
> The easiest test-case is Andrew's 198-patch patch-bomb on linux-kernel a 
> few weeks ago: they all apply cleanly to 2.6.12-rc2 (in order), and you 
> can use my "dotest" script to automate the test..

Oh, well. That was so trivial that I just did it:

With Z_BEST_COMPRESSION:

	torvalds@ppc970:~/git-speed-1> ./script 
	Removing old tree
	Creating new tree
	Initializing db
	defaulting to local storage area
	Doing sync
	Initial add
	
	real    0m37.526s
	user    0m33.317s
	sys     0m3.816s
	Initial commit
	Committing initial tree 0bba044c4ce775e45a88a51686b5d9f90697ea9d
	
	real    0m0.329s
	user    0m0.152s
	sys     0m0.176s
	Patchbomb
	
	real    0m50.408s
	user    0m18.933s
	sys     0m25.432s

With Z_DEFAULT_COMPRESSION:

	torvalds@ppc970:~/git-speed-1> ./script 
	Removing old tree
	Creating new tree
	Initializing db
	defaulting to local storage area
	Doing sync
	Initial add
	
	real    0m19.755s
	user    0m15.719s
	sys     0m3.756s
	Initial commit
	Committing initial tree 0bba044c4ce775e45a88a51686b5d9f90697ea9d
	
	real    0m0.337s
	user    0m0.139s
	sys     0m0.197s
	Patchbomb
	
	real    0m50.465s
	user    0m18.304s
	sys     0m25.567s

ie the "initial add" is almost twice as fast (because it spends most of
the time compressing _all_ the files), but the difference in applying 198
patches is not noticeable at all (because the costs are all elsewhere).

That's 198 patches in less than a minute even with the highest
compression. That rocks.

And don't try to make me explain why the patchbomb has any IO time at all,
it should all have fit in the cache, but I think the writeback logic
kicked in. Anyway, I tried it several times, and the real-time ends up 
fluctuating between 50-56 seconds, but the user/sys times are very stable, 
and end up being pretty much the same regardless of compression level.

Here's the script, in case anybody cares:

	#!/bin/sh
	echo Removing old tree
	rm -rf linux-2.6.12-rc2
	echo Creating new tree
	zcat < ~/v2.6/linux-2.6.12-rc2.tar.gz | tar xvf - > log
	echo Initializing db
	( cd linux-2.6.12-rc2 ; init-db )
	echo Doing sync
	sync
	echo Initial add
	time sh -c 'cd linux-2.6.12-rc2 && cat ../l | xargs update-cache --add --' >> log
	echo Initial commit
	time sh -c 'cd linux-2.6.12-rc2 && echo Initial commit | commit-tree 
	$(write-tree) > .git/HEAD' >> log
	echo Patchbomb
	time sh -c 'cd linux-2.6.12-rc2 ; dotest ~/andrews-first-patchbomb' >> log

and since the timing results were pretty much what I expected, I don't 
think this changes _my_ opinion on anything. Yes, you can speed up commits 
with Z_DEFAULT_COMPRESSION, but it's _not_ that big of a deal for my kind 
of model where you commit often, and commits are small.

It all boils down to:
 - huge commits are slowed down by compression overhead
 - I don't think huge commits really matter

I mean, if it took 2 _hours_ to do the initial commit, I'd think it 
matters. But when we're talking about less than a minute to create the 
initial commit of a whole kernel archive, does it really make any 
difference?

After all, it's something you do _once_, and never again (unless you
script it to do performance testing ;)

Anyway guys, feel free to test this on other machines. I bet there are
lots of subtle performance differences between different filesystems and
CPU architectures.. But the only hard numbers I have show that -9 isn't 
that expensive.

			Linus

Re: Mercurial 0.3 vs git benchmarks

[Chris Mason]

On Tuesday 26 April 2005 00:00, Linus Torvalds wrote:
> On Mon, 25 Apr 2005, Linus Torvalds wrote:
> > The easiest test-case is Andrew's 198-patch patch-bomb on linux-kernel a
> > few weeks ago: they all apply cleanly to 2.6.12-rc2 (in order), and you
> > can use my "dotest" script to automate the test..
>
> Oh, well. That was so trivial that I just did it:
[ ... ]

> ie the "initial add" is almost twice as fast (because it spends most of
> the time compressing _all_ the files), but the difference in applying 198
> patches is not noticeable at all (because the costs are all elsewhere).
>
> That's 198 patches in less than a minute even with the highest
> compression. That rocks.

This agrees with my tests here, the time to apply patches is somewhat disk 
bound, even for the small 100 or 200 patch series.  The io should be coming 
from data=ordered, since the commits are still every 5 seconds or so.

-chris

Re: Mercurial 0.3 vs git benchmarks

[Magnus Damm]

On 4/26/05, Chris Mason <mason@suse.com> wrote:
> This agrees with my tests here, the time to apply patches is somewhat disk
> bound, even for the small 100 or 200 patch series.  The io should be coming
> from data=ordered, since the commits are still every 5 seconds or so.

Yes, as long as you apply the patches to disk that is. I've hacked up
a small backend tool that applies patches to files kept in memory and
uses a modifed rabin-karp search to match hunks. So you basically read
once and write once per file instead of moving data around for each
applied patch. But it needs two passes.

And no, the source code for the entire Linux kernel is not kept in
memory - you need a smart frontend to manage the file cache. Drop me a
line if you are interested.

/ magnus

Re: Mercurial 0.3 vs git benchmarks

[Chris Mason]

On Tuesday 26 April 2005 11:09, Magnus Damm wrote:
> On 4/26/05, Chris Mason <mason@suse.com> wrote:
> > This agrees with my tests here, the time to apply patches is somewhat
> > disk bound, even for the small 100 or 200 patch series.  The io should be
> > coming from data=ordered, since the commits are still every 5 seconds or
> > so.
>
> Yes, as long as you apply the patches to disk that is. I've hacked up
> a small backend tool that applies patches to files kept in memory and
> uses a modifed rabin-karp search to match hunks. So you basically read
> once and write once per file instead of moving data around for each
> applied patch. But it needs two passes.
>
> And no, the source code for the entire Linux kernel is not kept in
> memory - you need a smart frontend to manage the file cache. Drop me a
> line if you are interested.

Sorry, you've lost me.  Right now the cycle goes like this:

1) patch reads patch file, reads source file, writes source file
2) update-cache reads source file, writes git file

Which of those writes are you avoiding?  We have a smart way to manage the 
cache already for the source files...the vm does pretty well.  There's 
nothing to manage for the git files.  For the apply a bunch of patches 
workload, they are write once, read never (except for the index).

-chris

Re: Mercurial 0.3 vs git benchmarks

[Magnus Damm]

On 4/26/05, Chris Mason <mason@suse.com> wrote:
> On Tuesday 26 April 2005 11:09, Magnus Damm wrote:
> > On 4/26/05, Chris Mason <mason@suse.com> wrote:
> > > This agrees with my tests here, the time to apply patches is somewhat
> > > disk bound, even for the small 100 or 200 patch series.  The io should be
> > > coming from data=ordered, since the commits are still every 5 seconds or
> > > so.
> >
> > Yes, as long as you apply the patches to disk that is. I've hacked up
> > a small backend tool that applies patches to files kept in memory and
> > uses a modifed rabin-karp search to match hunks. So you basically read
> > once and write once per file instead of moving data around for each
> > applied patch. But it needs two passes.
> >
> > And no, the source code for the entire Linux kernel is not kept in
> > memory - you need a smart frontend to manage the file cache. Drop me a
> > line if you are interested.
> 
> Sorry, you've lost me.  Right now the cycle goes like this:

Ehrm, maybe I'm way off. =)

> 1) patch reads patch file, reads source file, writes source file
> 2) update-cache reads source file, writes git file

Ok.

> Which of those writes are you avoiding?  We have a smart way to manage the
> cache already for the source files...the vm does pretty well.  There's
> nothing to manage for the git files.  For the apply a bunch of patches
> workload, they are write once, read never (except for the index).

Well, maybe I misunderstood everything, but I thought you were
applying a lot of patches and complained that it took a lot of time
due to the data order.

When I applied a lot of patches to the kernel recently the cpu load
dropped to zero after a while and the HD worked hard a sec or two and
then things came back again. My primitive guess is that it was because
the ext3 journal became full. To workaround this fact I started
hacking on this in-memory patcher.

In the cycle above, I'm trying to speed up step 1:
If the patch modifies each source file multiple times (either using
multiple hunks or multiple ---/+++) then the lines below the hunk in
the source file will be moved multiple times. And if the source file
is written to disk after each hunk or ---/+++ is applied then this
will generate a lot of writes that can be avoided if the entire patch
procedure is broken down into a first pass that analyzes the patches
and a second pass that applies the patches and keeps source files in
memory.

But my rather trivial observation above is of course only suitable if
you have a lot of patches that should be applied and you are only
interested in the final version of the patched source files. If you
apply one patch at a time and import each source file as a new
revision then my little hack is probably not for you.

/ magnus

Re: Mercurial 0.3 vs git benchmarks

[Chris Mason]

On Tuesday 26 April 2005 12:23, Magnus Damm wrote:

> Well, maybe I misunderstood everything, but I thought you were
> applying a lot of patches and complained that it took a lot of time
> due to the data order.
>
> When I applied a lot of patches to the kernel recently the cpu load
> dropped to zero after a while and the HD worked hard a sec or two and
> then things came back again. My primitive guess is that it was because
> the ext3 journal became full. To workaround this fact I started
> hacking on this in-memory patcher.

It looks like you'll only see the commits on ext3 when the log fills, and on 
reiser3 you'll see it every 5 seconds or when the log fills.  With the 
default mount options, both ext3 and reiser will flush the data blocks at the 
same time they are writing the metadata.

The easiest way to get around this is to mount -o data=writeback on 
ext3/reiser, but you'll still have to wait for the data blocks eventually.  

-chris

Re: Mercurial 0.3 vs git benchmarks

[Andrew Morton]

Magnus Damm <magnus.damm@gmail.com> wrote:
>
> My primitive guess is that it was because
>  the ext3 journal became full.

The default ext3 journal size is inappropriately small, btw.  Normally you
should manually make it 128M or so, rather than 32M.  Unless you have a
small amount of memory and/or a large number of filesystems, in which case
there might be problems with pinned memory.

Mounting as ext2 is a useful technique for determining whether the fs is
getting in the way.

Re: Mercurial 0.3 vs git benchmarks

[Linus Torvalds]

On Tue, 26 Apr 2005, Andrew Morton wrote:
> 
> Mounting as ext2 is a useful technique for determining whether the fs is
> getting in the way.

What's the preferred way to try to convert a root filesystem to a bigger
journal? Forcing "rootfstype=ext2" at boot and boot into single-user, and
then the appropriate magic tune2fs? Or what?

		Linus

Re: Mercurial 0.3 vs git benchmarks

[H. Peter Anvin]

Linus Torvalds wrote:
> 
> On Tue, 26 Apr 2005, Andrew Morton wrote:
> 
>>Mounting as ext2 is a useful technique for determining whether the fs is
>>getting in the way.
> 
> 
> What's the preferred way to try to convert a root filesystem to a bigger
> journal? Forcing "rootfstype=ext2" at boot and boot into single-user, and
> then the appropriate magic tune2fs? Or what?
> 

Boot single-user, "remount -o ro,remount /", "tune2fs -J size=xxxM" and 
reboot.

	-hpa

Re: Mercurial 0.3 vs git benchmarks

[Andrew Morton]

Linus Torvalds <torvalds@osdl.org> wrote:
>
> 
> 
> On Tue, 26 Apr 2005, Andrew Morton wrote:
> > 
> > Mounting as ext2 is a useful technique for determining whether the fs is
> > getting in the way.
> 
> What's the preferred way to try to convert a root filesystem to a bigger
> journal? Forcing "rootfstype=ext2" at boot and boot into single-user, and
> then the appropriate magic tune2fs? Or what?
> 

Gee, it's been ages.  umm,

- umount the fs
- tune2fs -O ^has_journal /dev/whatever
- fsck -fy                              (to clean up the now-orphaned journal inode)
- tune2fs -j -J size=nblocks    (normally 4k blocks)
- mount the fs

Re: Mercurial 0.3 vs git benchmarks

[H. Peter Anvin]

Andrew Morton wrote:
> Linus Torvalds <torvalds@osdl.org> wrote:
> 
>>
>>
>>On Tue, 26 Apr 2005, Andrew Morton wrote:
>>
>>>Mounting as ext2 is a useful technique for determining whether the fs is
>>>getting in the way.
>>
>>What's the preferred way to try to convert a root filesystem to a bigger
>>journal? Forcing "rootfstype=ext2" at boot and boot into single-user, and
>>then the appropriate magic tune2fs? Or what?
>>
> 
> 
> Gee, it's been ages.  umm,
> 
> - umount the fs
> - tune2fs -O ^has_journal /dev/whatever
> - fsck -fy                              (to clean up the now-orphaned journal inode)
> - tune2fs -j -J size=nblocks    (normally 4k blocks)
> - mount the fs
> 

I think this is overkill, but should of course be safe.

While you're doing this anyway, you might want to make sure you enable 
-O +dir_index and run fsck -D.

	-hpa

Re: Mercurial 0.3 vs git benchmarks

[Florian Weimer]

* H. Peter Anvin:

> While you're doing this anyway, you might want to make sure you enable 
> -O +dir_index and run fsck -D.

Directory hashing has a negative impact on some applications (notably
tar and unpatched mutt on large Maildir folders).  For git, it's a win
because hashing destroys locality anyway.

Re: Mercurial 0.3 vs git benchmarks

[Thomas Glanzmann]

Hello,

> Directory hashing has a negative impact on some applications (notably
> tar and unpatched mutt on large Maildir folders).  For git, it's a win
> because hashing destroys locality anyway.

this is inaccurate. Actually turning on directory hashing speeds-up big
maildirs a lot (tested with mutt-1.5.4 and higher with a maildir
containing 30thousand messages). But in the mutt case you also have the
header cache[1] which speeds up a lot - with or without hashed
directories. See also MEs comment[2] on this.

For tar I have no idea why it should slow down the operation, but maybe
you can enlighten us.

	Thomas

[1] http://wwwcip.informatik.uni-erlangen.de/~sithglan/mutt/
	- wait till TLR has released mutt-1.5.10
	- use mutt CVS HEAD
	- use mutt-1.5.9 + http://wwwcip.informatik.uni-erlangen.de/~sithglan/mutt/mutt-cvs-header-cache.29
	- and put the following in your .muttrc:
	set header_cache=/tmp/login-hcache
	set maildir_header_cache_verify=no

[2] http://www.advogato.org/person/scandal/

Re: Mercurial 0.3 vs git benchmarks

[H. Peter Anvin]

Thomas Glanzmann wrote:
> 
> For tar I have no idea why it should slow down the operation, but maybe
> you can enlighten us.
> 

Directory hashing slows down operations that do linear sweeps through 
the filesystem reading every single file, simply because without 
dir_index, there is likely to be a correlation between inode order and 
directory order, whereas with dir_index, readdir() returns entries in 
hash order.

	-hpa

Re: Mercurial 0.3 vs git benchmarks

[Thomas Glanzmann]

Hello,

> Directory hashing slows down operations that do linear sweeps through 
> the filesystem reading every single file, simply because without 
> dir_index, there is likely to be a correlation between inode order and 
> directory order, whereas with dir_index, readdir() returns entries in 
> hash order.

thank you for the awareness training. Than mutt should be slower, too.
Maybe I should repeat that tests.

	Thomas

Re: Mercurial 0.3 vs git benchmarks

[Theodore Ts'o]

On Wed, Apr 27, 2005 at 09:01:44PM +0200, Thomas Glanzmann wrote:
> Hello,
> 
> > Directory hashing slows down operations that do linear sweeps through 
> > the filesystem reading every single file, simply because without 
> > dir_index, there is likely to be a correlation between inode order and 
> > directory order, whereas with dir_index, readdir() returns entries in 
> > hash order.
> 
> thank you for the awareness training. Than mutt should be slower, too.
> Maybe I should repeat that tests.

If you are using the mutt in Debian unstable, it has the patch applied
which qsorts based on inode number returned from readdir(), which is
why you may not have been seeing the problem.

Or you can LD_PRELOAD the attached quick hack....

						- Ted

/*
 * readdir accelerator
 *
 * (C) Copyright 2003, 2004 by Theodore Ts'o.
 *
 * Compile using the command:
 *
 * gcc -o spd_readdir.so -shared spd_readdir.c -ldl
 *
 * %Begin-Header%
 * This file may be redistributed under the terms of the GNU Public
 * License.
 * %End-Header%
 * 
 */

#define ALLOC_STEPSIZE	100
#define MAX_DIRSIZE	0

#define DEBUG

#ifdef DEBUG
#define DEBUG_DIR(x)	{if (do_debug) { x; }}
#else
#define DEBUG_DIR(x)
#endif

#define _GNU_SOURCE
#define __USE_LARGEFILE64

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <stdlib.h>
#include <string.h>
#include <dirent.h>
#include <errno.h>
#include <dlfcn.h>

struct dirent_s {
	unsigned long long d_ino;
	long long d_off;
	unsigned short int d_reclen;
	unsigned char d_type;
	char *d_name;
};

struct dir_s {
	DIR	*dir;
	int	num;
	int	max;
	struct dirent_s *dp;
	int	pos;
	int	fd;
	struct dirent ret_dir;
	struct dirent64 ret_dir64;
};

static int (*real_closedir)(DIR *dir) = 0;
static DIR *(*real_opendir)(const char *name) = 0;
static struct dirent *(*real_readdir)(DIR *dir) = 0;
static struct dirent64 *(*real_readdir64)(DIR *dir) = 0;
static off_t (*real_telldir)(DIR *dir) = 0;
static void (*real_seekdir)(DIR *dir, off_t offset) = 0;
static int (*real_dirfd)(DIR *dir) = 0;
static unsigned long max_dirsize = MAX_DIRSIZE;
static num_open = 0;
#ifdef DEBUG
static int do_debug = 0;
#endif

static void setup_ptr()
{
	char *cp;

	real_opendir = dlsym(RTLD_NEXT, "opendir");
	real_closedir = dlsym(RTLD_NEXT, "closedir");
	real_readdir = dlsym(RTLD_NEXT, "readdir");
	real_readdir64 = dlsym(RTLD_NEXT, "readdir64");
	real_telldir = dlsym(RTLD_NEXT, "telldir");
	real_seekdir = dlsym(RTLD_NEXT, "seekdir");
	real_dirfd = dlsym(RTLD_NEXT, "dirfd");
	if ((cp = getenv("SPD_READDIR_MAX_SIZE")) != NULL) {
		max_dirsize = atol(cp);
	}
#ifdef DEBUG
	if (getenv("SPD_READDIR_DEBUG"))
		do_debug++;
#endif
}

static void free_cached_dir(struct dir_s *dirstruct)
{
	int i;

	if (!dirstruct->dp)
		return;

	for (i=0; i < dirstruct->num; i++) {
		free(dirstruct->dp[i].d_name);
	}
	free(dirstruct->dp);
	dirstruct->dp = 0;
}	

static int ino_cmp(const void *a, const void *b)
{
	const struct dirent_s *ds_a = (const struct dirent_s *) a;
	const struct dirent_s *ds_b = (const struct dirent_s *) b;
	ino_t i_a, i_b;
	
	i_a = ds_a->d_ino;
	i_b = ds_b->d_ino;

	if (ds_a->d_name[0] == '.') {
		if (ds_a->d_name[1] == 0)
			i_a = 0;
		else if ((ds_a->d_name[1] == '.') && (ds_a->d_name[2] == 0))
			i_a = 1;
	}
	if (ds_b->d_name[0] == '.') {
		if (ds_b->d_name[1] == 0)
			i_b = 0;
		else if ((ds_b->d_name[1] == '.') && (ds_b->d_name[2] == 0))
			i_b = 1;
	}

	return (i_a - i_b);
}


DIR *opendir(const char *name)
{
	DIR *dir;
	struct dir_s	*dirstruct;
	struct dirent_s *ds, *dnew;
	struct dirent64 *d;
	struct stat st;

	if (!real_opendir)
		setup_ptr();

	DEBUG_DIR(printf("Opendir(%s) (%d open)\n", name, num_open++));
	dir = (*real_opendir)(name);
	if (!dir)
		return NULL;

	dirstruct = malloc(sizeof(struct dir_s));
	if (!dirstruct) {
		(*real_closedir)(dir);
		errno = -ENOMEM;
		return NULL;
	}
	dirstruct->num = 0;
	dirstruct->max = 0;
	dirstruct->dp = 0;
	dirstruct->pos = 0;
	dirstruct->dir = 0;

	if (max_dirsize && (stat(name, &st) == 0) && 
	    (st.st_size > max_dirsize)) {
		DEBUG_DIR(printf("Directory size %ld, using direct readdir\n",
				 st.st_size));
		dirstruct->dir = dir;
		return (DIR *) dirstruct;
	}

	while ((d = (*real_readdir64)(dir)) != NULL) {
		if (dirstruct->num >= dirstruct->max) {
			dirstruct->max += ALLOC_STEPSIZE;
			DEBUG_DIR(printf("Reallocating to size %d\n", 
					 dirstruct->max));
			dnew = realloc(dirstruct->dp, 
				       dirstruct->max * sizeof(struct dir_s));
			if (!dnew)
				goto nomem;
			dirstruct->dp = dnew;
		}
		ds = &dirstruct->dp[dirstruct->num++];
		ds->d_ino = d->d_ino;
		ds->d_off = d->d_off;
		ds->d_reclen = d->d_reclen;
		ds->d_type = d->d_type;
		if ((ds->d_name = malloc(strlen(d->d_name)+1)) == NULL) {
			dirstruct->num--;
			goto nomem;
		}
		strcpy(ds->d_name, d->d_name);
		DEBUG_DIR(printf("readdir: %lu %s\n", 
				 (unsigned long) d->d_ino, d->d_name));
	}
	dirstruct->fd = dup((*real_dirfd)(dir));
	(*real_closedir)(dir);
	qsort(dirstruct->dp, dirstruct->num, sizeof(struct dirent_s), ino_cmp);
	return ((DIR *) dirstruct);
nomem:
	DEBUG_DIR(printf("No memory, backing off to direct readdir\n"));
	free_cached_dir(dirstruct);
	dirstruct->dir = dir;
	return ((DIR *) dirstruct);
}

int closedir(DIR *dir)
{
	struct dir_s	*dirstruct = (struct dir_s *) dir;

	DEBUG_DIR(printf("Closedir (%d open)\n", --num_open));
	if (dirstruct->dir)
		(*real_closedir)(dirstruct->dir);

	if (dirstruct->fd >= 0)
		close(dirstruct->fd);
	free_cached_dir(dirstruct);
	free(dirstruct);
	return 0;
}

struct dirent *readdir(DIR *dir)
{
	struct dir_s	*dirstruct = (struct dir_s *) dir;
	struct dirent_s *ds;

	if (dirstruct->dir)
		return (*real_readdir)(dirstruct->dir);

	if (dirstruct->pos >= dirstruct->num)
		return NULL;

	ds = &dirstruct->dp[dirstruct->pos++];
	dirstruct->ret_dir.d_ino = ds->d_ino;
	dirstruct->ret_dir.d_off = ds->d_off;
	dirstruct->ret_dir.d_reclen = ds->d_reclen;
	dirstruct->ret_dir.d_type = ds->d_type;
	strncpy(dirstruct->ret_dir.d_name, ds->d_name,
		sizeof(dirstruct->ret_dir.d_name));

	return (&dirstruct->ret_dir);
}

struct dirent64 *readdir64(DIR *dir)
{
	struct dir_s	*dirstruct = (struct dir_s *) dir;
	struct dirent_s *ds;

	if (dirstruct->dir)
		return (*real_readdir64)(dirstruct->dir);

	if (dirstruct->pos >= dirstruct->num)
		return NULL;

	ds = &dirstruct->dp[dirstruct->pos++];
	dirstruct->ret_dir64.d_ino = ds->d_ino;
	dirstruct->ret_dir64.d_off = ds->d_off;
	dirstruct->ret_dir64.d_reclen = ds->d_reclen;
	dirstruct->ret_dir64.d_type = ds->d_type;
	strncpy(dirstruct->ret_dir64.d_name, ds->d_name,
		sizeof(dirstruct->ret_dir64.d_name));

	return (&dirstruct->ret_dir64);
}

off_t telldir(DIR *dir)
{
	struct dir_s	*dirstruct = (struct dir_s *) dir;

	if (dirstruct->dir)
		return (*real_telldir)(dirstruct->dir);

	return ((off_t) dirstruct->pos);
}

void seekdir(DIR *dir, off_t offset)
{
	struct dir_s	*dirstruct = (struct dir_s *) dir;

	if (dirstruct->dir) {
		(*real_seekdir)(dirstruct->dir, offset);
		return;
	}

	dirstruct->pos = offset;
}

int dirfd(DIR *dir)
{
	struct dir_s	*dirstruct = (struct dir_s *) dir;

	if (dirstruct->dir)
		return (*real_dirfd)(dirstruct->dir);

	return (dirstruct->fd);
}

Re: Mercurial 0.3 vs git benchmarks

[Thomas Glanzmann]

Hello,

> Or you can LD_PRELOAD the attached quick hack....

nice one! I have to keep that around. :-)

Thanks,
	Thomas

Re: Mercurial 0.3 vs git benchmarks

[H. Peter Anvin]

Thomas Glanzmann wrote:
> Hello,
> 
> 
>>Directory hashing slows down operations that do linear sweeps through 
>>the filesystem reading every single file, simply because without 
>>dir_index, there is likely to be a correlation between inode order and 
>>directory order, whereas with dir_index, readdir() returns entries in 
>>hash order.
> 
> 
> thank you for the awareness training. Than mutt should be slower, too.
> Maybe I should repeat that tests.
> 

Only if you read every single file in each directory every time.  I 
thought mutt did header indexing and thus didn't need to do that.

	-hpa

Re: Mercurial 0.3 vs git benchmarks

[Thomas Glanzmann]

Hello,

> Only if you read every single file in each directory every time.  I 
> thought mutt did header indexing and thus didn't need to do that.

it does, but it is a very recent development (coming with the next
release). Prior to this you need a patch, which has debian applied since
some time. And configure it. Otherwise *all* Maildir files we opened and
parsed when a folder is entered.

	Thomas

Re: Mercurial 0.3 vs git benchmarks

[Florian Weimer]

* H. Peter Anvin:

> Only if you read every single file in each directory every time.  I 
> thought mutt did header indexing and thus didn't need to do that.

There was a patch for Mutt which implemented header indexing, but it
was buggy and had to be removed (from Debian).  After that, directory
sorting (actually, it's a merge sort 8-) practically became mandatory
on ext3 with directory hashing.

I think that in the meantime, the has been integrated into upstream
CVS (I don't know if it's been released as a developer snapshot,
though).  The header indexing patch may have been revived for Debian,
I think it was fixed recently.

Re: Mercurial 0.3 vs git benchmarks

[Florian Weimer]

* Thomas Glanzmann:

>> Directory hashing slows down operations that do linear sweeps through 
>> the filesystem reading every single file, simply because without 
>> dir_index, there is likely to be a correlation between inode order and 
>> directory order, whereas with dir_index, readdir() returns entries in 
>> hash order.
>
> thank you for the awareness training. Than mutt should be slower, too.
> Maybe I should repeat that tests.

Benchmarks are actually a bit tricky because as far as I can tell,
once you hash the directories, they are tainted even if you mount your
file system with ext2.

Re: Mercurial 0.3 vs git benchmarks

[H. Peter Anvin]

Florian Weimer wrote:
> 
> Benchmarks are actually a bit tricky because as far as I can tell,
> once you hash the directories, they are tainted even if you mount your
> file system with ext2.

That's what fsck -D is for.

	-hpa

Re: Mercurial 0.3 vs git benchmarks

[Florian Weimer]

* H. Peter Anvin:

> Florian Weimer wrote:
>> Benchmarks are actually a bit tricky because as far as I can tell,
>> once you hash the directories, they are tainted even if you mount your
>> file system with ext2.
>
> That's what fsck -D is for.

Ah, cool, I didn't know that it works the other way, too.  Thanks.

Re: Mercurial 0.3 vs git benchmarks

[Theodore Ts'o]

On Wed, Apr 27, 2005 at 11:06:06PM +0200, Florian Weimer wrote:
> * H. Peter Anvin:
> 
> > Florian Weimer wrote:
> >> Benchmarks are actually a bit tricky because as far as I can tell,
> >> once you hash the directories, they are tainted even if you mount your
> >> file system with ext2.
> >
> > That's what fsck -D is for.
> 
> Ah, cool, I didn't know that it works the other way, too.  Thanks.

If htree support is disabled, e2fsck -D sorts by name, which was a
silly thing to do.  I should change it to sort by inode number instead
(trivial patch).  This might not be a problem for the maildir format,
given its naming convention.

						- Ted

Re: Mercurial 0.3 vs git benchmarks

[Theodore Ts'o]

On Tue, Apr 26, 2005 at 03:56:09PM -0700, Andrew Morton wrote:
> - umount the fs
> - tune2fs -O ^has_journal /dev/whatever
> - fsck -fy                              (to clean up the now-orphaned journal inode)

Using moderately recent versions of e2fsprogs, tune2fs will clean up
the journal inode, so there's no reason to do an fsck.  (Harmless, but
it shouldn't be necessary and it takes time).

> - tune2fs -j -J size=nblocks    (normally 4k blocks)

The argument to "-J size" is in megabytes, not in blocks.

						- Ted

Re: Mercurial 0.3 vs git benchmarks

[Ingo Molnar]

* Andrew Morton <akpm@osdl.org> wrote:

> Magnus Damm <magnus.damm@gmail.com> wrote:
> >
> > My primitive guess is that it was because
> >  the ext3 journal became full.
> 
> The default ext3 journal size is inappropriately small, btw.  Normally 
> you should manually make it 128M or so, rather than 32M.  Unless you 
> have a small amount of memory and/or a large number of filesystems, in 
> which case there might be problems with pinned memory.
> 
> Mounting as ext2 is a useful technique for determining whether the fs 
> is getting in the way.

on ext3, when juggling patches and trees, the biggest performance boost 
for me comes from adding noatime,nodiratime to the mount options in 
/etc/fstab:

 LABEL=/ / ext3 noatime,nodiratime,defaults 1 1

	Ingo

Re: Mercurial 0.3 vs git benchmarks

[Bill Davidsen]

Ingo Molnar wrote:
> * Andrew Morton <akpm@osdl.org> wrote:
> 
> 
>>Magnus Damm <magnus.damm@gmail.com> wrote:
>>
>>>My primitive guess is that it was because
>>> the ext3 journal became full.
>>
>>The default ext3 journal size is inappropriately small, btw.  Normally 
>>you should manually make it 128M or so, rather than 32M.  Unless you 
>>have a small amount of memory and/or a large number of filesystems, in 
>>which case there might be problems with pinned memory.
>>
>>Mounting as ext2 is a useful technique for determining whether the fs 
>>is getting in the way.
> 
> 
> on ext3, when juggling patches and trees, the biggest performance boost 
> for me comes from adding noatime,nodiratime to the mount options in 
> /etc/fstab:
> 
>  LABEL=/ / ext3 noatime,nodiratime,defaults 1 1

I said much the same in another post, but noatime is not always what I 
really want. How about a "nojournalatime" option, so the atime would be 
updated at open and close, but not journaled at any other time. This 
would reduce journal traffic but still allow an admin to tell if anyone 
ever uses a file. The info would be lost in a crash, but otherwise 
preserved just as it is for ext2. Might even be useful for ext2, not to 
write the atime, just track it in core.

-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me

Re: Mercurial 0.3 vs git benchmarks

[Linus Torvalds]

On Wed, 27 Apr 2005, Bill Davidsen wrote:
> 
> I said much the same in another post, but noatime is not always what I 
> really want.

"atime" is really nasty for a filesystem. I don't know if anybody noticed, 
but git already uses O_NOATIME to open all the object files, because if 
you don't do that, then just looking at a full kernel tree (which has more 
than a thousand subdirectories) will cause nasty IO patterns from just 
writing back "atime" information for the "tree" objects we looked up.

So you can do (and git does) selective atime updates. It just requires a 
small amount of extra care. 

> How about a "nojournalatime" option, so the atime would be 
> updated at open and close, but not journaled at any other time.

Probably a good idea. 

		Linus

Re: Mercurial 0.3 vs git benchmarks

[Linus Torvalds]

On Tue, 26 Apr 2005, Chris Mason wrote:
> 
> This agrees with my tests here, the time to apply patches is somewhat disk 
> bound, even for the small 100 or 200 patch series.  The io should be coming 
> from data=ordered, since the commits are still every 5 seconds or so.

Yes, ext3 really does suck in many ways.

One of my (least) favourite suckage is a process that does "fsync" on a
single file (mail readers etc), which apparently causes ext3 to sync all
dirty data, because it can only sync the whole log. So if you have stuff
that writes out things that aren't critical, it negatively affects
something totally independent that _does_ care.

I remember some early stuff showing that reiserfs was _much_ better for 
BK. I'd be willing to bet that's probably true for git too.

		Linus

Re: Mercurial 0.3 vs git benchmarks

[Chris Mason]

On Tuesday 26 April 2005 12:42, Linus Torvalds wrote:
> On Tue, 26 Apr 2005, Chris Mason wrote:
> > This agrees with my tests here, the time to apply patches is somewhat
> > disk bound, even for the small 100 or 200 patch series.  The io should be
> > coming from data=ordered, since the commits are still every 5 seconds or
> > so.
>
> Yes, ext3 really does suck in many ways.
>
> One of my (least) favourite suckage is a process that does "fsync" on a
> single file (mail readers etc), which apparently causes ext3 to sync all
> dirty data, because it can only sync the whole log. So if you have stuff
> that writes out things that aren't critical, it negatively affects
> something totally independent that _does_ care.
>
> I remember some early stuff showing that reiserfs was _much_ better for
> BK. I'd be willing to bet that's probably true for git too.

reiserfs shares the same basic data=ordered idea as ext3, so the fsync will do 
the same on reiser as it does on ext3.  I do have code in there to try and 
keep the data=ordered writeback a little less bursty than it is in ext3 so 
you might not notice the fsync as much.

I haven't compared reiser vs ext3 for git.  reiser tails should help 
performance because once you read the object inode you've also got the data.  
But, I would expect the biggest help to come from mounting reiserfs -o 
alloc=skip_busy.  This basically allocates all new files one right after the 
other on disk regardless of which subdir they are in.  The effect is to time 
order most of your files.

As an example, here's the time to apply 300 patches on ext3.  This was with my 
packed patches applied, but vanilla git should show similar percentage 
differences.

data=writeback  32s			
data=ordered    44s

With a long enough test, data=ordered should fall into the noise, but 10-40 
second runs really show it.

-chris

Re: Mercurial 0.3 vs git benchmarks

[Chris Mason]

On Tuesday 26 April 2005 13:39, Chris Mason wrote:

> As an example, here's the time to apply 300 patches on ext3.  This was with
> my packed patches applied, but vanilla git should show similar percentage
> differences.
>
> data=writeback  32s
> data=ordered    44s
>
> With a long enough test, data=ordered should fall into the noise, but 10-40
> second runs really show it.

I get much closer numbers if the patches directory is already in 
cache...data=ordered means more contention for the disk when trying to read 
the patches.  

If the patches are hot in the cache data=writeback and data=ordered both take 
about 30s.  You still see some writes in data=writeback, but these are mostly 
async log commits.  

The same holds true for vanilla git as well, although it needs 1m7s to apply 
from a hot cache (sorry, couldn't resist the plug ;)

-chris

Re: Mercurial 0.3 vs git benchmarks

[H. Peter Anvin]

Linus Torvalds wrote:
> 
> And don't try to make me explain why the patchbomb has any IO time at all,
> it should all have fit in the cache, but I think the writeback logic
> kicked in.

The default log size on ext3 is quite small.  Making the log larger 
probably would have helped.

	-hpa

Re: Mercurial 0.3 vs git benchmarks

[Bill Davidsen]

H. Peter Anvin wrote:
> Linus Torvalds wrote:
> 
>>
>> And don't try to make me explain why the patchbomb has any IO time at 
>> all,
>> it should all have fit in the cache, but I think the writeback logic
>> kicked in.
> 
> 
> The default log size on ext3 is quite small.  Making the log larger 
> probably would have helped.

Experience tells me that making the log larger does very good things for 
performance in many load types. However, that fsync issue forcing the 
write of the whole log may get worse if there's a lot pending.

I suspect this would be helped by noatime.

-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me

Re: Mercurial 0.3 vs git benchmarks

[Bill Davidsen]

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

Linus Torvalds wrote:
> 
> On Mon, 25 Apr 2005, Mike Taht wrote:
> 
>>One difference is probably - mercurial appears to be using zlib's 
>>*default* compression of 6....
>>
>>using zlib compression of 9 really impacts git...
> 
> 
> I agree that it will hurt for big changes, but since I really do believe 
> that most changes are just a couple of files, I don't believe it matters 
> for those. 
> 
> I forget what the exact numbers were, but I did some timings on plain
> "gzip", and it basically said that doing gzip on a medium-sized file was
> not that different for -6 and -9. Why? Because most of the overhead was
> elsewhere ;)

Certainly not different in the overall numbers, but after trying gzip on 
a bunch of various source files on 32 bit CPUs, from P-II to Xeon, it 
looks as if after 7 the cpu jumps about 40% to 8, and another 30% to 9. 
Neither 8 nor 9 give any significant size improvement (< 2%).

Again, this is 32 bit CPU and just the gzip component, reading from 
stdin and writing to stdout which I hope gets directory operations out 
of the time measure.

Sample attached.

-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me

[-- Attachment #2: ziptime.log --]
[-- Type: text/plain, Size: 1037 bytes --]

Comp level 1

real	0m1.972s
user	0m1.790s
sys	0m0.098s
-rw-r--r--    1 davidsen  1792050 Apr 26 11:56 dummy.tar.gz
Comp level 2

real	0m2.021s
user	0m1.858s
sys	0m0.097s
-rw-r--r--    1 davidsen  1737227 Apr 26 11:56 dummy.tar.gz
Comp level 3

real	0m2.296s
user	0m2.124s
sys	0m0.095s
-rw-r--r--    1 davidsen  1697644 Apr 26 11:56 dummy.tar.gz
Comp level 4

real	0m2.604s
user	0m2.423s
sys	0m0.099s
-rw-r--r--    1 davidsen  1593207 Apr 26 11:56 dummy.tar.gz
Comp level 5

real	0m3.181s
user	0m3.003s
sys	0m0.087s
-rw-r--r--    1 davidsen  1549050 Apr 26 11:56 dummy.tar.gz
Comp level 6

real	0m4.185s
user	0m3.965s
sys	0m0.089s
-rw-r--r--    1 davidsen  1531866 Apr 26 11:56 dummy.tar.gz
Comp level 7

real	0m4.889s
user	0m4.642s
sys	0m0.096s
-rw-r--r--    1 davidsen  1524350 Apr 26 11:57 dummy.tar.gz
Comp level 8

real	0m7.836s
user	0m7.532s
sys	0m0.085s
-rw-r--r--    1 davidsen  1513763 Apr 26 11:57 dummy.tar.gz
Comp level 9

real	0m11.020s
user	0m10.616s
sys	0m0.092s
-rw-r--r--    1 davidsen  1511970 Apr 26 11:57 dummy.tar.gz

Re: Mercurial 0.3 vs git benchmarks

[Matt Mackall]

On Mon, Apr 25, 2005 at 07:08:28PM -0700, Linus Torvalds wrote:
> 
> 
> On Mon, 25 Apr 2005, Matt Mackall wrote:
> >
> > Here are the results of checking in the first 12 releases of Linux 2.6
> > into empty repositories for Mercurial v0.3 (hg) and git-pasky-0.7.
> > This is on my 512M Pentium M laptop. Times are in seconds.
> > 
> >                  user         system       real        du -sh
> > ver    files   hg    git    hg    git    hg    git    hg   git
> > 
> > 2.6.0  15007 19.949 35.526 3.171 2.264 25.138 87.994 145M   89M
> > 2.6.1    998  5.906  4.018 0.573 0.464 10.267  5.937 146M   99M
> > 2.6.2   2370  9.696 13.051 0.752 0.652 12.970 15.167 150M  117M
> > 2.6.3   1906 10.528 11.509 0.816 0.639 18.406 14.318 152M  135M
> > 2.6.4   3185 11.140  7.380 0.997 0.731 15.265 12.412 156M  158M
> > 2.6.5   2261 10.961  6.939 0.843 0.640 20.564  8.522 158M  177M
> > 2.6.6   2642 11.803 10.043 0.870 0.678 22.360 11.515 162M  197M
> > 2.6.7   3772 18.411 15.243 1.189 0.915 32.397 21.498 165M  227M
> > 2.6.8   4604 20.922 16.054 1.406 1.041 39.622 25.056 172M  262M
> > 2.6.9   4712 19.306 12.145 1.421 1.102 35.663 24.958 179M  297M
> > 2.6.10  5384 23.022 18.154 1.393 1.182 40.947 32.085 186M  338M
> > 2.6.11  5662 27.211 19.138 1.791 1.253 42.605 31.902 193M  379M
> 
> That time in checking things in is worrisome.
> 
> "git" is basically linear in the size of the patch, which is what I want,
> since most patches I work with are a couple of files at most. The patches
> you are checking in are huge - I never actually work with a change that is
> as big as a whole release. I work with changes that are five files or
> something.

Git (and hg) commit time should be basically linear in the number of
files touched, not the size of the patch.

> "hg" seems to basically slow down the more patches you have applied. It's 
> hard to tell from the limited test set, but look at "user" time. It seems 
> to increase from 6 seconds to 27 seconds.

And the number of files checked in grows from ~1000 to ~6000. Note
that git is growing from 4 to 19 seconds as well. Interestingly:

19.138/4.018 = 4.76 (git time ratio)
27.211/5.906 = 4.61 (hg time ratio)

So the scaling here is pretty similar.

> To make an interesting benchmark, try applying the first 200 patches in 
> the current git kernel archive. Can you do them three per second? THAT is 
> the thing you should optimize for, not checking in huge changes.

I'm not versant enough with git enough to know how but I'll give it a
shot. Do you have the patches in an mbox, perchance? This is Andrew's
x/198 patch bomb? It might be simpler for me to just apply everything
in -mm to git and hg and compare times. Modulo python startup time, it
should be pretty similar.

Oh, and can you send me the script you used for your test with git?

> If you're checking in a change to 1000+ files, you're doing something
> wrong.

That's primarily to demonstrate the scalability and show the
divergence in repository sizes.

However, it will not be uncommon for developers to pull/merge changes that
large and the numbers here will be about the same for hg.

> > Full-tree working dir diff (2.6.0 base with 2.6.1 in working dir):
> > hg:  real 4.920s  user 4.629s  sys 0.260s
> > git: real 3.531s  user 1.869s  sys 0.862s
> > (this needed an update-cache --refresh on top of git commit, which
> > took another: real 2m52.764s  user 2.833s  sys 1.008s)
> 
> You're doing something wrong with git here. Why would you need to update 
> your cache?

Quite possibly. Without it, I was getting a dump of a bunch of SHAs.
I'm pretty git-ignorant, I've been focusing on something else for the
past couple weeks.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Mercurial 0.3 vs git benchmarks

[Linus Torvalds]

On Mon, 25 Apr 2005, Matt Mackall wrote:
> 
> And the number of files checked in grows from ~1000 to ~6000. Note
> that git is growing from 4 to 19 seconds as well.

Heh,. I didn't much look at the git numbers, since I knew those were 
supposed to be linear in the size of the patch...

> I'm not versant enough with git enough to know how but I'll give it a
> shot. Do you have the patches in an mbox, perchance? This is Andrew's
> x/198 patch bomb?

Yes. I have my "tools" scripts for git in

	kernel.org:/pub/linux/kernel/people/torvalds/git-tools.git

and I sent out the script I used to test the 2.6.12-rc2 + patches stuff in 
the previous email, so you would just have to edit my mbox-applicator 
tools to work with hg and get comparable numbers.

> It might be simpler for me to just apply everything
> in -mm to git and hg and compare times.

That should work.

> > You're doing something wrong with git here. Why would you need to update 
> > your cache?
> 
> Quite possibly. Without it, I was getting a dump of a bunch of SHAs.
> I'm pretty git-ignorant, I've been focusing on something else for the
> past couple weeks.

Getting a bunch of SHA's means that the file contents match, but that your 
index file wasn't up-to-date, so git had to actually uncompress the object 
backing store and _compare_ the file contents to notice.

And I suspect that you may have done _all_ your numbers without ever
having initialized the git index, in which case git will really suck raw
eggs, because git will basically always re-read every file (it will never
realize that they are up-to-date already).

Basically, the theory of git operation is that the index file should
_always_ be up-to-date.  Normally you don't have to do anything about it,
since the git helper tools will always just keep it that way, but if you
didn't, then..

		Linus

Re: Mercurial 0.3 vs git benchmarks

[Chris Wedgwood]

On Mon, Apr 25, 2005 at 07:08:28PM -0700, Linus Torvalds wrote:

> If you're checking in a change to 1000+ files, you're doing
> something wrong.

arch or subsystem merge?

Re: Mercurial 0.3 vs git benchmarks

[Andreas Gal]

If adding a new arch touches 1000+ files, you're doing something 
_very_ wrong. Plus, how often did that happen in the past 10 years? 
30 times?? Probably less.

Andreas

On Mon, 25 Apr 2005, Chris Wedgwood wrote:

> On Mon, Apr 25, 2005 at 07:08:28PM -0700, Linus Torvalds wrote:
> 
> > If you're checking in a change to 1000+ files, you're doing
> > something wrong.
> 
> arch or subsystem merge?
> 
> -
> To unsubscribe from this list: send the line "unsubscribe git" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: Mercurial 0.3 vs git benchmarks

[Linus Torvalds]

On Mon, 25 Apr 2005, Chris Wedgwood wrote:
>
> On Mon, Apr 25, 2005 at 07:08:28PM -0700, Linus Torvalds wrote:
> 
> > If you're checking in a change to 1000+ files, you're doing
> > something wrong.
> 
> arch or subsystem merge?

No, if it's a merge, you just suck in all the already-compressed objects.  

You never compress anything new - you get the objects, you update your
tree index, and you're done. No overhead anywhere - a clean merge may
_look_ like it's changing thousands of files, but it didn't change a
single _object_ anywhere, it just re-arranged the objects and created a
new view of them.

Most merges are literally just a tree-level thing. Sometimes you have to 
do a content merge, but that tends to be a file or two.

			Linus

Mercurial 0.4b vs git patchbomb benchmark

[Matt Mackall]

On Mon, Apr 25, 2005 at 07:08:28PM -0700, Linus Torvalds wrote:
> 
> To make an interesting benchmark, try applying the first 200 patches in 
> the current git kernel archive. Can you do them three per second? THAT is 
> the thing you should optimize for, not checking in huge changes.

Ok, I've optimized for it a bit. This is basically:

 hg import -p1 -b ../broken-out `cat ../broken-out | grep -v #`

 ( latest code is at: http://selenic.com/mercurial/ )

My benchmark is to apply all 819 patches from -mm3 to 2.6.12-rc:

hg:

real    3m22.075s
user    1m57.195s
sys     0m14.068s

819/(60+57.195 + 14.068) = 6.239 patches/second  user+sys
repository: before 167M after 173M (3.5% growth)

git:

real    2m58.568s
user    1m11.196s
sys     0m50.144s

819/(60+11.196+50.144) = 6.750 patches/second  user+sys
repository: before 102M after 154M (51% growth)

Again, pretty close, time-wise. My code is actually spending a fair
amount of time doing delta compression in Python, which accounts for
most of the extra user time. So I think I can optimize most of that
away at some point. Interestingly hg is also using substantially less
system time.

What I'd like to highlight here is that git's repo is growing more
than 10 times faster. 52 megs is twice the size of a full kernel
tarball. And that's going to be the bottleneck for network pull
operations.

The fundamental problem I see with git is that the back-end has no
concept of the relation between files. This data is only present in
change nodes so you've got to potentially traverse all the commits to
reconstruct a file's history. That's gonna be O(top-level changes)
seeks. This introduces a number of problems:

- no way to easily find previous revisions of a file
  (being able to see when a particular change was introduced is a
  pretty critical feature)
- no way to do bandwidth-efficient delta transfer
- no way to do efficient delta storage
- no way to do merges based on the file's history[1]

Mercurial can grab look up and grab revisions of a file in O(1)
time/seeks. I haven't implemented annotate yet, but it can also be
done O(1) or O(file revisions).


[1] This last one is interesting. If we've got a repository with files A
and B:

M   M1   M2

AB
 |`-------v     M2 clones M
aB       AB     file A is change in mainline
 |`---v  AB'    file B is changed in M2
 |   aB / |     M1 clones M
 |   ab/  |     M1 changes B
 |   ab'  |     M1 merges from M2, changes to B conflict
 |    |  A'B'   M2 changes A
  `---+--.|
      |  a'B'   M2 merges from mainline, changes to A conflict
      `--.|
         ???    depending on which ancestor we choose, we will have
	        to redo A hand-merge, B hand-merge, or both
                but if we look at the files independently, everything
		is fine

-- 
Mathematics is the supreme nostalgia of our time.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Sean]

On Fri, April 29, 2005 2:01 am, Matt Mackall said:

> What I'd like to highlight here is that git's repo is growing more
> than 10 times faster. 52 megs is twice the size of a full kernel
> tarball. And that's going to be the bottleneck for network pull
> operations.

There isn't anything preventing optomized transfer protocols for git. 
Give it time.


> The fundamental problem I see with git is that the back-end has no
> concept of the relation between files. This data is only present in
> change nodes so you've got to potentially traverse all the commits to
> reconstruct a file's history. That's gonna be O(top-level changes)
> seeks. This introduces a number of problems:
>
> - no way to easily find previous revisions of a file
>   (being able to see when a particular change was introduced is a
>   pretty critical feature)

Scanning back through the history is a linear operation and will quite
likely be just fine for many uses.   As others have pointed out, you can
cache the result to improve subsequent lookups.


> - no way to do bandwidth-efficient delta transfer

There's nothing preventing this in the longer term.  And you know, we're
only talking about a few megabytes per release.  We're not talking about
video here.


> - no way to do efficient delta storage

This has been discussed.  It is a recognized and accepted design
trade-off.  Disk is cheap.


> - no way to do merges based on the file's history[1]

What is preventing merges from looking back through the git history?



The fundamental design of git is essentially done, it is what it is.

Your concearns are about performance rather than real limitations and it's
just too damn early in the development process for that.  Frankly it's
amazing how good git is considering its age; it's already _way_ faster and
easier to use than bk ever was for my use.


> Mathematics is the supreme nostalgia of our time.

I've been tying to figure out what this means for a while now <g>


Sean

Re: Mercurial 0.4b vs git patchbomb benchmark

[Matt Mackall]

On Fri, Apr 29, 2005 at 02:40:31AM -0400, Sean wrote:
> > - no way to do efficient delta storage
> 
> This has been discussed.  It is a recognized and accepted design
> trade-off.  Disk is cheap.

This trade-off FAILS, as my benchmarks against Mercurial have shown.
It trades 10x disk space for maybe 10% performance relative to my
approach. Meanwhile, it makes a bunch of other things hard, namely the
ones I've listed. Yes, you can hack around them, but the back end will
still be bloated.

> Your concearns are about performance rather than real limitations and it's
> just too damn early in the development process for that.  Frankly it's
> amazing how good git is considering its age; it's already _way_ faster and
> easier to use than bk ever was for my use.

Mercurial is even younger (Linus had a few days' head start, not to
mention a bunch of help), and it is already as fast as git, relatively
easy to use, much simpler, and much more space and bandwidth
efficient.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Sean]

On Fri, April 29, 2005 3:40 am, Matt Mackall said:

> This trade-off FAILS, as my benchmarks against Mercurial have shown.
> It trades 10x disk space for maybe 10% performance relative to my
> approach. Meanwhile, it makes a bunch of other things hard, namely the
> ones I've listed. Yes, you can hack around them, but the back end will
> still be bloated.

But since performance can be seen as worth so much more than disk, this
might still be a good tradeoff, even given your numbers.


> Mercurial is even younger (Linus had a few days' head start, not to
> mention a bunch of help), and it is already as fast as git, relatively
> easy to use, much simpler, and much more space and bandwidth
> efficient.


There are some really nice things about the git design, not just
performance related.   However, i have a git repository going back to the
start of 2.4 and for my uses there aren't any performance problems.  (okay
fsck-cache, gets oom killed but i suspect that can be fixed).

No _argument_ is going to change the fundamental design of git, it is what
it is.  Git started out as just an interim fix and maybe that's all it
will turn out to be.  But it's working pretty well so far, with lots of
room for improvement over time, and in my estimation Linus has made a
pretty compelling argument for the design tradeoffs he's made.

Sean

Re: Mercurial 0.4b vs git patchbomb benchmark

[Linus Torvalds]

On Fri, 29 Apr 2005, Matt Mackall wrote:
> 
> Mercurial is even younger (Linus had a few days' head start, not to
> mention a bunch of help), and it is already as fast as git, relatively
> easy to use, much simpler, and much more space and bandwidth
> efficient.

You've not mentioned two out of my three design goals:
 - distribution
 - reliability/trustability

ie does mercurial do distributed merges, which git was designed for, and 
does mercurial notice single-bit errors in a reasonably secure manner, or 
can people just mess with history willy-nilly?

For the latter, the cryptographic nature of sha1 is an added bonus - the
_big_ issue is that it is a good hash, and an _exteremely_ effective CRC
of the data. You can't mess up an archive and lie about it later. And if
you have random memory or filesystem corruption, it's not a "shit happens"  
kind of situation - it's a "uhhoh, we can catch it (and hopefully even fix
it, thanks to distribution)" thing.

I had three design goals. "disk space" wasn't one of them, so you've
concentrated on only one so far in your arguments.

		Linus

Re: Mercurial 0.4b vs git patchbomb benchmark

[Morten Welinder]

> I had three design goals. "disk space" wasn't one of them

And, if at some point it should become an issue, it's fixable.  Since
access to objects
is fairly centralized and since they are immutable, it would be quite
simple to move
an arbitrary selection of the objects into some other storage form
which could take
similarities between objects into account.

If you chose the selection of objects with care -- say those for files
that have changed
many times since -- it shouldn't even hurt performance of day-to-day
tasks (which aren't
likely to ever need those objects).

So disk space and its cousin number-of-files are both when-and-if
problems.  And not
scary ones at that.

Morten

Re: Mercurial 0.4b vs git patchbomb benchmark

[Matt Mackall]

On Fri, Apr 29, 2005 at 11:18:20AM -0400, Morten Welinder wrote:
> > I had three design goals. "disk space" wasn't one of them
> 
> And, if at some point it should become an issue, it's fixable. Since
> access to objects is fairly centralized and since they are
> immutable, it would be quite simple to move an arbitrary selection
> of the objects into some other storage form which could take
> similarities between objects into account.

This is not a fix, this is a band-aid. A fix is fitting all the data
in 10 times less space without sacrificing too much performance.

> So disk space and its cousin number-of-files are both when-and-if
> problems. And not scary ones at that.

But its sibling bandwidth _is_ a problem. The delta between 2.6.10 and
2.6.11 in git terms will be much larger than a _full kernel tarball_.
Simply checking in patch-2.6.11 on top of 2.6.10 as a single changeset
takes 41M. Break that into a thousand overlapping deltas (ie the way
it is actually done) and it will be much larger.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Bill Davidsen]

Matt Mackall wrote:
> On Fri, Apr 29, 2005 at 11:18:20AM -0400, Morten Welinder wrote:
> 
>>>I had three design goals. "disk space" wasn't one of them
>>
>>And, if at some point it should become an issue, it's fixable. Since
>>access to objects is fairly centralized and since they are
>>immutable, it would be quite simple to move an arbitrary selection
>>of the objects into some other storage form which could take
>>similarities between objects into account.
> 
> 
> This is not a fix, this is a band-aid. A fix is fitting all the data
> in 10 times less space without sacrificing too much performance.
> 
> 
>>So disk space and its cousin number-of-files are both when-and-if
>>problems. And not scary ones at that.
> 
> 
> But its sibling bandwidth _is_ a problem. The delta between 2.6.10 and
> 2.6.11 in git terms will be much larger than a _full kernel tarball_.
> Simply checking in patch-2.6.11 on top of 2.6.10 as a single changeset
> takes 41M. Break that into a thousand overlapping deltas (ie the way
> it is actually done) and it will be much larger.
> 
At this level of performance I would say it doesn't matter. If a full 
checkin take two minutes or three minutes doesn't concern me, because 
I'm not going to sit and watch it, I'm going to read LKML or write my 
beer blog in another window. I would care about two vs. three hours, but 
minutes are too long to wait and too short to care.

Now look at pulling 41MB over a T1 link. All of a sudden I care bigtime! 
I want very much to use my bandwidth for other things, I don't want 41MB 
added to my backup, etc. Disk space is cheap, but unless you ignore 
backups and have an OC3 or so, these numbers are large enough to be 
irritating. Not a huge issue, just one of those "piss me off every time 
I do it" things.

If there is a functional reason to use git, something Mercurial doesn't 
do, then developers will and should use git. But the associated hassles 
with large change size, rather than the absolute size, are worth 
considering.

-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me

Re: Mercurial 0.4b vs git patchbomb benchmark

[Sean]

On Mon, May 2, 2005 12:10 pm, Bill Davidsen said:

> Now look at pulling 41MB over a T1 link. All of a sudden I care bigtime!
> I want very much to use my bandwidth for other things, I don't want 41MB
> added to my backup, etc. Disk space is cheap, but unless you ignore
> backups and have an OC3 or so, these numbers are large enough to be
> irritating. Not a huge issue, just one of those "piss me off every time
> I do it" things.

That 41MB or lets say 200MB is spread over several months between
releases.   Pulling once a day from the git public repository, makes this
barely noticeable.  In the future there may be optimized protocols to
handle this more efficiently.

You bring up a good point about backups though.  Eventually it might be
nice to have a utility that exports/imports a git repository in a flat
file using deltas rather than snapshots.   Such an export format would
make backups and tarballs cheaper.

Sean

Re: Mercurial 0.4b vs git patchbomb benchmark

[Linus Torvalds]

On Mon, 2 May 2005, Bill Davidsen wrote:
> 
> If there is a functional reason to use git, something Mercurial doesn't 
> do, then developers will and should use git. But the associated hassles 
> with large change size, rather than the absolute size, are worth 
> considering.

Note that we discussed this early on, and the issues with full-file 
handling haven't changed. It does actually have real functional 
advantages:

 - you can share the objects freely between different trees, never 
   worrying about one tree corrupting another trees object by mistake.
 - you can drop old objects.

delta models very fundamentally don't support this. 

For example, a simple tree re-linker will work on any mirror site, and
work reliably, even if I end up uploading new objects with some tool that
doesn't know to break hardlinks etc. That can easily be much more than a
10x win for a git repository site (imagine something like bkbits.net, but
got git).

Whether it is a huge deal or not, I don't know. I do know that the big 
deal to me is just the simplicity of the git object models. It makes me 
trust it, even in the presense of inevitable bugs. It's a very safe model, 
and right now safe is good.

		Linus

Re: Mercurial 0.4b vs git patchbomb benchmark

[Matt Mackall]

On Mon, May 02, 2005 at 03:02:16PM -0700, Linus Torvalds wrote:
> 
> 
> On Mon, 2 May 2005, Bill Davidsen wrote:
> > 
> > If there is a functional reason to use git, something Mercurial doesn't 
> > do, then developers will and should use git. But the associated hassles 
> > with large change size, rather than the absolute size, are worth 
> > considering.
> 
> Note that we discussed this early on, and the issues with full-file 
> handling haven't changed. It does actually have real functional 
> advantages:
> 
>  - you can share the objects freely between different trees, never 
>    worrying about one tree corrupting another trees object by mistake.

Not sure if this is terribly useful. It just makes it harder to pull
the subset you're interested in.

>  - you can drop old objects.

You can't drop old objects without dropping all the changesets that
refer to them or otherwise being prepared to deal with the broken
links.

> delta models very fundamentally don't support this. 

The latter can be done in a pretty straightforward manner in mercurial
with one pass over the data. But I have a goal to make keeping the
whole history cheap enough that no one balks at it.

> For example, a simple tree re-linker will work on any mirror site, and
> work reliably, even if I end up uploading new objects with some tool that
> doesn't know to break hardlinks etc. That can easily be much more than a
> 10x win for a git repository site (imagine something like bkbits.net, but
> got git).

What is a tree re-linker? Finds duplicate files and hard-links them?
Ok, that makes some sense. But it's a win on one machine and a lose
everywhere else.

> Whether it is a huge deal or not, I don't know. I do know that the big 
> deal to me is just the simplicity of the git object models. It makes me 
> trust it, even in the presense of inevitable bugs. It's a very safe model, 
> and right now safe is good.

I've added an "hg verify" command to Mercurial. It doesn't attempt to
fix anything up yet, but it can catch a couple things that git
probably can't (like file revisions that aren't owned by any
changeset), namely because there's more metadata around to look at.

I'll probably post an updated version tomorrow, I'm beginning to work
on a git2hg script.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Linus Torvalds]

On Mon, 2 May 2005, Matt Mackall wrote:
> > 
> >  - you can share the objects freely between different trees, never 
> >    worrying about one tree corrupting another trees object by mistake.
> 
> Not sure if this is terribly useful. It just makes it harder to pull
> the subset you're interested in.

You don't have to share things in a single subdirectory. Symlinks and 
hardlinks work fine, as do actual filesystem tricks ;)

> >  - you can drop old objects.
> 
> You can't drop old objects without dropping all the changesets that
> refer to them or otherwise being prepared to deal with the broken
> links.

Absolutely. This needs support from fsck to allow us to say "commit xxxx 
is no longer in the tree, because we pruned it".

Alternatively (and that's the much less intrusive one), you keep all the
commit objects, but drop the tree and blob objects. Again, all you need 
for this to work is just feed a list of commits to fsck, and tell it 
"we've pruned those from the tree", which tells fsck not to start looking 
for the contents of those commits.

So for example, you can trivially have something that automates this: take 
each commit that is older than <x> days, add it to the "prune list", and 
run fsck, and delete all objects that now show up as being unreachable 
(since fsck won't be looking at what those commits reference).

I could write this up in ten minutes. It's really simple.

And it's simple _exactly_ because we don't do deltas.

> > delta models very fundamentally don't support this. 
> 
> The latter can be done in a pretty straightforward manner in mercurial
> with one pass over the data. But I have a goal to make keeping the
> whole history cheap enough that no one balks at it.

With delta's, you have two choices:

 - change all the sha1 names (ie a pruned tree would no longer be 
   compatible with a non-pruned one)
 - make the delta part not show up as part of the sha1 name (which means 
   that it's unprotected).

which one would you have?

> What is a tree re-linker? Finds duplicate files and hard-links them?
> Ok, that makes some sense. But it's a win on one machine and a lose
> everywhere else.

Where would it be a loss? Esepcially since with git, it's cheap (you don't 
need to compare content to find objects to link - you can just compare 
filename listings).

> I've added an "hg verify" command to Mercurial. It doesn't attempt to
> fix anything up yet, but it can catch a couple things that git
> probably can't (like file revisions that aren't owned by any
> changeset), namely because there's more metadata around to look at.

git-fsck-cache catches exactly those kinds of things. And since it checks
pretty much every _single_ assumption in git (which is not a lot, since
git doesn't have a lot of assumptions), I guarantee you that you can't
find any more than it does (the filename ordering is the big missing
piece: I _still_ don't verify that trees are ordered. I've been mentioning
it since the beginning, but I'm lazy).

In other words, your verifier can't verify anything more. It's entirely 
possible that more things can go _wrong_, since you have more indexes, so 
your verifier will have more to check, but that's not an advantage, that's 
a downside.

		Linus

Re: Mercurial 0.4b vs git patchbomb benchmark

[Matt Mackall]

On Mon, May 02, 2005 at 03:49:49PM -0700, Linus Torvalds wrote:
> > >  - you can drop old objects.
> > 
> > You can't drop old objects without dropping all the changesets that
> > refer to them or otherwise being prepared to deal with the broken
> > links.

[...]
 
> I could write this up in ten minutes. It's really simple.

It's still simple in Mercurial, but more importantly Mercurial _won't
need it_. Dropping history is a work-around, not a feature.
 
> > > delta models very fundamentally don't support this. 
> > 
> > The latter can be done in a pretty straightforward manner in mercurial
> > with one pass over the data. But I have a goal to make keeping the
> > whole history cheap enough that no one balks at it.
> 
> With delta's, you have two choices:
> 
>  - change all the sha1 names (ie a pruned tree would no longer be 
>    compatible with a non-pruned one)
>  - make the delta part not show up as part of the sha1 name (which means 
>    that it's unprotected).
> 
> which one would you have?

Umm.. I am _not_ calculating the SHA of the delta itself. That'd be
silly.

There are an arbitrary number of ways to calculate a delta between two
files. Similarly, there are an arbitrary number of ways to compress a
file (gzip has at least 9, not counting all the permutations of
flush). The only sensible thing to do is store a hash of the raw text
and check it against the fully restored text, because that's what you
care about being correct.

In Mercurial, deltas are just a storage detail and are effectively
completely hidden from everything except the innermost part of the
back-end. What's important is that Mercurial knows that A is a
revision of B in the backend and thus has enough information to
opportunistically attempt to calculate a delta.

So if the day ever comes when I want to prune the head of a log, I
simply reconstruct the first version to keep, store it in a new file,
then append all the deltas, unmodified. And fix up the offsets in the
indices. None of the hashes change.

> > What is a tree re-linker? Finds duplicate files and hard-links them?
> > Ok, that makes some sense. But it's a win on one machine and a lose
> > everywhere else.
> 
> Where would it be a loss? Esepcially since with git, it's cheap (you don't 
> need to compare content to find objects to link - you can just compare 
> filename listings).

Git repositories will be 10x larger than Mercurial everywhere that
doesn't benefit from this linking of unrelated trees. That is, folks
who aren't running gitbits.net.

> > I've added an "hg verify" command to Mercurial. It doesn't attempt to
> > fix anything up yet, but it can catch a couple things that git
> > probably can't (like file revisions that aren't owned by any
> > changeset), namely because there's more metadata around to look at.
> 
> git-fsck-cache catches exactly those kinds of things. And since it checks
> pretty much every _single_ assumption in git (which is not a lot, since
> git doesn't have a lot of assumptions), I guarantee you that you can't
> find any more than it does (the filename ordering is the big missing
> piece: I _still_ don't verify that trees are ordered. I've been mentioning
> it since the beginning, but I'm lazy).
> 
> In other words, your verifier can't verify anything more. It's entirely 
> possible that more things can go _wrong_, since you have more indexes, so 
> your verifier will have more to check, but that's not an advantage, that's 
> a downside.

Uh, no. It's just like a filesystem. Redundancy is what lets you
recover.

The extra indices are also very useful in their own right:

- they let you do easily do delta storage
- they let you efficiently do delta transmission
- they let you find past revisions of a file in O(1)
- they let you efficiently do "annotate"
- they let you do smarter merge

At least the first four seem fairly critical to me.

As various people have pointed out, you can hack delta transmission
and file revision indexing on top of git. But to do that, you'll need
to build the same indices that Mercurial has. And you'll need to check
their integrity.

Unfortunately, since the git back-end refuses to know anything about
the relation between file revisions, this will all happen in the front
end, and you'll have done almost all the work needed to do delta
storage without actually getting it. How sad.

You'll also likely end up with something quite a bit more complicated
than Mercurial because of the extra layering. This all strongly suggests
to me that the git back-end is just a little bit too simple.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Linus Torvalds]

On Mon, 2 May 2005, Matt Mackall wrote:
> 
> Umm.. I am _not_ calculating the SHA of the delta itself. That'd be
> silly.

It's not silly.

Meta-data consistency is supremely important. If people can corrupt their 
metadata in strange an unobservable ways, that's almost as bad as 
corrupting the data itself. In fact, to some degree it's worse, since you 
make people trust the thing, but you don't actually guarantee it.

So how _do_ you guarantee consistency of a tree and the history that led 
up to it? 

And by that I don't mean any of the individual blobs - I realize that it's 
perfectly valid to just check out every single version, and have the sha1 
of that. But how do you guarantee that the sha's you check are the sha's 
that you saved in the first place, and somebody didn't replace something 
in the middle?

In other words, you need to hash the metadata too. Otherwise how do you
consistency-check the _collection_ of files?

It's absolutely not enough to just protect single-file content. That 
doesn't help one whit. It's not what a SCM is all about. You have to 
protect the state of _multiple_ files, ie the metadata has to be 
verifiable too.

If that meta-data is the index, then the index needs to be protected by a
SHA1. In git, that's why we don't just sha1 every blob, but every tree and
every commit. That's the thing that gets consistency _beyond_ a single
file.

> As various people have pointed out, you can hack delta transmission
> and file revision indexing on top of git. But to do that, you'll need
> to build the same indices that Mercurial has. And you'll need to check
> their integrity.

No, absolutely not.

Building indeces on top of git would be stupid. You can _cache_ deltas,
but there's a big difference between a index that actually describes how
random blobs go together, and a cache of a delta between two
well-specified end-points. And in particular, there is no "consistency" to
a delta. You don't need it.

Why? Because either the delta is correct, or it isn't. If it's correct,
the end result will be the right sha1. If it's not, the end result will be
something else. So when you do a "pull" from another repository, you can
trivially check whether the delta's you got were valid: did applying them
result in the same sha1 that the other repository had?

So git really validates the _only_ thing that matters: it validates the 
state of the data. It doesn't validate anything else, but if validates 
that one thing very completely indeed.

		Linus

Re: Mercurial 0.4b vs git patchbomb benchmark

[Matt Mackall]

On Mon, May 02, 2005 at 07:48:29PM -0700, Linus Torvalds wrote:
> 
> 
> On Mon, 2 May 2005, Matt Mackall wrote:
> > 
> > Umm.. I am _not_ calculating the SHA of the delta itself. That'd be
> > silly.
> 
> It's not silly.

The delta is not the object I care about and its representation is
arbitrary. In fact different branches will store different deltas
depending on how their DAGs get topologically sorted. The object I
care about is the original text, so that's the hash I store.

> In other words, you need to hash the metadata too. Otherwise how do you
> consistency-check the _collection_ of files?

Well naturally, I hash the metadata too. For every change, there's a
toplevel changeset hash that is the hash of the entire project state
at that time. And it's all signable and so on. Just like git and just
like Monotone.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Linus Torvalds]

On Mon, 2 May 2005, Matt Mackall wrote:
> 
> The delta is not the object I care about and its representation is
> arbitrary. In fact different branches will store different deltas
> depending on how their DAGs get topologically sorted. The object I
> care about is the original text, so that's the hash I store.

Ok. In that case, it sounds like you're really doing everything git is
doing, except your "blob" objects effectively can have pointers to a
previous object (and you have a different on-disk representation)?  Is
that correct?

			Linus

Re: Mercurial 0.4b vs git patchbomb benchmark

[Linus Torvalds]

On Mon, 2 May 2005, Matt Mackall wrote:
> 
> It's still simple in Mercurial, but more importantly Mercurial _won't
> need it_. Dropping history is a work-around, not a feature.

Side note: this is what Larry thought about BK too. Until three years had
passed, and the ChangeSet file was many megabytes in size. Even slow
growth ends up being big growth in the end..

We had been talking about pruning the BK history as long back as a year 
ago.

		Linus

Re: Mercurial 0.4b vs git patchbomb benchmark

[Matt Mackall]

On Mon, May 02, 2005 at 09:24:54PM -0700, Linus Torvalds wrote:
> 
> 
> On Mon, 2 May 2005, Matt Mackall wrote:
> > 
> > It's still simple in Mercurial, but more importantly Mercurial _won't
> > need it_. Dropping history is a work-around, not a feature.
> 
> Side note: this is what Larry thought about BK too. Until three years had
> passed, and the ChangeSet file was many megabytes in size. Even slow
> growth ends up being big growth in the end..
> 
> We had been talking about pruning the BK history as long back as a year 
> ago.

Ok, I'll implement it on my red eye flight tonight. But Mercurial
won't suffer from the O(filesize) problem of BK.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Chris Wedgwood]

On Mon, May 02, 2005 at 09:24:54PM -0700, Linus Torvalds wrote:

> We had been talking about pruning the BK history as long back as a
> year ago.

Was that the history or all the deletes/renames that were painful
though?

Re: Mercurial 0.4b vs git patchbomb benchmark

[Tom Lord]

  > ie does mercurial do distributed merges, which git was designed for, and 
  > does mercurial notice single-bit errors in a reasonably secure manner, or 
  > can people just mess with history willy-nilly?

  > For the latter, the cryptographic nature of sha1 is an added bonus - the
  > _big_ issue is that it is a good hash, and an _exteremely_ effective CRC
  > of the data. You can't mess up an archive and lie about it later.

On the other hand, you're asking people to sign whole trees and not just at
first-import time but also for every change.

That's an impedence mismatch and undermines the security features of the
approach you're taking and here is why:

I shouldn't sign anything I haven't reviewed pretty carefully.  For
the kernel and in many other situations, it is too expensive to review
the whole tree.  Thus, the thing actually signed and the thing meant
by the signature are not equal.  I sign a tree, in this system,
because I think the right diffs and only the right diffs have been
applied to it.   My signature is intended to mean, though, that I vouche
for the *diffs*, not the tree.

If I've changed five files, I should be signing a statement of:

	1) my belief about the identity of the immediate ancestor tree
	2) a robust summary of my changes, sufficient to recreate my
	   new tree given a faithful copy of the ancestor

That's a short enough amount of data that a human can really review it
and thus it makes the signatures much more meaningful.

Probably doesn't matter much other than in cases where a mainline
is undergoing massive batch-patching based mostly on a web of trust.

But in that case --- someone or something generates purported diffs of
a tree; someone or something else scans those diffs and decides they
look good ---- and then on this basis, something distinct from
directly using those diffs occurs.  The diffs were used to vette the
change; the signature asserts that a certain tree is a faithful result
of applying those diffs.  Nothing checks that second assertion -- it's
taken on faith.

-t

Re: Mercurial 0.4b vs git patchbomb benchmark

[Linus Torvalds]

On Fri, 29 Apr 2005, Tom Lord wrote:
> 
> On the other hand, you're asking people to sign whole trees and not just at
> first-import time but also for every change.

I don't agree.

Sure, the commit determins the whole tree end result, but if you want to 
sign the _tree_, you can do so: just tag the actual _tree_ object as "this 
tree has been verified to be bug-free and non-baby-seal-clubbing".

But that's not what people do with tags. They sign a _commit_ object. And
yes, the commit object points to the tree, but it also points to the whole
history of other commit objects (and thus all historical trees etc), and 
together with just common sense it is very obvious that what you're really 
signing is that "point in time".

If you want to clarify it, you can always just say so in the tag. Instead 
of saying "I tag this as something I have verified every byte of", you can 
say "this was what I released as xxx", or "this commit contains my change" 
or something.

> If I've changed five files, I should be signing a statement of:
> 
> 	1) my belief about the identity of the immediate ancestor tree
> 	2) a robust summary of my changes, sufficient to recreate my
> 	   new tree given a faithful copy of the ancestor

So _do_ exactly that. You can say that in the tag you're signing.

			Linus

Re: Mercurial 0.4b vs git patchbomb benchmark

[Tom Lord]

   From: Linus Torvalds <torvalds@osdl.org>

   On Fri, 29 Apr 2005, Tom Lord wrote:
   > 
   > On the other hand, you're asking people to sign whole trees and not
   > just at first-import time but also for every change.

   I don't agree.

Let's be more precise, then.

   Sure, the commit determins the whole tree end result, but if you want to 
   sign the _tree_, you can do so: just tag the actual _tree_ object as "this 
   tree has been verified to be bug-free and non-baby-seal-clubbing".

   But that's not what people do with tags. They sign a _commit_ object. And
   yes, the commit object points to the tree, but it also points to the whole
   history of other commit objects (and thus all historical trees etc), and 
   together with just common sense it is very obvious that what you're really 
   signing is that "point in time".

   If you want to clarify it, you can always just say so in the tag. Instead 
   of saying "I tag this as something I have verified every byte of", you can 
   say "this was what I released as xxx", or "this commit contains my change" 
   or something.


A programmer publishing a change to the kernel has three pieces of 
data in play.  They are:
nn
	1) the ancestry of their modified tree

	2) the complete contents of their modified tree

	3) input data for a patching program (let's call it "PATCH")
	   which, at the very least, satisfies the equation:

		MOD_TREE = PATCH (this_diff, ORIG_TREE)


An upstream consumer, most often, is (should be) using (1) and (3).
In your system, the upstream consumer is given (1) and (2) and must
compute (3) for themselves.   The upstream consumer can also be provided
a signed version of (3) but if clients are mostly relying on the (2)
then there are multiple vulnerabilities there.

The set of pairs of type (1) and (2) is a dual space to the set of
pairs of type (1) and (3).   In that sense, it makes no mathematical
difference whether the programmer signs a {(1),(3)} pair or a {(1),(2)}
pair since either way, the other pair can be trivially derived.

On the other hand, signing documents which represent a {(1),(3)} pair
with robust accuracy is, in most cases, much much less expensive than
signing {(1),(2)} pairs with robust accuracy.  This is a bit like the
difference between "*I* didn't set loose any mice in the house" vs. "I
have searched every corner of the house and swear there are no mice
here."

Another way to say that is that if someone gives me a signed {(1),(3)} pair
I am likely to be much more confident that the signature represents
an in-depth endorsement of the content as opposed to "here is what the 
tools on my system happened to generate -- I hope it's what I meant".


   > If I've changed five files, I should be signing a statement of:
   > 
   > 	1) my belief about the identity of the immediate ancestor tree
   > 	2) a robust summary of my changes, sufficient to recreate my
   > 	   new tree given a faithful copy of the ancestor

   So _do_ exactly that. You can say that in the tag you're signing.

Which is pretty much exactly what Arch does except that, in the case
of Arch, the signed diff is actually used directly to produce the mod
tree.   There isn't a step in the process where a programmer reads
a purported diff, assumes that the signed tree accurately reflects
that diff, and then merges against the signed tree rather than the
diff.

The Arch approach also has the win that the signed diffs are useful
even in the absense of the ORIG_TREE.  In the Arch world, we use this
for the form of selective merging that we call "cherry-picking" (picking
the desired changes from somebody else's line of development while 
skipping those which are not desired -- yet still being able to proceed
with bidirectional merging in a simple way).

The Arch approach also has the win that it amounts to delta-compression,
simplifying the design of efficient transports and helping to tame
I/O bandwidth costs in the local case.   A lot of good features simply
"fall out" of this approach.

This is kind of a yin-yang thing.  It's also valuable, in my view, to
sign {(1),(2)} pairs.  It's also (in a more obscure way) valuable to
sign {(1),(2),(3)} triples, especially if clients are regularly validating
them by making sure the triple describes a true diff application.
So one ultimately wants both functionalities, really.

Signing trees which are really defined by a diff is a handy checksum
on the accuracy of tools which people are using but it isn't a substitute
for signing the diff itself and using it as the primary definition of 
the tree it generates when combined with the immediate ancestor(s).

Signing trees is also handy when that signature is then further linked
to a set of binaries.

Signing trees also is easier to implement and so gets git off the ground
faster.

But there's more to do, if a serious system is desired.

-t

Re: Mercurial 0.4b vs git patchbomb benchmark

[Linus Torvalds]

On Fri, 29 Apr 2005, Tom Lord wrote:
>
> 	1) the ancestry of their modified tree
> 
> 	2) the complete contents of their modified tree
> 
> 	3) input data for a patching program (let's call it "PATCH")
> 	   which, at the very least, satisfies the equation:
> 
> 		MOD_TREE = PATCH (this_diff, ORIG_TREE)
> 
> On the other hand, signing documents which represent a {(1),(3)} pair
> with robust accuracy is, in most cases, much much less expensive than
> signing {(1),(2)} pairs with robust accuracy. 

Not so.

It may be less expensive in your world, but that's the whole point of git: 
it's _not_ less expensive in the git world. 

In the git world, 1 and 2 aren't even separate things. They go together. 
And you just sign it. End of story. It's so cheap to sign that it's not 
even funny.

More importantly, signing 3 is meaningless. 3 only makes sense with a 
known starting point. You should never sign a patch without also saying 
what you're patching. 

And once you do that, 1+2 and 1+3 are _exactly_ the same thing.

And since git always works on the 1+2 level, it would be inexcusably
stupid to sign anything but that. 3 doesn't even exist per se, although 
it's obviously fully defined by 1+2.

So I don't see your point. You complain about git signing, but you 
complain on grounds that do not _exist_ in git, and then your alternative 
(1+3) which is senseless in a git world doesn't actually end up being 
anything really different - just more expensive.

		Linus

Re: Mercurial 0.4b vs git patchbomb benchmark

[Tom Lord]

   From: Linus Torvalds <torvalds@osdl.org>

   On Fri, 29 Apr 2005, Tom Lord wrote:
   >
   > 	1) the ancestry of their modified tree
   > 
   > 	2) the complete contents of their modified tree
   > 
   > 	3) input data for a patching program (let's call it "PATCH")
   > 	   which, at the very least, satisfies the equation:
   > 
   > 		MOD_TREE = PATCH (this_diff, ORIG_TREE)
   > 
   > On the other hand, signing documents which represent a {(1),(3)} pair
   > with robust accuracy is, in most cases, much much less expensive than
   > signing {(1),(2)} pairs with robust accuracy. 

   Not so.

   It may be less expensive in your world, but that's the whole point of git: 
   it's _not_ less expensive in the git world. 

   In the git world, 1 and 2 aren't even separate things. They go together. 
   And you just sign it. End of story. It's so cheap to sign that it's not 
   even funny.

The confusion here is that you are talking about computational complexity
while I am talking about complexity measured in hours of labor.

You are assuming that the programmer generating the signature blindly 
trusts the tool to generate the signed document accurately.   I am 
saying that it should be tractable for human beings to read the documents
they are going to sign.


   More importantly, signing 3 is meaningless. 3 only makes sense with a 
   known starting point. You should never sign a patch without also saying 
   what you're patching. 

I advocated signing a {(1),(3)} pair, not simply (3).

   And once you do that, 1+2 and 1+3 are _exactly_ the same thing.

I already spoke to that.

   And since git always works on the 1+2 level, it would be inexcusably
   stupid to sign anything but that. 3 doesn't even exist per se, although 
   it's obviously fully defined by 1+2.

   So I don't see your point. You complain about git signing, but you 
   complain on grounds that do not _exist_ in git, and then your alternative 
   (1+3) which is senseless in a git world doesn't actually end up being 
   anything really different - just more expensive.

I'm not sure what to suggest other than go back and read more carefully.

-t

Re: Mercurial 0.4b vs git patchbomb benchmark

[Sean]

On Fri, April 29, 2005 2:08 pm, Tom Lord said:

> The confusion here is that you are talking about computational complexity
> while I am talking about complexity measured in hours of labor.
>
> You are assuming that the programmer generating the signature blindly
> trusts the tool to generate the signed document accurately.   I am
> saying that it should be tractable for human beings to read the documents
> they are going to sign.


Developers obviously _do_ read the changes they submit to a project or
they would lose their trusted status.  That has absolutely nothing to do
with signing, it's the exact same way things work today, without sigs.

It's not "blind trust" to expect a script to reproducibly sign documents
you've decided to submit to a project.  The signature is not a QUALITY
guarantee in and of itself.  It doesn't mean you have any additional
responsibility to remove all bugs before submitting.  Conversely, not
signing something doesn't mean you can submit crap.

See?  Signing something does not change the quality guarantee one way or
the other.  It does not put any additional demands on the developer, so
it's fine to have an automated script do it.  It's just a way to avoid
impersonations.

Sean

Re: Mercurial 0.4b vs git patchbomb benchmark

[Tom Lord]

   From: "Sean" <seanlkml@sympatico.ca>

   On Fri, April 29, 2005 2:08 pm, Tom Lord said:

   > The confusion here is that you are talking about computational complexity
   > while I am talking about complexity measured in hours of labor.
   >
   > You are assuming that the programmer generating the signature blindly
   > trusts the tool to generate the signed document accurately.   I am
   > saying that it should be tractable for human beings to read the documents
   > they are going to sign.


   Developers obviously _do_ read the changes they submit to a project or
   they would lose their trusted status.  That has absolutely nothing to do
   with signing, it's the exact same way things work today, without sigs.

Nobody that I know is endorsing "the way things work today" as especially
robust.  Lots of people endorse it as successful in the marketplace and has
having not failed horribly yet -- but that's not the same thing.


   It's not "blind trust" to expect a script to reproducibly sign documents
   you've decided to submit to a project.

It *is* blind trust to assume without further guarantees that the diff
someone sends you (signed or not) describes a tree accurately unless
the tree in question is created by a local application of that diff.

In essense, `git' (today) wants *me* to trust that *you* have
correctly applied that diff -- evidently in order to speed things up.
It makes remote users "patch servers", for no good reason.

Triple signatures, signing both the name of the ancestor, the diff,
and the resulting tree are the most robust because I can apply the
diff to the ancestor and then *verify* that it matches the signed
tree.   But systems should neither ask users to sign something too large
to read nor rely on signatures of things too large to read.


   The signature is not a QUALITY
   guarantee in and of itself.

Which has nothing to do with any of this except indirectly.

   See?  Signing something does not change the quality guarantee one way or
   the other.  It does not put any additional demands on the developer, so
   it's fine to have an automated script do it.  It's just a way to avoid
   impersonations.

The process should not rely on the security of every developer's
machine.  The process should not rely on simply trusting quality
contributors by reputation (e.g., most cons begin by establishing
trust and continue by relying inappropriately on
trust-without-verification).  This relates to why Linus'
self-advertised process should be raising yellow and red cards all
over the place: either he is wasting a huge amount of his own time and
should be largely replaced by an automated patch queue manager, or he
is being trusted to do more than is humanly possible.

-t

Re: Mercurial 0.4b vs git patchbomb benchmark

[Sean]

On Fri, April 29, 2005 2:54 pm, Tom Lord said:

> The process should not rely on the security of every developer's
> machine.  The process should not rely on simply trusting quality
> contributors by reputation (e.g., most cons begin by establishing
> trust and continue by relying inappropriately on
> trust-without-verification).  This relates to why Linus'
> self-advertised process should be raising yellow and red cards all
> over the place: either he is wasting a huge amount of his own time and
> should be largely replaced by an automated patch queue manager, or he
> is being trusted to do more than is humanly possible.
>

Ahh, you don't believe in the development model that has produced Linux! 
Personally I do believe in it, so much so that I question the value of
signatures at the changeset level.  To me it doesn't matter where the code
came from just so long as it works.   Signatures are just a way to
increase the comfort level that the code has passed through a number of
people who have shown themselves to be relatively good auditors.  That's
why I trust the code from my distribution of choice.  Everything is out in
the open anyway so it's much harder for a con man to do his thing.

Sean

Re: Mercurial 0.4b vs git patchbomb benchmark

[Bill Davidsen]

Sean wrote:
> On Fri, April 29, 2005 2:54 pm, Tom Lord said:
> 
> 
>>The process should not rely on the security of every developer's
>>machine.  The process should not rely on simply trusting quality
>>contributors by reputation (e.g., most cons begin by establishing
>>trust and continue by relying inappropriately on
>>trust-without-verification).  This relates to why Linus'
>>self-advertised process should be raising yellow and red cards all
>>over the place: either he is wasting a huge amount of his own time and
>>should be largely replaced by an automated patch queue manager, or he
>>is being trusted to do more than is humanly possible.
>>
> 
> 
> Ahh, you don't believe in the development model that has produced Linux! 
> Personally I do believe in it, so much so that I question the value of
> signatures at the changeset level.  To me it doesn't matter where the code
> came from just so long as it works.

Lawyers must love you... That approach doesn't work in court.

Related: look at the new software patent law, it ignores the existing 
law, judge and jury, and lets MS avoid paying the judgement for a suit 
it already lost.

See Computerworld etc for details.

-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me

Re: Mercurial 0.4b vs git patchbomb benchmark

[Matt Mackall]

On Fri, Apr 29, 2005 at 07:34:15AM -0700, Linus Torvalds wrote:
> 
> 
> On Fri, 29 Apr 2005, Matt Mackall wrote:
> > 
> > Mercurial is even younger (Linus had a few days' head start, not to
> > mention a bunch of help), and it is already as fast as git, relatively
> > easy to use, much simpler, and much more space and bandwidth
> > efficient.
> 
> You've not mentioned two out of my three design goals:
>  - distribution
>  - reliability/trustability
> 
> ie does mercurial do distributed merges, which git was designed for, and 
> does mercurial notice single-bit errors in a reasonably secure manner, or 
> can people just mess with history willy-nilly?

Distribution: yes, it does BK/Monotone-style branching and merging.
In fact, these should be more "correct" than git as it has DAG
information at the file level in the case where there are multiple
ancestors at the changeset graph level:

M   M1   M2

AB
 |`-------v     M2 clones M
aB       AB     file A is change in mainline
 |`---v  AB'    file B is changed in M2
 |   aB / |     M1 clones M
 |   ab/  |     M1 changes B
 |   ab'  |     M1 merges from M2, changes to B conflict
 |    |  A'B'   M2 changes A
  `---+--.|
      |  a'B'   M2 merges from mainline, changes to A conflict
      `--.|
         ???    depending on which ancestor we choose, we will have
	        to redo A hand-merge, B hand-merge, or both
                but if we look at the files independently, everything
		is fine

> For the latter, the cryptographic nature of sha1 is an added bonus - the
> _big_ issue is that it is a good hash, and an _exteremely_ effective CRC
> of the data. You can't mess up an archive and lie about it later. And if
> you have random memory or filesystem corruption, it's not a "shit happens"  
> kind of situation - it's a "uhhoh, we can catch it (and hopefully even fix
> it, thanks to distribution)" thing.

Reliability/trustability: Mercurial is using a SHA1 hash as a checksum
as well, much like Monotone and git. A changeset contains a hash of a
manifest which contains a hash of each file in the project, so you can
do things like sign the manifest hash (though I haven't implemented it
yet. Making a backup is as simple as making a hardlink branch:

 mkdir backup
 cd backup
 hg branch ../linux  # takes about a second

> I had three design goals. "disk space" wasn't one of them, so you've
> concentrated on only one so far in your arguments.

That's because no one paid attention until I posted performance
numbers comparing it to git! Mercurial's goals are:

- to scale to the kernel development process
- to do clone/pull style development
- to be efficient in CPU, memory, bandwidth, and disk space
  for all the common SCM operations
- to have strong repo integrity

It's been doing all that quite nicely since its first release.
The UI is also pretty straightforward:

Setting up a Mercurial project:

 $ cd linux/
 $ hg init         # creates .hg
 $ hg status       # show changes between repo and working dir
 $ hg addremove    # add all unknown files and remove all missing files
 $ hg commit       # commit all changes, edit changelog entry

 Mercurial will look for a file named .hgignore in the root of your
 repository contains a set of regular expressions to ignore in file
 paths.

Mercurial commands:

 $ hg history          # show changesets
 $ hg log Makefile     # show commits per file
 $ hg diff             # generate a unidiff
 $ hg checkout         # check out the tip revision
 $ hg checkout <hash>  # check out a specified changeset
 $ hg add foo          # add a new file for the next commit
 $ hg remove bar       # mark a file as removed

Branching and merging:

 $ cd ..
 $ mkdir linux-work
 $ cd linux-work
 $ hg branch ../linux        # create a new branch
 $ hg checkout               # populate the working directory
 $ <make changes>
 $ hg commit
 $ cd ../linux
 $ hg merge ../linux-work    # pull changesets from linux-work

Importing patches:

 Fast:
 $ patch < ../p/foo.patch
 $ hg addremove
 $ hg commit

 Faster:
 $ patch < ../p/foo.patch
 $ hg commit `lsdiff -p1 ../p/foo.patch`

 Fastest:
 $ cat ../p/patchlist | xargs hg import -p1 -b ../p 

Network support:

 # export your .hg directory as a directory on your webserver
 foo$ ln -s .hg ~/public_html/hg-linux 

 # merge changes from a remote machine
 bar$ hg init                              # create an empty repo
 bar$ hg merge http://foo/~user/hg-linux   # populate it
 bar$ <do some work>
 bar$ hg merge http://foo/~user/hg-linux   # resync

 This is just a proof of concept of grabbing byte ranges, and is not
 expected to perform well.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Linus Torvalds]

On Fri, 29 Apr 2005, Matt Mackall wrote:
> 
> That's because no one paid attention until I posted performance
> numbers comparing it to git! Mercurial's goals are:
> 
> - to scale to the kernel development process
> - to do clone/pull style development
> - to be efficient in CPU, memory, bandwidth, and disk space
>   for all the common SCM operations
> - to have strong repo integrity

Ok, sounds good. Have you looked at how it scales over time, ie what 
happens with files that have a lot of delta's?

Let's see how these things work out..

		Linus

Re: Mercurial 0.4b vs git patchbomb benchmark

[Matt Mackall]

On Fri, Apr 29, 2005 at 10:09:38AM -0700, Linus Torvalds wrote:
> 
> 
> On Fri, 29 Apr 2005, Matt Mackall wrote:
> > 
> > That's because no one paid attention until I posted performance
> > numbers comparing it to git! Mercurial's goals are:
> > 
> > - to scale to the kernel development process
> > - to do clone/pull style development
> > - to be efficient in CPU, memory, bandwidth, and disk space
> >   for all the common SCM operations
> > - to have strong repo integrity
> 
> Ok, sounds good. Have you looked at how it scales over time, ie what 
> happens with files that have a lot of delta's?

I've done things like 10000 commits of a pair of revisions to printk.c
and it maintains consistently high speed and compression throughout that
range. I've also done things like commit all 500 revisions of
linux/Makefile from bkcvs. This took a couple seconds and resulted in
an 88k repo file (bkcvs takes 250k).

I haven't tried the whole kernel history corpus yet, but I've
committed all the 2.6 releases without any difficulties popping up and
I've had handling >1M total file revisions in my head since I sat down
to work on it. I'll maybe take a stab at a full history import next
week, if vacation doesn't interfere too much.

One downside Mercurial has is that long-lived repos can get fragmented on
disk. Things get defragmented to some extent as you go by doing COW on
files that are shared between local branches clones. Also a complete
defrag is a simple cp -a or equivalent, so I think this is not a big
deal.

Here's an excerpt from http://selenic.com/mercurial/notes.txt on how
the back-end works.

---

Revlogs:

The fundamental storage type in Mercurial is a "revlog". A revlog is
the set of all revisions to a file. Each revision is either stored
compressed in its entirety or as a compressed binary delta against the
previous version. The decision of when to store a full version is made
based on how much data would be needed to reconstruct the file. This
lets us ensure that we never need to read huge amounts of data to
reconstruct a file, regardless of how many revisions of it we store.

In fact, we should always be able to do it with a single read,
provided we know when and where to read. This is where the index comes
in. Each revlog has an index containing a special hash (nodeid) of the
text, hashes for its parents, and where and how much of the revlog
data we need to read to reconstruct it. Thus, with one read of the
index and one read of the data, we can reconstruct any version in time
proportional to the file size.

Similarly, revlogs and their indices are append-only. This means that
adding a new version is also O(1) seeks.

Generally revlogs are used to represent revisions of files, but they
also are used to represent manifests and changesets.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Linus Torvalds]

On Fri, 29 Apr 2005, Matt Mackall wrote:
> 
> Here's an excerpt from http://selenic.com/mercurial/notes.txt on how
> the back-end works.

Any notes on how you maintain repository-level information?

For example, the expense in BK wasn't the single-file history, it was the
_repository_ history, ie the "ChangeSet" file. Which grows quite slowly,
but because it _always_ grows, it ends up being quite big and expensive to
parse after three years.

Ie do you have the git kind of "independent trees/commits", or do you 
create a revision history of those too?

		Linus

Re: Mercurial 0.4b vs git patchbomb benchmark

[Matt Mackall]

On Fri, Apr 29, 2005 at 12:50:55PM -0700, Linus Torvalds wrote:
> 
> 
> On Fri, 29 Apr 2005, Matt Mackall wrote:
> > 
> > Here's an excerpt from http://selenic.com/mercurial/notes.txt on how
> > the back-end works.
> 
> Any notes on how you maintain repository-level information?
> 
> For example, the expense in BK wasn't the single-file history, it was the
> _repository_ history, ie the "ChangeSet" file. Which grows quite slowly,
> but because it _always_ grows, it ends up being quite big and expensive to
> parse after three years.
> 
> Ie do you have the git kind of "independent trees/commits", or do you 
> create a revision history of those too?

The changeset log (and everything else) has an external index. The
index is basically an array of (base, offset, length, parent1-hash,
parent2-hash, my-hash). This has everything you need to reconstruct a
given file revision with one seek/read into the data stream itself,
and also everything you need for doing graph merging.

This is small enough (68 bytes, currently) that the index for a
million changesets can be read into memory in a couple seconds or so,
even in Python. It can also be mmapped and random accessed since the
index entries are fixed-sized. (And it's already stored big-endian.)

So you never have to read all the data. You also never need more than
a few indices in memory at once. And you never have to rewrite the
data (it's all append-only), except to do a bulk copy when you break a
hardlink.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Linus Torvalds]

On Fri, 29 Apr 2005, Matt Mackall wrote:
> 
> The changeset log (and everything else) has an external index.

I don't actually know exactly how the BK changeset file works, but your 
explanation really sounds _very_ much like it.

I didn't want to do anything that even smelled of BK. Of course, part of
my reason for that is that I didn't feel comfortable with a delta model at
all (I wouldn't know where to start, and I hate how they always end up
having different rules for "delta"ble and "non-delta"ble objects).

But another was that exactly since I've been using BK for so long, I
wanted to make sure that my model just emulated the way I've been _using_
BK, rather than any BK technical details.

So it sounds like it could work fine, but it in fact sounds so much like 
the ChangeSet file that I'd personally not have done it that way. 

			Linus

Re: Mercurial 0.4b vs git patchbomb benchmark

[Matt Mackall]

On Fri, Apr 29, 2005 at 01:49:18PM -0700, Linus Torvalds wrote:
> 
> 
> On Fri, 29 Apr 2005, Matt Mackall wrote:
> > 
> > The changeset log (and everything else) has an external index.
> 
> I don't actually know exactly how the BK changeset file works, but your 
> explanation really sounds _very_ much like it.

I've never used BK, but I got the impression that it was all SCCS
under the covers, which means adding stuff and reconstructing random
versions is expensive (just as it is in CVS). The split between index
and data in Mercurial is intended to address that.
 
> I didn't want to do anything that even smelled of BK. Of course, part of
> my reason for that is that I didn't feel comfortable with a delta model at
> all (I wouldn't know where to start, and I hate how they always end up
> having different rules for "delta"ble and "non-delta"ble objects).

There aren't really any such rules here. While the index contains a
full DAG, the deltas are done opportunistically on a linearized
(topologically sorted) version of it. We try to make a delta against
the previous tip (regardless of whether or not it's the parent), and
if that is a win, we store it.

> So it sounds like it could work fine, but it in fact sounds so much like 
> the ChangeSet file that I'd personally not have done it that way. 

Well I originally set out to do it differently, but I decided my
current approach was the fastest route to something that actually
worked.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Bill Davidsen]

Linus Torvalds wrote:
> 
> On Fri, 29 Apr 2005, Matt Mackall wrote:
> 
>>Mercurial is even younger (Linus had a few days' head start, not to
>>mention a bunch of help), and it is already as fast as git, relatively
>>easy to use, much simpler, and much more space and bandwidth
>>efficient.
> 
> 
> You've not mentioned two out of my three design goals:
>  - distribution
>  - reliability/trustability
> 
> ie does mercurial do distributed merges, which git was designed for, and 
> does mercurial notice single-bit errors in a reasonably secure manner, or 
> can people just mess with history willy-nilly?
> 
> For the latter, the cryptographic nature of sha1 is an added bonus - the
> _big_ issue is that it is a good hash, and an _exteremely_ effective CRC
> of the data. You can't mess up an archive and lie about it later. And if
> you have random memory or filesystem corruption, it's not a "shit happens"  
> kind of situation - it's a "uhhoh, we can catch it (and hopefully even fix
> it, thanks to distribution)" thing.
> 
> I had three design goals. "disk space" wasn't one of them, so you've
> concentrated on only one so far in your arguments.

Reliability is a must have, but disk space matters in the real world if 
all other things are roughly equal. And bandwidth requirements are 
certainly another real issue if they result in significant delay.

Isn't the important thing  having the SCC reliable and easy to use, as 
in supports the things you want to do without jumping through hoops? One 
advantage of Mercurial is that it can be the only major project for 
someone who seems to understand the problems, as opposed to taking the 
time of someone (you) who has a load of other things in the fire. And if 
there isn't time to do all the things you want, perhaps generating a 
wisj list and stepping back would be a good thing.

If you have the energy and time to stay with git, I'm sure it will be 
great, but you might want to provide input on Mercurial and let it run.

PS: I don't think the performance difference is enough to constitute a 
real advantage in either direction.

-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me

Re: Mercurial 0.4b vs git patchbomb benchmark

[Andrea Arcangeli]

On Fri, Apr 29, 2005 at 02:40:31AM -0400, Sean wrote:
> There isn't anything preventing optomized transfer protocols for git. 

such a system might fall apart under load, converting on the fly from
git to network-optimized format sound quite expensive operation, even
ignorign the initial decompression of the payload. If something it
should be pre-converted to mercurial, so you checkout from mercurial and
you apply to local git.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Olivier Galibert]

On Fri, Apr 29, 2005 at 10:19:57PM +0200, Andrea Arcangeli wrote:
> such a system might fall apart under load, converting on the fly from
> git to network-optimized format sound quite expensive operation, even
> ignorign the initial decompression of the payload.

Nothing a little caching can't solve.  Given that git's objects are
immutable caching is especially easy to do, you can have the delta
reference indexes in the filename.

  OG.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Andrea Arcangeli]

On Sat, Apr 30, 2005 at 12:30:52AM +0200, Olivier Galibert wrote:
> Nothing a little caching can't solve.  Given that git's objects are
> immutable caching is especially easy to do, you can have the delta
> reference indexes in the filename.

Rather than creating delta reference indexes we can as well use
mercurial that uses them as primary storage.

git is the _storage_ filesystem, if we can't use it but we've to create
another different representation to do efficient network download, we
can as well the more efficient representation instead of git, that's
what mercurial does AFIK.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Andrea Arcangeli]

On Thu, Apr 28, 2005 at 11:01:57PM -0700, Matt Mackall wrote:
> change nodes so you've got to potentially traverse all the commits to
> reconstruct a file's history. That's gonna be O(top-level changes)
> seeks. This introduces a number of problems:
> 
> - no way to easily find previous revisions of a file
>   (being able to see when a particular change was introduced is a
>   pretty critical feature)
> - no way to do bandwidth-efficient delta transfer
> - no way to do efficient delta storage
> - no way to do merges based on the file's history[1]

And IMHO also no-way to implement a git-on-the-fly efficient network
protocol if tons of clients connects at the same time, it would be
dosable etc... At the very least such a system would require an huge
amount of ram. So I see the only efficient way to design a network
protocol for git not to use git, but to import the data into mercurial
and to implement the network protocol on top of mercurial.

The one downside is that git is sort of rock solid in the way it stores
data on disk, it makes rsync usage trivial too, the git fsck is reliable
and you can just sign the hash of the root of the tree and you sign
everything including file contents. And of course the checkin is
absolutely trivial and fast too.

With a more efficient diff-based storage like mercurial we'd be losing
those fsck properties etc.. but those reliability properties don't worth
the network and disk space they take IMHO, and the checkin time
shouldn't be substantially different (still running in O(1) when
appending at the head). And we could always store the hash of the
changeset, to give it some basic self-checking.

I give extreme value in a SCM in how efficiently it can represent the
whole tree for both network downloads and backups too. Being able to
store the whole history of 2.5 in < 100M is a very valuable feature
IMHO, much more valuable than to be able to sign the root.

Also don't get me wrong, I'm _very_ happy about git too, but I just
happen to prefer mercurial storage (I would never use git for anything
but the kernel, just like I wasn't using arch for similar reasons).

Re: Mercurial 0.4b vs git patchbomb benchmark

[Matt Mackall]

On Fri, Apr 29, 2005 at 10:30:27PM +0200, Andrea Arcangeli wrote:
> On Thu, Apr 28, 2005 at 11:01:57PM -0700, Matt Mackall wrote:
> > change nodes so you've got to potentially traverse all the commits to
> > reconstruct a file's history. That's gonna be O(top-level changes)
> > seeks. This introduces a number of problems:
> > 
> > - no way to easily find previous revisions of a file
> >   (being able to see when a particular change was introduced is a
> >   pretty critical feature)
> > - no way to do bandwidth-efficient delta transfer
> > - no way to do efficient delta storage
> > - no way to do merges based on the file's history[1]
> 
> And IMHO also no-way to implement a git-on-the-fly efficient network
> protocol if tons of clients connects at the same time, it would be
> dosable etc... At the very least such a system would require an huge
> amount of ram. So I see the only efficient way to design a network
> protocol for git not to use git, but to import the data into mercurial
> and to implement the network protocol on top of mercurial.
> 
> The one downside is that git is sort of rock solid in the way it stores
> data on disk, it makes rsync usage trivial too, the git fsck is reliable
> and you can just sign the hash of the root of the tree and you sign
> everything including file contents. And of course the checkin is
> absolutely trivial and fast too.

Mercurial is ammenable to rsync provided you devote a read-only
repository to it on the client side. In other words, you rsync from
kernel.org/mercurial/linus to local/linus and then you merge from
local/linus to your own branch. Mercurial's hashing hierarchy is
similar to git's (and Monotone's), so you can sign a single hash of
the tree as well.

> With a more efficient diff-based storage like mercurial we'd be losing
> those fsck properties etc.. but those reliability properties don't worth
> the network and disk space they take IMHO, and the checkin time
> shouldn't be substantially different (still running in O(1) when
> appending at the head). And we could always store the hash of the
> changeset, to give it some basic self-checking.

I think I can implement a decent repository check similar to git, it's
just not been a priority.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Andrea Arcangeli]

On Fri, Apr 29, 2005 at 01:39:59PM -0700, Matt Mackall wrote:
> Mercurial is ammenable to rsync provided you devote a read-only
> repository to it on the client side. In other words, you rsync from
> kernel.org/mercurial/linus to local/linus and then you merge from
> local/linus to your own branch. Mercurial's hashing hierarchy is
> similar to git's (and Monotone's), so you can sign a single hash of
> the tree as well.

Ok fine. It's also interesting how you already enabled partial transfers
through http.

Please apply this patch so it doesn't fail on my setup ;)

--- mercurial-0.4b/hg.~1~	2005-04-29 02:52:52.000000000 +0200
+++ mercurial-0.4b/hg	2005-04-30 00:53:02.000000000 +0200
@@ -1,4 +1,4 @@
-#!/usr/bin/python
+#!/usr/bin/env python
 #
 # mercurial - a minimal scalable distributed SCM
 # v0.4b "oedipa maas"

On a bit more technical side, one thing I'm wondering about is the
compression. If I change mercurial like this:

--- revlog.py.~1~	2005-04-29 01:33:14.000000000 +0200
+++ revlog.py	2005-04-30 03:54:12.000000000 +0200
@@ -11,9 +11,11 @@
 import zlib, struct, mdiff, sha, binascii, os, tempfile
 
 def compress(text):
+    return text
     return zlib.compress(text)
 
 def decompress(bin):
+    return text
     return zlib.decompress(bin)
 
 def hash(text):


the .hg directory sizes changes from 167M to 302M _BUT_ the _compressed_
size of the .hg directory (i.e. like in a full network transfer with
rsync -z or a tar.gz backup) changes from 55M to 38M:

andrea@opteron:~/devel/kernel> du -sm hg-orig hg-aa hg-orig.tar.bz2 hg-aa.tar.bz2 
167     hg-orig
302     hg-aa
55      hg-orig.tar.bz2
38      hg-aa.tar.bz2
^^^^^^^^^^^^^^^^^^^^^ 38M backup and network transfer is what I want

So I don't really see an huge benefit in compression, other than to
slowdown the checkins measurably [i.e. what Linus doesn't want] (the
time of compression is a lot higher than the time of python runtime during
checkin, so it's hard to believe your 100% boost with psyco in the hg file,
sometime psyco doesn't make any difference infact, I'd rather prefer people to
work on the real thing of generating native bytecode at compile time, rather
than at runtime, like some haskell compiler can do).

mercurial is already good at decreasing the entropy by using an efficient
storage format, it doesn't need to cheat by putting compression on each blob
that can only leads to bad ratios when doing backups and while transferring
more than one blob through the network.

So I suggest to try disabling compression optionally, perhaps it'll be even
faster than git in the initial checkin that way! No need of compressing or
decompressing anything with mercurial (unlike with git that would explode
without control w/o compression).

My time measurements follows:

w/o compression:

	9.52user 73.11system 1:30.49elapsed 91%CPU (0avgtext+0avgdata 0maxresident)k
	^
	0inputs+0outputs (0major+80109minor)pagefaults 0swaps

w/ compression (i.e. official package):

	26.78user 75.90system 1:44.87elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
	^^
	0inputs+0outputs (0major+484522minor)pagefaults 0swaps

The user time is by far the most important reliable number here, 17 seconds of
difference wasted in compression time. The 1:30 time w/o cache didn't fit
completely in cache, but still it was faster (only 14 sec faster instead of 17
sec faster due some minor I/O that happened due the larger pagecache size that
was recycled a bit).

Without compression the time is 90% system time, very little time is spent in
userland, and of course I made sure very little time is spent in I/O.  vmstat
looks like this:

 1  0 107008  61320  31964 546076    0    0     0  7860 1095  1147  5 46 41  9
 1  0 107008  59336  31972 547564    0    0     0     0 1074  1093  6 46 48  0
 1  0 107008  57544  31988 549044    0    0     0     0 1095  1239  5 45 50  0
 1  0 107008  55304  32000 550936    0    0     0     0 1064  1041  5 46 50  0
 1  0 107008  53384  32012 552488    0    0     0     0 1080  1081  5 45 50  0
 1  0 107008  51592  32032 553964    0    0     0  8260 1087  1018  3 48 40 10
 1  0 107008  49144  32040 555180    0    0     0     0 1099  1090  5 48 47  0
 1  0 107008  47432  32048 556532    0    0     0     0 1086  1014  4 46 50  0
 1  0 107008  45632  32060 557676    0    0     0     0 1102  1073  4 47 49  0
 2  0 107008  44032  32068 558892    0    0     0     0 1088  1044  4 46 49  0
 1  0 107008  42864  32116 560204    0    0     8  6672 1136  1265  5 47 41  7
 1  0 107008  41008  32124 561420    0    0     0   484 1182  1078  5 43 49  3

(5 = user, 43 system, 49 idle is the second cpu doing nothing, 3 is io-wait
time)

While with compression (default) the user time goes up, a lot higher than
what python wasted in the above trace:

 1  0 107008 282688  26756 346396    0    0     0 12064 1122   997 20 32 38 12
 1  0 107008 279936  26776 348552    0    0     0     0 1074   938 15 36 50  0
 1  0 107008 277296  26780 350656    0    0     0     0 1087  1070 15 36 50  0
 1  0 107008 274672  26796 352816    0    0     4    28 1060  1021 15 36 49  1
 1  0 107008 272176  26824 354828    0    0     0    52 1092  1082 19 32 50  0
 1  1 107008 269616  26844 356780    0    0     0 10856 1106  1019 16 36 36 13
 1  0 107008 267312  26864 358936    0    0     0     4 1081  1068 27 24 49  0
 1  0 107008 265072  26876 360760    0    0     0     0 1068  1073 23 27 50  0
 1  0 107008 263024  26888 362516    0    0     0  2764 1224  1457 18 29 49  5
 1  0 107008 260928  26900 364408    0    0     0    20 1060   969 21 29 50  0
 1  0 107008 258752  26928 366216    0    0     0  9768 1098   916 18 32 37 12
 1  0 107008 256640  26940 367972    0    0     0     0 1058  1093 13 37 50  0
 1  0 107008 254384  26952 369796    0    0     0     0 1089  1259 18 33 50  0
 1  0 107008 252016  26972 371680    0    0     0     0 1063  1040 29 22 50  0

The difference in time may be even higher than the above since the pass w/o
compression may have done some read I/O too sometime,  since I've 1G and
it didn't fit completely in cache (I made sure the second pass was completely
from cache instead, by running twice and verifying the free memory never went
lower than 100M).

Http is not intended for maximal efficiency, it's there just to make
life easy. special protocol with zlib is required for maximum
efficiency.

My suggestion is to leave compression optional by storing a bit in the .hg
directory (a global bit) to know if the blob is compressed or not... so if
people have problems and runs out of pagecache they can use it, but Linus
definitely must keep compression off to run the checkin at max speed (i.e.
potentially much faster than git, especially on big files). The cost of one
branch in python to know if compression is enabled or not shouldn't be an issue.
Compression should be a parameter to "hg init", perhaps hg -z, so in the future
we can add -j to add bzip2 too.

You also should move the .py into a hg directory, so that they won't
pollute the site-packages.

Matt, very great work with mercurial. The small mercurial size is striking, 1037
lines total excluding the classes you rightfully shared from other python
projects. That's less than 1/7 of the size of cogito (ok perhaps it's not as
mature as cogito but anyway). Great choice for the language too (but
perhaps I'm biased ;).

Re: Mercurial 0.4b vs git patchbomb benchmark

[Matt Mackall]

On Sat, Apr 30, 2005 at 04:52:11AM +0200, Andrea Arcangeli wrote:
> On Fri, Apr 29, 2005 at 01:39:59PM -0700, Matt Mackall wrote:
> > Mercurial is ammenable to rsync provided you devote a read-only
> > repository to it on the client side. In other words, you rsync from
> > kernel.org/mercurial/linus to local/linus and then you merge from
> > local/linus to your own branch. Mercurial's hashing hierarchy is
> > similar to git's (and Monotone's), so you can sign a single hash of
> > the tree as well.
> 
> Ok fine. It's also interesting how you already enabled partial transfers
> through http.
> 
> Please apply this patch so it doesn't fail on my setup ;)
> 
> --- mercurial-0.4b/hg.~1~	2005-04-29 02:52:52.000000000 +0200
> +++ mercurial-0.4b/hg	2005-04-30 00:53:02.000000000 +0200
> @@ -1,4 +1,4 @@
> -#!/usr/bin/python
> +#!/usr/bin/env python

Done.

> On a bit more technical side, one thing I'm wondering about is the
> compression. If I change mercurial like this:
> 
> --- revlog.py.~1~	2005-04-29 01:33:14.000000000 +0200
> +++ revlog.py	2005-04-30 03:54:12.000000000 +0200
> @@ -11,9 +11,11 @@
>  import zlib, struct, mdiff, sha, binascii, os, tempfile
>  
>  def compress(text):
> +    return text
>      return zlib.compress(text)
>  
>  def decompress(bin):
> +    return text
>      return zlib.decompress(bin)
>  
>  def hash(text):
> 
> 
> the .hg directory sizes changes from 167M to 302M _BUT_ the _compressed_
> size of the .hg directory (i.e. like in a full network transfer with
> rsync -z or a tar.gz backup) changes from 55M to 38M:
> 
> andrea@opteron:~/devel/kernel> du -sm hg-orig hg-aa hg-orig.tar.bz2 hg-aa.tar.bz2 
> 167     hg-orig
> 302     hg-aa
> 55      hg-orig.tar.bz2
> 38      hg-aa.tar.bz2
> ^^^^^^^^^^^^^^^^^^^^^ 38M backup and network transfer is what I want
> 
> So I don't really see an huge benefit in compression, other than to
> slowdown the checkins measurably [i.e. what Linus doesn't want] (the
> time of compression is a lot higher than the time of python runtime during
> checkin, so it's hard to believe your 100% boost with psyco in the hg file,
> sometime psyco doesn't make any difference infact, I'd rather prefer people to
> work on the real thing of generating native bytecode at compile time, rather
> than at runtime, like some haskell compiler can do).

Most of that psyco speed up is accelerating subsequent diffs in
difflib, which you probably didn't hit yet.

> mercurial is already good at decreasing the entropy by using an efficient
> storage format, it doesn't need to cheat by putting compression on each blob
> that can only leads to bad ratios when doing backups and while transferring
> more than one blob through the network.
> 
> So I suggest to try disabling compression optionally, perhaps it'll be even
> faster than git in the initial checkin that way! No need of compressing or
> decompressing anything with mercurial (unlike with git that would explode
> without control w/o compression).

I can make it some sort of environment variable, sure. I think the
speed is already in a domain where it's not a big deal though. There
are other things to do first, like unifying the merge/commit/update
code.

> Http is not intended for maximal efficiency, it's there just to make
> life easy. special protocol with zlib is required for maximum
> efficiency.

Yeah, I've got a plan here.

> You also should move the .py into a hg directory, so that they won't
> pollute the site-packages.

Yep, I'm rather new to actually packaging my Python hacks.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Andrea Arcangeli]

On Sat, Apr 30, 2005 at 08:20:15AM -0700, Matt Mackall wrote:
> Most of that psyco speed up is accelerating subsequent diffs in
> difflib, which you probably didn't hit yet.

Correct. Plus I've a 64bit python so I can't use psyco anyway.

> I can make it some sort of environment variable, sure. I think the
> speed is already in a domain where it's not a big deal though. There

No big deal of course, I mentioned it just because it was by far the
most CPU userland intensive operation during checkin. Perhaps doing less
vfs syscalls would improve checkin time too, but I'm unsure if that's
easily feasible (while disabling compression was certainly easy ;)

> Yep, I'm rather new to actually packaging my Python hacks.

I sent you by private email a modified package that gets that right.

Thanks!

Re: Mercurial 0.4b vs git patchbomb benchmark

[Bill Davidsen]

Andrea Arcangeli wrote:
> On Fri, Apr 29, 2005 at 01:39:59PM -0700, Matt Mackall wrote:
> 
>>Mercurial is ammenable to rsync provided you devote a read-only
>>repository to it on the client side. In other words, you rsync from
>>kernel.org/mercurial/linus to local/linus and then you merge from
>>local/linus to your own branch. Mercurial's hashing hierarchy is
>>similar to git's (and Monotone's), so you can sign a single hash of
>>the tree as well.
> 
> 
> Ok fine. It's also interesting how you already enabled partial transfers
> through http.
> 
> Please apply this patch so it doesn't fail on my setup ;)
> 
> --- mercurial-0.4b/hg.~1~	2005-04-29 02:52:52.000000000 +0200
> +++ mercurial-0.4b/hg	2005-04-30 00:53:02.000000000 +0200
> @@ -1,4 +1,4 @@
> -#!/usr/bin/python
> +#!/usr/bin/env python
>  #
>  # mercurial - a minimal scalable distributed SCM
>  # v0.4b "oedipa maas"

Could you explain why this is necessary or desirable? I looked at what 
env does, and I am missing the point of duplicating bash normal 
behaviour regarding definition of per-process environment entries.

-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me

Re: Mercurial 0.4b vs git patchbomb benchmark

[Valdis.Kletnieks]

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

On Mon, 02 May 2005 11:49:32 EDT, Bill Davidsen said:
> Andrea Arcangeli wrote:
> > On Fri, Apr 29, 2005 at 01:39:59PM -0700, Matt Mackall wrote:

> > -#!/usr/bin/python
> > +#!/usr/bin/env python
> >  #
> >  # mercurial - a minimal scalable distributed SCM
> >  # v0.4b "oedipa maas"
> 
> Could you explain why this is necessary or desirable? I looked at what 
> env does, and I am missing the point of duplicating bash normal 
> behaviour regarding definition of per-process environment entries.

Most likely, his python lives elsewhere than /usr/bin, and the 'env' call
results in causing a walk across $PATH to find it....

[-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --]

Re: Mercurial 0.4b vs git patchbomb benchmark

[Bill Davidsen]

Valdis.Kletnieks@vt.edu wrote:
> On Mon, 02 May 2005 11:49:32 EDT, Bill Davidsen said:
> 
>>Andrea Arcangeli wrote:
>>
>>>On Fri, Apr 29, 2005 at 01:39:59PM -0700, Matt Mackall wrote:
> 
> 
>>>-#!/usr/bin/python
>>>+#!/usr/bin/env python
>>> #
>>> # mercurial - a minimal scalable distributed SCM
>>> # v0.4b "oedipa maas"
>>
>>Could you explain why this is necessary or desirable? I looked at what 
>>env does, and I am missing the point of duplicating bash normal 
>>behaviour regarding definition of per-process environment entries.
> 
> 
> Most likely, his python lives elsewhere than /usr/bin, and the 'env' call
> results in causing a walk across $PATH to find it....

Assuming that he has env in a standard place... I hope this isn't going 
to start some rash of efforts to make packages run on non-standard 
toolchains, which add requirements for one tool to get around 
misplacement of another.

-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me

Re: Mercurial 0.4b vs git patchbomb benchmark (/usr/bin/env again)

[David A. Wheeler]

Valdis.Kletnieks@vt.edu wrote:
>> Most likely, his python lives elsewhere than /usr/bin, and the 'env' call
>> results in causing a walk across $PATH to find it....

Bill Davidsen wrote:
> Assuming that he has env in a standard place... I hope this isn't going 
> to start some rash of efforts to make packages run on non-standard 
> toolchains, which add requirements for one tool to get around 
> misplacement of another.

The #!/usr/bin/env prefix is, in my opinion, a very good idea.
There are a very few systems where env isn't in /usr/bin, but they
were extremely rare years ago & are essentially extinct now.
Basically, it's a 99% solution; getting the last 1% is really painful,
but since getting the 99% is easy, let's do it and be happy.

There are LOTS of systems where Python, bash, etc., do NOT
live in whatever place you think of as "standard".
I routinely use an OpenBSD 3.1 system; there is no /usr/bin/bash,
but there _IS_ a /usr/local/bin/bash (in my PATH) and a /usr/bin/env.
So this /usr/bin/env stuff REALLY is useful on a lot of systems, such
as OpenBSD.  It's critical to me, at least!

This is actually really useful on ANY system, though.
Even if some interpreter IS where you think it should be,
that is NOT necessarily the interpreter you want to use.
Using "/usr/bin/env" lets you use PATH
to override things, so you don't HAVE to use the interpreter
in some fixed location.  That's REALLY handy for testing... I
can download the whizbang Python 9.8.2, set it on the path,
and see if everything works as expected.  It's also nice
if someone insists on never upgrading a package; you can
install an interpreter "locally".  Yes, you can patch all the
files up, but resetting a PATH is _much_ easier.

--- David A. Wheeler

Re: Mercurial 0.4b vs git patchbomb benchmark

[Andrea Arcangeli]

On Mon, May 02, 2005 at 11:49:32AM -0400, Bill Davidsen wrote:
> Could you explain why this is necessary or desirable? I looked at what 

This is necessary here because of this:

andrea@opteron:~> which python
/home/andrea/bin/x86_64/python/bin/python

Of course I've /home/andrea/bin/x86_64/python/bin in the path before
/usr/bin.

The generally accepted way to start it is through env, other scripts in
mercurial were already getting that right too so it was probably not
intentional to hardcode it in the hg binary.

Re: Mercurial 0.4b vs git patchbomb benchmark

[Linus Torvalds]

On Mon, 2 May 2005, Bill Davidsen wrote:
> > -#!/usr/bin/python
> > +#!/usr/bin/env python

> Could you explain why this is necessary or desirable? I looked at what 
> env does, and I am missing the point of duplicating bash normal 
> behaviour regarding definition of per-process environment entries.

It's not about environment.

It's about the fact that many people have things like python in
/usr/local/bin/python, because they compiled it themselves or similar.

Pretty much the only path you can _really_ depend on for #! stuff is 
/bin/sh.

Any system that doesn't have /bin/sh is so fucked up that it's not worth
worrying about. Anything else can be in /bin, /usr/bin or /usr/local/bin
(and sometimes other strange places).

That said, I think the /usr/bin/env trick is stupid too. It may be more 
portable for various Linux distributions, but if you want _true_ 
portability, you use /bin/sh, and you do something like

	#!/bin/sh
	exec perl perlscript.pl "$@"

instead.
		Linus

Re: Mercurial 0.4b vs git patchbomb benchmark

[Daniel Jacobowitz]

On Mon, May 02, 2005 at 09:31:06AM -0700, Linus Torvalds wrote:
> It's not about environment.
> 
> It's about the fact that many people have things like python in
> /usr/local/bin/python, because they compiled it themselves or similar.
> 
> Pretty much the only path you can _really_ depend on for #! stuff is 
> /bin/sh.
> 
> Any system that doesn't have /bin/sh is so fucked up that it's not worth
> worrying about. Anything else can be in /bin, /usr/bin or /usr/local/bin
> (and sometimes other strange places).
> 
> That said, I think the /usr/bin/env trick is stupid too. It may be more 
> portable for various Linux distributions, but if you want _true_ 
> portability, you use /bin/sh, and you do something like
> 
> 	#!/bin/sh
> 	exec perl perlscript.pl "$@"
> 
> instead.

Do you know any vaguely Unix-like system where #!/usr/bin/env does not
work?  I don't; I've used it on Solaris, HP-UX, OSF/1...

-- 
Daniel Jacobowitz
CodeSourcery, LLC

Re: Mercurial 0.4b vs git patchbomb benchmark

[Linus Torvalds]

On Mon, 2 May 2005, Daniel Jacobowitz wrote:
> 
> Do you know any vaguely Unix-like system where #!/usr/bin/env does not
> work?  I don't; I've used it on Solaris, HP-UX, OSF/1...

I've used unixes where "#!" didn't work.

Things like bash still have support for such unixes, I think - you can
tell them to parse the #! line themselves, to make it appear to do the 
right thing.

Are these common? Hell no. But they definitely existed.

		Linus

Re: Mercurial 0.4b vs git patchbomb benchmark

[Sam Ravnborg]

On Mon, May 02, 2005 at 01:18:02PM -0400, Daniel Jacobowitz wrote:
> > 	#!/bin/sh
> > 	exec perl perlscript.pl "$@"
> > 
> > instead.
> 
> Do you know any vaguely Unix-like system where #!/usr/bin/env does not
> work?  I don't; I've used it on Solaris, HP-UX, OSF/1...

I had to pull out a call to env from kbuild due to strange errors in
some mandrake? based system.
I never tracked it down fully at that time, I just realised that two
different programs named env was present, and the less common one made
the linux kernel build fail. env was not called with any path in that
example so that may have cured it.

	Sam

Re: Mercurial 0.4b vs git patchbomb benchmark

[Ryan Anderson]

On Mon, May 02, 2005 at 09:31:06AM -0700, Linus Torvalds wrote:
> That said, I think the /usr/bin/env trick is stupid too. It may be more 
> portable for various Linux distributions, but if you want _true_ 
> portability, you use /bin/sh, and you do something like
> 
> 	#!/bin/sh
> 	exec perl perlscript.pl "$@"
		if 0;

You don't really want Perl to get itself into an exec loop.

-- 

Ryan Anderson
  sometimes Pug Majere

Re: Mercurial 0.4b vs git patchbomb benchmark

[Linus Torvalds]

On Mon, 2 May 2005, Ryan Anderson wrote:
>
> On Mon, May 02, 2005 at 09:31:06AM -0700, Linus Torvalds wrote:
> > That said, I think the /usr/bin/env trick is stupid too. It may be more 
> > portable for various Linux distributions, but if you want _true_ 
> > portability, you use /bin/sh, and you do something like
> > 
> > 	#!/bin/sh
> > 	exec perl perlscript.pl "$@"
> 		if 0;
> 
> You don't really want Perl to get itself into an exec loop.

This would _not_ be "perlscript.pl" itself. This is the shell-script, and 
it's not called ".pl".

In other words, you'd put this as ~/bin/cg-xxxx, and then "perlscript.pl" 
wouldn't be in the path at all, it would be in some separate install 
directory.

But hey, if people want to be safe for bad installations, add the extra 
line. Shell won't care ;)

		Linus

Re: Mercurial 0.4b vs git patchbomb benchmark

[Kyle Moffett]

On May 2, 2005, at 12:31:06, Linus Torvalds wrote:
> That said, I think the /usr/bin/env trick is stupid too. It may be  
> more
> portable for various Linux distributions, but if you want _true_
> portability, you use /bin/sh, and you do something like
>
>     #!/bin/sh
>     exec perl perlscript.pl "$@"

Oooh, I can one-up that hack with this evil from perlrun(1):

#!/bin/sh -- # -*- perl -*- -W -T
eval 'exec perl -wS $0 ${1+"$@"}'
     if 0;
# PERL SCRIPT HERE

Description:
Perl ignores the eval($string) because of the "if 0" in the  
statement. The
shell sees the statement end at the newline, and executes it faithfully.
The end result is that the preferred Perl gets the script.  I don't know
Python, so I don't know if such a trick exists there.

Cheers,
Kyle Moffett

-----BEGIN GEEK CODE BLOCK-----
Version: 3.12
GCM/CS/IT/U d- s++: a18 C++++>$ UB/L/X/*++++(+)>$ P+++(++++)>$
L++++(+++) E W++(+) N+++(++) o? K? w--- O? M++ V? PS+() PE+(-) Y+
PGP+++ t+(+++) 5 X R? tv-(--) b++++(++) DI+ D+ G e->++++$ h!*()>++$  
r  !y?(-)
------END GEEK CODE BLOCK------

Re: Mercurial 0.4b vs git patchbomb benchmark

[Bill Davidsen]

Linus Torvalds wrote:
> 
> On Mon, 2 May 2005, Bill Davidsen wrote:
> 
>>>-#!/usr/bin/python
>>>+#!/usr/bin/env python
> 
> 
>>Could you explain why this is necessary or desirable? I looked at what 
>>env does, and I am missing the point of duplicating bash normal 
>>behaviour regarding definition of per-process environment entries.
> 
> 
> It's not about environment.
> 
> It's about the fact that many people have things like python in
> /usr/local/bin/python, because they compiled it themselves or similar.
> 
> Pretty much the only path you can _really_ depend on for #! stuff is 
> /bin/sh.
> 
> Any system that doesn't have /bin/sh is so fucked up that it's not worth
> worrying about. Anything else can be in /bin, /usr/bin or /usr/local/bin
> (and sometimes other strange places).
> 
> That said, I think the /usr/bin/env trick is stupid too. It may be more 
> portable for various Linux distributions, but if you want _true_ 
> portability, you use /bin/sh, and you do something like
> 
> 	#!/bin/sh
> 	exec perl perlscript.pl "$@"
> 
> instead.
> 		Linus
> 
And that eliminates the need for having /usr/bin/env in the "expected" 
place. I like it.

Wish there was a way to specify "use path" without all this workaround.

-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me