Re: [PATCH v3] skip_prefix: rewrite so that prefix is scanned once
- From
Duy Nguyen <pclouds@gmail.com>
- Date
- Mar 4, 2014, 01:58 UTC
- Message-ID
- <20140304015819.GA10643@duynguyen-vnpc.dek-tpc.internal>
- In-Reply-To
- <877g8akenw.fsf@fencepost.gnu.org>
On Tue, Mar 04, 2014 at 01:09:39AM +0100, David Kastrup wrote:
Show 29 quoted lines
> Duy Nguyen <pclouds@gmail.com> writes:
>
> > On Tue, Mar 4, 2014 at 5:43 AM, Junio C Hamano <gitster@pobox.com> wrote:
> >> diff --git a/git-compat-util.h b/git-compat-util.h
> >> index cbd86c3..68ffaef 100644
> >> --- a/git-compat-util.h
> >> +++ b/git-compat-util.h
> >> @@ -357,8 +357,14 @@ extern int suffixcmp(const char *str, const char *suffix);
> >>
> >> static inline const char *skip_prefix(const char *str, const char *prefix)
> >> {
> >> - size_t len = strlen(prefix);
> >> - return strncmp(str, prefix, len) ? NULL : str + len;
> >
> > Just a note. gcc does optimize strlen("abcdef") to 6, and with that
> > information at compile time built-in strncmp might do better.
>
> Indeed, most (but not all) of the calls have a constant string as
> prefix. However, strncmp in each iteration checks for both *str as well
> as *prefix to be different from '\0' independently (and it appears
> unlikely to me that the optimizer will figure out that it's unnecessary
> for either) _and_ compares them for equality so it's not likely to be
> faster than the open-coded loop.
>
> One could, however, use memcmp instead of strncmp. I'm just not sure
> whether memcmp is guaranteed not to peek beyond the first mismatching
> byte even if the count would allow for more. It could lead to undefined
> behavior if the first mismatching byte would be the ending NUL byte of
> str.It turns out gcc does not generate a call to strncmp either. It inlines repz cmpsb instead. I recall we had a discussion long ago about the inefficiency of repz and and open-coded loop is preferred, maybe that was about hashcmp. Anyway this does not matter much as skip_prefix() is unlikely to be in any critical path, so I think readability has higher priority.
For the curious, this small C program
-- 8< -- #include <stdio.h> #include <string.h>
static inline const char *skip(const char *str, const char *prefix)
{
int len = strlen(prefix);
return strncmp(str, prefix, len) ? NULL : str + len;
}
int main(int ac, char **av)
{
const char *s = skip(av[1], "foo");
printf("%s\n", s);
return 0;
}
-- 8< --produces this assembly with gcc -O2 (on x86, apparently)
-- 8< -- 00000000 <main>: 0: 55 push %ebp 1: b9 03 00 00 00 mov $0x3,%ecx 6: 89 e5 mov %esp,%ebp 8: 57 push %edi 9: bf 00 00 00 00 mov $0x0,%edi e: 56 push %esi f: 53 push %ebx 10: 83 e4 f0 and $0xfffffff0,%esp 13: 83 ec 10 sub $0x10,%esp 16: 8b 45 0c mov 0xc(%ebp),%eax 19: 8b 40 04 mov 0x4(%eax),%eax 1c: 89 c6 mov %eax,%esi 1e: f3 a6 repz cmpsb %es:(%edi),%ds:(%esi) 20: 0f 97 c3 seta %bl 23: 0f 92 c1 setb %cl 26: 83 c0 03 add $0x3,%eax 29: 31 d2 xor %edx,%edx 2b: 38 cb cmp %cl,%bl 2d: 0f 44 d0 cmove %eax,%edx 30: 89 14 24 mov %edx,(%esp) 33: e8 fc ff ff ff call 34 <main+0x34> 38: 8d 65 f4 lea -0xc(%ebp),%esp 3b: 31 c0 xor %eax,%eax 3d: 5b pop %ebx 3e: 5e pop %esi 3f: 5f pop %edi 40: 5d pop %ebp 41: c3 ret -- 8< -- -- Duy