Which method is more efficient to merge strings?

Hello gurus, here is a question from an exercise:
Requirement: merge content of two strings. First method must use "new char". The second method should concatenate two strings.

QUESTION: WHICH METHOD IS BETTER?

My answer is the following, please let me know if I am wrong: Method 1 below using "new char" will allocate memory dynamically in the Heap. The Heap generally offers slower access than the memory allocated in the stack on method 2 below. Since memory was allocated using 'new', a explicit "delete" command will be needed to free memory and avoid a memory leak. The method 2 therefore accomplishes the same step using fewer lines of code and no need to deallocate memory.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//method 1: copy character by character to string; you must use "new char".
  Char * cat(char* string1, char* string2)
 {   
            Int size_s1 = strlen(string1); 
            Int size_s2 = strlen(string2);
 	    char * result = new char[size_s1+size_s2+1];
            Int i=0;
            While (string1[i] == ‘\0’) {
		Result[i] =  string1[i]; 
                         i++;
	}
          Int j=0;
          While (string2[j] == ‘\0’) {
                  Result[i] = string2[j];
                  i++;
                  j++;
             } 
          Result[i] = ‘\0’;      
	  Return result;
           
}
//Second method: concatenate strings
Std::string cat(const std::string & string1, const std::string & string2) {
	Return string1+string2;
}
Last edited on
It depends on how the std::string concatenation is implemented. I'm sure it will be as fast as possible. At the second function it will be returned a copy, whereby at the first only a pointer will get returned. You could avoid this copy if you pass and return a reference.
And usually std::string internally uses memory from heap, because it serves as a container.
It may be possible that the latter is faster because the CPU has to do less branch prediction; it already knows the length of each string, and can quick iterate over the sum of the string lengths, while the former has to calculate it. The former is also doing unnecessary branching: Your while loop on line 8 could just be a for loop since you've already calculated the length.

Overall, the two functions should be more or less the same, since the std::string version is basically doing the same thing under the covers. If you have return value optimization, then an extra copy wouldn't even be created, I don't think. But I always forget the caveats that determine whether or not RVO will actually happen.

As you mentioned, the std::string version handles the cleaning up of its memory automatically, so while this isn't necessarily a performance thing, it means that users of the function don't have to worry about manual memory management.

When in doubt... measure! Do (realistic) benchmarks!
Last edited on
the top one is exceedingly bad, not just for the dynamic memory, but that is maybe the worst piece of it.

I'd like to say the bottom one uses optimal code, but it may not. Ive seen a ton of slop in libraries lately.

I just noticed, the top one is bugged up. shouldn't it be != 0 when copying? The top one might be faster, though, given that....

here is a first cut at getting rid of the fluff.
1
2
3
4
5
6
7
8
9
10
 
char * cat(char* string1, char* string2)
 {   
     char * result = new char[strlen(string1) +  strlen(string2) +1]; //cant seem to get () zero init working?
     int i =0;    
     while (*string1) result[i++] = *string1++; 
     while (*string2) result[i++] = *string2++; 
	 result[i] = 0; //should be able to avoid this ^^
     return result;         
}


now if you were in a real fizz to get it done, I would do something so that the inputs were sized to a multiple of 8 bytes, cast out to 64 bit ints and move it 8 blocks at a time. I might also make a destructive version that appends 2 onto 1 without copying 1 at all, if string 1 is not useful after the copy.
Last edited on
Topic archived. No new replies allowed.