Is this a fast implementation of reversing a string?

Question

I thought of this algorithm today. It seems fast, but how can I know?

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

/*
 * Reverse a string
 * the caller has to free dynamic memory allocated
 */
char *mon_string_rev(char *string)
{
    char *out = malloc ( strlen(string) + 1 );

    assert(out);

    int len = strlen(string);

    int i;

    int counter = 0;

    int iterations = 0;

    while(1) {
        if(len < 0) break;
        // important to only start counting after 
        // determing that the loop will continue
        ++iterations;
        for(i = 0; i < len; i++) {
            // if this is the last character
            // push it onto the output string
            if(i == (len - 1)) {
                out[counter] = string[i];
                counter++;
            }
        }
        len--;
    }
    out[counter] = '\0';

    printf("Total iterations: %d\n", iterations);

    return out;

}

int main(int argc, char **argv)
{

    if(argc < 2) {
        fprintf(stderr, "Usage: %s <string>", argv[0]);
        exit(1);
    }

    char *str = mon_string_rev(argv[1]);

    printf("%s\n", str);

    free(str);

    return !1;

}

Answer 1

Over all, this is good, but there's unfortunately some very major performance problems, and I have a few minor design suggestions.

---

A string can be reversed quite trivially in linear time. Your algorithm is quadratic.

You can just do a single backwards loop over the input string instead of this convoluted nested loop.

---

Since mon_string_rev doesn't alter string it should be a pointer to constant character.

---

Instead of asserting that out isn't null, it might be better to simply return null instead. That allows the caller to handle the error instead of program termination (and when assertions are disabled, it avoids a rather nasty segfault...).

---

If you're using C99 or newer (and you should be), then declare variables in the tightest scope possible (i.e. declare i in the for loop).

---

return !1;... what? Just return 0, or, better yet, return EXIT_SUCCESS.

---

Any time you have an infinite loop terminated by a simple condition, just rewrite it to directly use that simple condition. Terminating 'infinite' loops are very hard to understand when you weren't the person who wrote them, so any time they can be avoided they should be.

Just to illustrate, your loop could instead be: for (; len >= 0; --len) { ... }.

---

It doesn't really apply here since instrumentation was clearly the main purpose, but in general it's a bad idea to have functions output anything unless their sole purpose is output. (Sorry if you already know this :).)

---

When it doesn't meaningful affect performance or usability, I like to have the caller manage memory. It's more flexible, and it's more explicit (no question of "wait... do I release this???").

Answer 2

Memory management

It's not a good idea to allocate memory in one function and free in another. Of course, if you allocate the output string in mon_string_rev, then you don't really have a choice. So it's better to allocate it in the caller instead. If you recall, this is how strcpy (and its friends) work, they expect the destination to be created.

Suggested implementation

Considering better memory management, and other simplifications, the main method would be better this way:

void str_reverse(char *str, char *out, int len)
{
    int i;
    for (i = 0; i <= len / 2; ++i) {
        out[i] = str[len - i - 1];
        out[len - i - 1] = str[i];
    }
    out[len] = '\0';
}

Several things to note:

• I pass to the method both the output string and its length, similar to strncpy. It is the caller's responsibility to correctly allocate the output and to pass a length value that won't lead to buffer overflow.
• It's enough to iterate until the middle of the string, and set the i-th and n-i-th letters.

Answer 3

Focusing on performance improvements, there are at least two main improvement points in your code:

• Extraneous call to strlen(). Bare in mind that a C string, unlike its C++ std::string counterpart, does not carry extra information about its length, except for the null char that terminates it. So each call to strlen() is a full scan of the string to find out its length (count the chars til a null is found). You can easily speed up your code by calling strlen() once and saving the result:

  char *mon_string_rev(char *string)
  {
      assert(string != NULL)
      size_t input_len = strlen(string);
  
      char *out = malloc(input_len + 1);
      assert(out != NULL);
  
      // use 'input_len' as many times as it is needed.
      ....
  

  Also note that strlen() returns a size_t object (which is usually a typedef to unsigned long). It is best to declare the variable that receives the return value as size_t.

• Your function creates a copy of the input string with malloc(). This might be a requirement of the implementation, if so, disregard this item. Allocating dynamic memory is a costly operation, so high performance software should avoid it as much as possible. Plus, you place the burden of deallocating the buffer on the caller. Which is more likely to lead to memory leaks. A best option would be perhaps to receive a null terminated string and reverse it in-place. I once wrote an in-place string reversing function that used the XOR swap algorithm. If you would like to compare it against yours here it is:

  char * StringReverse(char * str) 
  {
      assert(str != NULL);
      if (!*str) 
      {
          /* Empty string, do nothing */
          return (str);
      }
  
      char * p1;
      char * p2;
      for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2) 
      {
          /* XOR trick to swap integer values: */
          *p1 ^= *p2;
          *p2 ^= *p1;
          *p1 ^= *p2;
      }
  
      return (str);
  }
  

  Unlike yours, this function will reverse the input string in-place, without malloc(). You can also easily write a wrapper function that mallocs a new string, passes it to StringReverse() and then returns it. The XOR swapping might or might not be faster, this will largely depend on the CPU architecture.

Answer 4

A few things that @Corbin has left out:

• In main()'s first condition, it would be better to return EXIT_FAILURE. You really only need exit() if you're in a different function that must terminate the program right away.

• There's no need to add whitespace between variable declarations and initializations. It just makes your code longer overall.

• When declaring i for a for loop, it should be put right in front of the loop. This will make it easier to keep track of this variable and to maintain closest possible scope.

Answer 5

That is an inappropriate use of an assertion. You should assert conditions that you know to be true, not conditions that you hope to be true. There is no provable reason why malloc() must return a true value, so you don't have a right to make that assertion. If you build your code with assertions disabled, then the runtime error checking will be gone, and it's bad software engineering practice to introduce those kinds of differences between development and production code.

What you should have written was:

/**
 * Produces a copy of the string with the contents reversed.
 * On failure to allocate memory, returns null and sets errno.
 */
char *my_string_rev(const char *s)
{
    size_t len = strlen(s);
    char *out = malloc(len + 1);
    if (!out) {
        return out;     // Return null.  errno should have been set by malloc.
    }
    …
}

Note the use of const in the function signature as well.

Better yet, make it the caller's responsibility to pass you a buffer large enough to contain the result. That would make the memory management policy explicit. As a side benefit, the caller would have the flexibility to pass you an array on the stack instead of the heap.

Answer 6

I notice you ask how you can know whether it's fast, not just whether it's fast.

One way is to look at the complexity. You have two loops inside each other, and you're operating a one-dimensional data structure. 2>1. Your solution is more complex than the task. So can you justify the extra loop? What impact does it have on performance?

Answer those questions, and soon you'll arrive at the kind of answer Corbin posted above.

Answer 7

Let me expand a bit on something @janos mentioned but didn't spell out in detail.

It's dangerous for a function to take a char * or const char * parameter without knowing how big the buffer is. Any function that takes one of these types must also take a parameter for how large the buffer is.

What's wrong with just using strlen? Well, it duplicates work (the caller already knows, or should know, how big the buffer is), but more importantly, what if the caller passes you a pointer to memory that doesn't contain a trailing '\0'? The strlen will probably cause a segmentation fault or similar.