strcmp is too heavy for its everyday usage...

strcmp is too heavy for its everyday usage...

[Denis Zaitsev]

strcmp is _mostly_ used here and there to check strings for equality
only, not for finding their ordering.  And if we have a function for
this equality check only, it would be a reasonable benefit:

a) for a long strings this function can operate with a whole
   words vs. bytes, which is much faster;

b) for a very short strings, when strcmp and this function can be
   unrolled into a series of a direct bytes comparing, this defun
   don't have to cope with (unsigned char) -> (int) casting for the
   each pair of bytes, so it will be shorter, faster etc.

memcmp is the subject of the question, too.

Any comments?

Re: strcmp is too heavy for its everyday usage...

[Roland McGrath]

The optimized string functions already do word comparisons when that is
possible and advantageous.  The comparisons to extract the ordering vs just
equality/nonequality are only on the first nonmatching byte.

Re: strcmp is too heavy for its everyday usage...

[Denis Zaitsev]

On Wed, Jan 07, 2004 at 05:13:11PM -0800, Roland McGrath wrote:

> The optimized string functions already do word comparisons when that
> is possible and advantageous.  The comparisons to extract the
> ordering vs just equality/nonequality are only on the first
> nonmatching byte.

But it's an overhead anyway.  Then, it's bad enough for the inlining.
And then, where is such a strcmp in GLIBC?

Re: strcmp is too heavy for its everyday usage...

[Andreas Schwab]

Denis Zaitsev <zzz@anda.ru> writes:

> On Wed, Jan 07, 2004 at 05:13:11PM -0800, Roland McGrath wrote:
>
>> The optimized string functions already do word comparisons when that
>> is possible and advantageous.  The comparisons to extract the
>> ordering vs just equality/nonequality are only on the first
>> nonmatching byte.
>
> But it's an overhead anyway.

Rather neglectable, IMHO.

> Then, it's bad enough for the inlining.

If it's inlined then the compiler should be smart enough to discard the
unneded bits.  If not, and the difference is measurable, then the compiler
should be fixed.

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux AG, Maxfeldstraße 5, 90409 Nürnberg, Germany
Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: strcmp is too heavy for its everyday usage...

[Denis Zaitsev]

On Thu, Jan 08, 2004 at 10:30:04AM +0100, Andreas Schwab wrote:
> Denis Zaitsev <zzz@anda.ru> writes:
> 
> > On Wed, Jan 07, 2004 at 05:13:11PM -0800, Roland McGrath wrote:
> >
> >> The optimized string functions already do word comparisons when
> >> that is possible and advantageous.  The comparisons to extract
> >> the ordering vs just equality/nonequality are only on the first
> >> nonmatching byte.
> >
> > But it's an overhead anyway.
> 
> Rather neglectable, IMHO.

Nearly agreed.

> > Then, it's bad enough for the inlining.
> 
> If it's inlined then the compiler should be smart enough to discard
> the unneded bits.  If not, and the difference is measurable, then
> the compiler should be fixed.

GCC is smart enough.  It doesn't do the job thru the best possible
way, but this should and (important!) can really be fixed.  So,
generally I agree again.  But suppose such an example:

extern inline
s(const unsigned char *a, const unsigned char *b)
{
    int r;
    (r= a[0] - b[0]) &&
    (r= a[1] - b[1]) &&
    (r= a[2] - b[2]) &&
    (r= a[3] - b[3]);
    return r;
}

It's a typical inline code for compare 4-byte of mem.  When it is
used, say, in such a context

        s(a,b) ? A() : B();

GCC discards the value of r perfectly, leaving the only code needed
for compare bytes for eq/neq.  But GCC doesn't merge the 4 byte
comparing into single word comparing.  And, as I understand, it will
never do that, as it's not asked to.  Or this kind of optimization is
assumed ok for compiler, but just still unimplemented?

Re: strcmp is too heavy for its everyday usage...

[Richard Henderson]

On Fri, Jan 09, 2004 at 10:11:45AM +0500, Denis Zaitsev wrote:
>     (r= a[0] - b[0]) &&
>     (r= a[1] - b[1]) &&
>     (r= a[2] - b[2]) &&
>     (r= a[3] - b[3]);
>     return r;
> }
> 
> It's a typical inline code for compare 4-byte of mem.  When it is
> used, say, in such a context
> 
>         s(a,b) ? A() : B();
> 
> GCC discards the value of r perfectly, leaving the only code needed
> for compare bytes for eq/neq.  But GCC doesn't merge the 4 byte
> comparing into single word comparing.  And, as I understand, it will
> never do that, as it's not asked to.  Or this kind of optimization is
> assumed ok for compiler, but just still unimplemented?

Certainly it's ok if it converts.

However, on most targets you'd have to know that a and b are aligned.
Worse, even for targets like x86 that support unaligned loads you have
to know for certain that neither a[3] nor b[3] could possibly segv
when a[0] and b[0] won't.  That condition is trivial when a and b are
aligned, but otherwise...

Adding compensation code to deal with the extra conditions that must
be satisfied will probably negate whatever you're hoping to gain here.



r~

Re: strcmp is too heavy for its everyday usage...

[Denis Zaitsev]

On Fri, Jan 09, 2004 at 12:12:31AM -0800, Richard Henderson wrote:
> On Fri, Jan 09, 2004 at 10:11:45AM +0500, Denis Zaitsev wrote:
> >     (r= a[0] - b[0]) &&
> >     (r= a[1] - b[1]) &&
> >     (r= a[2] - b[2]) &&
> >     (r= a[3] - b[3]);
> >     return r;
> > }
> > 
> > It's a typical inline code for compare 4-byte of mem.  When it is
> > used, say, in such a context
> > 
> >         s(a,b) ? A() : B();
> > 
> > GCC discards the value of r perfectly, leaving the only code needed
> > for compare bytes for eq/neq.  But GCC doesn't merge the 4 byte
> > comparing into single word comparing.  And, as I understand, it will
> > never do that, as it's not asked to.  Or this kind of optimization is
> > assumed ok for compiler, but just still unimplemented?
> 
> Certainly it's ok if it converts.
> 
> However, on most targets you'd have to know that a and b are aligned.
> Worse, even for targets like x86 that support unaligned loads you have
> to know for certain that neither a[3] nor b[3] could possibly segv
> when a[0] and b[0] won't.

Yes, and therefore this code is for memcmp, not for strcmp.  BTW, do I
understand right, that memcmp is free of that problem, as it has the
explicit length argument?  And this arg says implicitly, that the
access for the mem thru all this length is ok?

Re: strcmp is too heavy for its everyday usage...

[James Antill]

Richard Henderson <rth@twiddle.net> writes:

> On Fri, Jan 09, 2004 at 10:11:45AM +0500, Denis Zaitsev wrote:
>>     (r= a[0] - b[0]) &&
>>     (r= a[1] - b[1]) &&
>>     (r= a[2] - b[2]) &&
>>     (r= a[3] - b[3]);
>>     return r;
>> }
>>
>> never do that, as it's not asked to.  Or this kind of optimization is
>> assumed ok for compiler, but just still unimplemented?
>
> Certainly it's ok if it converts.
>
> However, on most targets you'd have to know that a and b are aligned.
> Worse, even for targets like x86 that support unaligned loads you have
> to know for certain that neither a[3] nor b[3] could possibly segv
> when a[0] and b[0] won't.  That condition is trivial when a and b are
> aligned, but otherwise...

 Fair enough, but...

extern int
s(const unsigned char a[static 4], const unsigned char b[static 4])
{
    int r;
    (r= a[0] - b[0]) &&
    (r= a[1] - b[1]) &&
    (r= a[2] - b[2]) &&
    (r= a[3] - b[3]);
    return r;
}

...produces the same code.

-- 
# James Antill -- james@and.org
:0:
* ^From: .*james@and\.org
/dev/null