# Is this a fast implementation of reversing a string?

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;

}

-
You really have to put the code through a profiler to know for sure if one solution is fast or slow. It's like science: you might have a guess how the program behaves, even an educated guess, but you can't be sure until you measure. For example, one point I've noticed in the past is that some apps perform noticeably faster if they use buffers which are mod4 or mod8 in size. It's totally bizarre but a measurable phenomena. I believe the reason has to do with how arrays are moved into registers on the CPU. Here's some suggestions on profilers –  Jeff-Inventor ChromeOS Aug 5 '14 at 8:22
To compare the real time your algorithm/program needs in execution, call it with time (on linux machines), like this: time ./myprogram "my irreversed string." time ./myotherpr "my irreversed string." Employ a (e.g. bash) loop to call the program multiple times and compare the output. –  Felix Aug 5 '14 at 13:00
@Felix: Unless you pass a very long string on the command line (many thousands of characters), the run time of the process is dominated by the startup overhead. The way to measure would be to put a 10k or 100k iterations loop into your program, calling the same function. –  Peter Cordes Aug 5 '14 at 14:35

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???").

-
"A string can be reversed quite trivially in linear time. Your algorithm is quadratic." I dont get that either, if you care about how fast it is, a linear approach would definetly be faster. –  everlof Aug 4 '14 at 6:36
@true I don't understand what you mean? Do you want a proof that your algorithm is quadratic? Or do you want proof that a string can be reversed in linear time? –  Corbin Aug 4 '14 at 15:06

### 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.
-
"Also, this gives me a compiler error:" That's because you're compiling it as C++. It's customary in C to not cast the return of malloc. –  Corbin Aug 4 '14 at 23:57
Thanks @Corbin, I scratched that out for now. Can you enlighten me why it's better to omit the cast, other than it's less typing? –  janos Aug 5 '14 at 6:37
On a phone, so you'll have to excuse the short answer. The short version of it is that a forgotten header can still result in successful compilation with a cast, whereas it will properly fail without it. stackoverflow.com/a/605858/567864 –  Corbin Aug 5 '14 at 12:48
Isn't this the same as unrolling the loop from both ends. I suspect that the optimizer will do a better job of loop unrolling than this cleverness. –  Snowbody Aug 6 '14 at 14:36

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.

-
This answer would be improved by mentioning a few more of its benefits: Single call to strlen (and why that matters); avoidance of malloc. Also, you could show how a malloc based version can invoke this version. Also note that even with the XOR replaced by simple use of a temporary, this basic structure is still good. –  Keith Aug 4 '14 at 2:44
You are absolutely right, @Keith. I'll give it a revamp. –  glampert Aug 4 '14 at 5:07
XOR swapping probably isn't faster than using a temporary variable, and it also has a tricky failure mode (which you correctly avoided, but still…). –  200_success Aug 4 '14 at 7:06
Has anyone checked that the XOR-trick really has a benefit (performance wise) other than making the code harder to understand? I think that at least with an optimizing compiler, this should make no difference in runtime (IMHO this trick is only ever beneficial for saving one pointer in a doubly-linked list). –  Axel Aug 5 '14 at 7:07
@200_success: In fact, I'd go further and say that, on any reasonable modern compiler + CPU, the XOR-swap is going to be slower than simply using a temp variable, since it needs more memory accesses. (The only possible exception might be if the compiler recognizes the XOR-swap and optimizes it into something more efficient, like, say, a simple swap via a temp variable.) –  Ilmari Karonen Aug 5 '14 at 14:40

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.

-

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.

-
"errno should have been set by malloc"? Looked over the C spec, did not find this. Maybe some compilers do this? –  chux Aug 4 '14 at 22:12
@chux The behavior of malloc is governed by the UNIX standard, not the C spec. From the man page, "The UNIX 98 standard requires malloc(), [...] to set errno to ENOMEM upon failure." –  Aaron Dufour Aug 5 '14 at 15:31
@AaronDufour, what if you're using malloc() on Windows? Nothing in the OP's question is Unix-specific. –  godlygeek Aug 5 '14 at 16:52
@godlygeek Great point! The MSDN docs are the place to look for this - and indeed, they specify "malloc sets errno to ENOMEM if a memory allocation fails or if the amount of memory requested exceeds _HEAP_MAXREQ." Unfortunately, I don't know of a single place where a cross-platform C stdlib spec is defined (I suspect there isn't one). Anything non-trivial in C is just not going to be cross-platform without doing quite a bit of work. –  Aaron Dufour Aug 5 '14 at 16:57

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.

-

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.

-