{"thread":{"id":"30591","subject":"[PATCH] find_containing_dir(): allocate strbuf less extravagantly","startedAt":"2012-05-22T13:16:06Z","lastAt":"2012-05-24T04:34:01Z","messageCount":12,"participants":["mhagger@alum.mit.edu","Jeff King","René Scharfe","Junio C Hamano","Michael Haggerty"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"191894","messageId":"1337692566-3718-1-git-send-email-mhagger@alum.mit.edu","threadId":"30591","inReplyTo":null,"subject":"[PATCH] find_containing_dir(): allocate strbuf less extravagantly","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-22T13:16:06Z","receivedAt":"2012-05-22T13:16:06Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nIt might seem like allocating a fixed-length buffer of uninitialized\nmemory should be pretty cheap even if the buffer is of size PATH_MAX.\nBut empirically, it is measurably faster to allocated only the strlen\nof the input string.\n\nThanks to Peff for pointing out a performance regression in this area\nthat might be fixed by this patch.\n\nSigned-off-by: Michael Haggerty \n---\nI am not able to reproduce performance regressions as bad as those\nobserved by Peff. It seems to depend on the amount of memory\npressure. The smaller regression that I *did* see is fixed by this\npatch, reducing the time for \"git fetch . refs/*:refs/*\" from 10.1 s\nto 9.3 s. The change is sensible in any case, but we will have to\nwait for Peff's verdict about whether it fixes the whole problem for\nhim, too.\n\n refs.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/refs.c b/refs.c\nindex d6bdb47..fffbb17 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -383,7 +383,7 @@ static struct ref_dir *find_containing_dir(struct ref_dir *dir,\n {\n \tstruct strbuf dirname;\n \tconst char *slash;\n-\tstrbuf_init(&dirname, PATH_MAX);\n+\tstrbuf_init(&dirname, strlen(refname));\n \tfor (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) {\n \t\tstruct ref_dir *subdir;\n \t\tstrbuf_add(&dirname,\n-- \n1.7.10\n"},{"id":"191908","messageId":"20120522173448.GD11600@sigill.intra.peff.net","threadId":"30591","inReplyTo":"1337692566-3718-1-git-send-email-mhagger@alum.mit.edu","subject":"Re: [PATCH] find_containing_dir(): allocate strbuf less extravagantly","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-22T17:34:48Z","receivedAt":"2012-05-22T17:34:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 22, 2012 at 03:16:06PM +0200, mhagger@alum.mit.edu wrote:\n\n> From: Michael Haggerty \n> \n> It might seem like allocating a fixed-length buffer of uninitialized\n> memory should be pretty cheap even if the buffer is of size PATH_MAX.\n> But empirically, it is measurably faster to allocated only the strlen\n> of the input string.\n> \n> Thanks to Peff for pointing out a performance regression in this area\n> that might be fixed by this patch.\n> \n> Signed-off-by: Michael Haggerty \n> ---\n> I am not able to reproduce performance regressions as bad as those\n> observed by Peff. It seems to depend on the amount of memory\n> pressure. The smaller regression that I *did* see is fixed by this\n> patch, reducing the time for \"git fetch . refs/*:refs/*\" from 10.1 s\n> to 9.3 s. The change is sensible in any case, but we will have to\n> wait for Peff's verdict about whether it fixes the whole problem for\n> him, too.\n\nI see a similar small improvement. So I think it is worth doing, but it\ndoes not fix the main regression I found.\n\n-Peff\n"},{"id":"191923","messageId":"4FBBDFFF.8050207@lsrfire.ath.cx","threadId":"30591","inReplyTo":"1337692566-3718-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 1/3] refs: convert parameter of search_ref_dir() to length-limited string","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2012-05-22T18:50:39Z","receivedAt":"2012-05-22T18:50:39Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Signed-off-by: Rene Scharfe \n---\n refs.c | 13 +++++++------\n 1 file changed, 7 insertions(+), 6 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex d6bdb47..c028333 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -319,19 +319,19 @@ static void sort_ref_dir(struct ref_dir *dir);\n * (non-recursively), sorting dir if necessary. Return NULL if no\n * such entry is found. dir must already be complete.\n */\n-static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname)\n+static struct ref_entry *search_ref_dir(struct ref_dir *dir,\n+\t\t\t\t\tconst char *refname, size_t len)\n {\n \tstruct ref_entry *e, **r;\n-\tint len;\n \n \tif (refname == NULL || !dir->nr)\n \t\treturn NULL;\n \n \tsort_ref_dir(dir);\n \n-\tlen = strlen(refname) + 1;\n-\te = xmalloc(sizeof(struct ref_entry) + len);\n+\te = xmalloc(sizeof(struct ref_entry) + len + 1);\n \tmemcpy(e->name, refname, len);\n+\te->name[len] = '\\0';\n \n \tr = bsearch(&e, dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);\n \n@@ -353,7 +353,8 @@ static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname\n static struct ref_dir *search_for_subdir(struct ref_dir *dir,\n \t\t\t\t\t const char *subdirname, int mkdir)\n {\n-\tstruct ref_entry *entry = search_ref_dir(dir, subdirname);\n+\tsize_t len = strlen(subdirname);\n+\tstruct ref_entry *entry = search_ref_dir(dir, subdirname, len);\n \tif (!entry) {\n \t\tif (!mkdir)\n \t\t\treturn NULL;\n@@ -412,7 +413,7 @@ static struct ref_entry *find_ref(struct ref_dir *dir, const char *refname)\n \tdir = find_containing_dir(dir, refname, 0);\n \tif (!dir)\n \t\treturn NULL;\n-\tentry = search_ref_dir(dir, refname);\n+\tentry = search_ref_dir(dir, refname, strlen(refname));\n \treturn (entry && !(entry->flag & REF_DIR)) ? entry : NULL;\n }\n \n-- \n1.7.10.2\n"},{"id":"191921","messageId":"4FBBE00C.9020104@lsrfire.ath.cx","threadId":"30591","inReplyTo":"1337692566-3718-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 2/3] refs: convert parameter of create_dir_entry() to length-limited string","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2012-05-22T18:50:52Z","receivedAt":"2012-05-22T18:50:52Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Signed-off-by: Rene Scharfe \n---\n refs.c | 18 ++++++++++--------\n 1 file changed, 10 insertions(+), 8 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex c028333..c5e167b 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -294,12 +294,13 @@ static void clear_ref_dir(struct ref_dir *dir)\n * \"refs/heads/\") or \"\" for the top-level directory.\n */\n static struct ref_entry *create_dir_entry(struct ref_cache *ref_cache,\n-\t\t\t\t\t const char *dirname, int incomplete)\n+\t\t\t\t\t const char *dirname, size_t len,\n+\t\t\t\t\t int incomplete)\n {\n \tstruct ref_entry *direntry;\n-\tint len = strlen(dirname);\n \tdirentry = xcalloc(1, sizeof(struct ref_entry) + len + 1);\n-\tmemcpy(direntry->name, dirname, len + 1);\n+\tmemcpy(direntry->name, dirname, len);\n+\tdirentry->name[len] = '\\0';\n \tdirentry->u.subdir.ref_cache = ref_cache;\n \tdirentry->flag = REF_DIR | (incomplete ? REF_INCOMPLETE : 0);\n \treturn direntry;\n@@ -364,7 +365,7 @@ static struct ref_dir *search_for_subdir(struct ref_dir *dir,\n \t\t * therefore, create an empty record for it but mark\n \t\t * the record complete.\n \t\t */\n-\t\tentry = create_dir_entry(dir->ref_cache, subdirname, 0);\n+\t\tentry = create_dir_entry(dir->ref_cache, subdirname, len, 0);\n \t\tadd_entry_to_dir(dir, entry);\n \t}\n \treturn get_ref_dir(entry);\n@@ -823,7 +824,7 @@ static struct ref_dir *get_packed_refs(struct ref_cache *refs)\n \t\tconst char *packed_refs_file;\n \t\tFILE *f;\n \n-\t\trefs->packed = create_dir_entry(refs, \"\", 0);\n+\t\trefs->packed = create_dir_entry(refs, \"\", 0, 0);\n \t\tif (*refs->name)\n \t\t\tpacked_refs_file = git_path_submodule(refs->name, \"packed-refs\");\n \t\telse\n@@ -888,7 +889,8 @@ static void read_loose_refs(const char *dirname, struct ref_dir *dir)\n \t\t} else if (S_ISDIR(st.st_mode)) {\n \t\t\tstrbuf_addch(&refname, '/');\n \t\t\tadd_entry_to_dir(dir,\n-\t\t\t\t\t create_dir_entry(refs, refname.buf, 1));\n+\t\t\t\t\t create_dir_entry(refs, refname.buf,\n+\t\t\t\t\t\t\t refname.len, 1));\n \t\t} else {\n \t\t\tif (*refs->name) {\n \t\t\t\thashclr(sha1);\n@@ -918,12 +920,12 @@ static struct ref_dir *get_loose_refs(struct ref_cache *refs)\n \t\t * are about to read the only subdirectory that can\n \t\t * hold references:\n \t\t */\n-\t\trefs->loose = create_dir_entry(refs, \"\", 0);\n+\t\trefs->loose = create_dir_entry(refs, \"\", 0, 0);\n \t\t/*\n \t\t * Create an incomplete entry for \"refs/\":\n \t\t */\n \t\tadd_entry_to_dir(get_ref_dir(refs->loose),\n-\t\t\t\t create_dir_entry(refs, \"refs/\", 1));\n+\t\t\t\t create_dir_entry(refs, \"refs/\", 5, 1));\n \t}\n \treturn get_ref_dir(refs->loose);\n }\n-- \n1.7.10.2\n"},{"id":"191922","messageId":"4FBBE012.6090702@lsrfire.ath.cx","threadId":"30591","inReplyTo":"1337692566-3718-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 3/3] refs: use strings directly in find_containing_dir()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2012-05-22T18:50:58Z","receivedAt":"2012-05-22T18:50:58Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Convert the parameter subdirname of search_for_subdir() to a\nlength-limted string and then simply pass the interesting slice of the\nrefname from find_containing_dir(), thereby avoiding to duplicate the\nstring.\n\nSigned-off-by: Rene Scharfe \n---\nWhy allocate a NUL-terminated copy at all when we can teach the code to\nstop after a given number of characters just as easily? Alas, this\nwill still trigger an allocation in search_ref_dir() (see first patch).\n\n refs.c | 13 ++++---------\n 1 file changed, 4 insertions(+), 9 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex c5e167b..96e943c 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -352,9 +352,9 @@ static struct ref_entry *search_ref_dir(struct ref_dir *dir,\n * directory cannot be found. dir must already be complete.\n */\n static struct ref_dir *search_for_subdir(struct ref_dir *dir,\n-\t\t\t\t\t const char *subdirname, int mkdir)\n+\t\t\t\t\t const char *subdirname, size_t len,\n+\t\t\t\t\t int mkdir)\n {\n-\tsize_t len = strlen(subdirname);\n \tstruct ref_entry *entry = search_ref_dir(dir, subdirname, len);\n \tif (!entry) {\n \t\tif (!mkdir)\n@@ -383,15 +383,11 @@ static struct ref_dir *search_for_subdir(struct ref_dir *dir,\n static struct ref_dir *find_containing_dir(struct ref_dir *dir,\n \t\t\t\t\t const char *refname, int mkdir)\n {\n-\tstruct strbuf dirname;\n \tconst char *slash;\n-\tstrbuf_init(&dirname, PATH_MAX);\n \tfor (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) {\n+\t\tsize_t dirnamelen = slash - refname + 1;\n \t\tstruct ref_dir *subdir;\n-\t\tstrbuf_add(&dirname,\n-\t\t\t refname + dirname.len,\n-\t\t\t (slash + 1) - (refname + dirname.len));\n-\t\tsubdir = search_for_subdir(dir, dirname.buf, mkdir);\n+\t\tsubdir = search_for_subdir(dir, refname, dirnamelen, mkdir);\n \t\tif (!subdir) {\n \t\t\tdir = NULL;\n \t\t\tbreak;\n@@ -399,7 +395,6 @@ static struct ref_dir *find_containing_dir(struct ref_dir *dir,\n \t\tdir = subdir;\n \t}\n \n-\tstrbuf_release(&dirname);\n \treturn dir;\n }\n \n-- \n1.7.10.2\n"},{"id":"191953","messageId":"7vlikj3nzc.fsf@alter.siamese.dyndns.org","threadId":"30591","inReplyTo":"4FBBE012.6090702@lsrfire.ath.cx","subject":"Re: [PATCH 3/3] refs: use strings directly in find_containing_dir()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-22T21:27:51Z","receivedAt":"2012-05-22T21:27:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Why allocate a NUL-terminated copy at all when we can teach the code to\n> stop after a given number of characters just as easily? Alas, this\n> will still trigger an allocation in search_ref_dir() (see first patch).\n\nYeah, but it is only because search_ref_dir() tries to use ref_entry_cmp(),\nwhose signature is geared more towards being used as a qsort(3) callback,\nas the comparison function for bsearch(3).\n\nA bsearch() callback takes two pointers, one is for the key and the other\nfor an array element, and there is no reason to require the two types be\nthe same.\n\nIn other words, something like this patch and we won't need an allocation\nof the ref_entry that did not have to be a full ref_entry in the first\nplace (it only had to be something that supplies the \"key\" into a sorted\narray).\n\n refs.c | 32 +++++++++++++++++++++++---------\n 1 file changed, 23 insertions(+), 9 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 96e943c..52709ab 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -315,6 +315,23 @@ static int ref_entry_cmp(const void *a, const void *b)\n \n static void sort_ref_dir(struct ref_dir *dir);\n \n+struct string_slice {\n+\tsize_t len;\n+\tconst char *str;\n+};\n+\n+static int ref_entry_cmp_sslice(const void *key_, const void *ent_)\n+{\n+\tstruct string_slice *key = (struct string_slice *)key_;\n+\tstruct ref_entry *ent = *(struct ref_entry **)ent_;\n+\tint entlen = strlen(ent->name);\n+\tint cmplen = key->len < entlen ? key->len : entlen;\n+\tint cmp = memcmp(key->str, ent->name, cmplen);\n+\tif (cmp)\n+\t\treturn cmp;\n+\treturn key->len - entlen;\n+}\n+\n /*\n * Return the entry with the given refname from the ref_dir\n * (non-recursively), sorting dir if necessary. Return NULL if no\n@@ -323,20 +340,17 @@ static void sort_ref_dir(struct ref_dir *dir);\n static struct ref_entry *search_ref_dir(struct ref_dir *dir,\n \t\t\t\t\tconst char *refname, size_t len)\n {\n-\tstruct ref_entry *e, **r;\n+\tstruct ref_entry **r;\n+\tstruct string_slice key;\n \n \tif (refname == NULL || !dir->nr)\n \t\treturn NULL;\n \n \tsort_ref_dir(dir);\n-\n-\te = xmalloc(sizeof(struct ref_entry) + len + 1);\n-\tmemcpy(e->name, refname, len);\n-\te->name[len] = '\\0';\n-\n-\tr = bsearch(&e, dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);\n-\n-\tfree(e);\n+\tkey.len = len;\n+\tkey.str = refname;\n+\tr = bsearch(&key, dir->entries, dir->nr, sizeof(*dir->entries),\n+\t\t ref_entry_cmp_sslice);\n \n \tif (r == NULL)\n \t\treturn NULL;\n"},{"id":"191955","messageId":"4FBC0F12.2000001@lsrfire.ath.cx","threadId":"30591","inReplyTo":"7vlikj3nzc.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/3] refs: use strings directly in find_containing_dir()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2012-05-22T22:11:30Z","receivedAt":"2012-05-22T22:11:30Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 22.05.2012 23:27, schrieb Junio C Hamano:\n> René Scharfe writes:\n>\n>> Why allocate a NUL-terminated copy at all when we can teach the code to\n>> stop after a given number of characters just as easily? Alas, this\n>> will still trigger an allocation in search_ref_dir() (see first patch).\n>\n> Yeah, but it is only because search_ref_dir() tries to use ref_entry_cmp(),\n> whose signature is geared more towards being used as a qsort(3) callback,\n> as the comparison function for bsearch(3).\n>\n> A bsearch() callback takes two pointers, one is for the key and the other\n> for an array element, and there is no reason to require the two types be\n> the same.\n>\n> In other words, something like this patch and we won't need an allocation\n> of the ref_entry that did not have to be a full ref_entry in the first\n> place (it only had to be something that supplies the \"key\" into a sorted\n> array).\n\nRight, and this order (key-first) is documented for Linux, *BSD and by \nMicrosoft, so we can probably rely on it. The proposed asymmetry \nbetween sorting and lookup is a bit ... untidy, nevertheless. But it's \ncertainly worth it to avoid that ugly allocation.\n\nHere's a random observation that led me to write the three patches: When \nrunning the following command under valgrind, it reports a few \ninteresting numbers for total heap usage:\n\n\t$ git grep guess xdiff/xutils.c\n\n v1.7.8 591 allocs, 96 frees, 383,565 bytes allocated\n v1.7.9 2,940 allocs, 121 frees, 361,001 bytes allocated\n v1.7.10 3,002 allocs, 129 frees, 366,487 bytes allocated\n master 4,555 allocs, 1,586 frees, 2,380,265 bytes allocated\n 3 patches 4,079 allocs, 1,110 frees, 430,093 bytes allocated\n 4 patches 3,093 allocs, 124 frees, 377,749 bytes allocated\n\nWith your last patch, I think we're doing fine again, as the total\nallocated size is within a few KB of the smallest one in this\narbitrary list of versions.\n\nWhat has git grep to do with refs? It checks if the path in the command\nabove is a ref, which makes it iterate over all of them..\n\nRené\n"},{"id":"191956","messageId":"7vhav73lnl.fsf@alter.siamese.dyndns.org","threadId":"30591","inReplyTo":"4FBC0F12.2000001@lsrfire.ath.cx","subject":"Re: [PATCH 3/3] refs: use strings directly in find_containing_dir()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-22T22:18:06Z","receivedAt":"2012-05-22T22:18:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> What has git grep to do with refs? It checks if the path in the command\n> above is a ref, which makes it iterate over all of them..\n\nDo you mean:\n\n\t/* Is it a rev? */\n get_sha1()\n -> ...\n -> get_sha1_basic()\n -> dwim_ref()\n\ncallpath?\n"},{"id":"191999","messageId":"4FBD0E33.4060309@lsrfire.ath.cx","threadId":"30591","inReplyTo":"7vhav73lnl.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/3] refs: use strings directly in find_containing_dir()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2012-05-23T16:20:03Z","receivedAt":"2012-05-23T16:20:03Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 23.05.2012 00:18, schrieb Junio C Hamano:\n> René Scharfe writes:\n>\n>> What has git grep to do with refs? It checks if the path in the command\n>> above is a ref, which makes it iterate over all of them..\n>\n> Do you mean:\n>\n> \t/* Is it a rev? */\n> get_sha1()\n> -> ...\n> -> get_sha1_basic()\n> -> dwim_ref()\n>\n> callpath?\n\nYes, indeed. Hmm, this is done even if the paths come after a \ndouble-dash. Anyway, I don't consider the check to be a performance \nissue, just a quick way to test the allocation count that i stumbled \nupon while working on the recent grep patches.\n\nRené\n"},{"id":"192006","messageId":"7v4nr625vf.fsf@alter.siamese.dyndns.org","threadId":"30591","inReplyTo":"4FBD0E33.4060309@lsrfire.ath.cx","subject":"Re: [PATCH 3/3] refs: use strings directly in find_containing_dir()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-23T16:56:36Z","receivedAt":"2012-05-23T16:56:36Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Am 23.05.2012 00:18, schrieb Junio C Hamano:\n>> René Scharfe writes:\n>>\n>>> What has git grep to do with refs? It checks if the path in the command\n>>> above is a ref, which makes it iterate over all of them..\n>>\n>> Do you mean:\n>>\n>> \t/* Is it a rev? */\n>> get_sha1()\n>> -> ...\n>> -> get_sha1_basic()\n>> -> dwim_ref()\n>>\n>> callpath?\n>\n> Yes, indeed. Hmm, this is done even if the paths come after a\n> double-dash. Anyway, I don't consider the check to be a performance\n> issue, just a quick way to test the allocation count that i stumbled\n> upon while working on the recent grep patches.\n\nI was merely reacting \"iterate over all of them\"; dwim_ref() only checks\nif .git/blah, .git/refs/heads/blah, .git/refs/tags/blah, etc. exists and\nthe number of checks do not depend on the number of refs you have, so I\nwas wondering if I overlooked something that does for_each_ref() of\neverything.\n"},{"id":"192009","messageId":"4FBD1B36.5060404@lsrfire.ath.cx","threadId":"30591","inReplyTo":"7v4nr625vf.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/3] refs: use strings directly in find_containing_dir()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2012-05-23T17:15:34Z","receivedAt":"2012-05-23T17:15:34Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 23.05.2012 18:56, schrieb Junio C Hamano:\n> René Scharfe writes:\n> \n>> Am 23.05.2012 00:18, schrieb Junio C Hamano:\n>>> René Scharfe writes:\n>>>\n>>>> What has git grep to do with refs? It checks if the path in the command\n>>>> above is a ref, which makes it iterate over all of them..\n>>>\n>>> Do you mean:\n>>>\n>>> \t/* Is it a rev? */\n>>> get_sha1()\n>>> -> ...\n>>> -> get_sha1_basic()\n>>> -> dwim_ref()\n>>>\n>>> callpath?\n>>\n>> Yes, indeed. Hmm, this is done even if the paths come after a\n>> double-dash. Anyway, I don't consider the check to be a performance\n>> issue, just a quick way to test the allocation count that i stumbled\n>> upon while working on the recent grep patches.\n> \n> I was merely reacting \"iterate over all of them\"; dwim_ref() only checks\n> if .git/blah, .git/refs/heads/blah, .git/refs/tags/blah, etc. exists and\n> the number of checks do not depend on the number of refs you have, so I\n> was wondering if I overlooked something that does for_each_ref() of\n> everything.\n\nYeah, for loose refs that's true. However, I have 470 packed refs, and\nthis command:\n\n\t$ valgrind --tool=exp-dhat ./git grep guess xdiff/xutils.c\n\nreports (among other findings):\n\n==28255== max-live: 30,334 in 470 blocks\n==28255== tot-alloc: 30,334 in 470 blocks (avg size 64.54)\n==28255== deaths: none (none of these blocks were freed)\n==28255== acc-ratios: 7.76 rd, 0.95 wr (235,582 b-read, 28,924 b-written)\n==28255== at 0x402AEE8: malloc (in /usr/lib/valgrind/vgpreload_exp-dhat-x86-linux.so)\n==28255== by 0x813691D: xmalloc (wrapper.c:50)\n==28255== by 0x8106B1A: create_ref_entry.constprop.8 (refs.c:250)\n==28255== by 0x8107761: read_packed_refs (refs.c:817)\n==28255== by 0x810785F: get_packed_refs (refs.c:843)\n==28255== by 0x8107BE7: resolve_ref_unsafe (refs.c:1028)\n==28255== by 0x81090AA: dwim_ref (refs.c:1549)\n==28255== by 0x8122E06: get_sha1_1 (sha1_name.c:304)\n==28255== by 0x81237EF: get_sha1_with_context_1 (sha1_name.c:1044)\n==28255== by 0x8124016: get_sha1 (cache.h:795)\n==28255== by 0x75782F65: ???\n\nRené\n"},{"id":"192043","messageId":"4FBDBA39.5020101@alum.mit.edu","threadId":"30591","inReplyTo":"4FBD1B36.5060404@lsrfire.ath.cx","subject":"Re: [PATCH 3/3] refs: use strings directly in find_containing_dir()","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-24T04:34:01Z","receivedAt":"2012-05-24T04:34:01Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/23/2012 07:15 PM, René Scharfe wrote:\n> Am 23.05.2012 18:56, schrieb Junio C Hamano:\n>> René Scharfe writes:\n>>\n>>> Am 23.05.2012 00:18, schrieb Junio C Hamano:\n>>>> René Scharfe writes:\n>>>>\n>>>>> What has git grep to do with refs? It checks if the path in the command\n>>>>> above is a ref, which makes it iterate over all of them..\n>>>>\n>>>> Do you mean:\n>>>>\n>>>> \t/* Is it a rev? */\n>>>> get_sha1()\n>>>> -> ...\n>>>> -> get_sha1_basic()\n>>>> -> dwim_ref()\n>>>>\n>>>> callpath?\n>>>\n>>> Yes, indeed. Hmm, this is done even if the paths come after a\n>>> double-dash. Anyway, I don't consider the check to be a performance\n>>> issue, just a quick way to test the allocation count that i stumbled\n>>> upon while working on the recent grep patches.\n>>\n>> I was merely reacting \"iterate over all of them\"; dwim_ref() only checks\n>> if .git/blah, .git/refs/heads/blah, .git/refs/tags/blah, etc. exists and\n>> the number of checks do not depend on the number of refs you have, so I\n>> was wondering if I overlooked something that does for_each_ref() of\n>> everything.\n>\n> Yeah, for loose refs that's true. However, I have 470 packed refs, and\n> this command:\n>\n> \t$ valgrind --tool=exp-dhat ./git grep guess xdiff/xutils.c\n>\n> reports (among other findings):\n>\n> ==28255== max-live: 30,334 in 470 blocks\n> ==28255== tot-alloc: 30,334 in 470 blocks (avg size 64.54)\n> ==28255== deaths: none (none of these blocks were freed)\n> ==28255== acc-ratios: 7.76 rd, 0.95 wr (235,582 b-read, 28,924 b-written)\n> ==28255== at 0x402AEE8: malloc (in /usr/lib/valgrind/vgpreload_exp-dhat-x86-linux.so)\n> ==28255== by 0x813691D: xmalloc (wrapper.c:50)\n> ==28255== by 0x8106B1A: create_ref_entry.constprop.8 (refs.c:250)\n> ==28255== by 0x8107761: read_packed_refs (refs.c:817)\n> ==28255== by 0x810785F: get_packed_refs (refs.c:843)\n> ==28255== by 0x8107BE7: resolve_ref_unsafe (refs.c:1028)\n> ==28255== by 0x81090AA: dwim_ref (refs.c:1549)\n> ==28255== by 0x8122E06: get_sha1_1 (sha1_name.c:304)\n> ==28255== by 0x81237EF: get_sha1_with_context_1 (sha1_name.c:1044)\n> ==28255== by 0x8124016: get_sha1 (cache.h:795)\n> ==28255== by 0x75782F65: ???\n\nYou are seeing all of the packed refs being *read*, which is triggered \nin this case by resolve_ref_unsafe() -> get_packed_refs(). This stack \ntrace does not imply that all references are being iterated through as \npart of a search. IOW, if dwim_ref() were called again, there would not \nbe another 470 allocations.\n\nThis is similar to the old code, which also read all of the packed refs \nwhenever any of them were accessed.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"}]}