{"thread":{"id":"3810","subject":"[PATCH] Thin pack generation: optimization.","startedAt":"2006-04-06T06:58:19Z","lastAt":"2006-04-06T06:58:19Z","messageCount":1,"participants":["Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"18418","messageId":"7vu097ur5g.fsf_-_@assigned-by-dhcp.cox.net","threadId":"3810","inReplyTo":"7vd5fzlnyt.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH] Thin pack generation: optimization.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-06T06:58:19Z","receivedAt":"2006-04-06T06:58:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jens Axboe noticed that recent \"git push\" has become very slow\nsince we made --thin transfer the default.\n\nThin pack generation to push a handful revisions that touch\nrelatively small number of paths out of huge tree was stupid; it\nregistered _everything_ from the excluded revisions.  As a\nresult, \"Counting objects\" phase was unnecessarily expensive.\n\nThis changes the logic to register the blobs and trees from\nexcluded revisions only for paths we are actually going to send\nto the other end.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n\n pack-objects.c |  119 +++++++++++++++++++++++++++++++++++++-------------------\n 1 files changed, 79 insertions(+), 40 deletions(-)\n\nb5026f319fc873d03a02f15992b7e431b4b5ad03\ndiff --git a/pack-objects.c b/pack-objects.c\nindex 9346392..f1bd8a6 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -505,24 +505,17 @@ static unsigned name_hash(struct name_pa\n \t * but close enough.\n \t */\n \thash = (name_hash<<DIRBITS) | (hash & ((1U<<DIRBITS )-1));\n-\n-\tif (0) { /* debug */\n-\t\tn = name + strlen(name);\n-\t\tif (n != name && n[-1] == '\\n')\n-\t\t\tn--;\n-\t\twhile (name <= --n)\n-\t\t\tfputc(*n, stderr);\n-\t\tfor (p = path; p; p = p->up) {\n-\t\t\tfputc('/', stderr);\n-\t\t\tn = p->elem + p->len;\n-\t\t\twhile (p->elem <= --n)\n-\t\t\t\tfputc(*n, stderr);\n-\t\t}\n-\t\tfprintf(stderr, \"\\t%08x\\n\", hash);\n-\t}\n \treturn hash;\n }\n+\n+static struct pbase_tree {\n+\tstruct pbase_tree *next;\n \n+\tunsigned char sha1[20];\n+\tvoid *tree_data;\n+\tunsigned long tree_size;\n+} *pbase_tree;\n+\n static int add_object_entry(const unsigned char *sha1, unsigned hash, int exclude)\n {\n \tunsigned int idx = nr_objects;\n@@ -585,58 +578,99 @@ static int add_object_entry(const unsign\n \t\t}\n \t}\n \treturn status;\n+}\n+\n+static int name_cmp_len(const char *name)\n+{\n+\tint i;\n+\tfor (i = 0; name[i] && name[i] != '\\n' && name[i] != '/'; i++)\n+\t\t;\n+\treturn i;\n }\n \n-static void add_pbase_tree(struct tree_desc *tree, struct name_path *up)\n+static void add_pbase_object(struct tree_desc *tree,\n+\t\t\t     struct name_path *up,\n+\t\t\t     const char *name,\n+\t\t\t     int cmplen)\n {\n \twhile (tree->size) {\n \t\tconst unsigned char *sha1;\n-\t\tconst char *name;\n-\t\tunsigned mode, hash;\n+\t\tconst char *entry_name;\n+\t\tint entry_len;\n+\t\tunsigned mode;\n \t\tunsigned long size;\n \t\tchar type[20];\n \n-\t\tsha1 = tree_entry_extract(tree, &name, &mode);\n+\t\tsha1 = tree_entry_extract(tree, &entry_name, &mode);\n \t\tupdate_tree_entry(tree);\n-\t\tif (!has_sha1_file(sha1))\n-\t\t\tcontinue;\n-\t\tif (sha1_object_info(sha1, type, &size))\n-\t\t\tcontinue;\n-\n-\t\thash = name_hash(up, name);\n-\t\tif (!add_object_entry(sha1, hash, 1))\n+\t\tentry_len = strlen(entry_name);\n+\t\tif (entry_len != cmplen ||\n+\t\t    memcmp(entry_name, name, cmplen) ||\n+\t\t    !has_sha1_file(sha1) ||\n+\t\t    sha1_object_info(sha1, type, &size))\n \t\t\tcontinue;\n-\n+\t\tif (name[cmplen] != '/') {\n+\t\t\tunsigned hash = name_hash(up, name);\n+\t\t\tadd_object_entry(sha1, hash, 1);\n+\t\t\treturn;\n+\t\t}\n \t\tif (!strcmp(type, tree_type)) {\n \t\t\tstruct tree_desc sub;\n \t\t\tvoid *elem;\n \t\t\tstruct name_path me;\n \n+\t\t\t/* We probably should cache these\n+\t\t\t * intermediate tree buffers...\n+\t\t\t */\n \t\t\telem = read_sha1_file(sha1, type, &sub.size);\n \t\t\tsub.buf = elem;\n \t\t\tif (sub.buf) {\n+\t\t\t\tconst char *down = name+cmplen+1;\n+\t\t\t\tint downlen = name_cmp_len(down);\n+\n \t\t\t\tme.up = up;\n-\t\t\t\tme.elem = name;\n-\t\t\t\tme.len = strlen(name);\n-\t\t\t\tadd_pbase_tree(&sub, &me);\n+\t\t\t\tme.elem = entry_name;\n+\t\t\t\tme.len = entry_len;\n+\t\t\t\tadd_pbase_object(&sub, &me, down, downlen);\n \t\t\t\tfree(elem);\n \t\t\t}\n \t\t}\n \t}\n }\n+\n+static void add_preferred_base_object(char *name)\n+{\n+\tstruct pbase_tree *it;\n+\tint cmplen = name_cmp_len(name);\n \n+\tfor (it = pbase_tree; it; it = it->next) {\n+\t\tif (cmplen == 0) {\n+\t\t\tunsigned hash = name_hash(NULL, \"\");\n+\t\t\tadd_object_entry(it->sha1, hash, 1);\n+\t\t}\n+\t\telse {\n+\t\t\tstruct tree_desc tree;\n+\t\t\ttree.buf = it->tree_data;\n+\t\t\ttree.size = it->tree_size;\n+\t\t\tadd_pbase_object(&tree, NULL, name, cmplen);\n+\t\t}\n+\t}\n+}\n+\n static void add_preferred_base(unsigned char *sha1)\n {\n-\tstruct tree_desc tree;\n-\tvoid *elem;\n+\tstruct pbase_tree *it;\n \n-\telem = read_object_with_reference(sha1, tree_type, &tree.size, NULL);\n-\ttree.buf = elem;\n-\tif (!tree.buf)\n+\tfor (it = pbase_tree; it && memcmp(it->sha1, sha1, 20); it = it->next)\n+\t\t;\n+\tif (it)\n \t\treturn;\n-\tif (add_object_entry(sha1, name_hash(NULL, \"\"), 1))\n-\t\tadd_pbase_tree(&tree, NULL);\n-\tfree(elem);\n+\tit = xcalloc(1, sizeof(*it));\n+\tit->next = pbase_tree;\n+\tpbase_tree = it;\n+\tmemcpy(it->sha1, sha1, 20);\n+\tit->tree_data = read_object_with_reference(sha1, tree_type,\n+\t\t\t\t\t\t   &it->tree_size, NULL);\n }\n \n static void check_object(struct object_entry *entry)\n@@ -1051,6 +1085,7 @@ int main(int argc, char **argv)\n \tchar line[PATH_MAX + 20];\n \tint window = 10, depth = 10, pack_to_stdout = 0;\n \tstruct object_entry **list;\n+\tint num_preferred_base = 0;\n \tint i;\n \n \tsetup_git_directory();\n@@ -1116,6 +1151,7 @@ int main(int argc, char **argv)\n \n \tfor (;;) {\n \t\tunsigned char sha1[20];\n+\t\tunsigned hash;\n \n \t\tif (!fgets(line, sizeof(line), stdin)) {\n \t\t\tif (feof(stdin))\n@@ -1132,12 +1168,15 @@ int main(int argc, char **argv)\n \t\t\tif (get_sha1_hex(line+1, sha1))\n \t\t\t\tdie(\"expected edge sha1, got garbage:\\n %s\",\n \t\t\t\t    line+1);\n-\t\t\tadd_preferred_base(sha1);\n+\t\t\tif (num_preferred_base++ < window)\n+\t\t\t\tadd_preferred_base(sha1);\n \t\t\tcontinue;\n \t\t}\n \t\tif (get_sha1_hex(line, sha1))\n \t\t\tdie(\"expected sha1, got garbage:\\n %s\", line);\n-\t\tadd_object_entry(sha1, name_hash(NULL, line+41), 0);\n+\t\tadd_preferred_base_object(line+41);\n+\t\thash = name_hash(NULL, line+41);\n+\t\tadd_object_entry(sha1, hash, 0);\n \t}\n \tif (progress)\n \t\tfprintf(stderr, \"Done counting %d objects.\\n\", nr_objects);\n-- \n1.3.0.rc2.g9cda\n"}]}