Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > More efficient strcmp

Reply
Thread Tools

More efficient strcmp

 
 
Kaz Kylheku
Guest
Posts: n/a
 
      03-13-2012
On 2012-03-13, Kleuske <(E-Mail Removed)> wrote:
> On Tue, 13 Mar 2012 21:59:41 +0000, pembed2012 saw fit to publish the
>> int strcmp_fast(char* s,char* t){
>> uls=(unsigned long*)s;
>> ult=(unsigned long*)t;
>> if(*uls>*ult) return(1);
>> if(*uls<*ult) return(-1);
>> else return(strcmp(s,t));
>> }

>
> What if the strings are longer than an unsigned long and differ only in the
> last bit?


More importantly, what if they are shorter?

What if the compiler doesn't like the aliasing?

Also, this fails on x86 and elsewhere, because strings, if treated as numbers this way, are
big-endian.
 
Reply With Quote
 
 
 
 
BartC
Guest
Posts: n/a
 
      03-13-2012


"pembed2012" <(E-Mail Removed)> wrote in message
news:jjog0d$rcc$(E-Mail Removed)...

> int strcmp_fast(char* s,char* t){
> uls=(unsigned long*)s;
> ult=(unsigned long*)t;
> if(*uls>*ult) return(1);
> if(*uls<*ult) return(-1);
> else return(strcmp(s,t));
> }


That won't work well for various reasons already explained.

Try inventing a fast strcmp_eq() function instead; usually I only care about
equality, not whether one string is more or less than other.

That also means that endianness doesn't come into it so much. And if the
caller happens to have the string lengths already available, have a version
that makes use of that (which can be really fast when the lengths are
different).

However you'll have a job beating a good built-in strcmp(), unless you do
already have the lengths, to give you an edge.

--
Bartc


 
Reply With Quote
 
 
 
 
Bl0ckeduser
Guest
Posts: n/a
 
      03-14-2012
pembed2012 wrote:
> Dear friends
>
> I have created a more efficient strcmp function. However it only works on
> big endian architectures. I would like someone with same to run some
> timing tests to see how much is the speed up.
>
> Thank you
>
> int strcmp_fast(char* s,char* t){
> uls=(unsigned long*)s;
> ult=(unsigned long*)t;
> if(*uls>*ult) return(1);
> if(*uls<*ult) return(-1);
> else return(strcmp(s,t));
> }


This slightly modified version also works on a little-endian machine,
but I'm not sure if it's quite as fast as yours.

int strcmp_recursive(char* s,char* t){
if(!*s && *s==*t) return(0);
if(*s>*t) return(1);
if(*s<*t) return(-1);
return(strcmp_recursive(s+1,t+1));
}
 
Reply With Quote
 
James Kuyper
Guest
Posts: n/a
 
      03-14-2012
On 03/14/2012 02:37 AM, Gareth Owen wrote:
> James Kuyper <(E-Mail Removed)> writes:

....
>> char strings[0] = "a\0a\0b";

>
> Typo:
>
> char strings[] = "a\0a\0b"; // mutable
> const char *strings = "a\0a\0b"; // immutable


Aiee! Where'd that first 0 come from? I don't remember typing it.
I meant my example to be mutable, since, for some reason, strcmp_fast()
takes char* arguments.
--
James Kuyper
 
Reply With Quote
 
Andre
Guest
Posts: n/a
 
      03-14-2012
On 13.03.2012 22:59, pembed2012 wrote:
> Dear friends
>
> I have created a more efficient strcmp function. However it only works on
> big endian architectures. I would like someone with same to run some
> timing tests to see how much is the speed up.
>
> Thank you
>
> int strcmp_fast(char* s,char* t){
> uls=(unsigned long*)s;
> ult=(unsigned long*)t;
> if(*uls>*ult) return(1);
> if(*uls<*ult) return(-1);
> else return(strcmp(s,t));
> }


A string (or at least a substring) may start at an odd address, and some
hardware architectures will fail if you try to cast this to a long...
 
Reply With Quote
 
Fritz Wuehler
Guest
Posts: n/a
 
      03-14-2012
Kaz Kylheku <(E-Mail Removed)> wrote:

> On 2012-03-13, pembed2012 <(E-Mail Removed)> wrote:
> > Dear friends
> >
> > I have created a more efficient strcmp function.

>
> Gee, thanks a lot.
>
> Now, you wouldn't happen to have a more efficient paper towel for wiping coffee
> spit from a monitor?


if your monitor is spitting coffee may i suggest perhaps your monitor is
actually a faulty coffee maker? in case it's not then microfiber rags work a
treat for that, ask me how i know

watching a dope get his arse handed to him by the pros here is one of the
best things about this newsgroup. high in content and amusement all at once.

 
Reply With Quote
 
Kleuske
Guest
Posts: n/a
 
      03-14-2012
On Tue, 13 Mar 2012 22:25:31 +0000, BartC saw fit to publish the
following:

> "Kleuske" <(E-Mail Removed)> wrote in message
> news:jjogv1$iqp$(E-Mail Removed)...
>> On Tue, 13 Mar 2012 21:59:41 +0000, pembed2012 saw fit to publish the
>> following:

>
>>> I have created a more efficient strcmp function. However it only works
>>> on big endian architectures. I would like someone with same to run
>>> some timing tests to see how much is the speed up.

>
>>> int strcmp_fast(char* s,char* t){
>>> uls=(unsigned long*)s;
>>> ult=(unsigned long*)t;
>>> if(*uls>*ult) return(1);
>>> if(*uls<*ult) return(-1);
>>> else return(strcmp(s,t));
>>> }

>>
>> What if the strings are longer than an unsigned long and differ only in
>> the
>> last bit?

>
> Or shorter.


Ouch!

.... I should have seen that ...

--
Murder is contrary to the laws of man and God.
-- M-5 Computer, "The Ultimate Computer", stardate 4731.3
 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      03-14-2012
Bl0ckeduser <(E-Mail Removed)> writes:

> pembed2012 wrote:
>> Dear friends
>>
>> I have created a more efficient strcmp function. However it only
>> works on big endian architectures. I would like someone with same to
>> run some timing tests to see how much is the speed up.
>>
>> Thank you
>>
>> int strcmp_fast(char* s,char* t){
>> uls=(unsigned long*)s;
>> ult=(unsigned long*)t;
>> if(*uls>*ult) return(1);
>> if(*uls<*ult) return(-1);
>> else return(strcmp(s,t));
>> }

>
> This slightly modified version also works on a little-endian machine,
> but I'm not sure if it's quite as fast as yours.
>
> int strcmp_recursive(char* s,char* t){
> if(!*s && *s==*t) return(0);
> if(*s>*t) return(1);
> if(*s<*t) return(-1);
> return(strcmp_recursive(s+1,t+1));
> }


You have made an important semantic change (not counting the
changes that allow termination and provide for returning 0
if the strings are equal). Do you see what it is? Hint:
this version of strcmp does not match the specification for
strcmp() in the standard library (even ignoring the 'const'
modifiers in strcmp()'s prototype).

By the way, 'return' statements don't need parentheses
around the return expression. The statements

return 0;
return strcmp_recursive( s+1, t+1 );

will work just fine.
 
Reply With Quote
 
Bl0ckeduser
Guest
Posts: n/a
 
      03-14-2012
Tim Rentsch wrote:
> You have made an important semantic change (not counting the
> changes that allow termination and provide for returning 0
> if the strings are equal). Do you see what it is? Hint:
> this version of strcmp does not match the specification for
> strcmp() in the standard library (even ignoring the 'const'
> modifiers in strcmp()'s prototype).


Hmm, I have to do the comparisons using the unsigned char type (or
perhaps another unsigned type, like the OP), right ?

> By the way, 'return' statements don't need parentheses
> around the return expression. The statements
>
> return 0;
> return strcmp_recursive( s+1, t+1 );
>
> will work just fine.


By the way, thanks for reviewing my code . As a hobbyist, it's always
a thrill to talk with experts.
 
Reply With Quote
 
vaysagekv
Guest
Posts: n/a
 
      03-15-2012
On 14/03/12 3:29 AM, pembed2012 wrote:
> Dear friends
>
> I have created a more efficient strcmp function. However it only works on
> big endian architectures. I would like someone with same to run some
> timing tests to see how much is the speed up.
>
> Thank you
>
> int strcmp_fast(char* s,char* t){
> uls=(unsigned long*)s;
> ult=(unsigned long*)t;
> if(*uls>*ult) return(1);
> if(*uls<*ult) return(-1);
> else return(strcmp(s,t));
> }

Do you mean
int strcmp_fast(char* s,char* t){
unsigned long* uls=(unsigned long*)s;
unsigned long* ult=(unsigned long*)t;
if(*uls>*ult) return(1);
if(*uls<*ult) return(-1);
else return(strcmp(s,t));
}

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
segfault when strcmp Robert Mens C Programming 6 10-23-2003 02:53 AM
strcmp muser C++ 6 10-09-2003 08:18 AM
strcmp problem Shane Peck C++ 6 09-22-2003 05:44 PM
strcmp but with '\n' as the terrminator Allan Bruce C Programming 53 07-30-2003 07:38 PM
please help with strcmp() Andrej Hocevar C Programming 3 07-19-2003 04:41 PM



Advertisments