Re: cloning the kernel - why long time in "Resolving 313037 deltas"

quoted

quoted

quoted

quoted

"Nicolas" == Nicolas Pitre [off-list ref] writes:

Nicolas> Could you try the following please:

Nicolas> 	time git-index-pack -v -o /dev/null .git/objects/pack/*.pack

Nicolas> and provide us with the time it took (or an estimate if it is going to 
Nicolas> be on hour long)?

Nicolas> Performing the above on my kernel repository (after it was repacked into 
Nicolas> a single ~150MB pack) takes only 37 seconds.

I have a single pack.

"Indexing" took about 30 seconds.
"Resolving 313037 deltas" looks like it's going to take an hour.

So that *was* a local delay.

-- 
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
[off-list ref] <URL:http://www.stonehenge.com/merlyn/>
Perl/Unix/security consulting, Technical writing, Comedy, etc. etc.

Alex Riesen writes:
 > Marco Roeland, Tue, Dec 19, 2006 10:13:19 +0100:
 > > > Not that I personally frequently clone large projects on Mac OS X.
 > > > But new users to Git might.  :-)
 > > 
 > > And perhaps the Cygwin version might benefit too.
 > 
 > Does not work there at all. Even errno is not set (0).

Haven't seen a reply to this yet.

Upgrade cygwin.dll. The fix is pretty recent (1.5.22 or something).
Perhaps we now need a note in INSTALL.

Light testing seems to indicate that this change removes most of the
system times while leaving user time mostly unchanged (though I don't
know what cygwin time really reports in these categories). In the git
repository this is about 30% of the total time. For another (slightly
larger but with fewer objects) pack this still saves 20%. I haven't
compared it with the NO_MMAP version (too lazy), but overall it's a
win for cygwin as well (though we should note that cygwin's mmap seems
to have reasonable performance).

On Dec 18, 2006, at 18:02:07, Martin Langhoff wrote:

On 18 Dec 2006 14:26:36 -0800, Randal L. Schwartz  
[off-list ref] wrote:

quoted

Linus Torvalds wrote:

quoted

You're running this under OS X, aren't you? It's a pig of an OS,  
but "almost one hour" vs "25 seconds" is still unreasonable.

I agree!

Me too -- but entirely possible. Disk IO is specially painful on  
OSX.  Stat calls are horrid. Using Arch (which abused stat calls to  
no end) many ops would take 50x-100x longer on OSX than on Linux. A  
large unpacked repo with git is a real pain -- and packing it can  
take hours.

I've actually also seen filesystem operation latency double or triple  
if you start trying to do operations from multiple threads at once.   
Suddenly the already dog-slow single-CPU operations start bouncing  
caches and the Mac OS X mostly-whole-of-BSD-BKL across CPUs and it  
just crawls.  I can definitely see the local disk IO taking 100x  
longer than the network I/O, especially with an 8-megabit internet link.

Once you are packed it's sweet, but large repos are a pain to deal  
with. You won't impress anyone with performance over a linux kernel  
repo -- starting up gitk can take a long time. Stat-heavy stuff  
like git-diff is noticeably slower under OSX.

Just as an example, it takes my OS-X-running Quad-2.5GHz G5 ten times  
as long to do a "grep -rl foo linux/" as my Linux-running dual-1GHz  
G4 with 400MHz system bus.  This is disk-cache-hot too.  And that's  
not even a stat-heavy workload.  There's more than one reason I'm  
trying to make a Mac OS X ABI emulation layer on top of Linux :-D.

Cheers,
Kyle Moffett

Kyle Moffett [off-list ref] wrote:

Just as an example, it takes my OS-X-running Quad-2.5GHz G5 ten times  
as long to do a "grep -rl foo linux/" as my Linux-running dual-1GHz  
G4 with 400MHz system bus.  This is disk-cache-hot too.  And that's  
not even a stat-heavy workload.  There's more than one reason I'm  
trying to make a Mac OS X ABI emulation layer on top of Linux :-D.

Try 'git grep foo' instead; its very fast if you are working with
a fully packed Git repository.

Doesn't help any other application on Mac OS X however. :-(

-- 
Shawn.

On Thursday December 21st 2006 at 20:44 Kyle Moffett wrote:

I've actually also seen filesystem operation latency double or triple  
if you start trying to do operations from multiple threads at once.   
Suddenly the already dog-slow single-CPU operations start bouncing  
caches and the Mac OS X mostly-whole-of-BSD-BKL across CPUs and it  
just crawls.  I can definitely see the local disk IO taking 100x  
longer than the network I/O, especially with an 8-megabit internet link.

The mmap() implementation on Mac OS X ate 85% percent of system time on
the old version for git-index-pack. Of that time nearly all was spent on
some Mach locking function. So yes the BKL like locking inside the Mach
message passing seems to be the big culprit, perhaps Andy Tanenbaum can
explain this on LCA 2007. <ducks>

As most developers now run multicore CPU's we notice these differences
even better now! ;-)
-- 
Marco Roeland

Martin Langhoff wrote:

Once you are packed it's sweet, but large repos are a pain to deal
with. You won't impress anyone with performance over a linux kernel
repo -- starting up gitk can take a long time.

I'd suggest running qgit instead, and make sure you've run it once on 
the repo you're demoing. qgit has a nice little cache where it tucks 
away most of the data it uses, which makes it draw things a lot faster.

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231

On Mon, 18 Dec 2006, Randal L. Schwartz wrote:

quoted

quoted

quoted

quoted

quoted

"Nicolas" == Nicolas Pitre [off-list ref] writes:

Nicolas> Could you try the following please:

Nicolas> 	time git-index-pack -v -o /dev/null .git/objects/pack/*.pack

Nicolas> and provide us with the time it took (or an estimate if it is going to 
Nicolas> be on hour long)?

Nicolas> Performing the above on my kernel repository (after it was repacked into 
Nicolas> a single ~150MB pack) takes only 37 seconds.

I have a single pack.

"Indexing" took about 30 seconds.
"Resolving 313037 deltas" looks like it's going to take an hour.

So that *was* a local delay.

What CPU and amount of ram do you have?

Are you on Windows?

On Tuesday December 19th 2006 at 03:49 Shawn Pearce wrote:

[pread patch to speed up git-index-pack on Mac OS X]

More testing on Linux is probably needed, but if using pread()
on Linux is breakeven or slightly faster (as suggested by Johannes'
LilyPond test) this 60x performance improvement on initial clone
of largish projects on Mac OS X would be nice to have.

I see a decrease in total time (so an improvement in performance)
going from 37.3 to 35.2 seconds with the pread patch on Linux x86-64.
Note that both my testing on Linux and Mac OS X was done on dual core
processors (Athlon 3800+ XP on Linux and Intel Core 2 Duo 2.16GHz on an
iMac). Git is only single threaded and thus uses only core, but the
system can use the other core.

The minor page faults also decreased from 734866 to 370690. Nice.

Not that I personally frequently clone large projects on Mac OS X.
But new users to Git might.  :-)

And perhaps the Cygwin version might benefit too.
-- 

On Tuesday December 19th 2006 at 02:26 Shawn Pearce wrote:

[git-index-pack limping along on Mac OS X]

ActivityMonitor is showing that I'm spending 94% CPU in the kernel,
which is just insane.  Clearly Mac OS X's kernel cannot gracefully
handle what git-index-pack is currently doing.

A bit off topic but it might help people diagnose and test different
strategies.

The equivalent of "oprofile" on Mac OS X is a tool called "shark" from
Apple itself. It's very nice actually.

It's in the CHUD (Computer Hardware Understanding
Developer Tools) package. More information at
http://developer.apple.com/tools/performance and it is free as in beer.
;-)

Also the OpenSSL version on Mac OS X is rather old and compiled as
32-bit application. OpenSSL is one of the few userspace packages that
_really_ benefits tremendously from being compiled as 64-bit. It might
explain a bit of the enormous performance difference in this case. But
only profiling (perhaps with the help of "shark") will tell of course...

The kernel git repository isn't very handy on the Mac HFS+ filesystem,
due to it being case-insensitive, but I suppose it won't influence
git-index-pack.
-- 

On Mon, Dec 18, 2006 at 07:13:40PM -0500, Nicolas Pitre wrote:

Maybe.  However the mmap() may occur on section of the pack file which 
has just been written to in order to write even more, always to the same 
file.  On Linux this is fast because the mmap'd data is likely to still 
be in the cache.

I guess this could be turned into a malloc()/read()/free() with no 
trouble.

Actually, depending on the size of the chunk, even on Linux
malloc/read/free can be faster than the mmap/munmap, because
mmap/munmap calls involve page table manipulations, and even on Linux
that is often slower or dead even with the memory copy involved with
using malloc/read.  Even when reading huge chunks of Canon Raw File
data at a time, I found (experimentally) that it was no faster to use
mmap() compared to read().  And for small chunks of data, malloc/read
will definitely win out over mmap(), since the page table operations
and resulting page faults completely trump the cost of copying the
bytes from the page cache to the read() buffer.

Theodore Tso [off-list ref] wrote:

On Tue, Dec 19, 2006 at 01:39:30AM -0500, Shawn Pearce wrote:

quoted

This is why git-fast-import mmaps 128 MiB blocks from the file at
a time.  The mmap region is usually much larger than the file itself;
the application appends to the file via write() then goes back
and rereads data when necessary via the already established mmap.
Its rare for the application to need to unmap/remap a different block
so there really isn't very much page table manipulation overhead.

Yes, but unless you are using the (non-portable, Linux specific)
MAP_POPULATE flag to mmap, each time you touch a new page, you end up
taking a page fault; and so malloc/read/free might *still* be faster.
I'd encourage you to make the change and benchmark it; the results may
be surprising.  I played with this with dcraw, the Canon Raw File
converter a while back (before MAP_POPULATE was added), where I found
that with a linear access pattern, if you are reading the entire file,
it's stil marginally faster to use read() over mmap(), because with
dcraw taking a page fault every 4k of raw file, the system time was
significantly higher.

Interesting.  Lots of good reasons to probably just use pread()
in there instead of mmap.  For one thing git-fast-import doesn't
go back and hit the already written pack data very often. Its own
in memory caches usually perform very well.

-- 

Marco Roeland [off-list ref] wrote:

The kernel git repository isn't very handy on the Mac HFS+ filesystem,
due to it being case-insensitive, but I suppose it won't influence
git-index-pack.

Yea, I just play with it in packed format on this system.  :-)

-- 

On Tue, Dec 19, 2006 at 01:39:30AM -0500, Shawn Pearce wrote:

This is why git-fast-import mmaps 128 MiB blocks from the file at
a time.  The mmap region is usually much larger than the file itself;
the application appends to the file via write() then goes back
and rereads data when necessary via the already established mmap.
Its rare for the application to need to unmap/remap a different block
so there really isn't very much page table manipulation overhead.

Yes, but unless you are using the (non-portable, Linux specific)
MAP_POPULATE flag to mmap, each time you touch a new page, you end up
taking a page fault; and so malloc/read/free might *still* be faster.
I'd encourage you to make the change and benchmark it; the results may
be surprising.  I played with this with dcraw, the Canon Raw File
converter a while back (before MAP_POPULATE was added), where I found
that with a linear access pattern, if you are reading the entire file,
it's stil marginally faster to use read() over mmap(), because with
dcraw taking a page fault every 4k of raw file, the system time was
significantly higher.

So the main reason to use mamp, as Linus puts it, is if the management
overhead of needing to read lots of small bits of the file makes the
use of malloc/read to be a pain in the *ss, then go for it.  But don't
assume that you'll get better performance; in my experience, even on
the hyper-performant Linus kernel, mmap() in general only barely
breaks even with read().  On other systems, things are probably going
to be even worse.

Hi,

in a very unscientific test, without your patch local cloning of the 
LilyPond repo takes 1m33s (user), and with your patch (pread() instead of 
mmap()) it takes 1m13s (user). The real times are somewhat bogus, but 
still in favour of pread(), but only by 8 seconds instead of 20.

This is on Linux 2.4.32.

Ciao,
Dscho

Marco Roeland, Tue, Dec 19, 2006 10:13:19 +0100:

quoted

Not that I personally frequently clone large projects on Mac OS X.
But new users to Git might.  :-)

And perhaps the Cygwin version might benefit too.

Does not work there at all. Even errno is not set (0).

Marco Roeland [off-list ref] wrote:

On Tuesday December 19th 2006 at 03:32 Shawn Pearce wrote:

quoted

quoted

Anyway, try the pread() version first, see if that fixes the OS X problem.

It does.  Without pread() (aka stock 'next') it takes me over an
hour to index a pack of linux-2.6.  With pread() its 1m6s to run
index-pack on the same pack file.  The indexes are (of course)
identically produced.

I see the same here. From an (estimated) time of 37 minutes down to 52
seconds with the pread() patch. Running the profiler (shark) on the old
version showed that 85% of the time was spent in the Mac OS X mmap()
system call.

More testing on Linux is probably needed, but if using pread()
on Linux is breakeven or slightly faster (as suggested by Johannes'
LilyPond test) this 60x performance improvement on initial clone
of largish projects on Mac OS X would be nice to have.

Not that I personally frequently clone large projects on Mac OS X.
But new users to Git might.  :-)

-- 

On 18 Dec 2006 14:26:36 -0800, Randal L. Schwartz [off-list ref] wrote:

Linus> You're running this under OS X, aren't you? It's a pig of an OS, but
Linus> "almost one hour" vs "25 seconds" is still unreasonable.

I agree!

Me too -- but entirely possible. Disk IO is specially painful on OSX.
Stat calls are horrid. Using Arch (which abused stat calls to no end)
many ops would take 50x-100x longer on OSX than on Linux. A large
unpacked repo with git is a real pain -- and packing it can take
hours.

Once you are packed it's sweet, but large repos are a pain to deal
with. You won't impress anyone with performance over a linux kernel
repo -- starting up gitk can take a long time. Stat-heavy stuff like
git-diff is noticeably slower under OSX.

Have you got a linux partition you can boot into to get comparative timings?

[This is part of the reason I am migrating my OSX machine to Linux
fulltime, now that it seems that mergedfb+randr will let me switch to
dual monitors "hot".]

cheers,

quoted

quoted

quoted

quoted

"Nicolas" == Nicolas Pitre [off-list ref] writes:

quoted

"Indexing" took about 30 seconds.
"Resolving 313037 deltas" looks like it's going to take an hour.

So that *was* a local delay.

Nicolas> What CPU and amount of ram do you have?

2.2 Ghz Intel Core 2 Duo (Macbook Pro high end)
I can compile and install GNU Emacs from source in 11 minutes. :)

Nicolas> Are you on Windows?

Gawd no!

-- 
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
[off-list ref] <URL:http://www.stonehenge.com/merlyn/>
Perl/Unix/security consulting, Technical writing, Comedy, etc. etc.

On Mon, 18 Dec 2006, Randal L. Schwartz wrote:

I have a single pack.

"Indexing" took about 30 seconds.
"Resolving 313037 deltas" looks like it's going to take an hour.

So that *was* a local delay.

Ok, interesting. Two questions:

 - what does "top" say (is it CPU-bound? Is it perhaps blowing out your 
   disk cache? Is it swapping?)

 - do you have "oprofile" (or even just pgprof) to see where the *hell* 
   that time is spent, if it's actually CPU?

For me, it takes 25 seconds. Not an hour:

	[torvalds@woody linux]$ time git-index-pack -v -o /dev/null .git/objects/pack/*.pack
	Indexing 393507 objects.
	 100% (393507/393507) done
	Resolving 316071 deltas.
	 100% (316071/316071) done
	fatal: unable to create /dev/null: File exists
	
	real    0m24.619s
	user    0m22.569s
	sys     0m1.316s

(I admit that 25 seconds is already "too much", but it does actually end 
up exploding a lot of objects and doing quite a bit of work, so I guess 
it's fair).

And the process grew to 33MB in RSS at it's biggest, so it wasn't even 
using all that much memory (33MB isn't _tiny_, but considering that the 
pack in question is 155MB and has hundreds of thousands of objects, 33MB 
isn't really all that bad.

You're running this under OS X, aren't you? It's a pig of an OS, but 
"almost one hour" vs "25 seconds" is still unreasonable.

On Tue, 19 Dec 2006, Theodore Tso wrote:

So the main reason to use mamp, as Linus puts it, is if the management
overhead of needing to read lots of small bits of the file makes the
use of malloc/read to be a pain in the *ss, then go for it.

An example of this in git is the regular pack-file accesses. We're MUCH 
better off just mmap'ing the whole pack-file (or at least big chunks of 
it) and not having to maintain difficult structures of "this is where I 
read that part of the file into memory", or read _big_ chunks when 
quite often we just use a few kB of it.

So mmap for pack-files does make sense, but probably only when you can 
mmap big chunks, and are going to access much smaller (random) parts of 
it.

Theodore Tso [off-list ref] wrote:

On Mon, Dec 18, 2006 at 07:13:40PM -0500, Nicolas Pitre wrote:

quoted

Maybe.  However the mmap() may occur on section of the pack file which 
has just been written to in order to write even more, always to the same 
file.  On Linux this is fast because the mmap'd data is likely to still 
be in the cache.

I guess this could be turned into a malloc()/read()/free() with no 
trouble.

Actually, depending on the size of the chunk, even on Linux
malloc/read/free can be faster than the mmap/munmap, because
mmap/munmap calls involve page table manipulations, and even on Linux
that is often slower or dead even with the memory copy involved with
using malloc/read.  Even when reading huge chunks of Canon Raw File
data at a time, I found (experimentally) that it was no faster to use
mmap() compared to read().  And for small chunks of data, malloc/read
will definitely win out over mmap(), since the page table operations
and resulting page faults completely trump the cost of copying the
bytes from the page cache to the read() buffer.

This is why git-fast-import mmaps 128 MiB blocks from the file at
a time.  The mmap region is usually much larger than the file itself;
the application appends to the file via write() then goes back
and rereads data when necessary via the already established mmap.
Its rare for the application to need to unmap/remap a different block
so there really isn't very much page table manipulation overhead.

Why isn't git-index-pack doing the same?  Is there some hidden glitch
in some OS somewhere that has a problem with overmapping a file and
appending into it via write()?  I've done that on Mac OS X, Linux,
BSDi, Solaris...  never had a problem.

-- 

On Mon, 18 Dec 2006, Linus Torvalds wrote:

I've heard of other operations being slow on OS X - and two orders of 
magnitude really isn't unthinkable. I don't think people always seem to 
really understand how _good_ Linux is, and how much faster it can be. It's 
not just "Windows XP" sucks. Quite often it's literally "Linux is just 
damn fast".

Sadly, that causes problems when the main developers don't even see any 
issues, just because the Linux kernel environment makes things look really 
really cheap. Even when it isn't always cheap on other platforms.

Nico - have you looked at perhaps making the index-pack.c "mmap()" usage 
do chunking? Or just mmap the whole damn thing once? Linux is fast, but 
even Linux will be faster if you just mmap it once ;)

Maybe.  However the mmap() may occur on section of the pack file which 
has just been written to in order to write even more, always to the same 
file.  On Linux this is fast because the mmap'd data is likely to still 
be in the cache.

I guess this could be turned into a malloc()/read()/free() with no 
trouble.

quoted

quoted

quoted

quoted

"Linus" == Linus Torvalds [off-list ref] writes:

quoted

So that *was* a local delay.

Linus> Ok, interesting. Two questions:

Linus>  - what does "top" say (is it CPU-bound? Is it perhaps blowing out your 
Linus>    disk cache? Is it swapping?)

Not swapping, but CPU bound.

Linus>  - do you have "oprofile" (or even just pgprof) to see where the *hell* 
Linus>    that time is spent, if it's actually CPU?

I'm a "bear of very little brane" regarding code development on OSX.  I
can ask around to see if there's someway to profile this.

Linus> You're running this under OS X, aren't you? It's a pig of an OS, but 
Linus> "almost one hour" vs "25 seconds" is still unreasonable.

I agree!

-- 
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
[off-list ref] <URL:http://www.stonehenge.com/merlyn/>
Perl/Unix/security consulting, Technical writing, Comedy, etc. etc.

On Mon, 18 Dec 2006, Randal L. Schwartz wrote:

Nicolas> What CPU and amount of ram do you have?

2.2 Ghz Intel Core 2 Duo (Macbook Pro high end)
I can compile and install GNU Emacs from source in 11 minutes. :)

So it shouldn't be a lack of resource.

Nicolas> Are you on Windows?

Gawd no!

;-)

I asked because it could have had something with the mmap() usage 
recently reported to be dreadfully slow on Windows

Linus Torvalds [off-list ref] wrote:

On Tue, 19 Dec 2006, Shawn Pearce wrote:

quoted

Why isn't git-index-pack doing the same?  Is there some hidden glitch
in some OS somewhere that has a problem with overmapping a file and
appending into it via write()?  I've done that on Mac OS X, Linux,
BSDi, Solaris...  never had a problem.

It works on modern systems, but at least old HPUX versions had 
non-coherent mmap() and write(), and POSIX does not guarantee it. And if 
you ever want to port to Windows, I don't think you should do it.

Anyway, try the pread() version first, see if that fixes the OS X problem.

It does.  Without pread() (aka stock 'next') it takes me over an
hour to index a pack of linux-2.6.  With pread() its 1m6s to run
index-pack on the same pack file.  The indexes are (of course)
identically produced.

-- 

On Tuesday December 19th 2006 at 03:32 Shawn Pearce wrote:

quoted

Anyway, try the pread() version first, see if that fixes the OS X problem.

It does.  Without pread() (aka stock 'next') it takes me over an
hour to index a pack of linux-2.6.  With pread() its 1m6s to run
index-pack on the same pack file.  The indexes are (of course)
identically produced.

I see the same here. From an (estimated) time of 37 minutes down to 52
seconds with the pread() patch. Running the profiler (shark) on the old
version showed that 85% of the time was spent in the Mac OS X mmap()
system call.
-- 

Linus Torvalds [off-list ref] wrote:

On Tue, 19 Dec 2006, Shawn Pearce wrote:

quoted

Why isn't git-index-pack doing the same?  Is there some hidden glitch
in some OS somewhere that has a problem with overmapping a file and
appending into it via write()?  I've done that on Mac OS X, Linux,
BSDi, Solaris...  never had a problem.

It works on modern systems, but at least old HPUX versions had 
non-coherent mmap() and write(), and POSIX does not guarantee it. And if 
you ever want to port to Windows, I don't think you should do it.

Anyway, try the pread() version first, see if that fixes the OS X problem.

I'll give your pread() version a shot.

But right now I'm in the middle of cloning your linux-2.6 git
repository.

It is done downloading the pack and my system is pegged at 100%
CPU while resolving deltas.

ActivityMonitor is showing that I'm spending 94% CPU in the kernel,
which is just insane.  Clearly Mac OS X's kernel cannot gracefully
handle what git-index-pack is currently doing.

-- 

On Mon, 18 Dec 2006, Randal L. Schwartz wrote:

Linus> You're running this under OS X, aren't you? It's a pig of an OS, but 
Linus> "almost one hour" vs "25 seconds" is still unreasonable.

I agree!

The only thing that comes to mind is

 - some actual difference in how the pack looks. Although I don't really 
   see that. I re-pack both my own private kernel repos and the kernel.org 
   one fairly often, and usually with a pretty recent git. I don't think 
   any of the packing heuristics have changed in a long time. And I just 
   checked: the kernel.org pack-file (the big one) unpacks quickly too.

 - SHA1 library differences. Maybe OpenSSL on OS X sucks? I still don't 
   see the difference being _that_ big, but whatever..

 - OS X "mmap()" performance really really sucks.

   We do end up doing a _log_ of small mmaps in the "Resolving .." stage. 
   On Linux, the strace looks like

	write(2, "Resolving 316071 deltas.\n", 25) = 25
	mmap(NULL, 2619, PROT_READ, MAP_PRIVATE, 3, 0x4c000) = 0x2aaf13be2000
	munmap(0x2aaf13be2000, 2619)            = 0
	mmap(NULL, 2848, PROT_READ, MAP_PRIVATE, 3, 0x4c000) = 0x2aaf13be2000
	munmap(0x2aaf13be2000, 2848)            = 0
	mmap(NULL, 2988, PROT_READ, MAP_PRIVATE, 3, 0x4c000) = 0x2aaf13be2000
	munmap(0x2aaf13be2000, 2988)            = 0
	write(2, "   0% (2/316071) done\r", 22) = 22
	mmap(NULL, 3336, PROT_READ, MAP_PRIVATE, 3, 0x4c000) = 0x2aaf13be2000
	munmap(0x2aaf13be2000, 3336)            = 0
	mmap(NULL, 3471, PROT_READ, MAP_PRIVATE, 3, 0x4c000) = 0x2aaf13be2000
	munmap(0x2aaf13be2000, 3471)            = 0
	mmap(NULL, 3611, PROT_READ, MAP_PRIVATE, 3, 0x4c000) = 0x2aaf13be2000
	munmap(0x2aaf13be2000, 3611)            = 0
	...

   and it's entirely possible that mmap() really does suck *ss on OS X. 
   Those small mmap's go on for a _loong_ time.

I've heard of other operations being slow on OS X - and two orders of 
magnitude really isn't unthinkable. I don't think people always seem to 
really understand how _good_ Linux is, and how much faster it can be. It's 
not just "Windows XP" sucks. Quite often it's literally "Linux is just 
damn fast".

Sadly, that causes problems when the main developers don't even see any 
issues, just because the Linux kernel environment makes things look really 
really cheap. Even when it isn't always cheap on other platforms.

Nico - have you looked at perhaps making the index-pack.c "mmap()" usage 
do chunking? Or just mmap the whole damn thing once? Linux is fast, but 
even Linux will be faster if you just mmap it once ;)

On Tue, 19 Dec 2006, Shawn Pearce wrote:

Why isn't git-index-pack doing the same?  Is there some hidden glitch
in some OS somewhere that has a problem with overmapping a file and
appending into it via write()?  I've done that on Mac OS X, Linux,
BSDi, Solaris...  never had a problem.

It works on modern systems, but at least old HPUX versions had 
non-coherent mmap() and write(), and POSIX does not guarantee it. And if 
you ever want to port to Windows, I don't think you should do it.

Anyway, try the pread() version first, see if that fixes the OS X problem.

Linus Torvalds [off-list ref] wrote:

On Tue, 19 Dec 2006, Theodore Tso wrote:

quoted

So the main reason to use mamp, as Linus puts it, is if the management
overhead of needing to read lots of small bits of the file makes the
use of malloc/read to be a pain in the *ss, then go for it.

An example of this in git is the regular pack-file accesses. We're MUCH 
better off just mmap'ing the whole pack-file (or at least big chunks of 
it) and not having to maintain difficult structures of "this is where I 
read that part of the file into memory", or read _big_ chunks when 
quite often we just use a few kB of it.

So mmap for pack-files does make sense, but probably only when you can 
mmap big chunks, and are going to access much smaller (random) parts of 
it.

Yes, exactly.

git-fast-import mmaps the pack file for this very reason.  It every
so often needs to go back and reread a tree object which has expired
from its own in-memory LRU cache.  This usually doesn't happen
very often, but when it does we don't know where we are going to
jump to get data from.  mmaping a huge segment of the pack file
(or the whole thing if its reasonably small) works for this case as
the OS buffer cache can just take care of it for us.  But as Linus
pointed out mmap and write() aren't safe on some systems.  Arrrgh.

However git-fast-import would probably work just as well (or maybe
slightly better) with pread().  I really should port that code
forward to current Git, use pread() instead, and submit the patch
to Junio.  But nobody really showed a lot of interest.


My sliding window pack-file access implementation (that I'm currently
rewriting on top of current Git) tries to work in very large chunks,
by default its 32 MiB per chunk, but its user/repository configurable
so kernel hackers may just set it to 256 MiB and continue to get
one large mmap for quite some time to come.  Of course I would
also like to get that to autoselect the window size rather than
just hardcode it.  :-)

The implementation would prefer a very small number (<8) of very
large chunks (>32 MiB), but is designed to more gracefully degrade
on huge packs on limited address space systems (e.g. Windows 32 bit)
then the current code does.

-- 

On Tue, 19 Dec 2006, Theodore Tso wrote:

Actually, depending on the size of the chunk, even on Linux
malloc/read/free can be faster than the mmap/munmap

Yes.

In general, mmap/munmap is faster only if:
 - you access the same data multiple times within one page (ie a single 
   page-fault will actually result in more than one access)
OR
 - you can use it to avoid management overhead (ie you know your data is 
   going to accessed very sparsely, but you don't know the patterns, and 
   trying to keep track of it is painful as hell)

That said, under Linux, mmap is almost never really _slower_ either, which 
is why this issue never made any real difference. The overhead of doing 
page table manipulation is pretty much balanced out by the overhead of 
doing a memcpy.

But that "mmap is fast" is _not_ true on many other operating systems, 
which is why it might be worthwhile to try something like the appended on 
OS X, which uses pread() instead of mmap().

This is _not_ very much tested. It seems to work. Caveat emptor. It would 
be interesting to hear if many small "pread()" calls are faster than many 
mmap/munmap calls on OS X. I bet they are. Under Linux, there should be 
almost no difference.

		Linus
---

diff --git a/index-pack.c b/index-pack.c
index 6d6c92b..094f8b2 100644
--- a/index-pack.c
+++ b/index-pack.c

@@ -8,6 +8,7 @@
 #include "tree.h"
 #include <sys/time.h>
 #include <signal.h>
+#include <unistd.h>
 
 static const char index_pack_usage[] =
 "git-index-pack [-v] [-o <index-file>] [{ ---keep | --keep=<msg> }] { <pack-file> | --stdin [--fix-thin] [<pack-file>] }";

@@ -279,27 +280,25 @@ static void *get_data_from_pack(struct object_entry *obj)
 {
 	unsigned long from = obj[0].offset + obj[0].hdr_size;
 	unsigned long len = obj[1].offset - from;
-	unsigned pg_offset = from % getpagesize();
-	unsigned char *map, *data;
+	unsigned char *src, *data;
 	z_stream stream;
 	int st;
 
-	map = mmap(NULL, len + pg_offset, PROT_READ, MAP_PRIVATE,
-		   mmap_fd, from - pg_offset);
-	if (map == MAP_FAILED)
-		die("cannot mmap pack file: %s", strerror(errno));
+	src = xmalloc(len);
+	if (pread(mmap_fd, src, len, from) != len)
+		die("cannot pread pack file: %s", strerror(errno));
 	data = xmalloc(obj->size);
 	memset(&stream, 0, sizeof(stream));
 	stream.next_out = data;
 	stream.avail_out = obj->size;
-	stream.next_in = map + pg_offset;
+	stream.next_in = src;
 	stream.avail_in = len;
 	inflateInit(&stream);
 	while ((st = inflate(&stream, Z_FINISH)) == Z_OK);
 	inflateEnd(&stream);
 	if (st != Z_STREAM_END || stream.total_out != obj->size)
 		die("serious inflate inconsistency");
-	munmap(map, len + pg_offset);
+	free(src);
 	return data;
 }