Создание шаблонного класса создает серьезное узкое место

Question

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

for(unsigned int i = 0; i < l_NodeCount; ++i) 
                m_NodeList.push_back(Node<T>(m_NodeCounter++));

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

Есть ли лучший способ одновременно создавать все эти классы шаблонов без необходимости вызовакаждый раз конструктор или мне нужно переписать его без шаблонов?

Answer 1

Если конструктор почти ничего не делает, как вы говорите, узким местом, скорее всего, является выделение новой памяти.Вектор растет динамически, и каждый раз, когда его память исчерпывается, он резервирует новую память и копирует туда все данные.При добавлении большого количества объектов это может происходить очень часто и становится очень дорогим.Этого можно избежать, вызвав

m_NodeList.reserve(l_NodeCount);

. При таком вызове вектор выделит достаточно памяти для хранения l_NodeCount объектов, и у вас не будет дорогих перераспределений при массовом добавлении элементов.

Answer 2

В вашем коде происходят вещи:

• , когда вы добавляете элементы в вектор, иногда приходится изменять размер внутреннего массива, что включает копирование всех существующих элементов в новый массив
• конструктор вызывается для каждого элемента

Вызов конструктора неизбежен.Вы создаете миллион элементов, у вас есть миллион вызовов конструктора.То, что вы можете изменить - это то, что делает конструктор.

Добавление элементов также очевидно неизбежно, но копирование / изменение размера можно избежать.Сначала вызовите reserve для вектора, чтобы зарезервировать достаточно места для всех ваших узлов.

В зависимости от вашего компилятора, настроек оптимизации и других флагов, компилятор может сделать много ненужных границпроверка и отладка проверок также.

• Вы можете отключить это для компилятора (_SECURE_SCL=0 на VS2005 / 2008, _ITERATOR_DEBUG_LEVEL=0 в VS2010. Я считаю, что он выключен по умолчанию в GCC, и не 'не знаю о других компиляторах).
• В качестве альтернативы, вы можете переписать цикл, чтобы минимизировать количество проверок отладки, которые необходимо выполнить.Использование стандартных библиотечных алгоритмов вместо необработанного цикла позволяет библиотеке пропускать большинство проверок (как правило, проверка границ будет выполняться на начальном и конечном итераторе, а не на промежуточных итерациях, тогда как на простом цикле,это будет выполняться каждый раз, когда разыменовывается итератор)

Answer 3

Я бы сказал, что ваше узкое место - это не шаблонный класс, который не имеет ничего общего со временем выполнения и обрабатывается во время компиляции, но добавляет элемент в контейнер vector (в вашем вопросе есть тег "vector"),Вы выполняете ОЧЕНЬ МНОГО распределений, используя push_back.Попробуйте выделить необходимый объем памяти сразу, а затем заполните элементы.

Answer 4

вы можете избежать покупки шаблонов, имеющих список (void *) для объектов.и приведем их позже.
но ... если вы хотите иметь 1 000 000 экземпляров класса узла.вам нужно будет вызвать 1 000 000 конструктора узла.