[iterators] Proof-of-concept for a sentinel iterator adapter
Attached is proof-of-concept code for a sentinel iterator adapter. It turns a pointer to sentinel terminated sequence, such as a C-style string, into a forward iterator with a conforming end iterator. This is more efficient than doing a separate sequence traversal just to find the end. I'm a little surprised that Boost doesn't already have such an iterator adapter. Or am I just missing it? Would a production version of this iterator adapter be a worthwhile addition to Boost.Iterators? Any other comments appreciated, --Beman // sentinel terminated sequence iterator proof-of-concept // Copyright Beman Dawes, 2009 #include <cassert> // sentinel terminated sequence iterator template < class T, T Sentinel = T() > class sentinel_iterator { public: sentinel_iterator() : m_ptr(0) {} // construct end iterator sentinel_iterator( T * p ) : m_ptr( (p && *p != m_sentinel) ? p : 0 ) {} sentinel_iterator & operator++() { assert(m_ptr); if ( *++m_ptr == m_sentinel ) m_ptr = 0; return *this; } T & operator*() const { assert(m_ptr); return *m_ptr; } bool operator==( const sentinel_iterator & rhs ) const { return m_ptr == rhs.m_ptr; } bool operator!=( const sentinel_iterator & rhs ) const { return m_ptr != rhs.m_ptr; } private: T * m_ptr; // 0 == the end iterator static const T m_sentinel = Sentinel; }; int main() { // test cases using default sentinel sentinel_iterator<char> it( "abc" ); assert( it != sentinel_iterator<char>() ); assert( *it == 'a' ); assert( *++it == 'b' ); assert( *++it == 'c' ); assert( ++it == sentinel_iterator<char>() ); sentinel_iterator<char> it2( "" ); assert( it2 == sentinel_iterator<char>() ); sentinel_iterator<char> it3( 0 ); assert( it3 == sentinel_iterator<char>() ); // test cases using non-default sentinel typedef sentinel_iterator<unsigned, -1> my_iter_type; unsigned data[] = { 0, 1, -1 }; my_iter_type my_it( data ); assert( my_it != my_iter_type() ); assert( *my_it == 0 ); assert( *++my_it == 1 ); assert( ++my_it == my_iter_type() ); unsigned my_sentinel = -1; my_iter_type my_it2( &my_sentinel ); assert( my_it2 == my_iter_type() ); my_iter_type my_it3( 0 ); assert( my_it3 == my_iter_type() ); return 0; }
On Wed, May 13, 2009 at 4:34 PM, Beman Dawes <bdawes@acm.org> wrote:
I'm a little surprised that Boost doesn't already have such an iterator adapter. Or am I just missing it?
Would a production version of this iterator adapter be a worthwhile addition to Boost.Iterators?
Absolutely, I haven't even thought of such a simple solution. Kevin
Beman Dawes escribió:
Attached is proof-of-concept code for a sentinel iterator adapter. It turns a pointer to sentinel terminated sequence, such as a C-style string, into a forward iterator with a conforming end iterator.
Having Sentinel specified as a non-type template parameter greatly reduces the category of types this can work with. I'd replace it with some SentinelFactory policy or something. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
joaquin@tid.es skrev:
Beman Dawes escribió:
Attached is proof-of-concept code for a sentinel iterator adapter. It turns a pointer to sentinel terminated sequence, such as a C-style string, into a forward iterator with a conforming end iterator.
Having Sentinel specified as a non-type template parameter greatly reduces the category of types this can work with. I'd replace it with some SentinelFactory policy or something.
That is not a bad idea, although it would really be good if the basic case can stay as optimaized as currently (having a static member). I guess having a static member is not an option for a general policy, thus giving us the usual iterator problem of double storage. -Thorsten
AMDG Thorsten Ottosen wrote:
joaquin@tid.es skrev:
Beman Dawes escribió:
Attached is proof-of-concept code for a sentinel iterator adapter. It turns a pointer to sentinel terminated sequence, such as a C-style string, into a forward iterator with a conforming end iterator.
Having Sentinel specified as a non-type template parameter greatly reduces the category of types this can work with. I'd replace it with some SentinelFactory policy or something.
That is not a bad idea, although it would really be good if the basic case can stay as optimaized as currently (having a static member). I guess having a static member is not an option for a general policy, thus giving us the usual iterator problem of double storage.
What about using a function object for testing for the sentinal and using EBO to optimize it away if it is stateless? In Christ, Steven Watanabe
Steven Watanabe wrote:
What about using a function object for testing for the sentinal and using EBO to optimize it away if it is stateless?
Is your suggestion the same as the code I just posted? If not could you post what you had in mind and explain what you mean about EBO for those of us who aren't up to speed on that issue? By the way, can you spot anything wrong with the code I posted. The fact that it passes Beman's unit tests gives me some confidence, but I'm not completely convinced that it can really be so simple. Thanks, Luke
AMDG Simonson, Lucanus J wrote:
Steven Watanabe wrote:
What about using a function object for testing for the sentinal and using EBO to optimize it away if it is stateless?
Is your suggestion the same as the code I just posted?
It's a different syntax but the effect is the same
If not could you post what you had in mind and explain what you mean about EBO for those of us who aren't up to speed on that issue?
template<class T, class Sentinel> class sentinel_iterator { public: sentinel_iterator(T* ptr, Sentinel s = Sentinel()); sentinel_iterator& operator++() { ++data.first(); if(data.second()(*data.first())) data.first() = 0; } //... private: boost::compressed_pair<T*, Sentinel> data; };
By the way, can you spot anything wrong with the code I posted. The fact that it passes Beman's unit tests gives me some confidence, but I'm not completely convinced that it can really be so simple.
It looks okay to me... In Christ, Steven Watanabe
Steven Watanabe wrote:
template<class T, class Sentinel> class sentinel_iterator { public: sentinel_iterator(T* ptr, Sentinel s = Sentinel()); sentinel_iterator& operator++() { ++data.first(); if(data.second()(*data.first())) data.first() = 0; } //... private: boost::compressed_pair<T*, Sentinel> data; };
Hmm, if Sentinel can't be optimized away at compile time then we don't want to copy it around when we pass the iterator by value. Similarly, we don't want to cast it by value every time it is checked as in my earlier code. Instead we want to enable the static const optimization Beman had in mind. To do this I changed the casting operator of the struct I provide as the sentinel parameter to cast to a const reference instead of T by value. The sentinel_iterator itself stays the same as it was in my previous posting. static const int sc_val = -1; struct s_val { operator const int& () const { return sc_val; } }; In this way the user can provide a static const reference as the template parameter for the sentinel value if they feel the need for such optimization. If it is an iterator over objects that are expensive to copy or default construct you would not want to cast by value or default construct the sentinel value in the iterator. Regards, Luke
AMDG Simonson, Lucanus J wrote:
Steven Watanabe wrote:
template<class T, class Sentinel> class sentinel_iterator { public: sentinel_iterator(T* ptr, Sentinel s = Sentinel()); sentinel_iterator& operator++() { ++data.first(); if(data.second()(*data.first())) data.first() = 0; } //... private: boost::compressed_pair<T*, Sentinel> data; };
Hmm, if Sentinel can't be optimized away at compile time then we don't want to copy it around when we pass the iterator by value. Similarly, we don't want to cast it by value every time it is checked as in my earlier code. Instead we want to enable the static const optimization Beman had in mind. To do this I changed the casting operator of the struct I provide as the sentinel parameter to cast to a const reference instead of T by value. The sentinel_iterator itself stays the same as it was in my previous posting.
Ok. In that case just change my code to create the Sentinel on demand. As long as the Sentinel is an empty class (for example if its operator() compares to a global constant...) then the storage will be optimized away by compressed_pair, using EBO.
static const int sc_val = -1; struct s_val { operator const int& () const { return sc_val; } };
In this way the user can provide a static const reference as the template parameter for the sentinel value if they feel the need for such optimization. If it is an iterator over objects that are expensive to copy or default construct you would not want to cast by value or default construct the sentinel value in the iterator.
The use of implicit conversions is not quite bulletproof, as it can fail in cases like this: template<class T> class C; template<class T1, class T2> bool operator==(const C<T1>&, const C<T2>&); or like this class C { template<class T> C(const T&); }; You can try to get around this problem by defining your own comparison operators, but... // try to define a generic static sentinel template<class T> struct static_value { operator const T&() const { return(value); } static const T value; }; template<class T> const T static_value<T>::value = T(); template<class T> bool operator==(const static_value<T>&, const T&); // now create a class class C: // Let's define a generic comparison operator... template<class T> bool operator==(const T&, const C&); // and this breaks because of the ambiguity sentinel_iterator<T, static_value<T> > it; Of course this can be fixed by adding a more specialized overload just for C, but seems easier to not use operator== at all. Trying to bypass the problem by explicitly casting in sentinel_iterator is less than ideal, because it requires that the test to use equality for the value_type, rather than some other arbitrary operation. In Christ, Steven Watanabe
Thorsten Ottosen wrote:
joaquin@tid.es skrev:
Beman Dawes escribió:
Attached is proof-of-concept code for a sentinel iterator adapter. It turns a pointer to sentinel terminated sequence, such as a C-style string, into a forward iterator with a conforming end iterator.
Having Sentinel specified as a non-type template parameter greatly reduces the category of types this can work with. I'd replace it with some SentinelFactory policy or something.
That is not a bad idea, although it would really be good if the basic case can stay as optimaized as currently (having a static member). I guess having a static member is not an option for a general policy, thus giving us the usual iterator problem of double storage.
I don't understand the rationale for m_sentinel. Couldn't the code refer to Sentinel directly as a compile time constant as opposed to a static member variable? It seems like Beman had two different things in mind. What he seems to want is for the 2nd template parameter of sentinel_iterator to be something that can cast to T or T itself and default to default constructed T. The code below seems to work... Regards, Luke #include <cassert> // sentinel terminated sequence iterator template < class T, typename Sentinel = T > class sentinel_iterator { public: sentinel_iterator() : m_ptr(0) {} // construct end iterator sentinel_iterator( T * p ) : m_ptr( (p && *p != Sentinel()) ? p : 0 ) {} sentinel_iterator & operator++() { assert(m_ptr); if ( *++m_ptr == Sentinel() ) m_ptr = 0; return *this; } T & operator*() const { assert(m_ptr); return *m_ptr; } bool operator==( const sentinel_iterator & rhs ) const { return m_ptr == rhs.m_ptr; } bool operator!=( const sentinel_iterator & rhs ) const { return m_ptr != rhs.m_ptr; } private: T * m_ptr; // 0 == the end iterator //static const T m_sentinel = Sentinel(); }; struct s_val { operator int () const { return -1; } }; int main() { // test cases using default sentinel sentinel_iterator<char> it( "abc" ); assert( it != sentinel_iterator<char>() ); assert( *it == 'a' ); assert( *++it == 'b' ); assert( *++it == 'c' ); assert( ++it == sentinel_iterator<char>() ); sentinel_iterator<char> it2( "" ); assert( it2 == sentinel_iterator<char>() ); sentinel_iterator<char> it3( 0 ); assert( it3 == sentinel_iterator<char>() ); // test cases using non-default sentinel typedef sentinel_iterator<unsigned, s_val> my_iter_type; unsigned data[] = { 0, 1, -1 }; my_iter_type my_it( data ); assert( my_it != my_iter_type() ); assert( *my_it == 0 ); assert( *++my_it == 1 ); assert( ++my_it == my_iter_type() ); unsigned my_sentinel = -1; my_iter_type my_it2( &my_sentinel ); assert( my_it2 == my_iter_type() ); my_iter_type my_it3( 0 ); assert( my_it3 == my_iter_type() ); return 0; }
On Wed, May 13, 2009 at 12:38 PM, Simonson, Lucanus J <lucanus.j.simonson@intel.com> wrote:
Thorsten Ottosen wrote:
joaquin@tid.es skrev:
Beman Dawes escribió:
Attached is proof-of-concept code for a sentinel iterator adapter. It turns a pointer to sentinel terminated sequence, such as a C-style string, into a forward iterator with a conforming end iterator.
Having Sentinel specified as a non-type template parameter greatly reduces the category of types this can work with. I'd replace it with some SentinelFactory policy or something.
That is not a bad idea, although it would really be good if the basic case can stay as optimaized as currently (having a static member). I guess having a static member is not an option for a general policy, thus giving us the usual iterator problem of double storage.
I don't understand the rationale for m_sentinel. Couldn't the code refer to Sentinel directly as a compile time constant as opposed to a static member variable?
The concern is that Sentinel() isn't a compile time constant. It is a potentially expensive call to a constructor. An optimizer may be smart enough to resolve Sentinel() at compile time, and generate maximally efficient code accordingly, but there is no guarantee of that. --Beman
Attached is proof-of-concept code for a sentinel iterator adapter. It turns a pointer to sentinel terminated sequence, such as a C-style string, into a forward iterator with a conforming end iterator.
This is more efficient than doing a separate sequence traversal just to find the end.
No, it is not. :-) PS: #include <boost/functional/hash.hpp> #include <algorithm> #include <iostream> #include <windows.h> static size_t test_strlen( char const * s ); static size_t test_sentinel( char const * s ); int main() { int const N = 10000000; DWORD t1 = timeGetTime(); size_t m1 = 0; for( int i = 0; i < N; ++i ) { m1 += test_strlen( "This is a test." ); } DWORD t2 = timeGetTime(); size_t m2 = 0; for( int i = 0; i < N; ++i ) { m2 += test_sentinel( "This is a test." ); } DWORD t3 = timeGetTime(); std::cout << t2 - t1 << " (" << m1 << "); " << t3 - t2 << " (" << m2 << ")\n"; } static size_t test_strlen( char const * s ) { return boost::hash_range( s, s + strlen( s ) ); } // sentinel terminated sequence iterator proof-of-concept // Copyright Beman Dawes, 2009 #include <cassert> // sentinel terminated sequence iterator template < class T, T Sentinel = T() > class sentinel_iterator { public: sentinel_iterator() : m_ptr(0) {} // construct end iterator sentinel_iterator( T * p ) : m_ptr( (p && *p != m_sentinel) ? p : 0 ) {} sentinel_iterator & operator++() { assert(m_ptr); if ( *++m_ptr == m_sentinel ) m_ptr = 0; return *this; } T & operator*() const { assert(m_ptr); return *m_ptr; } bool operator==( const sentinel_iterator & rhs ) const { return m_ptr == rhs.m_ptr; } bool operator!=( const sentinel_iterator & rhs ) const { return m_ptr != rhs.m_ptr; } private: T * m_ptr; // 0 == the end iterator static const T m_sentinel = Sentinel; }; static size_t test_sentinel( char const * s ) { return boost::hash_range( sentinel_iterator< char const >( s ), sentinel_iterator< char const >() ); }
Peter Dimov skrev:
Attached is proof-of-concept code for a sentinel iterator adapter. It turns a pointer to sentinel terminated sequence, such as a C-style string, into a forward iterator with a conforming end iterator.
This is more efficient than doing a separate sequence traversal just to find the end.
No, it is not. :-)
In Boost.StringAlgo the end iterator is usually computed by a call to strlen(). I suspect for algorithms that do not need a. random access iterators b. to discover the whole range before terminating then a sentinel range could be more efficient. Of course, a random access range might be subject to other optimizations that are lost when the iterator cetagory is made more general. -Thorsten
On Wed, May 13, 2009 at 5:19 PM, Peter Dimov <pdimov@pdimov.com> wrote:
Attached is proof-of-concept code for a sentinel iterator adapter. It turns a pointer to sentinel terminated sequence, such as a C-style string, into a forward iterator with a conforming end iterator.
This is more efficient than doing a separate sequence traversal just to find the end.
No, it is not. :-)
PS:
#include <boost/functional/hash.hpp> #include <algorithm> #include <iostream> #include <windows.h>
static size_t test_strlen( char const * s ); static size_t test_sentinel( char const * s );
int main() { int const N = 10000000;
DWORD t1 = timeGetTime();
size_t m1 = 0;
for( int i = 0; i < N; ++i ) { m1 += test_strlen( "This is a test." ); }
Are you sure the compiler is not computing the len at compile time? -- gpd
Giovanni Piero Deretta: ...
for( int i = 0; i < N; ++i ) { m1 += test_strlen( "This is a test." ); }
Are you sure the compiler is not computing the len at compile time?
Good point. Yes, it actually was computing it at compile time. When I changed the test to use a literal in another TU, the sentinel iterator was indeed more efficient: 953 (3577225856); 703 (3577225856)
Interesting, I wrote a modified version where you can enter the string length and the sentinel version is consistently slower (using gcc-4.4.0 with -O3). // sentinel terminated sequence iterator proof-of-concept // Copyright Beman Dawes, 2009 #include <cassert> #include <cstring> #include <iostream> #include <boost/functional/hash.hpp> #include <boost/timer.hpp> // sentinel terminated sequence iterator template < class T, T Sentinel = T() > class sentinel_iterator { public: sentinel_iterator() : m_ptr(0) {} // construct end iterator sentinel_iterator( T * p ) : m_ptr( (p && *p != m_sentinel) ? p : 0 ) {} sentinel_iterator & operator++() { assert(m_ptr); if ( *++m_ptr == m_sentinel ) m_ptr = 0; return *this; } T & operator*() const { assert(m_ptr); return *m_ptr; } bool operator==( const sentinel_iterator & rhs ) const { return m_ptr == rhs.m_ptr; } bool operator!=( const sentinel_iterator & rhs ) const { return m_ptr != rhs.m_ptr; } private: T * m_ptr; // 0 == the end iterator static const T m_sentinel = Sentinel; }; static size_t test_strlen( const char* s ) { return boost::hash_range( s, s + strlen( s ) ); } static size_t test_sentinel( const char* s ) { return boost::hash_range( sentinel_iterator< const char >( s ), sentinel_iterator< const char >() ); } int main() { const unsigned N = 1000000; std::cout << "enter text length: "; unsigned len; std::cin >> len; char* text = new char[len]; for (unsigned i = 0; i < len; ++i) text[i] = '4'; text[len] = '\0'; std::size_t m1 = 0; std::size_t m2 = 0; { boost::timer t; for( unsigned i = 0; i < N; ++i ) { m1 += test_strlen( text ); } std::cout << "strlen: " << t.elapsed() << " " << m1 << std::endl; } { boost::timer t; for( unsigned i = 0; i < N; ++i ) { m2 += test_sentinel( text ); } std::cout << "sentinel: " << t.elapsed() << " " << m2 << std::endl; } delete[] text; return 0; }
AMDG Kevin Sopp wrote:
Interesting, I wrote a modified version where you can enter the string length and the sentinel version is consistently slower (using gcc-4.4.0 with -O3).
{ boost::timer t; for( unsigned i = 0; i < N; ++i ) { m1 += test_strlen( text ); }
std::cout << "strlen: " << t.elapsed() << " " << m1 << std::endl; }
I'm not absolutely sure about this, but from the assembler it looks like the call to strlen is being pulled out of the loop. movl 24(%esp), %eax movb $0, (%eax,%edx) call _clock movl %eax, 20(%esp) xorl %eax, %eax orl $-1, %ecx movl 24(%esp), %edi repne scasb // This looks like strlen notl %ecx movl 24(%esp), %eax leal -1(%eax,%ecx), %esi xorl %edi, %edi movl $0, 28(%esp) .p2align 2,,3 L11: // and the loop is here cmpl %esi, 24(%esp) je L32 movl 24(%esp), %edx xorl %eax, %eax .p2align 2,,3 L10: movsbl (%edx),%ebx movl %eax, %ecx sall $6, %ecx leal -1640531527(%ebx,%ecx), %ebx movl %eax, %ecx shrl $2, %ecx leal (%ebx,%ecx), %ecx xorl %ecx, %eax incl %edx cmpl %esi, %edx jne L10 addl %eax, 28(%esp) incl %edi cmpl $1000000, %edi jne L11 In Christ, Steven Watanabe
On Wed, May 13, 2009 at 6:50 PM, Steven Watanabe <watanabesj@gmail.com> wrote:
I'm not absolutely sure about this, but from the assembler it looks like the call to strlen is being pulled out of the loop.
You're right, I added __attribute__((noinline)) to the test_strlen and test_sentinel functions and I also added -DNDEBUG this time around now I get the following times: enter text length: 8 strlen: 0.05 2468358720 sentinel: 0.04 2468358720 enter text length: 512 strlen: 2.46 3054888576 sentinel: 2.17 3054888576 enter text length: 8096 strlen: 38.58 2775800256 sentinel: 34.09 2775800256 which shows that the sentinel version is indeed faster. It's comforting to know that programmer intuition works after all!
Attached is proof-of-concept code for a sentinel iterator adapter. It turns a pointer to sentinel terminated sequence, such as a C-style string, into a forward iterator with a conforming end iterator.
This is more efficient than doing a separate sequence traversal just to find the end.
I'm a little surprised that Boost doesn't already have such an iterator adapter. Or am I just missing it?
Would a production version of this iterator adapter be a worthwhile addition to Boost.Iterators?
Any other comments appreciated,
Yes !! Could be made even more generic as Joaquin noted, but other than that it would make a very useful addition. John.
Beman Dawes wrote:
Attached is proof-of-concept code for a sentinel iterator adapter.
This is not a true iterator adapter, since it can only adapt an iterator of pointer type, not just any iterator.
Would a production version of this iterator adapter be a worthwhile addition to Boost.Iterators?
I suggest turning it into a true iterator adapter that would apply a predicate on each element to tell whether it is the end.
AMDG Mathias Gaunard wrote:
Beman Dawes wrote:
Attached is proof-of-concept code for a sentinel iterator adapter.
This is not a true iterator adapter, since it can only adapt an iterator of pointer type, not just any iterator.
Would a production version of this iterator adapter be a worthwhile addition to Boost.Iterators?
I suggest turning it into a true iterator adapter that would apply a predicate on each element to tell whether it is the end.
How do you plan to represent the end without adding extra overhead for comparisons? In Christ, Steven Watanabe
Steven Watanabe wrote:
How do you plan to represent the end without adding extra overhead for comparisons?
In the general case, you would need to use a boolean since you cannot just set the iterator to some magic value such as null. The case of pointers could still be specialized. The efficiency overhead could eventually be avoided by relaxing the requirement that both the begin and the end iterator should have the same type, as was suggested by David Abrahams in this message: http://article.gmane.org/gmane.comp.lib.boost.devel/179289
On Wed, May 13, 2009 at 5:30 PM, Mathias Gaunard <mathias.gaunard@ens-lyon.org> wrote:
Beman Dawes wrote:
Attached is proof-of-concept code for a sentinel iterator adapter.
This is not a true iterator adapter, since it can only adapt an iterator of pointer type, not just any iterator.
Would a production version of this iterator adapter be a worthwhile addition to Boost.Iterators?
I suggest turning it into a true iterator adapter that would apply a predicate on each element to tell whether it is the end.
Yes, that's one of the approaches I considered. One issue with that approach is that optimizers can't always see into function objects. Although C++0x Lambda will fix that, at least for some compilers, the predicate adds a bit of complexity to an otherwise very simple specification. It may be worthwhile to have several sentinel iterators. The dust needs to settle a bit, then we can sort out what is actually worth doing. --Beman
Beman Dawes wrote:
Yes, that's one of the approaches I considered.
One issue with that approach is that optimizers can't always see into function objects. Although C++0x Lambda will fix that, at least for some compilers, the predicate adds a bit of complexity to an otherwise very simple specification.
That's how filter_iterator and transform_iterator, the adapters of Boost.Iterator, work. (as well as the derived Boost.RangeEx adapters that were accepted recently) I suppose it would be best to keep that design. I fail to see your point about function objects though. Maybe you're actually thinking of using type erasure? That would be quite a bad idea. The adapter should be templated on both the iterator type and the function object type. This has generated code without overhead for years on all decent compilers I'm aware of. Compilers have no problem inlining a call to a function object. Thankfully, since the whole algorithms part of the standard library depends on that...
participants (10)
-
Beman Dawes -
Giovanni Piero Deretta -
joaquin＠tid.es -
John Maddock -
Kevin Sopp -
Mathias Gaunard -
Peter Dimov -
Simonson, Lucanus J -
Steven Watanabe -
Thorsten Ottosen