String Class operator+= Problem

[Frederick2]

Here is the full code relating to my performance problem I’m having with my operator+= which I described in this adjacent thread….

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

As a quick review, I’m finding that the operator+= function in the Standard C++ Library’s String Class, i.e., <string>, is performing almost impossibly fast compared to the one in my own String Class, and I’m looking for help or explanations why this is so. In the thread referred to above I provided a stripped down version of my String Class with piles of console output statements in the various implicated String Class member functions to help folks see what is going on, and hopefully provide ideas/comment on which I could work. However, below are four full programs with included performance timings from the Windows Api GetTickCount() function. Included in the programs are output statements which clearly show what is happening rather quickly, and what is taking a lot of time. Before I post the code, however, here is the string algorithm being processed…

'1) Create a 500000 character string of dashes or spaces;
'2) Change every 7th dash or space to a "P";
'3) SEARCH FOR AND Replace every "P" with a "PU" (hehehe);
'4) Replace every dash or space with an "8";
'5) Put in a carriage return & line feed every 90 characters;
'6) Output last 4000 characters.

Here is my first implementation which uses the C++ Standard Library String Class…

#include "windows.h"
#include <stdio.h>
#include <string>
#define  NUMBER 500000
using namespace std;

string& ReplaceAll(string& context, const string& from, const string& to)  //This is Bruce Eckel's
{                                                                          //function from "Thinking
 size_t lookHere=0;                                                        //In C++", Volume Two.
 size_t foundHere;

 while((foundHere=context.find(from,lookHere)) != string::npos)
 {
  context.replace(foundHere, from.size(), to);
  lookHere=foundHere+to.size();
 }

 return context;
}

int main(void)
{
 unsigned t1=0,t2=0;
 int iCount=0;
 string s2;

 t1=GetTickCount(), t2=t1;
 puts("Starting....");
 string s1(NUMBER,'-');
 t2=GetTickCount()-t2;
 printf("Finished Creating String With %u Of These - :   milliseconds elapsed - %u\n",NUMBER,t2),  t2=t1;
 for(int i=0; i<NUMBER; i++)
 {
     iCount++;
     if(iCount%7==0) s1[iCount-1]='P';
 }
 t2=GetTickCount()-t2;
 printf("Finished Inserting 'P's In s1!                  :   milliseconds elapsed - %u\n",t2),     t2=t1;
 ReplaceAll(s1,"P","PU");
 t2=GetTickCount()-t2;
 printf("Finished Replacing 'P's With PU!                :   milliseconds elapsed - %u\n",t2),     t2=t1;
 ReplaceAll(s1,"-","8");
 t2=GetTickCount()-t2;
 printf("Finished Replacing '-'s With 8!                 :   milliseconds elapsed - %u\n",t2),     t2=t1;
 s2.reserve(750000);
 puts("Now Going To Create Lines With CrLfs!");
 for(int i=0; i<NUMBER; i=i+90)
     s2+=s1.substr(i,90)+"\r\n";
 t2=GetTickCount()-t2;
 printf("Finished Creating Lines!                        :   milliseconds elapsed - %u\n",t2);
 s1=s2.substr(s2.length()-4000,4000);
 t1=GetTickCount()-t1;
 printf("t1 = %u\n",(unsigned)t1);
 MessageBox(NULL,s1.c_str(),"Here Is Your String John!",MB_OK);
 getchar();

 return 0;
}

It compiles to 46592 bytes statically linked to all necessary library code and optimized fully for speed. Here are results from a couple runs on my old Win 2000 Compaq laptop, which is rather slow…

//Starting....
//Finished Creating String With 500000 Of These - :   milliseconds elapsed - 0
//Finished Inserting 'P's In s1!                  :   milliseconds elapsed - 20
//Finished Replacing 'P's With PU!                :   milliseconds elapsed - 17365
//Finished Replacing '-'s With 8!                 :   milliseconds elapsed - 17435
//Now Going To Create Lines With CrLfs!
//Finished Creating Lines!                        :   milliseconds elapsed - 17445
//t1 = 17445

//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
//Finished Replacing '-'s With 8!                 :   milliseconds elapsed - 17415
//Now Going To Create Lines With CrLfs!
//Finished Creating Lines!                        :   milliseconds elapsed - 17425
//t1 = 17425

As can be easily seen above, almost all the time is being burnt up replacing the Ps with PUs through this call…

ReplaceAll(s1,"P","PU");

I’ll do the arithmetic for you. 17345 of the total time of 17425 is going down that sink hole. Note that the big concatenation at the end is taking next to no time at all…

for(int i=0; i<NUMBER; i=i+90)
s2+=s1.substr(i,90)+"\r\n";

Ten ticks is about as close to instantaneous as you are going to get. That’s all but unbelievable. But there are the real numbers I’m seeing.

Now here is the same program using my String Class. My String Class is rather large in code it seems (Strings.cpp is 779 lines), but compiles to 20 K less (27136 bytes) than the C++ Standard String Class. Here is Main.cpp followed by Strings.h and Strings.cpp required by Main.cpp…

#include <windows.h>
#include <tchar.h>
#include <stdio.h>
#include "Strings.h"
#define NUMBER 500000

int main()
{
 const TCHAR* const CrLf=_T("\r\n");
 DWORD t1,t2;
 String s2;

 puts("Starting....");
 t1 = GetTickCount(), t2=t1;
 String s1(_T('-'),NUMBER);
 t2=GetTickCount()-t2;
 printf("s1 has %u of these -                milliseconds elapsed %u\n",NUMBER,(unsigned)t2), t2=t1;
 for(int i=1; i<=NUMBER; i++)
     if(i%7==0) s1.SetChar(i,_T('P'));
 t2=GetTickCount()-t2;
 printf("s1 has 'P' every 7th char               milliseconds elapsed %u\n",(unsigned)t2),    t2=t1;
 s2=s1.Replace((TCHAR*)_T("P"),(TCHAR*)_T("PU"));
 t2=GetTickCount()-t2;
 printf("s2 created with PUs in place of Ps      milliseconds elapsed %u\n",(unsigned)t2),    t2=t1;
 s1=s2.Replace((TCHAR*)_T("-"),(TCHAR*)_T("8"));
 t2=GetTickCount()-t2;
 printf("dashes replaced with 8s                 milliseconds elapsed %u\n",(unsigned)t2),    t2=t1;
 s2.SetChar(1,'\0');
 printf("Now Do Concatenation...\n");
 for(int i=1; i<NUMBER; i+=90)
     s2+=s1.Mid(i,90)+CrLf;
 t2 = GetTickCount() - t1;
 printf("Finished Creating Lines                 milliseconds elapsed %u\n",(unsigned)t2),    t2=t1;
 s1=s2.Right(4000);
 t1 = GetTickCount() - t1;
 printf("t1 = %u\n",(unsigned)t1);
 MessageBox(0,s1.lpStr(),_T("Here's Your String John!"),MB_OK);
 getchar();

 return 0;
}

//Strings.h                                //My String Class
#if !defined(STRINGS_H)
#define STRINGS_H
#define EXPANSION_FACTOR      4
#define MINIMUM_ALLOCATION    128

class String
{
 public:
 String();                                 //Uninitialized Constructor
 String(const TCHAR);                      //Constructor Initializes String With TCHAR
 String(const TCHAR*);                     //Constructor Initializes String With TCHAR*
 String(const String&);                    //Constructor Initializes String With Another String (Copy Constructor)
 String(int);                              //Constructor Initializes Buffer To Specific Size
 String(const TCHAR, const int);           //Constructor initializes String with int # of chars
 String& operator=(const TCHAR);           //Assigns TCHAR To String
 String& operator=(const TCHAR*);          //Assigns TCHAR* To String
 String& operator=(const String&);         //Assigns one String to another (this one)
 String& operator=(int);                   //Converts And Assigns An Integer to A String
 String& operator=(unsigned int);          //Converts And Assigns An Unsigned Integer to A String
 String& operator=(long);                  //Converts And Assigns A Long to A String
 String& operator=(double);                //Converts And Assigns A double to A String
 String& operator+(const TCHAR);           //For adding TCHAR to String
 String& operator+(const TCHAR*);          //For adding null terminated TCHAR array to String
 String& operator+(const String&);         //For adding one String to Another
 String& operator+=(const String&);        //For Concatenating another String Onto this
 bool operator==(const String);            //For comparing Strings
 String Left(unsigned int);                //Returns String of iNum Left Most TCHARs of this
 String Right(unsigned int);               //Returns String of iNum Right Most TCHARs of this
 String Mid(unsigned int, unsigned int);   //Returns String consisting of number of TCHARs from some offset
 String& Make(const TCHAR, int);           //Creates (Makes) a String with iCount TCHARs
 String Remove(const TCHAR*, bool);        //Returns A String With A Specified TCHAR* Removed
 String Remove(TCHAR* pStr);               //Returns A String With All The TCHARs In A TCHAR* Removed (Individual char removal)
 String Retain(TCHAR* pStr);               //Seems to return a String with some characters retained???
 String Replace(TCHAR*, TCHAR*);           //Replace a match string found in this with a new string
 int InStr(const TCHAR);                   //Returns one based offset of a specific TCHAR in a String
 int InStr(const TCHAR*, bool);            //Returns one based offset of a particular TCHAR pStr in a String
 int InStr(const String&, bool);           //Returns one based offset of where a particular String is in another String
 void LTrim();                             //Returns String with leading spaces/tabs removed
 void RTrim();                             //Returns String with spaces/tabs removed from end
 void Trim();                              //Returns String with both leading and trailing whitespace removed
 unsigned int ParseCount(const TCHAR);     //Returns count of Strings delimited by a TCHAR passed as a parameter
 void Parse(String*, TCHAR);               //Returns array of Strings in first parameter as delimited by 2nd TCHAR delimiter
 int iVal();                               //Returns int value of a String
 int LenStr(void);                         //Returns length of string
 TCHAR* lpStr();                           //Returns address of pStrBuffer member variable
 TCHAR GetChar(unsigned int);              //Returns TCHAR at one based index
 void SetChar(unsigned int, TCHAR);        //Sets TCHAR at one based index
 void Print(bool);                         //Outputs String to Console with or without CrLf
 ~String();                                //String Destructor

 private:
 TCHAR* pStrBuffer;                        //Holds String Buffer Allocated In Various Overloaded Constructors And Members
 int    iAllowableCharacterCount;          //Persists Number of characters which will fit in this->pStrBuffer
};

String operator+(TCHAR* lhs, String& rhs); //global function
#endif  //#if !defined(STRINGS_H)

//Strings.cpp          == My String Class 
#include  <tchar.h>
#include  <stdlib.h>
#include  <stdio.h>
#include  <math.h>
#include  <string.h>
#include  "Strings.h"


String operator+(TCHAR* lhs, String& rhs)         //Global Function Which
{                                                 //Operates On String
 String sr=lhs;                                   //Objects
 sr=sr+rhs;
 return sr;
}


String::String()    //Uninitialized Constructor
{
 pStrBuffer=new TCHAR[MINIMUM_ALLOCATION];
 pStrBuffer[0]=_T('\0');
 this->iAllowableCharacterCount=MINIMUM_ALLOCATION-1;
}


String::String(const TCHAR ch)  //Constructor: Initializes with TCHAR
{
 pStrBuffer=new TCHAR[MINIMUM_ALLOCATION];
 pStrBuffer[0]=ch;
 pStrBuffer[1]=_T('\0');
 iAllowableCharacterCount=MINIMUM_ALLOCATION-1;
}


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

 iLen=_tcslen(pStr);
 iNewSize=(iLen/16+1)*16;
 pStrBuffer=new TCHAR[iNewSize];
 this->iAllowableCharacterCount=iNewSize-1;
 _tcscpy(pStrBuffer,pStr);
}


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

 iLen=_tcslen(s.pStrBuffer);
 iNewSize=(iLen/16+1)*16;
 this->pStrBuffer=new TCHAR[iNewSize];
 this->iAllowableCharacterCount=iNewSize-1;
 _tcscpy(this->pStrBuffer,s.pStrBuffer);
}


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

 iNewSize=(iSize/16+1)*16;
 pStrBuffer=new TCHAR[iNewSize];
 this->iAllowableCharacterCount=iNewSize-1;
 this->pStrBuffer[0]=_T('\0');
}


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

 iNewSize=(iCount/16+1)*16;
 pStrBuffer=new TCHAR[iNewSize];
 this->iAllowableCharacterCount=iNewSize-1;
 for(int i=0; i<iCount; i++)
     pStrBuffer[i]=ch;
 pStrBuffer[iCount]=_T('\0');
}


String& String::operator=(const TCHAR ch)  //Overloaded operator = for assigning a TCHAR to a String
{
 this->pStrBuffer[0]=ch;
 this->pStrBuffer[1]=_T('\0');

 return *this;
}


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

 iLen=_tcslen(pStr);
 if(iLen<this->iAllowableCharacterCount)
    _tcscpy(pStrBuffer,pStr);
 else
 {
    delete [] pStrBuffer;
    iNewSize=(iLen/16+1)*16;
    pStrBuffer=new TCHAR[iNewSize];
    this->iAllowableCharacterCount=iNewSize-1;
    _tcscpy(pStrBuffer,pStr);
 }

 return *this;
}


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

 if(this==&strRight)
    return *this;
 iRightLen=_tcslen(strRight.pStrBuffer);
 if(iRightLen < this->iAllowableCharacterCount)
    _tcscpy(pStrBuffer,strRight.pStrBuffer);
 else
 {
    iNewSize=(iRightLen/16+1)*16;
    delete [] this->pStrBuffer;
    this->pStrBuffer=new TCHAR[iNewSize];
    this->iAllowableCharacterCount=iNewSize-1;
    _tcscpy(pStrBuffer,strRight.pStrBuffer);
 }

 return *this;
}


bool String::operator==(const String strCompare)
{
 if(_tcscmp(this->pStrBuffer,strCompare.pStrBuffer)==0)  //_tcscmp
    return true;
 else
    return false;
}


String& String::operator+(const TCHAR ch)      //Overloaded operator + (Puts TCHAR in String)
{
 int iLen,iNewSize;
 TCHAR* pNew;

 iLen=_tcslen(this->pStrBuffer);
 if(iLen<this->iAllowableCharacterCount)
 {
    this->pStrBuffer[iLen]=ch;
    this->pStrBuffer[iLen+1]='\0';
 }
 else
 {
    iNewSize=((this->iAllowableCharacterCount*EXPANSION_FACTOR)/16+1)*16;
    pNew=new TCHAR[iNewSize];
    this->iAllowableCharacterCount=iNewSize-1;
    _tcscpy(pNew,this->pStrBuffer);
    delete [] this->pStrBuffer;
    this->pStrBuffer=pNew;
    this->pStrBuffer[iLen]=ch;
    this->pStrBuffer[iLen+1]='\0';
 }

 return *this;
}


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

 iLen=_tcslen(this->pStrBuffer)+_tcslen(pChar);
 if(iLen<this->iAllowableCharacterCount)
 {
    if(this->pStrBuffer)
       _tcscat(this->pStrBuffer,pChar);
    else
       _tcscpy(this->pStrBuffer, pChar);
 }
 else
 {
    iNewSize=(iLen*EXPANSION_FACTOR/16+1)*16;
    pNew=new TCHAR[iNewSize];
    this->iAllowableCharacterCount = iNewSize-1;
    if(this->pStrBuffer)
    {
       _tcscpy(pNew,this->pStrBuffer);
       delete [] pStrBuffer;
       _tcscat(pNew,pChar);
    }
    else
       _tcscpy(pNew,pChar);
    this->pStrBuffer=pNew;
 }

 return *this;
}


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

 iLen=_tcslen(this->pStrBuffer) + _tcslen(strRight.pStrBuffer);
 if(iLen < this->iAllowableCharacterCount)
 {
    if(this->pStrBuffer)
       _tcscat(this->pStrBuffer,strRight.pStrBuffer);
    else
       _tcscpy(this->pStrBuffer,strRight.pStrBuffer);
 }
 else
 {
    iNewSize=(iLen*EXPANSION_FACTOR/16+1)*16;
    pNew=new TCHAR[iNewSize];
    this->iAllowableCharacterCount=iNewSize-1;
    if(this->pStrBuffer)
    {
       _tcscpy(pNew,this->pStrBuffer);
       delete [] pStrBuffer;
       _tcscat(pNew,strRight.pStrBuffer);
    }
    else
       _tcscpy(pNew,strRight.pStrBuffer);
    this->pStrBuffer=pNew;
 }

 return *this;
}


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

 iLen=_tcslen(this->pStrBuffer) + _tcslen(strRight.pStrBuffer);
 if(iLen < this->iAllowableCharacterCount)
 {
    if(this->pStrBuffer)
       _tcscat(this->pStrBuffer,strRight.pStrBuffer);
 }
 else
 {
    iNewSize=(iLen*EXPANSION_FACTOR/16+1)*16;
    pNew=new TCHAR[iNewSize];
    this->iAllowableCharacterCount=iNewSize-1;
    if(this->pStrBuffer)
    {
       _tcscpy(pNew,this->pStrBuffer);
       delete [] pStrBuffer;
       _tcscat(pNew,strRight.pStrBuffer);
    }
    else
       _tcscpy(pNew,strRight.pStrBuffer);
    this->pStrBuffer=pNew;
 }

 return *this;
}


String String::Left(unsigned int iNum)
{
 unsigned int iLen,i,iNewSize;

 iLen=_tcslen(this->pStrBuffer);
 if(iNum<iLen)
 {
    iNewSize=(iNum*EXPANSION_FACTOR/16+1)*16;
    String sr((int)iNewSize);
    sr.iAllowableCharacterCount=iNewSize-1;
    sr.pStrBuffer=new TCHAR[iNewSize];
    for(i=0;i<iNum;i++)
        sr.pStrBuffer[i]=this->pStrBuffer[i];
    sr.pStrBuffer[iNum]='\0';
    return sr;
 }
 else
 {
    String sr(*this);
    return sr;
 }
}


String String::Right(unsigned int iNum)  //Returns Right$(strMain,iNum)
{
 unsigned int iLen,iNewSize;

 iLen=_tcslen(this->pStrBuffer);
 if(iNum<iLen)
 {
    iNewSize=(iNum*EXPANSION_FACTOR/16+1)*16;
    String sr((int)iNewSize);
    sr.iAllowableCharacterCount=iNewSize-1;
    sr.pStrBuffer=new TCHAR[iNewSize];
    _tcsncpy(sr.pStrBuffer,this->pStrBuffer+iLen-iNum,iNum);
    sr.pStrBuffer[iNum]='\0';
    return sr;
 }
 else
 {
    String sr(*this);
    return sr;
 }
}


String String::Mid(unsigned int iStart, unsigned int iCount)
{
 unsigned int iLen,iNewSize;

 iLen=_tcslen(this->pStrBuffer);
 if(iStart && iStart<=iLen)
 {
    if(iCount && iStart+iCount-1<=iLen)
    {
       iNewSize=(iCount*EXPANSION_FACTOR/16+1)*16;
       String sr((int)iNewSize);
       sr.iAllowableCharacterCount=iNewSize-1;
       _tcsncpy(sr.pStrBuffer,this->pStrBuffer+iStart-1,iCount);
       sr.pStrBuffer[iCount]='\0';
       return sr;
    }
    else
    {
       String sr(*this);
       return sr;
    }
 }
 else
 {
    String sr(*this);
    return sr;
 }
}


String& String::Make(const TCHAR ch, int iCount)    //Creates (Makes) a String with iCount TCHARs
{
 if(iCount>this->iAllowableCharacterCount)
 {
    delete [] pStrBuffer;
    int iNewSize=(iCount*EXPANSION_FACTOR/16+1)*16;
    this->pStrBuffer=new TCHAR[iNewSize];
    this->iAllowableCharacterCount=iNewSize-1;
 }
 for(int i=0; i<iCount; i++)
     pStrBuffer[i]=ch;
 pStrBuffer[iCount]=_T('\0');

 return *this;
}


String String::Remove(const TCHAR* pToRemove, bool blnCaseSensitive)
{
 int i,j,iParamLen,iReturn=0;

 if(*pToRemove==0)
    return *this;
 String strNew(this->LenStr());
 iParamLen=_tcslen(pToRemove);
 i=0, j=0;
 do
 {
  if(pStrBuffer[i]==0)
     break;
  if(blnCaseSensitive)
     iReturn=_tcsncmp(pStrBuffer+i,pToRemove,iParamLen);  //_tcsncmp
  else
     iReturn=_tcsnicmp(pStrBuffer+i,pToRemove,iParamLen); //__tcsnicmp
  if(iReturn==0)
     i=i+iParamLen;
  strNew.pStrBuffer[j]=pStrBuffer[i];
  j++, i++;
  strNew.pStrBuffer[j]=_T('\0');
 }while(1);

 return strNew;
}


String String::Remove(TCHAR* pStr)
{
 unsigned int i,j,iStrLen,iParamLen;
 TCHAR *pThis, *pThat, *p;
 bool blnFoundBadChar;

 iStrLen=this->LenStr();    //The length of this
 String sr((int)iStrLen);   //Create new String big enough to contain original String (this)
 iParamLen=_tcslen(pStr);   //Get length of parameter (pStr) which contains chars to be removed
 pThis=this->pStrBuffer;
 p=sr.lpStr();
 for(i=0; i<iStrLen; i++)
 {
     pThat=pStr;
     blnFoundBadChar=false;
     for(j=0; j<iParamLen; j++)
     {
         if(*pThis==*pThat)
         {
            blnFoundBadChar=true;
            break;
         }
         pThat++;
     }
     if(!blnFoundBadChar)
     {
        *p=*pThis;
         p++;
        *p=_T('\0');
     }
     pThis++;
 }

 return sr;
}


String String::Retain(TCHAR* pStr)
{
 unsigned int i,j,iStrLen,iParamLen;
 TCHAR *pThis, *pThat, *p;
 bool blnFoundGoodChar;

 iStrLen=this->LenStr();    //The length of this
 String sr((int)iStrLen);   //Create new String big enough to contain original String (this)
 iParamLen=_tcslen(pStr);   //Get length of parameter (pStr) which contains chars to be retained
 pThis=this->pStrBuffer;    //pThis will point to this String's buffer, and will increment through string.
 p=sr.lpStr();              //p will start by pointing to new String's buffer and will increment through new string
 for(i=0; i<iStrLen; i++)
 {
     pThat=pStr;
     blnFoundGoodChar=false;
     for(j=0; j<iParamLen; j++)
     {
         if(*pThis==*pThat)
         {
            blnFoundGoodChar=true;
            break;
         }
         pThat++;
     }
     if(blnFoundGoodChar)
     {
        *p=*pThis;
         p++;
        *p=_T('\0');
     }
     pThis++;
 }

 return sr;
}


String String::Replace(TCHAR* pMatch, TCHAR* pNew)
{
 int iLenMatch,iLenNew,iLenMainString,iCountMatches,iExtra,iExtraLengthNeeded,iAllocation,iCtr;
 String sr;

 iCountMatches=0, iAllocation=0, iCtr=0;
 iLenMatch=_tcslen(pMatch);
 iLenNew=_tcslen(pNew);
 iLenMainString=this->LenStr();
 if(iLenNew==0)
    sr=this->Remove(pMatch); //return
 else
 {
    iExtra=iLenNew-iLenMatch;
    for(int i=0; i<iLenMainString; i++)
        if(_tcsncmp(pStrBuffer+i,pMatch,iLenMatch)==0) iCountMatches++;  //Count how many
    iExtraLengthNeeded=iCountMatches*iExtra;                             //match strings
    iAllocation=iLenMainString+iExtraLengthNeeded;
    String strNew(iAllocation);
    for(int i=0; i<iLenMainString; i++)
    {
        if(_tcsncmp(pStrBuffer+i,pMatch,iLenMatch)==0)
        {
           _tcscpy(strNew.pStrBuffer+iCtr,pNew);
           iCtr=iCtr+iLenNew;
           i=i+iLenMatch-1;
        }
        else
        {
           strNew.pStrBuffer[iCtr]=this->pStrBuffer[i];
           iCtr++;
        }
        strNew.pStrBuffer[iCtr]=_T('\0');
    }
    sr=strNew;
 }

 return sr;
}


int String::InStr(const TCHAR ch)
{
 int iLen,i;

 iLen=_tcslen(this->pStrBuffer);
 for(i=0;i<iLen;i++)
 {
     if(this->pStrBuffer[i]==ch)
        return (i+1);
 }

 return 0;
}


int String::InStr(const TCHAR* pStr, bool blnCaseSensitive)
{
 int i,iParamLen,iRange;

 if(*pStr==0)
    return 0;
 iParamLen=_tcslen(pStr);
 iRange=_tcslen(pStrBuffer)-iParamLen;
 if(iRange>=0)
 {
    for(i=0;i<=iRange;i++)
    {
        if(blnCaseSensitive)
        {
           if(_tcsncmp(pStrBuffer+i,pStr,iParamLen)==0)   //_tcsncmp
              return i+1;
        }
        else
        {
           if(_tcsnicmp(pStrBuffer+i,pStr,iParamLen)==0)  //__tcsnicmp
              return i+1;
        }
    }
 }

 return 0;
}


int String::InStr(const String& s, bool blnCaseSensitive)
{
 int i,iParamLen,iRange,iLen;

 iLen=_tcslen(s.pStrBuffer);
 if(iLen==0)
    return 0;
 iParamLen=iLen;
 iRange=_tcslen(pStrBuffer)-iParamLen;
 if(iRange>=0)
 {
    for(i=0;i<=iRange;i++)
    {
        if(blnCaseSensitive)
        {
           if(_tcsncmp(pStrBuffer+i,s.pStrBuffer,iParamLen)==0)  //_tcsncmp
              return i+1;
        }
        else
        {
           if(_tcsnicmp(pStrBuffer+i,s.pStrBuffer,iParamLen)==0) //__tcsnicmp
              return i+1;
        }
    }
 }

 return 0;
}


void String::LTrim()
{
 unsigned int i,iCt=0,iLenStr;

 iLenStr=this->LenStr();
 for(i=0;i<iLenStr;i++)
 {
     if(pStrBuffer[i]==32||pStrBuffer[i]==9)
        iCt++;
     else
        break;
 }
 if(iCt)
 {
    for(i=iCt;i<=iLenStr;i++)
        pStrBuffer[i-iCt]=pStrBuffer[i];
 }
}


void String::RTrim()
{
 unsigned int iCt=0, iLenStr;

 iLenStr=this->LenStr()-1;
 for(unsigned int i=iLenStr; i>0; i--)
 {
     if(this->pStrBuffer[i]==9||this->pStrBuffer[i]==10||this->pStrBuffer[i]==13||this->pStrBuffer[i]==32)
        iCt++;
     else
        break;
 }
 this->pStrBuffer[this->LenStr()-iCt]=0;
}


void String::Trim()
{
 this->LTrim();
 this->RTrim();
}


unsigned int String::ParseCount(const TCHAR c) //returns one more than # of
{                                              //delimiters so it accurately
 unsigned int iCtr=0;                          //reflects # of strings delimited
 TCHAR* p;                                     //by delimiter.

 p=this->pStrBuffer;
 while(*p)
 {
  if(*p==c)
     iCtr++;
  p++;
 }

 return ++iCtr;
}


void String::Parse(String* pStr, TCHAR delimiter)
{
 unsigned int i=0;
 TCHAR* pBuffer=0;
 TCHAR* c;
 TCHAR* p;

 pBuffer=new TCHAR[this->LenStr()+1];
 if(pBuffer)
 {
    p=pBuffer;
    c=this->pStrBuffer;
    while(*c)
    {
     if(*c==delimiter)
     {
        pStr[i]=pBuffer;
        p=pBuffer;
        i++;
     }
     else
     {
        *p=*c;
        p++;
        *p=0;
     }
     c++;
    }
    pStr[i]=pBuffer;
    delete [] pBuffer;
 }
}


int String::iVal()
{
 return _ttoi(this->pStrBuffer);  //_ttoi
}


String& String::operator=(int iNum)
{
 if(this->iAllowableCharacterCount<16)
 {
    int iNewSize;
    delete [] this->pStrBuffer;
    iNewSize=16;
    pStrBuffer=new TCHAR[iNewSize];
    this->iAllowableCharacterCount=iNewSize-1;
 }
 _stprintf(this->pStrBuffer,_T("%d"),iNum);

 return *this;
}


String& String::operator=(unsigned int iNum)
{
 if(this->iAllowableCharacterCount<16)
 {
    int iNewSize;
    delete [] this->pStrBuffer;
    iNewSize=16;
    pStrBuffer=new TCHAR[iNewSize];
    this->iAllowableCharacterCount=iNewSize-1;
 }
 _stprintf(this->pStrBuffer,_T("%d"),iNum);

 return *this;
}


String& String::operator=(long iNum)
{
 if(this->iAllowableCharacterCount<16)
 {
    int iNewSize;
    delete [] this->pStrBuffer;
    iNewSize=16;
    pStrBuffer=new TCHAR[iNewSize];
    this->iAllowableCharacterCount=iNewSize-1;
 }
 _stprintf(this->pStrBuffer,_T("%ld"),iNum);

 return *this;
}


String& String::operator=(double dblNum)
{
 if(this->iAllowableCharacterCount<16)
 {
    int iNewSize;
    delete [] this->pStrBuffer;
    iNewSize=32;
    pStrBuffer=new TCHAR[iNewSize];
    this->iAllowableCharacterCount=iNewSize-1;
 }
 _stprintf(this->pStrBuffer,_T("%10.14f"),dblNum);

 return *this;
}


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


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


TCHAR String::GetChar(unsigned int iOffset)
{
 return this->pStrBuffer[iOffset-1];
}


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


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


String::~String()   //String Destructor
{
 delete [] pStrBuffer;
 pStrBuffer=0;
}

Whew! I know…..

Anyway, here are the timings on that…

//Starting....
//s1 has 500000 of these -                milliseconds elapsed        0
//s1 has 'P' every 7th char               milliseconds elapsed       10
//s2 created with PUs in place of Ps      milliseconds elapsed       80
//dashes replaced with 8s                 milliseconds elapsed      150
//t1 =                                    completed concatenation 12538

Its beating the Standard C++ Library by almost 5000 ticks or five seconds. But that’s where things really start to get weird! My string class is only taking 70 ticks to replace the Ps with PUs (see my String::Replace() member function), whereas the ReplaceAll() function from Bruce Eckel which takes Std. C++ Library String Class parameters is taking like 17000 ticks or 17 seconds to do it! However, my String Class is taking some 12,400 ticks or twelve seconds to do what the Std. Library String Class is doing in 10 ticks or 0.010 seconds!!!! Go figure! All in all I’m coming out way ahead with my String Class, but I’m completely vexed by the time difference and apparent lack of performance of my operator+= String Class member compared to what I’m seeing with the Std. Lib. String Class.

In an attempt to see what I could do to lessen the time I thought I’d do just simple strcpy(), strcat() calls from the Standard C String Library, which I suppose are sitting right on top of the asm string primitives that blast memory blocks about blindingly fast, so here is that iteration of the program which is exactly the same as the above one except for the for loop at bottom with strcpy(), strcat() calls instead of my String Class member function calls…

#include <windows.h>
#include <tchar.h>
#include <stdio.h>
#include "Strings.h"
#define NUMBER 500000

int main()
{
 String s1(_T(' '),NUMBER);
 DWORD t1=0,t2=0;
 String s2;

 t1 = GetTickCount();
 for(int i=1; i<=NUMBER; i++)
     if(i%7==0)  s1.SetChar(i,_T('P'));
 t2=GetTickCount()-t1;
 printf("t2=%u\tAfter Setting Ps\n",(unsigned)t2), t2=t1;
 s2=s1.Replace((TCHAR*)_T("P"),(TCHAR*)_T("PU"));
 t2=GetTickCount()-t1;
 printf("t2=%u\tAfter Doing PUs\n",(unsigned)t2), t2=t1;
 s1=s2.Replace((TCHAR*)_T(" "),(TCHAR*)_T("8"));
 t2=GetTickCount()-t1;
 printf("t2=%u\tAfter Doing 8s\n",(unsigned)t2), t2=t1;
 s2.Make(_T('\0'),2200000);
 t2=GetTickCount()-t1;
 printf("t2=%u\tAfter Making s2\n",(unsigned)t2), t2=t1;
 TCHAR* pBuf1=s1.lpStr();
 TCHAR* pBuf2=s2.lpStr();
 for(int i=0; i<NUMBER; i+=90)
 {
     _tcsncpy(pBuf2,pBuf1,90);
     _tcscat(pBuf2,(TCHAR*)_T("\r\n"));
     pBuf2=pBuf2+92;
     pBuf1=pBuf1+90;
 }
 t2=GetTickCount()-t1;
 printf("t2=%u\tAfter Concatenation\n",(unsigned)t2), t2=t1;
 s1=s2.Right(4000);
 t2 = GetTickCount()-t1,  printf("t2=%u\n",(unsigned)t2);
 MessageBox(NULL,s1.lpStr(),_T("Here's Your String John!"),MB_OK);
 getchar();

 return 0;
}

t2=10 After Setting Ps
t2=80 After Doing PUs
t2=150 After Doing 8s
t2=160 After Making s2
t2=160 After Concatenation
t2=160

Well, that did the trick, how about it!?! Who says C isn’t worth learning? But it still doesn’t answer my original question about why my String Class is doing so bad at the concatenation compared to the Standard C++ Library String Class. Just as a matter of interest, here is a PowerBASIC program implementing the same algorithm. It does this in 40 ticks and compiles to 9216 bytes! That’s 1/3 rd the size of my smallest C++ version and four times faster…

#Compile Exe
#Dim All
Declare Function GetTickCount Lib "Kernel32.dll" Alias "GetTickCount" () As Dword
Declare Function printf CDecl Lib "msvcrt.dll" Alias "printf" (szFmtStr As Asciiz, lpVar1 As Any) As Long

Declare Function MessageBox Lib "User32.dll" Alias "MessageBoxA" _
(
 Byval hWnd As Dword, _
 lpText As Asciiz, _
 lpCaption As Asciiz, _
 Byval dwType As Dword _
) As Long

Function PBMain() As Long
  Register i As Long, iCnt As Long
  Local currPos As Long
  Local s, s1 As String
  Local tick As Dword

  tick = getTickCount()
  s = String$(500000, "-")      '1) Make String With 500000 dashes
  For i = 1 To 500000
    Incr iCnt
    If iCnt = 7 Then
       iCnt = 0
       Asc(s, i) = &h50         '2) Put Ps Every 7th character
    End If
  Next
  Replace "P" With "PU" In s    '3) Replace Ps with PUs
  Replace Any "-" With "8" In s '4) Change dashes to 8s
  s1 = String$(600000, $NUL)    '5) 2nd string for CRLF's a little bigger
  currPos = 1                   'for s2 position tracking
  For i = 1 To 500000 Step 90
    Mid$(s1, currPos) = Mid$(s, i, 90) & $CRLF
    currPos = currPos + 92
  Next ii
  s=Right$(s, 4000)
  tick = getTickCount() - tick
  printf("tick = %u",Byval tick)
  MessageBox(0,Byval Strptr(s),"Last 4000 Characters Of Result",%MB_OK)

  PBMain=0
End Function

[MosaicFuneral]

Store the string length before hand, add the length of the two strings to find the new length, if the new length is greater than the current capacity then you call to increase the size, then call to have the the data of the new string concatenated to yours.

class String
{
    private:
            size_t length;
            TCHAR  *data;
    public:
            String size() { return(length); }

            &String::operator+=(const String& str) {
              size_t new_length = this->size() + str.size();

              if(new_length > this.capacity())
                this->reallocate_reserve(new_length);

              concatenate(...);
            }
};

That's pretty much what's in the g++(well technically +=() calls append(), but whatever)

BTW, you should read this: http://www.agner.org/optimize/optimizing_cpp.pdf

[Frederick2]

Thanks for looking at my posts MosaicFuneral. That link you gave is interesting. I’m going to save and study it. In terms of this…

Store the string length before hand, add the length of the two strings to find the new length, if
the new length is greater than the current capacity then you call to increase the size, then call
to have the the data of the new string concatenated to yours.

I do believe I’m already doing that. Here are the private data members of my String Class…

private:
 TCHAR* pStrBuffer;                   //Holds String Buffer Allocated In Various Overloaded Constructors And Members
 int    iAllowableCharacterCount;     //Persists Number of characters which will fit in this->pStrBuffer

All my member functions which allocate memory (constructors, overloaded operator functions, etc.) allocate it on 16 byte paragraph boundaries and always round up to multiples of 16 bytes. Here is my operator+= member. You can see the very first line obtains the length of the string controlled by ‘this’ plus the length to be added, i.e., strRight. If the buffer indicated by my iAllowableCharacterCount member is big enough, the strRight is strcat()’ed to it. If not, a memory re-allocation occurs, and both strings are moved to the new and larger buffer. I might point out that in the real program there would be next to none of this time wasting re-allocation and string movement taking place. My swap/temp space is s2. Here it would have been made large enough to accommodate the larger string with the ‘PUs’ instead of just the ‘Ps’…

s2=s1.Replace((TCHAR*)_T("P"),(TCHAR*)_T("PU"));

Also note my EXPANSION_FACTOR define in the string class header. It is set to ‘4’ for this example which is extremely, extremely aggressive. Also, the MINIMUM_ALLOCATION was set to 128 which is also ridiculously high. I did that just to protect myself against the 92 byte chunk copies. Still no dice. The Std Lib String class is killing me.

String& String::operator+=(const String& strRight)
{
 int iLen=_tcslen(this->pStrBuffer) + _tcslen(strRight.pStrBuffer);  //get length of both
 if(iLen < this->iAllowableCharacterCount)                           //compare with present
    _tcscat(this->pStrBuffer,strRight.pStrBuffer);                   //allocation
 else                                                                //present alloc isn’t
 {                                                                   //enough, so re-alloc
    int iNewSize=(iLen*EXPANSION_FACTOR/16+1)*16;                    //and copy both to new
    TCHAR* pNew=new TCHAR[iNewSize];                                 //memory
    this->iAllowableCharacterCount=iNewSize-1;
    if(this->pStrBuffer)
    {
       _tcscpy(pNew,this->pStrBuffer);
       delete [] pStrBuffer;
       _tcscat(pNew,strRight.pStrBuffer);
    }
    else
       _tcscpy(pNew,strRight.pStrBuffer);
    this->pStrBuffer=pNew;
 }

 return *this;
}

You hsve given me an idea though that I want to check out further…

[MosaicFuneral]

Yes, it's pretty much a similar concept but you're shoving it all in one oversized function. The example I showed you kept things small, clean, and minimal.

[Frederick2]

I finally got your point MosaicFuneral. I haven't been saving the string length of 'this' in any of my member functions. That I haven't no doubt goes all the way back to when I first started to develop my own string class 3 or 4 years ago, I was only concerned with getting it to work at all; I wasn't concerned with speed or efficiency. Until now, that is. The way it is now my string lengths are being calculated in every member function call, and each concatenation in a loop is making about four calls or so. So I've added a private string length member to my class, and I'm working through the code now making the necessary changes. All the while I'm thinking, "Wow! "Should have done this before!". When I get it done I come back with the performance improvements. I can't help thinking they'll be substantial.