Menu
▾
▴
RE: [Dev-C++] Shallow copy
|
From: <Mat...@Ve...> - 2005-04-21 18:53:22
|
Per,
You spent a _lot_ longer on that than I ever would have. :-) I was just
giving a quick general answer since I'm at work and in kind of a hurry to
finish up a big project. Yours was a really cool explanation. Thanks for
writing it. It taught me a lot about how memcpy really works.
I suppose that-- this observation is for the truly pedantic, you could seek
out its "official" implementations in the GLIBC source code. Don't you just
love the GPL? :-)
Regards,
Matt
-----Original Message-----
From: Per Westermark [mailto:pw...@ia...]
Sent: Thursday, April 21, 2005 11:01 AM
To: Mat...@Ve...
Cc: xtr...@vi...; al...@ya...;
dev...@li...
Subject: RE: [Dev-C++] Shallow copy
For small objects, an inlined copy function might be better, but for
larger blocks, the memcpy() function is optimized to switch over to 32-bit
(or larger) moves for maximum performance, i.e. it definitely wins over a
char* copy.
By the way, a couple of problems with the code:
No (char*)i - you wan't to declare i as a variable, not typecast it to
char*.
Second, avoid extra variables. Your code is using 4 variables. Instead of
creating a new variable i and do begin+i you should increment begin.
Besides using a variable less, it also optimizes the memory reference for
some processors.
A low-end memcpy() looks something like:
void* copy(void *dst,void *src,unsigned size) {
char* orig_dst = dst;
char* end = (char*)src + size;
while ((char*)src < end) {
*((char*)dst)++ = *((char*)src)++;
}
return orig_dst;
}
A normal memcpy() will do some optional single byte copies at start to get
word-aligned, and then do several unrolled word-copies (as large word as
possible, i.e. normally 32 or 64 bit) and then end with some optional
single-byte copies again.
If data is known to always be well-aligned and of a reasonable size, a
better code would be (pseudo-code):
void* copy(void *dst,void *src,unsigned size) {
// Observe: Code assumes that src and dst are aligned to sizeof(long)
// If they are not, one or more single-byte copy are needed...
void* orig_dst = dst;
unsigned r = size % sizeof(unsigned long);
unsigned count = size / sizeof(unsigned long);
if (size >= 4) {
// Unroll loop 4 times.
size >>= 2;
r += 4*sizeof(unsigned long);
} else {
// Too small block to unroll.
r += 4*size;
size = 0;
}
for (;size; size--) {
*((unsigned long*)dst)++ = *((unsigned long*)src)++;
*((unsigned long*)dst)++ = *((unsigned long*)src)++;
*((unsigned long*)dst)++ = *((unsigned long*)src)++;
*((unsigned long*)dst)++ = *((unsigned long*)src)++;
}
// r and this code not needed if size is a multiple of sizeof(long)
for (;r; r--) {
*((char*)dst)++ = *((char*)src)++;
}
return *orig_dst;
}
In reality, this kind of code is written in assembler, to allow further
optimizations by for example using calculated jumps into the unrolling
code. Also, some processors have special instructions for memory transfer
operations.
/Per W
On Thu, 21 Apr 2005 Mat...@Ve... wrote:
> Alright. Once you have overloaded an operator, you are stuck with that
> operator. However, overloaded operators apply on a class by class basis.
The
> HugeStuff type will not use the operator= that you defined for your class.
> Can you think of a way to refactor your operator= to operate in terms of
the
> default operator= define for type HugeStuff?
>
> Also, memcpy should be very fast. If it's not, try rolling your own. It
> might work something like the below code. Also make sure you enable -O3
> -fexpensive-optimizations when you build the code. You might also need
-mcpu
> and -mtune.
>
> Some routines benefit heavily from optimization. Copy-heavy routines seem
to
> need help with this. When I wrote a crypto algorithm a while ago, it
doubled
> the speed to optimize it fully.
>
> void copy(void* begin, void* end, void* dest)
> {
> for((char*) i=0; i<(char*)end; i++)
> {
> *(char*)dest=(char*)(begin+i);
> }
> }
>
> HTH!
> Matt
> -----Original Message-----
> From: dev...@li...
> [mailto:dev...@li...]On Behalf Of Francesco
> Sent: Thursday, April 21, 2005 3:02 AM
> To: Alfred P. Reaud
> Cc: Dev C++
> Subject: Re: [Dev-C++] Shallow copy
>
>
> Thanks for answering Alfred,
> I'm already using the STL but since I'm still in a learning stage I was
> trying to understand the "inner workings". Suppose I'm building ( just for
> my own pleasure :-) ) a simple competitor to the vector template. Or to
make
> it even more banal, suppose I have the following code:
>
>
> class MyData
> {
> typeHugeStuff * mHugeStuffPtr;
> // ....
> public:
> // ....
> MyData const & operator=( MyData const & inMyData ); // the
> definition of this copies also the stuff pointed to by mHugeStuffPtr
> // .....
> };
>
>
> template< typename T >
> void MySwap( T * inDataPtr1, T * inDataPtr2 )
> {
> #ifdef BAD_SWAP
> // the following will swap in memory the two objects but will also
> deallocate/allocate/copy hugeStuff
> T tempData;
>
>
> tempData = *inDataPtr1;
> *inDataPtr1 = *inDataPtr2;
> *inDataPtr2 = tempData;
> #else
> // the following will just swap bitwise the members of the two
> objects without erasing/duplicating/whatever hugeStuff
> // but this bitwise copy seems to be slower than using the
operator=
> (when it's not overloaded)
> // so I was wondering if it is possible to access the UNoverloaded
> operator= in objects that have overloaded it....
> char * aPtr;
>
>
> aPtr = (char*) malloc ( sizeof( T ) );
> memcpy( aPtr, inDataPtr1, sizeof( T ) );
> memcpy( inDataPtr1, inDataPtr2, sizeof( T ) );
> memcpy( inDataPtr2, aPtr, sizeof( T ) );
> free( aPtr );
> #endif
> }
>
>
> void main( void )
> {
> MyData * aDataPtr;
>
> aDataPtr = new MyData[ 100 ];
> FillUp( aDataPtr, 100 ); // filling up with data
> MySwap< MyData >( aDataPtr + 20, aDataPtr + 40 ); // just
> because.... :-)
> }
>
>
> Thanks in advance for any insight,
> Francesco
>
>
> On Apr 20, 2005, at 7:46 PM, Alfred P. Reaud wrote:
>
>
> Hi Francesco,
>
> Your array of class objects would be better served if it where a list or
> vector of class objects instead of an array. Then you can use the
iterator
> features, including list and vector specific swap and sort member
functions.
> I f you must use an array of class objects, then there's always the
> <algorithm> standard template library header. Algorithm has a rich set of
> functions that include swap, sort, and other useful data manipulation
> algorithms such as unique, etc. These functions are usually optimized,
and
> work in most instances significantly better than manually coded swap or
sort
> functions.
>
> I'm not actually sure what you mean by "deep copy", however, I'm assuming
> that you mean actual data copying. You shouldn't be copying data to swap
> it! You should be swapping pointers to the data. Maybe the issue is in
> using a class class_objects[array_size]; declaration vs. a class
> *class_objects; declaration, because the overloaded operator= may operate
in
> a different fashion between a pointer and an array element (i.e.
> class_objects[7], is a pointer, but in machine code is actually a set of
> pointer arithmetic operations). The class operator= should already be
> configured to correctly do something like:
>
> class *obj_a, *obj_b, *temp;
> obj_a = new class; ...;
> temp = obj_a; obj_a = obj_b; obj_b = temp;
> delete(temp); ...
>
> so that should work correctly, ***** however *****
>
>
>
> list<class> obj_list;
> list<class>::iterator obj_iter;
> obj_list.push_back(obj_a); ...
> obj_iter = obj_list.begin();
> obj_list.sort() or obj_list.sort( compare_function );
> ...
>
> is easier, more elegant, and uses the optimized features of C++!
Hopefully
> the above helps!
>
>
> Francesco <xtr...@vi...> wrote:
> Hi everybody,
> I'm a total beginner and I have the following problem:
> I have an array of objects instantiated from a class that has member
> pointers to dynamically allocated data. This class has also the usual
> overloaded operator=. I have to sort this array and I need to do some
> swapping. But swapping by "deep copy" seems useless to me in this case,
> thus is it possible somehow to override the overloaded operator= and
> use just for the swapping the normal operator =? I could use memcpy for
> a bitwise copy, but it seems to be significantly slower, especially
> for small objects.
> Thanks in advance,
> Francesco
> <snip>
>
>
>
>
> Alfred P. Reaud
> <image.tiff>
> ___________________________________________________________________
> The information contained in this message and any attachment may be
> proprietary, confidential, and privileged or subject to the work
> product doctrine and thus protected from disclosure. If the reader
> of this message is not the intended recipient, or an employee or
> agent responsible for delivering this message to the intended
> recipient, you are hereby notified that any dissemination,
> distribution or copying of this communication is strictly prohibited.
> If you have received this communication in error, please notify me
> immediately by replying to this message and deleting it and all
> copies and backups thereof. Thank you.
>
>
>
> -------------------------------------------------------
> SF email is sponsored by - The IT Product Guide
> Read honest & candid reviews on hundreds of IT Products from real users.
> Discover which products truly live up to the hype. Start reading now.
> http://ads.osdn.com/?ad_id=6595&alloc_id=14396&op=click
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www23.brinkster.com/noicys/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>
|
