Compression speed for large files

I'm looking at doing version control of data files, potentially very large, often binary. In git, committing of large files is very slow; I have tested with a 45MB file, which takes about 1 minute to check in (on an intel core-duo 2GHz).

Now, most of the time is spent in compressing the file. Would it be a good idea to change the Z_BEST_COMPRESSION flag to zlib, at least for large files? I have measured the time spent by git-commit with different flags in sha1_file.c:

  method                 time (s)  object size (kB)
  Z_BEST_COMPRESSION     62.0      17136
  Z_DEFAULT_COMPRESSION  10.4      16536
  Z_BEST_SPEED            4.8      17071

In this case Z_BEST_COMPRESSION also compresses worse, but that's not the major
issue: the time is. Here's a couple of other data points, measured with gzip -9, -6 and -1 (comparable to the Z_ flags above):

129MB ascii data file

  method    time (s)  object size (kB)
  gzip -9   158       23066
  gzip -6    18       23619
  gzip -1     6       32304

3MB ascii data file

  gzip -9   2.2        887
  gzip -6   0.7        912
  gzip -1   0.3       1134

So: is it a good idea to change to faster compression, at least for larger files? From my (limited) testing I would suggest using Z_BEST_COMPRESSION only for small files (perhaps <1MB?) and Z_DEFAULT_COMPRESSION/Z_BEST_SPEED for larger ones.

-j.

I know this has already been somewhat solved, but I found your numbers curiously high. I work quite a bit with git and large files and I haven't noticed this slowdown. Can you be more specific about your load? Are you sure it is zlib?

On my 1.8Ghz Athlon, compressing 45MB of zeros into 20K takes about 2s. Compressing 45MB of random data into a 45MB object takes 6.3s. In either case, the commit takes only about 0.5s (since cogito stores the object during the cg-add).

Is there some specific file pattern which is slow to compress?

-Peff

Quite sure: at least to the extent that it is fixed by lowering the compression level. But the wording was inexact: it's during object creation, which happens at initial "git add" and then later during "git commit".

But...

yes, it seems so. At least the effect is much more pronounced for my files than for random/null data. "My" files are in this context generated data files, binary or ascii.

Here's a test with "time gzip -[169] -c file >/dev/null". Random data from /dev/urandom, kernel headers are concatenation of *.h in kernel sources. All times in seconds, on my puny home computer (1GHz Via Nehemiah)

       random (23MB)  data (23MB)   headers (44MB)
-9     10.2           72.5          38.5
-6     10.2           13.5          12.9

-1 9.9 4.1 7.0

So... data dependent, yes. But it hits even for normal source code.

(Btw; the default (-6) seems to be less data dependent than the other values. Maybe that's on purpose.)

If you want to look at a highly-variable dataset (the one above), try
http://lupus.ig3.net/SIMULATION.dx.gz (5MB, slow server), but that's just an example, I see the same variability for example also on binary data files.

-j.

That "Via Nehemiah" is probably a big part of it.

I think the VIA Nehemiah just has a 64kB L2 cache, and I bet performance plummets if the tables end up being used past that.

And I think a large part of the higher compressions is that they allow the compression window and tables to grow bigger.

Linus

Not really. The numbers in my original post were from a Intel core-duo, they were: 158/18/6 s for comparable (but larger) data.

And on a P4 1.8GHz with 512kB L2, the same 23MB data file compresses in 28.1/5.9/1.3 s. That's a factor 22 slowest/fastest; the VIA was only factor 18, so the difference is actually *larger*.

-j.

Probably yes, as a per-repo config option.

I can send a patch later. If it's to be a per-repo option, it's probably too confusing with several values. Is it ok with

core.compression = [-1..9]

where the numbers are the zlib/gzip constants,
-1 = zlib default (currently 6)
0 = no compression
1..9 = various speed/size tradeoffs (9 is git default)

Btw; I just tested the kernel sources. With gzip only, but files compressed individually:
time find . -type f | xargs gzip -9 -c | wc -c

I found the space saving from -6 to -9 to be under 0.6%, at double the CPU time. So perhaps Z_DEFAULT_COMPRESSION would be good as default.

-j

I think this makes a lot of sense, although IMHO I'd simply use Z_DEFAULT_COMPRESSION everywhere and be done with it without extra complexity which aren't worth the size difference.

Nicolas

I think Z_DEFAULT_COMPRESSION is fine too - we've long since started relying on pack-files and the delta compression for the _real_ size improvements, and as such, the zlib compression is less important.

That said, the "core.compression" thing sounds good to me, and gives people the ability to tune things for their loads.

Linus

This one I'm not so sure about, it's for completeness. But I don't actually use git and haven't tested beyond the git add / git commit stage. Still...

---
 csum-file.c |    2 +-
 diff.c      |    2 +-
 http-push.c |    2 +-
 3 files changed, 3 insertions(+), 3 deletions(-)

index ebaad03..6a7b40f 100644
@@ -122,7 +122,7 @@ int sha1write_compressed(struct sha1file
        void *out;
 
        memset(&stream, 0, sizeof(stream));
-       deflateInit(&stream, Z_DEFAULT_COMPRESSION);
+       deflateInit(&stream, zlib_compression_level);
        maxsize = deflateBound(&stream, size);
        out = xmalloc(maxsize);
 

index 5a71489..428ff78 100644
@@ -583,7 +583,7 @@ static unsigned char *deflate_it(char *d
        z_stream stream;
 
        memset(&stream, 0, sizeof(stream));
-       deflateInit(&stream, Z_BEST_COMPRESSION);
+       deflateInit(&stream, zlib_compression_level);
        bound = deflateBound(&stream, size);
        deflated = xmalloc(bound);
        stream.next_out = deflated;

index e281f70..f761584 100644
@@ -492,7 +492,7 @@ static void start_put(struct transfer_re
 
        /* Set it up */
        memset(&stream, 0, sizeof(stream));
-       deflateInit(&stream, Z_BEST_COMPRESSION);
+       deflateInit(&stream, zlib_compression_level);
        size = deflateBound(&stream, len + hdrlen);
        request->buffer.buffer = xmalloc(size);
 

1.4.1.g8fced-dirty

You made a good judgement to notice that these three are different.

* sha1write_compressed() in csum-file.c is for producing packs and most of the things we compress there are deltas and less compressible, so even when core.compression is set to high we might be better off using faster compression.

* diff's deflate_it() is about producing binary diffs (later encoded in base85) for textual transfer. Again it is almost always used to compress deltas so the same comment as above apply to this.

* http-push uses it to send compressed whole object, and this is only used over the network, so it is plausible that the user would want to use different compression level than the usual core.compression.

It is fine by me to use the same core.compression to these three. If somebody comes up with a workload that benefits from having different settings for them, we can add separate variables, falling back on the default core.compression if there isn't one, as needed.

Thanks for the patches.

why would deltas have poor compression? I'd expect them to have about the same as the files they are deltas of (or slightly better due to the fact that the deta metainfo is highly repetitive)

David Lang

Hi,

Deltas should have poor compression by definition, because compression tries to encode those parts of the file more efficiently, which do not bear much information (think entropy).

If you have deltas which really make sense, they are almost _pure_ information, i.e. they do not contain much redundancy, as compared to real files. So, the compression (which does not know anything about the characteristics of deltas in particular) cannot take much redundancy out of the delta. Therefore, the entropy is very high, and the compression rate is low.

Hope this makes sense to you,
Dscho

Make zlib compression level configurable, and change the default.

With the change in default, "git add ." on kernel dir is about twice as fast as before, with only minimal (0.5%) change in object size. The speed difference is even more noticeable when committing large files, which is now up to 8 times faster.

The configurability is through setting core.compression = [-1..9] which maps to the zlib constants; -1 is the default, 0 is no compression, and 1..9 are various speed/size tradeoffs, 9 being slowest.

---
 Documentation/config.txt |    6 ++++++
 cache.h                  |    1 +
 config.c                 |    5 +++++
 environment.c            |    1 +
 sha1_file.c              |    4 ++--
 5 files changed, 15 insertions(+), 2 deletions(-)

index a04c5ad..ac89be7 100644
@@ -91,6 +91,12 @@ core.warnAmbiguousRefs::
        If true, git will warn you if the ref name you passed it is ambiguous
        and might match multiple refs in the .git/refs/ tree. True by default.
 
+core.compression:
+       An integer -1..9, indicating the compression level for objects that
+       are not in a pack file. -1 is the zlib and git default. 0 means no 
+       compression, and 1..9 are various speed/size tradeoffs, 9 being
+       slowest.
+
 alias.*::
        Command aliases for the gitlink:git[1] command wrapper - e.g.
        after defining "alias.last = cat-file commit HEAD", the invocation

index 8719939..84770bf 100644
@@ -183,6 +183,7 @@ extern int log_all_ref_updates;
 extern int warn_ambiguous_refs;
 extern int shared_repository;
 extern const char *apply_default_whitespace;
+extern int zlib_compression_level;
 
 #define GIT_REPO_VERSION 0
 extern int repository_format_version;

index ec44827..61563be 100644
@@ -279,6 +279,11 @@ int git_default_config(const char *var, 
                return 0;
        }
 
+       if (!strcmp(var, "core.compression")) {
+               zlib_compression_level = git_config_int(var, value);
+               return 0;
+       }
+
        if (!strcmp(var, "user.name")) {
                strlcpy(git_default_name, value, sizeof(git_default_name));
                return 0;

index 3de8eb3..1d8ceef 100644
@@ -20,6 +20,7 @@ int repository_format_version = 0;
 char git_commit_encoding[MAX_ENCODING_LENGTH] = "utf-8";
 int shared_repository = PERM_UMASK;
 const char *apply_default_whitespace = NULL;
+int zlib_compression_level = -1;
 
 static char *git_dir, *git_object_dir, *git_index_file, *git_refs_dir,
        *git_graft_file;

index 8179630..bc35808 100644
@@ -1458,7 +1458,7 @@ int write_sha1_file(void *buf, unsigned 
 
        /* Set it up */
        memset(&stream, 0, sizeof(stream));
-       deflateInit(&stream, Z_BEST_COMPRESSION);
+       deflateInit(&stream, zlib_compression_level);
        size = deflateBound(&stream, len+hdrlen);
        compressed = xmalloc(size);
 

@@ -1511,7 +1511,7 @@ static void *repack_object(const unsigne
 
        /* Set it up */
        memset(&stream, 0, sizeof(stream));
-       deflateInit(&stream, Z_BEST_COMPRESSION);
+       deflateInit(&stream, zlib_compression_level);
        size = deflateBound(&stream, len + hdrlen);
        buf = xmalloc(size);
 

1.4.1.g8fced-dirty

My only worry is that this encodes "Z_DEFAULT_COMPRESSION" as being -1, which happens to be /true/, but I don't think that's a documented interface (you're supposed to use the Z_DEFAULT_COMPRESSION macro, which could have any value, and just _happens_ to be -1).

Is it likely to ever change from that -1? Probably not. So I think your patch is technically correct, but it might just be nicer if it did something like

	..
	if (!strcmp(var, "core.compression")) {
		int level = git_config_int(var, value);
		if (level == -1)
			level = Z_DEFAULT_COMPRESSION;
		else if (level < 0 || level > Z_BEST_COMPRESSION)
			die("bad zlib compression level %d", level);
		zlib_compression_level = level;
		return 0;
	}
	..

which would be safer, and a smart compiler might notice that the -1 case ends up being a no-op, and then just generate code AS IF we just had a

	if (level < -1 || level > Z_BEST_COMPRESSION)
		die(...

there.

Oh, and for all the same reasons, we should use

	int zlib_compression_level = Z_BEST_COMPRESSION;

for the default initializer.

Hmm?

Linus

Yes, that would be more... thorough. And, especially for the

  int zlib_compression_level = Z_DEFAULT_COMPRESSION;

line, more self-explanatory, too. So here's an updated patch (replacing the previous) including your suggestions.

-j.

-

Make zlib compression level configurable, and change default.

With the change in default, "git add ." on kernel dir is about twice as fast as before, with only minimal (0.5%) change in object size. The speed difference is even more noticeable when committing large files, which is now up to 8 times faster.

The configurability is through setting core.compression = [-1..9] which maps to the zlib constants; -1 is the default, 0 is no compression, and 1..9 are various speed/size tradeoffs, 9 being slowest.

---
 Documentation/config.txt |    6 ++++++
 cache.h                  |    1 +
 config.c                 |   10 ++++++++++
 environment.c            |    1 +
 sha1_file.c              |    4 ++--
 5 files changed, 20 insertions(+), 2 deletions(-)

index a04c5ad..ac89be7 100644
@@ -91,6 +91,12 @@ core.warnAmbiguousRefs::
        If true, git will warn you if the ref name you passed it is ambiguous
        and might match multiple refs in the .git/refs/ tree. True by default.
 
+core.compression:
+       An integer -1..9, indicating the compression level for objects that
+       are not in a pack file. -1 is the zlib and git default. 0 means no 
+       compression, and 1..9 are various speed/size tradeoffs, 9 being
+       slowest.
+
 alias.*::
        Command aliases for the gitlink:git[1] command wrapper - e.g.
        after defining "alias.last = cat-file commit HEAD", the invocation

index 8719939..84770bf 100644
@@ -183,6 +183,7 @@ extern int log_all_ref_updates;
 extern int warn_ambiguous_refs;
 extern int shared_repository;
 extern const char *apply_default_whitespace;
+extern int zlib_compression_level;
 
 #define GIT_REPO_VERSION 0
 extern int repository_format_version;

index ec44827..b23f4bf 100644
@@ -279,6 +279,16 @@ int git_default_config(const char *var, 
                return 0;
        }
 
+       if (!strcmp(var, "core.compression")) {
+               int level = git_config_int(var, value);
+               if (level == -1)
+                       level = Z_DEFAULT_COMPRESSION;
+               else if (level < 0 || level > Z_BEST_COMPRESSION)
+                       die("bad zlib compression level %d", level);
+               zlib_compression_level = level;
+               return 0;
+       }
+
        if (!strcmp(var, "user.name")) {
                strlcpy(git_default_name, value, sizeof(git_default_name));
                return 0;

index 3de8eb3..43823ff 100644
@@ -20,6 +20,7 @@ int repository_format_version = 0;
 char git_commit_encoding[MAX_ENCODING_LENGTH] = "utf-8";
 int shared_repository = PERM_UMASK;
 const char *apply_default_whitespace = NULL;
+int zlib_compression_level = Z_DEFAULT_COMPRESSION;
 
 static char *git_dir, *git_object_dir, *git_index_file, *git_refs_dir,
        *git_graft_file;

index 8179630..bc35808 100644
@@ -1458,7 +1458,7 @@ int write_sha1_file(void *buf, unsigned 
 
        /* Set it up */
        memset(&stream, 0, sizeof(stream));
-       deflateInit(&stream, Z_BEST_COMPRESSION);
+       deflateInit(&stream, zlib_compression_level);
        size = deflateBound(&stream, len+hdrlen);
        compressed = xmalloc(size);
 

@@ -1511,7 +1511,7 @@ static void *repack_object(const unsigne
 
        /* Set it up */
        memset(&stream, 0, sizeof(stream));
-       deflateInit(&stream, Z_BEST_COMPRESSION);
+       deflateInit(&stream, zlib_compression_level);
        size = deflateBound(&stream, len + hdrlen);
        buf = xmalloc(size);
 

1.4.1.g8fced-dirty

That should be Z_DEFAULT_COMPRESSION, of course.

Anyway, I think the patches are ok as-is, and my suggestion to avoid the "-1" and use Z_DEFAULT_COMPRESSION is really just an additional comment, not anything fundamental.

So Junio, feel free to add an

regardless of whether also doing that.

Linus

It would be arguable whether, say, 10% better compression is worth x(3-8) slower compression. But 3-4% better compression at the cost of x(3-8) slower compression time as data suggest ? I think this begs for switching the default to Z_DEFAULT_COMPRESSION

Yakov

Hi,

The real problem, of course, is that you cannot know before you tried, if your data is really well compressible or not.

Ciao,
Dscho

Joachim B Haga <cjhaga <at> fys.uio.no> writes:
[...]

[...]

I personally find that very interesting, is this a known "issue" with zlib? It suggests, that with different options, it's possible to create smaller repositories, despite the 'advertised' (by zlib, not git) "best" compression.

Alex Riesen <raa.lkml <at> gmail.com> writes:
[...]

The option probably should be the size for which to start using "default" compression.

Elrond

There are also other tunables in zlib, such as the balance between Huffman coding (good for data files) and string matching (good for text files). So with more knowledge of the data it should be possible to compress even better. I'm not advocating tuning this in git though ;)

That is possible, too. I'm open to any decision or consensus, as long as I get my commits in less than 10s :)

-j.