Faster range for loop (C++11)

Question

I have some code to iterate over a (multivariate) numeric range:

#include <array>
#include <limits>
#include <iostream>
#include <iterator>

template <int N>
class NumericRange : public std::iterator<double, std::input_iterator_tag>
{
public:
  NumericRange() {
    _lower.fill(std::numeric_limits<double>::quiet_NaN());
    _upper.fill(std::numeric_limits<double>::quiet_NaN());
    _delta.fill(std::numeric_limits<double>::quiet_NaN());
  }
  NumericRange(const std::array<double, N> & lower, const std::array<double, N> & upper, const std::array<double, N> & delta):
    _lower(lower), _upper(upper), _delta(delta) {
    _state.fill(std::numeric_limits<double>::quiet_NaN());
  }

  const std::array<double, N> & get_state() const {
    return _state;
  }

  NumericRange<N> begin() const {
    NumericRange<N> result = *this;
    result.start();
    return result;
  }

  NumericRange<N> end() const {
    NumericRange<N> result = *this;
    result._state = _upper;
    return result;
  }

  bool operator !=(const NumericRange<N> & rhs) const {
    return in_range();
    //    return ! (*this == rhs);
  }

  bool operator ==(const NumericRange<N> & rhs) const {
    return _state == rhs._state && _lower == rhs._lower && _upper == rhs._upper && _delta == rhs._delta;
  }

  const NumericRange<N> & operator ++() {
    advance();
    if ( ! in_range() )
      _state = _upper;
    return *this;
  }

  const std::array<double, N> & operator *() const {
    return _state;
  }

  void start() {
    _state = _lower;
  }

  bool in_range(int index_to_advance = N-1) const {
    return ( _state[ index_to_advance ] - _upper[ index_to_advance ] ) < _delta[ index_to_advance ];
  }

  void advance(int index_to_advance = 0) {
    _state[ index_to_advance ] += _delta[ index_to_advance ];
    if ( ! in_range(index_to_advance) ) {
      if (index_to_advance < N-1) {
    // restart index_to_advance
    _state[index_to_advance] = _lower[index_to_advance];

    // carry
    ++index_to_advance;
    advance(index_to_advance);
      }
    }
  }
private:
  std::array<double, N> _lower, _upper, _delta, _state;
};

int main() {
   std::array<double, 7> lower{{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0}};
   std::array<double, 7> upper{{1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0}};
   std::array<double, 7> delta{{0.03, 0.06, 0.03, 0.06, 0.03, 0.06, 0.03}};

  NumericRange<7> nr(lower, upper, delta);
  int c = 0;    
  for (nr.start(); nr.in_range(); nr.advance()) {
    ++c;
  }
  std::cout << "took " << c << " steps" << std::endl;    
  return 0;
}

Compiling with g++ -std=c++11 -O3 (or -std=c++0x with gcc < 4.7) runs in around 13.8 seconds on my computer.

If I change the main function to use a range-based for loop:

  for (const std::array<double, 7> & arr : nr) {
    ++c;
  }

the runtime increases to 29.8 seconds. Coincidentally, this ~30 seconds runtime is almost the same as the runtime of the original when using std::vector<double> instead of std::array<double, N>, leading me to believe the compiler cannot unroll the code produced by the range-based for loop.

Is there a way to have the speed of the original and still use range-based for loops?

---

What I've tried:

I can get the desired speed with a range-based for loop by changing two member functions in NumericRange:

bool operator !=(const NumericRange<N> & rhs) const {
  return in_range();
  //    return ! (*this == rhs);
}

const NumericRange<N> & operator ++() {
  advance();
  //    if ( ! in_range() )
  //      _state = _upper;
  return *this;
}

However, this code feels poorly designed because the != operator doesn't work as expected Normally for numeric operations, I use < to terminate a loop rather than ==. I thought of finding the first out-of-range value, but to do so analytically may not give an exact answer due to numerical error.

How can you force the != operator to behave similarly to a < without misleading others who will see my code? I'd simply make the begin() and end() functions private, but they need to be public for the range-based for loop.

Thanks a lot for your help.

Answer 1

The problem, as far as I am concerned, is that you are not using the range-for construct appropriately.

---

Let us take a step back:

void foo(std::vector<int> const& v) {
    for (int i: v) {
    }
}

Note how the range-for iterates over the vector to extract integers.

---

For some reasons you chose not to implement iterators to bridge from begin to end, but instead re-use a copy of what you are iterating over, even though it varies only very slightly, and you are doing a ton of extra-work (in the copy and checks)...

Note: std::iterator<double, ...> means that operator* should return a double&.

If you want to use the new idiom, you will have to conform to its expectations.

The expectation is that you iterate with iterators and not by copying the original object (slightly modified) over and over. This is the C++ idiom.

It means that you will need to cut your object in half: pull off everything that is immutable during the iteration in the object to be iterated over and what is modified in the iterator.

From what I can see:

• _lower, _upper and _delta are fixed
• _state is the iteration variable

Therefore, you would have:

template <typename> class NumericRangeIterator

template <unsigned N> // makes no sense having a negative here
class NumericRange {
public:
    template <typename> friend class NumericRangeIterator;

    typedef NumericRangeIterator<NumericRange> iterator;
    typedef NumericRangeIterator<NumericRange const> const_iterator;

    static unsigned const Size = N;

    // ... constructors

    iterator begin(); // to be defined after NumericRangeIterator
    iterator end();

    const_iterator begin() const;
    const_iterator end() const;

private:
    std::array<double, N> _lower, _upper, _delta;
}; // class NumericRange

template <typename T>
class NumericRangeIterator: public
    std::iterator< std::array<double, T::Size>,
                   std::forward_iterator_tag >
{
public:
    template <unsigned> friend class NumericRange;

    NumericRangeIterator(): _range(0), _state() {}

    NumericRangeIterator& operator++() {
        this->advance();
        return *this;
    }

    NumericRangeIterator operator++(int) {
        NumericRangeIterator tmp(*this);
        ++*this;
        return tmp;
    }

    std::array<double, T::Size> const& operator*() const {
        return _state;
    }

    std::array<double, T::Size> const* operator->() const {
        return _state;
    }

    bool operator==(NumericRangeIterator const& other) const {
        return _state != other._state;
    }

    bool operator!=(NumericRangeIterator const& other) const {
        return !(*this == other);
    }


private:
    NumericRangeIterator(T& t, std::array<double, T::Size> s):
        _range(&t), _state(s) {}

    void advance(unsigned index = T::Size - 1);  // as you did
    void in_range(unsigned index = T::Size - 1); // as you did

    T* _range;
    std::array<double, T::Size> _state;
}; // class NumericRangeIterator


template <unsigned N>
auto NumericRange<N>::begin() -> typename NumericRange<N>::iterator {
    return iterator(*this, _lower);
}

template <unsigned N>
auto NumericRange<N>::end() -> typename NumericRange<N>::iterator {
    return iterator(*this, _upper);
}

And with all this setup, you can write:

for (auto const& state: nr) {
}

Where auto will be deduced to be std::array<double, nr::Size>.

Note: not sure the iterator are useful, maybe only the const_iterator since it's a false iteration in a way; you cannot reach into the range object to modify it through the iterator.

EDIT: operator== is too slow, how to get it better ?

I propose to cheat.

1/ Modify the constructors of the iterator

NumericRangeIterator(): _range(0), _state() {}               // sentinel value
NumericRangeIterator(T& t): _range(&t), _state(t._lower) {}

2/ Tweak the iteration to create the new "sentinel" value at the end

void advance() {
    // ...

    if (not this->in_range()) {        // getting out of the iteration ?
       *this = NumericRangeIterator(); // then use the sentinel value
    }
}

3/ Change the begin and end definition accordingly

template <unsigned N>
auto NumericRange<N>::begin() -> typename NumericRange<N>::iterator {
    return iterator(*this);
}

template <unsigned N>
auto NumericRange<N>::end() -> typename NumericRange<N>::iterator {
    return iterator();
}

4/ Make == more equal by using the sentinel

bool operator==(NumericRangeIterator const& other) const {
    return _range == other._range and _state == other._state;
}

Now, all along iteration the == is short-circuited because one of the _range is null and the other is not. Only at the last call will the comparison of the two _state attributes actually occur.