Sign in to follow this  
Christoph

copy arrays

Recommended Posts

Christoph    122
Hi, can you tell me what is the fastest method to copy a part of an array to another array? For example, I have two pointers: int *index1; int *index2; index1 = new int[10]; index2 = new int[10]; Having filled these arrays, I want to copy, let's say, element 5 to 8 from index1 to index2. How do I best realize this? thx

Share this post


Link to post
Share on other sites
ApochPiQ    23063
int i;
for(i = 5; i <= 8; ++i)
index2[i] = index1[i];



Premature optimization is the root of all evil. Unless you're absolutely 100% sure with profiler evidence that your array copy is too slow (and maybe not even then), you are not sure enough to mess around with this kind of optimization. On a 32-bit system, the fastest you'll get in general is moving blocks of data in chunks of 32 bits, which, if your data is in ints, you're already doing.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Try:

memcpy(index2, index1 + (sizeof(int) * 5), sizeof(int) * (8 - 5));

It should be very fast and efficient that way. I don't know of a faster method but maybe there is one, let's see what other people say...

Be aware, that memcpy does not check for memory overflow on the target memory (index2 in this case). So you need to make sure that index2 offers enough space for the operation!

Share this post


Link to post
Share on other sites
Dave Hunt    4872
Quote:
Original post by Kuladus

#include <cstring>
std::memcpy(&(index2+5),&(index1+5),3*sizeof(int));


Almost. You don't want to take the address of (index2+5). (index2+5) is already an address. Same with (index1+5).

Share this post


Link to post
Share on other sites
me22    212
Well, you're using C++, so you should use the std::copy function:

#include <algorithm>

std::copy( index1+5, index1+8, index2 ); // copies index1[5],index1[6],index1[7]




A good implementation will implement that, for PoD types, as a memcpy, but will do the right thing if you change index1 and index2 to arrays of non-PoD types.

Note of course that you should also be using std::vector and not deaing with the memory yourself, or at the very least sticking the memory into a scoped_array<int> or shared_array<int> for RAII and exception-safety.

Fruny - added std prefix.

[Edited by - Fruny on June 30, 2005 10:34:37 AM]

Share this post


Link to post
Share on other sites
Fruny    1658
me22 got it right. There is little reason to use memcpy() anymore, std::copy() is infinitely superior.

Share this post


Link to post
Share on other sites
Dave Hunt    4872
Quote:
Original post by Fruny
me22 got it right. There is little reason to use memcpy() anymore, std::copy() is infinitely superior.



Not quite infinite. It's 9 characters to type instead of 6. [smile]

Share this post


Link to post
Share on other sites
MaulingMonkey    1730
Quote:
Original post by Dave Hunt
Quote:
Original post by Fruny
me22 got it right. There is little reason to use memcpy() anymore, std::copy() is infinitely superior.


Not quite infinite. It's 9 characters to type instead of 6. [smile]


I disagree. If you're using C++, you should be using <cstdlib>, and thus std::memcpy would be used instead of simply memcpy - which adds up to 11 characters, not 6.

"stdlib.h allows simply memcpy" you say?
"using namespace std; allows simply copy" I retort (making std::copy simply "copy", 4 characters).

They're the same in terms of namespace polution, I'd argue.

Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by me22
A good implementation will implement that, for PoD types, as a memcpy, but will do the right thing if you change index1 and index2 to arrays of non-PoD types.


In reality its more likely to dispatch at compile-time to use memmove, not memcpy, because the input and output ranges are permitted to overlap. It is still much better than explicit loop code.

To be more specific, a typical implementation of std::copy will dispatch (type and/or tag) at compile-time from the following:


  1. memmove whenever possible, normally the case when the iterator category is random access iterators and the value type is a POD-type

  2. Failing that, if random access iterators are passed and the value type is NON POD-type, then the loop count will be known (and therefore a candidate for compiler optimizations such as unrolling).

  3. Failing all of the above then the most generic copy is used



Note this happens all at compile-time so this selection doesn't exist at run-time and its typically all inlined away when optimizations are on.

Yes i suggest you use the C++ standard library algorithms because it handles cases you would never have thought of, besides you shouldn't use C memory rountines directly on NON POD-types.

[Edited by - snk_kid on June 30, 2005 10:27:09 AM]

Share this post


Link to post
Share on other sites
s_p_oneil    443
Quote:
Original post by ApochPiQ
Premature optimization is the root of all evil.


1. I strongly disagree. Sloppy/messy/unmaintainable code is much worse, whether it's optimized or not. Only premature operations that make the code sloppy, messy, or difficult to maintain are a problem (i.e. unrolling loops, converting code to assembler). If it makes the code cleaner, it's a good thing.

2. Since when is using memcpy an optimization? It's been the de-facto standard way to copy contiguous blocks of memory in C since the language was invented. (Although I agree that it seems like overkill for copying 3 elements.)

3. Unless Christoph knows STL and the new C++ standard extensions, he should stick with the standard C version of memcpy until he's ready to jump into STL.

Share this post


Link to post
Share on other sites
Dave Hunt    4872
Quote:
Original post by s_p_oneil
Quote:
Original post by ApochPiQ
Premature optimization is the root of all evil.


1. I strongly disagree.


Perhaps (to get closer to the oft-misquoted original) "Premature optimization is the root of all kinds of evil" would be a more accurate statement.

Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by s_p_oneil
2. Since when is using memcpy an optimization? It's been the de-facto standard way to copy contiguous blocks of memory in C since the language was invented. (Although I agree that it seems like overkill for copying 3 elements.)


memcpy is typically more efficent than a hand-written loop, but he is using C++ so in general he should be use C++ algorithms therefore std::copy.

Quote:
Original post by s_p_oneil
3. Unless Christoph knows STL and the new C++ standard extensions, he should stick with the standard C version of memcpy until he's ready to jump into STL.


Okay let him use memcpy on a array of NON-POD types and see what will happen. The best way to learn C++ is to learn it the wright way from the beginning which means learning to use the C++ standard library with C++ which has little to do with efficiency but they are written to be as a efficient + safe as possiable.

Share this post


Link to post
Share on other sites
ApochPiQ    23063
Quote:
Original post by s_p_oneil
1. I strongly disagree. Sloppy/messy/unmaintainable code is much worse, whether it's optimized or not. Only premature operations that make the code sloppy, messy, or difficult to maintain are a problem (i.e. unrolling loops, converting code to assembler). If it makes the code cleaner, it's a good thing.


Generally speaking, when a programmer knows enough about when to optimize and clean up code, they don't need to ask for the fastest way to copy memory. In my experience, it is quite rare for optimizations to make code cleaner. Distinguish optimization and refactoring.

IMHO, a memcpy() call with explicit address taking and sizeof() juggling is messier than a simple loop. Short is not equivalent to clean.


Quote:
Original post by s_p_oneil
2. Since when is using memcpy an optimization? It's been the de-facto standard way to copy contiguous blocks of memory in C since the language was invented. (Although I agree that it seems like overkill for copying 3 elements.)


I didn't say anything about memcpy being an optimization. My point was to the original poster: worrying about how long it takes to copy some array elements is not productive in the majority of cases. It is very rare for a data copy to be a serious performance bottleneck, and if it is, there is a very strong chance that the best optimization is algorithmic and high-level, not a "faster version of memcpy."

In the case of copying ints, memcpy() won't be any faster than a simple loop, because they both move memory in DWORDs (at least if the memcpy() implementation is the way it was several years ago when I last looked at it). On a 32-bit platform, in general, there isn't a faster way to copy memory blocks than in 32-bit chunks. In the case of complex data (structures, classes, strings, etc.) then certainly memcpy() will tend to be superior. In any case my point wasn't that an explicit loop is faster necessarily, but that the speed is almost certainly irrelevant and the simpler, more readable solution is preferable.

Quote:
Original post by s_p_oneil
3. Unless Christoph knows STL and the new C++ standard extensions, he should stick with the standard C version of memcpy until he's ready to jump into STL.


I fully agree with this. Do the simplest thing that could possibly work.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Quote:
Original post by MaulingMonkey
They're the same in terms of namespace polution, I'd argue.
Not IMO. memcpy is something cryptic you very likely wouldn't use as a function/method/whatever name yourself, whereas copy is clear english and nice and short, so it might very well be used.

Share this post


Link to post
Share on other sites
MaulingMonkey    1730
Quote:
Original post by Anonymous Poster
Quote:
Original post by MaulingMonkey
They're the same in terms of namespace polution, I'd argue.
Not IMO. memcpy is something cryptic you very likely wouldn't use as a function/method/whatever name yourself, whereas copy is clear english and nice and short, so it might very well be used.


When you include stdlib.h, or use the entire std namespace, you get much more than just memcpy, hence the problem.

I've run into clashes with (std::)system() vs my own system class before, the fact is that there's plenty of names you might want to use in stdlib.h

It dosn't matter if it's 20 or 100, fact is, the namespace will be poluted, period.

My solution has generally been to never write anything in the global namespace. The implementation of main usually follows this layout in my projects:
namespace project_name {
int main ( int argc , char * argv[] );
}

int main ( int argc , char * argv[] ) {
return project_name::main( argc , argv );
}


EDIT: DD edited out his post after the fact it'd seem, which I realized as I started to merge two consecutive posts by myself into one... I feel like keeping my comment on the matter though:

Quote:
Original post by DigitalDelusion
one could even be so bold as to advice making the code truly selfdocumenting and mind numbingly obvious by doing:

template <typename SrcItr, typename DstItr>
inline DstItr copy_n(SrcItr first, DstItr out, typename std::iterator_traits<SrcItr>::difference_type count)
{
return std::copy( first, first + count, out);
}


Bad idea IMO, argument order is not intuitive to me, plus it goes against existing practice as set by SGI (linky) where count is the second, not the third, argument.

Share this post


Link to post
Share on other sites
Quote:
Original post by MaulingMonkey
EDIT: DD edited out his post after the fact it'd seem, which I realized as I started to merge two consecutive posts by myself into one... I feel like keeping my comment on the matter though:

Quote:
Original post by DigitalDelusion
one could even be so bold as to advice making the code truly selfdocumenting and mind numbingly obvious by doing:

template <typename SrcItr, typename DstItr>
inline DstItr copy_n(SrcItr first, DstItr out, typename std::iterator_traits<SrcItr>::difference_type count)
{
return std::copy( first, first + count, out);
}


Bad idea IMO, argument order is not intuitive to me, plus it goes against existing practice as set by SGI (linky) where count is the second, not the third, argument.


I edited it out because I realized it was a bad idea since it was modled after the first response (using memcpy) instead of after the initial request (copying element 5 to 8) so I answered the wrong question.

I also got to grips with that the addition isn't sure to work effectivly and yeah it was a total brainfart on my part.

Share this post


Link to post
Share on other sites
Fruny    1658
Quote:
Original post by DigitalDelusion
I also got to grips with that the addition isn't sure to work effectivly and yeah it was a total brainfart on my part.


Either it is effective, or it isn't provided. That's why you got std::advance.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
Quote:
Original post by DigitalDelusion
I also got to grips with that the addition isn't sure to work effectivly and yeah it was a total brainfart on my part.


Either it is effective, or it isn't provided. That's why you got std::advance.


That was my realization to and that's why I ripped the code a good implementation would have to hop through a lot of hoops to competative and/or usefull in the general case.

Share this post


Link to post
Share on other sites
snk_kid    1312
Using std::advance in this case wouldn't be a great idea, better to use the iterator category and do tag dispatching at compile time.

Share this post


Link to post
Share on other sites
Fruny    1658
Quote:
Original post by snk_kid
Using std::advance in this case wouldn't be a great idea, better to use the iterator category and do tag dispatching at compile time.


std::advance does do tag dispatching.

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid
Using std::advance in this case wouldn't be a great idea, better to use the iterator category and do tag dispatching at compile time.


That would be the talked about hoops needed to hop through to make it good yes.
Half the thread is now officly talk about a terrible brainfart that I did rewoke for just the reasons that people have stated, and the weahter is junk to :p

Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by Fruny
Quote:
Original post by snk_kid
Using std::advance in this case wouldn't be a great idea, better to use the iterator category and do tag dispatching at compile time.


std::advance does do tag dispatching.


I'm aware of that [wink], have alook at GCC's imp of copy_n (in ext folder) to get what i mean.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this