Performance Factors in C++
in [C++]
|
From: James Kuyper on 3 Sep 2009 22:37 slobasso wrote: > On Sep 2, 6:02 am, James Kuyper <jameskuy...(a)verizon.net> wrote: >> Mathias Gaunard wrote: >>> On 31 ao�t, 02:55, Thomas Maeder <mae...(a)glue.ch> wrote: >>>> Provided the iterators are pointers (or close relatives to pointers), >>>> which is the prerequisite for considiering the usage of memmove() or >>>> memcpy(), std::copy can certainly determine whether the areas overlap. >>> No, it can't. >>> The compiler could do it, by doing alias analysis, which is a hard (NP- >>> hard even) problem -- which is why you can't rely on the compiler >>> doing it -- but a function certainly cannot. >> Could you explain that in more detail? It seems to me that >> std::copy<T*>(p,q,n) could certainly make use of std::less<T*> to check >> whether [p,p+n) overlaps [q,q+n). What's the barrier to performing such >> a comparison? > > There are multiple problems here: > > 1) std::copy() is an algorithm that uses iterators. Iterators are not > raw pointers, but raw pointers can be iterators. Some types of > iterators cannot be compared for 'less than' or 'greater than' (non > random access iterators). It would be possible to write std::copy to > handle this situation, but only for random access iterators, but this > would be in appropriate due to the second problem (see below). This not about the general case of std::copy<InputIterator,OutputIterator>. The question was very specifically restricted to iterators which are pointers; in other words, it's about std::copy<T*,U*>. To even be able to consider whether to use memcpy() or memmove(), we must additionally restrict the discussion to std::copy<T*,T*> where std::type_traits<T>.is_trivial must be true; these restrictions have not previously been mentioned. > 2) Most copies are non-overlapping. If I add code inside std::copy to > make it handle overlapping copies, it would slow down all the non- > overlapping copies. That's a reason why std::copy<T*,T*> shouldn't do this; it's not a reason why std::copy<T*,T*> can't do this. As far as I can see, there's nothing preventing a specialization of std::copy<T*,T*>, where T is a trivial type, from comparing the pointers with std::less<> (to ensure that the results are meaningful if that are pointers into different objects), and then calling either memmove() or memcpy(), depending upon whether or not the results of those comparisons indicate that there is overlap. It's pointless to do so, because such checks serve the same purpose as checks that must also be performed by memmove() itself; if those checks indicate that it is safe to do so, memmove() should do the equivalent of calling memcpy(). Therefore, std::copy<T*> might as well simply always call memmove(), I'm not arguing that checking to determine whether memcpy() can be used instead of memmove() is a good idea; I just don't understand the assertion that it cannot be done. > ... If you look at the standard implementation where > std::copy is used in various implementations, You seem to be confusing the implementation of std::copy<> with the use of std::copy<>. Even if you aren't confused about the distinction, the way you've worded your response leaves me confused about what you're trying to say. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: James Kuyper on 3 Sep 2009 22:38 David Abrahams wrote: > on Wed Sep 02 2009, James Kuyper <jameskuyper-AT-verizon.net> wrote: > >> Mathias Gaunard wrote: >>> On 31 août, 02:55, Thomas Maeder <mae...(a)glue.ch> wrote: >>> >>>> Provided the iterators are pointers (or close relatives to pointers), >>>> which is the prerequisite for considiering the usage of memmove() or >>>> memcpy(), std::copy can certainly determine whether the areas overlap. >>> No, it can't. >>> The compiler could do it, by doing alias analysis, which is a hard (NP- >>> hard even) problem -- which is why you can't rely on the compiler >>> doing it -- but a function certainly cannot. >> Could you explain that in more detail? It seems to me that std::copy<T*>(p,q,n) could That should have been std::copy<T*,T*>(p,q,n). >> certainly make use of std::less<T*> to check whether [p,p+n) overlaps [q,q+n). What's >> the barrier to performing such a comparison? > > Doesn't your implementation of memmove already contain that > optimization? ;-) > I'm only questioning the claim that "it is hard (NP-hard even)" to perform such a check; I'm not arguing that it's a good thing to do. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Jens Schmidt on 4 Sep 2009 08:23 James Kuyper wrote: > Mathias Gaunard wrote: >> The compiler could do it, by doing alias analysis, which is a hard (NP- >> hard even) problem -- which is why you can't rely on the compiler >> doing it -- but a function certainly cannot. > > NP is an abbreviation used in complexity theory for "nondeterministic > polynomial time", where the polynomial in question is a polynomial in > 'n', where 'n' is some measure of the size of the problem, which gives > the amount of time it takes to verify that the solution to the problem > is correct. NP problems are not necessarily hard to solve; the category > includes some of the very easiest problems to solve. I think what you > actually mean is NP-complete, which is the sub-set of NP problems for > which no polynomial-time solution is known. Those are very hard > problems, at least when 'n' is large. For a definition of NP-hard, NP-complete and their relation to each other see <http://en.wikipedia.org/wiki/NP-hard>. -- Viele Grüße, Jens Schmidt [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Jens Schmidt on 4 Sep 2009 08:23 James Kuyper schrieb: > I'm only questioning the claim that "it is hard (NP-hard even)" to > perform such a check; I'm not arguing that it's a good thing to do. I came to the understanding that you are talking about different things. The NP-hard claim was done for a compile-time check, where the check is not even computable in all cases (halting problem equivalent). For a run-time check this is trivial. -- Viele Grüße, Jens Schmidt [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Mathias Gaunard on 4 Sep 2009 08:32
On 4 sep, 15:39, James Kuyper <jameskuy...(a)verizon.net> wrote: > Mathias Gaunard wrote: > > On 31 ao t, 02:55, Thomas Maeder <mae...(a)glue.ch> wrote: > > >> Provided the iterators are pointers (or close relatives to pointers), > >> which is the prerequisite for considiering the usage of memmove() or > >> memcpy(), std::copy can certainly determine whether the areas overlap. > > > No, it can't. > > The compiler could do it, by doing alias analysis, which is a hard (NP- > > hard even) problem -- which is why you can't rely on the compiler > > doing it -- but a function certainly cannot. > > NP problems are not necessarily hard to solve; the category > includes some of the very easiest problems to solve. I think what you > actually mean is NP-complete, which is the sub-set of NP problems for > which no polynomial-time solution is known. That is not what NP-complete is. An NP-complete problem is a problem to which any NP problem can be reduced in polynomial time. (the point of that mechanism is that if you can prove a NP-complete problem to be P, then you solve the infamous P = NP) It seems you're confusing NP-complete with NP - P. NP-hard is also a different thing, which means "as hard as NP or harder". I suggest you look up the definitions on wikipedia. Note I'm no expert in such things however, nor do I have any desire to discuss them. > Those are very hard > problems, at least when 'n' is large. Size of the input is irrelevant to hardness of a problem. > What is the 'n' you're thinking of here? The input of the problem is the source code of the program, preferably encoded as a control-flow graph or something like that. (I'm no expert of the subject) It's not four pointers. It seems you've been confusing alias analysis with the problem of determining whether two integer intervals overlap. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |