How to speed up my object oriented Iterator class?

Question

With help in the question Fast and flexible iterator for abstract class I created an abstract GridIterator for an abstract class GridData. Now I am able to use any concrete subclass of GridIterator to iterate through any concrete subclass of GridData.

However, during testing I found out that the virtual operator++ and virtual operator* operators become real bottlenecks of my algorithms. I am wondering if there is anything I can do to speed it up. Because of the abstraction, inlining probably won't work for me?

I'd like to provide a const Iterator as well. I am not sure how to make this work with the current class design. Referring to my original question ( Fast and flexible iterator for abstract class ), can I just create a ConstGridIterator as subclass from a STL forward iterator with const T instead of T? Or do I have to implement a const version of every single iterator class (the GridIterator and baseImpl)?

Answer 1

Do as the STL and don't use virtual methods in an iterator or containers. Most compilers, when asked to optimize, are able to optimize out most STL iterators to the point they are completely bypassed and they don't even exist in the object file. For example a *(vector<T>.begin()+5) could be optimized to vector<T>.__underlying_array[5] even if vector<T>::iterator is a complex class with constructors, destructors and complex operator redefinitions.

Having a virtual method call anywhere in the call stack of operator++,begin(),end() oroperator !=() prevent the compiler to optimize this correctly because the method could be redefined by anything. virtual methods don't only have a small runtime overhead, they make the code unoptimizable by making it more modular.

If you want performance, consider using templates instead of inheritance, or tweak your compiler, saying that nobody inherit this class. This may conflict with your current design, but you need to choose two priorities among those three : performance, modularity and cost.