strcmp for empty string

Question

I was reviewing some code and I saw someone do a

if (0 == strcmp(foo,""))

I am curious because I think it would be faster to do a

if (foo[0] == '\0')

Is this correct or is strcmp optimized enough to make them the same.

(I realize that even if there was some difference it would be small, but am thinking you save at least a few instructions by using my method.)

Rotary

You're right for questioning the pattern, and I like your way better for this. – Afraid

When checking for the empty string, it makes more sense to me to do if (strlen(foo) == 0). – Tragic

@Jamie Wong: if the string is 1Meg long, then you have to check 1 million bytes before you find the terminating null; This is a pretty big lose when you are only interested in the case where the string has either zero, or more than zero characters. – Afraid

Your way will invariably be faster. Even if you ignore the fact that strcmp has call overhead, it must eventually do that same memory access too. Hence it can only be equal or slower speed. – Glycerite

@Mike: I think the spirit of the question is more to do with cases where strcmp might do something wiser than the direct array access; what with buffer overruns and the like. I think the answer is that in this case, there aren't any. – Afraid

wow thanks for all the responses everyone. I have learned a lot. – Rotary

@x4u provided a very good option below. I checked this conditions and found that "if( !*str )" requires one instruction less compare with "if (0 == strcmp(foo,""))". Microsoft compiler for x64 architecture produces 3 instr (12Bytes) vs 4 instr (18Bytes) respectively. BTW compiler produces the same code for "if( !*str )" and "if (str[0] == '\0')" – Tasker

Answer 1

You're right: since calling strcmp() adds up the stack management and the memory jump to the actual strcmp instructions, you'll gain a few instructions by just checking the first byte of your string.

For your curiosity, you can check the strcmp() code here: http://sourceware.org/git/?p=glibc.git;a=blob;f=string/strcmp.c;h=bd53c05c6e21130b091bd75c3fc93872dd71fe4b;hb=HEAD

(I thought the code would be filled with #ifdef and obscure __GNUSOMETHING, but it's actually rather simple!)

Gerdi

Answer 2

strcmp() is a function call and thus has a function call overhead. foo[0] is direct access to the array, so it's obviously faster.

Asta

Answer 3

I see no advantage of using strcmp in this case. The compiler my be clever enough to optimize it away but it won't be any faster than checking for the '\0' byte directly. The implementer of this might have chosen this construct because he thought it is more readable but I think this is a matter of taste in this case. Although I would write the check a little different as this is the idiom that seems to be used most often to check for an empty string:

if( !*str )

and

if( *str )

to check for a non empty string.

Rapallo

yeah I like that better, where I work though us some strict guidelines about being explicit in the conditional....so even if it doesn't make a whole lot of sense I have to explicitly check for '\0' or 0 – Rotary

Answer 4

+1 to Gui13 for providing a link to the source of gcc stdlib strcmp (http://sourceware.org/git/?p=glibc.git;a=blob;f=string/strcmp.c;h=bd53c05c6e21130b091bd75c3fc93872dd71fe4b;hb=HEAD)!

You are correct that strcmp can never be faster than a direct comparison[1], but the question is, will the compiler optimise it? I was intimidated to try measuring that, but I was pleasantly surprised at how easy it was. My sample code is (omitting headers):

bool isEmpty(char * str) {
   return 0==std::strcmp(str,"");
}
bool isEmpty2(char * str) {
   return str[0]==0;
}

And I tried compiling that, first with gcc -S -o- emptystrcmptest.cc and then with gcc -S -O2 -o- emptystrcmptest.cc. To my pleasant surprise, although I can't read the assembly very well, the non-optimised version clearly showed a difference, and the optimised version clearly showed the two functions produced identical assembly.

So, I would say that in general, there's no point worrying about this level of optimisation.

If you are using a compiler for an embedded system and know it not to handle this sort of simple optimisation (or don't have a standard library at all), use the hand-coded special-case version.

If you are coding normally, use the more readable version (imho that may be strcmp or strlen or [0]==0 depending on context).

If you are writing highly efficient code you expect to be called thousands or millions of times a second, (a) test which is actually more efficient and (b) if the readable version is actually too slow, try to write somethign which will compile to better assembly.

With gcc -S -o- emptystrcmptest.cc:

            .file   "emptystrcmptest.cc"
            .section .rdata,"dr"
    LC0:
            .ascii "\0"
            .text
            .align 2
    .globl __Z7isEmptyPc
            .def    __Z7isEmptyPc;  .scl    2;      .type   32;     .endef
    __Z7isEmptyPc:
            pushl   %ebp
            movl    %esp, %ebp
            subl    $24, %esp
            movl    $LC0, 4(%esp)
            movl    8(%ebp), %eax
            movl    %eax, (%esp)
            call    _strcmp
            movl    %eax, -4(%ebp)
            cmpl    $0, -4(%ebp)
            sete    %al
            movzbl  %al, %eax
            movl    %eax, -4(%ebp)
            movl    -4(%ebp), %eax
            leave
            ret
            .align 2
    .globl __Z8isEmpty2Pc
            .def    __Z8isEmpty2Pc; .scl    2;      .type   32;     .endef
    __Z8isEmpty2Pc:
            pushl   %ebp
            movl    %esp, %ebp
            movl    8(%ebp), %eax
            cmpb    $0, (%eax)
            sete    %al
            movzbl  %al, %eax
            popl    %ebp
            ret
    emptystrcmptest.cc:10:2: warning: no newline at end of file
            .def    _strcmp;        .scl    2;      .type   32;     .endef

With gcc -S -O2 -o- emptystrcmptest.cc:

        .file   "emptystrcmptest.cc"
emptystrcmptest.cc:10:2: warning: no newline at end of file
        .text
        .align 2
        .p2align 4,,15
.globl __Z7isEmptyPc
        .def    __Z7isEmptyPc;  .scl    2;      .type   32;     .endef
__Z7isEmptyPc:
        pushl   %ebp
        movl    %esp, %ebp
        movl    8(%ebp), %eax
        popl    %ebp
        cmpb    $0, (%eax)
        sete    %al
        movzbl  %al, %eax
        ret
        .align 2
        .p2align 4,,15
.globl __Z8isEmpty2Pc
        .def    __Z8isEmpty2Pc; .scl    2;      .type   32;     .endef
__Z8isEmpty2Pc:
        pushl   %ebp
        movl    %esp, %ebp
        movl    8(%ebp), %eax
        popl    %ebp
        cmpb    $0, (%eax)
        sete    %al
        movzbl  %al, %eax
        ret

[1] Although be careful -- in cases any more complicated than a direct test against zero, the library and compiler code a typically WILL be better than hand-crafted code.

Vacuous

+1 @Jack This lends great credence to @Brandon Moretz's comment. Good post. I'm still not sure which I prefer in terms of pure readability, but this definitely makes a good point in terms of premature-optimizations. – Moncada

Answer 5

A good optimizing compiler might optimize away the function call and then eliminate the loop from the inlined function. There's no way that your method could be slower, though there is a chance that it will be the same speed.

Diaphony

Answer 6

Access to an array is order 1 in execution time, so, it´s faster than the function.

Shuttlecock

Answer 7

This is as micro-optimizing as it gets, but I suppose if you added a null check before you index foo (unless you know it'll never be null) it would technically save the overhead of a function call.

Child

I think you missed the point. OP is not checking for a null pointer but for a zero-length string. There's never a purpose to performing both the direct check and the strcmp call since the effects are the same. – Coom

@R I believe you should re-read my response. I was simply stating that he should perform a null check on a pointer before blindly indexing it. I didn't say anything about calling strcmp. – Child

Answer 8

It's clearly going to be faster, and it's probably worth placing your own code in an inline function, or maybe even a macro, if you plan on moving forward with it:

int isEmpty(const char *string)
{
    return ! *string;
}

int isNotEmpty(const char *string)
{
    return *string;
}

int isNullOrEmpty(const char *string)
{
    return string == NULL || ! *string;
}

int isNotNullOrEmpty(const char *string)
{
    return string != NULL && *string;
}

and let the compiler optimize that for you. Regardless, strcmp needs to eventually check for '\0' so you're always at least equal to it. (honestly, I'd probably let the compiler optimize internal sharing of the above, e.g., isEmpty would probably just flip isNotEmpty)

Moncada

I'm pretty sure that determining f() == !a() is way beyond the abilities of any optimizer. – Paleoasiatic

@mike Correct, but it can still optimize the call to be inline rather than pushing the same pointer onto the stack. This also prevents potentially "non-standard" code littering the codebase. – Moncada