string comparison

[Al Bowers]

Re: string comparison



Ben Pfaff wrote:[color=blue]
> Netocrat <netocrat@dodo. com.au> writes:
>
>[color=green]
>>Actually that's useless as a fix per your words - instead:
>> return *a == *b ? 0 : *a > *b ? 1 : -1;
>>
>>There are probably cheaper ways to do this knowing details about the
>>implementatio n but this is hopefully a strictly compatible general
>>version.[/color]
>
>
> Here's my favorite version. I got it from someone here on clc
> but don't remember whom:
> return *a < *b ? -1 : *a > *b;[/color]

It's ok, but I don't believe you would need the last comparison
if you check equaity(requiri ng a return of 0) within the loop.

while(*a++ == *b++)
if(*a == '\0') return 0;
return *a<*b?-1:1;

--
Al Bowers
Tampa, Fl USA
mailto: xabowers@myrapi dsys.com (remove the x to send email)

http://www.geocities.com/abowers822/

[Al Bowers]

Re: string comparison



Al Bowers wrote:
[color=blue]
>
>
> Ben Pfaff wrote:
>[color=green]
>> Netocrat <netocrat@dodo. com.au> writes:
>>
>>[color=darkred]
>>> Actually that's useless as a fix per your words - instead:
>>> return *a == *b ? 0 : *a > *b ? 1 : -1;
>>>
>>> There are probably cheaper ways to do this knowing details about the
>>> implementation but this is hopefully a strictly compatible general
>>> version.[/color]
>>
>>
>>
>> Here's my favorite version. I got it from someone here on clc
>> but don't remember whom:
>> return *a < *b ? -1 : *a > *b;[/color]
>
>
> It's ok, but I don't believe you would need the last comparison
> if you check equaity(requiri ng a return of 0) within the loop.
>
> while(*a++ == *b++)
> if(*a == '\0') return 0;
> return *a<*b?-1:1;
>[/color]

That should be a for loop.
for( ; *a == *b; a++,b++)
if(*a == '\0') return 0;
return *a<*b?-1:1;

--
Al Bowers
Tampa, Fl USA
mailto: xabowers@myrapi dsys.com (remove the x to send email)

http://www.geocities.com/abowers822/

[Rajan]

Re: string comparison

Yadur,
I have written the strcmp function , let me just paste it here.
You don't need to do a seperate length comparison , you just need to
check for each of the arguments.

int strcmp(const char* a1, const char* b1)
{
while (*a1 == *b1)
{
if ((*a1 == '\0') && (*b1 == '\0'))
{
return 0;
}
a1++;
b1++;
}
return(*a1 - *b1);
}

[pete]

Re: string comparison

Rajan wrote:[color=blue]
>
> Yadur,
> I have written the strcmp function , let me just paste it here.
> You don't need to do a seperate length comparison , you just need to
> check for each of the arguments.
>
> int strcmp(const char* a1, const char* b1)
> {
> while (*a1 == *b1)
> {
> if ((*a1 == '\0') && (*b1 == '\0'))[/color]

There's no point in checking both *a1 and *b1
for equality with zero,
since you already know that *a1 == *b1 at this point in code.
[color=blue]
> {
> return 0;
> }
> a1++;
> b1++;
> }
> return(*a1 - *b1);
> }[/color]

That's wrong.
Any character compared with strcmp
has to give the same result as if compared by memcmp.

int str_cmp(const char *s1, const char *s2)
{
const unsigned char *p1 = (const unsigned char *)s1;
const unsigned char *p2 = (const unsigned char *)s2;

while (*p1 == *p2) {
if (*p1 == '\0') {
return 0;
}
++p1;
++p2;
}
return *p2 > *p1 ? -1 : 1;
}

N869
7.21.4 Comparison functions
[#1] The sign of a nonzero value returned by the comparison
functions memcmp, strcmp, and strncmp is determined by the
sign of the difference between the values of the first pair
of characters (both interpreted as unsigned char) that
differ in the objects being compared.

--
pete

[Rajan]

Re: string comparison

Pete,
I think you should do a "man strcmp" and check because if whenever you
compare let's say "Raj" and "Rajendra" it will always give you the
difference as ascii value of '\0' - ascii value of 'e' which comes to
-101.
It's not the same as memcmp. memcmp compares the number of bytes for
any data type unlike strcmp which is specifically for const char*.
Write a simple program using strcmp function and check the retval.

[pete]

Re: string comparison

Ben Pfaff wrote:[color=blue]
>
> Netocrat <netocrat@dodo. com.au> writes:
>[color=green]
> > Actually that's useless as a fix per your words - instead:
> > return *a == *b ? 0 : *a > *b ? 1 : -1;
> >
> > There are probably cheaper ways to do this knowing details about the
> > implementation but this is hopefully a strictly compatible general
> > version.[/color]
>
> Here's my favorite version. I got it from someone here on clc
> but don't remember whom:
> return *a < *b ? -1 : *a > *b;[/color]

It wasn't me.

I usually write that as:
return *b > *a ? -1 : *a != *b;
Sometimes as:
return *b > *a ? -1 : *a > *b;

because I like to write sorting functions
in terms of only a GT(,) macro.

#define GT(A, B) (*(A) > *(B))
/* The above macro is for arithmetic types only */

static int comp(const void *arg1, const void *arg2)
{
return GT((e_type*)arg 2, (e_type*)arg1)
? -1 : GT((e_type*)arg 1, (e_type*)arg2);
}

The above comp function,
would be for a function with a qsort interface,
which is comparing arithmetic types.

For functions which only can sort one dimensional arrays,
the GT(,) macro can be used directly.

void s3sort(e_type *array, size_t nmemb)
{
e_type temp, *i, *j, *k, *after;

after = array + nmemb;
if (nmemb > (size_t)-1 / 3 - 1) {
nmemb = nmemb / 3 - 1;
} else {
nmemb = (3 * nmemb + 1) / 7;
}
while (nmemb != 0) {
i = array + nmemb;
do {
j = i - nmemb;
if (GT(j, i)) {
k = i;
temp = *k;
do {
*k = *j;
k = j;
if (nmemb + array > j) {
break;
}
j -= nmemb;
} while (GT(j, &temp));
*k = temp;
}
++i;
} while (i != after);
nmemb = (3 * nmemb + 1) / 7;
}
}

The GT(,) macro can be made more complicated to do other things
like to sort an array string pointers by string length.

#define GT(A, B) (lencomp((A), (B)) > 0)

int lencomp(const void *a, const void *b)
{
const size_t a_len = strlen(*(char **)a);
const size_t b_len = strlen(*(char **)b);

return b_len > a_len ? -1 : a_len != b_len;
}

--
pete

[pete]

Re: string comparison

Rajan wrote:[color=blue]
>
> Pete,
> I think you should do a "man strcmp"[/color]

I think you should realise that the C standard defines the language,
and that "man" doesn't define the language.
The contents of your man pages are only
topical on this newsgroup to the extent
that they are right if they agree with the standard,
and that they are wrong if they disagree wiht the C standard.

ISO/IEC 9899:1999(E)
7.21.4 Comparison functions
1 The sign of a nonzero value returned by the comparison
functions memcmp, strcmp, and strncmp is determined by
the sign of the difference between the values of the first
pair of characters (both interpreted as unsigned char)
that differ in the objects being compared.

--
pete

[Netocrat]

Re: string comparison

On Thu, 23 Jun 2005 01:50:19 +0000, CBFalconer wrote:
[color=blue]
> Netocrat wrote:[color=green]
>>[/color]
> ... snip ...[color=green]
>>
>> No probs, I'm a new poster so you don't have much reference on my
>> perspective. It was good of you to be so gracious.[/color]
>
> Now that's rare. Calling any of us "gracious". We usually only get
> one-half of that number of letters.[/color]

But hang on, how do any of you get any programming done if you're all
Chief Information Officers.... oh, OK, not half of _those_ letters...

[Lawrence Kirby]

Re: string comparison

On Thu, 23 Jun 2005 05:46:57 +1000, Netocrat wrote:

....
[color=blue][color=green]
>> Similarly you need a
>> postamble to handle the last few bytes.[/color]
>
> Which I had; although correct me if you don't think it works as it should
> (it tested fine)...
>[color=green][color=darkred]
>>> while (ua < ua_max) {
>>> if (*ua > *ub)[/color][/color][/color]

This makes big assumptions abut the representation of integers in the
platform. It won't work if they contain any padding bits or use anything
other than big endian byte order. And technically speaking C's type
aliasing rules disallow this.
[color=blue][color=green]
>> ... snip code ...[color=darkred]
>>>
>>> This version is approximately 3 times faster than glibc and my original
>>> version, which surprised me. Is there any reason to _not_ make the
>>> assumption that I made - that we should operate on units of sizeof(int)
>>> rather than sizeof(char)? It may not necessarily improve performance -
>>> it certainly improves it on my setup - but could it degrade it?[/color][/color][/color]

Were you comparing equal data?

....
[color=blue]
> What you say makes sense, although alignment isn't an issue in my case. I
> wanted to see if, as you suggest is possible, the small comparison is
> degraded by my code as it seems it would be. So I re-tested and instead
> of setting the length of the random memory to 100 bytes I varied this
> length from 1 to 10 bytes. Anything over 3 bytes was faster; less than
> that and the library was faster.
>
> Length Speed of new version vs library
> 1 3 x slower
> 2 2 x slower
> 3 2 x slower
> 4 2.5 x faster
> 5 2.5 x faster
> 6 2 x faster
> 7 slightly faster
> 8 2.5 x faster
> 9 2 x faster
> 10 2 x faster
> 11 2 x faster
>
> It may be debatable whether the implementors made the right choice -
> what's the average length of data that memcmp() is used for? - I suspect a
> lot more than 3 bytes - but I don't suppose it's really on topic here.[/color]

The average length of data being compared is not important for non-equal
data, what is important is the position of the first character that
differs. For "random" data this will be the first character tested the
great majority of the time.

These are techniques available for the implementation to use for
standard library functions if the implementor chooses. They are not
normally techniques a program should use.

Lawrence

[Lawrence Kirby]

Re: string comparison

On Wed, 22 Jun 2005 20:34:00 -0700, Peter Nilsson wrote:
[color=blue]
> CBFalconer wrote:[color=green]
>> Try:
>> int compare_strings (char *a, char *b)
>> {
>> unsigned char *ua = a, *ub = b;
>> ...
>> ... No overflow. No casts.[/color]
>
> Just a required diagnostic from the constraint violation. ;)[/color]

Fix that and add const because the string aren't being modified and we
might be getting somewhere. :-)

Lawrence

[Lawrence Kirby]

Re: string comparison

On Wed, 22 Jun 2005 18:43:59 -0700, Ben Pfaff wrote:
[color=blue]
> Netocrat <netocrat@dodo. com.au> writes:
>[color=green]
>> Actually that's useless as a fix per your words - instead:
>> return *a == *b ? 0 : *a > *b ? 1 : -1;
>>
>> There are probably cheaper ways to do this knowing details about the
>> implementation but this is hopefully a strictly compatible general
>> version.[/color]
>
> Here's my favorite version. I got it from someone here on clc
> but don't remember whom:
> return *a < *b ? -1 : *a > *b;[/color]

I have vague recollections about that, but it was a long time ago,
probably in the previous millennium.

Lawrence

[lawrence.jones@ugs.com]

Re: string comparison

Ben Pfaff <blp@cs.stanfor d.edu> wrote:[color=blue]
>
> Here's my favorite version. I got it from someone here on clc
> but don't remember whom:
> return *a < *b ? -1 : *a > *b;[/color]

My favorite is the conditionless form:

return (*a > *b) - (*a < *b);

-Larry Jones

I suppose if I had two X chromosomes, I'd feel hostile too. -- Calvin

[Netocrat]

Re: string comparison

On Thu, 23 Jun 2005 13:52:50 +0100, Lawrence Kirby wrote:
[color=blue]
> On Thu, 23 Jun 2005 05:46:57 +1000, Netocrat wrote:
>
> ...
>[color=green][color=darkred]
>>> Similarly you need a
>>> postamble to handle the last few bytes.[/color]
>>
>> Which I had; although correct me if you don't think it works as it
>> should (it tested fine)...
>>[color=darkred]
>>>> while (ua < ua_max) {
>>>> if (*ua > *ub)[/color][/color]
>
> This makes big assumptions abut the representation of integers in the
> platform. It won't work if they contain any padding bits or use anything
> other than big endian byte order. And technically speaking C's type
> aliasing rules disallow this.[/color]

Where can I verify this from documentation - not that I don't believe
you, just that I'd like to know how to find these things out without
asking on the group? I know you can buy the standard, but I'd rather not
spend money. What are my options?

Since I posted I have realised that it is actually failing - my processor
is little endian...
[color=blue][color=green][color=darkred]
>>> ... snip code ...
>>>>
>>>> This version is approximately 3 times faster than glibc and my
>>>> original version, which surprised me. Is there any reason to _not_
>>>> make the assumption that I made - that we should operate on units of
>>>> sizeof(int) rather than sizeof(char)? It may not necessarily improve
>>>> performance - it certainly improves it on my setup - but could it
>>>> degrade it?[/color][/color]
>
> Were you comparing equal data?[/color]

I intended that it was random but didn't explicitly randomise it; and I
think that the memory block malloc was returning was zeroed for these
tests, although it's impossible to go back and check... I am now
explicitly setting each byte to a random value. So for the data above,
yes, it probably was all equal.
[color=blue][color=green]
>> What you say makes sense, although alignment isn't an issue in my case.
>> I wanted to see if, as you suggest is possible, the small comparison is
>> degraded by my code as it seems it would be. So I re-tested and
>> instead of setting the length of the random memory to 100 bytes I
>> varied this length from 1 to 10 bytes. Anything over 3 bytes was
>> faster; less than that and the library was faster.
>>
>> Length Speed of new version vs library 1 3 x slower 2 2 x slower 3
>> 2 x slower
>> 4 2.5 x faster
>> 5 2.5 x faster
>> 6 2 x faster
>> 7 slightly faster
>> 8 2.5 x faster
>> 9 2 x faster
>> 10 2 x faster
>> 11 2 x faster
>>
>> It may be debatable whether the implementors made the right choice -
>> what's the average length of data that memcmp() is used for? - I
>> suspect a lot more than 3 bytes - but I don't suppose it's really on
>> topic here.[/color]
>
> The average length of data being compared is not important for non-equal
> data, what is important is the position of the first character that
> differs. For "random" data this will be the first character tested the
> great majority of the time.[/color]

Well put.

<Off-topic (lots of it)>
It so happens that the data was probably equal for the post to which you
responded. I tested again, this time with equal data except for the final
compared byte which was alternately less than and greater than. I also
re-ordered the inner while loop of my naive memcmp to be:
if (*ua == *ub) {
ua++;
ub++;
} else if (*ua < *ub)
return -1;
else
return 1;

The results that I got are different to those I posted above - those above
were done pretty roughly so I may have made an error translating from
times to relative performance. Anyhow, for all lengths less than or equal
to 10, both of my functions out-perform the library when all data bar
the last byte is the same. Here are some very rough relative times:

Length Library Naive Word-based
0 2.782063 0.824878 1.026883
1 3.839585 1.794128 1.536425
2 3.979533 1.936510 1.711663
3 4.487526 2.082990 2.091040
4 4.911784 2.249875 4.031234
5 5.433289 2.392460 2.443990
6 5.142204 3.054199 2.226923
7 5.226639 3.310050 2.500838
8 5.122240 3.394408 4.416643
9 5.741017 3.498679 2.579461
10 5.832017 4.845331 3.007469
11 6.545730 5.683157 3.090258
12 6.340615 6.557857 4.964385
13 6.434350 6.702367 3.512579
14 6.485347 6.534230 3.369173
15 6.735006 7.560720 4.631879
16 8.304644 6.969153 4.455131
17 6.899765 6.990281 3.269464
18 7.499913 7.809836 4.871980
19 7.754756 7.356656 6.513516
20 8.369894 7.477097 5.325045
....
300 61.002508 65.282563 34.535567
301 61.211380 66.803313 33.170267
302 67.950986 66.556912 33.923567
303 66.034115 67.561750 32.898632

In all of these tests the word-based function far outperforms the library
function - although as I have noted, the endian-ness causes errors.
The naive approach is very similar in time to the library version and
sometimes faster; suggesting that no tricks/optimisations are being used
in the library version.

Intel chips seem to support an op-code that compares a 32-bit value in
byte-order, so I'm going to inline that into my function with some
assembly in gcc and see if I can get both a correct result and also
maintain the performance boost that this function provides, which I
suspect is possible. If so it would be an appropriate way to optimise the
intel version of glibc's memcpy function.

</Off-topic>
[color=blue]
> These are techniques available for the implementation to use for
> standard library functions if the implementor chooses. They are not
> normally techniques a program should use.[/color]

That's what I wanted to know. Cheers.

[Lawrence Kirby]

Re: string comparison

On Sat, 25 Jun 2005 02:59:23 +1000, Netocrat wrote:
[color=blue]
> On Thu, 23 Jun 2005 13:52:50 +0100, Lawrence Kirby wrote:
>[color=green]
>> On Thu, 23 Jun 2005 05:46:57 +1000, Netocrat wrote:
>>
>> ...
>>[color=darkred]
>>>> Similarly you need a
>>>> postamble to handle the last few bytes.
>>>
>>> Which I had; although correct me if you don't think it works as it
>>> should (it tested fine)...
>>>
>>>>> while (ua < ua_max) {
>>>>> if (*ua > *ub)[/color]
>>
>> This makes big assumptions abut the representation of integers in the
>> platform. It won't work if they contain any padding bits or use anything
>> other than big endian byte order. And technically speaking C's type
>> aliasing rules disallow this.[/color]
>
> Where can I verify this from documentation - not that I don't believe
> you, just that I'd like to know how to find these things out without
> asking on the group? I know you can buy the standard, but I'd rather not
> spend money. What are my options?[/color]

You could download a draft version of the standard or buy a good book. Of
course buying a book implies spending money and isn't guaranteed to be
accurate or complete. Drafts are also not going to be 100% accurate but at
least are based on the actual text of the standard.

The aliasing rules I referred to are in C99 6.5p7:

An object shall have its stored value accessed only by an lvalue
expression that has one of the following types:73)
- a type compatible with the effective type of the object,
- a qualified version of a type compatible with the effective type of the
object,
- a type that is the signed or unsigned type corresponding to the
effective type of the object,
- a type that is the signed or unsigned type corresponding to a
qualified version of the effective type of the object,
- an aggregate or union type that includes one of the aforementioned
types among its members (including, recursively, a member of a
subaggregate or contained union), or
- a character type.

Specifically you can access any type of object through an lvalue of
character type, but the reverse is not true - accessing a character, or an
array of characters, through an lvalue of non-character type is not one of
the permitted options. C99 introduces the concept of "effective type" as
used above. This supports the use of non-character objects in malloc'd
memory.

....
[color=blue]
> In all of these tests the word-based function far outperforms the library
> function - although as I have noted, the endian-ness causes errors.[/color]

You can make the code insensitive to byte order by using "word" ops to
find the first word that differs, then using byte ops to find the first
byte in the word that differs.

Lawrence

[Netocrat]

Re: string comparison

On Tue, 28 Jun 2005 15:17:11 +0100, Lawrence Kirby wrote:
[color=blue]
> On Sat, 25 Jun 2005 02:59:23 +1000, Netocrat wrote:
>[color=green]
>> On Thu, 23 Jun 2005 13:52:50 +0100, Lawrence Kirby wrote:
>>[color=darkred]
>>> On Thu, 23 Jun 2005 05:46:57 +1000, Netocrat wrote:
>>>
>>> ...
>>>
>>>>> Similarly you need a
>>>>> postamble to handle the last few bytes.
>>>>
>>>> Which I had; although correct me if you don't think it works as it
>>>> should (it tested fine)...
>>>>
>>>>>> while (ua < ua_max) {
>>>>>> if (*ua > *ub)
>>>
>>> This makes big assumptions abut the representation of integers in the
>>> platform. It won't work if they contain any padding bits or use
>>> anything other than big endian byte order. And technically speaking C's
>>> type aliasing rules disallow this.[/color]
>>
>> Where can I verify this from documentation - not that I don't believe
>> you, just that I'd like to know how to find these things out without
>> asking on the group? I know you can buy the standard, but I'd rather not
>> spend money. What are my options?[/color]
>
> You could download a draft version of the standard or buy a good book. Of
> course buying a book implies spending money and isn't guaranteed to be
> accurate or complete. Drafts are also not going to be 100% accurate but at
> least are based on the actual text of the standard.[/color]

I'm now using on-line drafts of both C90 and C99 as well as the ANSI
Rationale as posted in another thread by various people. So occasionally
it'll be inaccurate, but for the basics I should be fine, particularly
where the two drafts concur.
[color=blue]
> The aliasing rules I referred to are in C99 6.5p7:
>
> An object shall have its stored value accessed only by an lvalue
> expression that has one of the following types:73) - a type compatible
> with the effective type of the object, - a qualified version of a type
> compatible with the effective type of the
> object,
> - a type that is the signed or unsigned type corresponding to the
> effective type of the object,
> - a type that is the signed or unsigned type corresponding to a
> qualified version of the effective type of the object,
> - an aggregate or union type that includes one of the aforementioned
> types among its members (including, recursively, a member of a
> subaggregate or contained union), or
> - a character type.
>
> Specifically you can access any type of object through an lvalue of
> character type, but the reverse is not true - accessing a character, or an
> array of characters, through an lvalue of non-character type is not one of
> the permitted options. C99 introduces the concept of "effective type" as
> used above. This supports the use of non-character objects in malloc'd
> memory.[/color]

What do you mean by your last statement - how do you define non-character
objects?
[color=blue][color=green]
>> In all of these tests the word-based function far outperforms the
>> library function - although as I have noted, the endian-ness causes
>> errors.[/color]
>
> You can make the code insensitive to byte order by using "word" ops to
> find the first word that differs, then using byte ops to find the first
> byte in the word that differs.[/color]

It's always the simple solutions that are the most elusive. I had no need
to revert to assembly after all. Anyhow the excursion was informative.

I now have code that does effectively what you suggested except that
should it find a word that differs, it uses an assembly opcode to reverse
the byte order and test again. I haven't checked whether this is any
faster than as you have suggested simply reverting to byte ops in that
case. It may even vary from processor to processor - the array of Intel
chips supporting this opcode is vast.