Performance of various compressors

I started rolling a tool to measure various aspects of git performance. I will start looking at merge next, and at workloads different from the kernel (gcc4 anyone?) ...

The only data points worth sharing a this point are:

That doing the compression at a level of 3, rather than the max of 9, cuts the cpu time required for a big git commit by over half, and that that actually translates into a win on the I/O to disk. (these tests were performed on a dual opteron 842)

The benefits of compression aren't very much for git right now.

And: A big git commit is I/O bound. But we knew that. Maybe it's possible to make it less I/O bound.

Git branch: 7a4c67965de68ae7bc7aa1fde33f8eb9d8114697
Tree: 2.6.11.7 source tree
Branch: N/a
Merge File: N/a
HW: dual opteron 242
Mem: 1GB
Disk: seagate barracuda
Filesystem: Reiser3
Git add: N/a
Cache: Hot
Git Commit: 44.97user 5.94system 1:45.24elapsed 48%CPU Git Merge:
Options:
Feature: Test of compression=9 (std git)

du -s .git/objects 110106 # du is probably not the right thing du -s --apparent-size .git/objects 58979

Git branch: 9e272677621c91784cf2533123a41745178f0701
Tree: 2.6.11.7 source tree
Branch: N/a
Merge File: N/a
HW: dual opteron 242
Mem: 1GB
Disk: seagate barracuda
Disk mode: udma5
Filesystem: Reiser3
Git add: N/a
Cache: Hot
Git Commit: 16.79user 6.15system 1:21.92elapsed 28%CPU Git Merge:
Options:
Feature: Test of compression=3 (std git)

du -s .git/objects 115218
du -s --apparent-size .git/objects 64274

There's some variety in the best/worst case timings for I/O for the compressor=3 case...

16.79user 6.15system 1:21.92elapsed 28%CPU
16.68user 5.71system 1:13.19elapsed 30%CPU

Mike Taht


lastly -

Timings of git commit with tmpfs (note, these were done with an ancient, 5 hour old version of git and the script)

Hot cache, tmpfs .git compression=9
44.97user 2.76system 0:47.72elapsed 100%CPU

Hot cache, tmpfs .git, compression=6
Wed Apr 20 20:18:11 PDT 2005
23.55user 2.83system 0:26.36elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+568680minor)pagefaults 0swaps
109620  .git/objects
58618   .git/objects

Just to clarify this was a git add of the linux-2.6.11.7 sources (sorry, untimed) , and timing the git commit.

Mo betta data latah.

Mike Taht


  "The chief contribution of Protestantism to human thought is its 
massive proof
that God is a bore.
	-- H.L. Mencken, "The Aesthetic Recoil," American Mercury, July, 1931."

Don't apply this patch and change GIT_COMPRESSION unless you know what you are doing and why you are doing it. You will break an older version of git. You may break a newer version of git. You have been warned.

I also note that there's a bzlib out there.

cache.h: 828d660ab82bb35a1ca632a2ba4620dc483889bd

@@ -16,6 +16,8 @@
 #include <openssl/sha.h>
 #include <zlib.h>
 
+#define GIT_COMPRESSION Z_BEST_COMPRESSION
+
 /*
  * Basic data structures for the directory cache
  *

sha1_file.c: 754e8b4e9ea8104df48152f875d6b874304e2a62

@@ -199,7 +199,7 @@ int write_sha1_file(char *buf, unsigned
 
        /* Set it up */
        memset(&stream, 0, sizeof(stream));
-       deflateInit(&stream, Z_BEST_COMPRESSION);
+       deflateInit(&stream, GIT_COMPRESSION);
        size = deflateBound(&stream, len);
        compressed = malloc(size);
 

update-cache.c: a09883541c745c76413c62109a80f40df4b7a7fb

@@ -40,7 +40,7 @@ static int index_fd(unsigned char *sha1,
        SHA1_Final(sha1, &c);
 
        memset(&stream, 0, sizeof(stream));
-       deflateInit(&stream, Z_BEST_COMPRESSION);
+       deflateInit(&stream, GIT_COMPRESSION);
 
        /*
         * ASCII size + nul byte

Mike Taht


  ""His mind is like a steel trap -- full of mice."
	-- Foghorn Leghorn"

Hi,

I supply a patch that dehardcodes the path to bash (which is not /bin on all computers) and adds sys/limits.h to provide ULONG_MAX.

If this is not the right way to supply patches, or if this email misses some crucial point please tell me so, and supply explanation.

Robert Suetterlin ([email protected])
phone: (+49)89 / 30000-3546   fax: (+49)89 / 30000-3950

commit 5f6caff82b1f3b5931d92aaff99be6d8dbad10ca
tree d7ea8aeefbbc2ab63cb5acd41b647b1b5f11fb83
parent cd1c034369b73da7503da365fa556aab27004814
author Klaus Robert Suetterlin <[email protected]> 1114078431 +0200
committer Klaus Robert Suetterlin <[email protected]> 1114078431 +0200

Don't hardcode the path-to-bash please.

Index: commit.c
===================================================================
--- c0260bfb82da04aeff4e598ced5295d6ae2e262d/commit.c  (mode:100644 sha1:eda45d7e15358ed6f2cd0502de2a08987307fc98)
+++ d7ea8aeefbbc2ab63cb5acd41b647b1b5f11fb83/commit.c  (mode:100644 sha1:cfe9a8ddf6ee2702e3923cb22240f9f9ed1bd04c)
@@ -1,3 +1,4 @@
+#include <sys/limits.h>
 #include "commit.h"
 #include "cache.h"
 #include <string.h>
Index: gitdiff-do
===================================================================
--- c0260bfb82da04aeff4e598ced5295d6ae2e262d/gitdiff-do  (mode:100755 sha1:afed4e40b259a61b0f12979ba7326f26743bc553)
+++ d7ea8aeefbbc2ab63cb5acd41b647b1b5f11fb83/gitdiff-do  (mode:100755 sha1:218dfabeb4a5dcbd2cf58bd6f672f385690ec397)
@@ -1,4 +1,4 @@
-#!/bin/bash
+#!/usr/bin/env bash
 #
 # Make a diff between two GIT trees.
 # Copyright (c) Petr Baudis, 2005
Index: gitlog.sh
===================================================================
--- c0260bfb82da04aeff4e598ced5295d6ae2e262d/gitlog.sh  (mode:100755 sha1:a496a864f9586e47a4d7bd3ae0af0b3e07b7deb8)
+++ d7ea8aeefbbc2ab63cb5acd41b647b1b5f11fb83/gitlog.sh  (mode:100755 sha1:7b3aa8a89bc64273c648920ccd1686859754803e)
@@ -1,4 +1,4 @@
-#!/bin/bash
+#!/usr/bin/env bash
 #
 # Make a log of changes in a GIT branch.
 #

Hi, i did a similar patch a while back ago. As for ULONG_MAX, not every sytem has <sys/limits.h>, i think <limits.h> is the rite place to go.

The patch below tested on both debian and fbsd.

commit 2deea74db72fb57a8b80e7945f23814112b22723
tree 0c92ac3af53457b6b9651cf82d98ce3a7b166dcd
parent cd1c034369b73da7503da365fa556aab27004814 author Alecs King <alecsk ! gmail d@t com> 1114075114 +0800 committer Alecs King <alecsk ! gmail d@t com> 1114075114 +0800

trivial fix for making it more portable

Index: commit-tree.c
===================================================================
@@ -252,7 +252,7 @@
 
 	then -= offset;
 
-	snprintf(result, maxlen, "%lu %5.5s", then, p);
+	snprintf(result, maxlen, "%lu %5.5s", (unsigned long) then, p);
 }
 
 static void check_valid(unsigned char *sha1, const char *expect)

Index: commit.c
===================================================================
@@ -1,6 +1,7 @@
 #include "commit.h"
 #include "cache.h"
 #include <string.h>
+#include <limits.h>
 
 const char *commit_type = "commit";
 

Index: gitdiff-do
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/bash
+#!/usr/bin/env bash
 #
 # Make a diff between two GIT trees.
 # Copyright (c) Petr Baudis, 2005

Index: gitlog.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/bash
+#!/usr/bin/env bash
 #
 # Make a log of changes in a GIT branch.
 #

Index: revision.h
===================================================================
@@ -10,6 +10,7 @@
  * definition for this rev, and not just seen it as
  * a parent target.
  */
+#include <limits.h>
 #define marked(rev)	((rev)->flags & 0xffff)
 #define SEEN 0x10000
 #define USED 0x20000

Alecs King

And as for bash, only gitdiff-do and gitlog.sh 'explicitly' use bash instead of /bin/sh. On most Linux distros, /bin/sh is just a symbolic link to bash. But not on some others. I found gitlsobj.sh could not work using a plain /bin/sh on fbsd. To make life easier, i think it might be better if we all explicitly use bash for all shell scripts.

patch below assumes the patch above has been applied.

commit 341cd1241815178d567ce612c97c2bb5a663021a
tree abb16c39fe8354383b632f7fa9dd4611ff66e1d1
parent 2deea74db72fb57a8b80e7945f23814112b22723 author Alecs King <alecsk ! gmail d@t com> 1114107613 +0800 committer Alecs King <alecsk ! gmail d@t com> 1114107613 +0800

Explicitly use bash
#!/bin/sh ==> #!/usr/bin/env bash

Index: gitXlntree.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Provide an independent view to the objects database.
 # Copyright (c) Petr Baudis, 2005

Index: gitXnormid.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Internal: Normalize the given ID to a tree ID.
 # Copyright (c) Petr Baudis, 2005

Index: gitadd.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Add new file to a GIT repository.
 # Copyright (c) Petr Baudis, 2005

Index: gitaddremote.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Add new "remote" to the GIT repository.
 # Copyright (c) Petr Baudis, 2005

Index: gitapply.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Apply a diff generated by git diff.
 # Copyright (c) Petr Baudis, 2005

Index: gitcancel.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Cancels current edits in the working tree.
 # Copyright (c) Petr Baudis, 2005

Index: gitcommit.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Commit into a GIT repository.
 # Copyright (c) Petr Baudis, 2005

Index: gitdiff.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Make a diff between two GIT trees.
 # Copyright (c) Petr Baudis, 2005

Index: gitexport.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Exports a particular revision from a GIT repository.
 # Copyright (c) Johannes E. Schindelin, 2005

Index: gitfork.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Create a branch sharing the objects database.
 # Copyright (c) Petr Baudis, 2005

Index: gitinit.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Initialize a GIT repository.
 # Copyright (c) Petr Baudis, 2005

Index: gitls.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # List contents of a particular tree in a GIT repository.
 # Copyright (c) Petr Baudis, 2005

Index: gitlsobj.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # List objects of the GIT repository.
 # Copyright (c) Randy Dunlap, 2005

Index: gitlsremote.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Lists remote GIT repositories
 # Copyright (c) Steven Cole 2005

Index: gitmerge-file.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Copyright (c) Linus Torvalds, 2005
 #

Index: gitmerge.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Merge a branch to the current tree.
 # Copyright (c) Petr Baudis, 2005

Index: gitpatch.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Make a patch from a given commit.
 # Copyright (c) Petr Baudis, 2005

Index: gitpull.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Pulls changes from "remote" to the local GIT repository.
 # Copyright (c) Petr Baudis, 2005

Index: gitrm.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Remove a file from a GIT repository.
 # Copyright (c) Petr Baudis, 2005

Index: gitseek.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Seek the working tree to a given commit.
 # Copyright (c) Petr Baudis, 2005

Index: gitstatus.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Show status of entries in your working tree.
 # Copyright (c) Petr Baudis, 2005

Index: gittag.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Mark certain commit by a tag.
 # Copyright (c) Petr Baudis, 2005

Index: gittrack.sh
===================================================================
@@ -1,4 +1,4 @@
-#!/bin/sh
+#!/usr/bin/env bash
 #
 # Makes your working tree track the given branch.
 # Copyright (c) Petr Baudis, 2005

Alecs King

How about #!/bin/bash (build from .in files if you feel it necessary to support systems which don't have bash in /bin) instead of doubling the number of execs?

-hpa

If # of execs is that critical, it probably should not be in bash anyway. OpenBSD (at least 3.1)'s bash appears to be in /usr/local/bin/bash, NOT /bin/bash.
I'd go with the /bin/env solution for now;
it maximizes the "it just works" factor, and
when it comes time for .in files much of the cogito code (at least) will probably be rewritten in Perl, and anything performance-sensitive will be in C.

--- David A. Wheeler

Makes sense.

-hpa

If (de)compression is slowing things down, you might want to check out lzo (http://www.oberhumer.com/opensource/lzo/). I tested it on the 2.6.11 kernel source and found that lzo -7 output is only 2% larger than gzip -3, but lzo decompression is almost 3 times faster. The downside is that lzo took 5 times longer to perform the compression at -7. Compression with lzo -3 is 3.5 times faster than gzip -3, but it produces a file that's 37% bigger. Unfortunately, lzo has no settings in between -3 and -7. I'd expect git to be more sensitive to decompression speeds, though.

BTW, lzo decompression speed is not affected by the compression level.

I did some statistics on the freebsd /usr/src/sys directory, as I did not have access to the linux kernel sources.

This is 5435 Files, of about 81MB (according to du -sh). I did

find sys/ -type f -exec gzip -9 {} +
find sys/ -type f -exec gzip -d {} +

and similar calls to get an impression how different compression levels and compressors will act on the data most likely handled by git backend storage.

On a 700MHz p3, UDMA33, freebsd 5.3, ffs (soft updates) I get:

compressor | levels (size, time to compress, time to uncompress)
-----------+-------------------------------------------------------------------

gzip       | 9 (28M, 1:19, 30), 6 (28M, 31.7, 30), 3 (30M, 26.1, 28.7)
           | 1 (31M, 23.6, 29.8)
bzip2      | 9 (27M, 2:14, 37.4) 6 (27M, 2:11, 38.8) 3 (27M, 2:10, 38.3)
lzop       | 9 (32M, 2:15, 35.4) 7 (32M, 57.9, 40.3) 3 (39M, 36.0, 44.4)

These speeds are for the case that our work set fits into filesystem caches. This will be the most common case --- as normal commits will not checkin the whole tree.

That is. We should really use gzip -6. It results in the best compression at a reasonable time. bzip2 can't really compress those tiny files efficiently. lzop is limited by open/close (see below).

BTW. I also did this for the whole /usr/src of freebsd (which is 35000 files and 350MB, du -sh gives 398MB). The numbers look best for gzip -6.

The files we work with seem to have an average uncompressed size of 10-15kB and seem to compress by about a factor of three.

So I did a test in C: open("file%d"), write(file, buf, 10000), close(file). I repeated this for 35000 files as in the freebsd src case, to get some statistics. The gprof output tells me, that open+close take the same ammount of time as the write. (You should really try do to rm test[0-9]* on those 35000 files :)) I wrote the full 10000 bytes, to check for the case when we have no compression at all. When compression gets better we will become more and more open/close limited.

This means we are open/close limited in git. Even if we compress the files to zero size, we cannot get faster than by a factor of two!

Earlier messages in this thread showed that we are also limited by filesytem cache, so we should use compression and efficient prefetch to get best performance out of it. Because even if we cannot get faster than by a factor of two through compression (even delta compression won't help! It would make things worse IMHO) we can get a lot worse (like ten times slower) for large sets on slow machines with few memory.

I also tried to get a better ratio by using the standard db.h btree database, so I wouldn't have to open and close all those files. Unfortunately the btree is about twice as large as the files, so I had to write twice as much data to disk(800MB). Also db->put is much more complicated than write. So the test ended up taking about 10% more time, than the open/write/close case. Maybe in the case of a smaller work set (i.e. 1000 files instead of 35000) this might provide faster backend speeds. Also one could optimise speed by tweaking the acccess method parameters.

Robert Suetterlin ([email protected])
phone: (+49)89 / 30000-3546   fax: (+49)89 / 30000-3950