{"thread":{"id":"39005","subject":"[PATCH 0/6] address packed-refs speed regressions","startedAt":"2015-04-05T01:06:11Z","lastAt":"2015-06-02T18:22:29Z","messageCount":44,"participants":["Jeff King","René Scharfe","Duy Nguyen","Junio C Hamano","Eric Sunshine","Rasmus Villemoes","Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"259005","messageId":"20150405010611.GA15901@peff.net","threadId":"39005","inReplyTo":null,"subject":"[PATCH 0/6] address packed-refs speed regressions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-05T01:06:11Z","receivedAt":"2015-04-05T01:06:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"As I've mentioned before, I have some repositories with rather large\nnumbers of refs. The worst one has ~13 million refs, for a 1.6GB\npacked-refs file. So I was saddened by this:\n\n $ time git.v2.0.0 rev-parse refs/heads/foo >/dev/null 2>&1\n real 0m6.840s\n user 0m6.404s\n sys 0m0.440s\n\n $ time git.v2.4.0-rc1 rev-parse refs/heads/foo >/dev/null 2>&1\n real 0m19.432s\n user 0m18.996s\n sys 0m0.456s\n\nThe command isn't important; what I'm really measuring is loading the\npacked-refs file. And yes, of course this repository is absolutely\nridiculous. But the slowdowns here are linear with the number of refs.\nSo _every_ git command got a little bit slower, even in less crazy\nrepositories. We just didn't notice it as much.\n\nHere are the numbers after this series:\n\n real 0m8.539s\n user 0m8.052s\n sys 0m0.496s\n\nMuch better, but I'm frustrated that they are still 20% slower than the\noriginal.\n\nThe main culprits seem to be d0f810f (which introduced some extra\nexpensive code for each ref) and my 10c497a, which switched from fgets()\nto strbuf_getwholeline. It turns out that strbuf_getwholeline is really\nslow.\n\nThere may be other problems lurking to account for the remaining 20%.\nIt's hard to find performance regressions with a bisection if there are\nmultiple of them; if you stop at a random commit and it is 500ms slow,\nit is hard to tell which problem is causing it.\n\nNote that while these are regressions, they are in v2.2.0 and v2.2.2\nrespectively. So this can wait until post-2.4.\n\n [1/6]: strbuf_getwholeline: use getc macro\n [2/6]: git-compat-util: add fallbacks for unlocked stdio\n [3/6]: strbuf_getwholeline: use get_unlocked\n [4/6]: strbuf: add an optimized 1-character strbuf_grow\n [5/6]: t1430: add another refs-escape test\n [6/6]: refname_is_safe: avoid expensive normalize_path_copy call\n\n-Peff\n"},{"id":"259006","messageId":"20150405010734.GA30127@peff.net","threadId":"39005","inReplyTo":"20150405010611.GA15901@peff.net","subject":"[PATCH 1/6] strbuf_getwholeline: use getc macro","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-05T01:07:35Z","receivedAt":"2015-04-05T01:07:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"strbuf_getwholeline calls fgetc in a tight loop. Using the\ngetc form, which can be implemented as a macro, should be\nfaster (and we do not care about it evaluating our argument\ntwice, as we just have a plain variable).\n\nOn my glibc system, running \"git rev-parse\nrefs/heads/does-not-exist\" on a file with an extremely large\n(1.6GB) packed-refs file went from (best of 3 runs):\n\n real 0m19.383s\n user 0m18.876s\n sys 0m0.528s\n\nto:\n\n real 0m18.900s\n user 0m18.472s\n sys 0m0.448s\n\nfor a wall-clock speedup of 2.5%.\n\nSigned-off-by: Jeff King \n---\nNot that exciting a speedup. But later we will switch to getc_unlocked,\nand I wanted to measure how much of that was coming from the macro, and\nhow much from the locking.\n\n strbuf.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/strbuf.c b/strbuf.c\nindex 88cafd4..14f337d 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -443,7 +443,7 @@ int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n \t\treturn EOF;\n \n \tstrbuf_reset(sb);\n-\twhile ((ch = fgetc(fp)) != EOF) {\n+\twhile ((ch = getc(fp)) != EOF) {\n \t\tstrbuf_grow(sb, 1);\n \t\tsb->buf[sb->len++] = ch;\n \t\tif (ch == term)\n-- \n2.4.0.rc0.363.gf9f328b\n"},{"id":"259007","messageId":"20150405010800.GB30127@peff.net","threadId":"39005","inReplyTo":"20150405010611.GA15901@peff.net","subject":"[PATCH 2/6] git-compat-util: add fallbacks for unlocked stdio","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-05T01:08:01Z","receivedAt":"2015-04-05T01:08:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"POSIX.1-2001 specifies some functions for optimizing the\nlocking out of tight getc() loops. Not all systems are\nPOSIX, though, and even not all POSIX systems are required\nto implement these functions. We can check for the\nfeature-test macro to see if they are available, and if not,\nprovide a noop implementation.\n\nThere's no Makefile knob here, because we should just detect\nthis automatically. If there are very bizarre systems, we\nmay need to add one, but it's not clear yet in which\ndirection:\n\n 1. If a system defines _POSIX_THREAD_SAFE_FUNCTIONS but\n these functions are missing or broken, we would want a\n knob to manually turn them off.\n\n 2. If a system has these functions but does not define\n _POSIX_THREAD_SAFE_FUNCTIONS, we would want a knob to\n manually turn them on.\n\nWe can add such a knob when we find a real-world system that\nmatches this.\n\nSigned-off-by: Jeff King \n---\n git-compat-util.h | 6 ++++++\n 1 file changed, 6 insertions(+)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex bc8fc8c..685a0a4 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -883,4 +883,10 @@ struct tm *git_gmtime_r(const time_t *, struct tm *);\n # define SHELL_PATH \"/bin/sh\"\n #endif\n \n+#ifndef _POSIX_THREAD_SAFE_FUNCTIONS\n+#define flockfile(fh)\n+#define funlockfile(fh)\n+#define getc_unlocked(fh) getc(fh)\n+#endif\n+\n #endif\n-- \n2.4.0.rc0.363.gf9f328b\n"},{"id":"259008","messageId":"20150405011110.GC30127@peff.net","threadId":"39005","inReplyTo":"20150405010611.GA15901@peff.net","subject":"[PATCH 3/6] strbuf_getwholeline: use getc_unlocked","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-05T01:11:10Z","receivedAt":"2015-04-05T01:11:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"strbuf_getwholeline calls getc in a tight loop. On modern\nlibc implementations, the stdio code locks the handle for\nevery operation, which means we are paying a significant\noverhead. We can get around this by locking the handle for\nthe whole loop and using the unlocked variant.\n\nRunning \"git rev-parse refs/heads/does-not-exist\" on a repo\nwith an extremely large (1.6GB) packed-refs file went from:\n\n real 0m18.900s\n user 0m18.472s\n sys 0m0.448s\n\nto:\n\n real 0m10.953s\n user 0m10.384s\n sys 0m0.580s\n\nfor a wall-clock speedup of 42%. All times are best-of-3,\nand done on a glibc 2.19 system.\n\nNote that we call into strbuf_grow while holding the lock.\nIt's possible for that function to call other stdio\nfunctions (e.g., printing to stderr when dying due to malloc\nerror); however, the POSIX.1-2001 definition of flockfile\nmakes it clear that the locks are per-handle, so we are fine\nunless somebody else tries to read from our same handle.\nThis doesn't ever happen in the current code, and is\nunlikely to be added in the future (we would have to do\nsomething exotic like add a die_routine that tried to read\nfrom stdin).\n\nSigned-off-by: Jeff King \n---\nI don't think the complexity is worth it, but if we wanted to be more\ncareful about the locks, I think it would probably involve growing the\nbuffer, locking, doing unlocked reads until it's full, and then\nunlocking for the next round of growth.\n\nI also considered optimizing the \"term == '\\n'\" case by using fgets, but\nit gets rather complex (you have to pick a size, fgets into it, and then\nkeep going if you didn't get a newline). Also, fgets sucks, because you\nhave to call strlen() immediately after to find out how many bytes you\ngot!\n\n strbuf.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/strbuf.c b/strbuf.c\nindex 14f337d..af2bad4 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -443,12 +443,14 @@ int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n \t\treturn EOF;\n \n \tstrbuf_reset(sb);\n-\twhile ((ch = getc(fp)) != EOF) {\n+\tflockfile(fp);\n+\twhile ((ch = getc_unlocked(fp)) != EOF) {\n \t\tstrbuf_grow(sb, 1);\n \t\tsb->buf[sb->len++] = ch;\n \t\tif (ch == term)\n \t\t\tbreak;\n \t}\n+\tfunlockfile(fp);\n \tif (ch == EOF && sb->len == 0)\n \t\treturn EOF;\n \n-- \n2.4.0.rc0.363.gf9f328b\n"},{"id":"259009","messageId":"20150405011127.GD30127@peff.net","threadId":"39005","inReplyTo":"20150405010611.GA15901@peff.net","subject":"[PATCH 4/6] strbuf: add an optimized 1-character strbuf_grow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-05T01:11:28Z","receivedAt":"2015-04-05T01:11:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We have to call strbuf_grow anytime we are going to add data\nto a strbuf. In most cases, it's a noop (since we grow the\nbuffer aggressively), and the cost of the function call and\nsize check is dwarfed by the actual buffer operation.\n\nFor a tight loop of single-character additions, though, this\noverhead is noticeable. Furthermore, the single-character\ncase is much easier to check; since the \"extra\" parameter is\n1, we can do it without worrying about overflow.\n\nThis patch adds a simple inline function for checking\nsingle-character growth. For the growth case, it just calls\ninto the regular strbuf_grow(). This is redundant, as\nstrbuf_grow will check again whether we need to grow. But it\nkeeps our inline code simple, and most calls will not need\nto grow, so it's OK to treat this as a rare \"slow path\".\n\nWe apply the new function to strbuf_getwholeline. Running\n\"git rev-parse refs/heads/does-not-exist\" on a repo with an\nextremely large (1.6GB) packed-refs file went from\n(best-of-3):\n\n real 0m10.953s\n user 0m10.384s\n sys 0m0.580s\n\nto:\n\n real 0m8.910s\n user 0m8.452s\n sys 0m0.468s\n\nfor a wall-clock speedup of 18%.\n\nSigned-off-by: Jeff King \n---\n strbuf.c | 2 +-\n strbuf.h | 9 +++++++++\n 2 files changed, 10 insertions(+), 1 deletion(-)\n\ndiff --git a/strbuf.c b/strbuf.c\nindex af2bad4..2facd5f 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -445,7 +445,7 @@ int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n \tstrbuf_reset(sb);\n \tflockfile(fp);\n \twhile ((ch = getc_unlocked(fp)) != EOF) {\n-\t\tstrbuf_grow(sb, 1);\n+\t\tstrbuf_grow_ch(sb);\n \t\tsb->buf[sb->len++] = ch;\n \t\tif (ch == term)\n \t\t\tbreak;\ndiff --git a/strbuf.h b/strbuf.h\nindex 1883494..ef41151 100644\n--- a/strbuf.h\n+++ b/strbuf.h\n@@ -137,6 +137,15 @@ static inline size_t strbuf_avail(const struct strbuf *sb)\n */\n extern void strbuf_grow(struct strbuf *, size_t);\n \n+/*\n+ * An optimized version of strbuf_grow() for a single character.\n+ */\n+static inline void strbuf_grow_ch(struct strbuf *sb)\n+{\n+\tif (!sb->alloc || sb->alloc - 1 <= sb->len)\n+\t\tstrbuf_grow(sb, 1);\n+}\n+\n /**\n * Set the length of the buffer to a given value. This function does *not*\n * allocate new memory, so you should not perform a `strbuf_setlen()` to a\n-- \n2.4.0.rc0.363.gf9f328b\n"},{"id":"259010","messageId":"20150405011142.GE30127@peff.net","threadId":"39005","inReplyTo":"20150405010611.GA15901@peff.net","subject":"[PATCH 5/6] t1430: add another refs-escape test","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-05T01:11:42Z","receivedAt":"2015-04-05T01:11:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"In t1430, we check whether deleting the branch \"../../foo\"\nwill delete \".git/foo\". However, this is not that\ninteresting a test; the precious file \".git/foo\" does not\nlook like a ref, so even if we did not notice the \"escape\"\nfrom the \"refs/\" hierarchy, we would fail for that reason\n(i.e., if you turned refname_is_safe into a noop, the test\nstill passes).\n\nLet's add an additional test for the same thing, but with a\nfile that actually looks like a ref. That will make sure we\nare exercising the refname_is_safe code. While we're at it,\nlet's also make the code work a little harder by adding some\nextra paths and some empty path components.\n\nSigned-off-by: Jeff King \n---\n t/t1430-bad-ref-name.sh | 8 ++++++++\n 1 file changed, 8 insertions(+)\n\ndiff --git a/t/t1430-bad-ref-name.sh b/t/t1430-bad-ref-name.sh\nindex 468e856..16d0b8b 100755\n--- a/t/t1430-bad-ref-name.sh\n+++ b/t/t1430-bad-ref-name.sh\n@@ -68,6 +68,14 @@ test_expect_success 'branch -D cannot delete non-ref in .git dir' '\n \ttest_cmp expect .git/my-private-file\n '\n \n+test_expect_success 'branch -D cannot delete ref in .git dir' '\n+\tgit rev-parse HEAD >.git/my-private-file &&\n+\tgit rev-parse HEAD >expect &&\n+\tgit branch foo/legit &&\n+\ttest_must_fail git branch -D foo////./././../../../my-private-file &&\n+\ttest_cmp expect .git/my-private-file\n+'\n+\n test_expect_success 'branch -D cannot delete absolute path' '\n \tgit branch -f extra &&\n \ttest_must_fail git branch -D \"$(pwd)/.git/refs/heads/extra\" &&\n-- \n2.4.0.rc0.363.gf9f328b\n"},{"id":"259011","messageId":"20150405011557.GF30127@peff.net","threadId":"39005","inReplyTo":"20150405010611.GA15901@peff.net","subject":"[PATCH 6/6] refname_is_safe: avoid expensive normalize_path_copy call","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-05T01:15:57Z","receivedAt":"2015-04-05T01:15:57Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Usually refs are not allowed to contain a \"..\" component.\nHowever, since d0f810f (refs.c: allow listing and deleting\nbadly named refs, 2014-09-03), we relax these rules in some\ncases in order to help users examine and get rid of\nbadly-named refs. However, we do still check that these refs\ncannot \"escape\" the refs hierarchy (e.g., \"refs/../foo\").\n\nThis check is implemented by calling normalize_path_copy,\nwhich requires us to allocate a new buffer to hold the\nresult. But we don't care about the result; we only care\nwhether the \"up\" components outnumbered the \"down\".\n\nWe can therefore implement this check ourselves without\nrequiring any extra allocations. With this patch, running\n\"git rev-parse refs/heads/does-not-exist\" on a repo with\nlarge (1.6GB) packed-refs file went from:\n\n real 0m8.910s\n user 0m8.452s\n sys 0m0.468s\n\nto:\n\n real 0m8.529s\n user 0m8.044s\n sys 0m0.492s\n\nfor a wall-clock speedup of 4%.\n\nSigned-off-by: Jeff King \n---\nThis was a lot less than I was hoping for, especially considering that\ngoing from d0f810f^ to d0f810f is more like a 15% slowdown (or in\nabsolute numbers, ~1.1s versus only 400ms here). What's doubly confusing\nis that I think we were running check_ref_format before d0f810f, which\ndoes way more than the check we're doing here. So we should have ended\nup faster than either.\n\nSo this is certainly _an_ improvement, but I think there may be more\ngoing on.\n\n cache.h | 7 +++++++\n path.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n refs.c | 16 ++--------------\n 3 files changed, 73 insertions(+), 14 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 3d3244b..c2b3df4 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -836,6 +836,13 @@ char *strip_path_suffix(const char *path, const char *suffix);\n int daemon_avoid_alias(const char *path);\n extern int is_ntfs_dotgit(const char *name);\n \n+/**\n+ * Returns 1 if the path \"escapes\" its root (e.g., \"foo/../../bar\") and 0\n+ * otherwise. Note that this is purely textual, and does not care about\n+ * symlinks or other aspects of the filesystem.\n+ */\n+int check_path_escape(const char *path);\n+\n /* object replacement */\n #define LOOKUP_REPLACE_OBJECT 1\n extern void *read_sha1_file_extended(const unsigned char *sha1, enum object_type *type, unsigned long *size, unsigned flag);\ndiff --git a/path.c b/path.c\nindex e608993..1127cbd 100644\n--- a/path.c\n+++ b/path.c\n@@ -703,6 +703,70 @@ int normalize_path_copy(char *dst, const char *src)\n }\n \n /*\n+ * We want to detect a path that \"escapes\" its root. The general strategy\n+ * is to parse components left to right, keeping track of our depth,\n+ * which is increased by non-empty components and decreased by \"..\"\n+ * components.\n+ */\n+int check_path_escape(const char *path)\n+{\n+\tint depth = 0;\n+\n+\twhile (*path) {\n+\t\tchar ch = *path++;\n+\n+\t\t/*\n+\t\t * We always start our loop at the beginning of a path component. So\n+\t\t * we can skip past any dir separators. This handles leading\n+\t\t * \"/\", as well as any internal \"////\".\n+\t\t */\n+\t\tif (is_dir_sep(ch))\n+\t\t\tcontinue;\n+\n+\t\t/*\n+\t\t * If we start with a dot, we care about the four cases\n+\t\t * (similar to normalize_path_copy above):\n+\t\t *\n+\t\t * (1) \".\" - does not affect depth; we are done\n+\t\t * (2) \"./\" - does not affect depth; skip\n+\t\t * (3) \"..\" - check depth and finish\n+\t\t * (4) \"../\" - drop depth, check, and keep looking\n+\t\t */\n+\t\tif (ch == '.') {\n+\t\t\tch = *path++;\n+\n+\t\t\tif (!ch)\n+\t\t\t\treturn 1; /* case (1) */\n+\t\t\tif (is_dir_sep(ch))\n+\t\t\t\tcontinue; /* case (2) */\n+\t\t\tif (ch == '.') {\n+\t\t\t\tch = *path++;\n+\t\t\t\tif (!ch)\n+\t\t\t\t\treturn depth > 0; /* case (3) */\n+\t\t\t\tif (is_dir_sep(ch)) {\n+\t\t\t\t\t/* case (4) */\n+\t\t\t\t\tif (--depth < 0)\n+\t\t\t\t\t\treturn 0;\n+\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\t\t\t\t/* otherwise, \"..foo\"; fall through */\n+\t\t\t}\n+\t\t\t/* otherwise \".foo\"; fall through */\n+\t\t}\n+\n+\t\t/*\n+\t\t * We have a real component; inrement the depth and eat the\n+\t\t * rest of the component\n+\t\t */\n+\t\tdepth++;\n+\t\twhile (*path && !is_dir_sep(*path))\n+\t\t\tpath++;\n+\t}\n+\n+\treturn 1;\n+}\n+\n+/*\n * path = Canonical absolute path\n * prefixes = string_list containing normalized, absolute paths without\n * trailing slashes (except for the root directory, which is denoted by \"/\").\ndiff --git a/refs.c b/refs.c\nindex 47e4e53..daca499 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -312,20 +312,8 @@ static struct ref_dir *get_ref_dir(struct ref_entry *entry)\n */\n static int refname_is_safe(const char *refname)\n {\n-\tif (starts_with(refname, \"refs/\")) {\n-\t\tchar *buf;\n-\t\tint result;\n-\n-\t\tbuf = xmalloc(strlen(refname) + 1);\n-\t\t/*\n-\t\t * Does the refname try to escape refs/?\n-\t\t * For example: refs/foo/../bar is safe but refs/foo/../../bar\n-\t\t * is not.\n-\t\t */\n-\t\tresult = !normalize_path_copy(buf, refname + strlen(\"refs/\"));\n-\t\tfree(buf);\n-\t\treturn result;\n-\t}\n+\tif (skip_prefix(refname, \"refs/\", &refname))\n+\t\treturn check_path_escape(refname);\n \twhile (*refname) {\n \t\tif (!isupper(*refname) && *refname != '_')\n \t\t\treturn 0;\n-- \n2.4.0.rc0.363.gf9f328b\n"},{"id":"259012","messageId":"20150405045614.GA12053@peff.net","threadId":"39005","inReplyTo":"20150405011110.GC30127@peff.net","subject":"Re: [PATCH 3/6] strbuf_getwholeline: use getc_unlocked","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-05T04:56:15Z","receivedAt":"2015-04-05T04:56:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Apr 04, 2015 at 09:11:10PM -0400, Jeff King wrote:\n\n> I also considered optimizing the \"term == '\\n'\" case by using fgets, but\n> it gets rather complex (you have to pick a size, fgets into it, and then\n> keep going if you didn't get a newline). Also, fgets sucks, because you\n> have to call strlen() immediately after to find out how many bytes you\n> got!\n\nMy initial attempt at this had been to _just_ use fgets, but the\noptimization becomes much simpler if you just do an initial fgets, and\nthen follow up with character reads. In most cases, the initial fgets\nis big enough to get the whole line.\n\nI.e., doing:\n\ndiff --git a/strbuf.c b/strbuf.c\nindex 2facd5f..f319d8d 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -443,6 +443,18 @@ int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n \t\treturn EOF;\n \n \tstrbuf_reset(sb);\n+\n+\tif (term == '\\n') {\n+\t\tstrbuf_grow(sb, 256);\n+\t\tif (!fgets(sb->buf, sb->alloc - 1, fp)) {\n+\t\t\tstrbuf_release(sb);\n+\t\t\treturn EOF;\n+\t\t}\n+\t\tsb->len = strlen(sb->buf);\n+\t\tif (sb->buf[sb->len - 1] == '\\n')\n+\t\t\treturn 0;\n+\t}\n+\n \tflockfile(fp);\n \twhile ((ch = getc_unlocked(fp)) != EOF) {\n \t\tstrbuf_grow_ch(sb);\n\non top of the series drops me from:\n\n real 0m8.573s\n user 0m8.072s\n sys 0m0.508s\n\nto:\n\n real 0m6.671s\n user 0m6.216s\n sys 0m0.460s\n\nwhich is back to the v2.0.0 number. Even with the extra strlen, it seems\nthat what fgets does internally beats repeated getc calls. Which I guess\nis not too surprising, as each getc() will have to check for underflow\nin the buffer. Perhaps there is more room to micro-optimize\nstrbuf_getwholeline, but I kind of doubt it.\n\nThe big downside is that our input strings are no longer NUL-clean\n(reading \"foo\\0bar\\n\" would yield just \"foo\". I doubt that matters in\nthe real world, but it does fail a few of the tests (e.g., t7008 tries\nto read a list of patterns which includes NUL, and we silently truncate\nthe pattern rather than read in the NUL and barf).\n\nSo we'd have to either:\n\n 1. Decide that doesn't matter.\n\n 2. Have callers specify a \"damn the NULs, I want it fast\" flag.\n\n 3. Find some alternative that is more robust than fgets, and faster\n than getc. I don't think there is anything in stdio, but I am not\n above dropping in a faster non-portable call if it is available,\n and then falling back to the current code otherwise.\n\n-Peff\n"},{"id":"259013","messageId":"20150405052732.GA14771@peff.net","threadId":"39005","inReplyTo":"20150405045614.GA12053@peff.net","subject":"Re: [PATCH 3/6] strbuf_getwholeline: use getc_unlocked","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-05T05:27:33Z","receivedAt":"2015-04-05T05:27:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Apr 05, 2015 at 12:56:14AM -0400, Jeff King wrote:\n\n> The big downside is that our input strings are no longer NUL-clean\n> (reading \"foo\\0bar\\n\" would yield just \"foo\". I doubt that matters in\n> the real world, but it does fail a few of the tests (e.g., t7008 tries\n> to read a list of patterns which includes NUL, and we silently truncate\n> the pattern rather than read in the NUL and barf).\n\nSo there is this trick:\n\ndiff --git a/strbuf.c b/strbuf.c\nindex f319d8d..5ceebb7 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -445,12 +445,13 @@ int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n \tstrbuf_reset(sb);\n \n \tif (term == '\\n') {\n+\t\tlong pos = ftell(fp);\n \t\tstrbuf_grow(sb, 256);\n \t\tif (!fgets(sb->buf, sb->alloc - 1, fp)) {\n \t\t\tstrbuf_release(sb);\n \t\t\treturn EOF;\n \t\t}\n-\t\tsb->len = strlen(sb->buf);\n+\t\tsb->len = ftell(fp) - pos;\n \t\tif (sb->buf[sb->len - 1] == '\\n')\n \t\t\treturn 0;\n \t}\n\nbut much to my surprise it actually runs slower than the strlen version!\nIt also has a 32-bit overflow issue. There's fgetpos() as an\nalternative, but fpos_t is an opaque type, and we might not be able to\ndo arithmetic on it (for that matter, I am not sure if arithmetic is\nstrictly guaranteed on ftell() results). POSIX gives us ftello(), which\nreturns an off_t. That would probably be fine.\n\nThe ftello() version seems slower than the strlen, but faster than\nftell(). Puzzling.\n\n-Peff\n"},{"id":"259014","messageId":"20150405053535.GB14771@peff.net","threadId":"39005","inReplyTo":"20150405052732.GA14771@peff.net","subject":"Re: [PATCH 3/6] strbuf_getwholeline: use getc_unlocked","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-05T05:35:36Z","receivedAt":"2015-04-05T05:35:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Apr 05, 2015 at 01:27:32AM -0400, Jeff King wrote:\n\n> On Sun, Apr 05, 2015 at 12:56:14AM -0400, Jeff King wrote:\n> \n> > The big downside is that our input strings are no longer NUL-clean\n> > (reading \"foo\\0bar\\n\" would yield just \"foo\". I doubt that matters in\n> > the real world, but it does fail a few of the tests (e.g., t7008 tries\n> > to read a list of patterns which includes NUL, and we silently truncate\n> > the pattern rather than read in the NUL and barf).\n> \n> So there is this trick:\n> \n> diff --git a/strbuf.c b/strbuf.c\n> index f319d8d..5ceebb7 100644\n> --- a/strbuf.c\n> +++ b/strbuf.c\n> @@ -445,12 +445,13 @@ int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n> \tstrbuf_reset(sb);\n> \n> \tif (term == '\\n') {\n> +\t\tlong pos = ftell(fp);\n> \t\tstrbuf_grow(sb, 256);\n> \t\tif (!fgets(sb->buf, sb->alloc - 1, fp)) {\n> \t\t\tstrbuf_release(sb);\n> \t\t\treturn EOF;\n> \t\t}\n> -\t\tsb->len = strlen(sb->buf);\n> +\t\tsb->len = ftell(fp) - pos;\n> \t\tif (sb->buf[sb->len - 1] == '\\n')\n> \t\t\treturn 0;\n> \t}\n> \n> but much to my surprise it actually runs slower than the strlen version!\n> It also has a 32-bit overflow issue. There's fgetpos() as an\n> alternative, but fpos_t is an opaque type, and we might not be able to\n> do arithmetic on it (for that matter, I am not sure if arithmetic is\n> strictly guaranteed on ftell() results). POSIX gives us ftello(), which\n> returns an off_t. That would probably be fine.\n\nActually, scratch that idea. ftell() always returns 0 on a non-seekable\nfile, so we can't use it in the general case. And that probably explains\nthe performance difference, too, if it is not keeping its own counter\nand relies on lseek(fileno(fp)) or similar.\n\n-Peff\n"},{"id":"259021","messageId":"55213B93.9050207@web.de","threadId":"39005","inReplyTo":"20150405010611.GA15901@peff.net","subject":"Re: [PATCH 0/6] address packed-refs speed regressions","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2015-04-05T13:41:39Z","receivedAt":"2015-04-05T13:41:39Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 05.04.2015 um 03:06 schrieb Jeff King:\n> As I've mentioned before, I have some repositories with rather large\n> numbers of refs. The worst one has ~13 million refs, for a 1.6GB\n> packed-refs file. So I was saddened by this:\n> \n> $ time git.v2.0.0 rev-parse refs/heads/foo >/dev/null 2>&1\n> real 0m6.840s\n> user 0m6.404s\n> sys 0m0.440s\n> \n> $ time git.v2.4.0-rc1 rev-parse refs/heads/foo >/dev/null 2>&1\n> real 0m19.432s\n> user 0m18.996s\n> sys 0m0.456s\n> \n> The command isn't important; what I'm really measuring is loading the\n> packed-refs file. And yes, of course this repository is absolutely\n> ridiculous. But the slowdowns here are linear with the number of refs.\n> So _every_ git command got a little bit slower, even in less crazy\n> repositories. We just didn't notice it as much.\n> \n> Here are the numbers after this series:\n> \n> real 0m8.539s\n> user 0m8.052s\n> sys 0m0.496s\n> \n> Much better, but I'm frustrated that they are still 20% slower than the\n> original.\n> \n> The main culprits seem to be d0f810f (which introduced some extra\n> expensive code for each ref) and my 10c497a, which switched from fgets()\n> to strbuf_getwholeline. It turns out that strbuf_getwholeline is really\n> slow.\n\n10c497a changed read_packed_refs(), which reads *all* packed refs.\nEach is checked for validity. That sounds expensive if the goal is\njust to look up a single (non-existing) ref.\n\nWould it help to defer any checks until a ref is actually accessed?\nCan a binary search be used instead of reading the whole file?\n\nI wonder if pluggable reference backends could help here. Storing refs\nin a database table indexed by refname should simplify things.\n\nShort-term, can we avoid the getc()/strbuf_grow() dance e.g. by mapping\nthe packed refs file? What numbers do you get with the following patch?\n\n---\n refs.c | 36 ++++++++++++++++++++++++++++--------\n 1 file changed, 28 insertions(+), 8 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 47e4e53..144255f 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1153,16 +1153,35 @@ static const char *parse_ref_line(struct strbuf *line, unsigned char *sha1)\n * compatibility with older clients, but we do not require it\n * (i.e., \"peeled\" is a no-op if \"fully-peeled\" is set).\n */\n-static void read_packed_refs(FILE *f, struct ref_dir *dir)\n+static void read_packed_refs(int fd, struct ref_dir *dir)\n {\n \tstruct ref_entry *last = NULL;\n \tstruct strbuf line = STRBUF_INIT;\n \tenum { PEELED_NONE, PEELED_TAGS, PEELED_FULLY } peeled = PEELED_NONE;\n+\tstruct stat st;\n+\tvoid *map;\n+\tsize_t mapsz, len;\n+\tconst char *p;\n+\n+\tfstat(fd, &st);\n+\tmapsz = xsize_t(st.st_size);\n+\tif (!mapsz)\n+\t\treturn;\n+\tmap = xmmap(NULL, mapsz, PROT_READ, MAP_PRIVATE, fd, 0);\n \n-\twhile (strbuf_getwholeline(&line, f, '\\n') != EOF) {\n+\tfor (p = map, len = mapsz; len; ) {\n \t\tunsigned char sha1[20];\n \t\tconst char *refname;\n \t\tconst char *traits;\n+\t\tconst char *nl;\n+\t\tsize_t linelen;\n+\n+\t\tnl = memchr(p, '\\n', len);\n+\t\tlinelen = nl ? nl - p + 1 : len;\n+\t\tstrbuf_reset(&line);\n+\t\tstrbuf_add(&line, p, linelen);\n+\t\tp += linelen;\n+\t\tlen -= linelen;\n \n \t\tif (skip_prefix(line.buf, \"# pack-refs with:\", &traits)) {\n \t\t\tif (strstr(traits, \" fully-peeled \"))\n@@ -1204,6 +1223,7 @@ static void read_packed_refs(FILE *f, struct ref_dir *dir)\n \t}\n \n \tstrbuf_release(&line);\n+\tmunmap(map, mapsz);\n }\n \n /*\n@@ -1224,16 +1244,16 @@ static struct packed_ref_cache *get_packed_ref_cache(struct ref_cache *refs)\n \t\tclear_packed_ref_cache(refs);\n \n \tif (!refs->packed) {\n-\t\tFILE *f;\n+\t\tint fd;\n \n \t\trefs->packed = xcalloc(1, sizeof(*refs->packed));\n \t\tacquire_packed_ref_cache(refs->packed);\n \t\trefs->packed->root = create_dir_entry(refs, \"\", 0, 0);\n-\t\tf = fopen(packed_refs_file, \"r\");\n-\t\tif (f) {\n-\t\t\tstat_validity_update(&refs->packed->validity, fileno(f));\n-\t\t\tread_packed_refs(f, get_ref_dir(refs->packed->root));\n-\t\t\tfclose(f);\n+\t\tfd = open(packed_refs_file, O_RDONLY);\n+\t\tif (fd >= 0) {\n+\t\t\tstat_validity_update(&refs->packed->validity, fd);\n+\t\t\tread_packed_refs(fd, get_ref_dir(refs->packed->root));\n+\t\t\tclose(fd);\n \t\t}\n \t}\n \treturn refs->packed;\n-- \n2.3.5\n"},{"id":"259023","messageId":"CACsJy8Biv6D2foDxpn-CZhEsjn3WsPV=_A3UOnT4+1LVrpRnTw@mail.gmail.com","threadId":"39005","inReplyTo":"20150405045614.GA12053@peff.net","subject":"Re: [PATCH 3/6] strbuf_getwholeline: use getc_unlocked","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2015-04-05T14:36:04Z","receivedAt":"2015-04-05T14:36:04Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Apr 5, 2015 at 11:56 AM, Jeff King wrote:\n> So we'd have to either:\n>\n> 1. Decide that doesn't matter.\n>\n> 2. Have callers specify a \"damn the NULs, I want it fast\" flag.\n\n2+. Avoid FILE* interface and go with syscalls for reading\npacked-refs? If mmaping the entire file could be a problem for some\nplatform because it's too large, we have code for reading (with\nbufferring) from fd somewhere, e.g. index-pack.\n\n> 3. Find some alternative that is more robust than fgets, and faster\n> than getc. I don't think there is anything in stdio, but I am not\n> above dropping in a faster non-portable call if it is available,\n> and then falling back to the current code otherwise.\n-- \nDuy\n"},{"id":"259026","messageId":"20150405182401.GA13096@peff.net","threadId":"39005","inReplyTo":"CACsJy8Biv6D2foDxpn-CZhEsjn3WsPV=_A3UOnT4+1LVrpRnTw@mail.gmail.com","subject":"Re: [PATCH 3/6] strbuf_getwholeline: use getc_unlocked","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-05T18:24:02Z","receivedAt":"2015-04-05T18:24:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Apr 05, 2015 at 09:36:04PM +0700, Duy Nguyen wrote:\n\n> On Sun, Apr 5, 2015 at 11:56 AM, Jeff King wrote:\n> > So we'd have to either:\n> >\n> > 1. Decide that doesn't matter.\n> >\n> > 2. Have callers specify a \"damn the NULs, I want it fast\" flag.\n> \n> 2+. Avoid FILE* interface and go with syscalls for reading\n> packed-refs? If mmaping the entire file could be a problem for some\n> platform because it's too large, we have code for reading (with\n> bufferring) from fd somewhere, e.g. index-pack.\n\nThere's strbuf_getwholeline_fd, but it's horrifically inefficient (one\nsyscall per character). But the other option is to implement your own\nbuffering, and we're generally better off letting stdio do that for us\n(the exception here is that stdio does not have a good NUL-safe \"read\nuntil X\" function).\n\n-Peff\n"},{"id":"259028","messageId":"20150405185259.GB13096@peff.net","threadId":"39005","inReplyTo":"55213B93.9050207@web.de","subject":"Re: [PATCH 0/6] address packed-refs speed regressions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-05T18:52:59Z","receivedAt":"2015-04-05T18:52:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Apr 05, 2015 at 03:41:39PM +0200, René Scharfe wrote:\n\n> > The main culprits seem to be d0f810f (which introduced some extra\n> > expensive code for each ref) and my 10c497a, which switched from fgets()\n> > to strbuf_getwholeline. It turns out that strbuf_getwholeline is really\n> > slow.\n> \n> 10c497a changed read_packed_refs(), which reads *all* packed refs.\n> Each is checked for validity. That sounds expensive if the goal is\n> just to look up a single (non-existing) ref.\n> \n> Would it help to defer any checks until a ref is actually accessed?\n> Can a binary search be used instead of reading the whole file?\n\nYes, but addressing that is much more invasive.\n\nRight now we parse all of the packed-refs file into an in-memory cache,\nand then do single lookups from that cache. Doing an mmap() and a binary\nsearch is way faster (and costs less memory) for doing individual\nlookups. It relies on the list being sorted. This is generally true, but\nnot something we currently rely on (however, it would be easy to add a\n\"sorted\" flag to top of the file and have the readers fall back when the\nflag is missing). I've played with a patch to do this (it's not entirely\ntrivial, because you jump into the middle of a line, and then have to\nwalk backwards to find the start of the record).\n\nFor traversals, it's more complicated. Obviously if you are traversing\nall refs, you have to read the whole thing anyway. If you are traversing\na subset of the refs, you can binary-search the start of the subset, and\nthen walk forward. But that's where it gets tricky with the current\ncode.\n\nThe ref_cache code expects to fill in from outer to inner. So if you\nhave \"refs/foo\", you should also have filled in all of \"refs/\" (but not\nnecessarily \"refs/bar\"). This matches the way we traverse loose ref\ndirectories; we opendir \"refs/\", find out that it has \"foo\" and \"bar\",\nand the descend into \"foo\", and so forth. But reading a subset of the\npacked-ref file is \"inside out\". You fill in all of \"refs/foo\", but you\nhave no idea what else is in \"refs/\".\n\nSo going in that direction would involve some surgery to the ref_cache\ncode. It might even involve throwing it out entirely (i.e., just mmap\nthe packed-refs file and look through it directly, without any kind of\nin-memory cache; we don't tend to do more than one ref-iteration per\nprogram anyway, so I'm not sure the caching is buying us much anyway).\nMy big concern there would be that there are a lot of subtle race issues\nbetween packed and loose refs, and the current state is the result of a\nlot of tweaking. I'd be worried that a heavy rewrite there would risk\nintroducing subtle and rare corruptions.\n\nPlus it would be a lot of work, which leads me to...\n\n> I wonder if pluggable reference backends could help here. Storing refs\n> in a database table indexed by refname should simplify things.\n\n...this. I think that effort might be better spent on a ref storage\nformat that's more efficient, simpler (with respect to subtle races and\nsuch), and could provide other features (e.g., transactional atomicity).\n\nThe big plus side of packed-refs improvements is that they \"just work\"\nwithout worrying about compatibility issues. But ref storage is local,\nso I'm not sure how big a deal that is in practice.\n\n> Short-term, can we avoid the getc()/strbuf_grow() dance e.g. by mapping\n> the packed refs file? What numbers do you get with the following patch?\n\nIt's about 9% faster than my series + the fgets optimization I posted\n(or about 25% than using getc). Which is certainly nice, but I was\nreally hoping to just make strbuf_getline faster for all callers, rather\nthan introducing special code for one call-site. Certainly we could\ngeneralize the technique (i.e., a struct with the mmap data), but then I\nfeel we are somewhat reinventing stdio. Which is maybe a good thing,\nbecause stdio has a lot of rough edges (as seen here), but it does feel\na bit like NIH syndrome.\n\n-Peff\n"},{"id":"259029","messageId":"20150405185911.GA19902@peff.net","threadId":"39005","inReplyTo":"20150405185259.GB13096@peff.net","subject":"Re: [PATCH 0/6] address packed-refs speed regressions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-05T18:59:12Z","receivedAt":"2015-04-05T18:59:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Apr 05, 2015 at 02:52:59PM -0400, Jeff King wrote:\n\n> Right now we parse all of the packed-refs file into an in-memory cache,\n> and then do single lookups from that cache. Doing an mmap() and a binary\n> search is way faster (and costs less memory) for doing individual\n> lookups. It relies on the list being sorted. This is generally true, but\n> not something we currently rely on (however, it would be easy to add a\n> \"sorted\" flag to top of the file and have the readers fall back when the\n> flag is missing). I've played with a patch to do this (it's not entirely\n> trivial, because you jump into the middle of a line, and then have to\n> walk backwards to find the start of the record).\n> \n> For traversals, it's more complicated. Obviously if you are traversing\n> all refs, you have to read the whole thing anyway. If you are traversing\n> a subset of the refs, you can binary-search the start of the subset, and\n> then walk forward. But that's where it gets tricky with the current\n> code.\n\nIn case you are curious, here is my proof-of-concept for the packed-refs\nbinary search. You'll note that it's a separate program, and not\nintegrated into refs.c. I wrote this last August, and after trying to\nintegrate it into refs.c, I found the ref_cache problems I described,\nand I haven't touched it since.\n\nI also seem to have saved the patch for stuffing it into refs.c, but I\nam not sure if it even compiles (I wrote only \"horrible wip\" in the\ncommit message ;) ).\n\n-- >8 --\nSubject: [PATCH] add git-quick-list\n\nThis is a proof of concept for binary-searching the\npacked-refs file in order to traverse an ordered subset of\nit. Note that it _only_ reads the packed-refs file\ncurrently. To really compare to for-each-ref, it would need\nto also walk the loose ref area for its prefix. On a\nmostly-packed repository that shouldn't make a big speed\ndifference, though.\n\nAnd of course we don't _really_ want a separate command here\nat all. This should be part of refs.c, and everyone who\ncalls for_each_ref should benefit from it.\n\nStill, the numbers are promising. Here's are comparisons\nagainst for-each-ref on torvalds/linux, which has a 218M\npacked-refs file:\n\n $ time git for-each-ref \\\n --format='%(objectname) %(refname)' \\\n refs/remotes/2325298/ |\n wc -c\n 44139\n\n real 0m1.649s\n user 0m1.332s\n sys 0m0.304s\n\n $ time ~peff/git-quick-list refs/remotes/2325298/ | wc -c\n 44139\n\n real 0m0.012s\n user 0m0.004s\n sys 0m0.004s\n---\n Makefile | 1 +\n quick-list.c | 174 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 175 insertions(+)\n create mode 100644 quick-list.c\n\ndiff --git a/Makefile b/Makefile\nindex 2457065..aa32598 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -541,6 +541,7 @@ PROGRAM_OBJS += shell.o\n PROGRAM_OBJS += show-index.o\n PROGRAM_OBJS += upload-pack.o\n PROGRAM_OBJS += remote-testsvn.o\n+PROGRAM_OBJS += quick-list.o\n \n # Binary suffix, set to .exe for Windows builds\n X =\ndiff --git a/quick-list.c b/quick-list.c\nnew file mode 100644\nindex 0000000..e423f1f\n--- /dev/null\n+++ b/quick-list.c\n@@ -0,0 +1,174 @@\n+#include \"cache.h\"\n+#include \"refs.h\"\n+\n+struct packed_refs_iterator {\n+\tconst char *start;\n+\tconst char *end;\n+\n+\tconst char *cur;\n+\tconst char *ref;\n+\tconst char *eol;\n+\tconst char *next;\n+};\n+\n+static void iterator_init(struct packed_refs_iterator *pos,\n+\t\t\t const char *buf, size_t len)\n+{\n+\tpos->start = buf;\n+\tpos->end = buf + len;\n+\n+\t/* skip past header line */\n+\tif (pos->start < pos->end && *pos->start == '#') {\n+\t\twhile (pos->start < pos->end && *pos->start != '\\n')\n+\t\t\tpos->start++;\n+\t\tif (pos->start < pos->end)\n+\t\t\tpos->start++;\n+\t}\n+}\n+\n+static int iterator_cmp(const char *key, struct packed_refs_iterator *pos)\n+{\n+\tconst char *ref = pos->ref;\n+\tfor (; *key && ref < pos->eol; key++, ref++)\n+\t\tif (*key != *ref)\n+\t\t\treturn (unsigned char)*key - (unsigned char)*ref;\n+\treturn ref == pos->eol ? *key ? 1 : 0 : -1;\n+}\n+\n+static const char *find_eol(const char *p, const char *end)\n+{\n+\tp = memchr(p, '\\n', end - p);\n+\treturn p ? p : end;\n+}\n+\n+static void parse_line(struct packed_refs_iterator *pos, const char *p)\n+{\n+\tpos->cur = p;\n+\tif (pos->end - p < 41)\n+\t\tdie(\"truncated packed-refs file\");\n+\tp += 41;\n+\n+\tpos->ref = p;\n+\tpos->eol = p = find_eol(p, pos->end);\n+\n+\t/* skip newline, and then past any peel records */\n+\tif (p < pos->end)\n+\t\tp++;\n+\twhile (p < pos->end && *p == '^') {\n+\t\tp = find_eol(p, pos->end);\n+\t\tif (p < pos->end)\n+\t\t\tp++;\n+\t}\n+\tpos->next = p;\n+}\n+\n+static void iterator_next(struct packed_refs_iterator *pos)\n+{\n+\tif (pos->next < pos->end)\n+\t\tparse_line(pos, pos->next);\n+\telse\n+\t\tpos->cur = NULL;\n+}\n+\n+static void iterator_start(struct packed_refs_iterator *pos, const char *prefix)\n+{\n+\tconst char *lo = pos->start, *hi = pos->end;\n+\n+\twhile (lo < hi) {\n+\t\tconst char *mi = lo + ((hi - lo) / 2);\n+\t\tint cmp;\n+\n+\t\t/*\n+\t\t * We landed somewhere on a line. Walk back to find\n+\t\t * the start of the line.\n+\t\t */\n+\t\twhile (mi > lo && *(mi-1) != '\\n')\n+\t\t\tmi--;\n+\n+\t\t/*\n+\t\t * We may have hit a peel-line. In that case, try\n+\t\t * to walk back to the actual ref line (and skip as\n+\t\t * many peel lines as we find, for future-proofing).\n+\t\t */\n+\t\twhile (*mi == '^') {\n+\t\t\tif (mi == lo)\n+\t\t\t\tdie(\"peel line without a record before it?\");\n+\t\t\tmi--;\n+\t\t\tif (mi == lo)\n+\t\t\t\tdie(\"peel line with bare newline before it?\");\n+\t\t\tmi--;\n+\t\t\twhile (mi > lo && *(mi-1) != '\\n')\n+\t\t\t\tmi--;\n+\t\t}\n+\n+\t\t/* Now we should be at a real ref line. */\n+\t\tparse_line(pos, mi);\n+\t\tcmp = iterator_cmp(prefix, pos);\n+\t\tif (!cmp)\n+\t\t\treturn;\n+\t\telse if (cmp < 0)\n+\t\t\thi = pos->cur;\n+\t\telse\n+\t\t\tlo = pos->next;\n+\t}\n+\n+\tif (hi < pos->end)\n+\t\tparse_line(pos, hi);\n+\telse\n+\t\tpos->cur = NULL;\n+}\n+\n+static void quick_list(const char *prefix, each_ref_fn fn, void *data)\n+{\n+\tint fd = open(git_path(\"packed-refs\"), O_RDONLY);\n+\tstruct stat st;\n+\tconst char *buf = NULL;\n+\tsize_t len;\n+\tstruct packed_refs_iterator pos;\n+\n+\tif (fd < 0)\n+\t\tgoto out;\n+\tif (fstat(fd, &st) < 0)\n+\t\tgoto out;\n+\tlen = xsize_t(st.st_size);\n+\tbuf = xmmap(NULL, len, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tif (!buf)\n+\t\tgoto out;\n+\n+\titerator_init(&pos, buf, len);\n+\tfor (iterator_start(&pos, prefix);\n+\t pos.cur && starts_with(pos.ref, prefix);\n+\t iterator_next(&pos)) {\n+\t\tunsigned char sha1[20];\n+\t\tchar *refname;\n+\n+\t\tif (get_sha1_hex(pos.cur, sha1) < 0)\n+\t\t\tdie(\"packed-refs contained invalid sha1\");\n+\t\trefname = xmemdupz(pos.ref, pos.eol - pos.ref);\n+\t\tfn(refname, sha1, 0, data);\n+\t\tfree(refname);\n+\t}\n+\n+out:\n+\tclose(fd);\n+\tif (buf)\n+\t\tmunmap((void *)buf, len);\n+}\n+\n+static int show_ref(const char *refname, const unsigned char *sha1,\n+\t\t int flags, void *data)\n+{\n+\tprintf(\"%s %s\\n\", sha1_to_hex(sha1), refname);\n+\treturn 0;\n+}\n+\n+int main(int argc, char **argv)\n+{\n+\tif (argc != 2)\n+\t\tusage(\"git quick-list \");\n+\n+\tsetup_git_directory();\n+\tquick_list(argv[1], show_ref, NULL);\n+\n+\treturn 0;\n+}\n-- \n2.4.0.rc0.363.gf9f328b\n"},{"id":"259032","messageId":"xmqq4moue3rf.fsf@gitster.dls.corp.google.com","threadId":"39005","inReplyTo":"20150405045614.GA12053@peff.net","subject":"Re: [PATCH 3/6] strbuf_getwholeline: use getc_unlocked","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-04-05T20:09:24Z","receivedAt":"2015-04-05T20:09:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> So we'd have to either:\n>\n> 1. Decide that doesn't matter.\n>\n> 2. Have callers specify a \"damn the NULs, I want it fast\" flag.\n\nThe callers that used to call fgets and then later rewritten to\nstrbuf_getwholeline(), either of the above obviously should be OK,\nand because the whole reason why we added strbuf_getline() interface\nwas to avoid having to repeatedly call fgets() and concatenate the\nresult if the fixed-size buffer we would give it is too small, I'd\nsay the callers that want to read lines terminated by LF and have NUL\nas part of payload would be a tiny minority.\n\nIt depends on what we would find out after auditing all callers of\nthis function, but I would not be surprised if we decided #1 (i.e.\n\"this is about a _line_; what are you doing by having a NUL on\nit?\"), and the safest would be to do the inverse of #2, i.e. make it\nfast by default and make oddball callers that care about NULs to\npass a flag.\n\nThanks for working on this.\n"},{"id":"259034","messageId":"xmqqpp7icnbi.fsf@gitster.dls.corp.google.com","threadId":"39005","inReplyTo":"20150405053535.GB14771@peff.net","subject":"Re: [PATCH 3/6] strbuf_getwholeline: use getc_unlocked","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-04-05T20:49:53Z","receivedAt":"2015-04-05T20:49:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Sun, Apr 05, 2015 at 01:27:32AM -0400, Jeff King wrote:\n>\n>> On Sun, Apr 05, 2015 at 12:56:14AM -0400, Jeff King wrote:\n>> \n>> > The big downside is that our input strings are no longer NUL-clean\n>> > (reading \"foo\\0bar\\n\" would yield just \"foo\". I doubt that matters in\n>> > the real world, but it does fail a few of the tests (e.g., t7008 tries\n>> > to read a list of patterns which includes NUL, and we silently truncate\n>> > the pattern rather than read in the NUL and barf).\n>> \n>> So there is this trick:\n>> \n>> diff --git a/strbuf.c b/strbuf.c\n>> index f319d8d..5ceebb7 100644\n>> --- a/strbuf.c\n>> +++ b/strbuf.c\n>> @@ -445,12 +445,13 @@ int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n>> \tstrbuf_reset(sb);\n>> \n>> \tif (term == '\\n') {\n>> +\t\tlong pos = ftell(fp);\n>> \t\tstrbuf_grow(sb, 256);\n>> \t\tif (!fgets(sb->buf, sb->alloc - 1, fp)) {\n>> \t\t\tstrbuf_release(sb);\n>> \t\t\treturn EOF;\n>> \t\t}\n>> -\t\tsb->len = strlen(sb->buf);\n>> +\t\tsb->len = ftell(fp) - pos;\n>> \t\tif (sb->buf[sb->len - 1] == '\\n')\n>> \t\t\treturn 0;\n>> \t}\n>> \n>> but much to my surprise it actually runs slower than the strlen version!\n\n\nThe later loop you have \"oops, the thing turns out to be longer than\nwe thought, so let's do byte-by-byte\" is protected with locking, but\nthis part is not, and that suggests me that the ftell-fgets-ftell\nsequence we see here may have its own locking cost built-in in the\nstdio library, too, perhaps?\n\n>> It also has a 32-bit overflow issue. There's fgetpos() as an\n>> alternative, but fpos_t is an opaque type, and we might not be able to\n>> do arithmetic on it (for that matter, I am not sure if arithmetic is\n>> strictly guaranteed on ftell() results). POSIX gives us ftello(), which\n>> returns an off_t. That would probably be fine.\n>\n> Actually, scratch that idea. ftell() always returns 0 on a non-seekable\n> file, so we can't use it in the general case. And that probably explains\n> the performance difference, too, if it is not keeping its own counter\n> and relies on lseek(fileno(fp)) or similar.\n\nLooked so promising, though ;-) X-<.\n"},{"id":"259037","messageId":"5521B993.1080202@web.de","threadId":"39005","inReplyTo":"20150405185259.GB13096@peff.net","subject":"Re: [PATCH 0/6] address packed-refs speed regressions","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2015-04-05T22:39:15Z","receivedAt":"2015-04-05T22:39:15Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 05.04.2015 um 20:52 schrieb Jeff King:\n> On Sun, Apr 05, 2015 at 03:41:39PM +0200, René Scharfe wrote:\n>> I wonder if pluggable reference backends could help here. Storing refs\n>> in a database table indexed by refname should simplify things.\n>\n> ...this. I think that effort might be better spent on a ref storage\n> format that's more efficient, simpler (with respect to subtle races and\n> such), and could provide other features (e.g., transactional atomicity).\n\nSuch as a DBMS? :-) Leaving storage details to SQLite or whatever \nsounds attractive to me because I'm lazy.\n\n> The big plus side of packed-refs improvements is that they \"just work\"\n> without worrying about compatibility issues. But ref storage is local,\n> so I'm not sure how big a deal that is in practice.\n\nAdding a dependency is a big step, admittedly, so native improvements \nmight be a better fit. There's a chance that we'd run into issues \nalready solved by specialized database engines long ago, though.\n\n>> Short-term, can we avoid the getc()/strbuf_grow() dance e.g. by mapping\n>> the packed refs file? What numbers do you get with the following patch?\n>\n> It's about 9% faster than my series + the fgets optimization I posted\n> (or about 25% than using getc). Which is certainly nice, but I was\n> really hoping to just make strbuf_getline faster for all callers, rather\n> than introducing special code for one call-site. Certainly we could\n> generalize the technique (i.e., a struct with the mmap data), but then I\n> feel we are somewhat reinventing stdio. Which is maybe a good thing,\n> because stdio has a lot of rough edges (as seen here), but it does feel\n> a bit like NIH syndrome.\n\nForgot to say: I like your changes. But if strbuf_getline can only be \nmade fast enough beyond that by duplicating stdio buffering then I feel \nit's better to take a different way. E.g. dropping the requirement to \nhandle NUL chars and basing it on fgets as Junio suggested in his reply \nto patch 3 sounds good.\n\nIn any case, the packed refs file seems special enough to receive \nspecial treatment. Using mmap would make the most sense if we could \nalso avoid copying lines to a strbuf for parsing, though.\n\nRené\n"},{"id":"259040","messageId":"5521BF95.4030207@web.de","threadId":"39005","inReplyTo":"20150405185911.GA19902@peff.net","subject":"Re: [PATCH 0/6] address packed-refs speed regressions","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2015-04-05T23:04:53Z","receivedAt":"2015-04-05T23:04:53Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 05.04.2015 um 20:59 schrieb Jeff King:\n> Still, the numbers are promising. Here's are comparisons\n> against for-each-ref on torvalds/linux, which has a 218M\n> packed-refs file:\n>\n> $ time git for-each-ref \\\n> --format='%(objectname) %(refname)' \\\n> refs/remotes/2325298/ |\n> wc -c\n> 44139\n>\n> real 0m1.649s\n> user 0m1.332s\n> sys 0m0.304s\n>\n> $ time ~peff/git-quick-list refs/remotes/2325298/ | wc -c\n> 44139\n>\n> real 0m0.012s\n> user 0m0.004s\n> sys 0m0.004s\n\nSweet numbers. :-P\n\nI'm not familiar with refs.c, but its sheer size alone suggests that it \nwon't be easy to integrate this prototype code there. :-/\n\nRené\n"},{"id":"259042","messageId":"CAPig+cTK5MJLfwETFfM1Zdw35M2geKKmA6Q9M0kHdMP9t8qLNg@mail.gmail.com","threadId":"39005","inReplyTo":"20150405011127.GD30127@peff.net","subject":"Re: [PATCH 4/6] strbuf: add an optimized 1-character strbuf_grow","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2015-04-06T02:13:21Z","receivedAt":"2015-04-06T02:13:21Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Sat, Apr 4, 2015 at 9:11 PM, Jeff King wrote:\n> We have to call strbuf_grow anytime we are going to add data\n> to a strbuf. In most cases, it's a noop (since we grow the\n> buffer aggressively), and the cost of the function call and\n> size check is dwarfed by the actual buffer operation.\n>\n> For a tight loop of single-character additions, though, this\n> overhead is noticeable. Furthermore, the single-character\n> case is much easier to check; since the \"extra\" parameter is\n> 1, we can do it without worrying about overflow.\n>\n> This patch adds a simple inline function for checking\n> single-character growth. For the growth case, it just calls\n> into the regular strbuf_grow(). This is redundant, as\n> strbuf_grow will check again whether we need to grow. But it\n> keeps our inline code simple, and most calls will not need\n> to grow, so it's OK to treat this as a rare \"slow path\".\n>\n> We apply the new function to strbuf_getwholeline. [...]\n>\n> Signed-off-by: Jeff King \n> ---\n> diff --git a/strbuf.c b/strbuf.c\n> index af2bad4..2facd5f 100644\n> --- a/strbuf.c\n> +++ b/strbuf.c\n> @@ -445,7 +445,7 @@ int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n> strbuf_reset(sb);\n> flockfile(fp);\n> while ((ch = getc_unlocked(fp)) != EOF) {\n> - strbuf_grow(sb, 1);\n> + strbuf_grow_ch(sb);\n\nstrbuf_grow_ch() seems overly special-case. What about instead taking\nadvantage of inline strbuf_avail() to do something like this?\n\n if (!strbuf_avail())\n strbuf_grow(sb, 1);\n\n(Minor tangent: The 1 is still slightly magical and potentially\nconfusing for someone who doesn't know that the buffer is grown\naggressively, so changing it to a larger number might make it more\nobvious to the casual reader that the buffer is in fact not being\ngrown on every iteration.)\n\n> sb->buf[sb->len++] = ch;\n> if (ch == term)\n> break;\n> diff --git a/strbuf.h b/strbuf.h\n> index 1883494..ef41151 100644\n> --- a/strbuf.h\n> +++ b/strbuf.h\n> @@ -137,6 +137,15 @@ static inline size_t strbuf_avail(const struct strbuf *sb)\n> */\n> extern void strbuf_grow(struct strbuf *, size_t);\n>\n> +/*\n> + * An optimized version of strbuf_grow() for a single character.\n> + */\n> +static inline void strbuf_grow_ch(struct strbuf *sb)\n> +{\n> + if (!sb->alloc || sb->alloc - 1 <= sb->len)\n> + strbuf_grow(sb, 1);\n> +}\n> +\n> /**\n> * Set the length of the buffer to a given value. This function does *not*\n> * allocate new memory, so you should not perform a `strbuf_setlen()` to a\n> --\n> 2.4.0.rc0.363.gf9f328b\n"},{"id":"259050","messageId":"20150406044907.GA1932@peff.net","threadId":"39005","inReplyTo":"5521B993.1080202@web.de","subject":"Re: [PATCH 0/6] address packed-refs speed regressions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-06T04:49:07Z","receivedAt":"2015-04-06T04:49:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Apr 06, 2015 at 12:39:15AM +0200, René Scharfe wrote:\n\n> >...this. I think that effort might be better spent on a ref storage\n> >format that's more efficient, simpler (with respect to subtle races and\n> >such), and could provide other features (e.g., transactional atomicity).\n> \n> Such as a DBMS? :-) Leaving storage details to SQLite or whatever sounds\n> attractive to me because I'm lazy.\n\nExactly. Though I think some folks were worried about the extra\ndependency (e.g., I think SQLite is hard for JGit, because there's no\npure-java implementation, which makes Eclipse unhappy).\n\nWith pluggable backends we can make something like a SQLite backend\noptional. I.e., use it if you want the benefits and can accept the\nportability downsides. But that also risks fracturing the community, and\npeople on the \"old\" format being left behind.\n\n> Forgot to say: I like your changes. But if strbuf_getline can only be made\n> fast enough beyond that by duplicating stdio buffering then I feel it's\n> better to take a different way. E.g. dropping the requirement to handle NUL\n> chars and basing it on fgets as Junio suggested in his reply to patch 3\n> sounds good.\n\nYeah, though we probably need to either audit the callers, or provide a\nflag for each caller to turn on the speed-over-NULs behavior. I'll look\ninto that, but it may not be this week, as I'll be traveling starting\ntomorrow.\n\n> In any case, the packed refs file seems special enough to receive special\n> treatment. Using mmap would make the most sense if we could also avoid\n> copying lines to a strbuf for parsing, though.\n\nI had a similar thought. Below is hacky patch, on top of your mmap\npatch, that does this. It does shave off another 300ms (around 5%).\n\nI think we may be getting into a useless area of micro-optimizing here,\nthough. The results are noticeable on this ridiculous repository, but\nprobably not so much on real ones. The low-hanging fruit (e.g., dropping\ntime in half by using getc_unlocked) seems to provide the most bang for\nthe buck.\n\n---\ndiff --git a/refs.c b/refs.c\nindex 144255f..708b49b 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -334,27 +334,40 @@ static int refname_is_safe(const char *refname)\n \treturn 1;\n }\n \n-static struct ref_entry *create_ref_entry(const char *refname,\n-\t\t\t\t\t const unsigned char *sha1, int flag,\n-\t\t\t\t\t int check_name)\n+static struct ref_entry *create_ref_entry_len(const char *refname, size_t len,\n+\t\t\t\t\t const unsigned char *sha1, int flag,\n+\t\t\t\t\t int check_name)\n {\n-\tint len;\n \tstruct ref_entry *ref;\n \n+\t/*\n+\t * allocate before checking, since the check functions require\n+\t * a NUL-terminated refname. And since we die() anyway if\n+\t * the check fails, the overhead of the extra malloc is negligible\n+\t */\n+\tref = xmalloc(sizeof(struct ref_entry) + len + 1);\n+\thashcpy(ref->u.value.sha1, sha1);\n+\thashclr(ref->u.value.peeled);\n+\tmemcpy(ref->name, refname, len);\n+\tref->name[len] = '\\0';\n+\tref->flag = flag;\n+\n \tif (check_name &&\n \t check_refname_format(refname, REFNAME_ALLOW_ONELEVEL))\n \t\tdie(\"Reference has invalid format: '%s'\", refname);\n \tif (!check_name && !refname_is_safe(refname))\n \t\tdie(\"Reference has invalid name: '%s'\", refname);\n-\tlen = strlen(refname) + 1;\n-\tref = xmalloc(sizeof(struct ref_entry) + len);\n-\thashcpy(ref->u.value.sha1, sha1);\n-\thashclr(ref->u.value.peeled);\n-\tmemcpy(ref->name, refname, len);\n-\tref->flag = flag;\n \treturn ref;\n }\n \n+static struct ref_entry *create_ref_entry(const char *refname,\n+\t\t\t\t\t const unsigned char *sha1, int flag,\n+\t\t\t\t\t int check_name)\n+{\n+\treturn create_ref_entry_len(refname, strlen(refname), sha1, flag,\n+\t\t\t\t check_name);\n+}\n+\n static void clear_ref_dir(struct ref_dir *dir);\n \n static void free_ref_entry(struct ref_entry *entry)\n@@ -1095,7 +1108,9 @@ static const char PACKED_REFS_HEADER[] =\n * Return a pointer to the refname within the line (null-terminated),\n * or NULL if there was a problem.\n */\n-static const char *parse_ref_line(struct strbuf *line, unsigned char *sha1)\n+static const char *parse_ref_line(const char *line, int len,\n+\t\t\t\t unsigned char *sha1,\n+\t\t\t\t size_t *refname_len)\n {\n \tconst char *ref;\n \n@@ -1107,22 +1122,22 @@ static const char *parse_ref_line(struct strbuf *line, unsigned char *sha1)\n \t * +1 (space in between hex and name)\n \t * +1 (newline at the end of the line)\n \t */\n-\tif (line->len <= 42)\n+\tif (len <= 42)\n \t\treturn NULL;\n \n-\tif (get_sha1_hex(line->buf, sha1) < 0)\n+\tif (get_sha1_hex(line, sha1) < 0)\n \t\treturn NULL;\n-\tif (!isspace(line->buf[40]))\n+\tif (!isspace(line[40]))\n \t\treturn NULL;\n \n-\tref = line->buf + 41;\n+\tref = line + 41;\n \tif (isspace(*ref))\n \t\treturn NULL;\n \n-\tif (line->buf[line->len - 1] != '\\n')\n+\tif (line[len - 1] != '\\n')\n \t\treturn NULL;\n-\tline->buf[--line->len] = 0;\n \n+\t*refname_len = len - (ref - line) - 1;\n \treturn ref;\n }\n \n@@ -1156,7 +1171,6 @@ static const char *parse_ref_line(struct strbuf *line, unsigned char *sha1)\n static void read_packed_refs(int fd, struct ref_dir *dir)\n {\n \tstruct ref_entry *last = NULL;\n-\tstruct strbuf line = STRBUF_INIT;\n \tenum { PEELED_NONE, PEELED_TAGS, PEELED_FULLY } peeled = PEELED_NONE;\n \tstruct stat st;\n \tvoid *map;\n@@ -1172,18 +1186,20 @@ static void read_packed_refs(int fd, struct ref_dir *dir)\n \tfor (p = map, len = mapsz; len; ) {\n \t\tunsigned char sha1[20];\n \t\tconst char *refname;\n+\t\tsize_t refname_len;\n \t\tconst char *traits;\n \t\tconst char *nl;\n+\t\tconst char *line;\n \t\tsize_t linelen;\n \n \t\tnl = memchr(p, '\\n', len);\n+\t\tline = p;\n \t\tlinelen = nl ? nl - p + 1 : len;\n-\t\tstrbuf_reset(&line);\n-\t\tstrbuf_add(&line, p, linelen);\n \t\tp += linelen;\n \t\tlen -= linelen;\n \n-\t\tif (skip_prefix(line.buf, \"# pack-refs with:\", &traits)) {\n+\t\t/* XXX these should take care not to look past linelen */\n+\t\tif (skip_prefix(line, \"# pack-refs with:\", &traits)) {\n \t\t\tif (strstr(traits, \" fully-peeled \"))\n \t\t\t\tpeeled = PEELED_FULLY;\n \t\t\telse if (strstr(traits, \" peeled \"))\n@@ -1192,7 +1208,7 @@ static void read_packed_refs(int fd, struct ref_dir *dir)\n \t\t\tcontinue;\n \t\t}\n \n-\t\trefname = parse_ref_line(&line, sha1);\n+\t\trefname = parse_ref_line(line, linelen, sha1, &refname_len);\n \t\tif (refname) {\n \t\t\tint flag = REF_ISPACKED;\n \n@@ -1200,7 +1216,7 @@ static void read_packed_refs(int fd, struct ref_dir *dir)\n \t\t\t\thashclr(sha1);\n \t\t\t\tflag |= REF_BAD_NAME | REF_ISBROKEN;\n \t\t\t}\n-\t\t\tlast = create_ref_entry(refname, sha1, flag, 0);\n+\t\t\tlast = create_ref_entry_len(refname, len, sha1, flag, 0);\n \t\t\tif (peeled == PEELED_FULLY ||\n \t\t\t (peeled == PEELED_TAGS && starts_with(refname, \"refs/tags/\")))\n \t\t\t\tlast->flag |= REF_KNOWS_PEELED;\n@@ -1208,10 +1224,10 @@ static void read_packed_refs(int fd, struct ref_dir *dir)\n \t\t\tcontinue;\n \t\t}\n \t\tif (last &&\n-\t\t line.buf[0] == '^' &&\n-\t\t line.len == PEELED_LINE_LENGTH &&\n-\t\t line.buf[PEELED_LINE_LENGTH - 1] == '\\n' &&\n-\t\t !get_sha1_hex(line.buf + 1, sha1)) {\n+\t\t line[0] == '^' &&\n+\t\t linelen == PEELED_LINE_LENGTH &&\n+\t\t line[PEELED_LINE_LENGTH - 1] == '\\n' &&\n+\t\t !get_sha1_hex(line + 1, sha1)) {\n \t\t\thashcpy(last->u.value.peeled, sha1);\n \t\t\t/*\n \t\t\t * Regardless of what the file header said,\n@@ -1222,7 +1238,6 @@ static void read_packed_refs(int fd, struct ref_dir *dir)\n \t\t}\n \t}\n \n-\tstrbuf_release(&line);\n \tmunmap(map, mapsz);\n }\n \n"},{"id":"259051","messageId":"20150406050544.GB1932@peff.net","threadId":"39005","inReplyTo":"CAPig+cTK5MJLfwETFfM1Zdw35M2geKKmA6Q9M0kHdMP9t8qLNg@mail.gmail.com","subject":"Re: [PATCH 4/6] strbuf: add an optimized 1-character strbuf_grow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-06T05:05:44Z","receivedAt":"2015-04-06T05:05:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Apr 05, 2015 at 10:13:21PM -0400, Eric Sunshine wrote:\n\n> > - strbuf_grow(sb, 1);\n> > + strbuf_grow_ch(sb);\n> \n> strbuf_grow_ch() seems overly special-case. What about instead taking\n> advantage of inline strbuf_avail() to do something like this?\n> \n> if (!strbuf_avail())\n> strbuf_grow(sb, 1);\n\nThanks, I somehow missed that function (despite it being a few line\nabove the one I added!).\n\nI agree that strbuf_avail is a much better generic interface, and it\nturns out to be just as fast (actually, a tiny bit faster in my tests).\nI'll use that in the re-roll.\n\n> (Minor tangent: The 1 is still slightly magical and potentially\n> confusing for someone who doesn't know that the buffer is grown\n> aggressively, so changing it to a larger number might make it more\n> obvious to the casual reader that the buffer is in fact not being\n> grown on every iteration.)\n\nI agree this is slightly confusing (and I had to double-check how\nstrbuf_grow worked while writing this series). OTOH, this is not so much\nabout the \"1\" here as about how strbufs work. We care about the\namortized asymptotic cost. strbuf_add() has the same issue; we add more\nbytes in each chunk, but we would still want to make sure that there is\na sub-linear relationship between the number of adds and the number of\nallocations).\n\n-Peff\n"},{"id":"259128","messageId":"87zj6kjbgu.fsf@rasmusvillemoes.dk","threadId":"39005","inReplyTo":"20150405045614.GA12053@peff.net","subject":"Re: [PATCH 3/6] strbuf_getwholeline: use getc_unlocked","fromName":"Rasmus Villemoes","fromEmail":"rv@rasmusvillemoes.dk","sentAt":"2015-04-07T13:48:33Z","receivedAt":"2015-04-07T13:48:33Z","isPatch":true,"sender":{"key":"rv@rasmusvillemoes.dk","avatar":"https://avatars.githubusercontent.com/u/4375908?v=4"},"body":"On Sun, Apr 05 2015, Jeff King wrote:\n\n> which is back to the v2.0.0 number. Even with the extra strlen, it seems\n> that what fgets does internally beats repeated getc calls. Which I guess\n> is not too surprising, as each getc() will have to check for underflow\n> in the buffer. Perhaps there is more room to micro-optimize\n> strbuf_getwholeline, but I kind of doubt it.\n>\n> The big downside is that our input strings are no longer NUL-clean\n> (reading \"foo\\0bar\\n\" would yield just \"foo\". I doubt that matters in\n> the real world, but it does fail a few of the tests (e.g., t7008 tries\n> to read a list of patterns which includes NUL, and we silently truncate\n> the pattern rather than read in the NUL and barf).\n>\n> So we'd have to either:\n>\n> 1. Decide that doesn't matter.\n>\n> 2. Have callers specify a \"damn the NULs, I want it fast\" flag.\n>\n> 3. Find some alternative that is more robust than fgets, and faster\n> than getc. I don't think there is anything in stdio, but I am not\n> above dropping in a faster non-portable call if it is available,\n> and then falling back to the current code otherwise.\n\ngetdelim is in POSIX 2008\n(http://pubs.opengroup.org/stage7tc1/functions/getdelim.html), so should\nbe available on any half-{d,r}ecent platform. It obviously has the\nadvantage of having access to the internal stdio buffer, and by\ndefinition handles embedded NULs. No idea if using such modern\ninterfaces in git is ok, though. \n\nImplementation-wise, I think strbuf_getwholeline could be implemented\nmostly as a simple wrapper for getdelim. If I'm reading the current code\nand the posix spec for getdelim correctly, something like this should do\nit (though obviously not meant to be included as-is):\n\ndiff --git a/strbuf.c b/strbuf.c\nindex 0346e74..d3338b9 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -434,6 +434,32 @@ int strbuf_getcwd(struct strbuf *sb)\n \treturn -1;\n }\n \n+#if USE_GETDELIM\n+/* Hacky declaration to avoid messing with feature test macros. */\n+ssize_t getdelim(char **, size_t *, int, FILE *);\n+int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n+{\n+\tssize_t r;\n+\n+\tif (feof(fp))\n+\t\treturn EOF;\n+\n+\tstrbuf_reset(sb);\n+\tif (!sb->alloc)\n+\t\tsb->buf = NULL;\n+\n+\tr = getdelim(&sb->buf, &sb->alloc, term, fp);\n+\n+\tif (r > 0) {\n+\t\tsb->len = r;\n+\t\treturn 0;\n+\t}\n+\tassert(r == -1);\n+\tif (!sb->buf)\n+\t\tstrbuf_init(sb);\n+\treturn EOF;\n+}\n+#else\n int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n {\n \tint ch;\n@@ -454,6 +480,7 @@ int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n \tsb->buf[sb->len] = '\\0';\n \treturn 0;\n }\n+#endif\n \n int strbuf_getline(struct strbuf *sb, FILE *fp, int term)\n {\n\n\nRasmus\n"},{"id":"259146","messageId":"20150407190413.GB2553@peff.net","threadId":"39005","inReplyTo":"87zj6kjbgu.fsf@rasmusvillemoes.dk","subject":"Re: [PATCH 3/6] strbuf_getwholeline: use getc_unlocked","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-07T19:04:14Z","receivedAt":"2015-04-07T19:04:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 07, 2015 at 03:48:33PM +0200, Rasmus Villemoes wrote:\n\n> > 3. Find some alternative that is more robust than fgets, and faster\n> > than getc. I don't think there is anything in stdio, but I am not\n> > above dropping in a faster non-portable call if it is available,\n> > and then falling back to the current code otherwise.\n> \n> getdelim is in POSIX 2008\n> (http://pubs.opengroup.org/stage7tc1/functions/getdelim.html), so should\n> be available on any half-{d,r}ecent platform. It obviously has the\n> advantage of having access to the internal stdio buffer, and by\n> definition handles embedded NULs. No idea if using such modern\n> interfaces in git is ok, though.\n\nThanks, that's perfect. I knew about getline(), but not getdelim(), and\nI had thought getline() unconditionally malloc'd. But it doesn't; it\nbehaves exactly as we are already doing here. :-/\n\n> Implementation-wise, I think strbuf_getwholeline could be implemented\n> mostly as a simple wrapper for getdelim. If I'm reading the current code\n> and the posix spec for getdelim correctly, something like this should do\n> it (though obviously not meant to be included as-is):\n\nI think it's close to what we want. strbuf_grow calls xrealloc, which\nwill call try_to_free_routine() and possibly die() for us. So we would\nprobably want to check errno on failure and respond similarly if we get\nENOMEM.\n\nYour patch performs even faster than my fgets version (about 8%).\n\nI wonder if it is even worth doing the getc_unlocked dance at all. It\nwould potentially speed up the fallback code, but my hope that would be\nthat most systems would simply use the getdelim() version.\n\n-Peff\n"},{"id":"259158","messageId":"87k2xn8sqq.fsf@rasmusvillemoes.dk","threadId":"39005","inReplyTo":"20150407190413.GB2553@peff.net","subject":"Re: [PATCH 3/6] strbuf_getwholeline: use getc_unlocked","fromName":"Rasmus Villemoes","fromEmail":"rv@rasmusvillemoes.dk","sentAt":"2015-04-07T22:43:09Z","receivedAt":"2015-04-07T22:43:09Z","isPatch":true,"sender":{"key":"rv@rasmusvillemoes.dk","avatar":"https://avatars.githubusercontent.com/u/4375908?v=4"},"body":"On Tue, Apr 07 2015, Jeff King wrote:\n\n> On Tue, Apr 07, 2015 at 03:48:33PM +0200, Rasmus Villemoes wrote:\n>\n>> Implementation-wise, I think strbuf_getwholeline could be implemented\n>> mostly as a simple wrapper for getdelim. If I'm reading the current code\n>> and the posix spec for getdelim correctly, something like this should do\n>> it (though obviously not meant to be included as-is):\n>\n> I think it's close to what we want. strbuf_grow calls xrealloc, which\n> will call try_to_free_routine() and possibly die() for us. So we would\n> probably want to check errno on failure and respond similarly if we get\n> ENOMEM.\n\nHm, I'm afraid it's not that simple. It seems that data may be lost from\nthe stream if getdelim encounters ENOMEM: Looking at the glibc\nimplementation (libio/iogetdelim.c), if reallocating the user buffer\nfails, -1 is returned (presumably with errno==ENOMEM set by realloc), and\nthere's no way of knowing how many bytes were already copied to the\nbuffer (cur_len).\n\nFor regular files, I suppose one could do a ftell/fseek dance. For\nother cases, I don't see a reliable way to retry upon ENOMEM.\n\nRelated thread on the posix mailing list:\nhttp://thread.gmane.org/gmane.comp.standards.posix.austin.general/10091\n\n> I wonder if it is even worth doing the getc_unlocked dance at all. It\n> would potentially speed up the fallback code, but my hope that would be\n> that most systems would simply use the getdelim() version.\n\nWell, it's not really an intrusive patch, and 42% speedup is rather\nsignificant. And, of course, the above ENOMEM issue may mean that\ngetdelim isn't usable after all.\n\nRasmus\n"},{"id":"259159","messageId":"20150408001712.GA16798@peff.net","threadId":"39005","inReplyTo":"87k2xn8sqq.fsf@rasmusvillemoes.dk","subject":"Re: [PATCH 3/6] strbuf_getwholeline: use getc_unlocked","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-08T00:17:13Z","receivedAt":"2015-04-08T00:17:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Apr 08, 2015 at 12:43:09AM +0200, Rasmus Villemoes wrote:\n\n> Hm, I'm afraid it's not that simple. It seems that data may be lost from\n> the stream if getdelim encounters ENOMEM: Looking at the glibc\n> implementation (libio/iogetdelim.c), if reallocating the user buffer\n> fails, -1 is returned (presumably with errno==ENOMEM set by realloc), and\n> there's no way of knowing how many bytes were already copied to the\n> buffer (cur_len).\n> \n> For regular files, I suppose one could do a ftell/fseek dance. For\n> other cases, I don't see a reliable way to retry upon ENOMEM.\n\nAh, right, that makes sense.\n\nI think it may be OK to just `die()` on ENOMEM here. The \"try to free\"\nroutine is basically about unmapping pack memory, in case it is clogging\nup the address space (it is mmap'd, so it shouldn't cause real RAM\npressure; the OS can just drop the pages from the cache if it wants).\n\nBut getdelim() calls are not likely to be big allocations in the first\nplace (so they are not likely to fail at all, and if they do, we really\nare horribly out of memory). I'd also question whether\nrelease_pack_memory is doing anything in practice on 64-bit machines. We\nhave quite a bit of address space to work with in that case.\n\n-Peff\n"},{"id":"259468","messageId":"20150416084733.GA17811@peff.net","threadId":"39005","inReplyTo":"20150405010611.GA15901@peff.net","subject":"[PATCH v2 0/9] address packed-refs speed regressions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-16T08:47:34Z","receivedAt":"2015-04-16T08:47:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Apr 04, 2015 at 09:06:11PM -0400, Jeff King wrote:\n\n> As I've mentioned before, I have some repositories with rather large\n> numbers of refs. The worst one has ~13 million refs, for a 1.6GB\n> packed-refs file. So I was saddened by this:\n> \n> $ time git.v2.0.0 rev-parse refs/heads/foo >/dev/null 2>&1\n> real 0m6.840s\n> user 0m6.404s\n> sys 0m0.440s\n> \n> $ time git.v2.4.0-rc1 rev-parse refs/heads/foo >/dev/null 2>&1\n> real 0m19.432s\n> user 0m18.996s\n> sys 0m0.456s\n\nHere's a re-roll incorporating feedback from the list. Thanks everybody\nfor your comments. Last time the final number was ~8.5s, which was\ndisappointingly slower than v2.0.0. In this iteration, my final numbers\nare:\n\n real 0m5.703s\n user 0m5.276s\n sys 0m0.432s\n\nwhich is quite pleasing.\n\nThe big changes that resulted in this additional speedup are:\n\n 1. Use getdelim() when it is available. This is much faster than even\n a getc_unlocked() loop.\n\n 2. The slowdown from d0f810f was from adding in refname_is_safe calls.\n But what I didn't notice before is that we run them in _addition_\n to check_refname_format, rather than instead of it. So in the\n common case of a sanely-formatted refname, we can skip the call,\n rather than writing a lot of code to micro-optimize it.\n\nIt was also mentioned in a nearby thread that the config code could\nbenefit from some of the same micro-optimizations. It can't make use of\ngetdelim(), as it really does want to do character-by-character parsing.\nBut it can still use getc_unlocked() and the strbuf_avail() trick, which\nspeeds up config reading by 47%. Those patches are included here.\n\n [1/9]: strbuf_getwholeline: use getc macro\n [2/9]: git-compat-util: add fallbacks for unlocked stdio\n [3/9]: strbuf_getwholeline: use getc_unlocked\n [4/9]: config: use getc_unlocked when reading from file\n [5/9]: strbuf_addch: avoid calling strbuf_grow\n [6/9]: strbuf_getwholeline: avoid calling strbuf_grow\n [7/9]: strbuf_getwholeline: use getdelim if it is available\n [8/9]: read_packed_refs: avoid double-checking sane refs\n [9/9]: t1430: add another refs-escape test\n\n-Peff\n"},{"id":"259469","messageId":"20150416084822.GA17938@peff.net","threadId":"39005","inReplyTo":"20150416084733.GA17811@peff.net","subject":"[PATCH 1/9] strbuf_getwholeline: use getc macro","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-16T08:48:23Z","receivedAt":"2015-04-16T08:48:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"strbuf_getwholeline calls fgetc in a tight loop. Using the\ngetc form, which can be implemented as a macro, should be\nfaster (and we do not care about it evaluating our argument\ntwice, as we just have a plain variable).\n\nOn my glibc system, running \"git rev-parse\nrefs/heads/does-not-exist\" on a file with an extremely large\n(1.6GB) packed-refs file went from (best of 3 runs):\n\n real 0m19.383s\n user 0m18.876s\n sys 0m0.528s\n\nto:\n\n real 0m18.900s\n user 0m18.472s\n sys 0m0.448s\n\nfor a wall-clock speedup of 2.5%.\n\nSigned-off-by: Jeff King \n---\n strbuf.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/strbuf.c b/strbuf.c\nindex 88cafd4..14f337d 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -443,7 +443,7 @@ int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n \t\treturn EOF;\n \n \tstrbuf_reset(sb);\n-\twhile ((ch = fgetc(fp)) != EOF) {\n+\twhile ((ch = getc(fp)) != EOF) {\n \t\tstrbuf_grow(sb, 1);\n \t\tsb->buf[sb->len++] = ch;\n \t\tif (ch == term)\n-- \n2.4.0.rc2.384.g7297a4a\n"},{"id":"259470","messageId":"20150416084844.GB17938@peff.net","threadId":"39005","inReplyTo":"20150416084733.GA17811@peff.net","subject":"[PATCH 2/9] git-compat-util: add fallbacks for unlocked stdio","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-16T08:48:45Z","receivedAt":"2015-04-16T08:48:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"POSIX.1-2001 specifies some functions for optimizing the\nlocking out of tight getc() loops. Not all systems are\nPOSIX, though, and even not all POSIX systems are required\nto implement these functions. We can check for the\nfeature-test macro to see if they are available, and if not,\nprovide a noop implementation.\n\nThere's no Makefile knob here, because we should just detect\nthis automatically. If there are very bizarre systems, we\nmay need to add one, but it's not clear yet in which\ndirection:\n\n 1. If a system defines _POSIX_THREAD_SAFE_FUNCTIONS but\n these functions are missing or broken, we would want a\n knob to manually turn them off.\n\n 2. If a system has these functions but does not define\n _POSIX_THREAD_SAFE_FUNCTIONS, we would want a knob to\n manually turn them on.\n\nWe can add such a knob when we find a real-world system that\nmatches this.\n\nSigned-off-by: Jeff King \n---\n git-compat-util.h | 6 ++++++\n 1 file changed, 6 insertions(+)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex bc8fc8c..685a0a4 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -883,4 +883,10 @@ struct tm *git_gmtime_r(const time_t *, struct tm *);\n # define SHELL_PATH \"/bin/sh\"\n #endif\n \n+#ifndef _POSIX_THREAD_SAFE_FUNCTIONS\n+#define flockfile(fh)\n+#define funlockfile(fh)\n+#define getc_unlocked(fh) getc(fh)\n+#endif\n+\n #endif\n-- \n2.4.0.rc2.384.g7297a4a\n"},{"id":"259471","messageId":"20150416084906.GC17938@peff.net","threadId":"39005","inReplyTo":"20150416084733.GA17811@peff.net","subject":"[PATCH 3/9] strbuf_getwholeline: use getc_unlocked","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-16T08:49:06Z","receivedAt":"2015-04-16T08:49:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"strbuf_getwholeline calls getc in a tight loop. On modern\nlibc implementations, the stdio code locks the handle for\nevery operation, which means we are paying a significant\noverhead. We can get around this by locking the handle for\nthe whole loop and using the unlocked variant.\n\nRunning \"git rev-parse refs/heads/does-not-exist\" on a repo\nwith an extremely large (1.6GB) packed-refs file went from:\n\n real 0m18.900s\n user 0m18.472s\n sys 0m0.448s\n\nto:\n\n real 0m10.953s\n user 0m10.384s\n sys 0m0.580s\n\nfor a wall-clock speedup of 42%. All times are best-of-3,\nand done on a glibc 2.19 system.\n\nNote that we call into strbuf_grow while holding the lock.\nIt's possible for that function to call other stdio\nfunctions (e.g., printing to stderr when dying due to malloc\nerror); however, the POSIX.1-2001 definition of flockfile\nmakes it clear that the locks are per-handle, so we are fine\nunless somebody else tries to read from our same handle.\nThis doesn't ever happen in the current code, and is\nunlikely to be added in the future (we would have to do\nsomething exotic like add a die_routine that tried to read\nfrom stdin).\n\nSigned-off-by: Jeff King \n---\n strbuf.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/strbuf.c b/strbuf.c\nindex 14f337d..af2bad4 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -443,12 +443,14 @@ int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n \t\treturn EOF;\n \n \tstrbuf_reset(sb);\n-\twhile ((ch = getc(fp)) != EOF) {\n+\tflockfile(fp);\n+\twhile ((ch = getc_unlocked(fp)) != EOF) {\n \t\tstrbuf_grow(sb, 1);\n \t\tsb->buf[sb->len++] = ch;\n \t\tif (ch == term)\n \t\t\tbreak;\n \t}\n+\tfunlockfile(fp);\n \tif (ch == EOF && sb->len == 0)\n \t\treturn EOF;\n \n-- \n2.4.0.rc2.384.g7297a4a\n"},{"id":"259472","messageId":"20150416085118.GD17938@peff.net","threadId":"39005","inReplyTo":"20150416084733.GA17811@peff.net","subject":"[PATCH 4/9] config: use getc_unlocked when reading from file","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-16T08:51:18Z","receivedAt":"2015-04-16T08:51:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We read config files character-by-character from a stdio\nhandle using fgetc(). This incurs significant locking\noverhead, even though we know that only one thread can\npossibly access the handle. We can speed this up by taking\nthe lock ourselves, and then using getc_unlocked to read\neach character.\n\nOn a silly pathological case:\n\n perl -le '\n print \"[core]\";\n print \"key$_ = value$_\" for (1..1000000)\n ' >input\n git config -f input core.key1\n\nthis dropped the time to run git-config from:\n\n real 0m0.263s\n user 0m0.260s\n sys 0m0.000s\n\nto:\n\n real 0m0.159s\n user 0m0.152s\n sys 0m0.004s\n\nfor a savings of 39%. Most config files are not this big,\nbut the savings should be proportional to the size of the\nfile (i.e., we always save 39%, just of a much smaller\nnumber).\n\nSigned-off-by: Jeff King \n---\n config.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/config.c b/config.c\nindex 66c0a51..8b297fc 100644\n--- a/config.c\n+++ b/config.c\n@@ -49,7 +49,7 @@ static struct config_set the_config_set;\n \n static int config_file_fgetc(struct config_source *conf)\n {\n-\treturn fgetc(conf->u.file);\n+\treturn getc_unlocked(conf->u.file);\n }\n \n static int config_file_ungetc(int c, struct config_source *conf)\n@@ -1088,7 +1088,9 @@ int git_config_from_file(config_fn_t fn, const char *filename, void *data)\n \n \tf = fopen(filename, \"r\");\n \tif (f) {\n+\t\tflockfile(f);\n \t\tret = do_config_from_file(fn, filename, filename, f, data);\n+\t\tfunlockfile(f);\n \t\tfclose(f);\n \t}\n \treturn ret;\n-- \n2.4.0.rc2.384.g7297a4a\n"},{"id":"259473","messageId":"20150416085356.GE17938@peff.net","threadId":"39005","inReplyTo":"20150416084733.GA17811@peff.net","subject":"[PATCH 5/9] strbuf_addch: avoid calling strbuf_grow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-16T08:53:56Z","receivedAt":"2015-04-16T08:53:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We mark strbuf_addch as inline, because we expect it may be\ncalled from a tight loop. However, the first thing it does\nis call the non-inline strbuf_grow(), which can handle\narbitrary-sized growth. Since we know that we only need a\nsingle character, we can use the inline strbuf_avail() to\nquickly check whether we need to grow at all.\n\nOur check is redundant when we do call strbuf_grow(), but\nthat's OK. The common case is that we avoid calling it at\nall, and we have made that case faster.\n\nOn a silly pathological case:\n\n perl -le '\n print \"[core]\";\n print \"key$_ = value$_\" for (1..1000000)\n ' >input\n git config -f input core.key1\n\nthis dropped the time to run git-config from:\n\n real 0m0.159s\n user 0m0.152s\n sys 0m0.004s\n\nto:\n\n real 0m0.140s\n user 0m0.136s\n sys 0m0.004s\n\nfor a savings of 12%.\n\nSigned-off-by: Jeff King \n---\nI doubt anybody will really notice this in practice with config files,\nand for the most part we do not have tight loops of strbuf_addch\nelsewhere. But it is such an easy optimization, I'd rather do it now\nwhile we're thinking about it.\n\n strbuf.h | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/strbuf.h b/strbuf.h\nindex 1883494..01c5c63 100644\n--- a/strbuf.h\n+++ b/strbuf.h\n@@ -205,7 +205,8 @@ extern int strbuf_cmp(const struct strbuf *, const struct strbuf *);\n */\n static inline void strbuf_addch(struct strbuf *sb, int c)\n {\n-\tstrbuf_grow(sb, 1);\n+\tif (!strbuf_avail(sb))\n+\t\tstrbuf_grow(sb, 1);\n \tsb->buf[sb->len++] = c;\n \tsb->buf[sb->len] = '\\0';\n }\n-- \n2.4.0.rc2.384.g7297a4a\n"},{"id":"259474","messageId":"20150416085854.GF17938@peff.net","threadId":"39005","inReplyTo":"20150416084733.GA17811@peff.net","subject":"[PATCH 6/9] strbuf_getwholeline: avoid calling strbuf_grow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-16T08:58:54Z","receivedAt":"2015-04-16T08:58:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"As with the recent speedup to strbuf_addch, we can avoid\ncalling strbuf_grow() in a tight loop of single-character\nadds by instead checking strbuf_avail.\n\nNote that we would instead call strbuf_addch directly here,\nbut it does more work than necessary: it will NUL-terminate\nthe result for each character read. Instead, in this loop we\nread the characters one by one and then add the terminator\nmanually at the end.\n\nRunning \"git rev-parse refs/heads/does-not-exist\" on a repo\nwith an extremely large (1.6GB) packed-refs file went from\n(best-of-5):\n\n real 0m10.948s\n user 0m10.548s\n sys 0m0.412s\n\nto:\n\n real 0m8.601s\n user 0m8.084s\n sys 0m0.524s\n\nfor a wall-clock speedup of 21%.\n\nHelped-by: Eric Sunshine \nSigned-off-by: Jeff King \n---\nOur \"don't write a NUL for each character\" optimization is only possible\nbecause we're intimate with the strbuf details here. I thought about\nmaking a strbuf_addch_unsafe interface to let other callers do this,\ntoo. But the only other caller that would use it is the config reader,\nand I measured only a 3% speedup there. Which I don't think is worth the\nextra API complexity.\n\nWhereas here it does make a big difference. Switching to strbuf_addch\nknocks us back up into the 9.5s range. I think the difference is that\nour lines are much longer than the tokens we're parsing in the config\nfile. So the percentage of wasted NUL writes is much higher here.\n\n strbuf.c | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/strbuf.c b/strbuf.c\nindex af2bad4..921619e 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -445,7 +445,8 @@ int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n \tstrbuf_reset(sb);\n \tflockfile(fp);\n \twhile ((ch = getc_unlocked(fp)) != EOF) {\n-\t\tstrbuf_grow(sb, 1);\n+\t\tif (!strbuf_avail(sb))\n+\t\t\tstrbuf_grow(sb, 1);\n \t\tsb->buf[sb->len++] = ch;\n \t\tif (ch == term)\n \t\t\tbreak;\n-- \n2.4.0.rc2.384.g7297a4a\n"},{"id":"259475","messageId":"20150416090138.GG17938@peff.net","threadId":"39005","inReplyTo":"20150416084733.GA17811@peff.net","subject":"[PATCH 7/9] strbuf_getwholeline: use getdelim if it is available","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-16T09:01:38Z","receivedAt":"2015-04-16T09:01:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We spend a lot of time in strbuf_getwholeline in a tight\nloop reading characters from a stdio handle into a buffer.\nThe libc getdelim() function can do this for us with less\noverhead. It's in POSIX.1-2008, and was a GNU extension\nbefore that. Therefore we can't rely on it, but can fall\nback to the existing getc loop when it is not available.\n\nThe HAVE_GETDELIM knob is turned on automatically for Linux,\nwhere we have glibc. We don't need to set any new\nfeature-test macros, because we already define _GNU_SOURCE.\nOther systems that implement getdelim may need to other\nmacros (probably _POSIX_C_SOURCE >= 200809L), but we can\naddress that along with setting the Makefile knob after\ntesting the feature on those systems.\n\nRunning \"git rev-parse refs/heads/does-not-exist\" on a repo\nwith an extremely large (1.6GB) packed-refs file went from\n(best-of-5):\n\n real 0m8.601s\n user 0m8.084s\n sys 0m0.524s\n\nto:\n\n real 0m6.768s\n user 0m6.340s\n sys 0m0.432s\n\nfor a wall-clock speedup of 21%.\n\nBased on a patch from Rasmus Villemoes .\n\nSigned-off-by: Jeff King \n---\nIf somebody has a FreeBSD or OS X system to test on, I'd\nlove to see what is needed to compile with HAVE_GETDELIM\nthere. And to confirm that the performance is much better.\nSharing my 1.6GB packed-refs file would be hard, but you\nshould be able to generate something large and ridiculous.\nI'll leave that as an exercise to the reader.\n\n Makefile | 6 ++++++\n config.mak.uname | 1 +\n strbuf.c | 42 ++++++++++++++++++++++++++++++++++++++++++\n 3 files changed, 49 insertions(+)\n\ndiff --git a/Makefile b/Makefile\nindex 5f3987f..36655d5 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -359,6 +359,8 @@ all::\n # compiler is detected to support it.\n #\n # Define HAVE_BSD_SYSCTL if your platform has a BSD-compatible sysctl function.\n+#\n+# Define HAVE_GETDELIM if your system has the getdelim() function.\n \n GIT-VERSION-FILE: FORCE\n \t@$(SHELL_PATH) ./GIT-VERSION-GEN\n@@ -1437,6 +1439,10 @@ ifdef HAVE_BSD_SYSCTL\n \tBASIC_CFLAGS += -DHAVE_BSD_SYSCTL\n endif\n \n+ifdef HAVE_GETDELIM\n+\tBASIC_CFLAGS += -DHAVE_GETDELIM\n+endif\n+\n ifeq ($(TCLTK_PATH),)\n NO_TCLTK = NoThanks\n endif\ndiff --git a/config.mak.uname b/config.mak.uname\nindex f4e77cb..d26665f 100644\n--- a/config.mak.uname\n+++ b/config.mak.uname\n@@ -36,6 +36,7 @@ ifeq ($(uname_S),Linux)\n \tHAVE_DEV_TTY = YesPlease\n \tHAVE_CLOCK_GETTIME = YesPlease\n \tHAVE_CLOCK_MONOTONIC = YesPlease\n+\tHAVE_GETDELIM = YesPlease\n endif\n ifeq ($(uname_S),GNU/kFreeBSD)\n \tHAVE_ALLOCA_H = YesPlease\ndiff --git a/strbuf.c b/strbuf.c\nindex 921619e..0d4f4e5 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -435,6 +435,47 @@ int strbuf_getcwd(struct strbuf *sb)\n \treturn -1;\n }\n \n+#ifdef HAVE_GETDELIM\n+int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n+{\n+\tssize_t r;\n+\n+\tif (feof(fp))\n+\t\treturn EOF;\n+\n+\tstrbuf_reset(sb);\n+\n+\t/* Translate slopbuf to NULL, as we cannot call realloc on it */\n+\tif (!sb->alloc)\n+\t\tsb->buf = NULL;\n+\tr = getdelim(&sb->buf, &sb->alloc, term, fp);\n+\n+\tif (r > 0) {\n+\t\tsb->len = r;\n+\t\treturn 0;\n+\t}\n+\tassert(r == -1);\n+\n+\t/*\n+\t * Normally we would have called xrealloc, which will try to free\n+\t * memory and recover. But we have no way to tell getdelim() to do so.\n+\t * Worse, we cannot try to recover ENOMEM ourselves, because we have\n+\t * no idea how many bytes were read by getdelim.\n+\t *\n+\t * Dying here is reasonable. It mirrors what xrealloc would do on\n+\t * catastrophic memory failure. We skip the opportunity to free pack\n+\t * memory and retry, but that's unlikely to help for a malloc small\n+\t * enough to hold a single line of input, anyway.\n+\t */\n+\tif (errno == ENOMEM)\n+\t\tdie(\"Out of memory, getdelim failed\");\n+\n+\t/* Restore slopbuf that we moved out of the way before */\n+\tif (!sb->buf)\n+\t\tstrbuf_init(sb, 0);\n+\treturn EOF;\n+}\n+#else\n int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n {\n \tint ch;\n@@ -458,6 +499,7 @@ int strbuf_getwholeline(struct strbuf *sb, FILE *fp, int term)\n \tsb->buf[sb->len] = '\\0';\n \treturn 0;\n }\n+#endif\n \n int strbuf_getline(struct strbuf *sb, FILE *fp, int term)\n {\n-- \n2.4.0.rc2.384.g7297a4a\n"},{"id":"259476","messageId":"20150416090326.GH17938@peff.net","threadId":"39005","inReplyTo":"20150416084733.GA17811@peff.net","subject":"[PATCH 8/9] read_packed_refs: avoid double-checking sane refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-16T09:03:26Z","receivedAt":"2015-04-16T09:03:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Prior to d0f810f (refs.c: allow listing and deleting badly\nnamed refs, 2014-09-03), read_packed_refs would barf on any\nmalformed refnames by virtue of calling create_ref_entry\nwith the \"check\" parameter set to 1. That commit loosened\nour reading so that we call check_refname_format ourselves\nand just set a REF_BAD_NAME flag.\n\nWe then call create_ref_entry with the check parameter set\nto 0. That function learned to do an extra safety check even\nwhen the check parameter is 0, so that we don't load any\ndangerous refnames (like \"../../../etc/passwd\"). This is\nimplemented by calling refname_is_safe() in\ncreate_ref_entry().\n\nHowever, we can observe that refname_is_safe() can only be\ntrue if check_refname_format() also failed. So in the common\ncase of a sanely named ref, we perform _both_ checks, even\nthough we know that the latter will never trigger. This has\na noticeable performance impact when the packed-refs file is\nlarge.\n\nLet's drop the refname_is_safe check from create_ref_entry(),\nand make it the responsibility of the caller. Of the three\ncallers that pass a check parameter of \"0\", two will have\njust called check_refname_format(), and can check the\nrefname-safety only when it fails. The third case,\npack_if_possible_fn, is copying from an existing ref entry,\nwhich must have previously passed our safety check.\n\nWith this patch, running \"git rev-parse refs/heads/does-not-exist\"\non a repo with a large (1.6GB) packed-refs file went from:\n\n real 0m6.768s\n user 0m6.340s\n sys 0m0.432s\n\nto:\n\n real 0m5.703s\n user 0m5.276s\n sys 0m0.432s\n\nfor a wall-clock speedup of 15%.\n\nSigned-off-by: Jeff King \n---\n refs.c | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 47e4e53..f36ea75 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -344,8 +344,6 @@ static struct ref_entry *create_ref_entry(const char *refname,\n \tif (check_name &&\n \t check_refname_format(refname, REFNAME_ALLOW_ONELEVEL))\n \t\tdie(\"Reference has invalid format: '%s'\", refname);\n-\tif (!check_name && !refname_is_safe(refname))\n-\t\tdie(\"Reference has invalid name: '%s'\", refname);\n \tlen = strlen(refname) + 1;\n \tref = xmalloc(sizeof(struct ref_entry) + len);\n \thashcpy(ref->u.value.sha1, sha1);\n@@ -1178,6 +1176,8 @@ static void read_packed_refs(FILE *f, struct ref_dir *dir)\n \t\t\tint flag = REF_ISPACKED;\n \n \t\t\tif (check_refname_format(refname, REFNAME_ALLOW_ONELEVEL)) {\n+\t\t\t\tif (!refname_is_safe(refname))\n+\t\t\t\t\tdie(\"packed refname is dangerous: %s\", refname);\n \t\t\t\thashclr(sha1);\n \t\t\t\tflag |= REF_BAD_NAME | REF_ISBROKEN;\n \t\t\t}\n@@ -1323,6 +1323,8 @@ static void read_loose_refs(const char *dirname, struct ref_dir *dir)\n \t\t\t}\n \t\t\tif (check_refname_format(refname.buf,\n \t\t\t\t\t\t REFNAME_ALLOW_ONELEVEL)) {\n+\t\t\t\tif (!refname_is_safe(refname.buf))\n+\t\t\t\t\tdie(\"loose refname is dangerous: %s\", refname.buf);\n \t\t\t\thashclr(sha1);\n \t\t\t\tflag |= REF_BAD_NAME | REF_ISBROKEN;\n \t\t\t}\n-- \n2.4.0.rc2.384.g7297a4a\n"},{"id":"259477","messageId":"20150416090443.GI17938@peff.net","threadId":"39005","inReplyTo":"20150416084733.GA17811@peff.net","subject":"[PATCH 9/9] t1430: add another refs-escape test","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-16T09:04:44Z","receivedAt":"2015-04-16T09:04:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"In t1430, we check whether deleting the branch \"../../foo\"\nwill delete \".git/foo\". However, this is not that\ninteresting a test; the precious file \".git/foo\" does not\nlook like a ref, so even if we did not notice the \"escape\"\nfrom the \"refs/\" hierarchy, we would fail for that reason\n(i.e., if you turned refname_is_safe into a noop, the test\nstill passes).\n\nLet's add an additional test for the same thing, but with a\nfile that actually looks like a ref. That will make sure we\nare exercising the refname_is_safe code. While we're at it,\nlet's also make the code work a little harder by adding some\nextra paths and some empty path components.\n\nSigned-off-by: Jeff King \n---\nThis was originally included to exercise refname_is_safe(), because in\nthe v1 series I refactored it (here I just avoid calling it entirely).\nSo it's not as important in v2. But AFAICT, we do not exercise\nrefname_is_safe() at all in the test suite without this patch, so it's\nprobably a good thing to do regardless.\n\n t/t1430-bad-ref-name.sh | 8 ++++++++\n 1 file changed, 8 insertions(+)\n\ndiff --git a/t/t1430-bad-ref-name.sh b/t/t1430-bad-ref-name.sh\nindex 468e856..16d0b8b 100755\n--- a/t/t1430-bad-ref-name.sh\n+++ b/t/t1430-bad-ref-name.sh\n@@ -68,6 +68,14 @@ test_expect_success 'branch -D cannot delete non-ref in .git dir' '\n \ttest_cmp expect .git/my-private-file\n '\n \n+test_expect_success 'branch -D cannot delete ref in .git dir' '\n+\tgit rev-parse HEAD >.git/my-private-file &&\n+\tgit rev-parse HEAD >expect &&\n+\tgit branch foo/legit &&\n+\ttest_must_fail git branch -D foo////./././../../../my-private-file &&\n+\ttest_cmp expect .git/my-private-file\n+'\n+\n test_expect_success 'branch -D cannot delete absolute path' '\n \tgit branch -f extra &&\n \ttest_must_fail git branch -D \"$(pwd)/.git/refs/heads/extra\" &&\n-- \n2.4.0.rc2.384.g7297a4a\n"},{"id":"259478","messageId":"20150416092518.GA18135@peff.net","threadId":"39005","inReplyTo":"20150416084733.GA17811@peff.net","subject":"Re: [PATCH v2 0/9] address packed-refs speed regressions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-16T09:25:19Z","receivedAt":"2015-04-16T09:25:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 16, 2015 at 04:47:34AM -0400, Jeff King wrote:\n\n> Here's a re-roll incorporating feedback from the list. Thanks everybody\n> for your comments. Last time the final number was ~8.5s, which was\n> disappointingly slower than v2.0.0. In this iteration, my final numbers\n> are:\n> \n> real 0m5.703s\n> user 0m5.276s\n> sys 0m0.432s\n> \n> which is quite pleasing.\n\nI forgot to mention what I _didn't_ include.\n\nWe discussed using mmap instead of stdio. Applying René's mmap patch\ndrops my best-of-five here to 5.114s. Which is nice, but it is a bit\nmore invasive (and does not help other callers of strbuf_getline).\n\nIf I further apply my really nasty patch to avoid the strbuf entirely\n(i.e., we parse straight out of the mmap), I can get it down to 4.835s.\n\nI don't know if the complexity is worth it or not. Ultimately, I think\nthe best route to making packed-refs faster is to drop the whole\nref_cache structure and just iterate directly over the mmap data. It\nwould use less RAM, and it opens the possibility of binary-searching to\nlook at only a subset of the entries. That's a _lot_ more invasive,\nthough.\n\n-Peff\n"},{"id":"259558","messageId":"CAPig+cSKtMPQGxp1Y2GinVRh2y--QyJh_nxhDez2CGFPP6B=xg@mail.gmail.com","threadId":"39005","inReplyTo":"20150416090138.GG17938@peff.net","subject":"Re: [PATCH 7/9] strbuf_getwholeline: use getdelim if it is available","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2015-04-17T10:16:48Z","receivedAt":"2015-04-17T10:16:48Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Thu, Apr 16, 2015 at 5:01 AM, Jeff King wrote:\n> We spend a lot of time in strbuf_getwholeline in a tight\n> loop reading characters from a stdio handle into a buffer.\n> The libc getdelim() function can do this for us with less\n> overhead. It's in POSIX.1-2008, and was a GNU extension\n> before that. Therefore we can't rely on it, but can fall\n> back to the existing getc loop when it is not available.\n>\n> The HAVE_GETDELIM knob is turned on automatically for Linux,\n> where we have glibc. We don't need to set any new\n> feature-test macros, because we already define _GNU_SOURCE.\n> Other systems that implement getdelim may need to other\n> macros (probably _POSIX_C_SOURCE >= 200809L), but we can\n> address that along with setting the Makefile knob after\n> testing the feature on those systems.\n> [...]\n>\n> Based on a patch from Rasmus Villemoes .\n>\n> Signed-off-by: Jeff King \n> ---\n> If somebody has a FreeBSD or OS X system to test on, I'd\n> love to see what is needed to compile with HAVE_GETDELIM\n> there.\n\nModern Mac OS X, 10.10.x Yosemite, has getdelim() and git builds fine\nwith HAVE_GETDELIM. I also tested on old Snow Leopard 10.5.8 from\n2009. It does not have getdelim(). Unfortunately, I haven't been able\nto determine when getdelim() was introduced on the Mac OS X, thus have\nbeen unable to craft a simple rule for config.mak.uname.\n\n> And to confirm that the performance is much better.\n> Sharing my 1.6GB packed-refs file would be hard, but you\n> should be able to generate something large and ridiculous.\n> I'll leave that as an exercise to the reader.\n>\n> diff --git a/Makefile b/Makefile\n> index 5f3987f..36655d5 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -359,6 +359,8 @@ all::\n> # compiler is detected to support it.\n> #\n> # Define HAVE_BSD_SYSCTL if your platform has a BSD-compatible sysctl function.\n> +#\n> +# Define HAVE_GETDELIM if your system has the getdelim() function.\n>\n> GIT-VERSION-FILE: FORCE\n> @$(SHELL_PATH) ./GIT-VERSION-GEN\n> @@ -1437,6 +1439,10 @@ ifdef HAVE_BSD_SYSCTL\n> BASIC_CFLAGS += -DHAVE_BSD_SYSCTL\n> endif\n>\n> +ifdef HAVE_GETDELIM\n> + BASIC_CFLAGS += -DHAVE_GETDELIM\n> +endif\n> +\n> ifeq ($(TCLTK_PATH),)\n> NO_TCLTK = NoThanks\n> endif\n> diff --git a/config.mak.uname b/config.mak.uname\n> index f4e77cb..d26665f 100644\n> --- a/config.mak.uname\n> +++ b/config.mak.uname\n> @@ -36,6 +36,7 @@ ifeq ($(uname_S),Linux)\n> HAVE_DEV_TTY = YesPlease\n> HAVE_CLOCK_GETTIME = YesPlease\n> HAVE_CLOCK_MONOTONIC = YesPlease\n> + HAVE_GETDELIM = YesPlease\n> endif\n> ifeq ($(uname_S),GNU/kFreeBSD)\n> HAVE_ALLOCA_H = YesPlease\n"},{"id":"259777","messageId":"20150421230929.GA27773@peff.net","threadId":"39005","inReplyTo":"CAPig+cSKtMPQGxp1Y2GinVRh2y--QyJh_nxhDez2CGFPP6B=xg@mail.gmail.com","subject":"Re: [PATCH 7/9] strbuf_getwholeline: use getdelim if it is available","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-21T23:09:29Z","receivedAt":"2015-04-21T23:09:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Apr 17, 2015 at 06:16:48AM -0400, Eric Sunshine wrote:\n\n> > If somebody has a FreeBSD or OS X system to test on, I'd\n> > love to see what is needed to compile with HAVE_GETDELIM\n> > there.\n> \n> Modern Mac OS X, 10.10.x Yosemite, has getdelim() and git builds fine\n> with HAVE_GETDELIM. I also tested on old Snow Leopard 10.5.8 from\n> 2009. It does not have getdelim(). Unfortunately, I haven't been able\n> to determine when getdelim() was introduced on the Mac OS X, thus have\n> been unable to craft a simple rule for config.mak.uname.\n\nThanks for looking into it. Since there haven't been any other takers in\nthe meantime, do you want to prepare a patch that checks $(uname_R) for\n10.10.x? That's likely more conservative than is necessary, but we can\nloosen it later if somebody on 10.9.x shows up with test results.\n\n-Peff\n"},{"id":"259811","messageId":"alpine.DEB.1.00.1504222000040.28561@s15462909.onlinehome-server.info","threadId":"39005","inReplyTo":"CAPig+cSKtMPQGxp1Y2GinVRh2y--QyJh_nxhDez2CGFPP6B=xg@mail.gmail.com","subject":"Re: [PATCH 7/9] strbuf_getwholeline: use getdelim if it is available","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2015-04-22T18:00:55Z","receivedAt":"2015-04-22T18:00:55Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn 2015-04-17 12:16, Eric Sunshine wrote:\n> On Thu, Apr 16, 2015 at 5:01 AM, Jeff King wrote:\n>> We spend a lot of time in strbuf_getwholeline in a tight\n>> loop reading characters from a stdio handle into a buffer.\n>> The libc getdelim() function can do this for us with less\n>> overhead.\n\nJust for the record: Git for Windows cannot lean on `getdelim()`, as it is not available on Windows. Do not let that stop you; if it turns out to impact performance, we will just have to come up with our own implementation of that function.\n\nCiao,\nDscho\n"},{"id":"259812","messageId":"20150422180628.GA3535@peff.net","threadId":"39005","inReplyTo":"alpine.DEB.1.00.1504222000040.28561@s15462909.onlinehome-server.info","subject":"Re: [PATCH 7/9] strbuf_getwholeline: use getdelim if it is available","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-22T18:06:29Z","receivedAt":"2015-04-22T18:06:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Apr 22, 2015 at 08:00:55PM +0200, Johannes Schindelin wrote:\n\n> On 2015-04-17 12:16, Eric Sunshine wrote:\n> > On Thu, Apr 16, 2015 at 5:01 AM, Jeff King wrote:\n> >> We spend a lot of time in strbuf_getwholeline in a tight\n> >> loop reading characters from a stdio handle into a buffer.\n> >> The libc getdelim() function can do this for us with less\n> >> overhead.\n> \n> Just for the record: Git for Windows cannot lean on `getdelim()`, as\n> it is not available on Windows. Do not let that stop you; if it turns\n> out to impact performance, we will just have to come up with our own\n> implementation of that function.\n\nHopefully the earlier patch in the series to avoid locking will help\non Windows. After the end of the series, it isn't used anymore on Linux,\nbut I kept it in exactly for those less-fortunate systems.\n\nIf you can find a Windows equivalent that does the same thing as\ngetdelim, it should be pretty easy to drop it into an alternate\nstrbuf_getwholeline implementation (or just provide a compat \"getdelim\"\nif it is close enough to have the same interface).\n\n-Peff\n"},{"id":"260883","messageId":"CAPig+cQi7SfJJc4d3DJ2mJ0-5vT7LJDttPPec=UEsmjiqtLcZQ@mail.gmail.com","threadId":"39005","inReplyTo":"20150421230929.GA27773@peff.net","subject":"Re: [PATCH 7/9] strbuf_getwholeline: use getdelim if it is available","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2015-05-08T23:56:28Z","receivedAt":"2015-05-08T23:56:28Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Tue, Apr 21, 2015 at 7:09 PM, Jeff King wrote:\n> On Fri, Apr 17, 2015 at 06:16:48AM -0400, Eric Sunshine wrote:\n>> > If somebody has a FreeBSD or OS X system to test on, I'd\n>> > love to see what is needed to compile with HAVE_GETDELIM\n>> > there.\n>>\n>> Modern Mac OS X, 10.10.x Yosemite, has getdelim() and git builds fine\n>> with HAVE_GETDELIM. I also tested on old Snow Leopard 10.5.8 from\n>> 2009. It does not have getdelim(). Unfortunately, I haven't been able\n>> to determine when getdelim() was introduced on the Mac OS X, thus have\n>> been unable to craft a simple rule for config.mak.uname.\n>\n> Thanks for looking into it. Since there haven't been any other takers in\n> the meantime, do you want to prepare a patch that checks $(uname_R) for\n> 10.10.x? That's likely more conservative than is necessary, but we can\n> loosen it later if somebody on 10.9.x shows up with test results.\n\nI spent some time downloading old Xcode releases and poking through\nthe packages. Xcode 3.2.x seems to be the last in the Xcode 3 series,\nand none of the Xcode 3.2.x versions I examined carried getdelim().\nThe first package in which I found getdelim() was Xcode 4.1.\n(Unfortunately, Apple doesn't seem to make Xcode 4.0 available for\ndownload anymore or it's only available to paying developers, so I\ncouldn't check it.) According to Wikipedia[1], Xcode 4.1 was released\nthe same day as Lion (OS X 10.7 [2]), but was also available to paying\ndevelopers for Snow Leopard (OS X 10.6).\n\nConsequently, I think it's safe to say that getdelim() is available\nfor Lion (10.7) and later. If we don't mind being a bit less\nconservative, then we might assume that it also is available for Snow\nLeopard (10.6), which it definitely supported, but perhaps that's too\nrisky, since not everyone would have been a paid subscriber.\n\nAlternately, we could make the test more dynamic and accurate by\ngrepping stdio.h for 'getdelim' or just by trying a test compile,\nthough that's probably too expensive.\n\n[1]: http://en.wikipedia.org/wiki/Xcode\n[2]: http://en.wikipedia.org/wiki/OS_X\n"},{"id":"260885","messageId":"20150509010952.GA29555@peff.net","threadId":"39005","inReplyTo":"CAPig+cQi7SfJJc4d3DJ2mJ0-5vT7LJDttPPec=UEsmjiqtLcZQ@mail.gmail.com","subject":"Re: [PATCH 7/9] strbuf_getwholeline: use getdelim if it is available","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-05-09T01:09:52Z","receivedAt":"2015-05-09T01:09:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, May 08, 2015 at 07:56:28PM -0400, Eric Sunshine wrote:\n\n> I spent some time downloading old Xcode releases and poking through\n> the packages. Xcode 3.2.x seems to be the last in the Xcode 3 series,\n> and none of the Xcode 3.2.x versions I examined carried getdelim().\n> The first package in which I found getdelim() was Xcode 4.1.\n> (Unfortunately, Apple doesn't seem to make Xcode 4.0 available for\n> download anymore or it's only available to paying developers, so I\n> couldn't check it.) According to Wikipedia[1], Xcode 4.1 was released\n> the same day as Lion (OS X 10.7 [2]), but was also available to paying\n> developers for Snow Leopard (OS X 10.6).\n> \n> Consequently, I think it's safe to say that getdelim() is available\n> for Lion (10.7) and later. If we don't mind being a bit less\n> conservative, then we might assume that it also is available for Snow\n> Leopard (10.6), which it definitely supported, but perhaps that's too\n> risky, since not everyone would have been a paid subscriber.\n\nThanks for digging. I'd argue for the conservative choice, simply\nbecause this is a pure optimization. The old code should work just fine,\nand people have been living with it for years.\n\nI doubt it will affect many people either way, though. Lion is 4 years\nold, and most OS X people seem to upgrade fairly regularly. It is not\nlike long-term server systems where we are supporting Solaris 7. :)\n\nWant to roll a patch?\n\n> Alternately, we could make the test more dynamic and accurate by\n> grepping stdio.h for 'getdelim' or just by trying a test compile,\n> though that's probably too expensive.\n\nThe natural place would be in configure.ac, and that is orthogonal to\nthe default Darwin setting, I think.\n\n-Peff\n"},{"id":"262760","messageId":"CAPig+cTctJ0VaKP1GLoWSxsnnq-G=0=fbcgR7tvFY0Daci=1QQ@mail.gmail.com","threadId":"39005","inReplyTo":"20150509010952.GA29555@peff.net","subject":"Re: [PATCH 7/9] strbuf_getwholeline: use getdelim if it is available","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2015-06-02T18:22:29Z","receivedAt":"2015-06-02T18:22:29Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Fri, May 8, 2015 at 9:09 PM, Jeff King wrote:\n> On Fri, May 08, 2015 at 07:56:28PM -0400, Eric Sunshine wrote:\n>> I spent some time downloading old Xcode releases and poking through\n>> the packages. Xcode 3.2.x seems to be the last in the Xcode 3 series,\n>> and none of the Xcode 3.2.x versions I examined carried getdelim().\n>> The first package in which I found getdelim() was Xcode 4.1.\n>> (Unfortunately, Apple doesn't seem to make Xcode 4.0 available for\n>> download anymore or it's only available to paying developers, so I\n>> couldn't check it.) According to Wikipedia[1], Xcode 4.1 was released\n>> the same day as Lion (OS X 10.7 [2]), but was also available to paying\n>> developers for Snow Leopard (OS X 10.6).\n>>\n>> Consequently, I think it's safe to say that getdelim() is available\n>> for Lion (10.7) and later. If we don't mind being a bit less\n>> conservative, then we might assume that it also is available for Snow\n>> Leopard (10.6), which it definitely supported, but perhaps that's too\n>> risky, since not everyone would have been a paid subscriber.\n>\n> Thanks for digging. I'd argue for the conservative choice, simply\n> because this is a pure optimization. The old code should work just fine,\n> and people have been living with it for years.\n>\n> I doubt it will affect many people either way, though. Lion is 4 years\n> old, and most OS X people seem to upgrade fairly regularly. It is not\n> like long-term server systems where we are supporting Solaris 7. :)\n>\n> Want to roll a patch?\n\nAfter a long, long delay, here it is...[1]\n\n>> Alternately, we could make the test more dynamic and accurate by\n>> grepping stdio.h for 'getdelim' or just by trying a test compile,\n>> though that's probably too expensive.\n>\n> The natural place would be in configure.ac, and that is orthogonal to\n> the default Darwin setting, I think.\n\nI added that too[1].\n\n[1]: http://thread.gmane.org/gmane.comp.version-control.git/270576\n"}]}