Name help needed

[jacob navia]

We have strchr, that seeks a character in a character string

In the x86 architecture, there are processor specific search
operations wired in the hardware that can efficiently look for
a short, or an int.

I would like to add to lcc-win32's library two functions like this

strshort(short *data, size_t len,short i);

strint(int *data, size_t len,int i);


that would look for a short or an int in a short/int array.

What would be the right name for those functions?

Does anybody know if those functions already exist in
some implementation?

Thanks in advance

jacob

 

[Mole Wang]

There is another equivalent function in the library: memchr.
I think, maybe memshort and memint are better.

 

[Flash Gordon]

We have strchr, that seeks a character in a character string

In the x86 architecture, there are processor specific search
operations wired in the hardware that can efficiently look for
a short, or an int.

I would like to add to lcc-win32's library two functions like this

strshort(short *data, size_t len,short i);

strint(int *data, size_t len,int i);

that would look for a short or an int in a short/int array.

If you need a specific option to enable them then you can call them
whatever you like, otherwise do what MS have for a lot of their
extensions and stick them in the implementation name space. E.g.
_memshort & _memint. I would not use str as they are not string
functions.

What would be the right name for those functions?

Does anybody know if those functions already exist in
some implementation?

No idea if anyone has implemented them and I have no need of them so I'm
not looking.

 

[Keith Thompson]

We have strchr, that seeks a character in a character string

In the x86 architecture, there are processor specific search
operations wired in the hardware that can efficiently look for
a short, or an int.

I would like to add to lcc-win32's library two functions like this

strshort(short *data, size_t len,short i);

strint(int *data, size_t len,int i);

Don't start their names with "str", both because they don't operate on
strings and because names starting with "str" are reserved.

Are these CPU instructions? Would it make sense to use the same names
used for the instructions in assembly language? (Do this only if
there's no prospect of implementing the functions on other
architectures.)

 

[Richard Bos]

jacob navia <[email protected]> writes:

Are these CPU instructions? Would it make sense to use the same names
used for the instructions in assembly language? (Do this only if
there's no prospect of implementing the functions on other
architectures.)

Keith... who are you replying to? Is there _any_ prospect of any other
compiler suite adopting his spawnings?

Richard

 

[Michael Mair]

Keith... who are you replying to? Is there _any_ prospect of any other
compiler suite adopting his spawnings?

Keith mentioned not too long ago that he looks only at the merit of
the message, not of the poster.
Apart from that: You never know. lcc-win32 _might_ become a
C99 compliant compiler and might go open source. Windows _might_
migrate to other architectures.
And a consistent naming is a good idea.

I, personally would go with memint, memshrt, ... if the original
names are not feasible.


Cheers
Michael

 

[Keith Thompson]

Keith... who are you replying to? Is there _any_ prospect of any other
compiler suite adopting his spawnings?

Perhaps not, but it's plausible that functions added to lcc-win32
might find their way into lcc. (Jacob Navia's lcc-win32 is based on
lcc, a retargetable C compiler; see
<http://www.cs.princeton.edu/software/lcc/>.) And if they're x86 CPU
instructions, it's also plausible that other x86 compilers might
provide primitives that invoke them.

I don't know what Jacob meant by "processor specific search operations
wired in the hardware", thus my request for clarification.

 

[Lawrence Kirby]

Make the first parameters pointers to const type, and consider making the
parameter order consistent with memchr().

As others have indicated memshort and memint are more logical names for
this.

Don't start their names with "str", both because they don't operate on
strings and because names starting with "str" are reserved.

Since we're talking about adding functions to an implementation, using
reserved names is the correct thing to do. The implementation is permitted

Are these CPU instructions? Would it make sense to use the same names
used for the instructions in assembly language? (Do this only if
there's no prospect of implementing the functions on other architectures.)

The functions as described can be written in standard C so are
implementable on any architecture that can support standard C. The idea
here is that implementations have the opportinity to optimise these
vigorously where that is possible. However these days a good optimising
compiler could probably optimise an equivalent C loop in the same way.

Lawrence

 

[jacob navia]

The functions as described can be written in standard C so are
implementable on any architecture that can support standard C. The idea
here is that implementations have the opportinity to optimise these
vigorously where that is possible. However these days a good optimising
compiler could probably optimise an equivalent C loop in the same way.

Lawrence

Maybe one day compilers will be able to do that yes, but today...

gcc using optimization level 9 (maximum) writes for that
loop:

#include <stdio.h>
int main(void)
{
int tab[] = {0,1,2,3,4,999,6,7,8,9};
int i,*p,d = 999;

for (i=0,p=NULL; i<sizeof(tab)/sizeof(int);i++) {
if (d == tab) {
p = &tab;
break;
}
}
if (p)
printf("found at position %d\n",p-tab);
}

gcc generates for the loop code
..L20:
incl %ecx
cmpl $9, %ecx
ja .L19
leal 0(,%ecx,4), %edx
leal -72(%ebp), %eax
cmpl (%edx,%eax), %esi
jne .L20
leal (%edx,%eax), %ebx

instead of this:

movl $9,%ecx ; Put length in ecx
movl $999,%eax ; Integer to search for in eax
leal -72(%ebp),%esi; Start address in esi
rep scasl

No loops, and esi now points to the result, if ecx != 0

The Microsoft compiler produces a similar, normal loop code
with branching.

I would be surprised if a compiler exists that can realize
this optimization.

jacob

 

[jacob navia]

I don't know what Jacob meant by "processor specific search operations
wired in the hardware", thus my request for clarification.

The "repeat scasl" instruction does a high speed
search for an integer with the loop coded in the
processor itself.

jacob

 

[Lawrence Kirby]

On Wed, 29 Dec 2004 15:02:06 +0100, jacob navia wrote:

....

gcc generates for the loop code
.L20:
incl %ecx
cmpl $9, %ecx
ja .L19
leal 0(,%ecx,4), %edx
leal -72(%ebp), %eax
cmpl (%edx,%eax), %esi
jne .L20
leal (%edx,%eax), %ebx

instead of this:

movl $9,%ecx ; Put length in ecx
movl $999,%eax ; Integer to search for in eax
leal -72(%ebp),%esi; Start address in esi
rep scasl

No loops, and esi now points to the result, if ecx != 0

The Microsoft compiler produces a similar, normal loop code
with branching.

On which processors have you verified that the rep scasl code is actually
faster?

I would be surprised if a compiler exists that can realize this
optimization.

Assuming it really is an optimisation. These microcoded instructions are
sometimes fast, sometimes not.

Lawrence

 

[Keith Thompson]

Since we're talking about adding functions to an implementation, using
reserved names is the correct thing to do. The implementation is permitted
to add names such as memint and memshort to <string.h>.

Hmm, that's an interesting point. I assumed that identifers starting
with "str" or "mem" were reserved for future versions of the standard,
not for the implementation (which is why "strdup" is problematic,
though it actually predates the standard).

Certainly if an implementation provides a "strfoo" function, it could
cause problems if C200Y adds an incompatible "strfoo" function.

But in any case, the proposed functions don't operate on strings, so
calling them strwhatever would be misleading.

 

[Flash Gordon]

Hmm, that's an interesting point. I assumed that identifers starting
with "str" or "mem" were reserved for future versions of the standard,
not for the implementation (which is why "strdup" is problematic,
though it actually predates the standard).

Certainly if an implementation provides a "strfoo" function, it could
cause problems if C200Y adds an incompatible "strfoo" function.

That was my opinion as well. Hence my suggesting _mem* which is less
likely to conflict with any extensions to the standard.

But in any case, the proposed functions don't operate on strings, so
calling them strwhatever would be misleading.

Yes, str* is definitely wrong for something that does not treat the
input as a string.

 

[jacob navia]

On which processors have you verified that the rep scasl code is actually
faster?

Just did it in my AMD64.
For medium size blocks the rep scasl construct gives
1.056 seconds for scanning 100000 times a medium size
block of 10000 integers. Gcc with -O9 gives 1.546,
i.e. 50% slower.

For very large blocks (greater than 1MB) gcc and
rep scasl are more or less the same speed, with
a very slight difference in favor of rep/scasl.

Since scanning of very large blocks are bounded by RAM access,
I would bet that a non optimized version of any
compiler would be the same.

This instruction is recommended for
medium size blocks by AMD Optimizations guide and also
by Intel...

Medium size blocks will be the best for a general purpose,
inlined procedure.

Assuming it really is an optimisation. These microcoded instructions are
sometimes fast, sometimes not.

For medium size blocks this is better than the loop approach.
The overhead of the instruction is 15 clocks to setup the loop,
so for very small blocks the loop approach could be better.

 

[Old Wolf]

We have strchr, that seeks a character in a character string

In the x86 architecture, there are processor specific search
operations wired in the hardware that can efficiently look for
a short, or an int.

I would like to add to lcc-win32's library two functions like this

strshort(short *data, size_t len,short i);

strint(int *data, size_t len,int i);

that would look for a short or an int in a short/int array.

Obviously 'mem' instead of 'str' would be preferable because
they operate on length-counted data, instead of 0-terminated
data.

How about making a version for unsigned short and unsigned int too.
What about longs and long longs?

 

[jacob navia]

Obviously 'mem' instead of 'str' would be preferable because
they operate on length-counted data, instead of 0-terminated
data.

How about making a version for unsigned short and unsigned int too.
What about longs and long longs?

with lcc-win32 sizeof(long) == sizeof(int), so that's not needed.
For long longs, only the new machines (amd64, Intel prescott), can
seek a 64 bit number in a 64 bit number table.

But maybe I should add those functions in software, actually it
would be a good idea.

 

[Michael Mair]

with lcc-win32 sizeof(long) == sizeof(int), so that's not needed.
For long longs, only the new machines (amd64, Intel prescott), can
seek a 64 bit number in a 64 bit number table.

But maybe I should add those functions in software, actually it
would be a good idea.

Definitely. Even if you do not win a few cycles because you do not
optimise, it just makes sense to have them.
Note: I do not know whether you care about the environmental limits
of C89 (I am referring to the 6 "significant" characters) but if you
do, you may want to consider memint(), memshrt(), memlng()
[, memllng() if you have a respective compiler extension to C89,
otherwise you can of course do what you want within 31 characters
) ].

I think the suggestion to also provide unsigned variants is good.


Cheers
Michael

 

[Eric Sosman]

Just did it in my AMD64.
For medium size blocks the rep scasl construct gives
1.056 seconds for scanning 100000 times a medium size
block of 10000 integers. Gcc with -O9 gives 1.546,
i.e. 50% slower.

<off-topic excuse="stop the madness">

I.e., about one-half nanosecond per scanned integer.
If you're doing so many linear searches that this makes
an important difference, perhaps the searches shouldn't
be linear ...

</off-topic>

 

[Lawrence Kirby]

On Wed, 29 Dec 2004 00:48:06 +0000, Keith Thompson wrote: [...]
Don't start their names with "str", both because they don't operate
on> strings and because names starting with "str" are reserved.

Since we're talking about adding functions to an implementation,
using reserved names is the correct thing to do. The implementation
is permitted to add names such as memint and memshort to <string.h>.

Hmm, that's an interesting point. I assumed that identifers starting
with "str" or "mem" were reserved for future versions of the standard,
not for the implementation (which is why "strdup" is problematic,
though it actually predates the standard).

Reserved identifiers serve both purposes, although IMO allowing the
implementation to define things without breaking "correct" programs is the
more useful. New versions of the standard may attempt to stick to reserved
identifiers but they usually fail.

That was my opinion as well. Hence my suggesting _mem* which is less
likely to conflict with any extensions to the standard.

OTOH standards like C's should attempt to follow existing practice where
possible, so setting up some good existing practice isn't necessarily a
bad thing.

Yes, str* is definitely wrong for something that does not treat the
input as a string.

Hence memint() etc.

Lawrence

 

[Lawrence Kirby]

....

with lcc-win32 sizeof(long) == sizeof(int), so that's not needed.

The whole approach of forcing code to make avoidable compiler specific
assumptions seems wrong to me. Even if you do this you would be foring me
to write nasty pointer casts like the following:

long values[] = { ... };

size_t position = strint((int *)values, nelem, searchvalue);

For long longs, only the new machines (amd64, Intel prescott), can seek
a 64 bit number in a 64 bit number table.

But maybe I should add those functions in software, actually it would be
a good idea.

There may not be a single instruction solution, but since you seem to be
able to outdo the compiler in hand crafted assembly there are
opportunities for optimisation here.

Lawrence