Re: stl skipping algorithms

Simon Trew wrote:
"Tom Widmer [VC++ MVP]" <tom_usenet@xxxxxxxxxxx> wrote:

an implementation of std::copy might use loop unrolling (e.g. Duff's Device) to speed things up. Segmented iterator optimizations are another possibility, where e.g. a deque or streambuf iterator can be copied with a series of memcpy calls.

Tom


I wrote a function template to reverse bytes (for reversing network byte order into machine order); it was templated on the size of the structure to reverse. I used std::reverse by default, after some honest and necessary reinterpret_casts. I don't want to get into too many details (no doubt I will in any follow-up posts), but I was surprised to find that the VC2005 optimizer did not unroll the reversing loop even for the 8-byte case, and IIRC it didn't even for the 4-byte case. I hand-rolled template specializations for those cases, and other smallish multiples of 4, which improved the performance enormously. (Our stuff is built on all our supported platforms such that almost all structures/classes are padded to have a sizeof exactly divisible by 4.) But it certainly made me wonder about how good the VC2005 optimizer was with loop unrolling, and I chastised myself for relying on it.

Of course, Your Mileage May Vary, but this would seem to be a very simple case, almost a base case, yet VC2005 wouldn't unroll it.

From reading, IIRC GCC is much better at loop unrolling. See http://www.ddj.com/dept/cpp/184403799 if you haven't read it before.

Changing the subject a little, I found on Friday that the C++ Standard Library shipping with VC2005 complains for a few library function templates that take iterators as template parameters, if they are instantiated with iterators not defined in the library-- e.g. raw pointers-- then if no traits were defined for them, they won't compile.

That seems strange, since all pointers have iterator_traits (there's a partial specialisation for pointer types).

This was with a debug build and I
suppose checked iterator support, so perhaps it was to be expected, but even in a debug build the library is supposed to be conforming, so should not require e.g. iterator traits when the spec. is silent on the matter? Or perhaps the response from (e.g.) PJ Plauger would be something like "then don't use checked iterator support-- they're over and above what the spec requires, but you need to have the traits defined for some of the library function templates to work"-- which would be perfectly reasonable. I've probably got this all wrong since I didn't get to the bottom of it and will follow up my investigations on Monday, and try to give a potted example. But one of the experts here might be able to correct me before I even have to start.

Sounds like it might be a bug in the checked iterator support.

To change the subject once again, look at strcpy in the GNU implementation for Linux on x86. A bizarre bit of C, that funnily enough happens to compile down (with gcc) to an extremely tight bit of machine code-- it's kinda reverse reverse engineering, making a bit of C that you know happens to spit out the machine code that you wanted to write in the first place. Surprise! When you compile it on Intel's 7 and 8 series compilers, it crashes because the strings might not be aligned at 4-byte boundaries. Admittedly this is down to a bug in those compilers that structures aren't always correctly aligned, but we must stand back and wonder at the sheer bravado of pretending to be portable (it's written in C and will compile on any conforming C compiler) while actually being targeted to a particular implementation and platform, and then crashing if strings don't happen to be aligned on four-byte boundaries.

A good thing about being a standard library writer is that you can depend on undefined behaviour, implementation defined behaviour, etc.

Tom
.

Relevant Pages

  • Re: stl skipping algorithms
    ... Segmented iterator optimizations are another ... I wrote a function template to reverse bytes (for reversing network byte ... Library shipping with VC2005 complains for a few library function templates ... that funnily enough happens to compile ...
    (microsoft.public.vc.stl)
  • Re: Is DEFCONSTANT broken?
    ... I'm not insisting on using DEFCONSTANT to do what I want, ... worked just fine until I tried to compile the file. ... If you need to do something nasty with that "constant", then you must, ... My use-case is that I'm writing an iterator module, ...
    (comp.lang.lisp)
  • Re: On PEP 322 (ireverse)
    ... > reverse and sort already exist in Python, ... the risk of confusion between the existing list methods and the ... classmethod of list instead (more general, one less built-in), ... "reversed range" iterator. ...
    (comp.lang.python)
  • Re: What about an EXPLICIT naming scheme for built-ins?
    ... as the iterator versions of sortedand reversed. ... > can be used in expressions, as it returns a copy of the sequence, sorted. ... > reverse() works in-place. ... > I would like to see Python introducing a naming scheme for built-ins. ...
    (comp.lang.python)
  • Re: Foreach and Iterators
    ... for (Object orow: new MyIter()) { ... public Iterator iterator() { ... my question is: why won't the following line compile: ... Of course, with the code that *does* work, the cast from Object to ...
    (comp.lang.java.help)
Loading