{"thread":{"id":"18214","subject":"[PATCH 2/2] fast-import: treat large blobs (> 100 MiB) specially, by deflating them on-the-fly from stdin instead of keeping an entire copy in memory.","startedAt":"2009-03-08T18:40:57Z","lastAt":"2009-03-08T18:57:49Z","messageCount":2,"participants":["Sam Hocevar"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"107392","messageId":"20090308184057.GA9606@zoy.org","threadId":"18214","inReplyTo":null,"subject":"[PATCH 2/2] fast-import: treat large blobs (> 100 MiB) specially, by deflating them on-the-fly from stdin instead of keeping an entire copy in memory.","fromName":"Sam Hocevar","fromEmail":"sam@zoy.org","sentAt":"2009-03-08T18:40:57Z","receivedAt":"2009-03-08T18:40:57Z","isPatch":true,"sender":{"key":"sam@zoy.org","avatar":"https://gravatar.com/avatar/1fc1e5d8c3a8d737f14572135671adfbc0e61ffba5c3bc1d1b8a6f4aac764470?d=mp&s=160"},"body":"Since deltas need no longer be computed for such files, fast-import is\nnow twice as fast and memory usage decreases more than threefold when\nimporting large files.\n\nSigned-off-by: Sam Hocevar <sam@zoy.org>\n---\n I'd like to hear any suggestions on how to improve this patch. I am\nnot sure all the decisions I made by trying not to refactor too much\nof the code were appropriate. If at least the idea is welcome, I will\nalso write a proper patch to make the data size threshold a config\noption.\n\n Here is a graph of memory usage against time for the current version\nof fast-import and a patched version, when importing four 100 MiB files\nfilled with random data: http://zoy.org/~sam/git/git-faster-import.png\n\n fast-import.c |  155 +++++++++++++++++++++++++++++++++++++++++----------------\n 1 files changed, 112 insertions(+), 43 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 6419d00..bdd40e7 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1044,12 +1044,14 @@ static int store_object(\n \tstruct strbuf *dat,\n \tstruct last_object *last,\n \tunsigned char *sha1,\n-\tuintmax_t mark)\n+\tuintmax_t mark,\n+\tint orig_bytes)\n {\n \tvoid *out, *delta;\n \tstruct object_entry *e;\n \tunsigned char hdr[96];\n \tunsigned long hdrlen, deltalen;\n+\tsize_t outbytes;\n \tz_stream s;\n \n \te = insert_object(sha1);\n@@ -1066,7 +1068,9 @@ static int store_object(\n \t\treturn 1;\n \t}\n \n-\tif (last && last->data.buf && last->depth < max_depth) {\n+\t/* If orig_bytes is set, the object is already deflated and the\n+\t * caller does not want us to computes delta. */\n+\tif (!orig_bytes && last && last->data.buf && last->depth < max_depth) {\n \t\tdelta = diff_delta(last->data.buf, last->data.len,\n \t\t\tdat->buf, dat->len,\n \t\t\t&deltalen, 0);\n@@ -1077,24 +1081,30 @@ static int store_object(\n \t} else\n \t\tdelta = NULL;\n \n-\tmemset(&s, 0, sizeof(s));\n-\tdeflateInit(&s, pack_compression_level);\n-\tif (delta) {\n-\t\ts.next_in = delta;\n-\t\ts.avail_in = deltalen;\n+\tif (!orig_bytes) {\n+\t\tmemset(&s, 0, sizeof(s));\n+\t\tdeflateInit(&s, pack_compression_level);\n+\t\tif (delta) {\n+\t\t\ts.next_in = delta;\n+\t\t\ts.avail_in = deltalen;\n+\t\t} else {\n+\t\t\ts.next_in = (void *)dat->buf;\n+\t\t\ts.avail_in = dat->len;\n+\t\t}\n+\t\ts.avail_out = deflateBound(&s, s.avail_in);\n+\t\ts.next_out = out = xmalloc(s.avail_out);\n+\t\twhile (deflate(&s, Z_FINISH) == Z_OK)\n+\t\t\t/* nothing */;\n+\t\tdeflateEnd(&s);\n+\t\toutbytes = s.total_out;\n \t} else {\n-\t\ts.next_in = (void *)dat->buf;\n-\t\ts.avail_in = dat->len;\n+\t\tout = dat->buf;\n+\t\toutbytes = dat->len;\n \t}\n-\ts.avail_out = deflateBound(&s, s.avail_in);\n-\ts.next_out = out = xmalloc(s.avail_out);\n-\twhile (deflate(&s, Z_FINISH) == Z_OK)\n-\t\t/* nothing */;\n-\tdeflateEnd(&s);\n \n \t/* Determine if we should auto-checkpoint. */\n-\tif ((pack_size + 60 + s.total_out) > max_packsize\n-\t\t|| (pack_size + 60 + s.total_out) < pack_size) {\n+\tif ((pack_size + 60 + outbytes) > max_packsize\n+\t\t|| (pack_size + 60 + outbytes) < pack_size) {\n \n \t\t/* This new object needs to *not* have the current pack_id. */\n \t\te->pack_id = pack_id + 1;\n@@ -1141,24 +1151,27 @@ static int store_object(\n \t\tpack_size += sizeof(hdr) - pos;\n \t} else {\n \t\te->depth = 0;\n-\t\thdrlen = encode_header(type, dat->len, hdr);\n+\t\thdrlen = encode_header(type, orig_bytes ? orig_bytes\n+\t\t\t\t\t\t : dat->len, hdr);\n \t\twrite_or_die(pack_data->pack_fd, hdr, hdrlen);\n \t\tpack_size += hdrlen;\n \t}\n \n-\twrite_or_die(pack_data->pack_fd, out, s.total_out);\n-\tpack_size += s.total_out;\n+\twrite_or_die(pack_data->pack_fd, out, outbytes);\n+\tpack_size += outbytes;\n \n-\tfree(out);\n \tfree(delta);\n-\tif (last) {\n-\t\tif (last->no_swap) {\n-\t\t\tlast->data = *dat;\n-\t\t} else {\n-\t\t\tstrbuf_swap(&last->data, dat);\n+\tif (!orig_bytes) {\n+\t\tfree(out);\n+\t\tif (last) {\n+\t\t\tif (last->no_swap) {\n+\t\t\t\tlast->data = *dat;\n+\t\t\t} else {\n+\t\t\t\tstrbuf_swap(&last->data, dat);\n+\t\t\t}\n+\t\t\tlast->offset = e->offset;\n+\t\t\tlast->depth = e->depth;\n \t\t}\n-\t\tlast->offset = e->offset;\n-\t\tlast->depth = e->depth;\n \t}\n \treturn 0;\n }\n@@ -1343,7 +1356,7 @@ static void store_tree(struct tree_entry *root)\n \n \tmktree(t, 1, &new_tree);\n \tsha1_object(OBJ_TREE, &new_tree, root->versions[1].sha1);\n-\tstore_object(OBJ_TREE, &new_tree, &lo, root->versions[1].sha1, 0);\n+\tstore_object(OBJ_TREE, &new_tree, &lo, root->versions[1].sha1, 0, 0);\n \n \tt->delta_depth = lo.depth;\n \tfor (i = 0, j = 0, del = 0; i < t->entry_count; i++) {\n@@ -1711,11 +1724,15 @@ static void parse_mark(void)\n \n /* This actually parses a \"data\" command, with the addition that if sha1out\n  * is not NULL, it will also compute the sha1 on the fly. */\n-static void parse_object_data(\n+static int parse_object_data(\n \tenum object_type type,\n \tstruct strbuf *sb,\n-\tunsigned char *sha1out)\n+\tunsigned char *sha1out,\n+\tint candeflate)\n {\n+\tint orig_bytes = 0;\n+\tsize_t n = 0, length;\n+\n \tstrbuf_reset(sb);\n \n \tif (prefixcmp(command_buf.buf, \"data \"))\n@@ -1737,14 +1754,63 @@ static void parse_object_data(\n \t\t}\n \t\tfree(term);\n \n-\t\tif(sha1out)\n+\t\tif (sha1out)\n \t\t\tsha1_object(type, sb, sha1out);\n \t}\n-\telse {\n-\t\tsize_t n = 0, length;\n+\t/* TODO: make the hardcoded value a configuration option */\n+\telse if ((length = strtoul(command_buf.buf + 5, NULL, 10))\n+\t\t\t> 100 * 1024 * 1024\n+\t\t && candeflate) {\n+\t\t/* The incoming file is really big. As it is pretty unlikely\n+\t\t * it will give any interesting deltas, we immediately deflate\n+\t\t * it instead of storing the original data in memory. */\n+\t\tstatic struct strbuf tmp = STRBUF_INIT;\n+\t\tgit_SHA_CTX c;\n+\t\tz_stream zs;\n+\n+\t\tif (sha1out) {\n+\t\t\tunsigned char hdr[96];\n+\t\t\tunsigned long hdrlen;\n+\t\t\thdrlen = sprintf((char*)hdr,\"%s %lu\", typename(type),\n+\t\t\t\t(unsigned long)length) + 1;\n+\t\t\tgit_SHA1_Init(&c);\n+\t\t\tgit_SHA1_Update(&c, hdr, hdrlen);\n+\t\t}\n+\n+\t\tmemset(&zs, 0, sizeof(zs));\n+\t\tdeflateInit(&zs, pack_compression_level);\n+\t\t/* TODO: ideally, this should grow dynamically while we\n+\t\t * deflate the file. */\n+\t\tzs.avail_out = deflateBound(&zs, length);\n+\t\tstrbuf_grow(sb, zs.avail_out);\n+\t\tzs.next_out = (unsigned char *)sb->buf;\n \n-\t\tlength = strtoul(command_buf.buf + 5, NULL, 10);\n+\t\twhile (n < length) {\n+\t\t\tsize_t s = strbuf_fread(&tmp, length - n < 4096 ?\n+\t\t\t\t\t\tlength - n : 4096, stdin);\n+\t\t\tif (!s && feof(stdin))\n+\t\t\t\tdie(\"EOF in data (%lu bytes remaining)\",\n+\t\t\t\t\t(unsigned long)(length - n));\n+\t\t\tif (sha1out)\n+\t\t\t\tgit_SHA1_Update(&c, tmp.buf, s);\n+\t\t\tzs.next_in = (unsigned char *)tmp.buf;\n+\t\t\tzs.avail_in = s;\n+\t\t\twhile (deflate(&zs, Z_NO_FLUSH) == Z_OK)\n+\t\t\t\t/* nothing */;\n+\t\t\tstrbuf_reset(&tmp);\n \n+\t\t\tn += s;\n+\t\t}\n+\t\tdeflate(&zs, Z_FINISH);\n+\t\tdeflateEnd(&zs);\n+\t\tstrbuf_setlen(sb, zs.total_out);\n+\n+\t\tif (sha1out)\n+\t\t\tgit_SHA1_Final(sha1out, &c);\n+\n+\t\torig_bytes = length;\n+\t}\n+\telse {\n \t\twhile (n < length) {\n \t\t\tsize_t s = strbuf_fread(sb, length - n, stdin);\n \t\t\tif (!s && feof(stdin))\n@@ -1753,16 +1819,17 @@ static void parse_object_data(\n \t\t\tn += s;\n \t\t}\n \n-\t\tif(sha1out)\n+\t\tif (sha1out)\n \t\t\tsha1_object(type, sb, sha1out);\n \t}\n \n \tskip_optional_lf();\n+\treturn orig_bytes;\n }\n \n static void parse_data(struct strbuf *sb)\n {\n-\tparse_object_data(OBJ_NONE, sb, NULL);\n+\tparse_object_data(OBJ_NONE, sb, NULL, 0);\n }\n \n static int validate_raw_date(const char *src, char *result, int maxlen)\n@@ -1828,13 +1895,14 @@ static char *parse_ident(const char *buf)\n \n static void parse_new_blob(void)\n {\n-\tunsigned char sha1[20];\n \tstatic struct strbuf buf = STRBUF_INIT;\n+\tunsigned char sha1[20];\n+\tint orig_bytes;\n \n \tread_next_command();\n \tparse_mark();\n-\tparse_object_data(OBJ_BLOB, &buf, sha1);\n-\tstore_object(OBJ_BLOB, &buf, &last_blob, sha1, next_mark);\n+\torig_bytes = parse_object_data(OBJ_BLOB, &buf, sha1, 1);\n+\tstore_object(OBJ_BLOB, &buf, &last_blob, sha1, next_mark, orig_bytes);\n }\n \n static void unload_one_branch(void)\n@@ -1946,14 +2014,15 @@ static void file_change_m(struct branch *b)\n \t\t */\n \t} else if (inline_data) {\n \t\tstatic struct strbuf buf = STRBUF_INIT;\n+\t\tint orig_bytes;\n \n \t\tif (p != uq.buf) {\n \t\t\tstrbuf_addstr(&uq, p);\n \t\t\tp = uq.buf;\n \t\t}\n \t\tread_next_command();\n-\t\tparse_object_data(OBJ_BLOB, &buf, sha1);\n-\t\tstore_object(OBJ_BLOB, &buf, &last_blob, sha1, 0);\n+\t\torig_bytes = parse_object_data(OBJ_BLOB, &buf, sha1, 1);\n+\t\tstore_object(OBJ_BLOB, &buf, &last_blob, sha1, 0, orig_bytes);\n \t} else if (oe) {\n \t\tif (oe->type != OBJ_BLOB)\n \t\t\tdie(\"Not a blob (actually a %s): %s\",\n@@ -2236,7 +2305,7 @@ static void parse_new_commit(void)\n \tfree(committer);\n \n \tsha1_object(OBJ_COMMIT, &new_data, b->sha1);\n-\tif (!store_object(OBJ_COMMIT, &new_data, NULL, b->sha1, next_mark))\n+\tif (!store_object(OBJ_COMMIT, &new_data, NULL, b->sha1, next_mark, 0))\n \t\tb->pack_id = pack_id;\n \tb->last_commit = object_count_by_type[OBJ_COMMIT];\n }\n@@ -2317,7 +2386,7 @@ static void parse_new_tag(void)\n \tfree(tagger);\n \n \tsha1_object(OBJ_TAG, &new_data, t->sha1);\n-\tif (store_object(OBJ_TAG, &new_data, NULL, t->sha1, 0))\n+\tif (store_object(OBJ_TAG, &new_data, NULL, t->sha1, 0, 0))\n \t\tt->pack_id = MAX_PACK_ID;\n \telse\n \t\tt->pack_id = pack_id;\n-- \n1.6.2\n"},{"id":"107393","messageId":"20090308185749.GF12880@zoy.org","threadId":"18214","inReplyTo":"20090308184057.GA9606@zoy.org","subject":"Re: [PATCH 2/2] fast-import: treat large blobs (> 100 MiB) specially, by deflating them on-the-fly from stdin instead of keeping an entire copy in memory.","fromName":"Sam Hocevar","fromEmail":"sam@zoy.org","sentAt":"2009-03-08T18:57:49Z","receivedAt":"2009-03-08T18:57:49Z","isPatch":true,"sender":{"key":"sam@zoy.org","avatar":"https://gravatar.com/avatar/1fc1e5d8c3a8d737f14572135671adfbc0e61ffba5c3bc1d1b8a6f4aac764470?d=mp&s=160"},"body":"On Sun, Mar 08, 2009, Sam Hocevar wrote:\n> +\tint orig_bytes)\n\n   Self-comment: this variable should be size_t everywhere.\n\n-- \nSam.\n"}]}