strncmp performance

[pembed2003]

Hi,
I have an application where I use the strncmp function extensively to
compare 2 string to see if they are the same or not. Does anyone know
a faster replacement for strncmp? I notice there is a memncmp function
which is very fast but it doesn't work the same like strncmp so I
don't think I can use it. I also tried to write the string_equal
function myself like:

int string_equal(co nst char* s1,const char* s2){
while(*s1 && *s2 && *s1 == *s2){
s1++; s2++;
}
return *s1 == *s2;
}

but I don't get much performance gain. Any suggestion?

Thanks!

[Nick Landsberg]

The problem is probably not in strncmp(), but elsewhere.

Comparing strings linearly is an expensive proposition
when there are many strings to be compared. If there's
only a handful (10 or so) it's not bad, if there are
thousands, then strncmp() without an intelligent
algorithm (e.g. binary search) behind it is probably
not the way to go.

Try a newsgroup dealing with algorithms. Maybe
comp.programmin g?

pembed2003 wrote:

Hi,
I have an application where I use the strncmp function extensively to
compare 2 string to see if they are the same or not. Does anyone know
a faster replacement for strncmp? I notice there is a memncmp function
which is very fast but it doesn't work the same like strncmp so I
don't think I can use it. I also tried to write the string_equal
function myself like:

int string_equal(co nst char* s1,const char* s2){
while(*s1 && *s2 && *s1 == *s2){
s1++; s2++;
}
return *s1 == *s2;
}

but I don't get much performance gain. Any suggestion?

Thanks!

--
"It is impossible to make anything foolproof because fools are so
ingenious" - A. Bloch

[Tom St Denis]

"pembed2003 " <pe********@yah oo.com> wrote in message
news:db******** *************** **@posting.goog le.com...

Hi,
I have an application where I use the strncmp function extensively to
compare 2 string to see if they are the same or not. Does anyone know
a faster replacement for strncmp? I notice there is a memncmp function
which is very fast but it doesn't work the same like strncmp so I
don't think I can use it. I also tried to write the string_equal
function myself like:

int string_equal(co nst char* s1,const char* s2){
while(*s1 && *s2 && *s1 == *s2){
s1++; s2++;
}
return *s1 == *s2;
}

but I don't get much performance gain. Any suggestion?

Probably because the native strncmp is highly optimized code? E.g. doing
word-comparisons instead of char comparisons can easily give you upto
2x/4x/8x/etc speedup [based on your machine register size]. It also makes
the code a bit more complex but for strings longer than a dozen or so chars
is faster.

Tom

[Tim Prince]

"Tom St Denis" <to********@iah u.ca> wrote in message
news:RN******** ***********@new s04.bloor.is.ne t.cable.rogers. com...

"pembed2003 " <pe********@yah oo.com> wrote in message
news:db******** *************** **@posting.goog le.com...

Hi,
I have an application where I use the strncmp function extensively to
compare 2 string to see if they are the same or not. Does anyone know
a faster replacement for strncmp? I notice there is a memncmp function
which is very fast but it doesn't work the same like strncmp so I
don't think I can use it. I also tried to write the string_equal
function myself like:

int string_equal(co nst char* s1,const char* s2){
while(*s1 && *s2 && *s1 == *s2){
s1++; s2++;
}
return *s1 == *s2;
}

but I don't get much performance gain. Any suggestion?
Probably because the native strncmp is highly optimized code? E.g. doing
word-comparisons instead of char comparisons can easily give you upto
2x/4x/8x/etc speedup [based on your machine register size]. It also makes
the code a bit more complex but for strings longer than a dozen or so

chars is faster.

Tom

Combining Tom's suggestion with unrolling appropriate to the target
architecture should give additional performance on longer strings. Note
that the multi-byte comparisons won't gain speed without adjustments for
alignment, even on architectures which have alignment fixup. There's no
portable C way to optimize this for a given architecture, and then this
takes you beyond standard C on the most popular architectures.

[pembed2003]

Nick Landsberg <hu*****@att.ne t> wrote in message news:<fA******* *************** @bgtnsc05-news.ops.worldn et.att.net>...

The problem is probably not in strncmp(), but elsewhere.
No, I time the function and found out that the strcmp is the slowest
function of all. Without it (of course, I can't really remove it), the
whole function is much much faster.

Comparing strings linearly is an expensive proposition
when there are many strings to be compared. If there's
only a handful (10 or so) it's not bad, if there are
thousands, then strncmp() without an intelligent
algorithm (e.g. binary search) behind it is probably
not the way to go.
The function will eventually be moved to a server to do key/value pair
lookup so it will be called tens of thousands of times and that's why
I want to optimize it.

Try a newsgroup dealing with algorithms. Maybe
comp.programmin g?

If I can't get a good answer here, I will try there. Thanks!


pembed2003 wrote:

Hi,
I have an application where I use the strncmp function extensively to
compare 2 string to see if they are the same or not. Does anyone know
a faster replacement for strncmp? I notice there is a memncmp function
which is very fast but it doesn't work the same like strncmp so I
don't think I can use it. I also tried to write the string_equal
function myself like:

int string_equal(co nst char* s1,const char* s2){
while(*s1 && *s2 && *s1 == *s2){
s1++; s2++;
}
return *s1 == *s2;
}

but I don't get much performance gain. Any suggestion?

Thanks!

[pembed2003]

"Tom St Denis" <to********@iah u.ca> wrote in message news:<RN******* ************@ne ws04.bloor.is.n et.cable.rogers .com>...

"pembed2003 " <pe********@yah oo.com> wrote in message
news:db******** *************** **@posting.goog le.com...

Hi,
I have an application where I use the strncmp function extensively to
compare 2 string to see if they are the same or not. Does anyone know
a faster replacement for strncmp? I notice there is a memncmp function
which is very fast but it doesn't work the same like strncmp so I
don't think I can use it. I also tried to write the string_equal
function myself like:

int string_equal(co nst char* s1,const char* s2){
while(*s1 && *s2 && *s1 == *s2){
s1++; s2++;
}
return *s1 == *s2;
}

but I don't get much performance gain. Any suggestion?

Probably because the native strncmp is highly optimized code? E.g. doing
word-comparisons instead of char comparisons can easily give you upto
2x/4x/8x/etc speedup [based on your machine register size]. It also makes
the code a bit more complex but for strings longer than a dozen or so chars
is faster.

Tom

Thanks but I can't use word-comparisons because I need to know if the
strings match exactly or not, regardless of case.

[Christian Bau]

In article <db************ *************@p osting.google.c om>,
pe********@yaho o.com (pembed2003) wrote:

Hi,
I have an application where I use the strncmp function extensively to
compare 2 string to see if they are the same or not. Does anyone know
a faster replacement for strncmp? I notice there is a memncmp function
which is very fast but it doesn't work the same like strncmp so I
don't think I can use it. I also tried to write the string_equal
function myself like:

int string_equal(co nst char* s1,const char* s2){
while(*s1 && *s2 && *s1 == *s2){
This definitely does to many comparisons. If *s1 == *s2 then *s1 and *s2
are either both zero, or non of them is zero, so it is absolutely
pointless to check both of them.

s1++; s2++;
}
return *s1 == *s2;
}

but I don't get much performance gain. Any suggestion?

Instead of worrying about the performance of strncmp, you should ask
yourself why you make so many calls to it that it matters at all.

What are you doing that requires millions of calls to strncmp?

By the way, why strncmp and not strcmp?

[Christian Bau]

In article <rl************ *******@newssvr 27.news.prodigy .com>,
"Tim Prince" <tp*****@comput er.org> wrote:

Combining Tom's suggestion with unrolling appropriate to the target
architecture should give additional performance on longer strings. Note
that the multi-byte comparisons won't gain speed without adjustments for
alignment, even on architectures which have alignment fixup. There's no
portable C way to optimize this for a given architecture, and then this
takes you beyond standard C on the most popular architectures.

User code has to be portable. strncmp implementations don't.

[Christian Bau]

In article <db************ **************@ posting.google. com>,
pe********@yaho o.com (pembed2003) wrote:

The function will eventually be moved to a server to do key/value pair
lookup so it will be called tens of thousands of times and that's why
I want to optimize it.

Oh shit.

If I do a key/value pair lookup, no comparison function will be called
tens of thousands of times. Less than two compares on the average. I
suggest you buy yourself a nice book about data structures.

[Sean Kenwrick]

"pembed2003 " <pe********@yah oo.com> wrote in message
news:db******** *************** **@posting.goog le.com...

Hi,
I have an application where I use the strncmp function extensively to
compare 2 string to see if they are the same or not. Does anyone know
a faster replacement for strncmp? I notice there is a memncmp function
which is very fast but it doesn't work the same like strncmp so I
don't think I can use it. I also tried to write the string_equal
function myself like:

int string_equal(co nst char* s1,const char* s2){
while(*s1 && *s2 && *s1 == *s2){
s1++; s2++;
}
return *s1 == *s2;
}

but I don't get much performance gain. Any suggestion?

Thanks!

Have you tried forcing your compiler to use inline code rather than a
function call (either by implementing this as a Macro or by using the
'inline' keyword. You might find that setting up the stack frame (or
whatever) prior to making each call to your string_equal() function takes
just as long as the function itself.

Also it appears that you are implementing (a simplified version of) strcmp()
here NOT strncmp() and you are evaluating an extra condition in your loop
(drop the check on s2 for '\0'):.

int string_equal(co nst char * s1, const char * s2){
while(*s1 && * s1==*s2){
s1++; s2++;
}
return *s1==*s2;
}
Regarding memcmp() this is likely to be highly optimised and much faster
than strcmp(), but the problem is that you need to pass to it the length of
the strings that you are comparing. There might be a way you can make
use of memcmp() if you know that the strings are the same length. Do you
get this information somewhere earlier in your code (e.g when you first read
in the key value?). Otherwise try:

memcpy(s1,s2,st rlen(s1));

It might still be faster than doing strcmp() even with the extra strlen()
call...

Sean