strlen() speed test

[Nollie]

I need to write a couple of my own string manipulation routines (e.g.
a strcpy() alternative that returns the number of chars copied). I've
started with one of the simpler functions, strlen(). I've written a
very simple version call StringLength(), but it performs significantly
slower than its CRT counterparts.

Here's my implementation:
inline unsigned int StringLength( const char *pszString )
{
unsigned int cch = 0;
while ( *pszString++ )
cch++;
return cch;
}

I've compared my version to strlen() and _mbslen() using my own timer
function, which is a wrapper around the Windows
QueryPerformanc eCounter() API.

My only guess is that the CRT versions use the processor registers for
its counters and my version uses RAM. (You can't make use of the
"register" keyword with the VC++ compiler.)

How can I make my string manipulation functions compete speedwise with
the CRT functions?

[Rolf Magnus]

Nollie wrote:

I need to write a couple of my own string manipulation routines (e.g.
a strcpy() alternative that returns the number of chars copied). I've
started with one of the simpler functions, strlen(). I've written a
very simple version call StringLength(), but it performs significantly
slower than its CRT counterparts.

Here's my implementation:
inline unsigned int StringLength( const char *pszString )
{
unsigned int cch = 0;
while ( *pszString++ )
cch++;
return cch;
}
How about:

inline unsigned int StringLength( const char *pszString )
{
const char* p = pszString;
while (*p) p++;
return p - pszString;
}
I've compared my version to strlen() and _mbslen() using my own timer
function, which is a wrapper around the Windows
QueryPerformanc eCounter() API.

My only guess is that the CRT versions use the processor registers for
its counters and my version uses RAM.
The compiler will decide what to use. Did you set maximum optimization
level?
(You can't make use of the "register" keyword with the VC++ compiler.)
Why?
How can I make my string manipulation functions compete speedwise with
the CRT functions?

There might be some optimizations that you can do (e.g. not go though each
single character in the loop but instead checking multiple characters at
once, handling the string end separately).
OTOH, the library routine possibly uses some special assembler instructions
to speed this up. Systems like x86 have special built-in string
instructions to search quickly for a specific value in an array.

[Nollie]

>> (You can't make use of the "register" keyword with the VC++ compiler.)

Why? Dunno. Here's MS docs:
http://msdn.microsoft.com/library/de...er_keyword.asp
How about:
inline unsigned int StringLength( const char *pszString )
{
const char* p = pszString;
while (*p) p++;
return p - pszString;
} Thank you! Yes, this is a better algorithm. However, though it does
make StringLength() faster, it still does not rival the CRT functions.
The compiler will decide what to use. Did you set maximum optimization
level?

Yes, this is the answer. Sorry, I should have tried this before
posting. My timer only worked in unoptimized, DEBUG builds, but I've
rewritten it to work for all builds. StringLength() and strlen() now
use practically the exact same processing time.

However, now I have discovered another peculiarity...

Comparing 6 strlen() alternatives:
1. strlen() // CRT function
2. _tcslen() // redundant, maps to strlen
3. lstrlen() // Windows API
4. StringLength() // my function
5. _mbslen() // for multibyte strings
6. _mbstrlen() // for multibyte strings

Every one uses almost the exact same processing time, except _mbslen()
and _mbstrlen(), which are almost twice as fast as the others. I've
arranged the test so that the _mbs* functions are tested first, last,
and in between, so caching is not an issue.

It seems to me the _mbs* should be slower because they have to check
for double-byte character, but they are indeed quite faster. Why might
this be?

[Default User]

Nollie wrote:

(You can't make use of the
"register" keyword with the VC++ compiler.)

Says who?

Brian

[Nollie]

>Says who?

Topic = strlen() speed test.

http://msdn.microsoft.com/library/de...er_keyword.asp

[Stephen Howe]

>I need to write a couple of my own string manipulation routines (e.g.

a strcpy() alternative that returns the number of chars copied). I've
started with one of the simpler functions, strlen(). I've written a
very simple version call StringLength(), but it performs significantly
slower than its CRT counterparts.

Which it may well do.
Vendor implementations may well be written in assembler.
In particular for 32-bit Intel, there is a trick where it is possible to
process 4 bytes at once doing, bit manpulation to see if the '\0' is in any
of the 4 bytes. And if MMX is available, 8 bytes can be processed at once.
And for either, both are likely to faster than your code.

But in any case, why bother.

Stephen Howe

[Thomas Matthews]

Nollie wrote:

I need to write a couple of my own string manipulation routines (e.g.
a strcpy() alternative that returns the number of chars copied). I've
started with one of the simpler functions, strlen(). I've written a
very simple version call StringLength(), but it performs significantly
slower than its CRT counterparts.

Here's my implementation:
inline unsigned int StringLength( const char *pszString )
{
unsigned int cch = 0;
while ( *pszString++ )
cch++;
return cch;
}

I've compared my version to strlen() and _mbslen() using my own timer
function, which is a wrapper around the Windows
QueryPerformanc eCounter() API.

My only guess is that the CRT versions use the processor registers for
its counters and my version uses RAM. (You can't make use of the
"register" keyword with the VC++ compiler.)

How can I make my string manipulation functions compete speedwise with
the CRT functions?

Here are some {processor specific} ideas:
1. Rewrite in assembly using processor string instructions.
2. Instead of fetching one char at a time, fetch as many
as will fit into the processor's native register.
For example, if the processor register is 32-bits and
a char is 8-bits, then fetch 4 chars at a time.

The reasoning is the time for a "fetch" from memory
costs the same whether it is one char or one word.
So maximize this time.

3. If the processor has the ability, then fill as many
registers as possible during one fetch instruction
cycle. Note that there is a penalty for short strings,
because there is the wasted extra data.

So, why are you wasting your time optimizing library
routines?
Does your program work correctly?
Are the user's complaining about the speed?
Is the program missing events due to slowness?
Is your program causing the computer to miss events
because it is too slow, or locking up resources?

Don't optimize until the program works correctly.

I had a program that programmed a Flash memory device,
which took 5 minutes (but it worked correctly). I
reread the data sheet and optimized it, then the program
took 30 seconds. And yes, developers were complaining
about the time.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.l earn.c-c++ faq:
http://www.comeaucomputing.com/learn/faq/
Other sites:
http://www.josuttis.com -- C++ STL Library book
http://www.sgi.com/tech/stl -- Standard Template Library

[Default User]

Nollie wrote:

[context restored]

(You can't make use of the
"register" keyword with the VC++ compiler.)

Says who?

[MSDN link]
So by "make use of" you mean "can't get a register". Well, I'll break
the news that it's the same for almost every modern implementation.
Microsoft is just upfront about it.

Brian

[Nollie]

>So, why are you wasting your time optimizing library

routines?

It all started with a need for a strcpy() alternative that returns the
number of characters copied. But I actually have an OCD complex where
I have to know exactly how everything works. ;-) The blackbox concept
of programming with libraries and modules irks me to no end.

I have, however, decided that the you guys are right, and that the CRT
functions will serve my purpose just fine. Thanks for all the input.
This newsgroup really is a great example of how helpful Usenet can be.

[Rolf Magnus]

Nollie wrote:

So, why are you wasting your time optimizing library
routines?

It all started with a need for a strcpy() alternative that returns the
number of characters copied. But I actually have an OCD complex where
I have to know exactly how everything works. ;-) The blackbox concept
of programming with libraries and modules irks me to no end.

Then you should use more opensource/free software that comes with complete
source code. At least you don't need to write things yourself then, but
just look into the sources to "know exactly how everything is working". ;-)