[PATCH WIP] sha1-lookup: more memory efficient search in sorted list of SHA-1

[PATCH WIP] sha1-lookup: more memory efficient search in sorted list of SHA-1

[Junio C Hamano]

Currently, when looking for a packed object from the pack idx, a
simple binary search is used.

A conventional binary search loop looks like this:

        unsigned lo, hi;
        do {
                unsigned mi = (lo + hi) / 2;
                int cmp = "entry pointed at by mi" minus "target";
                if (!cmp)
                        return (mi is the wanted one)
                if (cmp > 0)
                        hi = mi; "mi is larger than target"
                else
                        lo = mi+1; "mi is smaller than target"
        } while (lo < hi);

The invariants are:

  - When entering the loop, 'lo' points at a slot that is never
    above the target (it could be at the target), 'hi' points at
    a slot that is guaranteed to be above the target (it can
    never be at the target).

  - We find a point 'mi' between 'lo' and 'hi' ('mi' could be
    the same as 'lo', but never can be the same as 'hi'), and
    check if 'mi' hits the target.  There are three cases:

     - if it is a hit, we have found the SHA-1;

     - if it is strictly higher than the target, we set it to
       'hi', and repeat the search.

     - if it is strictly lower than the target, we update 'lo'
       to one slot after it, because we allow 'lo' to be at the
       target.

    If the loop exits, there is no matching entry.

When choosing 'mi', we do not have to take the "middle" but
anywhere in between 'lo' and 'hi', as long as lo <= mi < hi is
satisfied.  When we somehow know that the distance between the
target and 'lo' is much shorter than the target and 'hi', we
could pick 'mi' that is much closer to 'lo' than (hi+lo)/2,
which a conventional binary search would pick.

This patch takes advantage of the fact that the SHA-1 is a good
hash function, and as long as there are enough entries in the
table, we can expect uniform distribution.  An entry that begins
with for example "deadbeef..." is much likely to appear much
later than in the midway of a reasonably populated table.  In
fact, it can be expected to be near 87% (222/256) from the top
of the table.

This is a work-in-progress and has switches to allow easier
experiments and debugging.  Exporting GIT_USE_LOOKUP environment
variable enables this code.

On my admittedly memory starved machine, with a partial KDE
repository (3.0G pack with 95M idx):

    $ GIT_USE_LOOKUP=t git log -800 --stat HEAD >/dev/null
    3.93user 0.16system 0:04.09elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
    0inputs+0outputs (0major+55588minor)pagefaults 0swaps

Without the patch, the numbers are:

    $ git log -800 --stat HEAD >/dev/null
    4.00user 0.15system 0:04.17elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
    0inputs+0outputs (0major+60258minor)pagefaults 0swaps

In the same repository:

    $ GIT_USE_LOOKUP=t git log -2000 HEAD >/dev/null
    0.12user 0.00system 0:00.12elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
    0inputs+0outputs (0major+4241minor)pagefaults 0swaps

Without the patch, the numbers are:

    $ git log -2000 HEAD >/dev/null
    0.05user 0.01system 0:00.07elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
    0inputs+0outputs (0major+8506minor)pagefaults 0swaps

There isn't much time difference, but the number of minor faults
seems to show that we are touching much smaller number of pages,
which is expected.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 Makefile      |    6 ++-
 sha1-lookup.c |  153 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 sha1-lookup.h |    9 +++
 sha1_file.c   |   35 ++++++++++++-
 4 files changed, 198 insertions(+), 5 deletions(-)
 create mode 100644 sha1-lookup.c
 create mode 100644 sha1-lookup.h

diff --git a/Makefile b/Makefile
index 21c80e6..9cff3ca 100644
--- a/Makefile
+++ b/Makefile
@@ -293,7 +293,8 @@ LIB_H = \
 	run-command.h strbuf.h tag.h tree.h git-compat-util.h revision.h \
 	tree-walk.h log-tree.h dir.h path-list.h unpack-trees.h builtin.h \
 	utf8.h reflog-walk.h patch-ids.h attr.h decorate.h progress.h \
-	mailmap.h remote.h parse-options.h transport.h diffcore.h hash.h
+	mailmap.h remote.h parse-options.h transport.h diffcore.h hash.h \
+	sha1-lookup.h
 
 DIFF_OBJS = \
 	diff.o diff-lib.o diffcore-break.o diffcore-order.o \
@@ -316,7 +317,8 @@ LIB_OBJS = \
 	alloc.o merge-file.o path-list.o help.o unpack-trees.o $(DIFF_OBJS) \
 	color.o wt-status.o archive-zip.o archive-tar.o shallow.o utf8.o \
 	convert.o attr.o decorate.o progress.o mailmap.o symlinks.o remote.o \
-	transport.o bundle.o walker.o parse-options.o ws.o
+	transport.o bundle.o walker.o parse-options.o ws.o \
+	sha1-lookup.o
 
 BUILTIN_OBJS = \
 	builtin-add.o \
diff --git a/sha1-lookup.c b/sha1-lookup.c
new file mode 100644
index 0000000..f5c9094
--- /dev/null
+++ b/sha1-lookup.c
@@ -0,0 +1,153 @@
+#include "cache.h"
+#include "sha1-lookup.h"
+
+/*
+ * Conventional binary search loop looks like this:
+ *
+ *	unsigned lo, hi;
+ *      do {
+ *              unsigned mi = (lo + hi) / 2;
+ *              int cmp = "entry pointed at by mi" minus "target";
+ *              if (!cmp)
+ *                      return (mi is the wanted one)
+ *              if (cmp > 0)
+ *                      hi = mi; "mi is larger than target"
+ *              else
+ *                      lo = mi+1; "mi is smaller than target"
+ *      } while (lo < hi);
+ *
+ * The invariants are:
+ *
+ * - When entering the loop, lo points at a slot that is never
+ *   above the target (it could be at the target), hi points at a
+ *   slot that is guaranteed to be above the target (it can never
+ *   be at the target).
+ *
+ * - We find a point 'mi' between lo and hi (mi could be the same
+ *   as lo, but never can be as same as hi), and check if it hits
+ *   the target.  There are three cases:
+ *
+ *    - if it is a hit, we are happy.
+ *
+ *    - if it is strictly higher than the target, we set it to hi,
+ *      and repeat the search.
+ *
+ *    - if it is strictly lower than the target, we update lo to
+ *      one slot after it, because we allow lo to be at the target.
+ *
+ *   If the loop exits, there is no matching entry.
+ *
+ * When choosing 'mi', we do not have to take the "middle" but
+ * anywhere in between lo and hi, as long as lo <= mi < hi is
+ * satisfied.  When we somehow know that the distance between the
+ * target and lo is much shorter than the target and hi, we could
+ * pick mi that is much closer to lo than the midway.
+ *
+ * Now, we can take advantage of the fact that SHA-1 is a good hash
+ * function, and as long as there are enough entries in the table, we
+ * can expect uniform distribution.  An entry that begins with for
+ * example "deadbeef..." is much likely to appear much later than in
+ * the midway of the table.  It can reasonably be expected to be near
+ * 87% (222/256) from the top of the table.
+ *
+ * The table at "table" holds at least "nr" entries of "elem_size"
+ * bytes each.  Each entry has the SHA-1 key at "key_offset".  The
+ * table is sorted by the SHA-1 key of the entries.  The caller wants
+ * to find the entry with "key", and knows that the entry at "lo" is
+ * not higher than the entry it is looking for, and that the entry at
+ * "hi" is higher than the entry it is looking for.
+ */
+int sha1_entry_pos(const void *table,
+		   size_t elem_size,
+		   size_t key_offset,
+		   unsigned lo, unsigned hi, unsigned nr,
+		   const unsigned char *key)
+{
+	const unsigned char *base = table;
+	const unsigned char *hi_key, *lo_key;
+	unsigned ofs_0;
+	static int debug_lookup = -1;
+
+	if (debug_lookup < 0)
+		debug_lookup = !!getenv("GIT_DEBUG_LOOKUP");
+
+	if (!nr || lo >= hi)
+		return -1;
+
+	if (nr == hi)
+		hi_key = NULL;
+	else
+		hi_key = base + elem_size * hi + key_offset;
+	lo_key = base + elem_size * lo + key_offset;
+
+	ofs_0 = 0;
+	do {
+		int cmp;
+		unsigned ofs, mi, range;
+		unsigned lov, hiv, kyv;
+		const unsigned char *mi_key;
+
+		range = hi - lo;
+		if (hi_key) {
+			for (ofs = ofs_0; ofs < 20; ofs++)
+				if (lo_key[ofs] != hi_key[ofs])
+					break;
+			ofs_0 = ofs;
+			/*
+			 * byte 0 thru (ofs-1) are the same between
+			 * lo and hi; ofs is the first byte that is
+			 * different.
+			 */
+			hiv = hi_key[ofs_0];
+			if (ofs_0 < 19)
+				hiv = (hiv << 8) | hi_key[ofs_0+1];
+		} else {
+			hiv = 256;
+			if (ofs_0 < 19)
+				hiv <<= 8;
+		}
+		lov = lo_key[ofs_0];
+		kyv = key[ofs_0];
+		if (ofs_0 < 19) {
+			lov = (lov << 8) | lo_key[ofs_0+1];
+			kyv = (kyv << 8) | key[ofs_0+1];
+		}
+		assert(lov < hiv);
+
+		if (kyv < lov)
+			return -1 - lo;
+		if (hiv < kyv)
+			return -1 - hi;
+
+		if (kyv == lov && lov < hiv - 1)
+			kyv++;
+		else if (kyv == hiv - 1 && lov < kyv)
+			kyv--;
+
+		mi = (range - 1) * (kyv - lov) / (hiv - lov) + lo;
+
+		if (debug_lookup) {
+			printf("lo %u hi %u rg %u mi %u ", lo, hi, range, mi);
+			printf("ofs %u lov %x, hiv %x, kyv %x\n",
+			       ofs_0, lov, hiv, kyv);
+		}
+		if (!(lo <= mi && mi < hi))
+			die("assertion failure lo %u mi %u hi %u %s",
+			    lo, mi, hi, sha1_to_hex(key));
+
+		mi_key = base + elem_size * mi + key_offset;
+		cmp = memcmp(mi_key + ofs_0, key + ofs_0, 20 - ofs_0);
+		if (!cmp)
+			return mi;
+		if (cmp > 0) {
+			hi = mi;
+			hi_key = mi_key;
+		}
+		else {
+			lo = mi + 1;
+			lo_key = mi_key + elem_size;
+		}
+	} while (lo < hi);
+	return -lo-1;
+}
+
diff --git a/sha1-lookup.h b/sha1-lookup.h
new file mode 100644
index 0000000..3249a81
--- /dev/null
+++ b/sha1-lookup.h
@@ -0,0 +1,9 @@
+#ifndef SHA1_LOOKUP_H
+#define SHA1_LOOKUP_H
+
+extern int sha1_entry_pos(const void *table,
+			  size_t elem_size,
+			  size_t key_offset,
+			  unsigned lo, unsigned hi, unsigned nr,
+			  const unsigned char *key);
+#endif
diff --git a/sha1_file.c b/sha1_file.c
index b0c2435..e99136a 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -14,6 +14,7 @@
 #include "tag.h"
 #include "tree.h"
 #include "refs.h"
+#include "sha1-lookup.h"
 
 #ifndef O_NOATIME
 #if defined(__linux__) && (defined(__i386__) || defined(__PPC__))
@@ -1655,7 +1656,12 @@ off_t find_pack_entry_one(const unsigned char *sha1,
 {
 	const uint32_t *level1_ofs = p->index_data;
 	const unsigned char *index = p->index_data;
-	unsigned hi, lo;
+	unsigned hi, lo, stride;
+	static int use_lookup = -1;
+	static int debug_lookup = -1;
+
+	if (debug_lookup < 0)
+		debug_lookup = !!getenv("GIT_DEBUG_LOOKUP");
 
 	if (!index) {
 		if (open_pack_index(p))
@@ -1670,11 +1676,34 @@ off_t find_pack_entry_one(const unsigned char *sha1,
 	index += 4 * 256;
 	hi = ntohl(level1_ofs[*sha1]);
 	lo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));
+	if (p->index_version > 1) {
+		stride = 20;
+	} else {
+		stride = 24;
+		index += 4;
+	}
+
+	if (debug_lookup)
+		printf("%02x%02x%02x... lo %u hi %u nr %u\n",
+		       sha1[0], sha1[1], sha1[2], lo, hi, p->num_objects);
+
+	if (use_lookup < 0)
+		use_lookup = !!getenv("GIT_USE_LOOKUP");
+	if (use_lookup) {
+		int pos = sha1_entry_pos(index, stride, 0,
+					 lo, hi, p->num_objects, sha1);
+		if (pos < 0)
+			return 0;
+		return nth_packed_object_offset(p, pos);
+	}
 
 	do {
 		unsigned mi = (lo + hi) / 2;
-		unsigned x = (p->index_version > 1) ? (mi * 20) : (mi * 24 + 4);
-		int cmp = hashcmp(index + x, sha1);
+		int cmp = hashcmp(index + mi * stride, sha1);
+
+		if (debug_lookup)
+			printf("lo %u hi %u rg %u mi %u\n",
+			       lo, hi, hi - lo, mi);
 		if (!cmp)
 			return nth_packed_object_offset(p, mi);
 		if (cmp > 0)
-- 
1.5.4.rc2.3.g441ed

[PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive

[Junio C Hamano]

If we pick 'mi' between 'lo' and 'hi' at 50%, which was what the
simple binary search did, we are halving the search space
whether the entry at 'mi' is lower or higher than the target.

The previous patch was about picking not the middle but closer
to 'hi', when we know the target is a lot closer to 'hi' than it
is to 'lo'.  However, if it turns out that the entry at 'mi' is
higher than the target, we would end up reducing the search
space only by the difference between 'mi' and 'hi' (which by
definition is less than 50% --- that was the whole point of not
using the simple binary search), which made the search less
efficient.  And the risk of overshooting is high, because we try
to be too precise.

This tweaks the selection of 'mi' to be a bit closer to the
middle than we would otherwise pick to avoid the problem.

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):

    $ GIT_USE_LOOKUP=t git log -800 --stat HEAD >/dev/null
    3.88user 0.18system 0:04.07elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
    0inputs+0outputs (0major+56378minor)pagefaults 0swaps

    $ git log -800 --stat HEAD >/dev/null
    3.93user 0.18system 0:04.11elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
    0inputs+0outputs (0major+60258minor)pagefaults 0swaps

    $ GIT_USE_LOOKUP=t git log -2000 HEAD >/dev/null
    0.05user 0.00system 0:00.06elapsed 95%CPU (0avgtext+0avgdata 0maxresident)k
    0inputs+0outputs (0major+4517minor)pagefaults 0swaps

    $ git log -2000 HEAD >/dev/null
    0.10user 0.03system 0:00.14elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
    0inputs+0outputs (0major+8505minor)pagefaults 0swaps

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---

 * This is no way close to even 'pu' yet, but I found it an
   interesting mental exercise with a bit of random hackery.

 sha1-lookup.c |   30 +++++++++++++++++++++++++-----
 1 files changed, 25 insertions(+), 5 deletions(-)

diff --git a/sha1-lookup.c b/sha1-lookup.c
index f5c9094..b309270 100644
--- a/sha1-lookup.c
+++ b/sha1-lookup.c
@@ -50,6 +50,12 @@
  * the midway of the table.  It can reasonably be expected to be near
  * 87% (222/256) from the top of the table.
  *
+ * However, we do not want to pick "mi" too precisely.  If the entry at
+ * the 87% in the above example turns out to be higher than the target
+ * we are looking for, we would end up narrowing the search space down
+ * only by 13%, instead of 50% we would get if we did a simple binary
+ * search.  So we would want to hedge our bets by being less aggressive.
+ *
  * The table at "table" holds at least "nr" entries of "elem_size"
  * bytes each.  Each entry has the SHA-1 key at "key_offset".  The
  * table is sorted by the SHA-1 key of the entries.  The caller wants
@@ -119,11 +125,25 @@ int sha1_entry_pos(const void *table,
 		if (hiv < kyv)
 			return -1 - hi;
 
-		if (kyv == lov && lov < hiv - 1)
-			kyv++;
-		else if (kyv == hiv - 1 && lov < kyv)
-			kyv--;
-
+		/*
+		 * Even if we know the target is much closer to 'hi'
+		 * than 'lo', if we pick too precisely and overshoot
+		 * (e.g. when we know 'mi' is closer to 'hi' than to
+		 * 'lo', pick 'mi' that is higher than the target), we
+		 * end up narrowing the search space by a smaller
+		 * amount (i.e. the distance between 'mi' and 'hi')
+		 * than what we would have (i.e. about half of 'lo'
+		 * and 'hi').  Hedge our bets to pick 'mi' less
+		 * aggressively, i.e. make 'mi' a bit closer to the
+		 * middle than we would otherwise pick.
+		 */
+		kyv = (kyv * 1022 + lov + hiv) / 1024;
+		if (lov < hiv - 1) {
+			if (kyv == lov)
+				kyv++;
+			else if (kyv == hiv)
+				kyv--;
+		}
 		mi = (range - 1) * (kyv - lov) / (hiv - lov) + lo;
 
 		if (debug_lookup) {
-- 
1.5.4.rc2.3.g441ed

Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive

[Marco Costalba]

On Dec 30, 2007 12:38 PM, Junio C Hamano <gitster@pobox.com> wrote:
>
> With this patch, we actually see slight improvements in
> execution time as well.

I have applied both your patch above and what we have discussed today,
the patch to speedup prefixcmp() and mine experimental one to avoid a
lookup loop in strbuf_expand().

I don't see big differences with or without you patch applied.

Just for document the profiling I have uploaded a snapshot of
KCachegrind profiling data on a run of git-log on the git tree:

http://digilander.libero.it/mcostalba/callgrind_git_log1.png

>From there you can see that pretty.c and strbuf.c, after all the
optimizations, account for less then 8% of total time.
The biggest part is that 86.64% that is due almost entirely to zlib.

In particular

st = inflate(&stream, Z_FINISH);

called from unpack_compressed_entry() in sha1_file.c accounts for 72%
of total time.


Marco

Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive

[Marco Costalba]

On Dec 30, 2007 8:06 PM, Marco Costalba <mcostalba@gmail.com> wrote:
>
> In particular
>
> st = inflate(&stream, Z_FINISH);
>
> called from unpack_compressed_entry() in sha1_file.c accounts for 72%
> of total time.
>

That's the snapshot:

http://digilander.libero.it/mcostalba/callgrind_git_log2.png

Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive

[Shawn O. Pearce]

Marco Costalba <mcostalba@gmail.com> wrote:
> Just for document the profiling I have uploaded a snapshot of
> KCachegrind profiling data on a run of git-log on the git tree:
> 
> http://digilander.libero.it/mcostalba/callgrind_git_log1.png
> 
> From there you can see that pretty.c and strbuf.c, after all the
> optimizations, account for less then 8% of total time.
> The biggest part is that 86.64% that is due almost entirely to zlib.
> 
> In particular
> 
> st = inflate(&stream, Z_FINISH);
> 
> called from unpack_compressed_entry() in sha1_file.c accounts for 72%
> of total time.

That's one of the areas where packv4 was actually a reasonably
good gain.  It was faster for packv4 to convert a dict based commit
or tree into the canonical raw format used by git than it was for
zlib inflate to decompress the very same data.

It wasn't a huge gain, but if I recall we were saving a good half
second on a 4 second "git log --raw >/dev/null" time.  And that
was before we even tried to improve the tree walking APIs to
take advantage of the smaller (and easier to read) dict based
tree objects.

Linus already mentioned in another reply on this thread that the
inflate time may be all page faults.  The savings we were seeing
from the dict based format may have simply been due to less page
faults; the dict based format was slightly smaller so we probably
got a lot more in disk cache at once.

-- 
Shawn.

Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive

[Linus Torvalds]

On Sun, 30 Dec 2007, Junio C Hamano wrote:
> 
> 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. And mine 
was buggy. See

	http://marc.info/?l=git&m=117537594112450&w=2

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.

		Linus

Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> On Sun, 30 Dec 2007, Junio C Hamano wrote:
>> 
>> 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.

Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive

[Marco Costalba]

On Dec 30, 2007 10:49 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Linus Torvalds <torvalds@linux-foundation.org> 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

Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive

[Linus Torvalds]

On Sun, 30 Dec 2007, Marco Costalba wrote:
> 
> 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

Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive

[Marco Costalba]

On Dec 31, 2007 9:37 PM, Linus Torvalds <torvalds@linux-foundation.org> 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

Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive

[Jeff King]

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

Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive

[Marco Costalba]

On Jan 1, 2008 7:36 AM, Jeff King <peff@peff.net> 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

Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive

[Marco Costalba]

On Jan 1, 2008 9:40 AM, Marco Costalba <mcostalba@gmail.com> wrote:
> On Jan 1, 2008 7:36 AM, Jeff King <peff@peff.net> 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.
>

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

Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive

[Pierre Habouzit]

[-- Attachment #1: Type: text/plain, Size: 1730 bytes --]

On Tue, Jan 01, 2008 at 06:36:16AM +0000, Jeff King wrote:
> zlib makes a noticeable impact in real world cases. On a git.git repo,
> fully packed with stock config, warm cache:

On linux-2.6.git, with compressed packs:

    $ =time git whatchanged >|/dev/null
    19.67user 1.24system 0:21.01elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
    0inputs+0outputs (0major+38556minor)pagefaults 0swaps

Without compression:

    $ =time git whatchanged >|/dev/null
    14.41user 1.23system 0:15.67elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
    0inputs+0outputs (0major+44678minor)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.

  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

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]