{"thread":{"id":"3980","subject":"PATCH: New diff-delta.c implementation (updated)","startedAt":"2006-04-28T01:59:53Z","lastAt":"2006-04-28T04:28:30Z","messageCount":4,"participants":["Geert Bosch","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"19211","messageId":"Pine.GSO.4.60.0604272132170.9650@nile.gnat.com","threadId":"3980","inReplyTo":null,"subject":"PATCH: New diff-delta.c implementation (updated)","fromName":"Geert Bosch","fromEmail":"bosch@gnat.com","sentAt":"2006-04-28T01:59:53Z","receivedAt":"2006-04-28T01:59:53Z","isPatch":false,"sender":{"key":"bosch@gnat.com","avatar":null},"body":"Even though the previous version did really well on large files\nwith many changes, performance was lacking for the many small\nfiles with very few changes that are so common for a VCS.\n\nFor example, it turns out that, for packing the 17005 objects in\nmy git.git repository, diff_delta processes 240 MB worth of target\ndata in about 12s on my powerbook. (There's even a little more\nsource data, and the 12s includes compression/decompression time.)\n\nSo the fancy fingerprint calculations really take too much time.\nFortunately, it turns out that of the 240M, 120M matches directly\nat the start or the end of the source data. After this trivial\nmatching, most remaining matches are quite small. The overhead\nof setting up buffers, computing longest runs of the same character\nand computing 64-bit fingerprints becomes very noticeable and\ncan't be regained later.\n\nAs a result I implemented special indexing and matching routines\nfor \"small\" files. Here a fixed hash table size and index step\nare used. The fingerprint window has been reduced to be equal to\nthe step size, which essentially gets rid of computation for\ncharacters leaving the window. Finally, the fingerprint size\nhas been reduced to 32 bits with polynome of 31st degree.\n\nThe result has been only a slight increase in delta size for\nvery large test cases (but with better performance), and\nboth smaller deltas and faster execution speed for repacking\ngit.git. I had trouble cloning the Linux kernel repository,\nbut am now reasonably confident this will outperform the\nexisting algorithm pretty consistently.\n\nOn PPC, the trivial matching in head and tail, and for long\nmatching runs now shows up high in the profile. On x86,\nbyte operations are very fast, so I think things should\nbe at least equally good there.\n\nPlease play around with this and let me know of any results.\n\n   -Geert\n\nSigned-off-by: Geert Bosch <bosch@gnat.com>\n\n#include <unistd.h>\n#include <stdlib.h>\n#include <assert.h>\n#include <string.h>\n#include <sys/types.h>\n\n#undef assert\n#define assert(x) do { } while (0)\n\n/*\n  * MIN_HTAB_SIZE is fixed amount to be added to the size of the hash table\n  * used for indexing and must be a power of two. This allows for small files\n  * to have a sparse hash table, since in that case it's cheap.\n  * Hash table sizes are rounded up to a power of two to avoid integer division.\n  */\n#define MIN_HTAB_SIZE 8192\n#define MAX_HTAB_SIZE (1024*1024*1024)\n#define SMALL_HTAB_SIZE 8192\n#define SMALL_INDEX_STEP 16\n\n/*\n  * Diffing files of gigabyte range is impractical with the current\n  * algorithm, so we're assuming 32-bit sizes everywhere.\n  * Size leaves some room for expansion when diffing random files.\n  */\n#define MAX_SIZE (0x7eff0000)\n\n/* For small files, indices are represented in 16 bits.\n  * Since indices are always a multiple of the index_step, they\n  * can be shifted right a few bits to accommodate files larger than 64K\n  */\n#define SMALL_SHIFT 4\n#define MAX_SMALL_SIZE (0xff00<<SMALL_SHIFT)\n\n/* Initial size of copies table, dynamically extended as needed. */\n#define MAX_COPIES 512\n\n/*\n  * Matching is done using a sliding window for which a Rabin\n  * polynomial is computed. The advantage of such polynomials is\n  * that they can efficiently be updated at every position.\n  * The tables needed for this are precomputed, as it is desirable\n  * to use the same polynomial all the time for repeatable results.\n  * The 16 byte window is convenient for indexing with index_step 16.\n  * In that special case, the U table is not needed during indexing.\n  * The 32-bit hash helps on register-starved 32-bit architectures.\n  */\n\n#define RABIN_POLY 0xf3a03ce5\n#define RABIN_DEGREE 31\n#define RABIN_SHIFT 23\n#define RABIN_WINDOW_SIZE 16\n\nunsigned T[256] =\n{ 0x00000000, 0xf3a03ce5, 0x14e0452f,\n   0xe74079ca, 0x29c08a5e, 0xda60b6bb, 0x3d20cf71, 0xce80f394, 0x538114bc,\n   0xa0212859, 0x47615193, 0xb4c16d76, 0x7a419ee2, 0x89e1a207, 0x6ea1dbcd,\n   0x9d01e728, 0x54a2159d, 0xa7022978, 0x404250b2, 0xb3e26c57, 0x7d629fc3,\n   0x8ec2a326, 0x6982daec, 0x9a22e609, 0x07230121, 0xf4833dc4, 0x13c3440e,\n   0xe06378eb, 0x2ee38b7f, 0xdd43b79a, 0x3a03ce50, 0xc9a3f2b5, 0x5ae417df,\n   0xa9442b3a, 0x4e0452f0, 0xbda46e15, 0x73249d81, 0x8084a164, 0x67c4d8ae,\n   0x9464e44b, 0x09650363, 0xfac53f86, 0x1d85464c, 0xee257aa9, 0x20a5893d,\n   0xd305b5d8, 0x3445cc12, 0xc7e5f0f7, 0x0e460242, 0xfde63ea7, 0x1aa6476d,\n   0xe9067b88, 0x2786881c, 0xd426b4f9, 0x3366cd33, 0xc0c6f1d6, 0x5dc716fe,\n   0xae672a1b, 0x492753d1, 0xba876f34, 0x74079ca0, 0x87a7a045, 0x60e7d98f,\n   0x9347e56a, 0x4668135b, 0xb5c82fbe, 0x52885674, 0xa1286a91, 0x6fa89905,\n   0x9c08a5e0, 0x7b48dc2a, 0x88e8e0cf, 0x15e907e7, 0xe6493b02, 0x010942c8,\n   0xf2a97e2d, 0x3c298db9, 0xcf89b15c, 0x28c9c896, 0xdb69f473, 0x12ca06c6,\n   0xe16a3a23, 0x062a43e9, 0xf58a7f0c, 0x3b0a8c98, 0xc8aab07d, 0x2feac9b7,\n   0xdc4af552, 0x414b127a, 0xb2eb2e9f, 0x55ab5755, 0xa60b6bb0, 0x688b9824,\n   0x9b2ba4c1, 0x7c6bdd0b, 0x8fcbe1ee, 0x1c8c0484, 0xef2c3861, 0x086c41ab,\n   0xfbcc7d4e, 0x354c8eda, 0xc6ecb23f, 0x21accbf5, 0xd20cf710, 0x4f0d1038,\n   0xbcad2cdd, 0x5bed5517, 0xa84d69f2, 0x66cd9a66, 0x956da683, 0x722ddf49,\n   0x818de3ac, 0x482e1119, 0xbb8e2dfc, 0x5cce5436, 0xaf6e68d3, 0x61ee9b47,\n   0x924ea7a2, 0x750ede68, 0x86aee28d, 0x1baf05a5, 0xe80f3940, 0x0f4f408a,\n   0xfcef7c6f, 0x326f8ffb, 0xc1cfb31e, 0x268fcad4, 0xd52ff631, 0x7f701a53,\n   0x8cd026b6, 0x6b905f7c, 0x98306399, 0x56b0900d, 0xa510ace8, 0x4250d522,\n   0xb1f0e9c7, 0x2cf10eef, 0xdf51320a, 0x38114bc0, 0xcbb17725, 0x053184b1,\n   0xf691b854, 0x11d1c19e, 0xe271fd7b, 0x2bd20fce, 0xd872332b, 0x3f324ae1,\n   0xcc927604, 0x02128590, 0xf1b2b975, 0x16f2c0bf, 0xe552fc5a, 0x78531b72,\n   0x8bf32797, 0x6cb35e5d, 0x9f1362b8, 0x5193912c, 0xa233adc9, 0x4573d403,\n   0xb6d3e8e6, 0x25940d8c, 0xd6343169, 0x317448a3, 0xc2d47446, 0x0c5487d2,\n   0xfff4bb37, 0x18b4c2fd, 0xeb14fe18, 0x76151930, 0x85b525d5, 0x62f55c1f,\n   0x915560fa, 0x5fd5936e, 0xac75af8b, 0x4b35d641, 0xb895eaa4, 0x71361811,\n   0x829624f4, 0x65d65d3e, 0x967661db, 0x58f6924f, 0xab56aeaa, 0x4c16d760,\n   0xbfb6eb85, 0x22b70cad, 0xd1173048, 0x36574982, 0xc5f77567, 0x0b7786f3,\n   0xf8d7ba16, 0x1f97c3dc, 0xec37ff39, 0x39180908, 0xcab835ed, 0x2df84c27,\n   0xde5870c2, 0x10d88356, 0xe378bfb3, 0x0438c679, 0xf798fa9c, 0x6a991db4,\n   0x99392151, 0x7e79589b, 0x8dd9647e, 0x435997ea, 0xb0f9ab0f, 0x57b9d2c5,\n   0xa419ee20, 0x6dba1c95, 0x9e1a2070, 0x795a59ba, 0x8afa655f, 0x447a96cb,\n   0xb7daaa2e, 0x509ad3e4, 0xa33aef01, 0x3e3b0829, 0xcd9b34cc, 0x2adb4d06,\n   0xd97b71e3, 0x17fb8277, 0xe45bbe92, 0x031bc758, 0xf0bbfbbd, 0x63fc1ed7,\n   0x905c2232, 0x771c5bf8, 0x84bc671d, 0x4a3c9489, 0xb99ca86c, 0x5edcd1a6,\n   0xad7ced43, 0x307d0a6b, 0xc3dd368e, 0x249d4f44, 0xd73d73a1, 0x19bd8035,\n   0xea1dbcd0, 0x0d5dc51a, 0xfefdf9ff, 0x375e0b4a, 0xc4fe37af, 0x23be4e65,\n   0xd01e7280, 0x1e9e8114, 0xed3ebdf1, 0x0a7ec43b, 0xf9def8de, 0x64df1ff6,\n   0x977f2313, 0x703f5ad9, 0x839f663c, 0x4d1f95a8, 0xbebfa94d, 0x59ffd087,\n   0xaa5fec62\n};\n\nunsigned U[256] =\n{ 0x00000000, 0x302a7c89, 0x6054f912,\n   0x507e859b, 0x3309cec1, 0x0323b248, 0x535d37d3, 0x63774b5a, 0x66139d82,\n   0x5639e10b, 0x06476490, 0x366d1819, 0x551a5343, 0x65302fca, 0x354eaa51,\n   0x0564d6d8, 0x3f8707e1, 0x0fad7b68, 0x5fd3fef3, 0x6ff9827a, 0x0c8ec920,\n   0x3ca4b5a9, 0x6cda3032, 0x5cf04cbb, 0x59949a63, 0x69bee6ea, 0x39c06371,\n   0x09ea1ff8, 0x6a9d54a2, 0x5ab7282b, 0x0ac9adb0, 0x3ae3d139, 0x7f0e0fc2,\n   0x4f24734b, 0x1f5af6d0, 0x2f708a59, 0x4c07c103, 0x7c2dbd8a, 0x2c533811,\n   0x1c794498, 0x191d9240, 0x2937eec9, 0x79496b52, 0x496317db, 0x2a145c81,\n   0x1a3e2008, 0x4a40a593, 0x7a6ad91a, 0x40890823, 0x70a374aa, 0x20ddf131,\n   0x10f78db8, 0x7380c6e2, 0x43aaba6b, 0x13d43ff0, 0x23fe4379, 0x269a95a1,\n   0x16b0e928, 0x46ce6cb3, 0x76e4103a, 0x15935b60, 0x25b927e9, 0x75c7a272,\n   0x45eddefb, 0x0dbc2361, 0x3d965fe8, 0x6de8da73, 0x5dc2a6fa, 0x3eb5eda0,\n   0x0e9f9129, 0x5ee114b2, 0x6ecb683b, 0x6bafbee3, 0x5b85c26a, 0x0bfb47f1,\n   0x3bd13b78, 0x58a67022, 0x688c0cab, 0x38f28930, 0x08d8f5b9, 0x323b2480,\n   0x02115809, 0x526fdd92, 0x6245a11b, 0x0132ea41, 0x311896c8, 0x61661353,\n   0x514c6fda, 0x5428b902, 0x6402c58b, 0x347c4010, 0x04563c99, 0x672177c3,\n   0x570b0b4a, 0x07758ed1, 0x375ff258, 0x72b22ca3, 0x4298502a, 0x12e6d5b1,\n   0x22cca938, 0x41bbe262, 0x71919eeb, 0x21ef1b70, 0x11c567f9, 0x14a1b121,\n   0x248bcda8, 0x74f54833, 0x44df34ba, 0x27a87fe0, 0x17820369, 0x47fc86f2,\n   0x77d6fa7b, 0x4d352b42, 0x7d1f57cb, 0x2d61d250, 0x1d4baed9, 0x7e3ce583,\n   0x4e16990a, 0x1e681c91, 0x2e426018, 0x2b26b6c0, 0x1b0cca49, 0x4b724fd2,\n   0x7b58335b, 0x182f7801, 0x28050488, 0x787b8113, 0x4851fd9a, 0x1b7846c2,\n   0x2b523a4b, 0x7b2cbfd0, 0x4b06c359, 0x28718803, 0x185bf48a, 0x48257111,\n   0x780f0d98, 0x7d6bdb40, 0x4d41a7c9, 0x1d3f2252, 0x2d155edb, 0x4e621581,\n   0x7e486908, 0x2e36ec93, 0x1e1c901a, 0x24ff4123, 0x14d53daa, 0x44abb831,\n   0x7481c4b8, 0x17f68fe2, 0x27dcf36b, 0x77a276f0, 0x47880a79, 0x42ecdca1,\n   0x72c6a028, 0x22b825b3, 0x1292593a, 0x71e51260, 0x41cf6ee9, 0x11b1eb72,\n   0x219b97fb, 0x64764900, 0x545c3589, 0x0422b012, 0x3408cc9b, 0x577f87c1,\n   0x6755fb48, 0x372b7ed3, 0x0701025a, 0x0265d482, 0x324fa80b, 0x62312d90,\n   0x521b5119, 0x316c1a43, 0x014666ca, 0x5138e351, 0x61129fd8, 0x5bf14ee1,\n   0x6bdb3268, 0x3ba5b7f3, 0x0b8fcb7a, 0x68f88020, 0x58d2fca9, 0x08ac7932,\n   0x388605bb, 0x3de2d363, 0x0dc8afea, 0x5db62a71, 0x6d9c56f8, 0x0eeb1da2,\n   0x3ec1612b, 0x6ebfe4b0, 0x5e959839, 0x16c465a3, 0x26ee192a, 0x76909cb1,\n   0x46bae038, 0x25cdab62, 0x15e7d7eb, 0x45995270, 0x75b32ef9, 0x70d7f821,\n   0x40fd84a8, 0x10830133, 0x20a97dba, 0x43de36e0, 0x73f44a69, 0x238acff2,\n   0x13a0b37b, 0x29436242, 0x19691ecb, 0x49179b50, 0x793de7d9, 0x1a4aac83,\n   0x2a60d00a, 0x7a1e5591, 0x4a342918, 0x4f50ffc0, 0x7f7a8349, 0x2f0406d2,\n   0x1f2e7a5b, 0x7c593101, 0x4c734d88, 0x1c0dc813, 0x2c27b49a, 0x69ca6a61,\n   0x59e016e8, 0x099e9373, 0x39b4effa, 0x5ac3a4a0, 0x6ae9d829, 0x3a975db2,\n   0x0abd213b, 0x0fd9f7e3, 0x3ff38b6a, 0x6f8d0ef1, 0x5fa77278, 0x3cd03922,\n   0x0cfa45ab, 0x5c84c030, 0x6caebcb9, 0x564d6d80, 0x66671109, 0x36199492,\n   0x0633e81b, 0x6544a341, 0x556edfc8, 0x05105a53, 0x353a26da, 0x305ef002,\n   0x00748c8b, 0x500a0910, 0x60207599, 0x03573ec3, 0x337d424a, 0x6303c7d1,\n   0x5329bb58\n};\n\n\nstatic unsigned char rabin_window[RABIN_WINDOW_SIZE];\nstatic unsigned rabin_pos = 0;\n\n#ifndef MIN\n#define MIN(x,y) ((y)<(x) ? (y) : (x))\n#endif\n#ifndef MAX\n#define MAX(x,y) ((y)>(x) ? (y) : (x))\n#endif\n\n/*\n  * The copies array is the central data structure for diff generation.\n  * Data statements are implicit, for ranges not covered by any copy command.\n  *\n  * The sum of tgt and length for each entry must be monotonically increasing,\n  * and data ranges must be non-overlapping. This is accomplished by not\n  * extending matches backwards during initial matching.\n  *\n  * Copies may have zero length, to make it quick to delete copies during\n  * optimization. However, the last copy in the list must always be a\n  * non-trivial copy.\n  *\n  * Before committing copies, an important optimization is performed: during\n  * a backward pass through the copies array, each entry is extended backwards,\n  * and redundant copies are eliminated.\n  *\n  * If each match were extended backwards on insertion, the same data may be\n  * matched an arbitrary number of times, resulting in potentially quadratic\n  * time behavior.\n  */\n\ntypedef struct copyinfo {\n \tunsigned src;\n \tunsigned tgt;\n \tunsigned length;\n} CopyInfo;\n\nstatic CopyInfo *copies;\nstatic int copy_count = 0;\nstatic unsigned max_copies = 0; /* Dynamically increased */\n\nstatic unsigned *idx;\nstatic unsigned idx_size;\nstatic unsigned char *idx_data;\nstatic unsigned idx_data_len;\n\ntypedef unsigned poly_t;\n\nstatic void rabin_reset(void)\n{\n \tmemset(rabin_window, 0, sizeof(rabin_window));\n}\n\nstatic poly_t rabin_slide (poly_t fp, unsigned char m)\n{\n \tunsigned char om;\n \tif (++rabin_pos == RABIN_WINDOW_SIZE) rabin_pos = 0;\n \tom = rabin_window[rabin_pos];\n \tfp ^= U[om];\n \trabin_window[rabin_pos] = m;\n \tfp = ((fp << 8) | m) ^ T[fp >> RABIN_SHIFT];\n \treturn fp;\n}\n\nstatic int add_copy (unsigned src, unsigned tgt, unsigned length)\n{\n \tif (copy_count == max_copies) {\n \t\tmax_copies *= 2;\n\n \t\tif (!max_copies) {\n \t\t\tmax_copies = MAX_COPIES;\n \t\t\tcopies = malloc (max_copies * sizeof (CopyInfo));\n \t\t} else\n \t\t\tcopies = realloc(copies,\n \t\t\t   max_copies * sizeof (CopyInfo));\n \t\tif (!copies)\n \t\t\treturn 0;\n \t}\n\n \tcopies[copy_count].src = src;\n \tcopies[copy_count].tgt = tgt;\n \tcopies[copy_count].length = length;\n \treturn ++copy_count;\n}\n\nstatic unsigned maxofs[256];\nstatic unsigned maxlen[256];\nstatic unsigned maxfp[256];\n\nstatic const unsigned small_idx_size = SMALL_HTAB_SIZE;\nstatic short unsigned small_idx[SMALL_HTAB_SIZE];\n\nstatic void small_init_idx (unsigned char * data, unsigned len,\n                      \t    unsigned head, unsigned tail)\n{\n \tconst unsigned index_step = SMALL_INDEX_STEP;\n \tunsigned j = head - head % index_step;\n \tunsigned k;\n\n \tif (len < index_step) return;\n\n \tidx_data = data;\n \tidx_data_len = len;\n \tlen -= MIN (len, tail + (index_step - 1));\n\n \tmemset (small_idx, 0, sizeof(small_idx));\n\n \twhile (j < len) {\n \t\tpoly_t fp = 0;\n \t\tdo\n \t\t\tfp = ((fp << 8) | data[j++]) ^ T[fp >> RABIN_SHIFT];\n \t\twhile (j % index_step);\n \t\tsmall_idx[fp % small_idx_size] = j >> SMALL_SHIFT;\n \t}\n}\n\nstatic void init_idx (unsigned char *data, unsigned len, int level,\n \t\t      unsigned head, unsigned tail)\n{\n \tunsigned index_step\n \t  = RABIN_WINDOW_SIZE / sizeof(unsigned) * sizeof(unsigned);\n \tunsigned j, k;\n \tunsigned char ch = 0;\n \tunsigned runlen = 0;\n \tpoly_t fp = 0;\n\n \t/* Special case small files at low optimization levels */\n \tif (level <= 1 && len < MAX_SMALL_SIZE\n \t  && len - head - tail < (SMALL_HTAB_SIZE * SMALL_INDEX_STEP)) {\n \t\tsmall_init_idx(data, len, head, tail);\n \t\treturn;\n \t}\n\n \tassert (len <= MAX_SIZE);\n \tassert (head < len);\n \tassert (level >= 0 && level <= 9);\n \tmemset(maxofs, 0, sizeof(maxofs));\n \tmemset(maxlen, 0, sizeof(maxlen));\n \tmemset(maxfp, 0, sizeof(maxfp));\n\n \t/* Smaller step size for higher optimization levels.\n \t   The index_step must be a multiple of the word size */\n \tif (level >= 1)\n \t\tindex_step = MIN(index_step, 4 * sizeof (unsigned));\n \tif (level >= 3)\n \t\tindex_step = MIN (index_step, 3 * sizeof (unsigned));\n \tif (level >= 4)\n \t\tindex_step = MIN (index_step, 2 * sizeof (unsigned));\n \tif (level >= 6)\n \t\tindex_step = MIN (index_step, 1 * sizeof (unsigned));\n \tassert (index_step && !(index_step % sizeof (unsigned)));\n\n \t/* Add fixed amount to hash table size, as small files will benefit\n \t   a lot without using significantly more memory or time. */\n \tidx_size = (level + 1) * ((len - head - tail) / index_step) / 2;\n \tidx_size = MIN (idx_size + MIN_HTAB_SIZE, MAX_HTAB_SIZE - 1);\n\n \t/* Round up to next power of two, but limit to MAX_HTAB_SIZE. */\n \t{\n \t\tunsigned s = MIN_HTAB_SIZE;\n \t\twhile (s < idx_size) s += s;\n \t\tidx_size = s;\n \t}\n\n \tidx_data = data;\n \tidx_data_len = len;\n \tidx = calloc(idx_size, sizeof(unsigned));\n\n \t/* It is tempting to first index higher addresses, so hashes of lower\n \t   addresses will get preference in the hash table. However, for\n \t   repetitive patterns with a period that is a divisor of the\n \t   fingerprint window, this may mean the match is not anchored at\n \t   the end. Furthermore, even when using a window length that is\n \t   prime, the benefits are small and the irregularity of the first\n \t   matches being more important is not worth it. */\n\n \trabin_reset();\n\n \tch = 0;\n \trunlen = 0;\n\n \tif (head < RABIN_WINDOW_SIZE + index_step)\n \t\thead = 0;\n \telse {\n \t\thead -= head % index_step;\n \t\tfor (j = head - RABIN_WINDOW_SIZE + 1; j < head; j++)\n \t\t\tfp = rabin_slide (fp, data[j]);\n \t}\n\n \tfor (j = head; j + index_step < len - tail; j += index_step) {\n \t\tunsigned char pch = 0;\n \t\tunsigned hash;\n\n \t\tfor (k = 0; k < index_step; k++) {\n \t\t\tpch = ch;\n \t\t\tch = data[j + k];\n \t\t\tif (ch != pch)\n \t\t\t\trunlen = 0;\n \t\t\trunlen++;\n \t\t\tfp = rabin_slide(fp, ch);\n \t\t}\n\n \t\t/* See if there is a word-aligned window-sized run of\n \t\t   equal characters */\n \t\tif (runlen >= RABIN_WINDOW_SIZE + sizeof(unsigned) - 1) {\n \t\t\t/* Skip ahead to end of run */\n \t\t\twhile (j + k < len && data[j + k] == ch) {\n \t\t\t\tk++;\n \t\t\t\trunlen++;\n \t\t\t}\n\n \t\t\t/* Although matches are usually anchored at the end,\n \t\t\t   in the case of extended runs of equal characters\n \t\t\t   it is better to anchor after the first\n \t\t\t   RABIN_WINDOW_SIZE bytes. This allows for quick\n \t\t\t   skip ahead while matching such runs, avoiding\n \t\t\t   unneeded fingerprint calculations.\n \t\t\t   Also, when anchoring at the end, matches will be\n \t\t\t   generated after every word, because the fingerprint\n \t\t\t   stays constant. Even though all matches would get\n \t\t\t   combined during match optimization, it wastes time\n \t\t\t   and space. */\n \t\t\tif (runlen > maxlen[pch] + 4) {\n \t\t\t\tunsigned ofs;\n \t\t\t\t/* ofs points RABIN_WINDOW_SIZE bytes after\n \t\t\t\t   the start of the run, rounded up to the\n \t\t\t\t   next word */\n \t\t\t\tofs = j + k - runlen + RABIN_WINDOW_SIZE\n \t\t\t\t   + (sizeof (unsigned) - 1);\n \t\t\t\tofs -= ofs % sizeof(unsigned);\n \t\t\t\tmaxofs[pch] = ofs;\n \t\t\t\tmaxlen [pch] = runlen;\n \t\t\t\tassert(maxfp[pch] == 0\n \t\t\t\t  || maxfp[pch] == (unsigned)fp);\n \t\t\t\tmaxfp[pch] = (unsigned)fp;\n \t\t\t}\n \t\t\t/* Keep input aligned as if no special run\n \t\t\t   processing had taken place */\n \t\t\tj += k - (k % index_step) - index_step;\n \t\t\tk = index_step;\n \t\t}\n\n \t\t/* Testing showed that avoiding collisions using secondary\n \t\t   hashing, or hash chaining had little effect and is not\n \t\t   worth the time. */\n \t\thash = ((unsigned)fp) & (idx_size - 1);\n \t\tidx[hash] = j + k;\n \t}\n\n \t/* Lastly, index the longest runs of equal characters found before.\n \t   This ensures we always match the longerst such runs available.  */\n \tfor (j = 0; j < 256; j++)\n \t\tif (maxlen[j])\n \t\t\tidx[maxfp[j] % idx_size] = maxofs[j];\n}\n\n/* Match data against the current index and record all possible copies */\nstatic int small_find_copies(unsigned char *data, unsigned len, unsigned head)\n{\n \tunsigned j = head < RABIN_WINDOW_SIZE ? 0 : head - RABIN_WINDOW_SIZE;\n \tpoly_t fp = 0;\n\n \twhile (j < MAX (head, RABIN_WINDOW_SIZE) && j < len)\n \t\tfp = ((fp << 8) | data[j++]) ^ T[fp >> RABIN_SHIFT];\n\n \twhile (j < len) {\n \t\tunsigned ofs, src, tgt, runlen, maxrun;\n\n \t\tfp ^= U[data[j - RABIN_WINDOW_SIZE]];\n \t\tfp = ((fp << 8) | data[j++]) ^ T[fp >> RABIN_SHIFT];\n\n \t\tofs = small_idx[fp & (small_idx_size - 1)] << SMALL_SHIFT;\n\n \t\t/* Invariant:\n \t\t   data[0] .. data[j-1] has been processed\n \t\t   fp is fingerprint of sliding window ending at j-1\n \t\t   ofs is zero or points just past tentative match\n \t\t   ofs is a multiple of index_step */\n\n \t\tif (!ofs)\n \t\t\tcontinue;\n\n \t\trunlen = 0;\n \t\ttgt = j - 4;\n \t\tsrc = ofs - 4;\n \t\tmaxrun = MIN(idx_data_len - src, len - tgt);\n\n \t\t/* Hot loop */\n \t\twhile (runlen < maxrun &&\n \t\t       data[tgt + runlen] == idx_data[src + runlen])\n \t\t\trunlen++;\n \t\tif (runlen < 4)\n \t\t\tcontinue;\n\n \t\tif (!add_copy(src, tgt, runlen)) return 0;\n\n \t\t/* For runs extending more than RABIN_WINDOW_SIZE bytes past j,\n \t\t   skip ahead to prevent useless fingerprint computations. */\n \t\tif (tgt + runlen > j + RABIN_WINDOW_SIZE)\n \t\t{\n \t\t\tfp = 0;\n \t\t\tj = tgt + runlen - RABIN_WINDOW_SIZE;\n \t\t\twhile (j < tgt + runlen)\n \t\t\t\tfp = ((fp << 8) | data[j++])\n \t\t\t\t      ^ T[fp >> RABIN_SHIFT];\n \t\t}\n\n \t\t/* Quickly scan ahead without looking for matches\n \t\t   until the end of this run */\n \t\twhile (j < tgt + runlen) {\n \t\t\tfp ^= U[data[j - RABIN_WINDOW_SIZE]];\n \t\t\tfp = ((fp << 8) | data[j++]) ^ T[fp >> RABIN_SHIFT];\n \t\t}\n \t}\n\n \treturn 1;\n}\n\n/* Match data against the current index and record all possible copies */\nstatic int find_copies(unsigned char *data, unsigned len, unsigned head)\n{\n \tunsigned j = head < RABIN_WINDOW_SIZE ? 0 : head - RABIN_WINDOW_SIZE;\n \tpoly_t fp = 0;\n\n \tassert (idx_data);\n\n \tif (!idx) return small_find_copies (data, len, head);\n\n \trabin_reset();\n\n \twhile (j < head + RABIN_WINDOW_SIZE && j < len)\n \t\tfp = rabin_slide(fp, data[j++]);\n\n \twhile (j < len) {\n \t\tunsigned ofs, src, tgt, runlen, maxrun;\n\n \t\tfp = rabin_slide(fp, data[j++]);\n \t\tofs = idx[fp & (idx_size - 1)];\n\n \t\t/* Invariant:\n \t\t   data[0] .. data[j-1] has been processed\n \t\t   fp is fingerprint of sliding window ending at j-1\n \t\t   ofs is zero or points just past tentative match\n \t\t   ofs is a multiple of index_step */\n\n \t\tif (!ofs)\n \t\t\tcontinue;\n\n \t\trunlen = 0;\n \t\ttgt = j - 4;\n \t\tsrc = ofs - 4;\n \t\tmaxrun = MIN(idx_data_len - src, len - tgt);\n\n \t\t/* Hot loop */\n \t\twhile (runlen < maxrun &&\n \t\t       data[tgt + runlen] == idx_data[src + runlen])\n \t\t\trunlen++;\n \t\tif (runlen < 4)\n \t\t\tcontinue;\n\n \t\tif (!add_copy(src, tgt, runlen)) return 0;\n\n \t\t/* For runs extending more than RABIN_WINDOW_SIZE bytes past j,\n \t\t   skip ahead to prevent useless fingerprint computations. */\n \t\tif (tgt + runlen > j + RABIN_WINDOW_SIZE)\n \t\t\tj = tgt + runlen - RABIN_WINDOW_SIZE;\n\n \t\t/* Quickly scan ahead without looking for matches\n \t\t   until the end of this run */\n \t\twhile (j < tgt + runlen)\n \t\t\tfp = rabin_slide(fp, data[j++]);\n \t}\n\n \treturn 1;\n}\n\nstatic unsigned header_length(unsigned srclen, unsigned tgtlen)\n{\n \tunsigned len = 0;\n \tassert (srclen <= MAX_SIZE && tgtlen <= MAX_SIZE);\n\n \t/* GIT headers start with the length of the source and target,\n \t   with 7 bits per byte, least significant byte first, and\n \t   the high bit indicating continuation. */\n \tdo { len++; srclen >>= 7; } while (srclen);\n \tdo { len++; tgtlen >>= 7; } while (tgtlen);\n\n \treturn len;\n}\n\nstatic unsigned char *\nwrite_header(unsigned char *patch, unsigned srclen, unsigned tgtlen)\n{\n \tassert (srclen <= MAX_SIZE && tgtlen <= MAX_SIZE);\n\n \twhile (srclen >= 0x80) {\n \t\t*patch++ = srclen | 0x80;\n \t\tsrclen >>= 7;\n \t}\n \t*patch++ = srclen;\n\n \twhile (tgtlen >= 0x80) {\n \t\t*patch++ = tgtlen | 0x80;\n \t\ttgtlen >>= 7;\n \t}\n \t*patch++ = tgtlen;\n\n \treturn patch;\n}\n\nstatic unsigned data_length(unsigned length)\n{\n \t/* Can only include 0x7f data bytes per command */\n \tunsigned partial = length % 0x7f;\n \tassert (length > 0 && length <= MAX_SIZE);\n \tif (partial) partial++;\n \treturn partial + (length / 0x7f) * 0x80;\n}\n\nstatic unsigned char *\nwrite_data(unsigned char *patch, unsigned char *data, unsigned size)\n{\n \tassert (size > 0 && size < MAX_SIZE);\n \t/* The return value must be equal to patch + data_length (patch, size).\n \t   This correspondence is essential for calculating the patch size.  */\n\n \t/* GIT has no data commands for large data, rest is same as GDIFF */\n \tdo {\n \t\tunsigned s = size;\n \t\tif (s > 0x7f)\n \t\t\ts = 0x7f;\n \t\t*patch++ = s;\n \t\tmemcpy(patch, data, s);\n \t\tdata += s;\n \t\tpatch += s;\n \t\tsize -= s;\n \t} while (size);\n\n \treturn patch;\n}\n\nstatic unsigned copy_length (unsigned offset, unsigned length)\n{\n \tunsigned size = 0;\n\n \tassert (offset < MAX_SIZE && length < MAX_SIZE);\n\n \t/* For now we only copy a maximum of 0x10000 bytes per command.\n \t   Longer copies are broken into pieces of that size. */\n \tdo {\n \t\tsigned s = length;\n \t\tif (s > 0x10000)\n \t\t\ts = 0x10000;\n \t\tsize += !!(s & 0xff) + !!(s & 0xff00);\n \t\tsize += !!(offset & 0xff) + !!(offset & 0xff00) +\n \t\t\t!!(offset & 0xff0000) + !!(offset & 0xff000000);\n \t\tsize += 1;\n \t\toffset += s;\n \t\tlength -= s;\n \t} while (length);\n\n \treturn size;\n}\n\nstatic unsigned char *\nwrite_copy(unsigned char *patch, unsigned offset, unsigned size)\n{\n \t/* The return value must be equal to patch + copy_length\n \t   (patch, offset, size). This correspondence is essential\n \t   for calculating the patch size.  */\n\n \tdo {\n \t\tunsigned char c = 0x80, *cmd = patch++;\n \t\tunsigned v, s = size;\n \t\tif (s > 0x10000)\n \t\t\ts = 0x10000;\n\n \t\tv = offset;\n \t\tif (v & 0xff) c |= 0x01, *patch++ = v;\n \t\tv >>= 8;\n \t\tif (v & 0xff) c |= 0x02, *patch++ = v;\n \t\tv >>= 8;\n \t\tif (v & 0xff) c |= 0x04, *patch++ = v;\n \t\tv >>= 8;\n \t\tif (v & 0xff) c |= 0x08, *patch++ = v;\n\n \t\tv = s;\n \t\tif (v & 0xff) c |= 0x10, *patch++ = v;\n \t\tv >>= 8;\n \t\tif (v & 0xff) c |= 0x20, *patch++ = v;\n\n \t\t*cmd = c;\n \t\toffset += s;\n \t\tsize -= s;\n \t} while (size);\n\n \treturn patch;\n}\n\nstatic unsigned\nprocess_copies (unsigned char *data, unsigned length, unsigned maxlen)\n{\n \tint j;\n \tunsigned ptr = length;\n \tunsigned patch_bytes = header_length(idx_data_len, length);\n\n \t/* Work through the copies backwards, extending each one backwards. */\n \tfor (j = copy_count - 1; j >= 0; j--) {\n \t\tCopyInfo *copy = copies+j;\n \t\tunsigned src = copy->src;\n \t\tunsigned tgt = copy->tgt;\n \t\tunsigned len = copy->length;\n \t\tint data_follows;\n\n \t\tif (tgt + len > ptr) {\n \t\t\t/* Part of copy already covered by later one,\n \t\t\t   so shorten copy. */\n \t\t\tif (ptr < tgt) {\n \t\t\t\t/* Copy completely disappeared, but guess\n \t\t\t\t   that a backward extension might still be\n \t\t\t\t   useful. This extension is non-contiguous,\n \t\t\t\t   as it is irrelevant whether the skipped\n \t\t\t\t   data would have matched or not. Be careful\n \t\t\t\t   to not extend past the beginning of\n \t\t\t\t   the source. */\n \t\t\t\tunsigned adjust = tgt - ptr;\n\n \t\t\t\ttgt = ptr;\n \t\t\t\tsrc = (src < adjust) ? 0 : src - adjust;\n\n \t\t\t\tcopy->tgt = tgt;\n \t\t\t\tcopy->src = src;\n \t\t\t}\n\n \t\t\tlen = ptr - tgt;\n \t\t}\n\n \t\twhile (src && tgt && idx_data[src - 1] == data[tgt - 1]) {\n \t\t\tsrc--;\n \t\t\ttgt--;\n \t\t}\n \t\tlen += copy->tgt - tgt;\n\n \t\tdata_follows = (tgt + len < ptr);\n\n \t\t/* A short copy may cost as much as 6 bytes for the copy and\n \t\t   5 as result of an extra data command. It's not worth\n \t\t   having extra copies in order to just save a byte or two.\n \t\t   Being too smart here may hurt later compression as well. */\n \t\tif (len < (data_follows ? 16 : 10))\n \t\t\tlen = 0;\n\n \t\t/* Some target data is not covered by the copies, account for\n \t\t   the DATA command that will follow the copy. */\n \t\tif (len && data_follows)\n \t\t\tpatch_bytes += data_length(ptr - (tgt + len));\n\n \t\t/* Everything about the copy is known and will not change.\n \t\t   Write back the new information and update the patch size\n \t\t   with the size of the copy instruction. */\n \t\tcopy->length = len;\n \t\tcopy->src = src;\n \t\tcopy->tgt = tgt;\n\n \t\tif (len) {\n \t\t\t/* update patch size for copy command */\n \t\t\tpatch_bytes += copy_length (src, len);\n \t\t\tptr = tgt;\n \t\t} else if (j == copy_count - 1) {\n \t\t\t/* Remove empty copies at end of list. */\n \t\t\tcopy_count--;\n \t\t}\n\n \t\tif (patch_bytes > maxlen)\n \t\t\treturn 0;\n \t}\n\n \t/* Account for data before first copy */\n \tif (ptr != 0)\n \t\tpatch_bytes += data_length(ptr);\n\n \tif (patch_bytes > maxlen)\n \t\treturn 0;\n \treturn patch_bytes;\n}\n\nstatic void *\ncreate_delta (unsigned char *data, unsigned len,\n \t      unsigned char *delta, unsigned delta_size)\n{\n \tunsigned char *ptr = delta;\n \tunsigned offset = 0;\n \tint j;\n\n \tptr = write_header(ptr, idx_data_len, len);\n\n \tfor (j = 0; j < copy_count; j++) {\n \t\tCopyInfo *copy = copies + j;\n \t\tunsigned copylen = copy->length;\n\n \t\tif (!copylen)\n \t\t\tcontinue;\n\n \t\tif (copy->tgt > offset) {\n \t\t\tptr = write_data(ptr, data + offset,\n \t\t\t   copy->tgt - offset);\n \t\t}\n\n \t\tptr = write_copy(ptr, copy->src, copylen);\n \t\toffset = copy->tgt + copylen;\n \t}\n\n \tif (offset < len)\n \t\tptr = write_data(ptr, data + offset, len - offset);\n\n \tassert(ptr - delta == delta_size);\n\n \treturn delta;\n}\n\nstatic void finalize_idx()\n{\n \tif (max_copies > 8 * MAX_COPIES) {\n \t\tfree(copies);\n \t\tcopies = 0;\n \t\tmax_copies = 0;\n \t}\n \tcopy_count = 0;\n \tif (idx) free(idx);\n \tidx = 0;\n \tidx_size = 0;\n \tidx_data = 0;\n \tidx_data_len = 0;\n}\n\nstatic unsigned\nmatch_head (unsigned char *from, unsigned char *to, unsigned size)\n{\n \tunsigned head = 0;\n \twhile (head < size && from[head] == to[head]) head++;\n \treturn head;\n}\n\nstatic unsigned\nmatch_tail (unsigned char *from, unsigned char *to, unsigned size)\n{\n \tunsigned tail = 0;\n \twhile (tail < size && *(from - tail) == *(to - tail)) tail++;\n \treturn tail;\n}\n\nvoid *diff_delta(void *from_buf, unsigned long from_size,\n \t\t void *to_buf, unsigned long to_size,\n \t\t unsigned long *delta_size, unsigned long max_size)\n{\n \tunsigned char *delta = 0;\n \tunsigned dsize;\n         unsigned head = 0;\n         unsigned tail = 0;\n\n \tassert (from_size <= MAX_SIZE && to_size <= MAX_SIZE);\n\n \t/* The following actually takes care of about half of all target\n \t   data. This is performance critical, and may need some work. */\n         head = match_head(from_buf, to_buf, MIN(from_size, to_size));\n \ttail = match_tail(from_buf + (from_size - 1), to_buf + (to_size - 1),\n \t                  MIN(from_size, to_size - head));\n\n \tif (head <= RABIN_WINDOW_SIZE) head = 0;\n \tif (tail <= RABIN_WINDOW_SIZE) tail = 0;\n\n \tif (!max_size)\n \t\tmax_size = from_size;\n\n \tinit_idx (from_buf, from_size, 1, head, tail);\n\n \tif (head) add_copy (0, 0, head);\n\n \tif (head + tail + RABIN_WINDOW_SIZE < from_size) {\n \t\tif (!find_copies(to_buf, to_size - tail, head))\n \t\t\treturn 0;\n \t}\n \tif (tail) add_copy (from_size - tail, to_size - tail, tail);\n\n \tdsize = process_copies(to_buf, to_size, max_size);\n \tif (dsize)\n \t{\n \t\tdelta = malloc (dsize);\n \t\tdelta = create_delta (to_buf, to_size, delta, dsize);\n \t}\n \tfinalize_idx ();\n \tif (delta)\n \t\t*delta_size = dsize;\n \treturn delta;\n}\n"},{"id":"19212","messageId":"E7746844-4275-4B9E-AC75-2B68CD056BAD@adacore.com","threadId":"3980","inReplyTo":"Pine.GSO.4.60.0604272132170.9650@nile.gnat.com","subject":"Re: PATCH: New diff-delta.c implementation (updated)","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-28T02:07:43Z","receivedAt":"2006-04-28T02:07:43Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Apr 27, 2006, at 21:59, Geert Bosch wrote:\n\n> The result has been only a slight increase in delta size for\n> very large test cases (but with better performance),\n\nJust to clarify: this is compared to my initial implementation.\nFor very large test cases, both delta size and execution time\nare much less than the current implementation.\n\n   -Geert\n"},{"id":"19213","messageId":"7v1wvigzka.fsf@assigned-by-dhcp.cox.net","threadId":"3980","inReplyTo":"Pine.GSO.4.60.0604272132170.9650@nile.gnat.com","subject":"Re: PATCH: New diff-delta.c implementation (updated)","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-28T03:16:05Z","receivedAt":"2006-04-28T03:16:05Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Geert Bosch <bosch@gnat.com> writes:\n\n> Even though the previous version did really well on large files\n> with many changes, performance was lacking for the many small\n> files with very few changes that are so common for a VCS.\n>...\n> The result has been only a slight increase in delta size for\n> very large test cases (but with better performance), and\n> both smaller deltas and faster execution speed for repacking\n> git.git. I had trouble cloning the Linux kernel repository,\n> but am now reasonably confident this will outperform the\n> existing algorithm pretty consistently.\n\nInteresting.\n\nInitial impression, the same test as before (a full packing of\nthe git.git repository that does not have _any_ pack -- all 18k\nobjects are loose).\n\nFirst, the incumbent, with the \"reusing delta-index\" patch applied.\n\nTotal 17724, written 17724 (delta 12002), reused 0 (delta 0)\n34.02user 6.48system 0:42.87elapsed 94%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+434478minor)pagefaults 0swaps\n\n 6188418 pack-nico-f1fac077a093ffdaf094aab2b7f11859ec0c18f1.pack\n\nThen diff-delta.c replaced with your version.\n\nTotal 17724, written 17724 (delta 12012), reused 0 (delta 0)\n44.87user 6.54system 0:54.01elapsed 95%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+441124minor)pagefaults 0swaps\n\n 6099183 pack-geert-f1fac077a093ffdaf094aab2b7f11859ec0c18f1.pack\n\nSecond impression, in a recent kernel tree which is mostly\npacked.  Packing 41k objects (v2.6.16..v2.6.17-rc3), with\n\"git-pack-objects --no-reuse-delta\".\n\n(Nico)\nTotal 41591, written 41591 (delta 29285), reused 8563 (delta 0)\n169.08user 12.60system 3:27.68elapsed 87%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (2major+1099928minor)pagefaults 0swaps\n\n37363966 pack-nico-b9e4339c482cb7d787a2117e6da6eb2114053abc.pack\n\n(Geert)\nTotal 41591, written 41591 (delta 29347), reused 8427 (delta 0)\n243.71user 12.32system 4:28.11elapsed 95%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+1077843minor)pagefaults 0swaps\n\n37165890 pack-geert-b9e4339c482cb7d787a2117e6da6eb2114053abc.pack\n\n\nOf course, the absolute numbers do not matter, but for the\nrecord these are on my Duron 750, 760MB or so RAM and with\nrelatively slow disks.\n\nIn the kernel repository (checked out is near the tip of the\nsource tree), the largest files are fs/nls/nls_cp949.c (900kB\nkorean character encoding), drivers/usb/misc/emi62_fw_s.h\n(800kB, Emagic firmware blob), arch/m68k/ifpsp060/src/fpsp.S\n(750kB, floating point emulation?), and nowhere near your\nalgorithm really should shine.\n\nWe would probably want some internal logic that says \"if we see\nthat blobs larger than X MB is involved in the packing, we\nshould use this version of diff-delta, otherwise the other one.\"\n"},{"id":"19214","messageId":"7vfyjyfhn5.fsf@assigned-by-dhcp.cox.net","threadId":"3980","inReplyTo":"7v1wvigzka.fsf@assigned-by-dhcp.cox.net","subject":"Re: PATCH: New diff-delta.c implementation (updated)","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-28T04:28:30Z","receivedAt":"2006-04-28T04:28:30Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> In the kernel repository (checked out is near the tip of the\n> source tree), the largest files are fs/nls/nls_cp949.c (900kB\n> korean character encoding), drivers/usb/misc/emi62_fw_s.h\n> (800kB, Emagic firmware blob), arch/m68k/ifpsp060/src/fpsp.S\n> (750kB, floating point emulation?), and nowhere near your\n> algorithm really should shine.\n>\n> We would probably want some internal logic that says \"if we see\n> that blobs larger than X MB is involved in the packing, we\n> should use this version of diff-delta, otherwise the other one.\"\n\nThird impression, synthetic workload.  A sequence of single file\nproject, the file is tarball of git.git tree (that is,\n\"git-tar-tree vX.Y.Z >tarball\"), 120 objects or so (1 commit per\nrev, 1 tree to hold 1 blob).  The (uncompressed) size of the 40\nblobs in the pack are between 2.06MB - 2.86MB (average 2.30MB).\n\n(Nico)\nTotal 123, written 123 (delta 38), reused 0 (delta 0)\n67.26user 1.03system 1:08.76elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+136066minor)pagefaults 0swaps\n\n1822079 pack-nico-26989d516c62197592d0d52db24dfc6a58b633eb.pack\n\n\n(Geert)\nTotal 123, written 123 (delta 38), reused 0 (delta 0)\n67.23user 1.35system 1:09.25elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+164124minor)pagefaults 0swaps\n\n1683139 pack-geert-26989d516c62197592d0d52db24dfc6a58b633eb.pack\n\nThat's an 8% improvement in the same time, which is quite\nimpressive.  But I am _very_ unhappy about this particular\nsynthetic workload.  I wonder if there are projects with many\nlarge blobs that is updated often, so that we can use it as a\nyardstick.  Maybe Wine people have icons, background images and\nsounds perhaps?  But I suspect you would not update them that\noften.\n\nThinking about it, it does not make much sense, at least to me,\nto store large tarballs or binary blobs or whatnot in a SCM (we\nare _not_ in the archival business) and keeping track of their\nchanges.  The tarball is out of question -- it is not a source\n(in GPL sense of the word -- it is not a preferred way to make\nmodification; you modify constituent files and bundle up the\nresult as a new tarball).  Graphics images, perhaps.\n"}]}