{"thread":{"id":"21357","subject":"[PATCH v2 0/2] Speedup fetch with large numbers of refs","startedAt":"2009-10-25T21:28:10Z","lastAt":"2009-10-26T23:12:14Z","messageCount":4,"participants":["Julian Phillips"],"isPatch":true,"patchVersion":2,"patchTotal":2},"messages":[{"id":"125916","messageId":"20091025212449.48498.23208.julian@quantumfyre.co.uk","threadId":"21357","inReplyTo":null,"subject":"[PATCH v2 0/2] Speedup fetch with large numbers of refs","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2009-10-25T21:28:10Z","receivedAt":"2009-10-25T21:28:10Z","isPatch":true,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"This is the same as v1, except that this time the tests pass on Linux\nas well as on MacOS.\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        |   42 +++++++++++++++++++++++-------------------\n 2 files changed, 37 insertions(+), 22 deletions(-)\n"},{"id":"125917","messageId":"20091025212813.48498.51868.julian@quantumfyre.co.uk","threadId":"21357","inReplyTo":"20091025212449.48498.23208.julian@quantumfyre.co.uk","subject":"[PATCH v2 1/2] remote: Make ref_remove_duplicates faster for large numbers of refs","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2009-10-25T21:28:11Z","receivedAt":"2009-10-25T21:28:11Z","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 |   42 +++++++++++++++++++++++-------------------\n 1 files changed, 23 insertions(+), 19 deletions(-)\n\ndiff --git a/remote.c b/remote.c\nindex 73d33f2..1380b20 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,32 @@ 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-\tfor (; ref_map; ref_map = ref_map->next) {\n+\tstruct string_list refs = { NULL, 0, 0, 0 };\n+\tstruct string_list_item *item = NULL;\n+\tstruct ref *prev = NULL, *next = NULL;\n+\tfor (; ref_map; ref_map = next) {\n+\t\tnext = 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":"125918","messageId":"20091025212813.48498.87676.julian@quantumfyre.co.uk","threadId":"21357","inReplyTo":"20091025212449.48498.23208.julian@quantumfyre.co.uk","subject":"[PATCH v2 2/2] fetch: Speed up fetch of large numbers of refs","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2009-10-25T21:28:12Z","receivedAt":"2009-10-25T21:28:12Z","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":"125962","messageId":"20091026231215.91316.47162.julian@quantumfyre.co.uk","threadId":"21357","inReplyTo":"20091025212813.48498.51868.julian@quantumfyre.co.uk","subject":"[PATCH v2 3/2] remote: fix poential ref_map list corruption in ref_remove_duplicates","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2009-10-26T23:12:14Z","receivedAt":"2009-10-26T23:12:14Z","isPatch":true,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"The prev pointer was not being updated when the peer_ref member\npointer was NULL, which means that that any items in the list with a\nNULL peer_ref immediately preceeding a duplicate would be dropped\nwithout being freed.\n\nSigned-off-by: Julian Phillips <julian@quantumfyre.co.uk>\n---\n\nHaving fixed the access after free bug, I realised that there was\nstill a problem.  This one didn't show up in the tests - due to the\nrather specific circumstances required, but may occur in real use.\n\n remote.c |    3 +--\n 1 files changed, 1 insertions(+), 2 deletions(-)\n\ndiff --git a/remote.c b/remote.c\nindex 1380b20..4f9f0cc 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -738,7 +738,7 @@ void ref_remove_duplicates(struct ref *ref_map)\n \tstruct string_list refs = { NULL, 0, 0, 0 };\n \tstruct string_list_item *item = NULL;\n \tstruct ref *prev = NULL, *next = NULL;\n-\tfor (; ref_map; ref_map = next) {\n+\tfor (; ref_map; prev = ref_map, ref_map = next) {\n \t\tnext = ref_map->next;\n \t\tif (!ref_map->peer_ref)\n \t\t\tcontinue;\n@@ -758,7 +758,6 @@ void ref_remove_duplicates(struct ref *ref_map)\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-- \n1.6.5.rc2\n"}]}