{"thread":{"id":"21332","subject":"[PATCH 1/2] remote: Make ref_remove_duplicates faster for large numbers of refs","startedAt":"2009-10-22T21:06:12Z","lastAt":"2009-10-25T20:48:45Z","messageCount":5,"participants":["Julian Phillips","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"125744","messageId":"20091022210444.18084.61685.julian@quantumfyre.co.uk","threadId":"21332","inReplyTo":null,"subject":"[PATCH 0/2] Speedup fetch with large numbers of refs","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2009-10-22T21:06:12Z","receivedAt":"2009-10-22T21:06:12Z","isPatch":true,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"These two commits make fetch quite a bit faster when dealing with\nlarge numbers of refs.  Unfortunately I've lost the exact figures, but\nmy silly test respository (50000 tags, 1 branch) went from something\nlike 30s for a \"fetch --tags\" that did nothing, to about 5.\n\nJulian Phillips (2):\n  remote: Make ref_remove_duplicates faster for large numbers of refs\n  fetch: Speed up fetch of large numbers of refs\n\n builtin-fetch.c |   17 ++++++++++++++---\n remote.c        |   39 +++++++++++++++++++++------------------\n 2 files changed, 35 insertions(+), 21 deletions(-)\n"},{"id":"125743","messageId":"20091022210615.18084.85466.julian@quantumfyre.co.uk","threadId":"21332","inReplyTo":"20091022210444.18084.61685.julian@quantumfyre.co.uk","subject":"[PATCH 1/2] remote: Make ref_remove_duplicates faster for large numbers of refs","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2009-10-22T21:06:13Z","receivedAt":"2009-10-22T21:06:13Z","isPatch":true,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"The ref_remove_duplicates function was very slow at dealing with very\nlarge numbers of refs.  This is because it was using a linear search\nthrough all remaining refs to find any duplicates of the current ref.\n\nRewriting it to use a string list to keep track of which refs have\nalready been seen and removing duplicates when they are found is much\nmore efficient.\n\nSigned-off-by: Julian Phillips <julian@quantumfyre.co.uk>\n---\n remote.c |   39 +++++++++++++++++++++------------------\n 1 files changed, 21 insertions(+), 18 deletions(-)\n\ndiff --git a/remote.c b/remote.c\nindex 73d33f2..a97c2c3 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -6,6 +6,7 @@\n #include \"revision.h\"\n #include \"dir.h\"\n #include \"tag.h\"\n+#include \"string-list.h\"\n \n static struct refspec s_tag_refspec = {\n \t0,\n@@ -734,29 +735,31 @@ int for_each_remote(each_remote_fn fn, void *priv)\n \n void ref_remove_duplicates(struct ref *ref_map)\n {\n-\tstruct ref **posn;\n-\tstruct ref *next;\n+\tstruct string_list refs = { NULL, 0, 0, 0 };\n+\tstruct string_list_item *item = NULL;\n+\tstruct ref *prev = NULL;\n \tfor (; ref_map; ref_map = ref_map->next) {\n \t\tif (!ref_map->peer_ref)\n \t\t\tcontinue;\n-\t\tposn = &ref_map->next;\n-\t\twhile (*posn) {\n-\t\t\tif ((*posn)->peer_ref &&\n-\t\t\t    !strcmp((*posn)->peer_ref->name,\n-\t\t\t\t    ref_map->peer_ref->name)) {\n-\t\t\t\tif (strcmp((*posn)->name, ref_map->name))\n-\t\t\t\t\tdie(\"%s tracks both %s and %s\",\n-\t\t\t\t\t    ref_map->peer_ref->name,\n-\t\t\t\t\t    (*posn)->name, ref_map->name);\n-\t\t\t\tnext = (*posn)->next;\n-\t\t\t\tfree((*posn)->peer_ref);\n-\t\t\t\tfree(*posn);\n-\t\t\t\t*posn = next;\n-\t\t\t} else {\n-\t\t\t\tposn = &(*posn)->next;\n-\t\t\t}\n+\n+\t\titem = string_list_lookup(ref_map->peer_ref->name, &refs);\n+\t\tif (item) {\n+\t\t\tif (strcmp(((struct ref *)item->util)->name,\n+\t\t\t\t   ref_map->name))\n+\t\t\t\tdie(\"%s tracks both %s and %s\",\n+\t\t\t\t    ref_map->peer_ref->name,\n+\t\t\t\t    ((struct ref *)item->util)->name,\n+\t\t\t\t    ref_map->name);\n+\t\t\tprev->next = ref_map->next;\n+\t\t\tfree(ref_map->peer_ref);\n+\t\t\tfree(ref_map);\n \t\t}\n+\n+\t\titem = string_list_insert(ref_map->peer_ref->name, &refs);\n+\t\titem->util = ref_map;\n+\t\tprev = ref_map;\n \t}\n+\tstring_list_clear(&refs, 0);\n }\n \n int remote_has_url(struct remote *remote, const char *url)\n-- \n1.6.5.rc2\n"},{"id":"125745","messageId":"20091022210615.18084.85572.julian@quantumfyre.co.uk","threadId":"21332","inReplyTo":"20091022210444.18084.61685.julian@quantumfyre.co.uk","subject":"[PATCH 2/2] fetch: Speed up fetch of large numbers of refs","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2009-10-22T21:06:14Z","receivedAt":"2009-10-22T21:06:14Z","isPatch":true,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"When there are large numbers of refs, calling read_ref for each ref is\ninefficent (and infact downright slow) - so instead use for_each_ref\nto build up a string list of all the refs that we currently have,\nwhich significantly improves the volume.\n\nSigned-off-by: Julian Phillips <julian@quantumfyre.co.uk>\n---\n builtin-fetch.c |   17 ++++++++++++++---\n 1 files changed, 14 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin-fetch.c b/builtin-fetch.c\nindex acb08e4..0f53cbd 100644\n--- a/builtin-fetch.c\n+++ b/builtin-fetch.c\n@@ -489,7 +489,8 @@ static int add_existing(const char *refname, const unsigned char *sha1,\n \t\t\tint flag, void *cbdata)\n {\n \tstruct string_list *list = (struct string_list *)cbdata;\n-\tstring_list_insert(refname, list);\n+\tstruct string_list_item *item = string_list_insert(refname, list);\n+\titem->util = (void *)sha1;\n \treturn 0;\n }\n \n@@ -606,9 +607,14 @@ static void check_not_current_branch(struct ref *ref_map)\n static int do_fetch(struct transport *transport,\n \t\t    struct refspec *refs, int ref_count)\n {\n+\tstruct string_list existing_refs = { NULL, 0, 0, 0 };\n+\tstruct string_list_item *peer_item = NULL;\n \tstruct ref *ref_map;\n \tstruct ref *rm;\n \tint autotags = (transport->remote->fetch_tags == 1);\n+\n+\tfor_each_ref(add_existing, &existing_refs);\n+\n \tif (transport->remote->fetch_tags == 2 && tags != TAGS_UNSET)\n \t\ttags = TAGS_SET;\n \tif (transport->remote->fetch_tags == -1)\n@@ -631,8 +637,13 @@ static int do_fetch(struct transport *transport,\n \t\tcheck_not_current_branch(ref_map);\n \n \tfor (rm = ref_map; rm; rm = rm->next) {\n-\t\tif (rm->peer_ref)\n-\t\t\tread_ref(rm->peer_ref->name, rm->peer_ref->old_sha1);\n+\t\tif (rm->peer_ref) {\n+\t\t\tpeer_item = string_list_lookup(rm->peer_ref->name,\n+\t\t\t\t\t\t       &existing_refs);\n+\t\t\tif (peer_item)\n+\t\t\t\thashcpy(rm->peer_ref->old_sha1,\n+\t\t\t\t\tpeer_item->util);\n+\t\t}\n \t}\n \n \tif (tags == TAGS_DEFAULT && autotags)\n-- \n1.6.5.rc2\n"},{"id":"125870","messageId":"7vd44cymcv.fsf@alter.siamese.dyndns.org","threadId":"21332","inReplyTo":"20091022210444.18084.61685.julian@quantumfyre.co.uk","subject":"Re: [PATCH 0/2] Speedup fetch with large numbers of refs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-10-25T07:16:32Z","receivedAt":"2009-10-25T07:16:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Hmm, t5515 does not seem to pass with this series for me.\n"},{"id":"125915","messageId":"alpine.LNX.2.00.0910252047340.11963@reaper.quantumfyre.co.uk","threadId":"21332","inReplyTo":"7vd44cymcv.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 0/2] Speedup fetch with large numbers of refs","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2009-10-25T20:48:45Z","receivedAt":"2009-10-25T20:48:45Z","isPatch":true,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"On Sun, 25 Oct 2009, Junio C Hamano wrote:\n\n> Hmm, t5515 does not seem to pass with this series for me.\n\nAh, sorry.  All the tests did (and still do) pass on my mac ...\nI'll send an updated version once I get them to pass on Linux too.\n\n-- \nJulian\n\n  ---\nGeorge Orwell was an optimist.\n"}]}