speed of comparing char arrays

andy_t_roo · #1 29-Jun-2005, 02:08

In this program that i'm currently writing, a quick performance analysis shows that i'm spending >95% of my time in the following routine - it's a simple routine that compares 2 char arrays (thisGraph and otherGraph) and returns the element that is extra in otherGraph, or -1 if there is more than one difference.

would there be any way to make this run quicker?

the size of the arrays that i'm comparing is between 10 and 25 charachters.

CPP / C++ / C Code:

        int isParent(char* otherGraph,int otherSize){
                char thisSize;

                // simply returns a pointer to a pre constructed array and puts the size in thisSize;
                char* thisGraph=this->getGraph(thisSize);
				

                 //for this to be the parent, the size of child has to be
                //one bigger, and all of the parent has to be included in the child
                if(thisSize+1!=otherSize)
                        return -1;
                int i,diffLocation;
                for(i=0;thisGraph[i]==otherGraph[i];i++); // first difference
                diffLocation=i;
                for(;(thisGraph[i]==otherGraph[i+1])&&i<otherSize;i++);// stop at second difference 

                if(i==otherSize) // only 1 difference
                        return otherGraph[diffLocation];
                return -1;
        }

thanks,
Andrew H

maprich · #2 29-Jun-2005, 05:39

Are you calling this function many times in your program? If the answer is yes and you are not satisfied with the current performance then maybe you could consider rewriting it in inside assembly. As a c++ code it looks quite effective in my eyes. Maybe you can re-arrange the program logic?

There is a potential vulnerability in your code you should be aware of.
Consider if:
otherGraph is "somestringZ" and thisGraph is "somestring" .

otherSize is 1 bigger than thisSize but the one different char is the last one in otherGraph. Your code will crash in the first for loop because of index overflow.

No problem if you know 100% that above scenario will not occur.

Dave Sinkula · #3 29-Jun-2005, 07:57

CPP / C++ / C Code:

for(;(thisGraph[i]==otherGraph[i+1])&&i<otherSize;i++);

You may want to consider pointer notation instead of array notation. The compiler may be recalculating the position each time with thisGraph[i] and i++. You might try a pointer pThisGraph and a ++pThisGraph (and the same for the otherGraph) instead.

andy_t_roo · #4 30-Jun-2005, 18:12

maprich,
the arrays are null terminated, so that is fine.

Dave Sinkula,
thanks for the tip.
do know if g++(3.4.4) would do that optimisation automatically?

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
2D arrays:dynamic allocation and freeing	bravetanveer	C Programming Language	48	27-Nov-2007 15:55
[Tutorial] Pointers in C (Part I)	Stack Overflow	C Programming Language	1	08-Apr-2005 18:35
Compiling Errors	ToddSAFM	C++ Forum	22	18-Dec-2004 11:42
Comparing two arrays	Nelly	C++ Forum	2	16-Jun-2004 04:38