unsafe STL patch

François Dumont francois.cppdevs@free.fr
Mon Feb 1 20:39:00 GMT 2010


Paolo Carlini wrote:
> Hi,
>   
>> I solved my problem, indeed it was coming from pch. I have regenerated
>> them now and it works fine, I will complete the patch.
>>     
> wait...
>   
>> About the limitation to random access iterator. It has to be so to
>> keep on detecting this kind of problem:
>>
>> using namespace std;
>> list<int> l({1, 2, 3});
>> vector<int> v;
>>
>> list<int>::iterator first(l.begin()), last(l.begin());
>> ++first; ++first;
>> ++last;
>> v.insert(v.end(), first, last);
>>
>>    You see range iterator is badly defined because first is after
>> last. This is something that cannot be detected by the check_range
>> function because there is no < operator on bidirectional iterator. The
>> problem will only appear when we will reach past the list end when
>> incrementing first if first is still a _Safe_Iterator.
>>     
> I see. Hey, when presenting your work, you should discuss these details
> in the first place! ;)
>   
This is just what I was expecting when I did my proposition !
> Anyway, before going ahead with more details, I'd like to understand
> more about the core idea: is it only in order to improve the
> *performance* of debug mode? How much do you expect the performance to
> improve? Are you **really** sure we don't loose any debug power (eg.,
> please explain why operator* of base() is equivalent, just more
> efficient, to operator* of _Safe_iterator)? Are the prospective changes
> limited to such templatized members?
>
>   
Yes indeed, the idea is _only_ to reduce performance impact of debug 
mode. Consider the list template constructor from iterator range for 
instance that rely on _M_initialize_dispatch:

template<typename _InputIterator>
        void
        _M_initialize_dispatch(_InputIterator __first, _InputIterator 
__last,
                               __false_type)
        {
          for (; __first != __last; ++__first)
            push_back(*__first);
        }

This code use 3 iterator operators:
- operator !=
- operator ++
- operator *

This patch will avoid the additional work performed in debug mode in all 
those operators:
- operator !=
      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
                            _M_message(__msg_iter_compare_bad)
                            ._M_iterator(__lhs, "lhs")
                            ._M_iterator(__rhs, "rhs"));
      _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
                            _M_message(__msg_compare_different)
                            ._M_iterator(__lhs, "lhs")
                            ._M_iterator(__rhs, "rhs"));
      return __lhs.base() != __rhs.base();

- operator ++:
        _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
                              _M_message(__msg_bad_inc)
                              ._M_iterator(*this, "this"));
        ++_M_current;
        return *this;

- operator *:

        _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
                              _M_message(__msg_bad_deref)
                              ._M_iterator(*this, "this"));
        return *_M_current;

As you can see it is a number of checks avoided N times, N being the 
number of elements in the range. The gain was rather clear so I haven't 
done any benchmark, I will try to do one.

Moreover, this patch will also avoid some instantiations because for the 
moment __norm::list::insert will be instantiated with 
_Safe_Iterator<vector::iterator, vector>; with the patch it will still 
be instantiated with vector::iterator like in non debug mode.

About the validity of the idea, aren't we going to lose debug mode 
power. IMO no we do not lose anything as we remove the debug layer 
around already validated iterators, we know that they belong to the same 
container and that __first <= __last so the loop in 
_M_initialize_dispatch cannot fail. But I also hope that some libstdc++ 
contributors will challenge my opinion. In fact we lose something, we 
won't expose normal code (from __norm namespace) to the debug mode. I 
simply consider that debug mode is here to validate libstdc++ clients 
code and not libstdc++ code itself that should be unit tested enough to 
avoid such additional checks when client code is running.

The patch is not limited to containers template methods, all range based 
algorithms could use the same technique.

Bests
> Paolo.
>   



More information about the Libstdc++ mailing list