Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #18708 > unrolled thread

More efficient strcmp

Back to article view | Back to comp.lang.c

Contents

  More efficient strcmp pembed2012 <once@was.enough.invalid> - 2012-03-13 21:59 +0000
    Re: More efficient strcmp Kleuske <kleuske@nowhere.net> - 2012-03-13 22:16 +0000
      Re: More efficient strcmp "BartC" <bc@freeuk.com> - 2012-03-13 22:25 +0000
        Re: More efficient strcmp Kleuske <kleuske@nowhere.net> - 2012-03-14 16:02 +0000
      Re: More efficient strcmp James Kuyper <jameskuyper@verizon.net> - 2012-03-13 18:30 -0400
      Re: More efficient strcmp Kaz Kylheku <kaz@kylheku.com> - 2012-03-13 23:05 +0000
    Re: More efficient strcmp James Kuyper <jameskuyper@verizon.net> - 2012-03-13 18:19 -0400
      Re: More efficient strcmp jacob navia <jacob@spamsink.net> - 2012-03-13 23:54 +0100
      Re: More efficient strcmp Gareth Owen <gwowen@gmail.com> - 2012-03-14 06:37 +0000
        Re: More efficient strcmp James Kuyper <jameskuyper@verizon.net> - 2012-03-14 07:32 -0400
    Re: More efficient strcmp Stephen Sprunk <stephen@sprunk.org> - 2012-03-13 17:28 -0500
    Re: More efficient strcmp Robert Wessel <robertwessel2@yahoo.com> - 2012-03-13 17:28 -0500
    Re: More efficient strcmp Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-13 22:43 +0000
      Re: More efficient strcmp "Joachim Schmitz" <nospam.jojo@schmitz-digital.de> - 2012-03-16 17:39 +0100
        Re: More efficient strcmp Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-16 18:17 +0000
    Re: More efficient strcmp Kaz Kylheku <kaz@kylheku.com> - 2012-03-13 23:03 +0000
      Re: More efficient strcmp Fritz Wuehler <fritz@spamexpire-201203.rodent.frell.theremailer.net> - 2012-03-14 15:55 +0100
        Re: More efficient strcmp Kenneth Brody <kenbrody@spamcop.net> - 2012-03-14 14:19 -0400
    Re: More efficient strcmp "BartC" <bc@freeuk.com> - 2012-03-13 23:25 +0000
    Re: More efficient strcmp Bl0ckeduser <bl0ckedusersoft@gmail.com> - 2012-03-13 21:42 -0500
      Re: More efficient strcmp Tim Rentsch <txr@alumni.caltech.edu> - 2012-03-14 15:17 -0700
        Re: More efficient strcmp Bl0ckeduser <bl0ckedusersoft@gmail.com> - 2012-03-14 19:06 -0400
          Re: More efficient strcmp Tim Rentsch <txr@alumni.caltech.edu> - 2012-03-15 18:53 -0700
    Re: More efficient strcmp Andre <lodwig@pathme.de> - 2012-03-14 14:26 +0100
    Re: More efficient strcmp China Blue Water Navy <chine.bleu@yahoo.com> - 2012-03-14 12:39 -0700
    Re: More efficient strcmp vaysagekv <kvvaysage@gmail.com> - 2012-03-15 18:24 +0530
      Re: More efficient strcmp gof@somewhere.invalid (Gof) - 2012-03-15 13:00 +0000
        Re: More efficient strcmp "BartC" <bc@freeuk.com> - 2012-03-15 15:05 +0000
          Re: More efficient strcmp Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-03-25 16:45 +0000

Page 2 of 2 — ← Prev page 1 [2]

#18783

Bl0ckeduser <bl0ckedusersoft@gmail.com> 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.

[toc] | [prev] | [next] | [standalone]

#18786

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.

[toc] | [prev] | [next] | [standalone]

#18822

Bl0ckeduser <bl0ckedusersoft@gmail.com> writes:

> 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 ?

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.

You're welcome.  Some other ideas, starting at the previous
version:

> 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));
> }


Personally I prefer more use of horizontal white space.
Also, sometimes you may want to combine several cases
into a single return and then using a conditional expression
in the return statement:

   int
   ustrcmp( const unsigned char *s, const unsigned char *t ){
       if(  *s != *t  ||  *s == 0  )  return  *s<*t ? -1 : *s>*t ? 1 : 0;
       return  ustrcmp( s+1, t+1 );
   }

There is a well-known idiom for the expression in the first
return statement:

   int
   ustrcmp( const unsigned char *s, const unsigned char *t ){
       if(  *s != *t  ||  *s == 0  )  return  (*s > *t) - (*s < *t);
       return  ustrcmp( s+1, t+1 );
   }

We can use the conditional-expression-folding technique again to
reduce this last version to a single return statement;

   int
   ustrcmp( const unsigned char *s, const unsigned char *t ){
       return  *s && *s == *t  ?  ustrcmp( s+1, t+1 )  :  (*s>*t) - (*s<*t);
   }

Obviously the sub-branches of the conditional expression could
be written in the other order with the condition reversed;
it depends on how you think of the function as working.

Please bear in mind, I don't mean to advocate any of these as
being better than some other way of writing this function.
But I think it's useful to see different variations and go
back and forth between them easily.

[toc] | [prev] | [next] | [standalone]

#18765

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...

[toc] | [prev] | [next] | [standalone]

#18776

In article <jjog0d$rcc$1@speranza.aioe.org>,
 pembed2012 <once@was.enough.invalid> 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.

Some implementation already do this. They can also check alignment and other 
issues. You can use this on little endian to find the first different word and 
then analyze that (or use byte swapping instructions if available).

-- 
My name Indigo Montoya.      |    R'lyeh 38o57'6.5''S 102o51'16''E.
You flamed my father.        |       I'm whoever you want me to be.
Prepare to be spanked.       |  Annoying Usenet one post at a time.
Stop posting that!           |    At least I can stay in character.

[toc] | [prev] | [next] | [standalone]

#18797

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));
  }

[toc] | [prev] | [next] | [standalone]

#18799

vaysagekv <kvvaysage@gmail.com> wrote:

>  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));
>  }

Besides obvious misconceptions, pointed by other people in this thread, 
I'm sensitive to constness of variables and arguments. By passing pointers 
to a function without const qualifiers, you make people think that your 
function is going to modify the strings.

I think that it would be better this way (still with errors mentoined 
in other posts):

int strcmp_fast(const char *s, const char *t)
{
	const unsigned long *uls = (const unsigned long *) s;
	const unsigned long *ult = (const unsigned long *) t;

	if (*uls > *ult)
		return 1;

	if (*uls < *ult)
		return -1;

	return strcmp(s, t);
}

-- 
Gof

[toc] | [prev] | [next] | [standalone]

#18801

"Gof" <gof@somewhere.invalid> wrote in message 
news:gof.1331816103.22577@somewhere.invalid...
> vaysagekv <kvvaysage@gmail.com> wrote:
>
>>  Do you mean
>>   int strcmp_fast(char* s,char* t){
>>    unsigned long* uls=(unsigned long*)s;

> Besides obvious misconceptions, pointed by other people in this thread,
> I'm sensitive to constness of variables and arguments. By passing pointers
> to a function without const qualifiers, you make people think that your
> function is going to modify the strings.
>
> I think that it would be better this way (still with errors mentoined
> in other posts):
>
> int strcmp_fast(const char *s, const char *t)
> {
> const unsigned long *uls = (const unsigned long *) s;
> const unsigned long *ult = (const unsigned long *) t;
>
> if (*uls > *ult)
> return 1;
>
> if (*uls < *ult)
> return -1;
>
> return strcmp(s, t);
> }

That's fine. But you've turned a simple function that could be taken in at a 
glance, into something where you almost have to hunt for the code amidst all 
the 'consts'!

Wouldn't just a comment to the same effect do?

-- 
Bartc

 

[toc] | [prev] | [next] | [standalone]

#19028

On Thu, 2012-03-15, BartC wrote:
> "Gof" <gof@somewhere.invalid> wrote in message 
> news:gof.1331816103.22577@somewhere.invalid...
>> vaysagekv <kvvaysage@gmail.com> wrote:
>>
>>>  Do you mean
>>>   int strcmp_fast(char* s,char* t){
>>>    unsigned long* uls=(unsigned long*)s;
>
>> Besides obvious misconceptions, pointed by other people in this thread,
>> I'm sensitive to constness of variables and arguments. By passing pointers
>> to a function without const qualifiers, you make people think that your
>> function is going to modify the strings.
>>
>> I think that it would be better this way (still with errors mentoined
>> in other posts):
>>
>> int strcmp_fast(const char *s, const char *t)
>> {
>> const unsigned long *uls = (const unsigned long *) s;
>> const unsigned long *ult = (const unsigned long *) t;
>>
>> if (*uls > *ult)
>> return 1;
>>
>> if (*uls < *ult)
>> return -1;
>>
>> return strcmp(s, t);
>> }
>
> That's fine. But you've turned a simple function that could be taken in at a 
> glance, into something where you almost have to hunt for the code amidst all 
> the 'consts'!
>
> Wouldn't just a comment to the same effect do?

No; people expect to see such things expressed using the 'const'
keyword rather than using comments. If I see a comment saying "I won't
be modifying this piece of data, honest" I get suspicious.

(Not that I understand what the code is trying to do. I haven't
followed the thread, but it seems fundamentally broken, with or
without const.)

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c

csiph-web