{"thread":{"id":"33216","subject":"[PATCH] read-cache: avoid memcpy in expand_name_field in index v4","startedAt":"2013-03-18T12:58:02Z","lastAt":"2013-03-19T01:29:01Z","messageCount":3,"participants":["Nguyễn Thái Ngọc Duy","Junio C Hamano","Duy Nguyen"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"211563","messageId":"1363611482-1015-1-git-send-email-pclouds@gmail.com","threadId":"33216","inReplyTo":null,"subject":"[PATCH] read-cache: avoid memcpy in expand_name_field in index v4","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-18T12:58:02Z","receivedAt":"2013-03-18T12:58:02Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"perf reports memcpy at the the 6th position [1] in \"git status -uno\"\nusing index v4, and strbuf_remove() in expand_name_field() accounts\nfor 25% of that. What we need here is a simple string cut and a\ncheaper strbuf_setlen() should be enough. After this change, memcpy\ndrops down to the 13th position [2] and is dominated by\nread_index_from.\n\n[1] before\n+     15.74%   git  git                [.] blk_SHA1_Block\n+     13.22%   git  [kernel.kallsyms]  [k] link_path_walk\n+     10.91%   git  [kernel.kallsyms]  [k] __d_lookup\n+      8.17%   git  [kernel.kallsyms]  [k] strncpy_from_user\n+      4.75%   git  [kernel.kallsyms]  [k] memcmp\n+      2.42%   git  libc-2.11.2.so     [.] memcpy\n\n[2] after\n+     16.30%   git  git                [.] blk_SHA1_Block\n+     13.43%   git  [kernel.kallsyms]  [k] link_path_walk\n+     11.45%   git  [kernel.kallsyms]  [k] __d_lookup\n+      8.73%   git  [kernel.kallsyms]  [k] strncpy_from_user\n+      5.14%   git  [kernel.kallsyms]  [k] memcmp\n+      2.29%   git  [kernel.kallsyms]  [k] do_lookup\n+      2.21%   git  libc-2.11.2.so     [.] 0x6daf6\n+      1.98%   git  [kernel.kallsyms]  [k] _atomic_dec_and_lock\n+      1.98%   git  [kernel.kallsyms]  [k] _raw_spin_lock\n+      1.86%   git  [kernel.kallsyms]  [k] acl_permission_check\n+      1.61%   git  [kernel.kallsyms]  [k] kmem_cache_free\n+      1.59%   git  git                [.] unpack_trees\n+      1.47%   git  libc-2.11.2.so     [.] memcpy\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n I was after something else when I noticed this. Seems like a simple\n and safe change.\n\n read-cache.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex 827ae55..8c443aa 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1354,7 +1354,7 @@ static unsigned long expand_name_field(struct strbuf *name, const char *cp_)\n \n \tif (name->len < len)\n \t\tdie(\"malformed name field in the index\");\n-\tstrbuf_remove(name, name->len - len, len);\n+\tstrbuf_setlen(name, name->len - len);\n \tfor (ep = cp; *ep; ep++)\n \t\t; /* find the end */\n \tstrbuf_add(name, cp, ep - cp);\n-- \n1.8.2.83.gc99314b\n"},{"id":"211587","messageId":"7vboagoav9.fsf@alter.siamese.dyndns.org","threadId":"33216","inReplyTo":"1363611482-1015-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH] read-cache: avoid memcpy in expand_name_field in index v4","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-18T17:50:50Z","receivedAt":"2013-03-18T17:50:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n\n> perf reports memcpy at the the 6th position [1] in \"git status -uno\"\n> using index v4, and strbuf_remove() in expand_name_field() accounts\n> for 25% of that. What we need here is a simple string cut and a\n> cheaper strbuf_setlen() should be enough.\n\nWhile it is true that strbuf_remove(&sb, sb.len - trim, trim) is\nequivalent to strbuf_setlen(&sb, sb.len - trim), I wonder why we see\nany memcpy() in the first place.\n\nstrbuf_remove(&sb, sb.len - trim, trim) is turned into\nstrbuf_splice(&sb, sb.len - trim, trim, NULL, 0) and then in turn it\ndoes these two:\n\n\tmemmove(sb.buf + (sb.len - trim) + 0,\n                sb.buf + sb.len, 0);\n\tmemcpy(sb.buf + (sb.len - trim), NULL, 0);\n\nboth of which should be a no-op, no?\n\nThere also is this call that has the same \"trim at the right end\":\n\n    pretty.c:       strbuf_remove(sb, sb->len - trimlen, trimlen);\n\nIt almost makes me suggest that it may be a better solution to make\nstrbuf_remove() more intelligent about such a call pattern _if_\nthese empty memmove/memcpy are so expensive, perhaps like the\nattached.  It could be that strbuf_splice() should be the one that\nought to be more intelligent, but I'll leave it up to you to\nbenchmark to find out where the best place to optimize is.\n\n strbuf.c | 5 ++++-\n 1 file changed, 4 insertions(+), 1 deletion(-)\n\ndiff --git a/strbuf.c b/strbuf.c\nindex 05d0693..12db700 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -179,7 +179,10 @@ void strbuf_insert(struct strbuf *sb, size_t pos, const void *data, size_t len)\n \n void strbuf_remove(struct strbuf *sb, size_t pos, size_t len)\n {\n-\tstrbuf_splice(sb, pos, len, NULL, 0);\n+\tif (pos + len == sb->len)\n+\t\tstrbuf_setlen(sb, pos);\n+\telse\n+\t\tstrbuf_splice(sb, pos, len, NULL, 0);\n }\n \n void strbuf_add(struct strbuf *sb, const void *data, size_t len)\n"},{"id":"211620","messageId":"CACsJy8DhMpQsNY3f4U3FmE1Bd1PvrxDLTYWT6boycrJVtv8WVg@mail.gmail.com","threadId":"33216","inReplyTo":"7vboagoav9.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] read-cache: avoid memcpy in expand_name_field in index v4","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-19T01:29:01Z","receivedAt":"2013-03-19T01:29:01Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Mar 19, 2013 at 12:50 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> While it is true that strbuf_remove(&sb, sb.len - trim, trim) is\n> equivalent to strbuf_setlen(&sb, sb.len - trim), I wonder why we see\n> any memcpy() in the first place.\n>\n> strbuf_remove(&sb, sb.len - trim, trim) is turned into\n> strbuf_splice(&sb, sb.len - trim, trim, NULL, 0) and then in turn it\n> does these two:\n>\n>         memmove(sb.buf + (sb.len - trim) + 0,\n>                 sb.buf + sb.len, 0);\n>         memcpy(sb.buf + (sb.len - trim), NULL, 0);\n>\n> both of which should be a no-op, no?\n\nApparently my memcpy does not bail out early when the third arg is\nzero (glibc 2.11.2 on gentoo, x86). It cares more about memory\nalignment. This is the beginning of memcpy:\n\nmov    %edi,%eax\nmov    0x4(%esp),%edi\nmov    %esi,%edx\nmov    0x8(%esp),%esi\nmov    %edi,%ecx\nxor    %esi,%ecx\nand    $0x3,%ecx\nmov    0xc(%esp),%ecx\ncld\njne    75946 <memcpy+0x56>\ncmp    $0x3,%ecx\njbe    75946 <memcpy+0x56>\n\n\n> There also is this call that has the same \"trim at the right end\":\n>\n>     pretty.c:       strbuf_remove(sb, sb->len - trimlen, trimlen);\n>\n> It almost makes me suggest that it may be a better solution to make\n> strbuf_remove() more intelligent about such a call pattern _if_\n> these empty memmove/memcpy are so expensive, perhaps like the\n> attached.  It could be that strbuf_splice() should be the one that\n> ought to be more intelligent, but I'll leave it up to you to\n> benchmark to find out where the best place to optimize is.\n\nmemcpy is not expensive per-se, but this is (again) webkit, where\nexpand_name_field (and memcpy) is called ~200k times. At that quantity\nI still prefer fixing in the \"hot\" call site expand_name_field(), and\nbecause strbuf_setlen is an inline function, we make no extra calls.\n\nMaking strbuf_remove/strbuf_splice more intelligent may be good (or\nmay make it harder to read), I don't know. But I think it could be a\nseparate topic.\n-- \nDuy\n"}]}