std :: vector :: clear () занимает больше времени после рефакторинга кода

Question

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

// Point 0
ptrlistVector.clear();

// Point 1
ptrlistVector.resize(50);
const size_t s = ptrlistVector.size();

// Point 2
for (ObjectList::iterator j = objList.begin(); j != objList.end(); ++j)
{
    for (UINT i = 0; i < s; ++i) 
    {
        ptrlistVector[i].push_back(&(*j)); 
    }
}
// Point 3

На самом деле в строке "push_back" есть более сложный код - я помещаю разные значения в список.Значения зависят от некоторого условия.

Декларация s и определения:

typedef std::list<void*> ObjectPtrList;
typedef std::vector<ObjectPtrList> PtrListVector;
typedef std::list<std::string> ObjectList;

ObjectList objList;
PtrListVector ptrlistVector;

Я измерял время между точками, в средних числах точка 1-0 занимает 0,02 секунды, а точка 32 занимает 0,05 сек.Я попытался реорганизовать циклы и обнаружил странное поведение.Я заменил вышеприведенные циклы на следующие:

for (UINT i = 0; i < s; ++i)
{
    for (ObjectList::iterator j = objList.begin(); j != objList.end(); ++j)
    {
        ptrlistVector[i].push_back(&(*j)); 
    }
}

После этого время было изменено.Точка 3-2 занимает 0,035 с, но вызов clear () (точка 1-0) теперь занимает 0,45 (!!!), что намного больше, чем в предыдущий раз.

Я использую MSVC 10.0, результаты примерно одинаковы как в режиме отладки, так и в режиме выпуска.В режиме Release разница во времени не так существенна, но в любом случае время больше для секунды.

Может кто-нибудь объяснить, почему вызов clear () занимает гораздо больше времени после того, как я изменил циклы?

Код ниже - консольное приложение, которое я использовал для своих тестов производительности.

#include "stdafx.h"
#include <windows.h>
#include <vector>
#include <list>
#include <cstdio>
#include <cassert>
#include <string>

int _tmain(int argc, _TCHAR* argv[])
{
    typedef std::list<void*> ObjectPtrList;
    typedef std::vector<ObjectPtrList> PtrListVector;
    typedef std::list<std::string> ObjectList;

    ObjectList objList;
    objList.insert(objList.begin(), 500, std::string());

    PtrListVector ptrlistVector;

    LARGE_INTEGER __counters[10];
    double __totals[10] = { 0 };
    UINT __counter = 0;
    BOOL bRes;

    LARGE_INTEGER __freq;
    bRes = QueryPerformanceFrequency(&__freq);
    assert(bRes);

    for (int k = 0; k < 500; ++k)
    {
        // Point 0
        bRes = QueryPerformanceCounter(&__counters[0]);
        ptrlistVector.clear();

        // Point 1
        bRes = QueryPerformanceCounter(&__counters[1]);
        ptrlistVector.resize(50);
        const size_t s = ptrlistVector.size();

        // Point 2
        bRes = QueryPerformanceCounter(&__counters[2]);
        /*
        // original
        for (ObjectList::iterator j = objList.begin(); j != objList.end(); ++j)
        {
            for (UINT i = 0; i < s; ++i) 
            {
                ptrlistVector[i].push_back(&(*j)); 
            }
        }
        /*/
        for (UINT i = 0; i < s; ++i) // refactored
        {
            for (ObjectList::iterator j = objList.begin(); j != objList.end(); ++j)
            {
                ptrlistVector[i].push_back(&(*j)); 
            }
        }
        //*/

        // Point 3  
        bRes = QueryPerformanceCounter(&__counters[3]);
        __counter += 1;
        __totals[1] += 1.0 * (__counters[1].QuadPart - __counters[0].QuadPart) / __freq.QuadPart;
        __totals[2] += 1.0 * (__counters[2].QuadPart - __counters[1].QuadPart) / __freq.QuadPart;
        __totals[3] += 1.0 * (__counters[3].QuadPart - __counters[2].QuadPart) / __freq.QuadPart;
        __totals[4] += 1.0 * (__counters[3].QuadPart - __counters[0].QuadPart) / __freq.QuadPart;
        printf("%s: %.4f  %.4f  %.4f = %.4f\n", 
            __FUNCTION__, 
            __totals[1]/__counter, 
            __totals[2]/__counter, 
            __totals[3]/__counter, 
            __totals[4]/__counter);
    }
    return 0;
}

Answer 1

Я хочу предвосхитить этот ответ с отказом от ответственности - это предположение, поскольку я не выполнил код в вопросе и не рассмотрел фактическую реализацию библиотеки.Но я думаю, что это обрисовывает в общих чертах возможное объяснение любой статистически значимой разницы во времени, описанном в вопросе.Но имейте в виду, что является гипотезой на данный момент.

---

Разница во времени, необходимая для очистки вектора списков, может быть связана с тем, как кучаиспользуется и работа, которая может выполняться, когда куча обрабатывает элементы списка, которые освобождаются, когда списки уничтожаются.Я думаю, что может быть больше работы в куче, когда элементы списка освобождаются со вторым типом цикла.Я могу только догадываться (я не прошел через код библиотеки).

В первом стиле цикла каждый список получает один элемент, добавляемый за каждую итерацию цикла;другими словами, итерация цикла 0 помещает один элемент в каждый список, затем итерация цикла 1 добавляет другой элемент в каждый список и т. д.

Во втором примере (где операция clear() занимает больше времени) каждый список создается отдельно;другими словами, список в ptrlistVector[0] заполняется, затем ptrlistVector[1] заполняется и т. д.

Я бы предположил, что для стиля первого цикла каждый элемент в определенном списке равен не подряд (в адресном пространстве) другим элементам в списке.Это произошло бы потому, что во время между любыми двумя push_back() операциями в определенном списке происходило 50 других выделений для добавления элементов в другие списки.

Однако я бы предположил, что во втором стиле циклаэлементы в определенном списке более или менее последовательны, так как это порядок, в котором произошли распределения.

Теперь давайте подумаем, что это может означать, когда список уничтожается (как это произойдет, когда вектор, содержащий списки, будет очищен).Для списка, в котором элементы расположены последовательно в адресном пространстве, куча может тратить кучу времени на объединение этих смежных свободных блоков.Но когда список, имеющий группу элементов, которые не являются смежными, освобождает свои элементы, освобожденные блоки памяти не являются смежными, поэтому объединение не может произойти.До тех пор, пока мы не доберемся до последних (или последних нескольких) списков, куча начнет видеть соседние свободные блоки памяти, которые могут быть объединены.