Performance Factors in C++
in [C++]
|
From: David Abrahams on 3 Sep 2009 01:26 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 > 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? ;-) -- Dave Abrahams BoostPro Computing http://www.boostpro.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Mathias Gaunard on 3 Sep 2009 07:28 On 2 sep, 15:02, James Kuyper <jameskuy...(a)verizon.net> wrote: > 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 is none. It would only need to happen at runtime, and conservative implementations usually only select the best algorithm at compile- time. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Edward Rosten on 3 Sep 2009 07:26 On 2 Sep, 14:02, 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? This is even easier for a given implementation since it can rely on implementation defined behavior of <, for instance that pointers ismply compare like unsigned integers. Presumably, the compiler could also make use of is_pod: gcc for instance has an __is_pod extension and this could easily be used to decide to simply call memcpy. There is nothing that states that the compiler can't use magic to create excellent implementations of the standard library. Indeed, gcc has an internal implementation of memcpy: it will often (usually?) insert inlined code instead of calling a function. -Ed -- (You can't go wrong with psycho-rats.)(http://mi.eng.cam.ac.uk/~er258) /d{def}def/f{/Times s selectfont}d/s{11}d/r{roll}d f 2/m{moveto}d -1 r 230 350 m 0 1 179{ 1 index show 88 rotate 4 mul 0 rmoveto}for/s 12 d f pop 235 420 translate 0 0 moveto 1 2 scale show showpage -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Brian Neal on 3 Sep 2009 09:10 On Aug 30, 9:44 am, Mathias Gaunard <loufo...(a)gmail.com> wrote: > On 30 ao�t, 01:24, Thomas Maeder <mae...(a)glue.ch> wrote: > > > Just use std::copy and let the library implementation sort out which > > optimizations apply. > > std::copy can't even call memcpy since the arguments are not > guaranteed not to overlap, at best it can call memmove. > It doesn't statically know the alignment and size of memory either, so > even if it the arguments were guaranteed not to overlap, it couldn't > do better than memcpy anyway. I've seen a std::copy() turn into a memcpy() call on gcc. And this was way back on gcc 2.95. It used template magic to determine it was being passed pointers to built in types. I don't recall if it did any overlap checking, but it might have. -- [ 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:39
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 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. What is the 'n' you're thinking of here? I see 4 pointers here that need to be compared. Even the worst NP-complete problems are usually pretty tractable when n==4. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |