swapping array values with just pointers?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 5 1234 ... LastLast
Results 1 to 15 of 61

Thread: swapping array values with just pointers?

  1. #1

    swapping array values with just pointers?

    First, I want to know how to do this in C++ itself. I know about stl boost etc. but I don't want to use those. I already have my own containers. Currently I have an array class (really a vector, just without the horrible semantics) that uses standard arrays internally for storage but the problem I encounter is that sorting large arrays of heavyweight objects is very slow.

    I want to swap the values in an array, but I don't want to do it by value because the objects are large and the copying is making it ridiculously slow even though the sort implementation itself is faster that stl or standard lib.

    So if I have a templated method defined as:

    Code:
    template <class type1> static inline void sort(type1* items, const long first, const long last){}

    I need to swap the elements without copying the whole objects back and forth. It's something pretty obvious but I am not sure any more it's actually possible if using standard arrays of objects.

    Obviously you can say:

    Code:
    type1* temp = items[6];
    items[6] = items[23];
    items[23] = temp;
    That's fine for primitives, but for objects it is very slow, and for large objects incredibly slow because it copies the whole thing.

    I tried to use references to pointers but that doesn't work. I can change pointers through references, but I am not changing the underlying array. I tried to make a swap on this basis but it will not compile it when I try to do something like:
    Code:
    template <class type> inline void swap(type*& one, type*& two){}
    
    ***
    swap(&items[6], &items[23]);
    It will work for single variables, but C++ can't make two implicit conversions in a row so I can't send it in that way.

    Similarly, I can't make a reference to a pointer directly, either. The following won't compile:
    Code:
    	long*& pr1 = contents+1;
    	long*& pr2 = contents+26;

    Doing it in the following manner compiles, but it just changes the values I send in:
    Code:
    template <class type> inline void swap(type* one, type* two){}
    I tried using memcopy, but that does not seem to work except for primitives:
    Code:
    	template <class type> inline void swap(type* one, type* two)
    	{
    		cerr<<"pointer size: "<<sizeof(one)<<endl;
    		type* temp[1];
    		memcpy(temp, one, sizeof(one));
    		memcpy(one, two, sizeof(one));
    		memcpy(two, temp, sizeof(one));
    	}
    It seems logical that memcpy would do the trick, so maybe I am just doing something wrong?


    It seems my only other option is to store everything as arrays of pointers instead, but I loathe to embark on such a change unless I absolutely have to. Is there some other way?

  2. #2

    Re: swapping array values with just pointers?

    ok, I was just using memcopy wrong. Looks like it does what I want:
    Code:
    	long* tempChunk = getSwapChunk(sizeof(SwapTester));
    	memcpy(&tempChunk, &contents[1], sizeof(SwapTester));
    	memcpy(&contents[1], &contents[27], sizeof(SwapTester));
    	memcpy(&contents[27], &tempChunk, sizeof(SwapTester));

  3. #3
    Join Date
    Aug 2007
    Posts
    858

    Re: swapping array values with just pointers?

    I want to know how to do this in C++ itself. I know about stl boost etc. but I don't want to use those.
    The "C++ way" is to use the Standard C++ Library, and for many people, Boost.

    I need to swap the elements without copying the whole objects back and forth. It's something pretty obvious but I am not sure any more it's actually possible if using standard arrays of objects.
    It is only possible when you are dealing with pointers to objects, allowing you to move around the pointers.

    It seems logical that memcpy would do the trick, so maybe I am just doing something wrong?
    ...
    ok, I was just using memcopy wrong. Looks like it does what I want:
    It doesn't. Any class or struct which implements a copy assignment operator, or has a member with a copy assignment operator, will be completely broken by memcpy.

  4. #4
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,315

    Re: swapping array values with just pointers?

    Quote Originally Posted by originalfamousjohnsmith
    I already have my own containers. Currently I have an array class (really a vector, just without the horrible semantics) that uses standard arrays internally for storage
    Since you claim that the semantics of your dynamic array container differs from std::vector, you should state exactly how does it differ. (Or are you merely talking about a slightly different interface in terms of function names, with functions that can be implemented as non-member non-friend functions implemented as such?)

    Quote Originally Posted by originalfamousjohnsmith
    the problem I encounter is that sorting large arrays of heavyweight objects is very slow.
    Quote Originally Posted by originalfamousjohnsmith
    It seems my only other option is to store everything as arrays of pointers instead, but I loathe to embark on such a change unless I absolutely have to. Is there some other way?
    Given what he states in his answer to the FAQ Why are the standard containers so slow?, I believe that Stroustrup will agree with the use of a container of pointers in this case. You could use a container of smart pointers, or a specialised container of pointers akin to Boost's pointer containers. Alternatively, if it is only sorting that is the problem rather than copying in general, you could use the pointer to an implementation idiom such that the swap function only needs to swap pointers to the implementation.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  5. #5

    Re: swapping array values with just pointers?

    I've seen that quote a million times. Stroustrup says a lot of things. This also obviously doesn't apply because 1) my containers user copies or this would not be an issue 2)since the other libs use copies it won't help my problem 3) my containers aren't intrusive.

    I just said I don't want to use those so it's completely unhelpful to ignore that. Moving to standard lib containers or stl or some similar crap is not an option. It would be far too much work and it would not actually gain me anything but overhead and more bugs, and it's simply not practical for me to do that anyway for reasons not worth going into.

    What does memcpy do to break objects with copy assignment operators? Is this an absolute rule in all cases or are you just pointing out that the proper initialization is not called by memcopy? As I mentioned I don't use any outside classes so if the latter is the case it should not be an issue. All the child members seem to be absolutely fine and I am only using it to swap between members in the same array, not to copy everything around willy-nilly and especially not to create objects.
    Last edited by originalfamousjohnsmith; August 23rd, 2009 at 10:14 AM.

  6. #6
    Join Date
    Apr 1999
    Posts
    27,433

    Re: swapping array values with just pointers?

    Quote Originally Posted by originalfamousjohnsmith View Post
    What does memcpy do to break objects with copy assignment operators? Is this an absolute rule in all cases or are you just pointing out that the proper initialization is not called by memcopy?
    Muliply inherited objects, where the layout may not be contiguous. Objects that use virtual classes. Objects that are referenced counted...

    Let's take a real life example -- If memcpy() is so safe, why does no compiler implementation from Microsoft, Gnu, or any other vendor use memcpy() internally on non-POD objects in the std::copy() algorithm function?

    Also, are you using std::sort() to sort your container? It doesn't matter that the container is a vector, deque, or your own invention as std::sort() works with any sequence of values with the proper iterator traits.
    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; August 23rd, 2009 at 10:53 AM.

  7. #7
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,315

    Re: swapping array values with just pointers?

    Quote Originally Posted by originalfamousjohnsmith
    This also obviously doesn't apply because 1) my containers user copies or this would not be an issue 2)since the other libs use copies it won't help my problem 3) my containers aren't intrusive.

    I just said I don't want to use those so it's completely unhelpful to ignore that.
    I did not suggest that you use a standard container. I suggested that you store (smart) pointers in your containers, or create pointer containers along the same lines as Boost's pointer containers. It is not at all obvious what does or does not apply since you provided no information about your containers in your original post other than to state that they were somehow different from the standard containers. Even now you fail to elaborate on what exactly are the interfaces and semantics of your containers.

    Quote Originally Posted by originalfamousjohnsmith
    Moving to standard lib containers or stl or some similar crap is not an option. It would be far too much work and it would not actually gain me anything but overhead and more bugs, and it's simply not practical for me to do that anyway for reasons not worth going into.
    I suggest you stop trolling, or be prepared to state why you consider the standard containers "crap". Not wanting to switch to the standard containers because of possible bugs introduced in such a switch is a reasonable position, but there is no need to also call them "crap" unless you are prepared to digress into a defense of your unnecessary position.

    Quote Originally Posted by originalfamousjohnsmith
    What does memcpy do to break objects with copy assignment operators? Is this an absolute rule in all cases or are you just pointing out that the proper initialization is not called by memcopy? As I mentioned I don't use any outside classes so if the latter is the case it should not be an issue.
    Since memcpy() just copies bytes, it may fail to correctly copy objects of non-POD types. (To quote the C++ Standard: "A POD-struct is an aggregate class that has no non-static data members of type non-POD-struct, non-POD-union (or array of such types) or reference, and has no user-defined copy assignment operator and no user-defined destructor.")

    EDIT:
    Quote Originally Posted by Paul McKenzie
    Also, are you using std::sort() to sort your container? It doesn't matter that the container is a vector, deque, or your own invention as std::sort() works with any sequence of values with the proper iterator traits.
    No, originalfamousjohnsmith claimed that "the sort implementation itself is faster that stl or standard lib".
    Last edited by laserlight; August 23rd, 2009 at 11:01 AM.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  8. #8
    Join Date
    Apr 1999
    Posts
    27,433

    Re: swapping array values with just pointers?

    Quote Originally Posted by laserlight View Post
    EDIT:

    No, originalfamousjohnsmith claimed that "the sort implementation itself is faster that stl or standard lib".
    Anyone can claim anything. The problem is that claims such as the one the OP states needs to be proven. Most veteran posters here aren't just wallflowers accepting claims from anyone posting.

    I've seen claims of "my sort is better than STL's sort" before, even here on CodeGuru way back (do a search, and you will see threads started many years ago by someone who couldn't keep his head that his sort was deemed unacceptable, so he was banned). Every time I see that claim, the user-written sort really fell down flat when other programmers scrutinized the code.

    If the claim is not bogus, more than likely, it's using techniques that are unsafe and would break anything else other than a small subset of specialized types that he may be using, therefore it is not usable as a generic sort. If it is supposed to be a generic sort, again, claims have fallen down flat before, and maybe the OP will take the challenge of actually proving their case.

    Also, the std::sort() can be implemented in any number of different ways by different compilers. So there is no "one" std::sort().

    Regards,

    Paul McKenzie

  9. #9
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,891

    Re: swapping array values with just pointers?

    Quote Originally Posted by originalfamousjohnsmith View Post
    (really a vector, just without the horrible semantics)
    What do you consider horrible about the vector semantics? I'm really curious.

    that uses standard arrays internally for storage but the problem I encounter is that sorting large arrays of heavyweight objects is very slow.

    I want to swap the values in an array, but I don't want to do it by value because the objects are large and the copying is making it ridiculously slow
    There are two possible solutions here. (1) If you want "array-like" random access to the objects, then you can internally store two arrays: one which contains the objects and is never reordered, and another which contains indexes to those objects which are reordered by the sort. Note that I suggested indexes rather than pointers, because those will be much easier to deal with when you want to resize the underlying object array. I'm guessing that this is essentially what Boost.MultiIndex does. Alternatively, (2) if you don't need random access, then you could use a different data structure (such as a linked list or binary tree) which is capable of reordering the elements without copying the objects themselves. This would be equivalent to choosing std::list, std::set or std::multiset over std::vector. Note also that std::multiset may be the best choice of the lot if you need the container to remain sorted after every insertion, while other options may be better if you only need to do one sort once everything is in there. Also note that if you only ever need to know the current greatest (or least) element, then something like std:riority_queue may be best. It all depends on your needs.

    even though the sort implementation itself is faster that stl or standard lib.
    I rather doubt it. I mean, if you use radix sort or bucket sort, then your algorithm may have better big-O time than STL's quicksort or mergesort implementation; but in my experience it's *still* hard to actually make it faster in terms of clock cycles. The STL sort algorithm is very, very good.

    I tried using memcopy, but that does not seem to work except for primitives:
    Don't use memcpy in a container intended for general use. Just don't. It'll cause you all sorts of grief later. (Don't use malloc() either. This isn't C.) The std::copy() algorithm will reduce to memcpy() when appropriate, and still work correctly the rest of the time; prefer it. The fact that you don't know this makes me even more dubious of your claims to have built a better container than what STL provides. The people who wrote those make experts look like noobs.

    It seems to me that you have some kind of bias against the STL. I'm curious where that comes from. Usually when people have trouble with the STL it's because they're using it suboptimally; properly leveraged, it's extremely powerful with good performance. If I needed to write a custom container, nine times out of ten I'd try to write it in terms of existing STL containers internally. In fact, if you post your container code, I'd be willing to write a container with an identical interface for you that leverages the STL internally, just for speed testing purposes. If you really did manage to do better, that'd be interesting to see.

    It would be far too much work and it would not actually gain me anything but overhead and more bugs
    Obviously I don't know your specific case, but I find it extremely unlikely that using STL would introduce more bugs unless you've got bugs already which are currently masked. One of the greatest benefits of STL is that it makes it a lot harder to write incorrect code that actually compiles.
    Last edited by Lindley; August 23rd, 2009 at 12:10 PM.

  10. #10

    Re: swapping array values with just pointers?

    Quote Originally Posted by Paul McKenzie View Post
    Muliply inherited objects, where the layout may not be contiguous. Objects that use virtual classes. Objects that are referenced counted...

    Let's take a real life example -- If memcpy() is so safe, why does no compiler implementation from Microsoft, Gnu, or any other vendor use memcpy() internally on non-POD objects in the std::copy() algorithm function?

    Also, are you using std::sort() to sort your container? It doesn't matter that the container is a vector, deque, or your own invention as std::sort() works with any sequence of values with the proper iterator traits.
    Regards,

    Paul McKenzie
    Well, what do you mean by contiguous? To my knowledge an object should be implemented as a struct. An object should never be anything but contiguous when it comes to its base members. Obviously any pointers will be pointing who knows where but the actual pointer values will get copied to the other object so they should point to the proper places. To copy is not the same as to swap. A shallow copy should be completely sufficient for a swap.

    If I copy from one array to another shallowly then for any pointers I wind up with two objects pointing to the same thing and 99.9% of the time that would be something very undesirable. There's also no temp object made so no destructors get called. The pointer values do copy over, but not the things pointed to but that's sort of the entire point.

    std sort has the same problem except it's much much slower.

  11. #11
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,891

    Re: swapping array values with just pointers?

    If you were working in C, then yes, all of that would be true and memcpy() would be fine for swapping.

    However, you're in C++, and the rules are a bit different. In some cases it may still be fine; in others it may not. Consider any object which is part of an inheritance hierarchy, for instance. Trying to swap that object via memcpy will probably break its virtual function table. And then there are user objects for which logical equality is not the same as bitwise equality----say, for instance, an object holds a pointer to some part of itself for some reason. Using memcpy() to swap that is clearly wrong, since now the object will hold a pointer to a different object instead of to itself.

    Just. Don't. Do. It. We aren't making this up.

    std sort has the same problem except it's much much slower.
    It depends on what you're sorting, doesn't it? If you're sorting an array of huge objects, then yeah, it's going to be slower. The secret to effective use of STL is-----don't try to do something which you know will be slow! If you've got an bunch of huge objects you need sorted, store them as a vector of smart pointers rather than a vector of the objects themselves. Then std::sort is fast!

    Like I said before----show me your container's interface. I'll code up an implementation of it using STL for speed testing purposes. Could be informative.
    Last edited by Lindley; August 23rd, 2009 at 01:08 PM.

  12. #12
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,315

    Re: swapping array values with just pointers?

    Quote Originally Posted by originalfamousjohnsmith
    The pointer values do copy over, but not the things pointed to but that's sort of the entire point.
    That is also the point behind both my suggestions of storing (smart) pointers or using the pointer to an implementation idiom.

    Quote Originally Posted by originalfamousjohnsmith
    std sort has the same problem except it's much much slower.
    Slower than what? Your sorting algorithm for which we also know nothing, and which could very well be fast but incorrect?
    Last edited by laserlight; August 23rd, 2009 at 01:12 PM.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  13. #13
    Join Date
    Apr 1999
    Posts
    27,433

    Re: swapping array values with just pointers?

    Quote Originally Posted by originalfamousjohnsmith View Post
    Well, what do you mean by contiguous? To my knowledge an object should be implemented as a struct. An object should never be anything but contiguous when it comes to its base members.
    You are thinking in 'C', when the language you're using is C++. When you are talking about non-POD types, the rules are not the same as for POD, i.e. 'C' types.

    Using 'C'-based, raw memory copying functions such as memcpy() invokes undefined behaviour on non-POD types -- that is the plain simple fact. Whether that undefined behaviour hurts you, that is another story. Even if it doesn't hurt you, the behaviour could change for a different compiler, a different version of the same compiler, or using different compiler options.

    Again, why does every implementation of std::copy() not use memcpy() internally if it's safe to use? Either the people who make the compiler implementations for the standard library are not very good programmers and aren't aware of memcpy(), or there are other reasons, the main one being the one I pointed out in this post.

    Regards,

    Paul McKenzie

  14. #14
    Join Date
    Apr 1999
    Posts
    27,433

    Re: swapping array values with just pointers?

    Quote Originally Posted by laserlight View Post
    Slower than what? Your sorting algorithm for which we also know nothing, and which could very well be fast but incorrect?
    That is exactly the scenario that occurred in those CodeGuru threads comparing std::sort() to the home-made sort (those threads were very long and go back at least 7 or 8 years ...)

    For a certain compiler, the home-made sort made a complete mess of sorting a non-POD type, while the std::sort() worked without any issues on the same type. The person who posted those claims got so flustered, he went on and basically blamed the failure of his code on a broken compiler, and not on the fact that 'C' based routines to do sorts using memcpy's all over the place did not work and are not guaranteed to work for certain non-POD types.

    Regards,

    Paul McKenzie

  15. #15
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,725

    Re: swapping array values with just pointers?

    To the O.P

    We write time critical image processing & machine control software.
    We are very concerned with the speed and efficiency of the code we write.
    We use the STL containers.
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

Page 1 of 5 1234 ... LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center