Help with First Real C++ Program (Text Reverser) and Pointers

[ArkPhaze]

Although it may result in more readable code, I'm using GCC, and profiling shows that memcpy (not "memcall" I assume  ) is faster than direct assignment in this case. For larger strings, I'd rather not sacrifice performance in a handshake for slightly better readability.

GCC replaces an assignment operation by a call to any library function of its liking, but this doesn't guarantee that it is better necessarily, and nor would it be viable to prove or disprove, however, it would also be rather difficult with compiler optimization. memcpy is also designed to be the most efficient way of copy blocks of memory for C..

memcpy is also much safer in other cases that do not necessarily apply here, but for instance in structs where unaligned exceptions can occur with unaligned memory, memcpy will be much faster at the reduction in cost of the exception.

All in all, I see no reason for changing memcpy out with direct assignment here. There is no point.

If somebody doesn't like memcpy, then fine:

Code: [Select]

void reverse_str_recur(char *s, int lower_index, int upper_index)
{
   if (upper_index <= lower_index) return;
   *(s + lower_index) = s[upper_index];
   *(s + upper_index) = s[lower_index];
   reverse_str_recur(s, upper_index - 1, lower_index + 1);
}But I'll stick with memcpy.

The other option would be memmove:

Code: [Select]

void reverse_str_recur(char *s, int lower_index, int upper_index)
{
   if (upper_index <= lower_index) return;
   memmove(s + lower_index, s + upper_index, 1);
   memmove(s + upper_index, s + lower_index, 1);
   reverse_str_recur(s, upper_index - 1, lower_index + 1);
}
However I could've also reduced my original memcpy version with:

Code: [Select]

void reverse_str_recur(char *s, int lower_index, int upper_index)
{
   if (upper_index <= lower_index) return;
   memcpy(s + lower_index, s + upper_index, 1);
   memcpy(s + upper_index, s + lower_index, 1);
   reverse_str_recur(s, upper_index - 1, lower_index + 1);
}
*EDIT: New version

Code: [Select]

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

void reverse_str_recur(char *s, int lower_index, int upper_index)
{
   if (upper_index <= lower_index) return;
   memcpy(s + lower_index, s + upper_index, 1);
   memcpy(s + upper_index, s + lower_index, 1);
   reverse_str_recur(s, upper_index - 1, lower_index + 1);
}

#define REVERSE_STRING(s) (reverse_str_recur(s, 0, strlen(s) - 1))

int main()
{
   char str[] = "12345";
   printf("Original: %s\n", str);
   REVERSE_STRING(str);
   printf("Reversed: %s\n", str);
}

[bluechill]

Although it may result in more readable code, I'm using GCC, and profiling shows that memcpy (not "memcall" I assume  ) is faster than direct assignment in this case. For larger strings, I'd rather not sacrifice performance in a handshake for slightly better readability.

GCC replaces an assignment operation by a call to any library function of its liking, but this doesn't guarantee that it is better necessarily, and nor would it be viable to prove or disprove, however, it would also be rather difficult with compiler optimization. memcpy is also designed to be the most efficient way of copy blocks of memory for C..

memcpy is also much safer in other cases that do not necessarily apply here, but for instance in structs where unaligned exceptions can occur with unaligned memory, memcpy will be much faster at the reduction in cost of the exception.

All in all, I see no reason for changing memcpy out with direct assignment here. There is no point.

If somebody doesn't like memcpy, then fine:

Code: [Select]

void reverse_str_recur(char *s, int lower_index, int upper_index)
{
   if (upper_index <= lower_index) return;
   *(s + lower_index) = s[upper_index];
   *(s + upper_index) = s[lower_index];
   reverse_str_recur(s, upper_index - 1, lower_index + 1);
}But I'll stick with memcpy.

The other option would be memmove:

Code: [Select]

void reverse_str_recur(char *s, int lower_index, int upper_index)
{
   if (upper_index <= lower_index) return;
   memmove(s + lower_index, s + upper_index, 1);
   memmove(s + upper_index, s + lower_index, 1);
   reverse_str_recur(s, upper_index - 1, lower_index + 1);
}
However I could've also reduced my original memcpy version with:

Code: [Select]

void reverse_str_recur(char *s, int lower_index, int upper_index)
{
   if (upper_index <= lower_index) return;
   memcpy(s + lower_index, s + upper_index, 1);
   memcpy(s + upper_index, s + lower_index, 1);
   reverse_str_recur(s, upper_index - 1, lower_index + 1);
}
*EDIT: New version

Code: [Select]

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

void reverse_str_recur(char *s, int lower_index, int upper_index)
{
   if (upper_index <= lower_index) return;
   memcpy(s + lower_index, s + upper_index, 1);
   memcpy(s + upper_index, s + lower_index, 1);
   reverse_str_recur(s, upper_index - 1, lower_index + 1);
}

#define REVERSE_STRING(s) (reverse_str_recur(s, 0, strlen(s) - 1))

int main()
{
   char str[] = "12345";
   printf("Original: %s\n", str);
   REVERSE_STRING(str);
   printf("Reversed: %s\n", str);
}

Function overloading exists for a reason js.  You don't need to use preprocessor macros for that.  Yes it'll be slightly more inefficient but that's why there's inline which is more readable and gets the same result.

[ArkPhaze]

You just described the reason why I used a macro instead. I know I can do things at least 100 different ways for reversing a string here, I can't use them all at once though. I chose my specific implementation for my own reasons.

Btw - Overloading in the traditional sense is not supported in C; you can't just have two reverse_str() functions with different signatures and expect it to work based on the parameter types and count during the call. This isn't C++.

Compile this in C if you don't believe me:

Code: [Select]

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

void reverse_str(char *s, int lower_index, int upper_index)
{
   if (upper_index <= lower_index) return;
   memcpy(s + lower_index, s + upper_index, 1);
   memcpy(s + upper_index, s + lower_index, 1);
   reverse_str(s, upper_index - 1, lower_index + 1);
}

void reverse_str(char *s)
{
   reverse_str(s, 0, strlen(s) - 1);
}

int main()
{
   char str[] = "12345";
   printf("Original: %s\n", str);
   reverse_str(str);
   printf("Reversed: %s\n", str);
}

[chapp]

As above, if you're using C++, why not use the string alias? Otherwise, in C, you can do this with recursion pretty easy too. Here's a method I wrote a while back:

Code: [Select]

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

void reverse_str_recur(char *s, int lower_index, int upper_index)
{
   if (upper_index <= lower_index) return;
   char c[2] = {s[lower_index], s[upper_index]};
   memcpy(s + lower_index, c + 1, 1);
   memcpy(s + upper_index, c, 1);
   reverse_str_recur(s, upper_index - 1, lower_index + 1);
}
void reverse_str(char *s)
{
   reverse_str_recur(s, 0, strlen(s) - 1);
}

int main()
{
   char str[] = "12345";
   printf("Original: %s\n", str);
   reverse_str(str);
   printf("Reversed: %s\n", str);
   return 0;
}
Just remember with C style strings you have a null terminator to work with.

That is quite a memory and instruction demanding function for a simple task like switching the value of two bytes.


12 bytes for each call + 8 bytes saving return and frame ptr and 4 additional bytes for "c" if we consider alignment.
In fact gcc allocates 0x28 bytes on the stack for each call with this function so reversing a 1024 string would cost 40 times as much memory space and numerous function calls, for something that could have cost 1024+9 bytes (2x4 for start and end pointer + 1 byte as temporary char storage).

edit: of course it would be only ~20 times more memory as the function takes n/2+1 calls to be reversed

[ArkPhaze]

You're essentially calling out this function as bad because of the extra variables used (fixed in my revisions if you read a few posts forward), and numerous function calls (explain how to avoid that with recursion? :S). As I mentioned above memcpy() was designed for efficiency, so to judge the function based on how many bytes it allocates on the stack is very odd. If you want to delve into micro-optimization then sure, but in most cases that is senseless.

Did you forget to read my edited version (or the rest of the posts within this thread)?    I also posted a version with memmove() too, but the idea here was the simplicity of a recursive method. Nobody chooses recursion for absolute optimization. Obviously you don't use recursion if you take into consideration the things you've mentioned and an iterative approach would be better, but I never claimed that a recursive approach would be the best solution, I simply posted a method demonstrating it. I wouldn't use this method on larger strings, but recursion was invented to replace complex iterative variations which achieve the same thing, and memcpy() was designed to be the most efficient way of copy blocks of memory in C.

You also don't *require* temp char storage, because chars can be treated as 8 bit integers in this case, enabling you to use bitwise operations. If you're idea of optimization is less memory usage then here is an example depicting the lack of a temp char to swap the values.

Example:

Code: [Select]

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

void revstr(char *s)
{
   size_t len = strlen(s);
   size_t limit = (size_t)(len / 2);
   for (size_t i = 0; i < limit; ++i)
   {
      *(s + i) ^= *(s + len - i - 1);
      *(s + len - i - 1) ^= *(s + i);
      *(s + i) ^= *(s + len - i - 1);
   }
}

int main()
{
   char mystr[] = "testing";
   revstr(mystr);
   printf("%s\n", mystr);
   getchar();
   return 0;
}
This uses bitwise operations to swap the values from the first char to the last char (before the null terminator).

Optimization is not entirely about less memory however. Some of the fastest algorithms for sorting and generating primes use up lots of memory, but are optimized in their own context, based on the methodology being used.