Большие тормоза из-за QVector?

[qtkoder777]

В функции производится около 4000 вставок в конец QVector. Реализуется линейный алгоритм построения полигональной сетки.
Даже если увеличим число операций в 100 раз, не понимаю как 400000 операций могут выполняться 1.5 секунды на проце 2.5 ГГц.
Может ли это быть из-за выделения памяти при каждой вставке в конец?
Раньше как то у меня были тормоза из-за структур вида QVector<QVector<T>>, что в принципе имеет место и здесь. С чем это связано?

Вставляются такие классы:

Код

C++ (Qt)
			class Vertex
			{
				public:
					QVector<double> coord;
					QVector<double> normal;
					QVector<double> texCoord;
			};
 
			class Edge
			{
				public:
					int p1;
					int p2;
					int mid;
					int e1;
					int e2;
			};

[Apktyc]

Если количество вставок известно, QVector::reserve() вам в помощь.
А может присмотреться к списку?

[Old]

Может ли это быть из-за выделения памяти при каждой вставке в конец?

Именно из-за этого, множественные переаллокации и копирования.
Как правило, вы знаете сколько элементов нужно будет добавить в вектор, резервируйте место сразу.

[Old]

А может присмотреться к списку?

Вы имеете ввиду QList (там тоже самое), или честный X-связный список?

[Apktyc]

Вы имеете ввиду QList (там тоже самое), или честный X-связный список?

Прочел, задумался, узнал про QLinkedList, просветился. 

[__Heaven__]

Я бы ещё присмотрелся к map (или set)
при этом QVector<double> сменил бы на struct MyVector{double x, y, z}
а в Edge заменил бы тип p1 и p2 на map::const_iterator
для чего нужны mid, e1, e2 - не понял

[qtkoder777]

Я бы ещё присмотрелся к map (или set)
при этом QVector<double> сменил бы на struct MyVector{double x, y, z}
а в Edge заменил бы тип p1 и p2 на map::const_iterator
для чего нужны mid, e1, e2 - не понял

Проводится рекурсивное разделение треугольников на 4 части. mid - номер точки середины ребра, e1, e2 - номера рёбер, получаемых при делении данного.
Надо избежать повторного добавления точек деления у соседних треугольников. Раньше это и было сделано с помощью QMap<начало ребра, конец ребра, середина>. Сначала грешил на map, так как это C*log(n) к сложности.
Переделал без map, а тормоза остались.

[Igors]

Надо избежать повторного добавления точек деления у соседних треугольников.

В этом есть смысл если есть фейсы (индексы) которых в приведенном коде не видно. Тогда структуры примерно такие

Код

C++ (Qt)
struct Triangle {
 int m_index[3];  // индексы вертексов   
 int m_edges[3];  // индексы ребер   
};
 
struct Edge {
  bool operator < ( const Edge & other ) const { return m_ver < other.m_ver; }
 
// data
  typedef std::pair<int> TPair;
  TPair m_ver;    // индексы вертексов ребра (first < second)
  TPair m_fac;    // индексы фейсов (Triangle) шарящих ребро (second = -1 если ребро открыто)
};

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

[__Heaven__]

Под linux можно ещё попробовать запустить профилирование в callgrind. Делается это через интерфейс qtcreator и результаты удобно выводится. Там и можно глянуть, что тормозит. Может это вообще не Vertex и QVector

[Racheengel]

QVector медленный, на винде раза в 2-3 медленней, чем std::vector.
Эта проблема известна (есть тикеты на Qt-Bugs), может быть, в 6-й версии починят.

[Igors]

Эта проблема известна (есть тикеты ...

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

[Авварон]

QVector медленный, на винде раза в 2-3 медленней, чем std::vector.
Эта проблема известна (есть тикеты на Qt-Bugs), может быть, в 6-й версии починят.

Ссылку в студию

[Racheengel]

https://bugreports.qt.io/browse/QTBUG-44683
https://bugreports.qt.io/browse/QTBUG-44566
https://bugreports.qt.io/browse/QTBUG-49250

Проблема реальная, сами с таким столкнулись. После того, как сменили QVector на std::vector - сильно возрос performance. Конечно, алгоритмических проблем это не решит, но в любом случае не повредит.

[Авварон]

Ну половина тикетов из-за неумения пользоваться qvector, например неконстантный operator[] вместо at() или const версии (он детачит контейнер).
А так, надеюсь в qt6 закопают cow и не потому что использовать сложнее, а потому что qvector не умеет хранить move-only типы.

[qtkoder777]

Эта проблема известна (есть тикеты ...

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

Вектор реально тормозит. Избавление от push-ей сократило время раз в 15.
Чисто переписать полученые 2000-3000 треугольников в массив для рисования занимает 30 мс. Вот и что с этим делать?