My operator+= In My String Class Is Too Slow! What Am I Doing Wrong?

[Frederick2]

I don’t know why my operator += and operator + string class member functions are taking so long to do their job and are so inefficient compared to the Standard C++ Library String Class. Its not that they don’t work; its just that they are slower by a factor of like a hundred or thousand or something ridiculous like that. I’m wondering if I’m doing something terribly wrong. I’m hoping that one of the C++ wizards here at Daniweb could take a brief look at my stripped down version of my String Class where I work on a very simple 20 byte long String, i.e., “11111111112222222222”; I dismember it into two 10 byte chunks; then concatenate it back together in a second buffer appending a “\r\n” after each of the two ten byte chunks. In other words, the output from the program is this…

1111111111
2222222222

…in a second buffer.

I’ve included the exact output from this program right beneath it, so you don’t even have to run it. The output includes a voluminous trace file showing in excruciating detail all the String Class Member Function Calls, addresses of everything, etc. Naturally, I have to include my stripped down String Class for anyone who would be willing to run it or examine the code. In my real String Class I use the <tchar.h> macros because I’m a Windows programmer, but I believe that brutality and nastiness is specific to Windows, so I removed it so Unix/Linux folks wouldn’t be left out in the cold (I wouldn’t want to do that because I really like Linux, and when I retire I’m hoping I have more time to work with it).

What I would love to know is what I might be doing wrong here that is causing it to run so slow. Just in the way of providing background information, this program is but a small part (albeit an important part) of a larger endeavor of mine where I’m trying to compare the speed of processing of C, C++, and PowerBASIC on a particularly brutal little string processing algorithm, i.e.,

'1) Create a 2MB string of dashes
'2) Change every 7th dash to a "P"
'3) Search for, locate, and replace every "P" with a "PU" (hehehe) (don’t assume P every 7th char!!!)
'4) Replace every dash with an "8"
'5) Put in a carriage return & line feed every 90 characters

My String Class is soundly beating the Standard C++ Library String Class in this algorithm; but that’s only telling part of the story. The reason its beating the Standard C++ Library’s String Class is because I’ve apparently succeeded in crafting a particularly effective Search and Replace function. Mine does Step 3 above almost instantly, then dies when it hits the concatenation at step 5. On the other hand, when I use the C++ Library’s String Class (#include <string>) and a replace function I got from Bruce Eckel’s “Thinking In C++”, Volume Two, the algorithm dies at Bruce’s code, then burns through the Step 5 concatenation almost instantly, completely putting my String Class to shame. The net result is that my String class is only taking about two thirds the time to run the algorithm, but that appears to be only because either my replace function is so good or Bruce Eckel’s is so bad, or a combination of both of the above. The Standard String Class is killing me at concatenation. Here are the tick counts for 1st my string class, then the Std C++ String Class..

My String Class

Starting....
s1 has 500000 of these “-“ milliseconds elapsed 0
s1 has 'P' every 7th char milliseconds elapsed 20
s2 created with PUs in place of Ps milliseconds elapsed 80
dashes replaced with 8s milliseconds elapsed 150
Now Do Concatenation...
Finished Creating Lines milliseconds elapsed 12558
t1 = 12558 <<< final tick count

Standard C++ Library String Class And ReplaceAll() Function From Bruce Eckel’s “Thinking In C++” Book

Starting....
Finished Creating String With 500000 Of These - : milliseconds elapsed - 0
Finished Inserting 'P's In s1! : milliseconds elapsed - 10
Finished Replacing 'P's With PU! : milliseconds elapsed – 17335 !!! 17275 more than mine!
Finished Replacing '-'s With 8! : milliseconds elapsed - 17415
Now Going To Create Lines With CrLfs!
Finished Creating Lines! : milliseconds elapsed – 17425 !!! 12400 faster than mine!
t1 = 17425 <<< final tick count

As can be seen, using my Replace member function of my string class, only 60 ticks were burnt in doing the Search & Replace of Ps with PU. Using the Std. String Class and Bruce’s external replaceAll() function which operates on Std. String Class objects took 17325 ticks! However, it burnt through the concatenation in ten ticks, whereas mine cost me like 12,400 ticks!!!!!!! Hence my initial question above. After this post I’ll provide the full code for the above algorithms. I thought it best to separate this out though in terms of my string concatenation issue, as it is indeed a separate issue. Here is my shortened example, hopefully for your examination…

#include "Windows.h"
#include <Stdio.h>
#include "Strings.h"

int main()
{
 String s1="11111111112222222222"; //Create String To Work On; 20 bytes long
 String s2('-',32);                //Create swap/temp/work buffer; add a few 
                                   //extra bytes breathing room
 s1.Print(true);      
 s2.Print(true);                   //Null s2 out at offset 0 in preallocated 
 s2.SetChar(1,'\0');               //buffer to zero length
 printf("s1.lpStr() = %u\n",(unsigned)s1.lpStr());   //output address of buffer s1
 printf("s2.lpStr() = %u\n",(unsigned)s2.lpStr());   //output address of buffer s2
 for(unsigned i=1; i<=20; i=i+10)
 {
     s2+=s1.Mid(i,10)+"\r\n";      //Don't know why this is so much slower
     s2.Print(false);              //than Std C++ String Class!
 }
 getchar();

 return 0;
}

Output From Above Program…

Entering String::String(TCHAR* pStr) Constructor!
Leaving String::String(TCHAR* pStr) Constructor!

Entering String::String(const TCHAR ch, int iCount)
Leaving String::String(const TCHAR ch, int iCount)

11111111112222222222
--------------------------------
s1.lpStr() = 4138224
s2.lpStr() = 4138264


Entering String String::Mid(unsigned int iStart, unsigned int iCount)  //1st Concatenation
  this->pStrBuffer = 4138224    11111111112222222222                   //s1 in main()
  Entering String::String(int iSize)
    this->pStrBuffer = 4138320                                         //tmp1 created
  Leaving String::String(int iSize)
Leaving String String::Mid(unsigned int iStart, unsigned int iCount)

Entering String::String(const String& s)
  s.pStrBuffer     = 4138320    1111111111                             //tmp1 received
  this->pStrBuffer = 4145104    1111111111                             //tmp2 created
Leaving String::String(const String& s)

Entering String Destructor!
  pStrBuffer = 4138320  1111111111                                     //tmp1 deleted
Leaving String Destructor!

Entering String& String::operator+(const TCHAR* pChar)
Leaving String& String::operator+(const TCHAR* pChar)

Entering String::operator+=(const String&)!
  this->pStrBuffer               = 4138264                             //1st assignment to s2
  this->iAllowableCharacterCount = 47
  this->LenStr()                 = 0
Leaving String::operator+=(const String&)!

Entering String Destructor!
  pStrBuffer = 4145104  1111111111   // + \r\n                         //tmp2 deleted
Leaving String Destructor!

1111111111   // + \r\n




Entering String String::Mid(unsigned int iStart, unsigned int iCount)
  this->pStrBuffer = 4138224    11111111112222222222
  Entering String::String(int iSize)
    this->pStrBuffer = 4138320
  Leaving String::String(int iSize)
Leaving String String::Mid(unsigned int iStart, unsigned int iCount)

Entering String::String(const String& s)
  s.pStrBuffer     = 4138320    2222222222
  this->pStrBuffer = 4145104    2222222222
Leaving String::String(const String& s)

Entering String Destructor!
  pStrBuffer = 4138320  2222222222
Leaving String Destructor!

Entering String& String::operator+(const TCHAR* pChar)
Leaving String& String::operator+(const TCHAR* pChar)

Entering String::operator+=(const String&)!
  this->pStrBuffer               = 4138264      1111111111  // + \r\n
  this->iAllowableCharacterCount = 47
  this->LenStr()                 = 12
Leaving String::operator+=(const String&)!

Entering String Destructor!
  pStrBuffer = 4145104  2222222222                          // + \r\n
Leaving String Destructor!

1111111111
2222222222

Entering String Destructor!
  pStrBuffer = 4138264  1111111111
                        2222222222
Leaving String Destructor!

Entering String Destructor!
  pStrBuffer = 4138224  11111111112222222222
Leaving String Destructor!

And here is my abbreviated String Class, which is required to run the above program by including Strings.h and Strings.cpp in the compile…

//Strings.h  -- My String Class
#if !defined(STRINGS_H)
#define STRINGS_H
#define EXPANSION_FACTOR      2
#define MINIMUM_ALLOCATION    16

class __declspec(dllexport) String
{
 public:
 String(const char*);                      //Constructor Initializes String With char*
 String(const String&);                    //Constructor Initializes String With Another String (Copy Constructor)
 String(int);                              //Constructor Initializes Buffer To Specific Size
 String(const char ch, const int iCount);  //Constructor initializes String with int # of chars
 String& operator=(const char*);           //Assigns char* To String
 String& operator=(const String&);         //Assigns one String to another (this one)
 String& operator+(const char*);           //For adding null terminated char array to String
 String& operator+(const String&);         //For adding one String to Another
 String& operator+=(const char*);          //For adding null terminated char array to String
 String& operator+=(const String&);        //For adding one String to Another
 String Mid(unsigned int, unsigned int);   //Returns String consisting of number of TCHARs from some offset
 int LenStr(void);                         //Returns length of string
 char* lpStr();                            //Returns address of pStrBuffer member variable
 void SetChar(unsigned int, char);         //Sets char at one based index
 void Print(bool);                         //Outputs String to Console with or without CrLf
 ~String();                                //String Destructor

 private:
 char* pStrBuffer;
 int    iAllowableCharacterCount;
};
#endif  //#if !defined(STRINGS_H)

//Strings.cpp
#include  <stdlib.h>
#include  <stdio.h>
#include  <math.h>
#include  <string.h>
#include  "Strings.h"


String::String(const char* pStr)  //Constructor: Initializes with char*
{
 int iLen,iNewSize;

 printf("Entering String::String(char* pStr) Constructor!\n");
 iLen=strlen(pStr);
 iNewSize=(iLen/16+1)*16;
 pStrBuffer=new char[iNewSize];
 this->iAllowableCharacterCount=iNewSize-1;
 strcpy(pStrBuffer,pStr);
 printf("Leaving String::String(char* pStr) Constructor!\n\n");
}


String::String(const String& s)  //Constructor Initializes With Another String, i.e., Copy Constructor
{
 int iLen,iNewSize;

 printf("Entering String::String(const String& s)\n");
 printf("  s.pStrBuffer     = %u\t%s\n",(unsigned)s.pStrBuffer,s.pStrBuffer);
 iLen=strlen(s.pStrBuffer);
 iNewSize=(iLen/16+1)*16;
 this->pStrBuffer=new char[iNewSize];
 this->iAllowableCharacterCount=iNewSize-1;
 strcpy(this->pStrBuffer,s.pStrBuffer);
 printf("  this->pStrBuffer = %u\t%s\n",(unsigned)this->pStrBuffer,this->pStrBuffer);
 printf("Leaving String::String(const String& s)\n\n");
}


String::String(int iSize)        //Constructor Creates String With Custom Sized
{                                //Buffer (rounded up to paragraph boundary)
 int iNewSize;

 printf("  Entering String::String(int iSize)\n");
 iNewSize=(iSize/16+1)*16;
 pStrBuffer=new char[iNewSize];
 this->iAllowableCharacterCount=iNewSize-1;
 this->pStrBuffer[0]='\0';
 printf("    this->pStrBuffer = %u\n",(unsigned)this->pStrBuffer);
 printf("  Leaving String::String(int iSize)\n");
}


String::String(const char ch, int iCount)
{
 int iNewSize;

 printf("Entering String::String(const char ch, int iCount)\n");
 iNewSize=(iCount/16+1)*16;
 pStrBuffer=new char[iNewSize];
 this->iAllowableCharacterCount=iNewSize-1;
 for(int i=0; i<iCount; i++)
     pStrBuffer[i]=ch;
 pStrBuffer[iCount]='\0';
 printf("Leaving String::String(const char ch, int iCount)\n\n");
}


String& String::operator=(const char* pStr) //Constructor For If Pointer To Asciiz/Unicode String Parameter
{
 int iLen,iNewSize;

 printf("Entering String& String::operator=(const char* pStr)\n");
 printf("  pStr = %s\n",pStr);
 iLen=strlen(pStr);
 if(iLen<this->iAllowableCharacterCount)
    strcpy(pStrBuffer,pStr);
 else
 {
    delete [] pStrBuffer;
    iNewSize=(iLen/16+1)*16;
    pStrBuffer=new char[iNewSize];
    this->iAllowableCharacterCount=iNewSize-1;
    strcpy(pStrBuffer,pStr);
 }
 printf("Leaving String& String::operator=( char* pStr)\n\n");

 return *this;
}


String& String::operator=(const String& strRight)  //Overloaded operator = for
{                                                  //assigning another String to
 int iRightLen,iNewSize;                           //a String

 printf("Entering String::operator=( String& strRight)!\n");
 printf("  strRight = %s\n",strRight.pStrBuffer);
 printf("  strRight = %u\n",(unsigned)strRight.pStrBuffer);
 if(this==&strRight)
 {
    printf("Leaving String::operator=( String& strRight)!  -- EARLY EXIT!!!\n\n");
    return *this;
 }
 iRightLen=strlen(strRight.pStrBuffer);
 if(iRightLen < this->iAllowableCharacterCount)
    strcpy(pStrBuffer,strRight.pStrBuffer);
 else
 {
    iNewSize=(iRightLen/16+1)*16;
    delete [] this->pStrBuffer;
    this->pStrBuffer=new char[iNewSize];
    this->iAllowableCharacterCount=iNewSize-1;
    strcpy(pStrBuffer,strRight.pStrBuffer);
 }
 printf("Leaving String::operator=( String& strRight)!\n\n");

 return *this;
}


String& String::operator+(const char* pChar) //Overloaded operator + (Adds char literals
{                                             //or pointers to Asciiz Strings)
 int iLen,iNewSize;
 char* pNew;

 printf("Entering String& String::operator+(const char* pChar)\n");
 iLen=strlen(this->pStrBuffer)+strlen(pChar);
 if(iLen<this->iAllowableCharacterCount)
 {
    if(this->pStrBuffer)
       strcat(this->pStrBuffer,pChar);
    else
       strcpy(this->pStrBuffer, pChar);
 }
 else
 {
    iNewSize=(iLen*EXPANSION_FACTOR/16+1)*16;
    pNew=new char[iNewSize];
    this->iAllowableCharacterCount = iNewSize-1;
    if(this->pStrBuffer)
    {
       strcpy(pNew,this->pStrBuffer);
       delete [] pStrBuffer;
       strcat(pNew,pChar);
    }
    else
       strcpy(pNew,pChar);
    this->pStrBuffer=pNew;
 }
 printf("Leaving String& String::operator+(const char* pChar)\n\n");

 return *this;
}


String& String::operator+(const String& strRight)  //Overloaded operator + Adds
{                                                  //Another String to the left
 int iLen,iNewSize;                                //operand
 char* pNew;

 printf("Entering String& String::operator+(const String& strRight)\n");
 printf("  strRight.pStrBuffer = %s\n",strRight.pStrBuffer);
 iLen=strlen(this->pStrBuffer) + strlen(strRight.pStrBuffer);
 if(iLen < this->iAllowableCharacterCount)
 {
    if(this->pStrBuffer)
       strcat(this->pStrBuffer,strRight.pStrBuffer);
    else
       strcpy(this->pStrBuffer,strRight.pStrBuffer);
 }
 else
 {
    iNewSize=(iLen*EXPANSION_FACTOR/16+1)*16;
    pNew=new char[iNewSize];
    this->iAllowableCharacterCount=iNewSize-1;
    if(this->pStrBuffer)
    {
       strcpy(pNew,this->pStrBuffer);
       delete [] pStrBuffer;
       strcat(pNew,strRight.pStrBuffer);
    }
    else
       strcpy(pNew,strRight.pStrBuffer);
    this->pStrBuffer=pNew;
 }
 printf("Leaving String& String::operator+(const String& strRight)\n\n");

 return *this;
}


String& String::operator+=(const String& strRight)
{
 int iLen,iNewSize;                                
 char* pNew;

 printf("Entering String::operator+=(const String&)!\n");
 printf("  this->pStrBuffer               = %u\t%s\n",(unsigned)this->pStrBuffer,this->pStrBuffer);
 printf("  this->iAllowableCharacterCount = %u\n",(unsigned)this->iAllowableCharacterCount);
 printf("  this->LenStr()                 = %u\n",(unsigned)this->LenStr());
 iLen=strlen(this->pStrBuffer) + strlen(strRight.pStrBuffer);
 if(iLen < this->iAllowableCharacterCount)
 {
    if(this->pStrBuffer)
       strcat(this->pStrBuffer,strRight.pStrBuffer);
 }
 else
 {
    iNewSize=(iLen*EXPANSION_FACTOR/16+1)*16;
    pNew=new char[iNewSize];
    this->iAllowableCharacterCount=iNewSize-1;
    if(this->pStrBuffer)
    {
       strcpy(pNew,this->pStrBuffer);
       delete [] pStrBuffer;
       strcat(pNew,strRight.pStrBuffer);
    }
    else
       strcpy(pNew,strRight.pStrBuffer);
    this->pStrBuffer=pNew;
 }
 printf("Leaving String::operator+=(const String&)!\n\n");

 return *this;
}


String String::Mid(unsigned int iStart, unsigned int iCount)
{
 printf("Entering String String::Mid(unsigned int iStart, unsigned int iCount)\n");
 unsigned int iLen,iNewSize;

 iLen=strlen(this->pStrBuffer);
 if(iStart && iStart<=iLen)
 {
    if(iCount && iStart+iCount-1<=iLen)
    {
       printf("  this->pStrBuffer = %u\t%s\n",(unsigned)this->pStrBuffer,this->pStrBuffer);
       iNewSize=(iCount*EXPANSION_FACTOR/16+1)*16;
       String sr((int)iNewSize);
       sr.iAllowableCharacterCount=iNewSize-1;
       strncpy(sr.pStrBuffer,this->pStrBuffer+iStart-1,iCount);
       sr.pStrBuffer[iCount]='\0';
       printf("Leaving String String::Mid(unsigned int iStart, unsigned int iCount)\n\n");
       return sr;
    }
    else
    {
       String sr=*this;
       printf("Leaving String String::Mid(unsigned int iStart, unsigned int iCount)\n\n");
       return sr;
    }
 }
 else
 {
    String sr=*this;
    printf("Leaving String String::Mid(unsigned int iStart, unsigned int iCount)\n\n");
    return sr;
 }
}


int String::LenStr(void)
{
 return strlen(this->pStrBuffer);
}


char* String::lpStr()
{
 return pStrBuffer;
}


void String::SetChar(unsigned int iOneBasedOffset, char tcChar)
{
 if((int)iOneBasedOffset<=this->iAllowableCharacterCount)
    this->pStrBuffer[iOneBasedOffset-1]=tcChar;
}


void String::Print(bool blnCrLf)
{
 printf("%s",pStrBuffer);
 if(blnCrLf)
    printf("\n");
}


String::~String()   //String Destructor
{
 printf("Entering String Destructor!\n");
 printf("  pStrBuffer = %u\t%s\n",(unsigned)pStrBuffer,pStrBuffer);
 delete [] pStrBuffer;
 pStrBuffer=0;
 printf("Leaving String Destructor!\n");
}

[MosaicFuneral]

Why do you have all those printf's in +=()? Maybe you should log the values into a record and print it afterwards and wrap it with #ifndef DEBUG.

[Frederick2]

I typically debug that way. I don't always like conditional compilation code in my programs. I do do that about half the time though. In this case I thought console output would be fine, as its just a small test program.

[Frederick2]

Here is the link to the other thread referred to in this post where all my String Class code for the full class is located, along with a number of programs utilizing it and their relative performance...

http://www.daniweb.com/forums/thread340738.html