Page 1 of 2
Something I bet you didnt know you could do with pointers #2
Posted: Sat Dec 06, 2008 5:41 pm
by sparda
Well, I have a little free time from my studies and I see avansc at work already. So I decided to add my two cents about pointer tricks.
To all of you C++ programmers (I'm one too), you can use pseudo-templates in C, using generic pointers and the memcpy function. I think the correct term is generic functions in C.
For instance, say you want to swap two values of arbitrary data-type. You would do something like this in C++:
Code: Select all
#include <iostream>
#include <cstdlib>
template<typename T>
void swap(T &a, T &b);
int main(void)
{
int a = 10, b = 20;
swap(a, b);
std::cout << "a: " << a << " and b: " << b << std::endl;
return EXIT_SUCCESS;
}
template<class T>
void swap(T &a, T &b)
{
T tmp = a;
a = b;
b = tmp;
}
You can do the same thing in C, and more efficiently by:
Code: Select all
#include <stdio.h>
#include <stdlib.h>
void swap(void *a, void *b, int n);
int main(void)
{
int a=0, b=10;
swap(&a, &b, sizeof(int));
printf("a: %d, b: %d", a, b);
return EXIT_SUCCESS;
}
void swap(void *a, void *b, int n)
{
void *buffer = malloc(n);
memcpy(buffer, a, n);
memcpy(a, b, n);
memcpy(b, buffer, n);
free(buffer);
}
The "n" would be used to wrap the bytes to be copied. Actually, thats the reason you can't dereference void*s, because compilers "don't" know how many bytes to "bound" in the dereferencing process.
Just remember that you can not dereference void*'s and you'll be alright
This works better than templates in that, it works in analogue to an inline functions, internally at the asm level. With C++ templates, if you have a huge amount of different types (including user-defined types i.e. classes) using template functions, the implementations would expands per-type. Whereas, with generic C functions, you only have this one representation for the implementation of swap.
So those are my two cents
Re: Something I bet you didnt know you could do with pointers #2
Posted: Sat Dec 06, 2008 5:44 pm
by avansc
dont use int n
use size_t n
Re: Something I bet you didnt know you could do with pointers #2
Posted: Sat Dec 06, 2008 5:55 pm
by sparda
avansc: truth be told, it doesn't really matter.
Reason: A precondition to using the generic swap function would be that sizeof always be used. To my knowledge, sizeof never returns a negative number. The only thing I can think of is if there is a ridiculously large user-defined type, that makes sizeof(user-defined type) return a number greater than 2147483647, and it causes a bitwise wrap-around bug. Please name a sighed data-type that when passed to sizeof returns 2147483647
Re: Something I bet you didnt know you could do with pointers #2
Posted: Sat Dec 06, 2008 6:02 pm
by avansc
sparda wrote:avansc: truth be told, it doesn't really matter.
Reason: A precondition to using the generic swap function would be that sizeof always be used. To my knowledge, sizeof never returns a negative number. The only thing I can think of is if there is a ridiculously large user-defined type, that makes sizeof(user-defined type) return a number greater than 2147483647, and it causes a bitwise wrap-around bug. Please name a sighed data-type that when passed to sizeof returns 2147483647
its not about that.
but with size_t you can add whatever you want to there.
with int n, you can only an int, unless you do a cast.
its just a better programming practice to use size_t
more "professional"
Re: Something I bet you didnt know you could do with pointers #2
Posted: Sat Dec 06, 2008 6:05 pm
by avansc
i mean im not trying to say anything bad. but malloc(n) is such a bad programming practice.
you would lose a job programming like that.
(type*)malloc(n*sizeof(type));
Re: Something I bet you didnt know you could do with pointers #2
Posted: Sat Dec 06, 2008 6:20 pm
by Amarant
avansc wrote:i mean im not trying to say anything bad. but malloc(n) is such a bad programming practice.
you would lose a job programming like that.
(type*)malloc(n*sizeof(type));
I think you should reread the example, because inside the swap function there's no information about the type.
I do agree the n parameter should have the size_t type since that is what sizeof() returns.
Btw, would you consider using variable length arrays instead of malloc and free.
I believe variable length arrays just use memory on the stack so that would be a lot faster I guess.
Re: Something I bet you didnt know you could do with pointers #2
Posted: Sat Dec 06, 2008 6:32 pm
by avansc
i just added to show what malloc is suppose to look like.
and depending on the situatiuon arrays might be faster. but i use linked list that use malloc and free. and even with 10000 items in the list i get little to no lag. so yeah im not sure about that one.
Re: Something I bet you didnt know you could do with pointers #2
Posted: Sat Dec 06, 2008 6:35 pm
by avansc
Code: Select all
void swap(void *a, void *b, int n)
{
void *buffer = malloc(n);
memcpy(buffer, a, n);
memcpy(a, b, n);
memcpy(b, buffer, n);
free(buffer);
}
also, that code might work fine on his mahine. but that code is not portable. not meaning that it wont work on another platform.
anytime you do malloc(n) you are running a risk.
Re: Something I bet you didnt know you could do with pointers #2
Posted: Sat Dec 06, 2008 6:36 pm
by sparda
I see what you're saying, but I don't get what you're trying to do here. I'm not applying for a job.
Re: Something I bet you didnt know you could do with pointers #2
Posted: Sat Dec 06, 2008 6:39 pm
by Amarant
I don't see what you're saying. What's not portable about it?
Re: Something I bet you didnt know you could do with pointers #2
Posted: Sat Dec 06, 2008 6:41 pm
by sparda
Also, can you explain how using malloc(n) is not portable in my example? I can only see how the casting of the return type might have something to do with it. Remember, if I go swap(&a, &b, sizeof(a)), and then do malloc(n), it is the same as if I did, malloc(sizeof(int)).
Re: Something I bet you didnt know you could do with pointers #2
Posted: Sat Dec 06, 2008 6:43 pm
by avansc
also assuming you wanted to swap to variables they, they would likely be the same size.
i would use an XOR swap.
Re: Something I bet you didnt know you could do with pointers #2
Posted: Sat Dec 06, 2008 6:46 pm
by avansc
malloc(n) does not return the same value on different platforms.
maybe for that specific example you'll be fine. but most likely you are gonna run into trouble with malloc(n) somewhere.
Re: Something I bet you didnt know you could do with pointers #2
Posted: Sat Dec 06, 2008 6:46 pm
by sparda
?
Yeah avansc, I know. I posted that same XOR example in these forums about 2 months ago. In this case though, I was trying to show some pointer stuff, i.e. the generic functions in C
Re: Something I bet you didnt know you could do with pointers #2
Posted: Sun Dec 07, 2008 7:37 pm
by bugmenot
If you are using C++ then always prefer using the standard library's swap function unless you can prove that it is slower then any implementation that you can provide. Generally, it is at least going to be as fast if not faster then most generic implementations.
Code: Select all
#include <algorithm>
int main()
{
int blah = 0;
int foo = 10;
std::swap( blah, foo );
}
This code:
Code: Select all
void swap(void *a, void *b, int n)
{
void *buffer = malloc(n);
memcpy(buffer, a, n);
memcpy(a, b, n);
memcpy(b, buffer, n);
free(buffer);
}
Is inherently slower then the template version because of the malloc. Allocating off the heap is always slower then stack. If I was stuck with C, then I wold consider using a macro.
Below is the sample code and the results in running the release build (using ctime is inaccurate to a degree but the difference is so large it is adequate to demonstrate my point:
Code: Select all
#include <algorithm>
#include <iostream>
#include <ctime>
#define C_SWAP( a, b, t ) do{ t temp = (a); (a) = (b); (b) = temp; } while(0);
void CPointerSwap( void *a, void *b, int n)
{
void *buffer = malloc(n);
memcpy(buffer, a, n);
memcpy(a, b, n);
memcpy(b, buffer, n);
free(buffer);
}
template<class T>
void CppSelfSwap(T &a, T &b)
{
T tmp = a;
a = b;
b = tmp;
}
int main()
{
int blah = 0;
int foo = 10;
clock_t startTime;
clock_t finishTime;
static const int ITERATIONS = 1000000000;
startTime = clock();
for( int i = 0; i < ITERATIONS; ++i )
{
std::swap( blah, foo );
}
finishTime = clock();
std::cout << "C++ algorithm swap " << finishTime - startTime << std::endl;
size_t n = sizeof(int);
startTime = clock();
for( int i = 0; i < ITERATIONS; ++i )
{
CPointerSwap( &blah, &foo, n );
}
finishTime = clock();
std::cout << "C pointer swap " << finishTime - startTime << std::endl;
startTime = clock();
for( int i = 0; i < ITERATIONS; ++i )
{
C_SWAP( blah, foo, int );
}
finishTime = clock();
std::cout << "C macro swap " << finishTime - startTime << std::endl;
startTime = clock();
for( int i = 0; i < ITERATIONS; ++i )
{
blah ^= foo;
foo ^= blah;
blah ^= foo;
}
finishTime = clock();
std::cout << "XOR swap " << finishTime - startTime << std::endl;
startTime = clock();
for( int i = 0; i < ITERATIONS; ++i )
{
CppSelfSwap( blah, foo );
}
finishTime = clock();
std::cout << "C++ self swap function " << finishTime - startTime << std::endl;
}
Prints:
Code: Select all
[Session started at 2008-12-08 01:47:02 +0000.]
C++ algorithm swap 113
C pointer swap 12486
C macro swap 113
XOR swap 93
C++ self swap function 119
The Debugger has exited with status 0.
As a side note, XOR only inherently work with integers. You have to add some extra code to make it work with non base types which will can it slower