I'm starting to think repacking is just not feasible on a 64-bit
server with 256MB of RAM (which is a very popular configuration in the
VPS market).
As a quick workaround you could try it with a 32bit git executable?
(assuming you have a distribution with proper multilib support)
I think the right fix would be to make git throttle itself (not
use mmap, use very small defaults etc.) on low memory systems.
It could take a look a /proc/meminfo for this.
-Andi
From: Ken Pratt <hidden> Date: 2016-06-15 22:45:08
As a quick workaround you could try it with a 32bit git executable?
(assuming you have a distribution with proper multilib support)
In this case, I do have control over the server (running Arch Linux,
which should do 32-bit multilib just fine), but for my workflow I
cannot assume that the server will have 32-bit git support.
I will use the previously mentioned solution of doing the packing
elsewhere for now as a band-aid, with hopes that this will get fixed
sometime soon.
Thanks!
-Ken
From: Shawn O. Pearce <hidden> Date: 2016-06-15 22:45:08
Andi Kleen [off-list ref] wrote:
"Ken Pratt" [off-list ref] writes:
quoted
I'm starting to think repacking is just not feasible on a 64-bit
server with 256MB of RAM (which is a very popular configuration in the
VPS market).
I think the right fix would be to make git throttle itself (not
use mmap, use very small defaults etc.) on low memory systems.
It could take a look a /proc/meminfo for this.
Well, we had thought it was already able to throttle itself, as
we did put code in to respond to mmap() and malloc() failures by
trying to release memory and retrying the failed operation again.
However what we don't do is try to limit our heap usage to some
limit that is smaller than physical memory. We just assume that
whatever we need is available from the OS. This fails when what
we need exceeds physical memory and the OS tries to use swap.
We can get better performance by reducing what we mmap instead.
:-|
Looking at /proc/meminfo only works on Linux, and maybe some other
OSes which support a /proc like design. But even then we don't
really know how much we are competing with other active processes
and how much memory we can use.
--
Shawn.
From: Ken Pratt <hidden> Date: 2016-06-15 22:45:08
Looking at /proc/meminfo only works on Linux, and maybe some other
OSes which support a /proc like design. But even then we don't
really know how much we are competing with other active processes
and how much memory we can use.
Could we create a git config variable to specify the maximumum amoung
memory to mmap? Any if that variable wasn't explicitly set, it would
fall back on looking at /proc/meminfo?
From: Shawn O. Pearce <hidden> Date: 2016-06-15 22:45:08
Ken Pratt [off-list ref] wrote:
quoted
Looking at /proc/meminfo only works on Linux, and maybe some other
OSes which support a /proc like design. But even then we don't
really know how much we are competing with other active processes
and how much memory we can use.
Could we create a git config variable to specify the maximumum amoung
memory to mmap? Any if that variable wasn't explicitly set, it would
fall back on looking at /proc/meminfo?
Well, core.packedGitLimit is supposed to be related to this limit
you are asking for. But it doesn't cover all memory usage as we
malloc other things. core.deltaBaseCacheLimit covers part of the
malloc'd area. pack.windowLimit I think covers another part of
the malloc'd area. Etc...
There really isn't a global "malloc/mmap at most X bytes".
--
Shawn.
There really isn't a global "malloc/mmap at most X bytes".
Sure it can never be 100% accurate because other processes
can also steal memory.
Still a 90+% heuristic can work pretty well. If memory < 512MB then don't
use mmap for example. If memory < 256MB do everything as tight
as possible. gcc is using such heuristics quite successfully.
The only problem might be testing coverage for such options.
It might be useful to add options to force it and then run
the test suite with it.
-Andi
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:45:09
On Mon, 11 Aug 2008, Ken Pratt wrote:
quoted
As a quick workaround you could try it with a 32bit git executable?
(assuming you have a distribution with proper multilib support)
In this case, I do have control over the server (running Arch Linux,
which should do 32-bit multilib just fine), but for my workflow I
cannot assume that the server will have 32-bit git support.
I will use the previously mentioned solution of doing the packing
elsewhere for now as a band-aid, with hopes that this will get fixed
sometime soon.
I'm afraid no fix is "possible" since you said:
Largest object is ~150MB, and there are a couple 5-10MB objects as
well.
If you have only 256 MB of RAM, I'm afraid the machine dives into swap
the moment it attempts to process that single 150-MB object during
repacking. Objects are always allocated entirely, including the
deflated and inflated copy at some point. Making git handle partial
objects in memory would add complexity all over the map so I don't think
it'll ever be implemented nor be desirable.
If you do repack once with 'git repack -a -f -d' on a bigger machine
then 256 MB of RAM might be fine for serving clone and fetch requests
though.
Nicolas
If you have only 256 MB of RAM, I'm afraid the machine dives into swap
the moment it attempts to process that single 150-MB object during
repacking. Objects are always allocated entirely, including the
deflated and inflated copy at some point. Making git handle partial
objects in memory would add complexity all over the map so I don't think
it'll ever be implemented nor be desirable.
If the access pattern is sequential and not much reuse it might be possible
to madvise() strategically to do prefetch and early unmap of not used
anymore data. I used that successfully in a few programs in the past that did
aggressive mmap on very large files.
-Andi
From: Shawn O. Pearce <hidden> Date: 2016-06-15 22:45:09
Andi Kleen [off-list ref] wrote:
quoted
If you have only 256 MB of RAM, I'm afraid the machine dives into swap
the moment it attempts to process that single 150-MB object during
repacking. Objects are always allocated entirely, including the
deflated and inflated copy at some point. Making git handle partial
objects in memory would add complexity all over the map so I don't think
it'll ever be implemented nor be desirable.
If the access pattern is sequential and not much reuse it might be possible
to madvise() strategically to do prefetch and early unmap of not used
anymore data. I used that successfully in a few programs in the past that did
aggressive mmap on very large files.
We actually do something better where we can. However parts of
Git assume that it can get back a contiguous block of memory which
contains the entire file content, decompressed. The data is stored
on disk compressed, so we cannot just mmap the data from disk.
--
Shawn.
From: Shawn O. Pearce <hidden> Date: 2016-06-15 22:45:09
Geert Bosch [off-list ref] wrote:
I've always felt that keeping largish objects (say anything >1MB)
loose makes perfect sense. These objects are accessed infrequently,
often binary or otherwise poor candidates for the delta algorithm.
Sadly this causes huge problems with streaming a pack because the
loose object has to be inflated and then delfated again to fit into
the pack stream.
The new style loose object format was meant to fix this problem,
and it did, but the code was difficult to manage so it was backed
out of the tree.
--
Shawn.
As a quick workaround you could try it with a 32bit git executable?
(assuming you have a distribution with proper multilib support)
I think the right fix would be to make git throttle itself (not
use mmap, use very small defaults etc.) on low memory systems.
It could take a look a /proc/meminfo for this.
I've always felt that keeping largish objects (say anything >1MB)
loose makes perfect sense. These objects are accessed infrequently,
often binary or otherwise poor candidates for the delta algorithm.
Many repositories are mostly well-behaved with large number of text
files that aren't overly large and compress/diff well. However, often
a few huge files creep in. These might be a 30 MB Word or PDF documents
(with lots of images of course), a bunch of artwork, some random .tgz
files
with required tools or otherwise.
Regardless of their origin, the presence of such files in real-world
SCMs
is a given and can ruin performance, even if they're hardly ever
accessed
or updated. If we would leave such oddball objects loose, the pack would
be much smaller, easier to generate, faster to use and there should be
no
memory usage issues.
-Geert
I've always felt that keeping largish objects (say anything >1MB)
loose makes perfect sense. These objects are accessed infrequently,
often binary or otherwise poor candidates for the delta algorithm.
Sadly this causes huge problems with streaming a pack because the
loose object has to be inflated and then delfated again to fit into
the pack stream.
Sure, but that really is not that much of an issue. For people
with large systems connected by very fast networks, the current
situation is probably fine, and spending a lot of effort for
packing often makes sense.
However, for a random repository of Joe User, all the effort spent
on packing will probably never be gained back. Most people just
suck content from upstream and at most maintain a couple of local
hacks on top of that. Little or nothing is ever pushed to other
systems.
Even when pushing to other systems, this often is just a handful of
objects
though a slow line and compression/decompression speeds just don't
matter
much.
The new style loose object format was meant to fix this problem,
and it did, but the code was difficult to manage so it was backed
out of the tree.
One nice optimization we could do for those pesky binary large objects
(like PDF, JPG and GZIP-ed data), is to detect such files and revert
to compression level 0. This should be especially beneficial
since already compressed data takes most time to compress again.
-Geert
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:45:09
On Tue, 12 Aug 2008, Geert Bosch wrote:
I've always felt that keeping largish objects (say anything >1MB)
loose makes perfect sense. These objects are accessed infrequently,
often binary or otherwise poor candidates for the delta algorithm.
Or, as I suggested in the past, they can be grouped into a separate
pack, or even occupy a pack of their own. As soon as you have more than
one revision of such largish objects then you lose again by keeping them
loose.
Many repositories are mostly well-behaved with large number of text
files that aren't overly large and compress/diff well. However, often
a few huge files creep in. These might be a 30 MB Word or PDF documents
(with lots of images of course), a bunch of artwork, some random .tgz files
with required tools or otherwise.
Regardless of their origin, the presence of such files in real-world SCMs
is a given and can ruin performance, even if they're hardly ever accessed
or updated. If we would leave such oddball objects loose, the pack would
be much smaller, easier to generate, faster to use and there should be no
memory usage issues.
You'll have memory usage issues whenever such objects are accessed,
loose or not. However, once those big objects are packed once, they can
be repacked (or streamed over the net) without really "accessing" them.
Packed object data is simply copied into a new pack in that case which
is less of an issue on memory usage, irrespective of the original pack
size.
Nicolas
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:45:09
On Tue, 12 Aug 2008, Geert Bosch wrote:
One nice optimization we could do for those pesky binary large objects
(like PDF, JPG and GZIP-ed data), is to detect such files and revert
to compression level 0. This should be especially beneficial
since already compressed data takes most time to compress again.
From: Jakub Narebski <hidden> Date: 2016-06-15 22:45:09
Nicolas Pitre [off-list ref] writes:
On Tue, 12 Aug 2008, Geert Bosch wrote:
quoted
One nice optimization we could do for those pesky binary large objects
(like PDF, JPG and GZIP-ed data), is to detect such files and revert
to compression level 0. This should be especially beneficial
since already compressed data takes most time to compress again.
That would be a good thing indeed.
Perhaps take a sample of some given size and calculate entropy in it?
Or just simply add gitattribute for per file compression ratio...
--
Jakub Narebski
Poland
ShadeHawk on #git
From: Shawn O. Pearce <hidden> Date: 2016-06-15 22:45:09
Nicolas Pitre [off-list ref] wrote:
You'll have memory usage issues whenever such objects are accessed,
loose or not. However, once those big objects are packed once, they can
be repacked (or streamed over the net) without really "accessing" them.
Packed object data is simply copied into a new pack in that case which
is less of an issue on memory usage, irrespective of the original pack
size.
And fortunately here we actually do stream the objects we have
chosen to reuse from the pack. We don't allocate the entire thing
in memory. Its probably the only place in all of Git where we can
handle a 16 GB (after compression) object on a machine with only
2 GB of memory and no swap.
Where little memory systems get into trouble with already packed
repositories is enumerating the objects to include in the pack.
This can still blow out their physical memory if the number of
objects to pack is high enough. We need something like 160 bytes
of memory (my own memory is fuzzy on that estimate) per object.
Have 500k objects and its suddenly something quite real in terms
of memory usage.
--
Shawn.
From: Shawn O. Pearce <hidden> Date: 2016-06-15 22:45:09
Jakub Narebski [off-list ref] wrote:
Nicolas Pitre [off-list ref] writes:
quoted
On Tue, 12 Aug 2008, Geert Bosch wrote:
quoted
One nice optimization we could do for those pesky binary large objects
(like PDF, JPG and GZIP-ed data), is to detect such files and revert
to compression level 0. This should be especially beneficial
since already compressed data takes most time to compress again.
That would be a good thing indeed.
Perhaps take a sample of some given size and calculate entropy in it?
Or just simply add gitattribute for per file compression ratio...
Estimating the entropy would make it "just magic". Most of Git is
"just magic" so that's a good direction to take. I'm not familiar
enough with the PDF/JPG/GZIP/ZIP stream formats to know what the
first 4-8k looks like to know if it would give a good indication
of being already compressed.
Though I'd imagine looking at the first 4k should be sufficient
for any compressed file. Having a header composed of 4k of _text_
before binary compressed data would be nuts. Or a git-bundle with
a large refs listing. ;-)
Using a gitattribute inside of pack-objects is not "simple".
We currently only support reading attributes from the working
directory if I recall correctly. pack-objects may not have a
working directory.
Hence, "just magic" is probably the better route.
--
Shawn.
From: David Tweed <hidden> Date: 2016-06-15 22:45:09
On Wed, Aug 13, 2008 at 4:04 PM, Shawn O. Pearce [off-list ref] wrote:
Jakub Narebski [off-list ref] wrote:
quoted
Nicolas Pitre [off-list ref] writes:
quoted
On Tue, 12 Aug 2008, Geert Bosch wrote:
quoted
One nice optimization we could do for those pesky binary large objects
(like PDF, JPG and GZIP-ed data), is to detect such files and revert
to compression level 0. This should be especially beneficial
since already compressed data takes most time to compress again.
That would be a good thing indeed.
Perhaps take a sample of some given size and calculate entropy in it?
Or just simply add gitattribute for per file compression ratio...
Estimating the entropy would make it "just magic". Most of Git is
"just magic" so that's a good direction to take. I'm not familiar
enough with the PDF/JPG/GZIP/ZIP stream formats to know what the
first 4-8k looks like to know if it would give a good indication
of being already compressed.
Though I'd imagine looking at the first 4k should be sufficient
for any compressed file. Having a header composed of 4k of _text_
before binary compressed data would be nuts. Or a git-bundle with
a large refs listing. ;-)
FWIW, PDF format is a mix of sections of uncompressed higher level
ASCII notation and sections of compressed actual glyph/location data
for individual pages, and I don't think the rules are very strict
about what goes where. Looking at some academic papers some contain
compressed data within the first hundred characters whilst I've got a
couple with the first compressed byte 1968 and 12304; I'm sure if I
had a longer pdf to look at I'd find one where compression data first
occurred even later. I leave discussions of whether this is nuts to
others ;-) .
JPG is pretty much guaranteed to contain compressed data after a
couple of metadata lines.
--
cheers, dave tweed__________________________
david.tweed@gmail.com
Rm 124, School of Systems Engineering, University of Reading.
"while having code so boring anyone can maintain it, use Python." --
attempted insult seen on slashdot
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:45:09
On Wed, 13 Aug 2008, Shawn O. Pearce wrote:
Nicolas Pitre [off-list ref] wrote:
quoted
You'll have memory usage issues whenever such objects are accessed,
loose or not. However, once those big objects are packed once, they can
be repacked (or streamed over the net) without really "accessing" them.
Packed object data is simply copied into a new pack in that case which
is less of an issue on memory usage, irrespective of the original pack
size.
And fortunately here we actually do stream the objects we have
chosen to reuse from the pack. We don't allocate the entire thing
in memory. Its probably the only place in all of Git where we can
handle a 16 GB (after compression) object on a machine with only
2 GB of memory and no swap.
Where little memory systems get into trouble with already packed
repositories is enumerating the objects to include in the pack.
This can still blow out their physical memory if the number of
objects to pack is high enough. We need something like 160 bytes
of memory (my own memory is fuzzy on that estimate) per object.
I'm counting something like 104 bytes on a 64-bit machine for
struct object_entry.
Have 500k objects and its suddenly something quite real in terms
of memory usage.
Well, we are talking about 50MB which is not that bad.
However there is a point where we should be realistic and just admit
that you need a sufficiently big machine if you have huge repositories
to deal with. Git should be fine serving pull requests with relatively
little memory usage, but anything else such as the initial repack simply
require enough RAM to be effective.
Nicolas
From: Shawn O. Pearce <hidden> Date: 2016-06-15 22:45:09
Nicolas Pitre [off-list ref] wrote:
On Wed, 13 Aug 2008, Shawn O. Pearce wrote:
quoted
Where little memory systems get into trouble with already packed
repositories is enumerating the objects to include in the pack.
I'm counting something like 104 bytes on a 64-bit machine for
struct object_entry.
Don't forget that we need not just struct object_entry, but
also the struct commit/tree/blob, their hash tables, and the
struct object_entry* in the sorted object list table, and
the pack reverse index table. It does add up.
quoted
Have 500k objects and its suddenly something quite real in terms
of memory usage.
Well, we are talking about 50MB which is not that bad.
I think we're closer to 100MB here due to the extra overheads
I just alluded to above, and which weren't in your 104 byte
per object figure.
However there is a point where we should be realistic and just admit
that you need a sufficiently big machine if you have huge repositories
to deal with. Git should be fine serving pull requests with relatively
little memory usage, but anything else such as the initial repack simply
require enough RAM to be effective.
Yea. But it would also be nice to be able to just concat packs
together. Especially if the repository in question is an open source
one and everything published is already known to be in the wild,
as say it is also available over dumb HTTP. Yea, I know people
like the 'security feature' of the packer not including objects
which aren't reachable.
But how many times has Linus published something to his linux-2.6
tree that he didn't mean to publish and had to rewind? I think
that may be "never". Yet how many times per day does his tree get
cloned from scratch?
This is also true for many internal corporate repositories.
Users probably have full read access to the object database anyway,
and maybe even have direct write access to it. Doing the object
enumeration there is pointless as a security measure.
I'm too busy to write a pack concat implementation proposal, so
I'll just shutup now. But it wouldn't be hard if someone wanted
to improve at least the initial clone serving case.
--
Shawn.
I've always felt that keeping largish objects (say anything >1MB)
loose makes perfect sense. These objects are accessed infrequently,
often binary or otherwise poor candidates for the delta algorithm.
Or, as I suggested in the past, they can be grouped into a separate
pack, or even occupy a pack of their own.
This is fine, as long as we're not trying to create deltas
of the large objects, or do other things that requires keeping
the inflated data in memory.
As soon as you have more than
one revision of such largish objects then you lose again by keeping
them
loose.
Yes, you lose potentially in terms of disk space, but you avoid the
large memory footprint during pack generation. For very large blobs,
it is best to degenerate to having each revision of each file on
its own (whether we call it a single-file pack, loose object or
whatever).
That way, the large file can stay immutable on disk, and will only
need to be accessed during checkout. GIT will then scale with good
performance until we run out of disk space.
The alternative is that people need to keep large binary data out
of their SCMs and handle it on the side. Consider a large web site
where I have all scripts, HTML content, as well as a few movies
to manage. The movies basically should be copied and stored, only
to be accessed when a checkout (or push) is requested.
If we mix the very large movies with the 100,000 objects representing
the webpages, the resulting pack will become unwieldy and slow even
to just copy around during repacks.
You'll have memory usage issues whenever such objects are accessed,
loose or not.
Why? The only time we'd need to access their contents for checkout
or when pushing across the network. These should all be steaming
operations
with small memory footprint.
However, once those big objects are packed once, they can
be repacked (or streamed over the net) without really "accessing"
them.
Packed object data is simply copied into a new pack in that case which
is less of an issue on memory usage, irrespective of the original pack
size.
Agreed, but still, at least very large objects. If I have a 600MB
file in my repository, it should just not get in the way. If it gets
copied around during each repack, that just wastes I/O time for no
good reason. Even worse, it causes incremental backups or filesystem
checkpoints to become way more expensive. Just leaving large files
alone as immutable objects on disk avoids all these issues.
-Geert
From: Johan Herland <hidden> Date: 2016-06-15 22:45:09
On Wednesday 13 August 2008, Shawn O. Pearce wrote:
Jakub Narebski [off-list ref] wrote:
quoted
Nicolas Pitre [off-list ref] writes:
quoted
On Tue, 12 Aug 2008, Geert Bosch wrote:
quoted
One nice optimization we could do for those pesky binary large
objects (like PDF, JPG and GZIP-ed data), is to detect such
files and revert to compression level 0. This should be
especially beneficial since already compressed data takes most
time to compress again.
That would be a good thing indeed.
Perhaps take a sample of some given size and calculate entropy in
it? Or just simply add gitattribute for per file compression
ratio...
Estimating the entropy would make it "just magic". Most of Git is
"just magic" so that's a good direction to take. I'm not familiar
enough with the PDF/JPG/GZIP/ZIP stream formats to know what the
first 4-8k looks like to know if it would give a good indication
of being already compressed.
Though I'd imagine looking at the first 4k should be sufficient
for any compressed file. Having a header composed of 4k of _text_
before binary compressed data would be nuts. Or a git-bundle with
a large refs listing. ;-)
As for how to estimate entropy, isn't that just a matter of feeding it
through zlib and compare the output size to the input size? Especially
if we're already about to feed it through zlib anyway... In other
words, feed (an initial part of) the data through zlib, and if the
compression ratio so far looks good, keep going and write out the
compressed object, otherwise abort zlib and write out the original
object with compression level 0.
Hence, "just magic" is probably the better route.
Agreed.
Have fun!
...Johan
--
Johan Herland, [off-list ref]
www.herland.net
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:45:09
On Wed, 13 Aug 2008, Shawn O. Pearce wrote:
Nicolas Pitre [off-list ref] wrote:
quoted
Well, we are talking about 50MB which is not that bad.
I think we're closer to 100MB here due to the extra overheads
I just alluded to above, and which weren't in your 104 byte
per object figure.
Sure. That should still be workable on a machine with 256MB of RAM.
quoted
However there is a point where we should be realistic and just admit
that you need a sufficiently big machine if you have huge repositories
to deal with. Git should be fine serving pull requests with relatively
little memory usage, but anything else such as the initial repack simply
require enough RAM to be effective.
Yea. But it would also be nice to be able to just concat packs
together. Especially if the repository in question is an open source
one and everything published is already known to be in the wild,
as say it is also available over dumb HTTP. Yea, I know people
like the 'security feature' of the packer not including objects
which aren't reachable.
It is not only that, even if it is a point I consider important. If you
end up with 10 packs, it is likely that a base object in each of those
packs could simply be a delta against a single common base object, and
therefore the amount of data to transfer might be up to 10 times higher
than necessary.
But how many times has Linus published something to his linux-2.6
tree that he didn't mean to publish and had to rewind? I think
that may be "never". Yet how many times per day does his tree get
cloned from scratch?
That's not a good argument. Linus is a very disciplined git users,
probably more than average. We should not use that example to paper
over technical issues.
This is also true for many internal corporate repositories.
Users probably have full read access to the object database anyway,
and maybe even have direct write access to it. Doing the object
enumeration there is pointless as a security measure.
It is good for network bandwidth efficiency as I mentioned.
I'm too busy to write a pack concat implementation proposal, so
I'll just shutup now. But it wouldn't be hard if someone wanted
to improve at least the initial clone serving case.
A much better solution would consist of finding just _why_ object
enumeration is so slow. This is indeed my biggest grip with git
performance at the moment.
|nico@xanadu:linux-2.6> time git rev-list --objects --all > /dev/null
|
|real 0m21.742s
|user 0m21.379s
|sys 0m0.360s
That's way too long for 1030198 objects (roughly 48k objects/sec). And
it gets even worse with the gcc repository:
|nico@xanadu:gcc> time git rev-list --objects --all > /dev/null
|
|real 1m51.591s
|user 1m50.757s
|sys 0m0.810s
That's for 1267993 objects, or about 11400 objects/sec.
Clearly something is not scaling here.
Nicolas
Hi Geert,
I wrote the blob-size-threshold patch last year to which
Jakub Narebski referred.
I think there will eventually be a way to better handle large
objects in Git. Some possible elements:
* Loose objects have a format which can be streamed
directly into or out of packs. This avoids a round-trip through zlib,
which is a big deal for big objects. This was the effect of the "new"
loose object format to which Shawn referred. This was
removed apparently because it was ugly and/or difficult
to maintain, which I didn't understand since I didn't personally
suffer.
* Loose objects actually _are_ singleton packs, but saved
in .git/objects/xx. Workable, but would never happen due to
the extra pack header at the beginning it would add. This
takes advantage of the existing pack-to-pack streaming.
* Large loose objects are never deltified and/or never packed.
The latter was the focus of my patch.
* Large loose objects are placed in their own packs in .git/packs .
Doesn't work for me since I have too many large objects,
thus slowing down _all_ pack operations.
All this is complicated by the dual nature of packfiles --
they are used as a "wire format" for serial transmission,
as well as a database format for random access.
The "magic" entropy detection idea is cute, but probably not
needed -- using the blob size should be sufficient. Trying to
(re)compress an incompressible _smallish_ blob is probably
not worth trying to avoid, and any computation on sufficiently large
blobs should be avoided.
Hopefully I can return to this problem after New Year's. And
perhaps with the expanding Git userbase, more people will have
"large blob" problems ;-) and there will be more interest in
better addressing this usage pattern.
At the moment, I am thinking about how to better structure
git's handling of very large repositories in a team entirely
connected by high-speed LAN. It seems a method where
each user has a repository with deep history, but shallow
blobs, would be ideal, but that's also very different from
how git does things now.
Have fun,
Dana How
On Wed, Aug 13, 2008 at 9:01 AM, Geert Bosch [off-list ref] wrote:
On Aug 13, 2008, at 10:35, Nicolas Pitre wrote:
quoted
On Tue, 12 Aug 2008, Geert Bosch wrote:
quoted
I've always felt that keeping largish objects (say anything >1MB)
loose makes perfect sense. These objects are accessed infrequently,
often binary or otherwise poor candidates for the delta algorithm.
Or, as I suggested in the past, they can be grouped into a separate
pack, or even occupy a pack of their own.
This is fine, as long as we're not trying to create deltas
of the large objects, or do other things that requires keeping
the inflated data in memory.
quoted
As soon as you have more than
one revision of such largish objects then you lose again by keeping them
loose.
Yes, you lose potentially in terms of disk space, but you avoid the
large memory footprint during pack generation. For very large blobs,
it is best to degenerate to having each revision of each file on
its own (whether we call it a single-file pack, loose object or whatever).
That way, the large file can stay immutable on disk, and will only
need to be accessed during checkout. GIT will then scale with good
performance until we run out of disk space.
The alternative is that people need to keep large binary data out
of their SCMs and handle it on the side. Consider a large web site
where I have all scripts, HTML content, as well as a few movies
to manage. The movies basically should be copied and stored, only
to be accessed when a checkout (or push) is requested.
If we mix the very large movies with the 100,000 objects representing
the webpages, the resulting pack will become unwieldy and slow even
to just copy around during repacks.
quoted
You'll have memory usage issues whenever such objects are accessed,
loose or not.
Why? The only time we'd need to access their contents for checkout
or when pushing across the network. These should all be steaming operations
with small memory footprint.
quoted
However, once those big objects are packed once, they can
be repacked (or streamed over the net) without really "accessing" them.
Packed object data is simply copied into a new pack in that case which
is less of an issue on memory usage, irrespective of the original pack
size.
Agreed, but still, at least very large objects. If I have a 600MB
file in my repository, it should just not get in the way. If it gets
copied around during each repack, that just wastes I/O time for no
good reason. Even worse, it causes incremental backups or filesystem
checkpoints to become way more expensive. Just leaving large files
alone as immutable objects on disk avoids all these issues.
-Geert
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
--
Dana L. How danahow@gmail.com +1 650 804 5991 cell
From: Shawn O. Pearce <hidden> Date: 2016-06-15 22:45:09
Nicolas Pitre [off-list ref] wrote:
On Wed, 13 Aug 2008, Shawn O. Pearce wrote:
quoted
Doing the object
enumeration is pointless as a security measure.
It is good for network bandwidth efficiency as I mentioned.
The network bandwidth efficiency is the most valid argument for
the enumeration.
quoted
I'm too busy to write a pack concat implementation proposal
A much better solution would consist of finding just _why_ object
enumeration is so slow. This is indeed my biggest grip with git
performance at the moment.
...
|nico@xanadu:gcc> time git rev-list --objects --all > /dev/null
|
|real 1m51.591s
|user 1m50.757s
|sys 0m0.810s
That's for 1267993 objects, or about 11400 objects/sec.
Clearly something is not scaling here.
Yikes. Last time I was looking at this sort of thing I think we
spent around 60% of our time dealing with inflating, patching and
parsing commit and tree objects. pack v4's formatting spawned
out of that particular point, but we never really finished that.
Its been years so I can't trust my memory enough to say pack v4 is
the solution to this, without redoing the profiling. But I think
that is what one would find.
Though the decreasing objects/sec rate with increased total number
of objects suggets the object hash isn't scaling.
--
Shawn.
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:45:09
On Wed, 13 Aug 2008, Geert Bosch wrote:
On Aug 13, 2008, at 10:35, Nicolas Pitre wrote:
quoted
On Tue, 12 Aug 2008, Geert Bosch wrote:
quoted
I've always felt that keeping largish objects (say anything >1MB)
loose makes perfect sense. These objects are accessed infrequently,
often binary or otherwise poor candidates for the delta algorithm.
Or, as I suggested in the past, they can be grouped into a separate
pack, or even occupy a pack of their own.
This is fine, as long as we're not trying to create deltas
of the large objects, or do other things that requires keeping
the inflated data in memory.
First, there is the delta attribute:
|commit a74db82e15cd8a2c53a4a83e9a36dc7bf7a4c750
|Author: Junio C Hamano [off-list ref]
|Date: Sat May 19 00:39:31 2007 -0700
|
| Teach "delta" attribute to pack-objects.
|
| This teaches pack-objects to use .gitattributes mechanism so
| that the user can specify certain blobs are not worth spending
| CPU cycles to attempt deltification.
|
| The name of the attrbute is "delta", and when it is set to
| false, like this:
|
| == .gitattributes ==
| *.jpg -delta
|
| they are always stored in the plain-compressed base object
| representation.
This could probably be extended to take a size limit argument as well.
quoted
As soon as you have more than
one revision of such largish objects then you lose again by keeping them
loose.
Yes, you lose potentially in terms of disk space, but you avoid the
large memory footprint during pack generation. For very large blobs,
it is best to degenerate to having each revision of each file on
its own (whether we call it a single-file pack, loose object or whatever).
That way, the large file can stay immutable on disk, and will only
need to be accessed during checkout. GIT will then scale with good
performance until we run out of disk space.
Loose objects, though, will always be selected for potential delta
generation. Packed objects, deltified or not, are always streamed as is
when serving pull requests. And by default delta compression is not
(re)attempted between objects which are part of the same pack, the
reason being that if they were not deltified on the first packing
attempt then there is no point trying again when streaming them over the
net. So you always benefit from having your large objects packed with
the rest. This, plus the delta prevention mechanism above should cover
most cases.
quoted
You'll have memory usage issues whenever such objects are accessed,
loose or not.
Why? The only time we'd need to access their contents for checkout
or when pushing across the network. These should all be steaming operations
with small memory footprint.
Pushing across the network, or repacking without -f, is streamed.
Checking out currently isn't (although it probably could). Repacking
with -f definitely isn't and probably shouldn't because of complexity
issues.
quoted
However, once those big objects are packed once, they can
be repacked (or streamed over the net) without really "accessing" them.
Packed object data is simply copied into a new pack in that case which
is less of an issue on memory usage, irrespective of the original pack
size.
Agreed, but still, at least very large objects. If I have a 600MB
file in my repository, it should just not get in the way. If it gets
copied around during each repack, that just wastes I/O time for no
good reason. Even worse, it causes incremental backups or filesystem
checkpoints to become way more expensive. Just leaving large files
alone as immutable objects on disk avoids all these issues.
Pack them in a pack of their own and stick a .keep file along with it.
At that point they will never be rewritten.
Nicolas
From: Ken Pratt <hidden> Date: 2016-06-15 22:45:09
As for how to estimate entropy, isn't that just a matter of feeding it
through zlib and compare the output size to the input size? Especially
if we're already about to feed it through zlib anyway... In other
words, feed (an initial part of) the data through zlib, and if the
compression ratio so far looks good, keep going and write out the
compressed object, otherwise abort zlib and write out the original
object with compression level 0.
This if probably off topic now, but as the OP, I'd like to mention
that I tried setting pack.compression = 0 and it did not solve my
memory issues. So it seems to be that the packing itself that is
sucking up all the memory -- not the compression.
Thanks for all the insightful replies!
-Ken
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:45:09
On Wed, 13 Aug 2008, Ken Pratt wrote:
quoted
As for how to estimate entropy, isn't that just a matter of feeding it
through zlib and compare the output size to the input size? Especially
if we're already about to feed it through zlib anyway... In other
words, feed (an initial part of) the data through zlib, and if the
compression ratio so far looks good, keep going and write out the
compressed object, otherwise abort zlib and write out the original
object with compression level 0.
This is probably off topic now, but as the OP, I'd like to mention
that I tried setting pack.compression = 0 and it did not solve my
memory issues.
Yeah, the compression level is a tengential issue which has to do with
speed.
So it seems to be that the packing itself that is
sucking up all the memory -- not the compression.
Initial packing requires enough memory. And if your repository is not
packed, then every clone request will act just like a first packing. So
for git on a server to behave well, repositories have to be well packed.
Nicolas
From: Martin Langhoff <hidden> Date: 2016-06-15 22:45:09
On Thu, Aug 14, 2008 at 3:26 AM, David Tweed [off-list ref] wrote:
FWIW, PDF format is a mix of sections of uncompressed higher level
ASCII notation and sections of compressed actual glyph/location data
The PDF spec allows compression of the "text" sections - if a PDF is
uncompressed, it's a good candidate for delta & compression.
Unfortunately, within the same file you might have an embedded JPEG.
cheers,
m
--
martin.langhoff@gmail.com
martin@laptop.org -- School Server Architect
- ask interesting questions
- don't get distracted with shiny stuff - working code first
- http://wiki.laptop.org/go/User:Martinlanghoff
From: Andreas Ericsson <hidden> Date: 2016-06-15 22:45:09
Nicolas Pitre wrote:
On Wed, 13 Aug 2008, Shawn O. Pearce wrote:
quoted
Nicolas Pitre [off-list ref] wrote:
quoted
Well, we are talking about 50MB which is not that bad.
I think we're closer to 100MB here due to the extra overheads
I just alluded to above, and which weren't in your 104 byte
per object figure.
Sure. That should still be workable on a machine with 256MB of RAM.
quoted
quoted
However there is a point where we should be realistic and just admit
that you need a sufficiently big machine if you have huge repositories
to deal with. Git should be fine serving pull requests with relatively
little memory usage, but anything else such as the initial repack simply
require enough RAM to be effective.
Yea. But it would also be nice to be able to just concat packs
together. Especially if the repository in question is an open source
one and everything published is already known to be in the wild,
as say it is also available over dumb HTTP. Yea, I know people
like the 'security feature' of the packer not including objects
which aren't reachable.
It is not only that, even if it is a point I consider important. If you
end up with 10 packs, it is likely that a base object in each of those
packs could simply be a delta against a single common base object, and
therefore the amount of data to transfer might be up to 10 times higher
than necessary.
[cut]
quoted
This is also true for many internal corporate repositories.
Users probably have full read access to the object database anyway,
and maybe even have direct write access to it. Doing the object
enumeration there is pointless as a security measure.
It is good for network bandwidth efficiency as I mentioned.
As a corporate git user, I can say that I'm very rarely worried
about how much data gets sent over our in-office gigabit network.
My primary concern wrt server side git is cpu- and IO-heavy
operations, as we run the entire machine in a vmware guest os
which just plain sucks at such things.
With that in mind, a config variable in /etc/gitconfig would
work wonderfully for that situation, as our central watering
hole only ever serves locally.
quoted
I'm too busy to write a pack concat implementation proposal, so
I'll just shutup now. But it wouldn't be hard if someone wanted
to improve at least the initial clone serving case.
A much better solution would consist of finding just _why_ object
enumeration is so slow. This is indeed my biggest grip with git
performance at the moment.
|nico@xanadu:linux-2.6> time git rev-list --objects --all > /dev/null
|
|real 0m21.742s
|user 0m21.379s
|sys 0m0.360s
That's way too long for 1030198 objects (roughly 48k objects/sec). And
it gets even worse with the gcc repository:
|nico@xanadu:gcc> time git rev-list --objects --all > /dev/null
|
|real 1m51.591s
|user 1m50.757s
|sys 0m0.810s
That's for 1267993 objects, or about 11400 objects/sec.
Clearly something is not scaling here.
What are the different packing options for the two repositories?
A longer deltachain and larger packwindow would increase the
enumeration time, wouldn't it?
--
Andreas Ericsson andreas.ericsson@op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
From: David Tweed <hidden> Date: 2016-06-15 22:45:09
On Thu, Aug 14, 2008 at 12:54 AM, Martin Langhoff
[off-list ref] wrote:
On Thu, Aug 14, 2008 at 3:26 AM, David Tweed [off-list ref] wrote:
quoted
FWIW, PDF format is a mix of sections of uncompressed higher level
ASCII notation and sections of compressed actual glyph/location data
The PDF spec allows compression of the "text" sections - if a PDF is
uncompressed, it's a good candidate for delta & compression.
Unfortunately, within the same file you might have an embedded JPEG.
Sure, all I was pointing out was that even pdfs with compressed page
contents can look like uncompressed text from looking at the entropy
of the first 4k or 8k.
--
cheers, dave tweed__________________________
david.tweed@gmail.com
Rm 124, School of Systems Engineering, University of Reading.
"while having code so boring anyone can maintain it, use Python." --
attempted insult seen on slashdot
From: Thomas Rast <hidden> Date: 2016-06-15 22:45:09
Andreas Ericsson wrote:
Nicolas Pitre wrote:
quoted
|nico@xanadu:linux-2.6> time git rev-list --objects --all > /dev/null
|
|real 0m21.742s
|user 0m21.379s
|sys 0m0.360s
That's way too long for 1030198 objects (roughly 48k objects/sec). And
it gets even worse with the gcc repository:
|nico@xanadu:gcc> time git rev-list --objects --all > /dev/null
|
|real 1m51.591s
|user 1m50.757s
|sys 0m0.810s
That's for 1267993 objects, or about 11400 objects/sec.
Clearly something is not scaling here.
What are the different packing options for the two repositories?
A longer deltachain and larger packwindow would increase the
enumeration time, wouldn't it?
For the fun of it, I ran a test without deltas. Here's my normal
git.git:
$ du -h .git/objects/pack
26M .git/objects/pack
$ git rev-list --all | wc -l
17638
$ git rev-list --all --objects | wc -l
82194
On a hot cache I get about 61800 objects/sec:
$ /usr/bin/time git rev-list --all --objects >/dev/null
1.33user 0.04system 0:01.39elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+8087minor)pagefaults 0swaps
I then made a copy of that and repacked it without deltas (remember to
remove *.keep, I tripped over that twice):
$ git repack --depth=0 --window=0 -a -f -d
Counting objects: 82906, done.
Writing objects: 100% (82906/82906), done.
Total 82906 (delta 0), reused 0 (delta 0)
$ du -h .git/objects/pack
339M .git/objects/pack
Which results in only 28739 objects/sec:
$ /usr/bin/time git rev-list --all --objects >/dev/null
2.86user 0.11system 0:02.98elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+50162minor)pagefaults 0swaps
So maybe the GCC repository would need to be packed _better_?
Unfortunately I cannot sensibly run the same test on linux-2.6.git,
which is the next bigger git I have around: it inflates to about 3GB
after the repack, which does not fit into memory.
- Thomas
--
Thomas Rast
trast@student.ethz.ch
From: Andreas Ericsson <hidden> Date: 2016-06-15 22:45:09
Thomas Rast wrote:
Andreas Ericsson wrote:
quoted
Nicolas Pitre wrote:
quoted
|nico@xanadu:linux-2.6> time git rev-list --objects --all > /dev/null
|
|real 0m21.742s
|user 0m21.379s
|sys 0m0.360s
That's way too long for 1030198 objects (roughly 48k objects/sec). And
it gets even worse with the gcc repository:
|nico@xanadu:gcc> time git rev-list --objects --all > /dev/null
|
|real 1m51.591s
|user 1m50.757s
|sys 0m0.810s
That's for 1267993 objects, or about 11400 objects/sec.
Clearly something is not scaling here.
What are the different packing options for the two repositories?
A longer deltachain and larger packwindow would increase the
enumeration time, wouldn't it?
For the fun of it, I ran a test without deltas. Here's my normal
git.git:
$ du -h .git/objects/pack
26M .git/objects/pack
$ git rev-list --all | wc -l
17638
$ git rev-list --all --objects | wc -l
82194
On a hot cache I get about 61800 objects/sec:
$ /usr/bin/time git rev-list --all --objects >/dev/null
1.33user 0.04system 0:01.39elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+8087minor)pagefaults 0swaps
I then made a copy of that and repacked it without deltas (remember to
remove *.keep, I tripped over that twice):
$ git repack --depth=0 --window=0 -a -f -d
Counting objects: 82906, done.
Writing objects: 100% (82906/82906), done.
Total 82906 (delta 0), reused 0 (delta 0)
$ du -h .git/objects/pack
339M .git/objects/pack
Which results in only 28739 objects/sec:
Well, if the objects are, on average, >twice the size, would that
explain it? I'd hate to see some of the sharper git minds hop off
on a wild goose chase if it's not necessary.
How does one go about getting the object sizes? rev-list appears
to have no option for it.
--
Andreas Ericsson andreas.ericsson@op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:45:09
On Thu, 14 Aug 2008, Andreas Ericsson wrote:
As a corporate git user, I can say that I'm very rarely worried
about how much data gets sent over our in-office gigabit network.
My primary concern wrt server side git is cpu- and IO-heavy
operations, as we run the entire machine in a vmware guest os
which just plain sucks at such things.
In the general case, the amount of data sent over the network is
directly proportional to disk IO.
Nicolas
A much better solution would consist of finding just _why_ object
enumeration is so slow. This is indeed my biggest grip with git
performance at the moment.
|nico@xanadu:linux-2.6> time git rev-list --objects --all > /dev/null
|
|real 0m21.742s
|user 0m21.379s
|sys 0m0.360s
That's way too long for 1030198 objects (roughly 48k objects/sec).
Why do you think that's horribly slow?
Doing a rev-list of all objects is a fairly rare operation, but even if
you want to clone/repack all of your archives the whole time, please
realize that listing objects is _not_ a simple operation. It opens up and
parses every single tree in the whole history. That's a _lot_ of data to
unpack.
And trees also pack very efficiently (because they delta so well), so
there's a lot of complex ops there.
And it gets even worse with the gcc repository:
I bet it's because gcc has a different directory structure. I don't have
the gcc sources in front of me, but I'd suspect something like a single
large directory or other.
Clearly something is not scaling here.
I don't agree. There's no "clearly" about it. Different data sets.
Linus
Doing a rev-list of all objects is a fairly rare operation, but even if
you want to clone/repack all of your archives the whole time, please
realize that listing objects is _not_ a simple operation. It opens up and
parses every single tree in the whole history. That's a _lot_ of data to
unpack.
Btw, it's not that hard to run oprofile (link git statically to get better
numbers). For me, the answer to what is going on for a kernel rev-list is
pretty straightforward:
263742 26.6009 lookup_object
135945 13.7113 inflate
110525 11.1475 inflate_fast
75124 7.5770 inflate_table
64676 6.5232 strlen
48635 4.9053 memcpy
47744 4.8154 find_pack_entry_one
35265 3.5568 _int_malloc
31579 3.1850 decode_tree_entry
28388 2.8632 adler32
19441 1.9608 process_tree
10398 1.0487 patch_delta
8925 0.9002 _int_free
..
so most of it is in inflate, but I suspect the cost of "lookup_object()"
is so high becuase when we parse the trees we also have to look up every
blob - even if they didn't change - just to see whether we already saw it
or not.
For me, an instruction-level profile of lookup_object() shows that the
cost is all in the hashcmp (53% of the profile is on that "repz cmpsb")
and in the loading of the object pointer (26% of the profile is on the
test instruction after the "obj_hash[i]" load). I don't think we can
really improve that code much - the hash table is very efficient, and the
cost is just in the fact that we have a lot of meory accesses.
We could try to use the (more memory-hungry) "hash.c" implementation for
object hashing, which actually includes a 32-bit key inside the hash
table, but while that will avoid the cost of fetching the object pointer
for the cases where we have collisions, most of the time the cost is not
in the collision, but in the fact that we _hit_.
I bet the hit percentage is 90+%, and the cost really is just that we
encounter the same object hundreds or thousands of times.
Please realize that even if there may be "only" a million objects in the
kernel, there are *MANY* more ways to _reach_ those objects, and that is
what git-rev-list --objects does! It's not O(number-of-objects), it's
O(number-of-object-linkages).
For my current kernel archive, for example, the number of objects is
roughly 900k. However, think about how many times we'll actually reach a
blob: that's roughly (blobs per commit)*(number of commits), which can be
approximated with
echo $(( $(git ls-files | wc -l) * $(git rev-list --all | wc -l) ))
which is 24324*108518=2639591832 ie about 2.5 _billion_ times.
Now, we don't actually do anything close to that many lookups, because
when a subdirectory doesn't change at all, we'll skip the whole tree after
having seen it just once, so that will cut down on the number of objects
we have to look up by probably a couple of orders of magnitude.
But this is why the "one large directory" load performs worse: in the
worst case, if you really have a totally flat directory tree, you'd
literally see that 2.5 billion object lookup case.
So it's not that git scales badly. It's that "git rev-list --objects" is
really a very expensive operation, and while some good practices (deep
directory structures) makes it able to optimize the load away a lot, it's
still potentially very tough.
Linus
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:45:09
On Thu, 14 Aug 2008, Linus Torvalds wrote:
On Wed, 13 Aug 2008, Nicolas Pitre wrote:
quoted
A much better solution would consist of finding just _why_ object
enumeration is so slow. This is indeed my biggest grip with git
performance at the moment.
|nico@xanadu:linux-2.6> time git rev-list --objects --all > /dev/null
|
|real 0m21.742s
|user 0m21.379s
|sys 0m0.360s
That's way too long for 1030198 objects (roughly 48k objects/sec).
Why do you think that's horribly slow?
Call it gut feeling. Or 60% CPU wasted in zlib.
Doing a rev-list of all objects is a fairly rare operation, but even if
you want to clone/repack all of your archives the whole time, please
realize that listing objects is _not_ a simple operation. It opens up and
parses every single tree in the whole history. That's a _lot_ of data to
unpack.
I disagree. Well, right _now_ it is not a simple operation. But if you
remember, I'm one of the co-investigator of the pack v4 format which
goal is to make history and tree walking much much cheaper, while making
their packed representation denser too. Even with early prototypes of
the format with the overhead of converting objects back into the current
format on the fly in unpack_entry() the object enumeration was _faster_
than current git.
So this might just be what was needed to bring back some incentive
behind the pack v4 effort.
Nicolas
I disagree. Well, right _now_ it is not a simple operation. But if you
remember, I'm one of the co-investigator of the pack v4 format which
goal is to make history and tree walking much much cheaper, while making
their packed representation denser too.
See my other email with profile data and explanation.
Yes, zlib is high up, but it's not dominant to the point where a packfile
format change would maek a huge difference. You'd still need deltas for
trees, so even if you replaced zlib with something else, you'd still get a
large hit.
You do realize that a lot of the zlib costs are due to cache misses, not
zlib being fundamentally expensive in itself, right? Even if you made the
zlib CPU costs be zero, you still couldn't avoid the _biggest_ cost.
Linus
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:45:09
On Thu, 14 Aug 2008, Linus Torvalds wrote:
Btw, it's not that hard to run oprofile (link git statically to get better
numbers). For me, the answer to what is going on for a kernel rev-list is
pretty straightforward:
263742 26.6009 lookup_object
135945 13.7113 inflate
110525 11.1475 inflate_fast
75124 7.5770 inflate_table
64676 6.5232 strlen
48635 4.9053 memcpy
47744 4.8154 find_pack_entry_one
35265 3.5568 _int_malloc
31579 3.1850 decode_tree_entry
28388 2.8632 adler32
19441 1.9608 process_tree
10398 1.0487 patch_delta
8925 0.9002 _int_free
..
OK, inflate went down since last time I profiled this, but that's
probably because lookup_object went up.
so most of it is in inflate,
Which, again, would be eliminated entirely by pack v4.
but I suspect the cost of "lookup_object()"
is so high becuase when we parse the trees we also have to look up every
blob - even if they didn't change - just to see whether we already saw it
or not.
One optimization with pack v4 was to have delta chunks aligned on tree
records, and because tree objects are no longer compressed, parsing a
tree object could be done by simply walking the delta chain directly.
Then, another optimization would consist of simply skipping any part of
a tree object making a delta reference to a base object which has
already been parsed which would avoid a large bunch of lookup_object()
calls too.
And because
delta base objects are normally seen first in recency order then this
would reduce the combinatorial complexity significantly.
Nicolas
Which, again, would be eliminated entirely by pack v4.
I seriously doubt that.
Nico, it's really easy to say "I wave my magic wand and nothing remains".
It's hard to actually _do_.
One optimization with pack v4 was to have delta chunks aligned on tree
records, and because tree objects are no longer compressed, parsing a
tree object could be done by simply walking the delta chain directly.
Even if you do that, please take a look at the performance characteristics
of modern CPU's.
Here's a hint: the cost of a cache miss is generally about a hundred times
the cost of just about anything else.
So to make a convincing argument, you'd have to show that the actual
memory access patterns are also much better.
No, zlib isn't perfect, and nope, inflate_fast() is no "memcpy()". And
yes, I'm sure a pure memcpy would be much faster. But I seriously suspect
that a lot of the cost is literally in bringing in the source data to the
CPU. Because we just mmap() the whole pack-file, the first access to the
data is going to see the cost of the cache misses.
Linus
Here's a hint: the cost of a cache miss is generally about a hundred times
100 times seems quite optimistic %)
No, zlib isn't perfect, and nope, inflate_fast() is no "memcpy()". And
yes, I'm sure a pure memcpy would be much faster. But I seriously suspect
that a lot of the cost is literally in bringing in the source data to the
CPU. Because we just mmap() the whole pack-file, the first access to the
data is going to see the cost of the cache misses.
I would have thought that zlib has a sequential access pattern that the
CPU prefetchers have a easy time with hiding latency.
BTW I always wonder why people reason about cache misses in oprofile
logs without actually using the cache miss counters.
-Andi
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:45:09
On Thu, 14 Aug 2008, Linus Torvalds wrote:
Here's a hint: the cost of a cache miss is generally about a hundred times
the cost of just about anything else.
So to make a convincing argument, you'd have to show that the actual
memory access patterns are also much better.
No, zlib isn't perfect, and nope, inflate_fast() is no "memcpy()". And
yes, I'm sure a pure memcpy would be much faster. But I seriously suspect
that a lot of the cost is literally in bringing in the source data to the
CPU. Because we just mmap() the whole pack-file, the first access to the
data is going to see the cost of the cache misses.
Possible. However, the fact that both the "Compressing objects" and the
"Writing objects" phases during a repack (without -f) together are
_faster_ than the "Counting objects" phase is a sign that something is
more significant than cache misses here, especially when tree
information is a small portion of the total pack data size.
Of course we can do further profiling, say with core.compression set to
0 and a full repack, or even hacking the pack-objects code to force a
compression level of 0 for tree objects, and possibly commits too since
pack v4 intend to deflate only the log text). Tree objects delta very
well, but they don't deflate well at all.
OK, so I did, and the quick test for the kernel is:
|nico@xanadu:linux-2.6> time git rev-list --all --objects > /dev/null
|
|real 0m14.737s
|user 0m14.432s
|sys 0m0.296s
That's for 1031404 objects, hence we're now talking around 70k
objects/sec instead of 48k objects/sec. _Only_ by removing zlib out of
the equation despite the fact that the pack is now larger. So I bet
that additional improvements from pack v4 could improve things even
more, including the object lookup avoidance optimization I mentioned
previously.
Nicolas
From: Shawn O. Pearce <hidden> Date: 2016-06-15 22:45:09
Andreas Ericsson [off-list ref] wrote:
How does one go about getting the object sizes? rev-list appears
to have no option for it.
With great pain. You can use the output of verify-pack -v to
tell you the size of the inflated portion of the object, but for
a delta this is the inflated size of the delta, not of the fully
unpacked object.
--
Shawn.
Possible. However, the fact that both the "Compressing objects" and the
"Writing objects" phases during a repack (without -f) together are
_faster_ than the "Counting objects" phase is a sign that something is
more significant than cache misses here, especially when tree
information is a small portion of the total pack data size.
Hmm. I think I may have clue.
The size of the delta cache seems to be a sensitive parameter for this
thing. Not so much for the git archive, but working on the kernel tree,
raising it to 1024 seems to give a 20% performance improvement. That, in
turn, implies that we may be unpacking things over and over again because
of bad locality wrt delta generation.
I'm not sure how easy something like that is to fix, though. We generate
the object list in "recency" order for a reason, but that also happens to
be the worst possible order for re-using the delta cache - by the time we
get back to the next version of some tree entry, we'll have cycled through
all the other trees, and blown all the caches, so we'll end up likely
re-doing the whole delta chain.
So it's quite possible that what ends up happening is that some directory
with a deep delta chain will basically end up unpacking the whole chain -
which obviously includes inflating each delta - over and over again.
That's what the delta cache was supposed to avoid..
Looking at some call graphs, for the kernel I get:
- process_tree() called 10 million times
- causing parse_tree() called 479,466 times (whew, so 19 out of 20 trees
have already been seen and can be discarded)
- which in turn calls read_sha1_file() (total: 588,110 times, but there's
a hundred thousand+ commits)
but that actually causes
- 588,110 cals to cache_or_unpack_entry
out of which 5,850 calls hit in the cache, and 582,260 do *not*.
IOW, the delta cache effectively never triggers because the working set is
_way_ bigger than the cache, and the patterns aren't good. So since most
trees are deltas, and the max delta depth is 10, the average depth is
soemthing like 5, and we actually get an ugly
- 1,637,999 calls to unpack_compressed_entry
which all results in a zlib inflate call.
So we actually have three times as many calls to inflate as we even have
objects parsed, due to the delta chains on the trees (the commits almost
never delta-chain at all, much less any deeper than a couple of entries).
So yeah, trees are the problem here, and yes, avoiding inflating them
would help - but mainly because we do it something like four times per
object on average!
Ouch. But we really can't just make the cache bigger, and the bad access
patterns really are on purpose here. The delta cache was not meant for
this, it was really meant for the "dig deeper into the history of a single
file" kind of situation that gets very different patterns indeed.
I'll see if I can think of anything simple to avoid all this unnecessary
work. But it doesn't look too good.
Linus
From: Björn Steinbrink <hidden> Date: 2016-06-15 22:45:09
On 2008.08.14 16:14:26 -0700, Linus Torvalds wrote:
On Thu, 14 Aug 2008, Nicolas Pitre wrote:
quoted
Possible. However, the fact that both the "Compressing objects" and the
"Writing objects" phases during a repack (without -f) together are
_faster_ than the "Counting objects" phase is a sign that something is
more significant than cache misses here, especially when tree
information is a small portion of the total pack data size.
Hmm. I think I may have clue.
The size of the delta cache seems to be a sensitive parameter for this
thing. Not so much for the git archive, but working on the kernel tree,
raising it to 1024 seems to give a 20% performance improvement. That, in
turn, implies that we may be unpacking things over and over again because
of bad locality wrt delta generation.
Since you mention the delta cache, uau (no idea about his real name) on
#git was talking about some delta cache optimizations lately, although
he was dealing with "git log -S", maybe it affects rev-list in a similar
way. Unfortunately, I can't seem to find any code for that, just a
description of what he did and some numbers on the results in the IRC
logs.
http://colabti.org/irclogger/irclogger_log/git?date=2008-08-04,Mon#l65
Maybe that helps in some way.
Björn
Since you mention the delta cache, uau (no idea about his real name) on
#git was talking about some delta cache optimizations lately, although
he was dealing with "git log -S", maybe it affects rev-list in a similar
way. Unfortunately, I can't seem to find any code for that, just a
description of what he did and some numbers on the results in the IRC
logs.
Yes, interesting.
The delta cache was really a huge hack that just turned out rather
successful. It's been hacked on further since (to do some half-way
reasonable replacement with _another_ hack by adding an LRU on top of it),
but it really is very hacky indeed.
The "hash" we use for looking things up is also pretty much a joke, and it
has no overflow capability, it just replaces the old entry with a new one.
I wonder how hard it would be to replace the whole table thing with our
generic hash.c hash thing. I'll take a look.
Linus
I wonder how hard it would be to replace the whole table thing with our
generic hash.c hash thing. I'll take a look.
Ok, I did a quick version that didn't replace anything at all, and it
doesn't look like there is room for that helping much. Yes, I can speed
things up, but it didn't get much faster than just raising the delta cache
to 1024 entries.
Admittedly my quick hack might have been fundamentally flawed, but it was
such an ugly thing that I'm not even going to post it.
And the added memory footprint makes it unacceptable, so it's going to be
limited by the cache size anyway, and not get a lot of hits in git
rev-list, methinks.
Linus
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:45:09
On Thu, 14 Aug 2008, Shawn O. Pearce wrote:
Andreas Ericsson [off-list ref] wrote:
quoted
How does one go about getting the object sizes? rev-list appears
to have no option for it.
With great pain. You can use the output of verify-pack -v to
tell you the size of the inflated portion of the object, but for
a delta this is the inflated size of the delta, not of the fully
unpacked object.
Delta objects have the size of the final object in their header. There
is get_size_from_delta() extracting that information already. There is
simply no interface exporting that info to external tools but that
shouldn't be hard to add.
Nicolas
I would have thought that zlib has a sequential access pattern that the
CPU prefetchers have a easy time with hiding latency.
No, the lookup tables for the patterns are quite non-sequential. It does
do a lot of indirect accesses, ie it loads data from the input stream and
then looks things up through that.
But it's quite possible that we should use different compression factors
for different object types. Right now we have different (configurable)
compression levels for loose objects and packs, but it might be
interesting to see what happens for just "packed tree objects".
The trees really end up having rather different access patterns in
pack-files. They also tend to be rather less compressible than other
blobs, since the SHA1's in there are just random binary data. They also
delta very well - obviously regular blobs do that _too_, but regular blobs
are seldom as performance-critical in git (ie once you actually unpack a
blob, there are other things going on like actually generating a diff -
but trees get unpacked over and over for "internal git reasons")
Linus
So yeah, trees are the problem here, and yes, avoiding inflating them
would help - but mainly because we do it something like four times per
object on average!
Interestingly, it turns out that git also hits a sad performance downside
of using zlib.
We always tend to set "stream.avail_out" to the exact size of the expected
output. And it turns out that that means that the fast-path case of
inffast.c doesn't trigger as often as it could. This (idiotic) patch
actually seems to help performance on git rev-list by about 5%.
But maybe it's just me seeing things. But I did this because of the entry
assumptions in inflate_fast(), that code only triggers for the case of
strm->avail_out >= 258.
Sad, if true.
Linus
---
sha1_file.c | 4 ++--
1 files changed, 2 insertions(+), 2 deletions(-)
From: Björn Steinbrink <hidden> Date: 2016-06-15 22:45:10
On 2008.08.14 17:06:13 -0700, Linus Torvalds wrote:
The "hash" we use for looking things up is also pretty much a joke, and it
has no overflow capability, it just replaces the old entry with a new one.
So I added some stupid tracing to cache_or_unpack entry to see how often
we reread the same stuff. The whole thing just logs the base_offset in
case of a cache miss. I've gc'ed my linux-2.6.git before the run, so
that there's only a single packed_git around (at least I hope so), and I
can ignore that for the tracing.
The whole log for a "git rev-list --objects HEAD" has about 1.2M
entries, while the output of the rev-list command has about 870k lines.
Some postprocessing of the trace shows that the majority of objects is
read only once or twice. A few percent are read three to ten times, and
some are read more than two hundred times.
I'll attach the post-processed thing. The format is:
x y
Meaning that there were x base_offset values for which we had y cache
misses.
Björn