[xpressive] Performance Tuning?

[Robert Jones-2]

2009/7/20 <jon_zhou@...>

> hi there
>
> any design patterns implementation in boost？
>
> such as ,singleton,object factory,etc?
>

Boost.Signals implements the observer pattern, I believe.

- Rob.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[OvermindDL1]

On Mon, Jul 20, 2009 at 1:40 PM, Edward Grace<ej.grace@...> wrote:

>>>    chrono_start = chrono();
>>>    while ( double( chrono_wall() - chrono_wall_start ) <
>>> chrono_wall_scale*4.0);
>>>    chrono_end = chrono();
>>>
>>> I'm now doubly confused as it appears to be complaining about the return
>>> type of std::clock, (the default wall-clock timer).  Maybe I can get my
>>> hands on a windows machine and compiler tomorrow....
>>
>> Edward, just a compliment (for now): what you are doing is cool!
>> I'm starting to be an eager supporter.
>
> Always good to hear.... ;-)
>
> After a mammoth effort and much code rejigging I've got it to not only
> compile, but work on Windows with MSVC8!  In fairness to the MS compiler it
> did spot some subtle run-time errors that I was getting away with just fine
> with g++.   I've had to rip out parts that used my home brew
> striding_iterator since there's no way to avoid dereferencing one past the
> end of the end.
>
> Similarly I've had to give up on keeping all the time deltas as integer
> types in order to cope with the Windows .QuadPart approach.  If you refer
> back to the discussion I was having with OverminD1 (thanks a lot for your
> efforts) you'll see it was causing some grief when trying to compile on
> Windows.   As a consequence the timer appears to be less sensitive, so may
> not pick out differences < 0.5%, but frankly who cares? ;-)
>
> Anyhow, enough rambling:
>
>  http://tinyurl.com/km9xlh
>
> The new timing code (with a better PDF containing docs) is:
>
>  ejg-timer-0.0.3.tar.gz
>
> Those of you watching in black and white need to set up MSVC and compile
> example_timer.cpp.  Everyone watching in colour need only do the usual:
>
>  ./configure; make; make install
>
> voodo...
>
> The uint_parser example that utilises the above is:
>
>  ejg_uint_parser_0_0_3.cpp
>
> I wait with baited breath.

Two warnings, but compile is successful.

1>R:\Programming_Projects\Spirit_Price\ejg_uint_parser_timing\other_includes\ejg/timer.cpp(468)
: warning C4267: 'initializing' : conversion from 'size_t' to
'unsigned int', possible loss of data
1>        R:\Programming_Projects\Spirit_Price\ejg_uint_parser_timing\other_includes\ejg/timer.cpp(558)
: see reference to function template instantiation
'ejg::timer_result_type
&ejg::generic_timer<ticks>::measure_execution_result<void(__cdecl
*)(void)>(_Operation,ejg::timer_result_type &)' being compiled
1>        with
1>        [
1>            ticks=ticks,
1>            _Operation=void (__cdecl *)(void)
1>        ]
1>        R:\Programming_Projects\Spirit_Price\ejg_uint_parser_timing\other_includes\ejg/timer.cpp(242)
: see reference to function template instantiation 'double
ejg::generic_timer<ticks>::measure_execution_time<void(__cdecl
*)(void)>(_Operation)' being compiled
1>        with
1>        [
1>            ticks=ticks,
1>            _Operation=void (__cdecl *)(void)
1>        ]
1>        .\ejg_uint_parser_0_0_3.cpp(154) : see reference to function
template instantiation 'void
ejg::generic_timer<ticks>::measure_percentage_speedup<void(__cdecl
*)(void),void(__cdecl *)(void)>(_OperationA,_OperationB,double
&,double &,double &)' being compiled
1>        with
1>        [
1>            ticks=ticks,
1>            _OperationA=void (__cdecl *)(void),
1>            _OperationB=void (__cdecl *)(void)
1>        ]
1>R:\Programming_Projects\Spirit_Price\ejg_uint_parser_timing\other_includes\ejg/timer.cpp(468)
: warning C4267: 'initializing' : conversion from 'size_t' to
'unsigned int', possible loss of data
1>        R:\Programming_Projects\Spirit_Price\ejg_uint_parser_timing\other_includes\ejg/timer.cpp(558)
: see reference to function template instantiation
'ejg::timer_result_type
&ejg::generic_timer<ticks>::measure_execution_result<_LARGE_INTEGER(__cdecl
*)(void)>(_Operation,ejg::timer_result_type &)' being compiled
1>        with
1>        [
1>            ticks=ticks,
1>            _Operation=_LARGE_INTEGER (__cdecl *)(void)
1>        ]
1>        R:\Programming_Projects\Spirit_Price\ejg_uint_parser_timing\other_includes\ejg/timer.cpp(166)
: see reference to function template instantiation 'double
ejg::generic_timer<ticks>::measure_execution_time<_LARGE_INTEGER(__cdecl
*)(void)>(_Operation)' being compiled
1>        with
1>        [
1>            ticks=ticks,
1>            _Operation=_LARGE_INTEGER (__cdecl *)(void)
1>        ]
1>        R:\Programming_Projects\Spirit_Price\ejg_uint_parser_timing\other_includes\ejg/timer.cpp(92)
: see reference to function template instantiation 'void
ejg::generic_timer<ticks>::measure_infinity_time<_LARGE_INTEGER(__cdecl
*)(void)>(_Operation,double &,double &,double &,size_t)' being
compiled
1>        with
1>        [
1>            ticks=ticks,
1>            _Operation=_LARGE_INTEGER (__cdecl *)(void)
1>        ]
1>        R:\Programming_Projects\Spirit_Price\ejg_uint_parser_timing\other_includes\ejg/timer.cpp(80)
: while compiling class template member function 'void
ejg::generic_timer<ticks>::calibrate_chrono_overhead(void)'
1>        with
1>        [
1>            ticks=ticks
1>        ]
1>        .\ejg_uint_parser_0_0_3.cpp(133) : see reference to class
template instantiation 'ejg::generic_timer<ticks>' being compiled
1>        with
1>        [
1>            ticks=ticks
1>        ]


Running the file gives:
initializing input strings...
Calibrating overhead...<Unhandled Exception>

So, debugging into it now reveals that the error happens on line 170
in timer.cpp, this function call:

      ejg::statistics::robust_linear_fit(xs.begin() ,  xs.begin() + n,
                                         ys.begin() ,  ys.begin() + n,
                                         tmp.begin(), tmp.begin() + n,
                                         intercept,  slope, __);

The problem is that n==4, xs.size()==4, ys.size()==4, and
tmp.size()==0, thus it is trying to get an iterator 4 elements past
the end.  I do not see where you can set tmp either, at the start of
the function you tmp.clear(), but then never touch it again, so of
course it is going to be a size of 0, does this function really work
in gcc, and if so how?
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Joel de Guzman-2]

Edward Grace wrote:

> Anyhow, enough rambling:
>
>   http://tinyurl.com/km9xlh
>
> The new timing code (with a better PDF containing docs) is:
>
>   ejg-timer-0.0.3.tar.gz
>
> Those of you watching in black and white need to set up MSVC and compile
> example_timer.cpp.  Everyone watching in colour need only do the usual:
>
>   ./configure; make; make install

If you're really watching in color, and assuming you want that library
in Boost, then you'd want to use Bjam instead ;-) Also, most docs in
Boost use Quickbook/Boostbook.

Regards,
--
Joel de Guzman
http://www.boostpro.com
http://spirit.sf.net

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Edward Grace]

>> I wait with baited breath.
>
> Two warnings, but compile is successful.
>
> 1>R:\Programming_Projects\Spirit_Price\ejg_uint_parser_timing
> \other_includes\ejg/timer.cpp(468)
> : warning C4267: 'initializing' : conversion from 'size_t' to
> 'unsigned int', possible loss of data
> 1>

[....] etc.

> Running the file gives:
> initializing input strings...
> Calibrating overhead...<Unhandled Exception>
>
> So, debugging into it now reveals that the error happens on line 170
> in timer.cpp, this function call:
>
>       ejg::statistics::robust_linear_fit(xs.begin() ,  xs.begin() + n,
> ys.begin() ,  ys.begin() + n,
> tmp.begin(), tmp.begin() + n,
> intercept,  slope, __);

Blast!

That's one of the goofs I spotted via MSVC.  It turns out I didn't  
pull the latest sources from CVS when building the tar file.  Sorry.

> the function you tmp.clear(), but then never touch it again, so of
> course it is going to be a size of 0, does this function really work
> in gcc, and if so how?

Yes it does work in g++, I think because it's less conforming to the  
true concept of a vector object than the MSVC compiler (there I wrote  
it).  I presume that's what all the

#if defined(BOOST_MSVC)
#pragma inline_depth(255)
#pragma inline_recursion(on)
#define _SECURE_SCL 0
#endif // defined(BOOST_MSVC)

means at the top of Joel's file - switching off the bounds  
checking.   I think the gcc implementation of the stl is unchecked by  
default. Consider the following:

#include <vector>
#include <iostream>
#include <iterator>
int main() {
   using namespace std;
   vector<double> v(10);
   cout << v.capacity() << " " << v.size() << endl;
   v.clear();
   cout << v.capacity() << " " << v.size() << endl;

   // Will the following fail? It jolly well should!
   v[5]  = 2;
   cout << v.capacity() << " " << v.size() << endl;

   // Consequently if we squirt it out using
   copy(v.begin(),v.begin()+10,ostream_iterator<double>(cout," "));

   // It *might* work as in practice it should access the same memory  
as if we
   // had not done .clear().  Strictly though it's evil!
   return 0;
}


$ ./clear_capacity
10 10
10 0
10 0
0 0 0 0 0 2 0 0 0 0

That's pure evil of course! I suppose that's a good reason for always  
using .begin() and .end() rather than .begin() + N.

I'll double and triple check everything again to confirm it works,  
then post it up again.

Sorry about this mucking around. It makes me appreciate how hard it  
is to get things not just working but 'correct' across so many  
platforms.

-ed
>

------------------------------------------------
"No more boom and bust." -- Dr. J. G. Brown, 1997

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[OvermindDL1]

On Tue, Jul 21, 2009 at 4:17 AM, Edward Grace<ej.grace@...> wrote:
> Sorry about this mucking around. It makes me appreciate how hard it is to
> get things not just working but 'correct' across so many platforms.

Heh, I know how that is.  My development is on Windows, but I still
distribute many of my libraries to people who use it with GCC, so I
have learned to fix many things.  :)

In my own written code I am in a pretty good habit now, whatever I
write seems to compile correctly everywhere, but that was after many
many years...
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Celtic Minstrel]

On Tue, Jul 21, 2009 at 6:17 AM, Edward Grace<ej.grace@...> wrote:
>  // Will the following fail? It jolly well should!
>  v[5]  = 2;
>  cout << v.capacity() << " " << v.size() << endl;

> That's pure evil of course! I suppose that's a good reason for always using
> .begin() and .end() rather than .begin() + N.

Correct me if I'm wrong, but it seems you're complaining that v[5]
doesn't do bounds checking?
The standard does not require bounds checking on array subscript,
though it seems there's
nothing saying it shouldn't bounds check. But there's the alternate
v.at(5) notation if you do need
bounds checking.

--SPCD
"Celtic Minstrel"
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Stewart, Robert]

Stewart, Robert wrote:
> Eric Niebler wrote:
> >
> > Robert, can you please post your complete code so that we can
> > actually
> > have meaningful numbers to look at? Thanks.
>
> I will do so as soon as I'm able.

As a step in that direction, I have placed a file in the vault which contains test inputs and the corresponding result, as gleaned from a run of my test suite: http://tinyurl.com/n77jt4.

_____
Rob Stewart                           robert.stewart@...
Software Engineer, Core Software      using std::disclaimer;
Susquehanna International Group, LLP  http://www.sig.com

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Edward Grace]

On 21 Jul 2009, at 11:42, OvermindDL1 wrote:

> On Tue, Jul 21, 2009 at 4:17 AM, Edward  
> Grace<ej.grace@...> wrote:
>> Sorry about this mucking around. It makes me appreciate how hard  
>> it is to
>> get things not just working but 'correct' across so many platforms.
>
> Heh, I know how that is.  My development is on Windows, but I still
> distribute many of my libraries to people who use it with GCC, so I
> have learned to fix many things.  :)

Right,

Hopefully this is (n+1) time lucky!  I've placed them on the Boost  
Vault under Tools as before.

Direct links below:

http://tinyurl.com/ejg-timer-0-0-4-zip

http://tinyurl.com/uint-parser-0-0-4-cpp

I have verified these working under Release and Debug on MSVC8.  The  
uint_parser gives a load of spirit related warnings, but seems to  
work - not sure what to make of them.

Again, for 'Debug' Spirit is reported as being around -50% faster  
[negative speedup - like the expanding economy] than the native  
versions, for 'Release' with all optimisation switched on it is  
reported as being ~1000% faster than atol.  As I mentioned before I  
find this speedup unnerving.  Not knowing what Spirit does I've no  
idea if somewhere deep in its guts things might be optimised away.

Please ignore the message on the Vault saying '(Please wait) -  
Currently I am testing this again from the download.' For some  
unknown reason I don't seem to be able to modify it.

Attached is a screen shot for proof!

-ed



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Raindog]

Celtic Minstrel wrote:

> On Tue, Jul 21, 2009 at 6:17 AM, Edward Grace<ej.grace@...> wrote:
> >  // Will the following fail? It jolly well should!
> >  v[5]  = 2;
> >  cout << v.capacity() << " " << v.size() << endl;
>
> > That's pure evil of course! I suppose that's a good reason for always using
> > .begin() and .end() rather than .begin() + N.
>
> Correct me if I'm wrong, but it seems you're complaining that v[5]
> doesn't do bounds checking?
> The standard does not require bounds checking on array subscript,
> though it seems there's
> nothing saying it shouldn't bounds check. But there's the alternate
> v.at(5) notation if you do need
> bounds checking.
>
> --SPCD
> "Celtic Minstrel"
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>
>  

The issue is that v.begin(), v.begin()+5 should not be bounds checked,
but by default in vc9 (vs 2008) it is. In vc10, the default is that it
is not on by default.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Christopher Jefferson]

On 21 Jul 2009, at 21:35, Raindog wrote:

> Celtic Minstrel wrote:
>> On Tue, Jul 21, 2009 at 6:17 AM, Edward  
>> Grace<ej.grace@...> wrote:
>> >  // Will the following fail? It jolly well should!
>> >  v[5]  = 2;
>> >  cout << v.capacity() << " " << v.size() << endl;
>>
>> > That's pure evil of course! I suppose that's a good reason for  
>> always using
>> > .begin() and .end() rather than .begin() + N.
>>
>> Correct me if I'm wrong, but it seems you're complaining that v[5]
>> doesn't do bounds checking?
>> The standard does not require bounds checking on array subscript,
>> though it seems there's
>> nothing saying it shouldn't bounds check. But there's the alternate
>> v.at(5) notation if you do need
>> bounds checking.
>>
>> --SPCD
>> "Celtic Minstrel"
>> _______________________________________________
>> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>>
>>
> The issue is that v.begin(), v.begin()+5 should not be bounds  
> checked, but by default in vc9 (vs 2008) it is. In vc10, the default  
> is that it is not on by default.
>

No no, it's quite legal to bounds check it. As soon as you go past the  
end of the vector, you are into undefined behaviour, and any kind of  
nasty thing could happen.

In practice you might find your code works fine, but it's not  
impossible some future case or optimisation will cause broken behaviour.

Chris
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Edward Grace]

On 21 Jul 2009, at 13:42, Celtic Minstrel wrote:

> On Tue, Jul 21, 2009 at 6:17 AM, Edward  
> Grace<ej.grace@...> wrote:
>>  // Will the following fail? It jolly well should!
>>  v[5]  = 2;
>>  cout << v.capacity() << " " << v.size() << endl;
>
>> That's pure evil of course! I suppose that's a good reason for  
>> always using
>> .begin() and .end() rather than .begin() + N.
>
> Correct me if I'm wrong, but it seems you're complaining that v[5]
> doesn't do bounds checking?

Not really. Perhaps 'fail' in the above is not quite what I mean.  My  
main gripe is the inconsistency.

> The standard does not require bounds checking on array subscript,
> though it seems there's
> nothing saying it shouldn't bounds check. But there's the alternate
> v.at(5) notation if you do need
> bounds checking.

My problem is really that this is 'undefined' behaviour.  Surely  
anything that's 'undefined' is open to error?

My second gripe is that even the idea of undefined behaviour is  
inconsistent (in MSVC at least).  I can quite happily iterate  
something to .end() (one past the last element) but not to .end()+n  
--- why?  From what I understand dereferencing either is wrong, why  
is one more wrong than the other?

 From what I can see this prevents the simple creation of a striding  
iterator, for which the .end() can be at .end() + stride of the  
underlying vector.  One can do it easily by default in g++ as it  
doesn't hold your hand (exposing you to dereferincing this as being  
undefined) and leaving that up to you. In MSVC8 it will barf since  
the debug bounds checking doesn't allow you to keep iterating past  
the end.

Which is the correct treatment?

-ed
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Stewart, Robert]

Edward Grace wrote:

> On 21 Jul 2009, at 13:42, Celtic Minstrel wrote:
> > On Tue, Jul 21, 2009 at 6:17 AM, Edward
> > Grace<ej.grace@...> wrote:
>
> > The standard does not require bounds checking on array
> > subscript, though it seems there's nothing saying it
> > shouldn't bounds check. But there's the alternate v.at(5)
> > notation if you do need bounds checking.
>
> My problem is really that this is 'undefined' behaviour.
> Surely anything that's 'undefined' is open to error?
>
> My second gripe is that even the idea of undefined behaviour is
> inconsistent (in MSVC at least).  I can quite happily iterate
> something to .end() (one past the last element) but not to
> .end()+n --- why?

Because dereferencing an end iterator has undefined behavior.

> From what I understand dereferencing either is wrong, why is
> one more wrong than the other?

It isn't more wrong.  The effects are simply more pronounced for
one than the other due to some implementation detail on which you
cannot count.

>  From what I can see this prevents the simple creation of a
> striding iterator, for which the .end() can be at .end() +
> stride of the underlying vector.  One can do it easily by
> default in g++ as it doesn't hold your hand (exposing you to
> dereferincing this as being undefined) and leaving that up to
> you. In MSVC8 it will barf since the debug bounds checking
> doesn't allow you to keep iterating past the end.

The debug bounds checking is revealing that you are relying on
undefined behavior.

> Which is the correct treatment?

Perhaps you're unfamiliar with the phrase "undefined behavior."
It means that absolutely anything is possible.  Each
implementation can behave differently, even in different cases.
If you avoid doing what has undefined behavior, you'll never
encounter such vagaries.  If you persist in doing what has
undefined behavior, you'll need to account for the differences
among compilers -- across versions and operating systems -- and
any use cases that lead to different results.  Furthermore, you'd
have to maintain the non-portable code as each new compiler or
use cases presents.

If it isn't clear by now, don't dereference an end iterator and
don't try to dereference anything past it.  Doing so is
untenable in portable code.

_____
Rob Stewart                           robert.stewart@...
Software Engineer, Core Software      using std::disclaimer;
Susquehanna International Group, LLP  http://www.sig.com

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Edward Grace]

Dear Robert,

[ We're probably in danger of irritating other people if we continue  
this discussion too long let's try and keep it brief].

>> My second gripe is that even the idea of undefined behaviour is
>> inconsistent (in MSVC at least).  I can quite happily iterate
>> something to .end() (one past the last element) but not to
>> .end()+n --- why?
>
> Because dereferencing an end iterator has undefined behavior.

The above was a slip of the finger.  I agree with you regarding  
the .end() + n.   I should have based it on .begin() which was the  
original source of my iteration.

A concrete example of what I'm talking about is here:

   http://tinyurl.com/ns8j83

I assert that the problem is that the bounds checking in MSVC is  
wrong - it should only be checking for the de-referencing of invalid  
iterators not their creation.

What do you think?

>>  From what I can see this prevents the simple creation of a
>> striding iterator, for which the .end() can be at .end() +
>> stride of the underlying vector.  One can do it easily by
>> default in g++ as it doesn't hold your hand (exposing you to
>> dereferincing this as being undefined) and leaving that up to
>> you. In MSVC8 it will barf since the debug bounds checking
>> doesn't allow you to keep iterating past the end.
>
> The debug bounds checking is revealing that you are relying on
> undefined behavior.

I may be in practice - but I don't think I am in principle.

>> Which is the correct treatment?
>
> Perhaps you're unfamiliar with the phrase "undefined behavior."

It's occasionally been used to describe the conduct of some friends  
of mine.

> If it isn't clear by now, don't dereference an end iterator and
> don't try to dereference anything past it.

I don't think I am -- that's my point.

Ultimately are random access iterators *supposed* to be homeomorphic  
to the integers in the same (apparent) way C indices are?

-ed
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Stewart, Robert]

Edward Grace wrote:

>
> Dear Robert,
>
> >> My second gripe is that even the idea of undefined behaviour is
> >> inconsistent (in MSVC at least).  I can quite happily iterate
> >> something to .end() (one past the last element) but not to
> >> .end()+n --- why?
> >
> > Because dereferencing an end iterator has undefined behavior.
>
> The above was a slip of the finger.  I agree with you regarding
> the .end() + n.   I should have based it on .begin() which was the
> original source of my iteration.
>
> A concrete example of what I'm talking about is here:
>
>    http://tinyurl.com/ns8j83

   typedef std::vector<int> vector;
   vector v(3);

> I assert that the problem is that the bounds checking in MSVC is
> wrong - it should only be checking for the de-referencing of invalid
> iterators not their creation.

It is not valid according to the standard.  The operational equivalent for v.begin() + n, in Table 76 (random access iterator requirements) is:

   vector::iterator tmp(v.begin());
   tmp += n;

The operational semantics for tmp += n, same table, is:

   iterator_traits<vector::iterator>::difference_type m(n);
   if (m >= 0) while (m--) ++tmp;
   else while (m++) --tmp;

Finally, the precondition for ++tmp, from Table 74 (forward iterator requirements), and for --tmp, from Table 75 (bidirectional iterator requirements), requires that tmp be dereferenceable.

Once n >= v.size(), the resulting iterator is no longer dereferenceable and the MSVC checking is valid.

> >>  From what I can see this prevents the simple creation of a
> >> striding iterator, for which the .end() can be at .end() +
> >> stride of the underlying vector.  One can do it easily by
> >> default in g++ as it doesn't hold your hand (exposing you to
> >> dereferincing this as being undefined) and leaving that up to
> >> you. In MSVC8 it will barf since the debug bounds checking
> >> doesn't allow you to keep iterating past the end.
> >
> > The debug bounds checking is revealing that you are relying on
> > undefined behavior.
>
> I may be in practice - but I don't think I am in principle.

You are.

> Ultimately are random access iterators *supposed* to be homeomorphic
> to the integers in the same (apparent) way C indices are?

There are additional preconditions for the iterators.

_____
Rob Stewart                           robert.stewart@...
Software Engineer, Core Software      using std::disclaimer;
Susquehanna International Group, LLP  http://www.sig.com

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Christopher Jefferson]

On 22 Jul 2009, at 16:23, Stewart, Robert wrote:
>
>
>> Ultimately are random access iterators *supposed* to be homeomorphic
>> to the integers in the same (apparent) way C indices are?

I'm sure that:

int a[3]
int* b = a + 4;

Is illegal C code, as you have gone outside the bounds of your array,  
even if you never dereference the pointer.

Chris

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Edward Grace]

>> I assert that the problem is that the bounds checking in MSVC is
>> wrong - it should only be checking for the de-referencing of invalid
>> iterators not their creation.
>
> It is not valid according to the standard.  The operational  
> equivalent for v.begin() + n, in Table 76 (random access iterator  
> requirements) is:
>
>    vector::iterator tmp(v.begin());
>    tmp += n;
>
> The operational semantics for tmp += n, same table, is:
>
>    iterator_traits<vector::iterator>::difference_type m(n);
>    if (m >= 0) while (m--) ++tmp;
>    else while (m++) --tmp;
>
> Finally, the precondition for ++tmp, from Table 74 (forward  
> iterator requirements), and for --tmp, from Table 75 (bidirectional  
> iterator requirements), requires that tmp be dereferenceable.

Presumably the above requirement for the random access iterator is a  
result of it being an extension of a forward iterator?

> Once n >= v.size(), the resulting iterator is no longer  
> dereferenceable and the MSVC checking is valid.

Fair enough.  It is what it is.  As long as I know what to believe  
I'm happy.

-ed
------------------------------------------------
"No more boom and bust." -- Dr. J. G. Brown, 1997

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Edward Grace]

On 22 Jul 2009, at 18:02, Christopher Jefferson wrote:

> On 22 Jul 2009, at 16:23, Stewart, Robert wrote:
>>
>>
>>> Ultimately are random access iterators *supposed* to be homeomorphic
>>> to the integers in the same (apparent) way C indices are?
>
> I'm sure that:
>
> int a[3]
> int* b = a + 4;
>
> Is illegal C code, as you have gone outside the bounds of your array,
> even if you never dereference the pointer.

Following your minimalistic example, I'm thinking about:

typdef int index;
int a[3];

index i = 0;  // Index idx is homeomorphic to the integers 'cause it  
is one.

i -= 1000;
i += 2002;

int b=a[i];

That's clearly ok as idx is 2 and the last line is b=*(a + 2).

Whereas.

int *p = a;

p = p - 1000; // Undefined?
p = p + 1002;  // Also undefined?

int b=*p;

Is presumably undefined.

That implies to me that pointer arithmetic is *not* like integer  
arithmetic since the first example is not identical to the second.

Baring in mind the old adage of Mark Twain,

   http://www.quotationspage.com/quote/369.html

it seems to me absurd that they are not the same.  I guess that's  
just the way it is.


-ed


------------------------------------------------
"No more boom and bust." -- Dr. J. G. Brown, 1997

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Steven Watanabe-4]

AMDG

Edward Grace wrote:

> Following your minimalistic example, I'm thinking about:
>
> typdef int index;
> int a[3];
>
> index i = 0;  // Index idx is homeomorphic to the integers 'cause it
> is one.
>
> i -= 1000;
> i += 2002;
>
> int b=a[i];
>
> That's clearly ok as idx is 2 and the last line is b=*(a + 2).
>
> Whereas.
>
> int *p = a;
>
> p = p - 1000; // Undefined?
> p = p + 1002;  // Also undefined?
>
> int b=*p;
>
> Is presumably undefined.
>
> That implies to me that pointer arithmetic is *not* like integer
> arithmetic since the first example is not identical to the second.
>
> Baring in mind the old adage of Mark Twain,
>
>   http://www.quotationspage.com/quote/369.html
>
> it seems to me absurd that they are not the same.  I guess that's just
> the way it is.

This is also undefined behavior:

int i = 10;
i += std::numeric_limits<int>::max();
i -= std::numeric_limits<int>::max();

So integer arithmetic and pointer arithmetic are
really not very different.  The behavior of integer
arithmetic is defined as long as no calculations
overflow (This only applies to signed integers.
unsigned integers are guaranteed to wrap).
The behavior of pointer arithmetic is defined
as long as the pointers stay within the bounds of
the array (allowing for a one past the end, pointer).

In Christ,
Steven Watanabe

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[David Abrahams-3]

on Mon Jul 20 2009, Edward Grace <ej.grace-AT-imperial.ac.uk> wrote:

> I've had to rip out parts that used my home brew striding_iterator
> since there's no way to avoid dereferencing one past the end of the
> end.

A correct strided_iterator is enclosed.


// Copyright David Abrahams 2008. Distributed under the Boost
// Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#define _GLIBCXX_DEBUG 1

#include "boost/iterator/iterator_adaptor.hpp"
#include "boost/iterator/counting_iterator.hpp"
//#include <algorithm>
#include <numeric>
#include <cassert>
#include <iostream>
#include <iterator>

template <class RandomAccessIterator, std::size_t N>
struct strided_iterator
  : boost::iterator_adaptor<
        strided_iterator<RandomAccessIterator,N>,
        RandomAccessIterator
    >
{
    strided_iterator() {}
   
    explicit strided_iterator(
        RandomAccessIterator p,
        RandomAccessIterator start,
        RandomAccessIterator finish
    )
      : strided_iterator::iterator_adaptor_(p),
        start(start), finish(finish)
    {
    }
 private:
    friend class boost::iterator_core_access;
   
    void increment()
    {
        this->advance(1);
    }
   
    void decrement()
    {
        this->advance(-1);
    }

    typename strided_iterator::difference_type
    distance_to(strided_iterator const& rhs) const
    {
        return (rhs.base() - this->base() + N - 1) / N;
    }
   
    void advance(typename strided_iterator::difference_type x)
    {
        if (x > 0)
        {
            if (finish - this->base() >= N*x)
                this->base_reference() += N*x;
            else
                this->base_reference() = finish;
        }
        else
        {
            if (this->base() - start >= x*N)
                this->base_reference() -= x*N;
            else
                this->base_reference() = start;
        }
    }
   
    RandomAccessIterator start, finish;
};

template <std::size_t N, class I>
strided_iterator<I,N> make_strided_iterator(I pos, I start, I finish)
{
    return strided_iterator<I,N>(pos, start, finish);
}

int main()
{
    boost::counting_iterator<int> start(0);
    boost::counting_iterator<int> finish(13*7);

    int total = std::accumulate(
        make_strided_iterator<5>(start, start, finish),
        make_strided_iterator<5>(finish, start, finish), 0);

    int t2 = 0;
    for (int i = 0; i < 13*7; i+=5)
        t2 += i;

    assert(total == t2);

    std::copy(
        make_strided_iterator<5>(start, start, finish),
        make_strided_iterator<5>(finish, start, finish),
        std::ostream_iterator<int>(std::cout, " "));
}

   


--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[David Abrahams-3]

on Tue Jul 21 2009, Edward Grace <ej.grace-AT-imperial.ac.uk> wrote:

> I think the gcc
> implementation of the stl is unchecked by  default.

Yes, you can #define _GLIBCXX_DEBUG to get checking for GCC

--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost