{"thread":{"id":"8137","subject":"Re: [RFC] Optimize diff-delta.c","startedAt":"2007-05-13T20:50:13Z","lastAt":"2007-05-14T16:34:06Z","messageCount":2,"participants":["Martin Koegler","Nicolas Pitre"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"42055","messageId":"1179089413753-git-send-email-mkoegler@auto.tuwien.ac.at","threadId":"8137","inReplyTo":null,"subject":"Re: [RFC] Optimize diff-delta.c","fromName":"Martin Koegler","fromEmail":"mkoegler@auto.tuwien.ac.at","sentAt":"2007-05-13T20:50:13Z","receivedAt":"2007-05-13T20:50:13Z","isPatch":false,"sender":{"key":"mkoegler@auto.tuwien.ac.at","avatar":null},"body":"---\nOn Fri, 04 May 2007, Nicolas Pitre wrote:\n> On Fri, 4 May 2007, Martin Koegler wrote:\n> > On 2007-05-01 16:05:24, Nicolas Pitre wrote:\n> > In the long term, I think, that the delta generation code needs to get\n> > tunable.\n> \n> No.  It should be self-tunable certainly, but there are way too many \n> config options already, and another one for the inner working of the \n> delta algorithm would be a bit too esoteric for most users and they \n> won't get advantage of it.  This thing really has to self tune itself.\n\nI would like that too, but that will probably not the case for\neverybody. \n\nWhy does git has options to control the zlib compression?  \n\nWhy are patches like \"Custom compression levels for objects and packs\"\n(http://www.spinics.net/lists/git/msg30244.html) sent to the mailing\nlist?\n\n> > > > I tried to speed up the delta generation by searching for a common \n> > > > prefix, as my blobs are mostly append only. I tested it with about \n> > > > less than 1000 big blobs. The time for finding the deltas decreased \n> > > > from 17 to 14 minutes cpu time.\n> > > \n> > > I'm surprised that your patch makes so much of a difference.  Normally \n> > > the first window should always match in the case you're trying to \n> > > optimize and the current code should already perform more or less the \n> > > same as your common prefix match does.\n> > \n> > A block is limited to 64k. If the file has some hundred MBs, it has to\n> > match many blocks.\n> \n> Only if the first match is smaller than 64K.  If the first match is 64K \n> in size then the rest of the file is not considered at all.\n\nIf I read the code correctly, the currect code does a new hash table\nsearch after writing a block.\n\n> > My patch can process everything except the few last thousand lines by\n> > doing a memcmp.\n> > \n> > Additionally, nearly every line starts with the same, longer than 16\n> > byte prefix. So its likely, that many blocks map to the same hash\n> > value.\n> \n> The hash index only remembers the lowest of consecutive identical blocks \n> so repeated blocks are indexed only with the first one.  If however you \n> happen to have many identical blocks interlaced between other blocks \n> then there is not much that can be done.  What the code does in that \n> case is to trim those hash buckets that gets too large by keeping only a \n> few entries across the reference buffer to avoid a O(n^2) behavior. But \n> that happens only when your line beginnings are located on the same \n> block boundary (but with a block size of 16 this is rather likely in the \n> presence of lots of lines I suppose).\n> \n> I'll be very interested in the results you get with my suggested patch.\n\nAs my original patch is not considering other and possibly better\nmatches, I rewrote the patch. The new version matches block of\nunlimited length (stopping after finding a match >=64kB). If the block\nit bigger than 64kB, it writes block of 64kB in a loop.\n\nThe patch recomputes the hash of 16 bytes after writing a block, as I\nhaven't had time to correct the hash update code for blocks < 16\nbytes. (By the way, is this code path necessary?)\n\nI did some tests on differenent machines:\n\nRepacking a test repository with big blobs:\n\n- original version:\n   Total 6452 (delta 4582), reused 1522 (delta 0)\n   11752.26user 4256.21system 4:26:52elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n   0inputs+0outputs (576major+1042499851minor)pagefaults 0swaps\n   =>92 MB pack size\n- your patch (stop at 4096 bytes block size):\n   Total 6452 (delta 4582), reused 1522 (delta 0)\n   11587.41user 4064.73system 4:20:54elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n   0inputs+0outputs (0major+1042500427minor)pagefaults 0swaps\n   =>92 MB pack size\n- my first patch\n   Total 6452 (delta 4706), reused 1450 (delta 0)\n   10316.93user 4220.67system 4:02:20elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n   0inputs+0outputs (0major+1045003394minor)pagefaults 0swaps\n   =>92 MB pack size\n- attached patch\n   Total 6452 (delta 4581), reused 1522 (delta 0)\n   11354.38user 5451.60system 4:40:09elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n   0inputs+0outputs (0major+1371504762minor)pagefaults 0swaps\n   =>75 MB pack size\n\nRepacking git.git repository:\n\n- original version\n   Total 42893 (delta 29900), reused 12400 (delta 0)\n   57.32user 1.17system 1:03.73elapsed 91%CPU (0avgtext+0avgdata 0maxresident)k\n   0inputs+0outputs (267major+47813minor)pagefaults 0swaps\n   11538746 bytes pack size\n- attached patch\n   Total 42893 (delta 29899), reused 12400 (delta 0)\n   57.04user 0.80system 1:00.68elapsed 95%CPU (0avgtext+0avgdata 0maxresident)k\n   0inputs+0outputs (7major+28628minor)pagefaults 0swaps\n   11538869 bytes pack size\n\nRepacking linux kernel repository:\n\n- original version\n   Total 467313 (delta 376494), reused 78113 (delta 0)\n   809.08user 39.59system 36:54.70elapsed 38%CPU (0avgtext+0avgdata 0maxresident)k\n   0inputs+0outputs (83839major+1257686minor)pagefaults 0swaps\n   149460017 bytes pack size\n- attached patch\n   Total 467313 (delta 376495), reused 78113 (delta 0)\n   806.27user 37.81system 35:06.12elapsed 40%CPU (0avgtext+0avgdata 0maxresident)k\n   0inputs+0outputs (79755major+1235874minor)pagefaults 0swaps\n   149336835 bytes pack size\n\nThe following patch is only for testing purposes and not cleaned up.\n\n diff-delta.c |  105 +++++++++++++++++++++++++++++++++++++--------------------\n 1 files changed, 68 insertions(+), 37 deletions(-)\n\ndiff --git a/diff-delta.c b/diff-delta.c\nindex 9f998d0..df9b336 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -305,8 +305,6 @@ create_delta(const struct delta_index *index,\n \t\t\t\tcontinue;\n \t\t\tif (ref_size > top - src)\n \t\t\t\tref_size = top - src;\n-\t\t\tif (ref_size > 0x10000)\n-\t\t\t\tref_size = 0x10000;\n \t\t\tif (ref_size <= msize)\n \t\t\t\tbreak;\n \t\t\twhile (ref_size-- && *src++ == *ref)\n@@ -315,6 +313,8 @@ create_delta(const struct delta_index *index,\n \t\t\t\t/* this is our best match so far */\n \t\t\t\tmsize = ref - entry->ptr;\n \t\t\t\tmoff = entry->ptr - ref_data;\n+\t\t\t\tif (msize >= 0x10000)\n+\t\t\t\t    break;\n \t\t\t}\n \t\t}\n \n@@ -328,30 +328,15 @@ create_delta(const struct delta_index *index,\n \t\t\t\tinscnt = 0;\n \t\t\t}\n \t\t} else {\n-\t\t\tunsigned char *op;\n-\n-\t\t\tif (msize >= RABIN_WINDOW) {\n-\t\t\t\tconst unsigned char *sk;\n-\t\t\t\tsk = data + msize - RABIN_WINDOW;\n-\t\t\t\tval = 0;\n-\t\t\t\tfor (i = 0; i < RABIN_WINDOW; i++)\n-\t\t\t\t\tval = ((val << 8) | *sk++) ^ T[val >> RABIN_SHIFT];\n-\t\t\t} else {\n-\t\t\t\tconst unsigned char *sk = data + 1;\n-\t\t\t\tfor (i = 1; i < msize; i++) {\n-\t\t\t\t\tval ^= U[sk[-RABIN_WINDOW]];\n-\t\t\t\t\tval = ((val << 8) | *sk++) ^ T[val >> RABIN_SHIFT];\n-\t\t\t\t}\n-\t\t\t}\n-\n+\t\t\tunsigned int wsize, undo = 0;\n+\t\t\t\n \t\t\tif (inscnt) {\n \t\t\t\twhile (moff && ref_data[moff-1] == data[-1]) {\n-\t\t\t\t\tif (msize == 0x10000)\n-\t\t\t\t\t\tbreak;\n \t\t\t\t\t/* we can match one byte back */\n \t\t\t\t\tmsize++;\n \t\t\t\t\tmoff--;\n \t\t\t\t\tdata--;\n+\t\t\t\t\tundo++;\n \t\t\t\t\toutpos--;\n \t\t\t\t\tif (--inscnt)\n \t\t\t\t\t\tcontinue;\n@@ -359,27 +344,72 @@ create_delta(const struct delta_index *index,\n \t\t\t\t\tinscnt--;  /* make it -1 */\n \t\t\t\t\tbreak;\n \t\t\t\t}\n-\t\t\t\tout[outpos - inscnt - 1] = inscnt;\n+\t\t\t\t\tout[outpos - inscnt - 1] = inscnt;\n \t\t\t\tinscnt = 0;\n \t\t\t}\n+\t\t\t\n+\t\t\twsize=msize;\n+\t\t\twhile (wsize >= 4)\n+\t\t\t{\n+\t\t\t\tunsigned char *op;\n+\t\t\t\tunsigned int boff, bsize;\n+\t\t\t\tboff = moff;\n+\t\t\t\tbsize = wsize;\n+\n+\t\t\t\tif (bsize > 0x10000)\n+\t\t\t\t\tbsize = 0x10000;\n+\n+\t\t\t\tmoff += bsize;\n+\t\t\t\twsize -= bsize;\n+\t\t\t\t\n+\t\t\t\top = out + outpos++;\n+\t\t\t\ti = 0x80;\n+\t\t\t\t\n+\t\t\t\tif (boff & 0xff) { out[outpos++] = boff; i |= 0x01; }\n+\t\t\t\tboff >>= 8;\n+\t\t\t\tif (boff & 0xff) { out[outpos++] = boff; i |= 0x02; }\n+\t\t\t\tboff >>= 8;\n+\t\t\t\tif (boff & 0xff) { out[outpos++] = boff; i |= 0x04; }\n+\t\t\t\tboff >>= 8;\n+\t\t\t\tif (boff & 0xff) { out[outpos++] = boff; i |= 0x08; }\n+\t\t\t\t\n+\t\t\t\tif (bsize & 0xff) { out[outpos++] = bsize; i |= 0x10; }\n+\t\t\t\tbsize >>= 8;\n+\t\t\t\tif (bsize & 0xff) { out[outpos++] = bsize; i |= 0x20; }\n+\t\t\t\t\n+\t\t\t\t*op = i;\n+\n+\t\t\t\tif (outpos >= outsize - MAX_OP_SIZE) {\n+\t\t\t\t\tvoid *tmp = out;\n+\t\t\t\t\toutsize = outsize * 3 / 2;\n+\t\t\t\t\tif (max_size && outsize >= max_size)\n+\t\t\t\t\t\toutsize = max_size + MAX_OP_SIZE + 1;\n+\t\t\t\t\tif (max_size && outpos > max_size)\n+\t\t\t\t\t\tgoto out;\n+\t\t\t\t\tout = xrealloc(out, outsize);\n+\t\t\t\t\tif (!out) {\n+\t\t\t\t\t\tfree(tmp);\n+\t\t\t\t\t\treturn NULL;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t}\n+\t\t\t\n+\t\t\tmsize -= wsize;\n+\t\t\tif (msize - undo >= RABIN_WINDOW || 1) {\n+\t\t\t\tconst unsigned char *sk;\n+\t\t\t\tsk = data + msize - RABIN_WINDOW;\n+\t\t\t\tval = 0;\n+\t\t\t\tfor (i = 0; i < RABIN_WINDOW; i++)\n+\t\t\t\t\tval = ((val << 8) | *sk++) ^ T[val >> RABIN_SHIFT];\n+\t\t\t} else {\n+\t\t\t\tconst unsigned char *sk = data + 1;\n+\t\t\t\tfor (i = 1; i < msize; i++) {\n+\t\t\t\t\tval ^= U[sk[-RABIN_WINDOW + undo]];\n+\t\t\t\t\tval = ((val << 8) | *sk++) ^ T[val >> RABIN_SHIFT];\n+\t\t\t\t}\n+\t\t\t}\n \n \t\t\tdata += msize;\n-\t\t\top = out + outpos++;\n-\t\t\ti = 0x80;\n-\n-\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x01; }\n-\t\t\tmoff >>= 8;\n-\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x02; }\n-\t\t\tmoff >>= 8;\n-\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x04; }\n-\t\t\tmoff >>= 8;\n-\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x08; }\n-\n-\t\t\tif (msize & 0xff) { out[outpos++] = msize; i |= 0x10; }\n-\t\t\tmsize >>= 8;\n-\t\t\tif (msize & 0xff) { out[outpos++] = msize; i |= 0x20; }\n-\n-\t\t\t*op = i;\n \t\t}\n \n \t\tif (outpos >= outsize - MAX_OP_SIZE) {\n@@ -397,6 +427,7 @@ create_delta(const struct delta_index *index,\n \t\t}\n \t}\n \n+ out:\n \tif (inscnt)\n \t\tout[outpos - inscnt - 1] = inscnt;\n \n-- \n1.4.4.4\n"},{"id":"42143","messageId":"alpine.LFD.0.99.0705141130480.24220@xanadu.home","threadId":"8137","inReplyTo":"1179089413753-git-send-email-mkoegler@auto.tuwien.ac.at","subject":"Re: [RFC] Optimize diff-delta.c","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-14T16:34:06Z","receivedAt":"2007-05-14T16:34:06Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 13 May 2007, Martin Koegler wrote:\n\n> ---\n> On Fri, 04 May 2007, Nicolas Pitre wrote:\n> > On Fri, 4 May 2007, Martin Koegler wrote:\n> > > On 2007-05-01 16:05:24, Nicolas Pitre wrote:\n> > > In the long term, I think, that the delta generation code needs to get\n> > > tunable.\n> > \n> > No.  It should be self-tunable certainly, but there are way too many \n> > config options already, and another one for the inner working of the \n> > delta algorithm would be a bit too esoteric for most users and they \n> > won't get advantage of it.  This thing really has to self tune itself.\n> \n> I would like that too, but that will probably not the case for\n> everybody. \n> \n> Why does git has options to control the zlib compression?  \n> \n> Why are patches like \"Custom compression levels for objects and packs\"\n> (http://www.spinics.net/lists/git/msg30244.html) sent to the mailing\n> list?\n\nBecause there is no nice ways to auto-tune them given the current zlib \ninterface.\n\n> > > > > I tried to speed up the delta generation by searching for a common \n> > > > > prefix, as my blobs are mostly append only. I tested it with about \n> > > > > less than 1000 big blobs. The time for finding the deltas decreased \n> > > > > from 17 to 14 minutes cpu time.\n> > > > \n> > > > I'm surprised that your patch makes so much of a difference.  Normally \n> > > > the first window should always match in the case you're trying to \n> > > > optimize and the current code should already perform more or less the \n> > > > same as your common prefix match does.\n> > > \n> > > A block is limited to 64k. If the file has some hundred MBs, it has to\n> > > match many blocks.\n> > \n> > Only if the first match is smaller than 64K.  If the first match is 64K \n> > in size then the rest of the file is not considered at all.\n> \n> If I read the code correctly, the currect code does a new hash table\n> search after writing a block.\n\nRight.\n\n> As my original patch is not considering other and possibly better\n> matches, I rewrote the patch. The new version matches block of\n> unlimited length (stopping after finding a match >=64kB). If the block\n> it bigger than 64kB, it writes block of 64kB in a loop.\n\nI like this idea a lot.\n\n> The patch recomputes the hash of 16 bytes after writing a block, as I\n> haven't had time to correct the hash update code for blocks < 16\n> bytes. (By the way, is this code path necessary?)\n\nIt certainly helps in those cases where the block match is smaller than \na Rabin window size, although I don't know how much.  Sliding the window \nover 8 bytes might be approximately the same cost as computing the \nhash from scratch over 16 bytes since in the sliding case there are \ntwice the amount of pointer dereferences.  So the test should probably \nbe \"if (msize >= RABIN_WINDOW/2) ...\" for the full reinitialization.\n\n> I did some tests on differenent machines:\n> \n> Repacking a test repository with big blobs:\n> \n> - original version:\n>    Total 6452 (delta 4582), reused 1522 (delta 0)\n>    11752.26user 4256.21system 4:26:52elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n>    0inputs+0outputs (576major+1042499851minor)pagefaults 0swaps\n>    =>92 MB pack size\n> - your patch (stop at 4096 bytes block size):\n>    Total 6452 (delta 4582), reused 1522 (delta 0)\n>    11587.41user 4064.73system 4:20:54elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n>    0inputs+0outputs (0major+1042500427minor)pagefaults 0swaps\n>    =>92 MB pack size\n> - my first patch\n>    Total 6452 (delta 4706), reused 1450 (delta 0)\n>    10316.93user 4220.67system 4:02:20elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n>    0inputs+0outputs (0major+1045003394minor)pagefaults 0swaps\n>    =>92 MB pack size\n> - attached patch\n>    Total 6452 (delta 4581), reused 1522 (delta 0)\n>    11354.38user 5451.60system 4:40:09elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n>    0inputs+0outputs (0major+1371504762minor)pagefaults 0swaps\n>    =>75 MB pack size\n\nThis is quite weird.  I wonder what might cause such a large difference \nin pack size.\n\nYour first patch is probably faster due to the use of memcmp() which is \ncertainly highly optimized, more than the comparison loop we have.  It \nis unfortunate that there is no library function to find the number of \nidentical bytes between two buffers.  Or is there some?\n\nBut the size difference?  That has certainly something to do with your \ndata set since your patch makes no significant difference on the git.git \nnor the Linux kernel repos.  Would it be possible for me to have a copy \nof your repo for further analysis?\n\n\nNicolas\n"}]}