C: What is the best and fastest way to concatenate strings

Question

I currently concatenate strings in c using the strcat() function from string.h library.

I thought about it, and I got to a conclusion that it should be very expensive function, as before it starts to concatenate, it has to iterate over the char array until it finds the '\0' char.

For example, if I concatenate the string "horses" 1000 times using strcat(), I'll have to pay (1 + 2 + 3 + ... + 1000) * strlen("horses") = (1000*1001)/2 * 6 = 3003000

I thought about the non-standard way, of maintaining an integer with the string length, and then sending to strcat() the pointer to the end of the string:

strcat(dest + dest_len, "string");

In this case, I'll pay only 1000 * strlen("horses") = 1000 * 6 = 6000.

6000 is 500x smaller than 3003000, so it can be very critical for performance if you make a lot of such concatenations.

Is there some more standard way to do it, looking better than my solution?

Answer 1

Joel Spolsky, in his Back to Basics article, describes the problem of inefficient string concatenation with strcat as the Shlemiel the painter's algorithm (read the article, it's quite good). As an example of inefficient code, he gives this example, which runs in O(n²) time:

char bigString[1000];     /* I never know how much to allocate... */
bigString[0] = '\0';
strcat(bigString,"John, ");
strcat(bigString,"Paul, ");
strcat(bigString,"George, ");
strcat(bigString,"Joel ");

It's not really a problem to walk over the first string the first time; since we've already got to walk over the second string, the runtime of one strcat is linear in the length of the result. Multiple strcats is problematic though, because we walk over the previously concatenated results again and again. He provides this alternative:

How do we fix this? A few smart C programmers implemented their own mystrcat as follows:

char* mystrcat( char* dest, char* src )
{
     while (*dest) dest++;
     while (*dest++ = *src++);
     return --dest;
}

What have we done here? At very little extra cost we're returning a pointer to the end of the new, longer string. That way the code that calls this function can decide to append further without rescanning the string:

char bigString[1000];     /* I never know how much to allocate... */
char *p = bigString;
bigString[0] = '\0';
p = mystrcat(p,"John, ");
p = mystrcat(p,"Paul, ");
p = mystrcat(p,"George, ");
p = mystrcat(p,"Joel ");

This is, of course, linear in performance, not n-squared, so it doesn't suffer from degradation when you have a lot of stuff to concatenate.

Of course, this is what you can do if you want to use standard C strings. The alternative that you're describing of caching the length of the string and using a special concatenation function (e.g., calling strcat with slightly different arguments) is sort of a variation on Pascal strings, which Joel also mentioned:

The designers of Pascal were aware of this problem and "fixed" it by storing a byte count in the first byte of the string. These are called Pascal Strings. They can contain zeros and are not null terminated. Because a byte can only store numbers between 0 and 255, Pascal strings are limited to 255 bytes in length, but because they are not null terminated they occupy the same amount of memory as ASCIZ strings. The great thing about Pascal strings is that you never have to have a loop just to figure out the length of your string. Finding the length of a string in Pascal is one assembly instruction instead of a whole loop. It is monumentally faster.

…

For a long time, if you wanted to put a Pascal string literal in your C code, you had to write:

char* str = "\006Hello!";

Yep, you had to count the bytes by hand, yourself, and hardcode it into the first byte of your string. Lazy programmers would do this, and have slow programs:

char* str = "*Hello!";
str[0] = strlen(str) - 1;

Answer 2

If you want it easy, fast, general, and safe, I suggest using the open_memstream() function (it's a part of the POSIX-2008 standard, unfortunately it did not make it into the C11 standard, thought). It works like this:

First, you hand it the address of a pointer and a size

char* result = NULL;
size_t resultSize = 0;
FILE* stream = open_memstream(&result, &resultSize);

the return value is a file stream just as if you had used fopen() to open a file. As such, you can use the entire arsenal of fprintf() & co. to stream anything you like to your memory buffer, which is automatically allocated and managed for you. Most importantly, it also keeps track of the size of the accumulated string, so it does not have to rescan it to compute its size.

for(int i = 0; i < 1000000; i++) {
    fprintf(stream, "current number is %d, or 0x%x\n", i, i);
}

Finally, you close the stream, which will update your result pointer and the size variable to reflect the actual amount of string data written.

fclose(stream);
//Now you have a zero terminated C-string in result, and also its size in resultSize.
//You can do with it whatever you like.
//Just remember to free it afterwards:
free(result);

Answer 3

To concatenate multiple strings, code may use strlen() and memcpy() which are both often well optimized functions.

With this approach, easy to add an inexpensive size limit.
Given the real chance the destination buffer may overflow otherwise, a size limit is essential.

Run time proportional to the sum of string lengths: O(len(S[0]) + len(S[1]) + len(S[2]) + ...)

char *strsncat(char *dest, size_t size, char * strs[], size_t n) {
  assert(size > 0);
  size--;
  char *p = dest;
  while (n-- > 0) {
    size_t len = strlen(*strs);
    if (len >= size) {
      len = size;
    }
    size -= len;
    memcpy(p, *strs, len);
    strs++;
    p += len;
  }
  *p = '\0';
  return dest;
}

void cat_test(void) {
  char dest[10];
  char *strs[]  = { "Red", "Green", "Blue" };
  printf("'%s'\n",strsncat(dest, sizeof dest, strs, sizeof strs/sizeof strs[0]));
  // 'RedGreenB'
}