From: Junio C Hamano <hidden> Date: 2016-06-15 22:44:02
Linus Torvalds [off-list ref] writes:
On Sun, 30 Dec 2007, Junio C Hamano wrote:
quoted
With this patch, we actually see slight improvements in
execution time as well. In the same partial kde repository
(3.0GB pack, 95MB idx; the numbers are from the same machine as
before, best of 5 runs):
Ok, I tried this a year ago, and never got any real improvement.
Yes, I remember that one.
and I decided it wasn't worth it. Yours looks much better, and seems to
get a real performance improvement, so go for it, but I doubt that the
actual object lookup is really ever the main issue. I've never seen it
stand out in the real profiles, although if it is able to cut down on IO
(and your minor fault numbers are promising!), it might be more important
than I'd otherwise think.
The cost of the key comparison done in each round is
insignificant compared to the actual cost of accessing the
object data through zlib. The only potential performance
benefit that could come from this patch to reduce the average
number of rounds in the search is I/O reduction.
The only case I can think of that this may matter in real life
is accessing only small number of objects in a history with a
huge pack. Once you dig down the history deep enough to check
enough number of objects inside a single process, you would need
to touch every page of the mapped idx and the minor-fault gain
rapidly diminishes.
Accessing only small number of objects in a huge history most
often happens when building near the tip of the history
(e.g. commit, rebase, merge), but these operations tend to deal
with very young objects, often unpacked. We check pack first
and then loose objects, so the search for young loose objects
will benefit from the patch because the negative look-up to
notice that they do not live in any pack also becomes cheaper,
but I do not think it is such a big deal.
From: Marco Costalba <hidden> Date: 2016-06-15 22:44:02
On Dec 30, 2007 10:49 PM, Junio C Hamano [off-list ref] wrote:
Linus Torvalds [off-list ref] writes:
The cost of the key comparison done in each round is
insignificant compared to the actual cost of accessing the
object data through zlib.
Sorry to ask, but just out of curiosity, what were the reasons to
choose zlib compression algorithm among the possible ones?
There is a thread where this has been discussed in the past? Sorry to
ask but I didn't find such a thread myself.
Thanks
Marco
Sorry to ask, but just out of curiosity, what were the reasons to
choose zlib compression algorithm among the possible ones?
It's out there, it's common, it's stable, and it's very good "on average".
In other words, other compression methods tend to be worse. No, zlib isn't
perfect, but it was the obvious default choice for me (I've used it
before, we use it in the kernel, it's usually good enough), and I actually
expected the SHA1 to be the bigger expense.
Even today, I don't really know of a better compression choice, despite
now being more aware of how critical uncompression performance is.
And quite honestly I'm not really even sure that the performance downside
is entirely about zlib itself: I suspect a lot of the reason zlib shows up
in the profiles is that the source data is usually cold in the cache, so
it probably takes a lot of cache misses (it also will take all the page
faults!).
Quite possibly, the cache miss costs dominate over any algorithmic costs.
Linus
From: Marco Costalba <hidden> Date: 2016-06-15 22:44:02
On Dec 31, 2007 9:37 PM, Linus Torvalds [off-list ref] wrote:
Even today, I don't really know of a better compression choice, despite
now being more aware of how critical uncompression performance is.
In the kernel, from not long ago, is used also LZO compression that
_seems_ much faster to decompress then zlib
http://lkml.org/lkml/2007/5/1/297
The developer, Richard Purdie, says it's also 40% faster to read for jffs2.
Quite possibly, the cache miss costs dominate over any algorithmic costs.
What way could be used to build up a test to check this?
Thanks
Marco
From: Jeff King <hidden> Date: 2016-06-15 22:44:02
On Mon, Dec 31, 2007 at 12:37:36PM -0800, Linus Torvalds wrote:
And quite honestly I'm not really even sure that the performance downside
is entirely about zlib itself: I suspect a lot of the reason zlib shows up
in the profiles is that the source data is usually cold in the cache, so
it probably takes a lot of cache misses (it also will take all the page
faults!).
zlib makes a noticeable impact in real world cases. On a git.git repo,
fully packed with stock config, warm cache:
$ /usr/bin/time git whatchanged >/dev/null
4.12user 0.37system 0:04.50elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+6452minor)pagefaults 0swaps
$ git config pack.compression 0
$ git repack -a -d -f
$ /usr/bin/time git whatchanged >/dev/null
2.93user 0.43system 0:03.36elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+8501minor)pagefaults 0swaps
More pagefaults, but a 25% improvement in wall clock time. The packfile
is noticeably larger (55M versus 40M), so I'm sure the cold cache case
sucks. It may also change with larger repos, where the packfile size
difference kills your cache.
-Peff
From: Marco Costalba <hidden> Date: 2016-06-15 22:44:02
On Jan 1, 2008 7:36 AM, Jeff King [off-list ref] wrote:
The packfile is noticeably larger (55M versus 40M)
Well 55M versus 40M is _only_ 27% of compression ratio. It means that
the compression algorithm is not so fundamental because the data is
already, how to say, well packaged.
IOW if a compression algorithm X is say 30% less size efficient then
zlib it means that the final packfile size using X would be 44.5M
instead of 40M, i.e. only 11% bigger then using zlib.
Marco
From: Marco Costalba <hidden> Date: 2016-06-15 22:44:02
On Jan 1, 2008 9:40 AM, Marco Costalba [off-list ref] wrote:
On Jan 1, 2008 7:36 AM, Jeff King [off-list ref] wrote:
quoted
The packfile is noticeably larger (55M versus 40M)
Well 55M versus 40M is _only_ 27% of compression ratio. It means that
the compression algorithm is not so fundamental because the data is
already, how to say, well packaged.
I think zlib is a very good general purpose algorithm, but is main
strength is to give good final file sizes, it is mainly intended for
files that are seldom decompressed.
For the use we do in git IMHO it would seem appropriate to look for
algorithms used in the field of filesystem compression, where
decompression penalty is a design goal. I know very little about this
but I think among kernel people, expert and competent hackers should
not be difficult to find, given that compressed filesystem are around
from many years under linux/fs/ directory.
Marco
More pagefaults, but a 25% improvement in wall clock time. The packfile
is noticeably larger (55M versus 40M), so I'm sure the cold cache case
sucks. It may also change with larger repos, where the packfile size
difference kills your cache.
The packfile is _incredibly_ larger (~200Mo -> ~420, though I suppose
the first one was packed with a larger window, coming from kernel.org).
I experience the same 25% wall clock reduction here as well. Though,
even if larger, linux-2.6.git still stays in RAM easily on my machine.
On an unrelated note, I wonder if it wouldn't be possible for git at
fetch time to "share" a very efficient pack that was computed on some
host. I mean, if I'm not mistaken, at clone time you get the efficient
pack, but at fetch time only incremental parts. I wonder if there would
be ways to say "hey, we recomputed here a very very very good pack, take
it instead of yours.
--
·O· Pierre Habouzit
··O madcoder@debian.org
OOO http://www.madism.org