{"thread":{"id":"7929","subject":"[RFC] Optimize diff-delta.c","startedAt":"2007-05-01T14:49:27Z","lastAt":"2007-05-01T16:05:24Z","messageCount":3,"participants":["Martin Koegler","Johannes Schindelin","Nicolas Pitre"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"40821","messageId":"1178030967273-git-send-email-mkoegler@auto.tuwien.ac.at","threadId":"7929","inReplyTo":null,"subject":"[RFC] Optimize diff-delta.c","fromName":"Martin Koegler","fromEmail":"mkoegler@auto.tuwien.ac.at","sentAt":"2007-05-01T14:49:27Z","receivedAt":"2007-05-01T14:49:27Z","isPatch":false,"sender":{"key":"mkoegler@auto.tuwien.ac.at","avatar":null},"body":"I try to use git with large blobs. Putting such blobs into pack files\nis a slow operation and requires lots of memory. So I take a look at\nthe packing process.\n\nAs the delta format only supports 32 bit offsets, the uncompressed\nblob size is limited to 4GB.\n\nThe delta index has approximately the same size in memory as the\nuncompressed blob ((blob size)/16*(sizeof(index_entry)).\ngit-pack-objects keep the delta index of all objects in the search\nwindow in memory.\n\nSo doing a delta of 4 GB files is totally unrealistic:\n (4GB data + ~4GB index)* window size [default: 10]= 80 GB in the worst case\n\nIn my case, the blobs are some hundred MB big, but git-pack-objects\nalready uses some GB of memory. As the memory requirement of\ngit-pack-objects is currently below the available memory of my system,\nI need not to address this issue yet.\n\nIn the future, I'll propably need to create a patch to free big delta\nindexes in find_delta immediatly, after create_delta returned. This\nwill increase the processing time, but better than not being able to \npack objects.\n\nI tried to speed up the delta generation by searching for a common\nprefix, as my blobs are mostly append only. I tested it with about\nless than 1000 big blobs. The time for finding the deltas decreased\nfrom 17 to 14 minutes cpu time.\n\nWhen repacking the git-repostiory itself, I get the following numbers:\n\nUnmodified version (gcc-4.1):\n$ echo | time ./git-pack-objects --non-empty --all --reflog --unpacked=pack-d44dc76d0e873a7c7566bcc4503731b9a5640b30.pack --no-reuse-delta .git/.tmp-28449-pack\nGenerating pack...\nDone counting 42553 objects.\nDeltifying 42553 objects...\n 100% (42553/42553) done\nWriting 42553 objects...\n 100% (42553/42553) done\nd44dc76d0e873a7c7566bcc4503731b9a5640b30\nTotal 42553 (delta 29605), reused 12346 (delta 0)\n63.82user 0.80system 1:06.64elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+29177minor)pagefaults 0swaps\n\nPatched version (gcc-4.1):\n$ echo | time ../git/git-pack-objects --non-empty --all --reflog --unpacked=pack-d44dc76d0e873a7c7566bcc4503731b9a5640b30.pack --no-reuse-delta .git/.tmp-28448-pack\nGenerating pack...\nDone counting 42553 objects.\nDeltifying 42553 objects...\n 100% (42553/42553) done\nWriting 42553 objects...\n 100% (42553/42553) done\nd44dc76d0e873a7c7566bcc4503731b9a5640b30\nTotal 42553 (delta 29581), reused 12353 (delta 0)\n62.13user 0.91system 1:05.07elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+39690minor)pagefaults 0swaps\n\nSo it can help improve the performance a little bit (62.13+0.91<->63.82+0.80) on normal\nrepositories.\n\nThe following patch is only for testing purposes and not cleaned up.\n\nmfg Martin Kögler\n\n diff-delta.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 files changed, 62 insertions(+), 0 deletions(-)\n\ndiff --git a/diff-delta.c b/diff-delta.c\nindex 9f998d0..4f29eb7 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -250,6 +250,8 @@ create_delta(const struct delta_index *index,\n \tint inscnt;\n \tconst unsigned char *ref_data, *ref_top, *data, *top;\n \tunsigned char *out;\n+\tconst unsigned char* d, *dt, *t, *td;\n+\tunsigned int psize;\n \n \tif (!trg_buf || !trg_size)\n \t\treturn NULL;\n@@ -283,6 +285,66 @@ create_delta(const struct delta_index *index,\n \tdata = trg_buf;\n \ttop = (const unsigned char *) trg_buf + trg_size;\n \n+\tpsize = 0;\n+\td=data;\n+\tdt=top-RABIN_WINDOW;\n+\tt=ref_data;\n+\ttd=ref_top-RABIN_WINDOW;\n+\twhile (d
0xFFFFFF)\n+\t\tsize=0xFFFFFF;\n+\n+\n+\t data+=size;\n+\t moff=offset;\n+\t offset+=size;\n+\t psize-=size;\n+\n+\t op = out + outpos++;\n+\t i = 0x80;\n+\n+\t if (moff & 0xff) { out[outpos++] = moff; i |= 0x01; }\n+\t moff >>= 8;\n+\t if (moff & 0xff) { out[outpos++] = moff; i |= 0x02; }\n+\t moff >>= 8;\n+\t if (moff & 0xff) { out[outpos++] = moff; i |= 0x04; }\n+\t moff >>= 8;\n+\t if (moff & 0xff) { out[outpos++] = moff; i |= 0x08; }\n+\t \n+\t if (size & 0xff) { out[outpos++] = size; i |= 0x10; }\n+\t size >>= 8;\n+\t if (size & 0xff) { out[outpos++] = size; i |= 0x20; }\n+\t size >>= 8;\n+\t if (size & 0xff) { out[outpos++] = size; i |= 0x40; }\n+\n+\t *op = i;\n+\n+\t\tif (outpos >= outsize - MAX_OP_SIZE) {\n+\t\t\tvoid *tmp = out;\n+\t\t\toutsize = outsize * 3 / 2;\n+\t\t\tif (max_size && outsize >= max_size)\n+\t\t\t\toutsize = max_size + MAX_OP_SIZE + 1;\n+\t\t\tif (max_size && outpos > max_size)\n+\t\t\t\tbreak;\n+\t\t\tout = xrealloc(out, outsize);\n+\t\t\tif (!out) {\n+\t\t\t\tfree(tmp);\n+\t\t\t\treturn NULL;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n \toutpos++;\n \tval = 0;\n \tfor (i = 0; i < RABIN_WINDOW && data < top; i++, data++) {\n-- \n1.4.4.4\n"},{"id":"40829","messageId":"Pine.LNX.4.64.0705011748510.4010@racer.site","threadId":"7929","inReplyTo":"1178030967273-git-send-email-mkoegler@auto.tuwien.ac.at","subject":"Re: [RFC] Optimize diff-delta.c","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-05-01T15:51:06Z","receivedAt":"2007-05-01T15:51:06Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 1 May 2007, Martin Koegler wrote:\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 less \n> than 1000 big blobs. The time for finding the deltas decreased from 17 \n> to 14 minutes cpu time.\n\nThe interesting timings, of course, would be of big blobs which are _not_ \nappend-only, as they are more common, at least for me.\n\nSince git.git contained next to no binary blobs, this is not a good test \ncase.\n\nCiao,\nDscho\n"},{"id":"40831","messageId":"alpine.LFD.0.98.0705011124250.6574@xanadu.home","threadId":"7929","inReplyTo":"1178030967273-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-01T16:05:24Z","receivedAt":"2007-05-01T16:05:24Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 1 May 2007, Martin Koegler wrote:\n\n> As the delta format only supports 32 bit offsets, the uncompressed\n> blob size is limited to 4GB.\n\nRight. I think it would be a good idea to extend the delta format as \nwell to allow for larger offsets in pack v4.\n\n> The delta index has approximately the same size in memory as the\n> uncompressed blob ((blob size)/16*(sizeof(index_entry)).\n\nOne thing that could be done with really large blobs is to create a \nsparser index, i.e. have a larger step than 16. Because the delta match \nloop scans backward after a match the sparse index shouldn't affect \ncompression that much on large blobs and the index could be \nsignificantly smaller.\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\nI'm surprised that your patch makes so much of a difference. Normally \nthe first window should always match in the case you're trying to \noptimize and the current code should already perform more or less the \nsame as your common prefix match does.\n\nAh, no, actually what your patch does is a pessimisation of the matching \ncode by not considering other and possibly better matches elsewhere in \nthe reference buffer whenever there is a match at the beginning of both \nbuffers. I don't think this is a good idea in general.\n\nWhat you should try instead if you want to make the process faster is to \nlower the treshold used to consider a match sufficiently large to stop \nsearching. That has the potential for even faster processing as the \n\"optimization\" would then be effective throughout the buffer and not \nonly at the beginning.\n\nCurrently the treshold is implicit and equal to 65536. Please consider \nthis patch instead of yours for testing:\n\ndiff --git a/diff-delta.c b/diff-delta.c\nindex 9f998d0..755c0a9 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -315,6 +315,9 @@ 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\t/* a sufficiently large match is good enough */\n+\t\t\t\tif (msize >= 4096)\n+\t\t\t\t\tbreak;\n \t\t\t}\n \t\t}\n \n\nYou could experiment with that value to determine the best speed vs size \ncompromize.\n\n\nNicolas\n"}]}