Дядя Дима (ddima) wrote,
Дядя Дима
ddima

Category:

list vs vector и немного про синтетические примеры

Недавно в ICQ развершулась довольно жаркая дискуссия про сравнение производительности и удобства списков и векторов для выполнения разных операций. Результат этой переписки и интересный листинг с разрешения программиста выкладываю сюда.

Собственно сама задача, за которую мы зацепились, формулировалась просто.
Имеется N объектов. M объектов из этого списка находится в состоянии "Активно" (остальные, соответственно, в состоянии "Неактивно"). Задача - выполнить определенные действия на всех активных объектах.

Можно предложить 2 основных варианта реализации вопроса:

1. У каждого объекта есть флаг IsActive(). Объекты помещены в массив или вектор. На фрейме выполняется пробежка по массиву, для активных объектов выполняются какие-то действия.
2. Существует 2 списка объектов - ActiveList и InactiveList. Активируемые объекты перемещаются из списка InactiveList в ActiveList. Пробежка ведется по ActiveList.

Результаты оказались довольно необычные. Настолько, что решил поделиться с коллегами.
Для того, чтобы было проще анализивать результаты, добавил некоторое количество кода к тестовой программе.

Во первых, сама реализация проверяемого класса. Класс Object имеет методы SetActive() и IsActive() и заглушечную процедуру, которая занимается несложным рассчетом.

// Size of data in each Object
const int OBJECT_DATA_SIZE = 128;

// Base test object with inactive and active states
class Object {
public:
    // ctor. object is inactive by default
    Object() :
    bActive(false) {
        memset(data, 1, sizeof(data));
    }
    // check is object active
    inline bool IsActive() const { return bActive; }
    // set object activity
    inline void SetActive() { bActive = true; }
    // do stub execution for active object
    bool CheckObject() const {
        unsigned long acc = 0;

        _ASSERT(bActive);
        for(int i=0; i<OBJECT_DATA_SIZE; ++i)
            acc+= data[i];
        return acc > 512;
    };

private:
    // activity flag
    bool bActive;
    // stub object data
    unsigned long data[OBJECT_DATA_SIZE];
};
_Winnie C++ Colorizer


К этому делу имеется инициализация вектора объектов и списка объектов

// vector of all objects (size is TOTAL_OBJECTS_NUM, ACTIVE_OBJECTS_NUM objects are active)
static std::vector<Object> v_objects;
// list of all objects (size is ACTIVE_OBJECTS_NUM, all objects are active)
static std::list<Object*> l_objects;


static void InitObjectsV(const CommandArguments& arg)
{
    v_objects.reserve(arg.total_object_count);
    for(int i=0;i<arg.total_object_count;++i) {
        Object trigger;
        v_objects.push_back(trigger);
    };
    for (int i=0; i<arg.active_object_count; ++i)
        v_objects[2*i+1].SetActive();
}

static void InitObjectsL(const CommandArguments& arg)
{
    for(int i=0;i<arg.active_object_count;++i) {
        Object * trigger = new Object();

        if (arg.list_delta_size > 0)
            new unsigned int[1 + (rand() % arg.list_delta_size)];

        trigger->SetActive();
        l_objects.push_back(trigger);
    }
}
_Winnie C++ Colorizer


Соответственно, выполнение объектов выглядит следующим образом:

static __int64 CheckObjectsV()
{
    std::vector<Object>::const_iterator itr = v_objects.begin();
    std::vector<Object>::const_iterator end = v_objects.end();
    __int64 time0 = GetTime();

    while(itr != end) {
        if (itr->IsActive()) {
            if (itr->CheckObject())
                ++v_counter;
        }
        ++itr;
    }
    return GetTime() - time0;
}

static __int64 CheckObjectsL()
{
    std::list<Object*>::const_iterator itr = l_objects.begin();
    std::list<Object*>::const_iterator end = l_objects.end();
    __int64 time0 = GetTime();

    while(itr != end) {
        if ((*itr)->CheckObject())
            ++l_counter;
        ++itr;
    };
    return GetTime() - time0;
}
_Winnie C++ Colorizer


И наконец, тестовая программа умеет анализировать командную строку, вызывать создание вектора/списка и проверять объекты (в векторе - только активные, в списке - все) и делать временную аллокацию памяти для сброса кеша. Полный листинг программы доступен по ссылке: http://www.everfall.com/paste/id.php?u1rcn6zpxn4k, описание аргументов командой строки доступно при запуске с ключом -help. По умолчанию создается вектор на 10000 объектов (из них 300 активировано) и список на 300 активированных объектов.

Результаты получились следующие. Сначала потренируемся на кошках на векторе.

D:\LVTest>test.exe -create V -exec V
Vector: 1079304;
Vector: 336920;
Vector: 236608;
Vector: 355072;
Vector: 300368;
Vector: 265040;
Vector: 266232;
Vector: 280176;
Vector: 155720;
Vector: 149888;

Первый момент, который бросается в глаза - время выполнения заметно "плавает". Причем первый замер вообще ни в какие ворота не лезет. Если добавить ключ -repeat 1000, то время вычисления будет тоже разным, но плавать будет в районе 150000 - 180000 тиков.
Что это может быть? Гипотеза номер раз - поскольку время замера невелико, то могут влиять посторонние процессы и треды. Также может влиять кеш. Также (после http://ddima.livejournal.com/62676.html я уже ничему не верю) может влиять предсказатель переходов. Проверим его с помощью аргумента -vector first (все активированные объекты расположены в начале):

D:\LVTest>test.exe -create V -exec V -vector first
Vector: 1093376;
Vector: 300440;
Vector: 300384;
Vector: 162808;
Vector: 186792;
Vector: 142552;
Vector: 146216;
Vector: 209704;
Vector: 140000;
Vector: 144624;

Результаты в целом получше, на длинных прогонах уменьшение времени работы примерно на 20000 тактов. Впрочем, это около процента от времени вычисления. Попробуем зафлешить кеш, для этого в опции -exec добавим режим A (Allocation)

D:\LVTest>test.exe -create V -exec VA
Vector: 1011696; Alloc;
Vector: 842568; Alloc;
Vector: 694384; Alloc;
Vector: 925096; Alloc;
Vector: 876408; Alloc;
Vector: 855848; Alloc;
Vector: 927312; Alloc;
Vector: 883648; Alloc;
Vector: 901104; Alloc;
Vector: 879000; Alloc;

Результат в среднем в 5 раз превышает предыдущий. При этом (что очень странно) первый прогон стабильно вылезает за все остальные.

Аналогичные проверки для списка дают следующий результат:

D:\LVTest>test.exe -create L -exec L
List: 56488;
List: 58976;
List: 57672;
List: 57536;
List: 57704;
List: 57496;
List: 57512;
List: 57504;
List: 57456;
List: 57464;

D:\LVTest>test.exe -create L -exec LA
List: 56664; Alloc;
List: 265920; Alloc;
List: 272992; Alloc;
List: 235832; Alloc;
List: 254576; Alloc;
List: 274632; Alloc;
List: 245696; Alloc;
List: 248400; Alloc;
List: 274704; Alloc;
List: 242056; Alloc;

А теперь собственно, основной момент, вокруг которого разгорелся основной сыр бор. Смотрим на выполнение программы, если создается и исполняется сразу оба варианта:

D:\LVTest>test.exe -create LV -exec LV
List: 403680; Vector: 1324808;
List: 148232; Vector: 248776;
List: 97488; Vector: 206656;
List: 96240; Vector: 211504;
List: 88776; Vector: 202448;
List: 86304; Vector: 199096;
List: 86872; Vector: 197448;
List: 86088; Vector: 197272;
List: 183624; Vector: 458456;
List: 205104; Vector: 500336;

D:\LVTest>test.exe -create VL -exec VL
Vector: 804256; List: 220472;
Vector: 475224; List: 174344;
Vector: 377992; List: 163544;
Vector: 363600; List: 158984;
Vector: 343664; List: 167432;
Vector: 377872; List: 162024;
Vector: 359800; List: 153960;
Vector: 275848; List: 91576;
Vector: 203640; List: 85472;
Vector: 196792; List: 84720;

D:\LVTest>test.exe -create VLA -exec AVALA
Alloc; Vector: 848672; Alloc; List: 354160; Alloc;
Alloc; Vector: 851488; Alloc; List: 330280; Alloc;
Alloc; Vector: 833992; Alloc; List: 349984; Alloc;
Alloc; Vector: 848240; Alloc; List: 245056; Alloc;
Alloc; Vector: 871880; Alloc; List: 294720; Alloc;
Alloc; Vector: 891680; Alloc; List: 319920; Alloc;
Alloc; Vector: 719904; Alloc; List: 352816; Alloc;
Alloc; Vector: 642424; Alloc; List: 316056; Alloc;
Alloc; Vector: 599248; Alloc; List: 315336; Alloc;
Alloc; Vector: 889056; Alloc; List: 322680; Alloc;

Анализ, почему оно именно так, а не иначе, пока еще ведется, есть несколько идей. Во первых, если кому не лень, посмотрите плиз, как ведет себя такое приложение с разными вариантами командной строки у вас на компьютере. Во вторых, неожиданный вопрос: почему первый вариант -exec L всегда быстрее, чем последующие? Т.е. список сразу после создания работает чуть быстрее (разница еле заметная, но все же есть, причем постоянно), чем остальные замеры. Есть гипотеза, что это как-то связано с гранулярностью таск шедулинга Windows и нам просто так повезло. Но может быть, есть что-то еще...

Предварительные выводы:
1. Проводить синтетические тесты, которые "замеряют" время выполнения базовых функций в течение нескольких секунд (чтобы было типа точнее) бесмысленно. Кеш портит всю картину, ускоряя выполнение в несколько раз. А ведь в реальном приложение подобные алгоритмы будут получать управление как правило в плохих условиях без префетча.
2. Вектор чуть менее чувствителен к кеш-мисам, чем список. И несмотря на то, что в режиме "300 активных на 10000 объектов" он работает медленее списка на 300 объектов, разница не такая существенная. Разумеется, все также зависит от сложности вычислений внутри CheckObject().
3. Лично мое мнение - использование списков в подобных случаях неоправдано (разумеется, если речь не идет о ситуации "найти пару активных в 50000000 объектов"). Перетасовка объектов между списками, да еще и необходимость следить за синхронизцией факта нахождения объекта в списке с его локальным состоянием типа bActive - отличное место для багов, и конфликтная ситуация типа "неактивный объект в активном списке" без специальных ботлнеков рано или поздно возникнет обязательно. Впрочем, это уже совсем другая история, к делу не относящаяся.

Продолжение следует...
Tags: prog
Subscribe

  • .

    Я никуда не пропал, но последнее время меня можно найти только за городом (все выходные + отпуск, из которого на 3 дня вышел на работу :) ).

  • Тренд и текущее

    По результатам майской расчистки участка в ночь с 1 на 10 число: насколько я понимаю, смысл жизни среднестатистического советского дачника заключался…

  • Строительство, и ни капли agile'а

    Вот оно, чего я так долго планировал сам, продумывал, рисовал в Google SketchUp, и наконец, вопротил в жизнь при помощи профессиональных…

  • Post a new comment

    Error

    Comments allowed for friends only

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 18 comments

  • .

    Я никуда не пропал, но последнее время меня можно найти только за городом (все выходные + отпуск, из которого на 3 дня вышел на работу :) ).

  • Тренд и текущее

    По результатам майской расчистки участка в ночь с 1 на 10 число: насколько я понимаю, смысл жизни среднестатистического советского дачника заключался…

  • Строительство, и ни капли agile'а

    Вот оно, чего я так долго планировал сам, продумывал, рисовал в Google SketchUp, и наконец, вопротил в жизнь при помощи профессиональных…