Performance issues when using iterators?

Question

I have a function which takes in a list of characters and generates the next lexicographic permutation. For fun, I tried generalizing the code to use iterators, as well as being able to generate permutations of more different types.

template<typename ITER>
bool nextPermutation(ITER start, ITER end, std::random_access_iterator_tag)
{
    for(ITER i = end-1; i != start; --i)
    {
        if(*(i-1) < *i)
        {
            // found where can be swapped
            for(ITER j = end-1; j != (i-1); --j)
            {
                if(*(i-1) < *j)
                {
                    // found what to swap with
                    auto temp = *j;
                    *j = *(i-1);
                    *(i-1) = temp;
                    // put everything from i on into "sorted" order by reversing
                    for(ITER k = end-1; k > i; --k,++i)
                    {
                        temp = *k;
                        *k = *i;
                        *i = temp;
                    }
                    return true;
                }
            }
        }
    }
    return false;
}

However, I'm running into issues where when I don't use raw pointers the performance of the code is significantly slower. Here's my test rig:

template<typename ITER>
bool nextPermutation(ITER start, ITER end, std::random_access_iterator_tag);

template<typename ITER>
bool nextPermutation(ITER start, ITER end)
{
    return nextPermutation(start, end, std::iterator_traits<ITER>::iterator_category());
}

#define USE_VECTOR

int main(void)
{
    bool hasNext = true;
#ifdef USE_VECTOR
    std::vector<char> c;
    for(char i = '0'; i <= '9'; ++i)
    {
        c.push_back(i);
    }
    for(size_t i = 0; i < 999999 && hasNext; ++i)
    {
        hasNext = nextPermutation(c.begin(), c.end());
    }
#else
    char c[] = "0123456789";
    size_t LENGTH = 10;
    for(size_t i = 0; i < 999999 && hasNext; ++i)
    {
        hasNext = nextPermutation(c, c+LENGTH);
    }
#endif
    std::cout << "done" << std::endl;
    std::cin.ignore();
    return 0;
}

When USE_VECTOR is defined, it takes ~20 seconds to run this test rig. When I undefine it, the codes runs in less than a second (I didn't write any timing code, but it's sufficient to say there's a very significant difference in performance).

Now my question is where am I taking such a huge performance hit which would affect using an iterator (std::string iterator, std::vector iterator, etc.) vs. a raw pointer?

Well, are you turning on optimizations? Also, why not use things like `std::swap`? — GManNickG, Apr 15 '11 at 22:32
mainly laziness. I wrote the code originally using `char*`, and when I came back I just modified the function definition to be able to take iterators. edit: oh duh, I forgot Visual studio doesn't optimize debug builds by default. durr :( — helloworld922, Apr 15 '11 at 22:36
Well, it would be cruel not to mention [`std::next_permutation`](http://www.cplusplus.com/reference/algorithm/next_permutation/)… Reading the standard library's implementation can be educational even if you want to do it yourself. — Potatoswatter, Apr 15 '11 at 22:51
yeah, but I wrote this from a learning standpoint (plus I'm one of those people who finds algorithms fascinating). I'm still slightly uncomfortable working with pointers, more so when stuff from the standard library gets mixed in, so I thought this would be a nice exercise. — helloworld922, Apr 15 '11 at 22:52
If you're into algorithms dealing with permutations and combinations, here's more fun for you: http://home.roadrunner.com/~hinnant/combinations.html Read just the spec, not the source code and then try to implement it. But the source code is there too. — Howard Hinnant, Apr 15 '11 at 23:11

score 8 · Accepted Answer · answered Apr 15 '11 at 22:51

8

Without optimizations, due to heavy iterator debugging (_ITERATOR_DEBUG_LEVEL is defaulted to 2 in debug mode, aka full debugging), the code is also slow on my machine.
With /02 however, the iterator debugging is disabled completely and the code executes in full before the console window even shows up.
Here you got a nice example of debugging making things slower but safer. :)

answered Apr 15 '11 at 22:51

Xeo

129,499
52
291
397

And in general the other advantage of things being slower in debug, of course, is that you're less likely to hit any of those nasty old race conditions that plague you in release mode. Much safer ;-) – Steve Jessop Apr 15 '11 at 23:29
@Steve: I'm so glad I don't have to code multithreaded apps yet. ;) – Xeo Apr 15 '11 at 23:30

score 1 · Answer 2 · answered Apr 15 '11 at 23:14

On my box these are the timings, from taking the above timing, removing the cin.ignore(), and benchmarked using:

$ g++-4.6 -O4 -DUSE_VECTOR -std=gnu++0x t.cpp -o t
$ time for a in $(seq 1 1000); do ./t; done > /dev/null

real 0m10.145s user 0m7.204s sys 0m1.088s

$ g++-4.6 -O4 -std=gnu++0x t.cpp -o t
$ time for a in $(seq 1 1000); do ./t; done > /dev/null

real 0m7.693s user 0m3.280s sys 0m0.984s

** No shocking difference there, if you ask me **

Now for the punch:

$ g++-4.6 -O0 -std=gnu++0x t.cpp -o t
$ time for a in $(seq 1 1000); do ./t; done > /dev/null

real 0m29.540s user 0m27.294s sys 0m0.976s

Performance issues when using iterators?

2 Answers2

Linked