Re: [PATCH] read-cache: avoid memcpy in expand_name_field in index v4

Nguyễn Thái Ngọc Duy  [off-list ref] writes:

perf reports memcpy at the the 6th position [1] in "git status -uno"
using index v4, and strbuf_remove() in expand_name_field() accounts
for 25% of that. What we need here is a simple string cut and a
cheaper strbuf_setlen() should be enough.

While it is true that strbuf_remove(&sb, sb.len - trim, trim) is
equivalent to strbuf_setlen(&sb, sb.len - trim), I wonder why we see
any memcpy() in the first place.

strbuf_remove(&sb, sb.len - trim, trim) is turned into
strbuf_splice(&sb, sb.len - trim, trim, NULL, 0) and then in turn it
does these two:

	memmove(sb.buf + (sb.len - trim) + 0,
                sb.buf + sb.len, 0);
	memcpy(sb.buf + (sb.len - trim), NULL, 0);

both of which should be a no-op, no?

There also is this call that has the same "trim at the right end":

    pretty.c:       strbuf_remove(sb, sb->len - trimlen, trimlen);

It almost makes me suggest that it may be a better solution to make
strbuf_remove() more intelligent about such a call pattern _if_
these empty memmove/memcpy are so expensive, perhaps like the
attached.  It could be that strbuf_splice() should be the one that
ought to be more intelligent, but I'll leave it up to you to
benchmark to find out where the best place to optimize is.

 strbuf.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/strbuf.c b/strbuf.c
index 05d0693..12db700 100644
--- a/strbuf.c
+++ b/strbuf.c

@@ -179,7 +179,10 @@ void strbuf_insert(struct strbuf *sb, size_t pos, const void *data, size_t len)
 
 void strbuf_remove(struct strbuf *sb, size_t pos, size_t len)
 {
-	strbuf_splice(sb, pos, len, NULL, 0);
+	if (pos + len == sb->len)
+		strbuf_setlen(sb, pos);
+	else
+		strbuf_splice(sb, pos, len, NULL, 0);
 }
 
 void strbuf_add(struct strbuf *sb, const void *data, size_t len)

On Tue, Mar 19, 2013 at 12:50 AM, Junio C Hamano [off-list ref] wrote:

While it is true that strbuf_remove(&sb, sb.len - trim, trim) is
equivalent to strbuf_setlen(&sb, sb.len - trim), I wonder why we see
any memcpy() in the first place.

strbuf_remove(&sb, sb.len - trim, trim) is turned into
strbuf_splice(&sb, sb.len - trim, trim, NULL, 0) and then in turn it
does these two:

        memmove(sb.buf + (sb.len - trim) + 0,
                sb.buf + sb.len, 0);
        memcpy(sb.buf + (sb.len - trim), NULL, 0);

both of which should be a no-op, no?

Apparently my memcpy does not bail out early when the third arg is
zero (glibc 2.11.2 on gentoo, x86). It cares more about memory
alignment. This is the beginning of memcpy:

mov    %edi,%eax
mov    0x4(%esp),%edi
mov    %esi,%edx
mov    0x8(%esp),%esi
mov    %edi,%ecx
xor    %esi,%ecx
and    $0x3,%ecx
mov    0xc(%esp),%ecx
cld
jne    75946 <memcpy+0x56>
cmp    $0x3,%ecx
jbe    75946 <memcpy+0x56>

There also is this call that has the same "trim at the right end":

    pretty.c:       strbuf_remove(sb, sb->len - trimlen, trimlen);

It almost makes me suggest that it may be a better solution to make
strbuf_remove() more intelligent about such a call pattern _if_
these empty memmove/memcpy are so expensive, perhaps like the
attached.  It could be that strbuf_splice() should be the one that
ought to be more intelligent, but I'll leave it up to you to
benchmark to find out where the best place to optimize is.

memcpy is not expensive per-se, but this is (again) webkit, where
expand_name_field (and memcpy) is called ~200k times. At that quantity
I still prefer fixing in the "hot" call site expand_name_field(), and
because strbuf_setlen is an inline function, we make no extra calls.

Making strbuf_remove/strbuf_splice more intelligent may be good (or
may make it harder to read), I don't know. But I think it could be a
separate topic.
-- 
Duy