{"thread":{"id":"8344","subject":"[PATCH 2/3] git-pack-objects: cache small deltas between big objects","startedAt":"2007-05-28T21:20:57Z","lastAt":"2007-05-29T02:53:49Z","messageCount":6,"participants":["Martin Koegler","Dana How","Nicolas Pitre","Shawn O. Pearce"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"43521","messageId":"11803872591522-git-send-email-mkoegler@auto.tuwien.ac.at","threadId":"8344","inReplyTo":null,"subject":"[PATCH 1/3] builtin-pack-objects: don't fail, if delta is not possible","fromName":"Martin Koegler","fromEmail":"mkoegler@auto.tuwien.ac.at","sentAt":"2007-05-28T21:20:57Z","receivedAt":"2007-05-28T21:20:57Z","isPatch":true,"sender":{"key":"mkoegler@auto.tuwien.ac.at","avatar":null},"body":"If builtin-pack-objects runs out of memory while finding\nthe best deltas, it bails out with an error.\n\nIf the delta index creation fails (because there is not enough memory),\nwe can downgrade the error message to a warning and continue with the\nnext object.\n\nSigned-off-by: Martin Koegler <mkoegler@auto.tuwien.ac.at>\n---\nThe patches apply on top of next.\n\n builtin-pack-objects.c |    8 ++++++--\n 1 files changed, 6 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex e52332d..17627b3 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -1454,8 +1454,12 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t}\n \tif (!src->index) {\n \t\tsrc->index = create_delta_index(src->data, src_size);\n-\t\tif (!src->index)\n-\t\t\tdie(\"out of memory\");\n+\t\tif (!src->index) {\n+\t\t\tstatic int warned = 0;\n+\t\t\tif (!warned++)\n+\t\t\t\twarning(\"suboptimal pack - out of memory\");\n+\t\t\treturn 0;\n+\t\t}\n \t}\n \n \tdelta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);\n-- \n1.5.2.846.g9a144\n"},{"id":"43520","messageId":"11803872591103-git-send-email-mkoegler@auto.tuwien.ac.at","threadId":"8344","inReplyTo":"11803872591522-git-send-email-mkoegler@auto.tuwien.ac.at","subject":"[PATCH 2/3] git-pack-objects: cache small deltas between big objects","fromName":"Martin Koegler","fromEmail":"mkoegler@auto.tuwien.ac.at","sentAt":"2007-05-28T21:20:58Z","receivedAt":"2007-05-28T21:20:58Z","isPatch":true,"sender":{"key":"mkoegler@auto.tuwien.ac.at","avatar":null},"body":"Creating deltas between big blobs is a CPU and memory intensive task.\nIn the writing phase, all (not reused) deltas are redone.\n\nThis patch adds support for caching deltas from the deltifing phase, so\nthat that the writing phase is faster.\n\nThe caching is limited to small deltas to avoid increasing memory usage very much.\nThe implemented limit is (memory needed to create the delta)/1024.\n\nSigned-off-by: Martin Koegler <mkoegler@auto.tuwien.ac.at>\n---\nThe patch is an improved version of the last patch. I added a limit\nfor the cache size. It's only configureable by git-config, as \nbuiltin-back-objects (git-repack) has already enough options.\n\nThe patch applies on top of next.\n\n Documentation/config.txt |    5 +++\n builtin-pack-objects.c   |   69 ++++++++++++++++++++++++++++++++++++----------\n 2 files changed, 59 insertions(+), 15 deletions(-)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 3d8f03d..83cc4cd 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -567,6 +567,11 @@ pack.compression::\n \tslowest.  If not set,  defaults to core.compression.  If that is\n \tnot set,  defaults to -1.\n \n+pack.deltaCacheSize::\n+\tThe maxium memory in bytes used for caching deltas in \n+\tgitlink:git-pack-objects[1]. \t\n+\tA value of 0 means no limit. Defaults to 0.\n+\n pull.octopus::\n \tThe default merge strategy to use when pulling multiple branches\n \tat once.\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 17627b3..85e08dc 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -36,6 +36,7 @@ struct object_entry {\n \tstruct object_entry *delta_sibling; /* other deltified objects who\n \t\t\t\t\t     * uses the same base as me\n \t\t\t\t\t     */\n+\tvoid *delta_data;\t/* cached delta (uncompressed) */\n \tunsigned long delta_size;\t/* delta data size (uncompressed) */\n \tenum object_type type;\n \tenum object_type in_pack_type;\t/* could be delta */\n@@ -76,6 +77,9 @@ static struct progress progress_state;\n static int pack_compression_level = Z_DEFAULT_COMPRESSION;\n static int pack_compression_seen;\n \n+static unsigned long delta_cache_size = 0;\n+static unsigned long max_delta_cache_size = 0;\n+\n /*\n  * The object names in objects array are hashed with this hashtable,\n  * to help looking up the entry by object name.\n@@ -405,24 +409,31 @@ static unsigned long write_object(struct sha1file *f,\n \t\tz_stream stream;\n \t\tunsigned long maxsize;\n \t\tvoid *out;\n-\t\tbuf = read_sha1_file(entry->sha1, &type, &size);\n-\t\tif (!buf)\n-\t\t\tdie(\"unable to read %s\", sha1_to_hex(entry->sha1));\n-\t\tif (size != entry->size)\n-\t\t\tdie(\"object %s size inconsistency (%lu vs %lu)\",\n-\t\t\t    sha1_to_hex(entry->sha1), size, entry->size);\n-\t\tif (usable_delta) {\n-\t\t\tbuf = delta_against(buf, size, entry);\n+\t\tif (entry->delta_data && usable_delta) {\n+\t\t\tbuf = entry->delta_data;\n \t\t\tsize = entry->delta_size;\n \t\t\tobj_type = (allow_ofs_delta && entry->delta->offset) ?\n \t\t\t\tOBJ_OFS_DELTA : OBJ_REF_DELTA;\n \t\t} else {\n-\t\t\t/*\n-\t\t\t * recover real object type in case\n-\t\t\t * check_object() wanted to re-use a delta,\n-\t\t\t * but we couldn't since base was in previous split pack\n-\t\t\t */\n-\t\t\tobj_type = type;\n+\t\t\tbuf = read_sha1_file(entry->sha1, &type, &size);\n+\t\t\tif (!buf)\n+\t\t\t\tdie(\"unable to read %s\", sha1_to_hex(entry->sha1));\n+\t\t\tif (size != entry->size)\n+\t\t\t\tdie(\"object %s size inconsistency (%lu vs %lu)\",\n+\t\t\t\t    sha1_to_hex(entry->sha1), size, entry->size);\n+\t\t\tif (usable_delta) {\n+\t\t\t\tbuf = delta_against(buf, size, entry);\n+\t\t\t\tsize = entry->delta_size;\n+\t\t\t\tobj_type = (allow_ofs_delta && entry->delta->offset) ?\n+\t\t\t\t\tOBJ_OFS_DELTA : OBJ_REF_DELTA;\n+\t\t\t} else {\n+\t\t\t\t/*\n+\t\t\t\t * recover real object type in case\n+\t\t\t\t * check_object() wanted to re-use a delta,\n+\t\t\t\t * but we couldn't since base was in previous split pack\n+\t\t\t\t */\n+\t\t\t\tobj_type = type;\n+\t\t\t}\n \t\t}\n \t\t/* compress the data to store and put compressed length in datalen */\n \t\tmemset(&stream, 0, sizeof(stream));\n@@ -1385,6 +1396,20 @@ struct unpacked {\n \tstruct delta_index *index;\n };\n \n+static int delta_cacheable (struct unpacked *trg, struct unpacked *src,\n+\t\t\t    unsigned long src_size, unsigned long trg_size,\n+\t\t\t    unsigned long delta_size)\n+{\n+\tif (max_delta_cache_size && delta_cache_size + delta_size > max_delta_cache_size)\n+\t\treturn 0;\n+\n+\t/* cache delta, if objects are large enough compared to delta size */\n+\tif ((src_size >> 20) + (trg_size >> 21) > (delta_size >> 10))\n+\t\treturn 1;\n+\n+\treturn 0;\n+}\n+\n /*\n  * We search for deltas _backwards_ in a list sorted by type and\n  * by size, so that we see progressively smaller and smaller files.\n@@ -1466,10 +1491,20 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \tif (!delta_buf)\n \t\treturn 0;\n \n+\tif (trg_entry->delta_data) {\n+\t\tdelta_cache_size -= trg_entry->delta_size;\n+\t\tfree (trg_entry->delta_data);\n+\t}\n+\ttrg_entry->delta_data = 0;\n \ttrg_entry->delta = src_entry;\n \ttrg_entry->delta_size = delta_size;\n \ttrg_entry->depth = src_entry->depth + 1;\n-\tfree(delta_buf);\n+\n+\tif (delta_cacheable (src, trg, src_size, trg_size, delta_size)) {\n+\t\ttrg_entry->delta_data = realloc(delta_buf, delta_size);\n+\t\tdelta_cache_size += trg_entry->delta_size;\n+\t} else\n+\t\tfree(delta_buf);\n \treturn 1;\n }\n \n@@ -1615,6 +1650,10 @@ static int git_pack_config(const char *k, const char *v)\n \t\tpack_compression_seen = 1;\n \t\treturn 0;\n \t}\n+\tif(!strcmp(k, \"pack.deltacachesize\")) {\n+\t\tmax_delta_cache_size = git_config_int(k, v);\n+\t\treturn 0;\n+\t}\n \treturn git_default_config(k, v);\n }\n \n-- \n1.5.2.846.g9a144\n"},{"id":"43522","messageId":"11803872602056-git-send-email-mkoegler@auto.tuwien.ac.at","threadId":"8344","inReplyTo":"11803872591103-git-send-email-mkoegler@auto.tuwien.ac.at","subject":"[PATCH 3/3] builtin-pack-object: cache small deltas","fromName":"Martin Koegler","fromEmail":"mkoegler@auto.tuwien.ac.at","sentAt":"2007-05-28T21:20:59Z","receivedAt":"2007-05-28T21:20:59Z","isPatch":true,"sender":{"key":"mkoegler@auto.tuwien.ac.at","avatar":null},"body":"Signed-off-by: Martin Koegler <mkoegler@auto.tuwien.ac.at>\n---\nCaching small deltas improves packing time even on small repostistories.\nRepacking git.git with a delta size limit of 1000 brings CPU time from\n66 to 49 seconds down. A limit of 500 bytes is only two secondes slower.\n\nThe implicit cache size limit is (#objects)*(delta size limit).\n\n Documentation/config.txt |    4 ++++\n builtin-pack-objects.c   |    8 ++++++++\n 2 files changed, 12 insertions(+), 0 deletions(-)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 83cc4cd..0061f7f 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -572,6 +572,10 @@ pack.deltaCacheSize::\n \tgitlink:git-pack-objects[1]. \t\n \tA value of 0 means no limit. Defaults to 0.\n \n+pack.deltaCacheLimit::\n+\tThe maxium size of a delta, that is cached in \n+\tgitlink:git-pack-objects[1]. Defaults to 1000.\n+\n pull.octopus::\n \tThe default merge strategy to use when pulling multiple branches\n \tat once.\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 85e08dc..c316fea 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -79,6 +79,7 @@ static int pack_compression_seen;\n \n static unsigned long delta_cache_size = 0;\n static unsigned long max_delta_cache_size = 0;\n+static unsigned long cache_max_small_delta_size = 1000;\n \n /*\n  * The object names in objects array are hashed with this hashtable,\n@@ -1403,6 +1404,9 @@ static int delta_cacheable (struct unpacked *trg, struct unpacked *src,\n \tif (max_delta_cache_size && delta_cache_size + delta_size > max_delta_cache_size)\n \t\treturn 0;\n \n+\tif (delta_size < cache_max_small_delta_size) \n+\t\treturn 1;\n+\n \t/* cache delta, if objects are large enough compared to delta size */\n \tif ((src_size >> 20) + (trg_size >> 21) > (delta_size >> 10))\n \t\treturn 1;\n@@ -1654,6 +1658,10 @@ static int git_pack_config(const char *k, const char *v)\n \t\tmax_delta_cache_size = git_config_int(k, v);\n \t\treturn 0;\n \t}\n+\tif(!strcmp(k, \"pack.deltacachelimit\")) {\n+\t\tcache_max_small_delta_size = git_config_int(k, v);\n+\t\treturn 0;\n+\t}\n \treturn git_default_config(k, v);\n }\n \n-- \n1.5.2.846.g9a144\n"},{"id":"43532","messageId":"56b7f5510705281733q2f5e7063j7e349b1a3821acc0@mail.gmail.com","threadId":"8344","inReplyTo":"11803872602056-git-send-email-mkoegler@auto.tuwien.ac.at","subject":"Re: [PATCH 3/3] builtin-pack-object: cache small deltas","fromName":"Dana How","fromEmail":"danahow@gmail.com","sentAt":"2007-05-29T00:33:51Z","receivedAt":"2007-05-29T00:33:51Z","isPatch":true,"sender":{"key":"danahow@gmail.com","avatar":null},"body":"On 5/28/07, Martin Koegler <mkoegler@auto.tuwien.ac.at> wrote:\n> Signed-off-by: Martin Koegler <mkoegler@auto.tuwien.ac.at>\n> ---\n> Caching small deltas improves packing time even on small repostistories.\n> Repacking git.git with a delta size limit of 1000 brings CPU time from\n> 66 to 49 seconds down. A limit of 500 bytes is only two secondes slower.\n>\n> The implicit cache size limit is (#objects)*(delta size limit).\n\nThis patchset appears a lot more robust over more special cases.\nThanks for your extra work,\n-- \nDana L. How  danahow@gmail.com  +1 650 804 5991 cell\n"},{"id":"43534","messageId":"alpine.LFD.0.99.0705282243280.11491@xanadu.home","threadId":"8344","inReplyTo":"11803872591522-git-send-email-mkoegler@auto.tuwien.ac.at","subject":"Re: [PATCH 1/3] builtin-pack-objects: don't fail, if delta is not possible","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-29T02:45:16Z","receivedAt":"2007-05-29T02:45:16Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 28 May 2007, Martin Koegler wrote:\n\n> If builtin-pack-objects runs out of memory while finding\n> the best deltas, it bails out with an error.\n> \n> If the delta index creation fails (because there is not enough memory),\n> we can downgrade the error message to a warning and continue with the\n> next object.\n\nIn the same vain, there is one realloc() that was turned into a \nxrealloc() in diff-delta.c.  I think this was a mistake and should \nprobably be a non fatal realloc again to let the caller go on.\n\n\nNicolas\n"},{"id":"43535","messageId":"20070529025349.GD7044@spearce.org","threadId":"8344","inReplyTo":"alpine.LFD.0.99.0705282243280.11491@xanadu.home","subject":"Re: [PATCH 1/3] builtin-pack-objects: don't fail, if delta is not possible","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-05-29T02:53:49Z","receivedAt":"2007-05-29T02:53:49Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre <nico@cam.org> wrote:\n> On Mon, 28 May 2007, Martin Koegler wrote:\n> \n> > If builtin-pack-objects runs out of memory while finding\n> > the best deltas, it bails out with an error.\n> > \n> > If the delta index creation fails (because there is not enough memory),\n> > we can downgrade the error message to a warning and continue with the\n> > next object.\n> \n> In the same vain, there is one realloc() that was turned into a \n> xrealloc() in diff-delta.c.  I think this was a mistake and should \n> probably be a non fatal realloc again to let the caller go on.\n\nAnd if those two calls fail to alloc their memory, they might want\nto try calling the pack window gc thingy (release_pack_memory(need,\n-1)) and then retry the alloc before they fail the delta generation.\nIts possible that we are better off releasing the LRU pack window\nand produce the delta, then to fail because we're hanging onto some\nmmap we don't need...\n\nAnd actaully release_pack_memory could get more aggressive now that\nthe index_data can be lazily loaded.  We could actually unload LRU\nindexes too.\n\n-- \nShawn.\n"}]}