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 1 of 2  [1] 2  Next page →

#18708 — More efficient strcmp

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

[toc] | [next] | [standalone]

#18712

On Tue, 13 Mar 2012 21:59:41 +0000, pembed2012 saw fit to publish the
following:

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

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

Just asking...

-- 
Women are more easily and more deeply terrified ... generating more
sheer horror than the male of the species.
		-- Spock, "Wolf in the Fold", stardate 3615.4

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

#18716

"Kleuske" <kleuske@nowhere.net> wrote in message 
news:jjogv1$iqp$2@dont-email.me...
> 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.

-- 
Bartc 

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

#18768

On Tue, 13 Mar 2012 22:25:31 +0000, BartC saw fit to publish the
following:

> "Kleuske" <kleuske@nowhere.net> wrote in message
> news:jjogv1$iqp$2@dont-email.me...
>> 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

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

#18720

On 03/13/2012 06:16 PM, Kleuske wrote:
> On Tue, 13 Mar 2012 21:59:41 +0000, pembed2012 saw fit to publish the
> following:
> 
>> 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));
>> }
> 
> What if the strings are longer than an unsigned long and differ only in the
> last bit?

Then it ends up calling strcmp(s,t), and ends up actually being slower.
That's not one of the several serious problems with this code:

1. Either s or t might not have an alignment suitable for conversion to
unsigned long*. Behavior: undefined.
2. *uls or *ult each access sizeof(unsigned long) bytes; if the strings
pointed at are shorter than that, those expressions might attempt to
access memory that the program doesn't have permission to read.
Behavior: undefined.
3. The comparison compares the entire sizeof(unsigned long) bytes, even
if that includes bytes past the end of the strings being compared.
Behavior: incorrect
4. In the unlikely case that unsigned long has padding bits, they won't
participate in the comparison. Behavior: incorrect.

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

#18727

On 2012-03-13, Kleuske <kleuske@nowhere.net> 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.

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

#18713

On 03/13/2012 05:59 PM, 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));
> }

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

Compare the results of strcmp(strings, strings+2) and
strcmp_fast(strings, strings+2).

Fast is nice; defined behavior is better; correct behavior is even better.

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

#18723

Le 13/03/12 23:19, James Kuyper a écrit :
>
> char strings[0] = "a\0a\0b";
>

?????

An array of zero chars?
And you assign a char * to it?

Can't parse that, sorry.

Maybe you wanted to write:

char *strings = "a\0a\0b";

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

#18747

James Kuyper <jameskuyper@verizon.net> writes:

> On 03/13/2012 05:59 PM, 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));
>> }
>
> char strings[0] = "a\0a\0b";

Typo:

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

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

#18762

On 03/14/2012 02:37 AM, Gareth Owen wrote:
> James Kuyper <jameskuyper@verizon.net> 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

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

#18717

On 13-Mar-12 16:59, pembed2012 wrote:
> 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));
> }

You can make lots of things faster if you aren't worried about the code
crashing or giving incorrect answers when called with valid inputs.

However, that is a rather dubious definition of "more efficient".

Note that any reasonable strcmp() implementation _does_ use the
multi-byte comparison trick; however, unlike your code, they also ensure
that the pointers are aligned, strings are not compared past their ends,
etc. so that the results are _correct_, and that does slow things down a
bit.  Ditto for memcmp().

S

-- 
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

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

#18718

On Tue, 13 Mar 2012 21:59:41 +0000 (UTC), 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.
>
>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));
>}


Which will abend on many platforms if the input strings are shorter
than four* characters (counting the NUL), and they start just before
an unallocated page.

Also, this will abend on many platforms requiring alignment, where the
input string are not, by chance, aligned on "long" boundaries.

It also won't correctly compare strings shorter than four* characters
for equality (again, counting the NUL), if the character(s) after the
string happen not to be equal.  IOW, if storage contains ('a', 'b', 0,
34) for one string, and ('a', 'b', 0, 7) for the other, you won't
compare equal.

IOW, not so much...


*Some other value on platforms where sizeof(long) is not four.

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

#18721

pembed2012 <once@was.enough.invalid> writes:

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

Without having done tests, aren't you jumping the gun by saying it's more
efficient?

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

The trouble is it doesn't work, regardless of the machine's byte
ordering.  There are two big issues.  First, a pointer to a string won't
always be correctly aligned for a larger access, and, second:

  char test[5] = {0, 0, 1};
  strcmp_fast(test, test+1);

By the way, the Campaign to Remove All Spaces from Source would no
approve of your half-hearted effort -- four whole spaces have survived
the delete key!

-- 
Ben.

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

#18827

Ben Bacarisse wrote:
> pembed2012 <once@was.enough.invalid> writes:
> 
>> 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.
> 
> Without having done tests, aren't you jumping the gun by saying it's
> more efficient?
> 
>> 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));
>> }
<snip>
> By the way, the Campaign to Remove All Spaces from Source would no
> approve of your half-hearted effort -- four whole spaces have survived
> the delete key!

I count 14 spaces (plus 6 linefeeds) that are not strictly required?

Bye, Jojo

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

#18828

"Joachim Schmitz" <nospam.jojo@schmitz-digital.de> writes:

> Ben Bacarisse wrote:
>> pembed2012 <once@was.enough.invalid> writes:
>>
>>> 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.
>>
>> Without having done tests, aren't you jumping the gun by saying it's
>> more efficient?
>>
>>> 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));
>>> }
> <snip>
>> By the way, the Campaign to Remove All Spaces from Source would no
>> approve of your half-hearted effort -- four whole spaces have survived
>> the delete key!
>
> I count 14 spaces (plus 6 linefeeds) that are not strictly required?

CRASS laments the fact, but very few people go all the way -- I was
assuming a style that had some indentation (and therefore also line
break) rules.

But, yes, you are right, a truly committed supporter of CRASS would go
much further.

-- 
Ben.

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

#18725

On 2012-03-13, pembed2012 <once@was.enough.invalid> 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? :)

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

#18766

Kaz Kylheku <kaz@kylheku.com> wrote:

> On 2012-03-13, pembed2012 <once@was.enough.invalid> 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.

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

#18771

On 3/14/2012 10:55 AM, Fritz Wuehler wrote:
> Kaz Kylheku<kaz@kylheku.com>  wrote:
>
>> On 2012-03-13, pembed2012<once@was.enough.invalid>  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 ;-)

Unless "spit" was not a verb, but rather part of the term "coffee spit", 
which is what needs to be wiped from the monitor?  ;-)

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

:-)

-- 
Kenneth Brody

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

#18733

"pembed2012" <once@was.enough.invalid> wrote in message 
news:jjog0d$rcc$1@speranza.aioe.org...

> 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
 

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

#18739

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

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web