std :: установить быстро и медленно, что происходит? - PullRequest
Новая
       15

std :: установить быстро и медленно, что происходит?

9 голосов
/ 16 ноября 2011

Я столкнулся со странным поведением std :: set.

Вот код: 

#include <cstdio>
#include <windows.h>
#include <stdlib.h>

#include <vector>
#include <set>

using namespace std;

int main(int argc, char *argv[])
{
    set<int> b[100];

    for (int o=0; o<10; o++)
    {
        int tt = GetTickCount();

        for (int i=0; i<5000000; i++)
        {
            b[o].insert(i);
        }

        tt = GetTickCount() - tt;

        b[o].clear();

        printf("%d\n", tt);
    }

    return 0;
}

Я работаю на Windows XP.

Вот интересная часть: первое время печати составляет около 3500 мс, а все последующие - более 9000 мс!Почему это происходит?

О, и это происходит только в версии выпуска (оптимизация -O2).

Этого не происходит в Linux (после изменения кода для его компиляции).

Еще одна вещь: когда я запускаю его во время профилирования с Intel VTune, это всегда занимает около 3000 мс, поэтому так и должно быть.

ОБНОВЛЕНИЕ: Вот новый код: 

#include <cstdio>
#include <windows.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
const int count = 10000000;
int **a = new int*[count];

for (int o=0; o<10; o++)
{
    int ttt = GetTickCount();

    for (int i=0; i<count; i++)
    {
        a[i] = new int;

        *a[i] = i;
    }

    int ttt2 = GetTickCount();

    for (int i=0; i<count; i++)
    {
        int r1 = rand() * 10000 + rand();
        int r2 = rand() * 10000 + rand();
        r1 = r1%count;
        r2 = r2%count;

        int *e = a[r1];
        a[r1] = a[r2];
        a[r2] = e;
    }

    int ttt3 = GetTickCount();

    for (int i=0; i<count; i++)
    {
        delete a[i];
    }

    int ttt4 = GetTickCount();

    printf("%d %d\n", ttt2-ttt, ttt4-ttt3);
}

return 0;
}

Это та же проблема.Что происходит, я выделяю много маленьких объектов, а затем удаляю их в случайном порядке, так что это похоже на то, как это выглядит в std :: set.Так что это проблема управления памятью Windows.Он не может справиться с большим количеством мелких ассигнований и удалений.

Ответы [ 2 ]

6 голосов
/ 16 ноября 2011

Я не могу точно объяснить, почему это происходит, но я мог бы предложить решение.Я смог воспроизвести это на своем ПК, когда я запускаю сборку релиза под отладчиком (с F5).Когда я запускаю сборку из командной строки или с помощью Ctrl-F5, я не получаю такого поведения.

Это как-то связано с кучей отладки, которая включена по умолчанию при запуске из отладчика,Это описано очень подробно здесь .Чтобы этого не произошло, либо

  1. Запустите из командной строки или с помощью Ctrl-F5 (Отладка -> Запуск без отладки).
  2. Перейдите в Проект -> Свойства -> Отладка -> Среда и добавление _NO_DEBUG_HEAP=1.

Если бы мне пришлось угадывать, я бы сказал, что это как-то связано с реализацией отслеживания выделения памяти в среде выполнения Windows / VS.Возможно, некоторые внутренние списки заполняются и перераспределяются или что-то еще в этом духе.

0 голосов
/ 17 ноября 2011

Я думаю, std::set реализован в виде бинарного дерева поиска. Так как вы увеличиваете i на 1 каждый раз, когда вы по существу создаете состязательный (наихудший случай) сценарий для этого типа структуры данных (изменение баланса дерева требуется почти на каждой вставке).

Кроме того, это 50 миллионов вставок, поэтому ожидается некоторое время, хотя я не думаю, что это будет 5 мс.

Кроме того, я бы выполнил «очистку» после того, как вы напечатаете свое время, поскольку не вижу причины, по которой вы могли бы сравнивать как вставку, так и удаление элементов.

...