вставка QVector в другой QVector Опции

[Авварон]

Iron Bug
Вы зря считаете, что никто Qt не оптимизировал Я лично гонял бенчмарки на маке по просьбе человека, к-ый занимался оптимизацией строк (там вообще весьма забавно, скорость работы строк рассчитывается на "наиболее частые юзкейзы" - читай подгоняют код под определенные последовательности строк).
Для стд же контейнеров оптимизация если даже и проводится в большем количестве, но проводится она _разными_ людьми, реализующим _разные_ имплементации в компиляторах. Соответственно то, что оптимизировали в одном компилере, может не быть оптимизировано в другом (что и является главной причиной для меня не использовать stl контейнеры - я хочу делать оценки о производительности не привязываясь к компилятору, а только лишь к самому алгоритму)

От слов к делу - будьте добры, погоняйте этот http://mtgs.clan.su/stlvsqt.zip бенчмарк на вашем компуторе. Он не совсем "честный", так как использует QString, базированную на корове, а не wstring, так как кутешные контейнеры оптимизированы на использование Qt типов. В случае wstring результаты чуть другие (некоторые вещи, например deep copy QList'а будут сильно медленнее, чем копия QVector'a или std::vector, а аппенд std::vector'а в 2 раза быстрее аппенда qt; остальные же операции у qt по-прежнему быстрее).
Поправьте, если я где налажал в бенчмарке.

Вот мои результаты (OX X 10.8, Apple clang 4.1 (llvm 3.1))

Раскрывающийся текст

********* Start testing of StlvsqtTest *********
Config: Using QTest library 5.0.1, Qt 5.0.1
PASS   : StlvsqtTest::initTestCase()
PASS   : StlvsqtTest::testAppendQVector()
RESULT : StlvsqtTest::testAppendQVector():
     0.000037 msecs per iteration (total: 79, iterations: 2097152)
PASS   : StlvsqtTest::testAppendQList()
RESULT : StlvsqtTest::testAppendQList():
     0.000018 msecs per iteration (total: 78, iterations: 4194304)
PASS   : StlvsqtTest::testAppendSTLVector()
RESULT : StlvsqtTest::testAppendSTLVector():
     0.000033 msecs per iteration (total: 71, iterations: 2097152)
PASS   : StlvsqtTest::testPrependQVector()
RESULT : StlvsqtTest::testPrependQVector():
     0.00473 msecs per iteration (total: 155, iterations: 32768)
PASS   : StlvsqtTest::testPrependQList()
RESULT : StlvsqtTest::testPrependQList():
     0.000021 msecs per iteration (total: 92, iterations: 4194304)
PASS   : StlvsqtTest::testPrependSTLVector()
RESULT : StlvsqtTest::testPrependSTLVector():
     0.0454 msecs per iteration (total: 186, iterations: 4096)
PASS   : StlvsqtTest::insertMiddleQVector()
RESULT : StlvsqtTest::insertMiddleQVector():
     0.0023 msecs per iteration (total: 76, iterations: 32768)
PASS   : StlvsqtTest::insertMiddleQList()
RESULT : StlvsqtTest::insertMiddleQList():
     0.0023 msecs per iteration (total: 77, iterations: 32768)
PASS   : StlvsqtTest::insertMiddleSTLVector()
RESULT : StlvsqtTest::insertMiddleSTLVector():
     0.022 msecs per iteration (total: 93, iterations: 4096)
PASS   : StlvsqtTest::insertRandomQVector()
RESULT : StlvsqtTest::insertRandomQVector():
     0.0024 msecs per iteration (total: 79, iterations: 32768)
PASS   : StlvsqtTest::insertRandomQList()
RESULT : StlvsqtTest::insertRandomQList():
     0.00514 msecs per iteration (total: 337, iterations: 65536)
PASS   : StlvsqtTest::insertRandomSTLVector()
RESULT : StlvsqtTest::insertRandomSTLVector():
     0.022 msecs per iteration (total: 93, iterations: 4096)
PASS   : StlvsqtTest::deepCopyQVector()
RESULT : StlvsqtTest::deepCopyQVector():
     0.22 msecs per iteration (total: 57, iterations: 256)
PASS   : StlvsqtTest::deepCopyQList()
RESULT : StlvsqtTest::deepCopyQList():
     0.21 msecs per iteration (total: 56, iterations: 256)
PASS   : StlvsqtTest::deepCopyStlVector()
RESULT : StlvsqtTest::deepCopyStlVector():
     0.21 msecs per iteration (total: 56, iterations: 256)
PASS   : StlvsqtTest::cleanupTestCase()
Totals: 17 passed, 0 failed, 0 skipped
********* Finished testing of StlvsqtTest *********

Вкратце (больше значит быстрее, больше либо равно значит чуть быстрее, но вообще цифры сравнимы)

для QString

Append: QList > std::vector >= QVector
Prepend: QList > QVector > std::vector
InsertMiddle: QList >= QVector > std::vector
InsertRandom: QVector > QList > std::vector
DeepCopy: std::vector == QList >= QVector

для std::wstring

Append: std::vector > QVector >= QList
Prepend: QList > std::vector >= QVector
InsertMiddle: QList > QVector == std::vector
InsertRandom: std::vector >= QVector > QList
DeepCopy: std::vector == QVector > QList (тут кулист почему-то ОЧЕНЬ медленный)

Сообщение отредактировал Авварон - 15.2.2013, 10:50

[Алексей1153]

Авварон,

Да, эта программа подпадает под мое понимание "одной формочки". Что у нее там внутри крутится, не могу сказать

в первой программе крутится несколько потоков -
- чтение с порта со скоростью 115200 бод непрерывно (объектов, присылающих сообщения со всего города - порядка 3 тысяч на пульт, каждый да пришлёт чего-нибудь - тестовые сигналы, охранные сигналы, учитывай ещё повторы для радиоканала и с ретрансляторов - но одинаковые сообщения я отбрасываю по тайм-фильтру), обработка и сохранение этого всего в БД , ответ прибору (ок-транспорт), так как без ответа "ок" он будет повторять сообщение. Заметь, что БД - не шустрик MySQL, а откровенный тормоз на FireBird 1.5 . Мне приходится большую часть данных хранить в озу, а это - журнал событий для оператора(до 5 лимонов сообщений , загруженных из БД) , около поллимона сообщений железных - для настройщиков (кольцевой буфер)
- приём по TCP и UDP сообщений, ретранслированных с других машин
- отправка писем и SMS (модем подключен к компу)
- работа в сети с другими рабочими местами (операторов несколько)
- обработка текущих состояний объектов, охранных алгоритм и контроль всяческих периодов - пропадание, тестовые, задержка на вход, проверка расписания объекта
- составление отчётов, статистика и прочее

ВСЁ ЭТО обязано работать на машине чуть сильнее средней, причём работать без выключения месяцами.


во второй программе таких ужасов нет, но все диалоги построены из XML файла с применением нелюбимого тобой STL . В момент переключений приборов создание и разрушение объектов (в том числе и объектов GUI системы) идёт очень интенсивно

У меня нет утечек, чесна чесна! )


Про профилировщик я ничего не мог сказать - я ими не пользовался ни разу.

Фриланс - это движение вперёд и уход от стереотипов , вливайся free-lance.ru

по скорости работы Qt ничем не уступает MFC или WinAPI

Приведённые тесты лично мне ни о чём не говорят

Append: QList > std::vector >= QVector
Prepend: QList > QVector > std::vector
InsertMiddle: QList >= QVector > std::vector
InsertRandom: QVector > QList > std::vector
DeepCopy: std::vector == QList >= QVector

- всеми этими операциями я пользуюсь редко. А у вектора резервирование памяти учитывал ? Или без него ?

опять же, если нужен ассоциативный массив, всё равно городить надо. А тут раз - и есть готовый std::map

к слову, из всех контейнеров мне хватает
std::vector
std::set
std::multiset
std::map
std::multimap

остальное не требуется

[Авварон]

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

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

Про ассоциативный массив - в Qt есть и они, вы не поверите Плюс кутешники используют скип-лист вместо черно-красного дерева в стд, который в каких-то случаях лучше, в каких-то хуже. Кто знает, может QMap вам подойдет лучше

[Алексей1153]

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

опыт сказывается Лично я раньше по-всякому куролесил. В старые проекты без волосодыбления невозможно заглядывать. И запускать тоже их смешно

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

он автоматом резервирует capacity вдвое больше от последнего, если памяти не хватает. При этом происходит "тяжёлая вещь" - переаллокация. То есть, для 1024 элемента, если их вставлять по одному, произойдёт около 10 переаллокаций. Чаще всего размер вектора можно предсказать заранее и reserve его

в Qt есть и они, вы не поверите

я в курсе.


Тут ещё такой момент присутствует - захочется мне использовать некий отлаженный алгоритм из Qt-проекта применить в проекте другого типа, я просто скопипастю его и всё. А с Qt-контейнерами придётся возиться переделывать, а потом тестить

топикстартер __ilya__ - Последнее посещение: 11.2.2013, 14:22

вот порадуется, какой вброс совершил

[lanz]

Every C++ programmer is a showoff

[Алексей1153]

lanz, ну давай, начинай ))

[Авварон]

он автоматом резервирует capacity вдвое больше от последнего, если памяти не хватает. При этом происходит "тяжёлая вещь" - переаллокация. То есть, для 1024 элемента, если их вставлять по одному, произойдёт около 10 переаллокаций. Чаще всего размер вектора можно предсказать заранее и reserve его

При этом количество переаллокаций уменьшается логарифмически при увеличении кол-ва эл-тов. А при бенчмарке 4096 итераций - это минимум.

То, что вы предлагаете - это как тестить map, вставляя в него эл-ты так, чтобы он оставался идеально сбалансированным Ну и аппенд - это лишь одна из операций (самая быстрая у вектора), а вот вставки в середину/начало вы никаким преалоком не улучшите.

[Алексей1153]

То, что вы предлагаете

а что я предлагаю ?

map, вставляя в него эл-ты так, чтобы он оставался идеально сбалансированным

алгоритм сортировки std::map работает всегда одинаково (впрочем, как и у QMap), повлиять на эту работу без предиката невозможно. Поэтому непонятна фраза про "так,чтобы он оставался". И как можно сравнивать вектор и мап, непонятно ) Мы же про вектор говорим вроде

а вот вставки в середину/начало вы никаким преалоком не улучшите.

копирование и сдвиг произойдёт гораздо быстрее, чем переаллокация. Несоизмеримо

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

[Авварон]

алгоритм сортировки std::map работает всегда одинаково (впрочем, как и у QMap), повлиять на эту работу без предиката невозможно. Поэтому непонятна фраза про "так,чтобы он оставался". И как можно сравнивать вектор и мап, непонятно ) Мы же про вектор говорим вроде

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

копирование и сдвиг произойдёт гораздо быстрее, чем переаллокация. Несоизмеримо

Я прогнал тест с преаллоцированным размером на 10^9 элементов, результаты еще интереснее:
при добавлении в конец - std::vector в 4 раза быстрее, чем QVector и чуть-чуть опережает QList
при вставке в случайное место - std::vector хуже на порядок (0.0023 для QList, 0.0024 для QVector, 0.023 (в десять раз медленнее!) для std::vector),
при вставке в начало - std::vector на 3 (!) порядка (!) хуже QList'а , на 1 порядок хуже, чем QVector

Правда, следует понимать, что эти цифры возможны благодаря тому, что QList/QVector "знают" о том, что QString (и другие Qt классы) используют Корову, и можно применять memmove вместо копирующего/мувающего конструкторов.
Скорее всего, при использовании обычных классов или структур std:: типы будут быстрее; однако ничто не мешает переписать свою структуру на Корову или тупо использовать указатель.

Сообщение отредактировал Авварон - 15.2.2013, 17:22

[Алексей1153]

при вставке в случайное место - std::vector хуже на порядок

в качестве элементов использовались указатели, надеюсь ? Если нет - тест некорректен

Сообщение отредактировал Алексей1153 - 15.2.2013, 18:19