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.
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
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
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"
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
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
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.
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?
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
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
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 [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
>
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
On 4/26/05, Chris Mason <[email protected]> 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
On Tuesday 26 April 2005 11:09, Magnus Damm wrote:
> On 4/26/05, Chris Mason <[email protected]> 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
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
On 4/26/05, Chris Mason <[email protected]> wrote:
> On Tuesday 26 April 2005 11:09, Magnus Damm wrote:
> > On 4/26/05, Chris Mason <[email protected]> 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
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
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
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
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
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
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 ([email protected])
"The secret to procrastination is to put things off until the
last possible moment - but no longer" -me
Magnus Damm <[email protected]> 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 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
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
Linus Torvalds <[email protected]> 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
Andrew Morton wrote:
> Linus Torvalds <[email protected]> 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
* Andrew Morton <[email protected]> wrote:
> Magnus Damm <[email protected]> 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
* 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.
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/
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
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
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
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);
}
Hello,
> Or you can LD_PRELOAD the attached quick hack....
nice one! I have to keep that around. :-)
Thanks,
Thomas
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
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
* 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.
* 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.
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
* 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.
Ingo Molnar wrote:
> * Andrew Morton <[email protected]> wrote:
>
>
>>Magnus Damm <[email protected]> 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 ([email protected])
"The secret to procrastination is to put things off until the
last possible moment - but no longer" -me
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
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
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.
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
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.
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
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
> 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
> 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
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
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.
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 ([email protected])
"The secret to procrastination is to put things off until the
last possible moment - but no longer" -me
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.
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
From: Linus Torvalds <[email protected]>
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
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
From: Linus Torvalds <[email protected]>
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
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
From: "Sean" <[email protected]>
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
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.
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
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
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.
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).
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.
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.
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
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.
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.
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.
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 ;).
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.
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!
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 ([email protected])
"The secret to procrastination is to put things off until the
last possible moment - but no longer" -me
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 ([email protected])
"The secret to procrastination is to put things off until the
last possible moment - but no longer" -me
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....
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 ([email protected])
"The secret to procrastination is to put things off until the
last possible moment - but no longer" -me
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.
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
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
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
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
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
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
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
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------
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
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.
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
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.
Linus Torvalds <[email protected]> wrote:
> 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;
exec may fail.
#!/bin/sh
exec perl -x $0 ${1+"$@"} || exit 127
#!perl
>> 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 this thread, it originally was.
--
"Our parents, worse than our grandparents, gave birth to us who are worse than
they, and we shall in our turn bear offspring still more evil."
-- Horace (BC 65-8)
On Tue, May 03, 2005 at 03:16:26AM +0200, Bodo Eggert <[email protected]> wrote:
> Linus Torvalds <[email protected]> wrote:
> > 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;
>
> exec may fail.
>
> #!/bin/sh
> exec perl -x $0 ${1+"$@"} || exit 127
> #!perl
>
> >> 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 this thread, it originally was.
In this thread, it was originally a Python script. In particular, one
aimed at managing the Linux kernel source. I'm going to use
/usr/bin/env, systems where that doesn't exist can edit the source.
--
Mathematics is the supreme nostalgia of our time.
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
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.
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
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
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.
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?
Matt Mackall wrote:
> On Tue, May 03, 2005 at 03:16:26AM +0200, Bodo Eggert <[email protected]> wrote:
>
>>Linus Torvalds <[email protected]> wrote:
>>
>>>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;
>>
>>exec may fail.
>>
>>#!/bin/sh
>>exec perl -x $0 ${1+"$@"} || exit 127
>>#!perl
>>
>>
>>>>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 this thread, it originally was.
>
>
> In this thread, it was originally a Python script. In particular, one
> aimed at managing the Linux kernel source. I'm going to use
> /usr/bin/env, systems where that doesn't exist can edit the source.
On the theory that my first post got lost, why use /usr/bin/env at all,
when bash already does that substitution? To support people who use
other shells?
ie.:
FOO=xx perl -e '$a=$ENV{FOO}; print "$a\n"'
--
-bill davidsen ([email protected])
"The secret to procrastination is to put things off until the
last possible moment - but no longer" -me
Bill Davidsen schrieb:
> On the theory that my first post got lost, why use /usr/bin/env at
> all, when bash already does that substitution? To support people who
> use other shells?
>
> ie.: FOO=xx perl -e '$a=$ENV{FOO}; print "$a\n"'
/usr/bin/env is used in scripts in the shebang line (the very first line
of the script, starting with "#!", which denotes the interpreter to use
for that script) to make a PATH search for the real interpreter.
Some folks keep their python (or Perl, or Bash etc.) in /usr/local/bin
or in $HOME, that's why this construct is needed at all.
Changing environment variables is not the goal, insofar this usage
exploits only a side-effect of env. It is portable in practice because
env is in /usr/bin on most modern systems.
So you could replace this first line of a bash script:
#!/usr/bin/env python
with this:
#!python
except that the latter doesn't work because you need to specify an
absolute path there. :]
Rene
[email protected] 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 ([email protected])
"The secret to procrastination is to put things off until the
last possible moment - but no longer" -me
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 ([email protected])
"The secret to procrastination is to put things off until the
last possible moment - but no longer" -me
[email protected] 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
Rene Scharfe wrote:
> Bill Davidsen schrieb:
>
>>On the theory that my first post got lost, why use /usr/bin/env at
>>all, when bash already does that substitution? To support people who
>>use other shells?
>>
>>ie.: FOO=xx perl -e '$a=$ENV{FOO}; print "$a\n"'
>
>
> /usr/bin/env is used in scripts in the shebang line (the very first line
> of the script, starting with "#!", which denotes the interpreter to use
> for that script) to make a PATH search for the real interpreter.
> Some folks keep their python (or Perl, or Bash etc.) in /usr/local/bin
> or in $HOME, that's why this construct is needed at all.
>
> Changing environment variables is not the goal, insofar this usage
> exploits only a side-effect of env. It is portable in practice because
> env is in /usr/bin on most modern systems.
>
> So you could replace this first line of a bash script:
>
> #!/usr/bin/env python
>
> with this:
>
> #!python
>
> except that the latter doesn't work because you need to specify an
> absolute path there. :]
Assuming that you want the PATH search rather than a symlink in
/usr/bin, of course. This opens the door to forgetting you just loaded
the CVS daily of python into your test directory and doing an unplanned
test of alpha software, but if people think the application should work
with non-standard tool chains, and realize it has possible unwanted
effects, that's a design decision.
--
-bill davidsen ([email protected])
"The secret to procrastination is to put things off until the
last possible moment - but no longer" -me