why is this code so slow?

[Somebody]

Hi,

I'm trying to write the function below and have it working, but I
benchmarked it against strcmp() and its much slower. My test is to compare 2
strings that are identitical 100,000,000 times. Yeah, thats a lot, but I
needed to scale up the test to get a real timing on the function. The weird
thing is, even when I comment out almost the entire function, its still much
slower then strcmp()... at full implementation, strcmp() takes 5 seconds and
my function takes 78 seconds. If I comment everything out in my function
except the main while loop, it still takes 13 seconds. WTH?!?! I *AM* in
debug mode, but so is the crt library.

Basically the goal of this function is to perform a LOGICAL string compare
vs. a textual one. This is also called a NATURAL string compare by some...

For example, a normal string compare will sort as follows:

string1
string10
string2

where as the natural or logical string compare will sort as follows:

string1
string2
string10

taking digits into account as numbers.

the strings I'm comparing are two copies of:

"Sample description [1/10]"

I tried swapping out isdigit() with a quick & dirty macro, and that sped it
up quite a bit, but 5 vs. 78 seconds seems far off. I understand my function
is doing a lot more then strcmp(), but I was expecting maybe 20 to 30
seconds for my function. Not 78 seconds.

P.S. the if (n1 == n2) {} portion of the code is to sort zero padded #'s
correctly... ie... 01 should appear before 1.

I also tried implementing it with strtol()... that allowed me to get rid of
the two while loops that go to the end of the number and some of the pointer
math, but strtol() was sooooo much slower.

--- code below ---


#define SCLF_IGNORECASE 0x00000001

#define DIGIT(x) (x >= _T('0') && x <= _T('9'))
//#define DIGIT(x) isdigit(x)

int __cdecl StrCmpLogical(LPCTSTR lpsz1, LPCTSTR lpsz2, DWORD dwFlags)
{
if ((dwFlags != 0) && (dwFlags != SCLF_IGNORECASE))
return 0;

if ((lpsz1 != NULL) && (lpsz2 != NULL))
{
while (*lpsz1 != _T('\0'))
{
if (*lpsz2 == _T('\0'))
return 1;

if (/*_istdigit*/DIGIT(*lpsz1))
{
if (!/*_istdigit*/DIGIT(*lpsz2))
return -1;

int n1 = _ttoi(lpsz1);
int n2 = _ttoi(lpsz2);

if (n1 < n2)
return -1;
else if (n1 > n2)
return 1;

LPCTSTR lpszOrig1 = lpsz1;
LPCTSTR lpszOrig2 = lpsz2;

while (/*_istdigit*/DIGIT(*lpsz1))
lpsz1++;

while (/*_istdigit*/DIGIT(*lpsz2))
lpsz2++;

if (n1 == n2)
{
int nOffset1 = (int)(lpsz1 - lpszOrig1);
int nOffset2 = (int)(lpsz2 - lpszOrig2);

if (nOffset1 > nOffset2)
return -1;
else if (nOffset1 < nOffset2)
return 1;
}
}
else if (/*_istdigit*/DIGIT(*lpsz2))
{
return 1;
}
else
{
if (dwFlags & SCLF_IGNORECASE)
{
TCHAR ch1 = _totlower(*lpsz1);
TCHAR ch2 = _totlower(*lpsz2);

if (ch1 < ch2)
return -1;
else if (ch1 > ch2)
return 1;
}
else
{
if (*lpsz1 < *lpsz2)
return -1;
else if (*lpsz1 > *lpsz2)
return 1;
}

lpsz1++;
lpsz2++;
}
}
}
else
{
if ((lpsz1 == NULL) && (lpsz2 != NULL))
return -1;

if ((lpsz1 == NULL) && (lpsz2 == NULL))
return 0;

if ((lpsz1 != NULL) && (lpsz2 == NULL))
return 1;
}

return 0;
}

 

[cpunerd]

Hi,

I'm trying to write the function below and have it working, but I
benchmarked it against strcmp() and its much slower. My test is to compare 2
strings that are identitical 100,000,000 times. Yeah, thats a lot, but I
needed to scale up the test to get a real timing on the function. The weird
thing is, even when I comment out almost the entire function, its still much
slower then strcmp()... at full implementation, strcmp() takes 5 seconds and
my function takes 78 seconds. If I comment everything out in my function
except the main while loop, it still takes 13 seconds. WTH?!?! I *AM* in
debug mode, but so is the crt library.

Basically the goal of this function is to perform a LOGICAL string compare
vs. a textual one. This is also called a NATURAL string compare by some...

For example, a normal string compare will sort as follows:

string1
string10
string2

where as the natural or logical string compare will sort as follows:

string1
string2
string10

taking digits into account as numbers.

the strings I'm comparing are two copies of:

"Sample description [1/10]"

I tried swapping out isdigit() with a quick & dirty macro, and that sped it
up quite a bit, but 5 vs. 78 seconds seems far off. I understand my function
is doing a lot more then strcmp(), but I was expecting maybe 20 to 30
seconds for my function. Not 78 seconds.

P.S. the if (n1 == n2) {} portion of the code is to sort zero padded #'s
correctly... ie... 01 should appear before 1.

I also tried implementing it with strtol()... that allowed me to get rid of
the two while loops that go to the end of the number and some of the pointer
math, but strtol() was sooooo much slower.

--- code below ---

#define SCLF_IGNORECASE 0x00000001

#define DIGIT(x) (x >= _T('0') && x <= _T('9'))
//#define DIGIT(x) isdigit(x)

int __cdecl StrCmpLogical(LPCTSTR lpsz1, LPCTSTR lpsz2, DWORD dwFlags)
{
if ((dwFlags != 0) && (dwFlags != SCLF_IGNORECASE))
return 0;

if ((lpsz1 != NULL) && (lpsz2 != NULL))
{
while (*lpsz1 != _T('\0'))
{
if (*lpsz2 == _T('\0'))
return 1;

if (/*_istdigit*/DIGIT(*lpsz1))
{
if (!/*_istdigit*/DIGIT(*lpsz2))
return -1;

int n1 = _ttoi(lpsz1);
int n2 = _ttoi(lpsz2);

if (n1 < n2)
return -1;
else if (n1 > n2)
return 1;

LPCTSTR lpszOrig1 = lpsz1;
LPCTSTR lpszOrig2 = lpsz2;

while (/*_istdigit*/DIGIT(*lpsz1))
lpsz1++;

while (/*_istdigit*/DIGIT(*lpsz2))
lpsz2++;

if (n1 == n2)
{
int nOffset1 = (int)(lpsz1 - lpszOrig1);
int nOffset2 = (int)(lpsz2 - lpszOrig2);

if (nOffset1 > nOffset2)
return -1;
else if (nOffset1 < nOffset2)
return 1;
}
}
else if (/*_istdigit*/DIGIT(*lpsz2))
{
return 1;
}
else
{
if (dwFlags & SCLF_IGNORECASE)
{
TCHAR ch1 = _totlower(*lpsz1);
TCHAR ch2 = _totlower(*lpsz2);

if (ch1 < ch2)
return -1;
else if (ch1 > ch2)
return 1;
}
else
{
if (*lpsz1 < *lpsz2)
return -1;
else if (*lpsz1 > *lpsz2)
return 1;
}

lpsz1++;
lpsz2++;
}
}
}
else
{
if ((lpsz1 == NULL) && (lpsz2 != NULL))
return -1;

if ((lpsz1 == NULL) && (lpsz2 == NULL))
return 0;

if ((lpsz1 != NULL) && (lpsz2 == NULL))
return 1;
}

return 0;

}

the string library is probably intrinsic with your compiler, and
strcmp works off the knowledge that one can compare multiple bytes at
a time before the end of the string. it may be faster for you to write
an inlined function that finds the first number in a string, then
strcmp the bytes previous to the numbers, and then do your inlined
compare of the numbers

 

[Somebody]

On Apr 30, 8:24 pm, "Somebody" <[email protected]> wrote:

the string library is probably intrinsic with your compiler, and
strcmp works off the knowledge that one can compare multiple bytes at
a time before the end of the string. it may be faster for you to write
an inlined function that finds the first number in a string, then
strcmp the bytes previous to the numbers, and then do your inlined
compare of the numbers

Hmm...

I did think of doing something like that, but even though the example string
I gave above was "nice"... it isn't always going to be that way. Imagine if
you have something like "DVD-ISO9817-FULLIMAGE-1-07-2005" as an example. I'd
have to compare every string segment of the string seperately and keep track
of where I'm at. I thought it would be more overhead.

Hmm again... yeah, it looks like there is an intrinsic form of strcmp with
Visual Studio 2005, *BUT* intrinsic functions are disabled in debug mode.

Before intrinsics:
strcmp took 6688

StrCmpLogical took 139640

After intrinsics:

strcmp took 2188

StrCmpLogical took 139609

 

[cpunerd]

Hmm...

I did think of doing something like that, but even though the example string
I gave above was "nice"... it isn't always going to be that way. Imagine if
you have something like "DVD-ISO9817-FULLIMAGE-1-07-2005" as an example. I'd
have to compare every string segment of the string seperately and keep track
of where I'm at. I thought it would be more overhead.

Hmm again... yeah, it looks like there is an intrinsic form of strcmp with
Visual Studio 2005, *BUT* intrinsic functions are disabled in debug mode.

Before intrinsics:
strcmp took 6688

StrCmpLogical took 139640

After intrinsics:

strcmp took 2188

StrCmpLogical took 139609

hmmm, just judging from your example, it seems that your code is
significantly more complicated than strcmp, and hence *should* take
significantly longer. though i still cant explain the extra
overhead... ASM vs C/C++ calling convention, perhaps? try __fastcall?

 

[Ian Collins]

Hi,

I'm trying to write the function below and have it working, but I
benchmarked it against strcmp() and its much slower. My test is to compare 2
strings that are identitical 100,000,000 times. Yeah, thats a lot, but I
needed to scale up the test to get a real timing on the function. The weird
thing is, even when I comment out almost the entire function, its still much
slower then strcmp()... at full implementation, strcmp() takes 5 seconds and
my function takes 78 seconds. If I comment everything out in my function
except the main while loop, it still takes 13 seconds. WTH?!?! I *AM* in
debug mode, but so is the crt library.

Basically the goal of this function is to perform a LOGICAL string compare
vs. a textual one. This is also called a NATURAL string compare by some...

For example, a normal string compare will sort as follows:

string1
string10
string2

where as the natural or logical string compare will sort as follows:

string1
string2
string10

taking digits into account as numbers.

the strings I'm comparing are two copies of:

"Sample description [1/10]"

I tried swapping out isdigit() with a quick & dirty macro, and that sped it
up quite a bit, but 5 vs. 78 seconds seems far off. I understand my function
is doing a lot more then strcmp(), but I was expecting maybe 20 to 30
seconds for my function. Not 78 seconds.

P.S. the if (n1 == n2) {} portion of the code is to sort zero padded #'s
correctly... ie... 01 should appear before 1.

I also tried implementing it with strtol()... that allowed me to get rid of
the two while loops that go to the end of the number and some of the pointer
math, but strtol() was sooooo much slower.

--- code below ---


#define SCLF_IGNORECASE 0x00000001

#define DIGIT(x) (x >= _T('0') && x <= _T('9'))
//#define DIGIT(x) isdigit(x)

int __cdecl StrCmpLogical(LPCTSTR lpsz1, LPCTSTR lpsz2, DWORD dwFlags)
{

Can you post a standard C++ version?

 

[Obnoxious User]

Somebody skrev:

Hmm...

I did think of doing something like that, but even though the example string
I gave above was "nice"... it isn't always going to be that way. Imagine if
you have something like "DVD-ISO9817-FULLIMAGE-1-07-2005" as an example. I'd
have to compare every string segment of the string seperately and keep track
of where I'm at. I thought it would be more overhead.

What about:
(Written without enough debugging, but I expect it to work. Not benchmarked)

//---------------------------------------------------------------------------
#include <set>
#include <ostream>
#include <algorithm>
#include <iterator>

inline bool isd(char c) {
return (c >= '0') && (c <= '9');
}

int cmplogic(char const * a, char const * b) {
int result = 0;
bool ad,bd,ab,ob,pb = false;
while(*a && *b) {
ad = isd(*a);
bd = isd(*b);
ab = ad && bd;
ob = !ab && (ad || bd);
if(*a < *b) {
if(ab) { if(!result) result = -1; }
else if(pb && ob) return 1;
else if(pb && !ab) return result?result:-1;
else return -1;
} else
if(*a > *b) {
if(ab) { if(!result) result = 1; }
else if(pb && ob) return -1;
else if(pb && !ab) return result?result:1;
else return 1;
} else
if(result) return result;
pb = ab;
++a;
++b;
}
if(!(*a || *b)) {
return result;
}
if(*a) {
if(isd(*a)) return 1;
return result?result:1;
}
if(isd(*b)) return -1;
return result?result:-1;
}

struct diff {
bool operator()(char const * a, char const * b) {
return cmplogic(a,b) == -1;
}
};

int main(int argc, char* argv[])
{
std::set<char const *,diff> s;
s.insert("string11");
s.insert("string1");
s.insert("2u");
s.insert("963y");
s.insert("963h");
s.insert("string481");
s.insert("DVD-ISO9817-FULLIMAGE-1-08-2006");
s.insert("string23u4");
s.insert("string25");
s.insert("string10");
s.insert("41");
s.insert("string110");
s.insert("string23a");
s.insert("string2");
s.insert("string23u21");
s.insert("963");
s.insert("957");
s.insert("DVD-ISO9817-FULLIMAGE-1-07-2006");
s.insert("DVD-ISO9819-FULLIMAGE-2-07-2005");
std::copy(s.begin(),s.end(),
std:stream_iterator<char const*>(std::cout,"\n"));
return 0;
}

//---------------------------------------------------------------------------

Outputs:

2u
41
957
963
963h
963y
DVD-ISO9817-FULLIMAGE-1-07-2006
DVD-ISO9817-FULLIMAGE-1-08-2006
DVD-ISO9819-FULLIMAGE-2-07-2005
string1
string10
string11
string23
string23a
string23u4
string23u21
string25
string110
string481

 

[Old Wolf]

I'm trying to write the function below and have it working, but I
benchmarked it against strcmp() and its much slower.
at full implementation, strcmp() takes 5 seconds and
my function takes 78 seconds. If I comment everything
out in my function except the main while loop, it still takes
13 seconds. WTH?!?!

Your function does a gajillion more things than strcmp, as
well as taking extra parameters and using a different calling
convention. Why are you surprised that it is slower?

 

[Somebody]

It doesn't work actually . It seems like you only look at one digit at a
time rather then the number as a whole...

It fails on:

String [1/10]
String [01/10]
String[10/10]
String [2/10]

But it was faster though... LOL...

Anyways, I got my working algorithm optimized down so that its as fast as
yours (but works )...

strcmp() = 36ms
my logical string compare = 175ms

This is about the timing I expected, not a MINUTE+ with my original
implementation.

I got it down this fast by:

1) writing a very small streamlined macro for "IsDigit()". That chopped off
a SIGNIFICANT amount of time since its not an intrinsic function and the CRT
function (for VS2005) does a bunch of locale crap.

2) writing a very small streamlined INLINE block of code for atoi()... Yes,
it was copy & pasted twice since it would be easier to read . We are only
talking about 4 lines here. This allowed me to combine the atoi() code and
the "find end of number" loops that followed. Another significant chunk of
time.

3) finally, I wrote a streamlined macro for tolower()... that had a big
effect on the case insensitive compares.

Calling conventions had almost zero effect on performance.

Somebody skrev:

Hmm...

I did think of doing something like that, but even though the example
string I gave above was "nice"... it isn't always going to be that way.
Imagine if you have something like "DVD-ISO9817-FULLIMAGE-1-07-2005" as
an example. I'd have to compare every string segment of the string
seperately and keep track of where I'm at. I thought it would be more
overhead.

What about:
(Written without enough debugging, but I expect it to work. Not
benchmarked)

//---------------------------------------------------------------------------
#include <set>
#include <ostream>
#include <algorithm>
#include <iterator>

inline bool isd(char c) {
return (c >= '0') && (c <= '9');
}

int cmplogic(char const * a, char const * b) {
int result = 0;
bool ad,bd,ab,ob,pb = false;
while(*a && *b) {
ad = isd(*a);
bd = isd(*b);
ab = ad && bd;
ob = !ab && (ad || bd);
if(*a < *b) {
if(ab) { if(!result) result = -1; }
else if(pb && ob) return 1;
else if(pb && !ab) return result?result:-1;
else return -1;
} else
if(*a > *b) {
if(ab) { if(!result) result = 1; }
else if(pb && ob) return -1;
else if(pb && !ab) return result?result:1;
else return 1;
} else
if(result) return result;
pb = ab;
++a;
++b;
}
if(!(*a || *b)) {
return result;
}
if(*a) {
if(isd(*a)) return 1;
return result?result:1;
}
if(isd(*b)) return -1;
return result?result:-1;
}

struct diff {
bool operator()(char const * a, char const * b) {
return cmplogic(a,b) == -1;
}
};

int main(int argc, char* argv[])
{
std::set<char const *,diff> s;
s.insert("string11");
s.insert("string1");
s.insert("2u");
s.insert("963y");
s.insert("963h");
s.insert("string481");
s.insert("DVD-ISO9817-FULLIMAGE-1-08-2006");
s.insert("string23u4");
s.insert("string25");
s.insert("string10");
s.insert("41");
s.insert("string110");
s.insert("string23a");
s.insert("string2");
s.insert("string23u21");
s.insert("963");
s.insert("957");
s.insert("DVD-ISO9817-FULLIMAGE-1-07-2006");
s.insert("DVD-ISO9819-FULLIMAGE-2-07-2005");
std::copy(s.begin(),s.end(),
std:stream_iterator<char const*>(std::cout,"\n"));
return 0;
}

//---------------------------------------------------------------------------

Outputs:

2u
41
957
963
963h
963y
DVD-ISO9817-FULLIMAGE-1-07-2006
DVD-ISO9817-FULLIMAGE-1-08-2006
DVD-ISO9819-FULLIMAGE-2-07-2005
string1
string10
string11
string23
string23a
string23u4
string23u21
string25
string110
string481

 

[Obnoxious User]

Somebody skrev:

It doesn't work actually . It seems like you only look at one digit at a
time rather then the number as a whole...

It fails on:

String [1/10]
String [01/10]
String[10/10]
String [2/10]

No, it doesn't look at one digit at time. It considers the entire
number. Exactly how do you wish it to sort the strings? It outputs:

String [01/10]
String [1/10]
String [2/10]
String[10/10]

Precisely as I would expect it to do. 01 < 1 < 2.
When two numbers are found it compares the complete value.

 

[Obnoxious User]

Obnoxious User skrev:

Somebody skrev:

It doesn't work actually . It seems like you only look at one digit
at a time rather then the number as a whole...

It fails on:

String [1/10]
String [01/10]
String[10/10]
String [2/10]

No, it doesn't look at one digit at time. It considers the entire
number. Exactly how do you wish it to sort the strings? It outputs:

Well, actually more likely just the partial number, but still enough
to know which number is bigger or smaller. The rest is irrelevant.

 

[Default User]

It doesn't work actually . It seems like you only look at one digit
at a time rather then the number as a whole...

Please don't top-post. Your replies belong following or interspersed
with properly trimmed quotes. See the majority of other posts in the
newsgroup, or the group FAQ list:
<http://www.parashift.com/c++-faq-lite/how-to-post.html>

 

[Somebody]

Obnoxious User skrev:

Somebody skrev:

It doesn't work actually . It seems like you only look at one digit at
a time rather then the number as a whole...

It fails on:

String [1/10]
String [01/10]
String[10/10]
String [2/10]

No, it doesn't look at one digit at time. It considers the entire
number. Exactly how do you wish it to sort the strings? It outputs:

Well, actually more likely just the partial number, but still enough
to know which number is bigger or smaller. The rest is irrelevant.

Sorry, typo in the data I posted. The [10/10] string was missing a space...
should have been:

s.insert("Sample [1/10]");
s.insert("Sample [10/10]");
s.insert("Sample [2/10]");
s.insert("Sample [01/10]");

this outputs:

Sample [01/10]
Sample [10/10]
Sample [1/10]
Sample [2/10]

as you can see, the 10/10 is in the wrong place. It should be 01, 1, 2, 10.

 

[Obnoxious User]

Somebody skrev:

Obnoxious User skrev:

Somebody skrev:
It doesn't work actually . It seems like you only look at one digit at
a time rather then the number as a whole...

It fails on:

String [1/10]
String [01/10]
String[10/10]
String [2/10]

No, it doesn't look at one digit at time. It considers the entire
number. Exactly how do you wish it to sort the strings? It outputs:

Well, actually more likely just the partial number, but still enough
to know which number is bigger or smaller. The rest is irrelevant.

Sorry, typo in the data I posted. The [10/10] string was missing a space...
should have been:

s.insert("Sample [1/10]");
s.insert("Sample [10/10]");
s.insert("Sample [2/10]");
s.insert("Sample [01/10]");

this outputs:

Sample [01/10]
Sample [10/10]
Sample [1/10]
Sample [2/10]

as you can see, the 10/10 is in the wrong place. It should be 01, 1, 2, 10.

Yes, you're right. It's flawed. Won't really matter since you said you
found your own solution, but just for the fun of it, here's an improved
version, hopefully flawless. It disregards any leading zeros, treating
"00001" and "1" as the same number. My last attempt, moving on. Enjoy.

inline bool isd(char c) {
return (c >= '0') && (c <= '9');
}

int cmplogic(char const * a, char const * b) {
int result = 0;
bool ad,bd,ab,pb = false;
while(*a && *b) {
ad = isd(*a);
bd = isd(*b);
ab = ad && bd;
if(pb && !ab) {
if(ad) return 1;
if(bd) return -1;
}
if(!pb && ad && *a == '0' && ++a) continue;
if(!pb && bd && *b == '0' && ++b) continue;
if(*a < *b) {
if(ab) { if(!result) result = -1; }
else return result?result:-1;
} else
if(*a > *b) {
if(ab) { if(!result) result = 1; }
else return result?result:1;
} else
if(result) return result;
pb = ab;
++a;
++b;
}
if(!(*a || *b)) {
return result;
}
if(*a) {
if(pb && isd(*a)) return 1;
return result?result:1;
}
if(pb && isd(*b)) return -1;
return result?result:-1;
}