Проблемы с производительностью при использовании итераторов?

Question

У меня есть функция, которая берет список символов и генерирует следующую лексикографическую перестановку. Ради интереса я попытался обобщить код для использования итераторов, а также для возможности генерировать перестановки более разных типов.

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;
}

Однако у меня возникают проблемы, когда без использования необработанных указателей производительность кода значительно снижается. Вот мой испытательный стенд:

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;
}

Когда определено USE_VECTOR, запуск этой испытательной установки занимает ~ 20 секунд. Когда я определяю его, коды запускаются менее чем за секунду (я не писал никакого временного кода, но достаточно сказать, что есть очень существенная разница в производительности).

Теперь мой вопрос: где я получаю такой огромный удар по производительности, который может повлиять на использование итератора (итератор std :: string, итератор std :: vector и т. Д.) И необработанного указателя?

Answer 1

Без оптимизации из-за интенсивной отладки итератора (_ITERATOR_DEBUG_LEVEL по умолчанию равен 2 в режиме отладки, или полной отладке), код на моей машине также работает медленно.
С /02 однако отладка итератораполностью отключен, и код выполняется полностью еще до того, как открывается окно консоли.
Здесь вы видите хороший пример отладки, делающей вещи медленнее, но безопаснее.:)

Answer 2

На моем боксе это время, от взятия вышеупомянутого времени, удаления cin.ignore() и сравнения с помощью:

$ 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

реальный 0m10.145s пользователь 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

реальный 0m7.693s пользователь 0m3.280s sys 0m0.984s

** Нет шокирующей разницы, если вы спросите меня **

Теперь для удара:

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

реальный 0m29.540s пользователь 0m27.294s sys 0m0.976s