String comparison for fixed strings

String comparison for fixed strings

[KhaOsh]

Hello everyone,

In terms of speed what the fastest way of doing a strings comparison
on fixed strings? Using one of those strcmp() functions or doing the
following:

(Pseudo code)
"if (s[0] == 0xa && s[1] == 0xb && s[2] == 0xc)" (etc)
or
"if (s[0] == 'A' && s[1] == 'B' && s[2[ == 'C')" (etc)

Thanks for your help.

Re: String comparison for fixed strings

[Stephen Kratzer]

On Wednesday 15 August 2007 07:06:24 KhaOsh wrote:
> Hello everyone,
>
> In terms of speed what the fastest way of doing a strings comparison
> on fixed strings? Using one of those strcmp() functions or doing the
> following:
>
> (Pseudo code)
> "if (s[0] == 0xa && s[1] == 0xb && s[2] == 0xc)" (etc)
> or
> "if (s[0] == 'A' && s[1] == 'B' && s[2[ == 'C')" (etc)
>
> Thanks for your help.

The function strcmp uses a do/while loop, a conditional to test every 
character in the first string against the null character, and pointer 
arithmetic, so, in terms of sheer speed, your method would probably be 
faster. But, in terms of program clarity, strcmp wins by a mile.

Stephen Kratzer

Re: String comparison for fixed strings

[Glynn Clements]

Stephen Kratzer wrote:

> > In terms of speed what the fastest way of doing a strings comparison
> > on fixed strings? Using one of those strcmp() functions or doing the
> > following:
> >
> > (Pseudo code)
> > "if (s[0] == 0xa && s[1] == 0xb && s[2] == 0xc)" (etc)
> > or
> > "if (s[0] == 'A' && s[1] == 'B' && s[2[ == 'C')" (etc)
> >
> > Thanks for your help.
> 
> The function strcmp uses a do/while loop, a conditional to test every 
> character in the first string against the null character, and pointer 
> arithmetic, so, in terms of sheer speed, your method would probably be 
> faster. But, in terms of program clarity, strcmp wins by a mile.

1. The test against the NUL byte can't be eliminated unless you know
in advance that the string is long enough.

2. The above pseudo-code also does pointer arithmetic: "s[2]" is just
another way of writing "*(s+2)".

3. An actual loop is typically quicker than an "unrolled" loop (where
you just repeat the loop body) as it results in smaller code and thus
better cache coherency.

All things considered, strcmp() is likely to be faster.

-- 
Glynn Clements <glynn@gclements.plus.com>

Re: String comparison for fixed strings

[Leslie P. Polzer]

> 3. An actual loop is typically quicker than an "unrolled" loop (where
> you just repeat the loop body) as it results in smaller code and thus
> better cache coherency.

I'm not sure whether it was the OP's intention to talk about
the (dis)advantages of unrolled code.


> All things considered, strcmp() is likely to be faster.

Given these things:

1. The null byte check is mandatory.

2. The haystack string is not _considerably_ larger than the
   needle string.

Re: String comparison for fixed strings

[Glynn Clements]

Leslie P. Polzer wrote:

> > 3. An actual loop is typically quicker than an "unrolled" loop (where
> > you just repeat the loop body) as it results in smaller code and thus
> > better cache coherency.
> 
> I'm not sure whether it was the OP's intention to talk about
> the (dis)advantages of unrolled code.

No, but Stephen mentioned that strcmp() "uses a do/while loop".
On a modern CPU, branches don't normally take any CPU cycles.

> > All things considered, strcmp() is likely to be faster.
> 
> Given these things:
> 
> 1. The null byte check is mandatory.
> 
> 2. The haystack string is not _considerably_ larger than the
>    needle string.

Huh? The question was about strcmp(), not strstr().

For strcmp(), you don't really gain much by having the string fixed. 
If you are performing the check often enough, the string will be
cached. If the check is infrequent, a single strcmp() function is more
likely to be cached than several fixed-string checks. The strings
themselves won't necessarily be cached, but a cache miss for data is a
lot less significant than a cache miss for code.

For strstr() with a fixed "needle", a pre-compiled finite automaton
will win. With a variable "needle", if the "haystack" is large enough,
even a dynamically-generated finite automaton will be faster than an
strncmp() loop.

-- 
Glynn Clements <glynn@gclements.plus.com>

Re: String comparison for fixed strings

[Per Jessen]

Glynn Clements wrote:

> No, but Stephen mentioned that strcmp() "uses a do/while loop".
> On a modern CPU, branches don't normally take any CPU cycles.

I would have thought everything takes CPU cycles, modern CPU or not?


/Per Jessen

Re: String comparison for fixed strings

[Glynn Clements]

Per Jessen wrote:

> > No, but Stephen mentioned that strcmp() "uses a do/while loop".
> > On a modern CPU, branches don't normally take any CPU cycles.
> 
> I would have thought everything takes CPU cycles, modern CPU or not?

The Intel architecture from the Pentium Pro onwards has a great deal
of parallelism. It can commence and complete up to 3 instructions per
CPU cycle, but in practice it will almost never be able to sustain
that rate continuously. Adding another instruction will only require
additional CPU cycles if the instruction delays processing of
subsequent instructions.

In particular, branch instructions are dealt with by dedicated logic
circuitry which does nothing but process branch instructions. This
enables speculative execution to work handle branches even when the
calculation of the branch condition hasn't completed.

The end result is that the only difference between a loop and an
unrolled loop is that the unrolled loop results in the branch
processing logic remaining idle.

More generally, duplicating blocks of code (e.g. unrolling loops or
having multiple specialised versions of a routine instead of one
generalised version) is usually a net loss on modern architectures, as
cache coherence (particularly for code) has a far greater impact than
the total number of instructions executed, due to the fact that the
CPU is much faster than the RAM.

The actual cost of a code cache miss varies depending upon the
relative speed of the CPU and RAM, but 400 cycles is typical. You
would need to have a lot of additional instructions before their cost
outweighs that of a cache miss.

-- 
Glynn Clements <glynn@gclements.plus.com>

Re: String comparison for fixed strings

[Per Jessen]

Glynn Clements wrote:

> In particular, branch instructions are dealt with by dedicated logic
> circuitry which does nothing but process branch instructions. This
> enables speculative execution to work handle branches even when the
> calculation of the branch condition hasn't completed.

Yep, I understand all that - it doesn't even have to be a particularly
modern CPU, even IBMs S390 architecture did this in the early '90s.
Speculative execution and branch prediction etc. have both been around
for a while, just not in the Intel world.

Regardless, I still wouldn't say "branches don't normally take any CPU
cycles", but maybe that's splitting hairs.

> The actual cost of a code cache miss varies depending upon the
> relative speed of the CPU and RAM, but 400 cycles is typical. You
> would need to have a lot of additional instructions before their cost
> outweighs that of a cache miss.

Very true, but given the size of L1 cache these days, you also have a
lot more leeway than you did e.g. in the 90s.  A typical memcmp() for
short strings is unrolled by default by gcc.  (at least I'm fairly
certain it does that).


/Per

Re: String comparison for fixed strings

[KhaOsh]

Thanks everyone! :-)

On 17/08/07, Per Jessen <per@computer.org> wrote:
> Glynn Clements wrote:
>
> > In particular, branch instructions are dealt with by dedicated logic
> > circuitry which does nothing but process branch instructions. This
> > enables speculative execution to work handle branches even when the
> > calculation of the branch condition hasn't completed.
>
> Yep, I understand all that - it doesn't even have to be a particularly
> modern CPU, even IBMs S390 architecture did this in the early '90s.
> Speculative execution and branch prediction etc. have both been around
> for a while, just not in the Intel world.
>
> Regardless, I still wouldn't say "branches don't normally take any CPU
> cycles", but maybe that's splitting hairs.
>
> > The actual cost of a code cache miss varies depending upon the
> > relative speed of the CPU and RAM, but 400 cycles is typical. You
> > would need to have a lot of additional instructions before their cost
> > outweighs that of a cache miss.
>
> Very true, but given the size of L1 cache these days, you also have a
> lot more leeway than you did e.g. in the 90s.  A typical memcmp() for
> short strings is unrolled by default by gcc.  (at least I'm fairly
> certain it does that).
>
>
> /Per
> -
> To unsubscribe from this list: send the line "unsubscribe linux-c-programming" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re: String comparison for fixed strings

[Glynn Clements]

Glynn Clements wrote:

> 1. The test against the NUL byte can't be eliminated unless you know
> in advance that the string is long enough.

Actually, this is false. If the variable string terminates
prematurely, it will differ from the fixed string at that point, so a
separate NUL check is unnecessary.

As Jesse points out, the logical alternative to the hard-coded
comparisons is memcmp(), not strcmp().

You only need to use strcmp() if you don't know the length of either
string in advance.

-- 
Glynn Clements <glynn@gclements.plus.com>

Re: String comparison for fixed strings

[Jesse Ruffin]

[-- Attachment #1: Type: text/plain, Size: 865 bytes --]

If you are only checking for exact equality of a buffer against a string, the memcmp() function may be slightly faster.

if ( memcmp( (const void*) s, (const void*) "ABC", 3 ) == 0 ) {
	// equal
} else {
	// not equal
}

Jesse Ruffin

On Wednesday 15 August 2007 07:06, KhaOsh wrote:
> Hello everyone,
> 
> In terms of speed what the fastest way of doing a strings comparison
> on fixed strings? Using one of those strcmp() functions or doing the
> following:
> 
> (Pseudo code)
> "if (s[0] == 0xa && s[1] == 0xb && s[2] == 0xc)" (etc)
> or
> "if (s[0] == 'A' && s[1] == 'B' && s[2[ == 'C')" (etc)
> 
> Thanks for your help.
> -
> To unsubscribe from this list: send the line "unsubscribe linux-c-programming" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]