Производительность: сетка из множества элементов

NEbO · Регистрация: 22.01.2009

Author24 — интернет-сервис помощи студентам

Имеется некое приложение-редактор, в основе которого лежит некая сетка из графических элементов. Сетка приличных размеров при "нормальных" данных: 100х100 элементов. Пока что сделано на основе стандартного QGraphicsView/QGraphicsScene/QGraphicsItem. Без bsp-индексации наблюдаются приличные тормоза, особенно при масштабировании. После ее включения сцена перестает терять интерактивность (рендеринг <0.1 сек), однако, понятно, что проблема проявится, в случае, если размер данных увеличится, или если компьютер будет послабее.
Даже если предположить, что для конкретно данного приложения хватит всего этого, я задумался на тему общего случая. Наверняка моя задача -- не единственная, в которой применяются подобные сетки, и встает вопрос об эффективности в случае использования, скажем, 1000х1000 элементов и более. Чтобы более наглядно представить себе, о чем я говорю, представьте photoshop, в котором каждый пиксель представляется в виде объекта. Очевидно, что хранить координаты x и y, и связанные с ними индексы и прочее и прочее -- это лишь оверхед, потому что и без них есть алгоритм с константной сложностью для определения item-а в указанной точке, и линейной сложности -- внутри прямоугольника (все элементы имеют одинаковый размер).
Также, ясно, что в такой сетке гораздо проще (с вычислительной точки зрения) вычислять коллизии, ибо элементы в сетке не пересекаются.
Но это еще не все. Если бы в редакторе были только эти элементы, я бы, даже не попробовав потратить чье-то время (возможно и зря), реализовал бы с нуля такую систему (в конкретную реализацию я не вдавался, но не думаю, что это сложно). Но в нем также присутствуют и обычные линии, и, возможно, прямоугольники. Ну вообщем, обычные QGraphicsItem с нефиксированными размерами. Проблема связана с тем, что каждый элемент сетки должен полностью эмулировать поведение QGraphicsItem. Например, они должны выделяться вместе с этими, "обычными" линиями, должна быть возможность переместить выделенную группу на клетку вправо,влево ну и т.д.
Я довольно долго уже гуглил по различным опциям, которые влияют на производительность.
Всякие QGraphicsView::optimizationFlags, QGraphicsView::cacheMode, QGraphicsView::setViewport(new QGLWidget()), QGraphicsItem::cacheMode никакой роли по сути не сыграли.
QGraphicsScene::setItemIndexMethod снижает до log(N) сложности определение видимых элементов, однако рендеринг видимых, скажем, 200х200 элементов все равно идет довольно долго. После того, как я догадался запустить профайлер, оказалось, что основное время уходит на QGraphicsItem::boundingRect. Его я оптимизировал так, чтобы даже не вызывался лишний конструктор, и все равно после этого он тратит больше 50% времени. Вот здесь возникает предположение, что можно добиться приличной производительности, как-то задав опцию, чтобы этот boundingRect не вычислялся каждый раз заново для НЕКОТОРЫХ элементов сцены, а именно, тех, которые лежат на этой сетке: ведь они постоянны. Просмотрев беглым взглядом в т.ч. сами исходники QGraphicsScene, я такой опции не нашел, однако, предполагаю, что она может существовать (буду признателен, если кто знает и подскажет). Думаю, что для реализации моей задачи мне хватит только убрать этот оверхед.
Однако, в более общем случае, оверхеда больше. А поэтому, интересно, как реализовать такую систему, скажем для 1000x1000 элементов? а для 2000х2000 ? Ну, вообщем, интересует алгоритм, структура классов, ну или просто идеи, как сократить сложность алгоритма.

Не по теме:

Возможно, стоит зайти с другой стороны и использовать OpenGL, но тогда все равно все это дело может упереться в тот же самый "аналог boundingRect" в SceneGraph (или как там его) -- разве нет? Я не шибко владею OpenGL и, тем более, применением оного в qt. Вроде как не сильно хочется уходить от удобных QGraphicsItem/QGraphicsScene. Однако, если в действительности задачу решить можно через него, намекните, пожалуйста, в какие классы смотреть, для реализации аналогичных возможностей. Сам по себе 3д в программе, возможно, и понадобится, когда-то, но явно нескоро, и в виде дополнительной возможности. Редактировать непосредственно в 3д в данном случае, точно также нечего, как рисовать прямоугольники в пеинте, и это будет просто мешаться

ПС. если это важно, элементов на сетке много, многие из них повторяются (различных всего-то, скажем, 100, может изредка быть на реальных данных), да еще при этом рендеринг каждого из них довольно сложен. Это сделано для относительной реалистичности, в виде векторной графики, рендерящейся в QPixmap. Исходя из всего этого, разумеется, применяется flyweight, и все это дело очень эффективно использует память.

@Night_Light · 12.03.2013, 13:18

1) Почти уверен, что встречал в примерах Qt пример со сценой, зумингом и кучей элементов.

2) У меня ощущение, что когда-то видел эту проблему. Вы случайно не пробовали ставить вот этот флаг оптимизации:

setCacheMode(QGraphicsItem::ItemCoordinateCache)

3) http://www.qtcentre.org/thread... -of-items-!

NEbO · 12.03.2013, 15:21 **[ТС]**

из описания ItemCoordinateCache:

Caching is enabled for the item's logical (local) coordinate system.

, что для меня не подходит, по двум причинам: внутри отдельного item-а кешировать нечего, т.к. он представляет собой обычный pixmap. ну и второе: сам итем пока что рисуется в прямоугольнике (0,0,1,1), т.е. все координаты для рисования внутри него, в локальной системе координат представляют собой double. точность сильно страдает: все итемы буквально сливаются в одно пятно

ну даже если б этого не происходило, и я бы перешел к целочисленным координатам, установив некий cellSize и умножал бы каждую координату на него, похоже, что из-за первого пункта производительность не возрастает, а только лишь падает. DeviceCoordinateCache стоял, щас его попробовал убрать, но от этого производительность не поменялась (а то и вообще стало чуть побыстрее работать).
Вообще, как я понял из описания этих cacheMode-ов, они действуют только на рендеринг самого итема, увеличивая производительность за счет кеширования трансформаций... но у меня то обычные pixamp-ы, вложенных итемов нет, функция paint -- одна строчка, drawPixamp и все

(ну да, да, еще два Q_UNUSED, но их я не считаю

).
тему эту, конечно, читал, но видимо, не обратил внимания на последнее сообщение, с prepareGeometryChange. Правда, пока еще не разобрался как им пользоваться, но его название мне нравится, возможно, именно оно поможет избавиться от кучи вычислений boundingRect.
впрочем, какого-то процента производительности удалось еще добиться переопределением QGraphicsItem::contains(), collidesWithPath(), collidesWithItem(). пока что это не имеет никакого значения, т.к. все таки цикл, вызывающий boundingRect, является узким местом, но после его исправления, ради интереса можно будет попробовать поменять алгоритм на O(const) для того же contains(), скажем. и можно будет не кешировать тысячи этих итемов, находящихся в гриде, и будет вообще клева (пока что съедается около 200 мб памяти)

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

остается конечно проблема со scale, ибо там без полной перерисовки никак... а если еще попробовать включить анимацию (ну чтоб плавно масштабировалось), то будет плохо. Впрочем, это уже кеширование вида -- можно все рендерить во временный pixmap, и приближать/удалять сам этот pixmap. а когда scale отработает, перерисовыать (и то не сразу, может там два раза колесиком прокрутят, или три) с более высоким качеством. Правда, может есть какой-то способ как-то прозрачно это дело в программу внести? Иначе итемы все равно будут оставаться на сцене, это при каждом масштабировании придется их толи удалять, толи девать еще куда-то, а это, вроде как, довольно долго.
да, Graphics View Framework реально прикольный... особенно, если получится переопредилить сами алгоритмы. Иногда же ведь порядок итемов на сцене строгий, а не от балды -- туда-сюда их кто-то раскидал. Поэтому, в общем случае, наверняка это очень полезная фишка. Раньше я как-то даже и не задумывался покопать в эту сторону, искал именно по many items slow performance, ну и потом по boundingRect еще немного погуглил. Видел на англоязычных форумах что-то подобное, но решения не находил. а щас вроде понял куда копать, думаю, что все получится. и даже не надо делать отдельный grid-item, который как-то должен эмулировать часть поведения сцены, для выделения, перемещения элементов... просто это какой-то костыль. А тут вродь все без костылей и очень красиво

тьфу-тьфу, надеюсь, не сглажу

Добавлено через 9 минут
а, насчет идеи с pixmap-ом при scale, кажется, придумал: переопределить paint у сцены (да или даже у самого View, наверное, будет правильнее, т.к. относится все это к виду) и сделать два состояния: при масштабировании и без него. соответственно, во время scale рендерить только сам этот pixmap. а рендерить в pixmap item-ы можно чуть ли не в отдельном потоке с низким приоритетом, scale чуть задерживать, пока поток не отправит finished()-сигнал, ну и тогда уже начинать саму анимацию масштабирования. ну а можно и без потока попробовать. тоже вроде ничего.
пс. нда, туплю я немного, извиняюсь

@Dmitriy_M · 12.03.2013, 15:53

Есть замечательная демка

NEbO · 12.03.2013, 16:25 **[ТС]**

ага, вот кстати, как раз щас посмотрел, чуть изменил, чтоб было видно побольше элементов. на данный момент она тормозит также (хотя, может чуть поменьше, подсмотрю еще флаги оптимизации), как моя программа (160к итемов). но тут оптимизировать, по сути, нечего. у каждого итема нет никаких ограничений на расположение: их можно подвинуть на любое расстояние. А вот в сетке координаты item-а можно вычислить строго, зная его местоположение в этой сетке. Да, конечно, я спрашивал и про флаги оптимизации, но это все лишь 2х-3х кратное (ну пусть даже 4-5-ти кратное) увеличение производительности. Согласитесь, зная координаты мышки, scale factor, а также то, что ни один элемент не может быть наложен на другой, вычислить итем под мышкой -- дело всего двух-трех операций трансформации матрицы 3х3, что дает константную сложность без кеша. Учитывая, как быстро сейчас, на SSE, производятся эти операции с матрицами, еще неизвестно, что быстрее -- вычислить хеш для того, чтобы считать из кеша это значение, или выполнить эти три трансформации. что, в итоге, увеличивает производительность не в разы, а в десятки (если не сотни) раз, даже на "нормальных" данных. Т.е. я говорю именно о том, чтобы убрать оверхед для данного частного случая, в виде такой вот сетки

пример хороший, но он не показывает того, что мне нужно

@Dmitriy_M · 12.03.2013, 16:48

Сообщение от NEbO

у каждого итема нет никаких ограничений на расположение: их можно подвинуть на любое расстояние.

Ничто не мешает привязать объект.

Сообщение от NEbO

Согласитесь, зная координаты мышки, scale factor, а также то, что ни один элемент не может быть наложен на другой, вычислить итем под мышкой -- дело всего двух-трех операций трансформации матрицы 3х3, что дает константную сложность без кеша

можно без трансформаций обойтись.

Сообщение от NEbO

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

Может ошибаюсь, но SSE это векторные операции, и что бы перемножать матрицы требуется написать специальный код использующий инструкции SSE.

NEbO · 12.03.2013, 17:45 **[ТС]**

Сообщение от Dmitriy_M

Может ошибаюсь, но SSE это векторные операции, и что бы перемножать матрицы требуется написать специальный код использующий инструкции SSE.

ну если б так, то у gcc не было бы таких опций как -msse, -msse2 и так далее

наверняка это не так то просто сделать, но недаром же тот же gcc весит так много

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

Сообщение от Dmitriy_M

Ничто не мешает привязать объект.

привязка всмысле snap через переопределение itemChange, ну или через pos? оно тут ни при чем, это лишь искуственное ограничение на координаты сцены, а в общем плане ничего не меняется: у меня есть естественное ограничение, и я хочу его использовать эффективно. помоему вы меня не поняли

Добавлено через 35 минут
о, кстати, щас вспомнил про itemChange, после вставки такого кода:

C++ (Qt)

QVariant itemChange(GraphicsItemChange change, const QVariant &value)
    {
        static QList <GraphicsItemChange> changes;
        switch (change) {
        case QGraphicsItem::ItemParentChange:
        case QGraphicsItem::ItemParentHasChanged:
        case QGraphicsItem::ItemSceneChange:
        case QGraphicsItem::ItemPositionChange:
        case QGraphicsItem::ItemPositionHasChanged:
            return QGraphicsItem::itemChange(change, value);
        default:
            if (!changes.contains(change)) {
                changes.append(change);
                qDebug() << change;
            }
            return 0;
        }
    }

стало работать быстрее

может так понятнее будет. засунул некий счетчик в своего наследника QGraphicsItem:

C++ (Qt)

QRectF boundingRect() const {
        CNTR++;
        if (CNTR % 10000 == 0) {
            qDebug() << CNTR;
        }
        return QRectF(0, 0, 1, 1); // на самом деле, тут стояло return _boundingRect, чтобы не возникало лишнего конструктора, я просто вернул, чтобы указать, что все итемы реально одинаковые
    }

на сцене 100х100 итемов, расположенных в гриде. Итемы не могут изменять размер, и вообще стоят себе никого не трогают. на кой фиг запрашивать boundingRect() каждый раз, когда я двигаю мышкой, вот тут, в этой сетке? как это запретить, или вычислить заранее (prepareGeometryChange я пока еще не разобрался как работает, да и вообще похоже, все-таки это не совсем то)? а когда нет itemChange, то CNTR вообще сам по себе увеличивается, причем очень нехило

и это запрашивается у каждого итема, в сетке, хотя на самом деле каждый этот итем абсолютно одинаковый, т.е. вообще просто ссылается на какой то другой объект (который один) и который реализует сам paint. размеры тоже задает этот объект. в итоге graphicsItem-ы должны различаться только позицией, ну и создавать некий рисунок, в виде сетки.
короче, как действительно эффективно реализовать flyweight в QGraphicsScene?

@Dmitriy_M · 12.03.2013, 17:46

Сообщение от NEbO

ну если б так, то у gcc не было бы таких опций как -msse, -msse2 и так далее

Есть и что? На практике пока, что ручная оптимизация дает намного лучший результат.

Сообщение от NEbO

наверняка это не так то просто сделать

это не сложно. У gcc/vs есть расширение для работы с SSE

Сообщение от NEbO

векторные операции -- это как раз работа с массивами (кхм, матрица -- тот же массив).

Массив массивов или вектор?
В случае если матрица представлена массивом массивов, то ты уже не можешь выполнить скалярного произведения строки на столбец одной инструкцией SSE.

Сообщение от NEbO

а вот без трансформаций проблематично, по-моему... это как?

Я создам матрицу NxM указателей на элементы, дальше вычисляю номер строки и номер столбца нужного элемента.
Если шаг сетки фиксирован, по высоте и ширине, то это будет:

C

1 2	n = y / stepH; m = x / stepW;

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

@Night_Light · 12.03.2013, 17:52

Сообщение от NEbO

не обратил внимания на последнее сообщение, с prepareGeometryChange

NEbO, ага, я именно это имел в виду в качестве возможного варианта решения

NEbO · 12.03.2013, 18:05 **[ТС]**

Сообщение от Dmitriy_M

Я создам матрицу NxM указателей на элементы, дальше вычисляю номер строки и номер столбца нужного элемента.
Если шаг сетки фиксирован, по высоте и ширине, то это будет:

C

1 2	n = y / stepH; m = x / stepW;

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

так как указать QGraphicsScene, чтобы для НЕКОТОРЫХ элементов он работал по вашему алгоритму?

(items() не виртуальный, наверняка с ним будут проблемы).

Не по теме:

пофиг, что это и есть по сути и есть трансформация, хоть и неполная

Не по теме:

насчет оптимизации под sse вы правы, за исключением того, что матрицу транформации в иделе можно наверняка представить в виде обычного массива (9 элементов), правда инструкций sse, работающих с 9ю элементами по 80 бит (double) я пока не встречал. про математику трансформации я точно не знаю (определитель считается и умножается на каждый элемент?), но если нужно будет, я найду:)
никто не говорит, что выполняется это одной инструкцией. в мануале по qt говорится, что они оптимизировали для процессоров, аппаратно работающих с double, и трансформации быстрые. применяется там sse или нет, не уточняли, правда, но в данном случае это не суть.
а по поводу векторизации циклов см. http://gcc.gnu.org/projects/tr... ation.html.

Добавлено через 1 минуту
Night_Light, плииин. скажите пожалуйста, а как им пользоваться?

чувствую себя блондинкой

ну ничего за 2 часа не понял, boundingRect как считался, так и считается.

@Night_Light · 12.03.2013, 18:42

NEbO, если бы я этим пользовался, то сказал бы

кажется, что-то есть тут http://www.qtcentre.org/archiv... 49021.html

а именно:

A shortlist to check (as always with graphics items):
1. Is my bounding rect defined correctly (e.g. is it independent of the placement of the item)?
2. Is my shape defined within the bounding rect?
3. Is my paint() routine painting only within the bounding rect?
4. Am I calling prepareGeometryChange() each time the bounging rect is going to change?

Т.е. по идее у Вас должны быть переопределены boundingRect() и shape()

По ссылке, вроде, проблема была из-за того, что boundingRect() возвращал невалидное значение.

NEbO · 12.03.2013, 19:28 **[ТС]**

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

Не по теме:

одна беда, что никак не могу нормального профайлера найти. обычный gprof под виндой не строит call-graph, и я не вижу, откуда вызывается boundingRect, vtune у меня не запустился почему-то (может, изза семерки, а на рутрекере явно не самый последний), амд-шный профайлер указывает вообще непонятно на что, а AQTime сильнейше тормозит, и изза этих тормозов он вообще вправе подумать на любую функцию внутри цикла перерисовки сцены. пока что мне показал, что дольше всех выполняется qMax или что-то в этом роде:) можно, конечно, повозиться с флагами для vc++, заинлайнить половину всего, и прикрутить отладочную информацию, но боюсь, от этого он может начать показывать вообще левые вещи... например, пробовал в gcc компилить с -gstabs+ -g -gp -O2, в выводе вообще какая-то полная ерунда, boundingRect он не показывает, показывает какую-то другую функцию, которая вызывалась ровно столько же, сколько boundingRect (на котором у меня свой счетчик). То есть отладочная информация как-то сбивается. наверное, с -g надо поиграться, но я пока не копал в эту сторону, просто боюсь, что даже знание всех функций мало чем поможет, да и без call-graph-а как то не то.

@Night_Light · 13.03.2013, 11:29

Если возможно, можете скинуть мне исходники, я попробую посмотреть, но не в самое ближайшее время

На счёт профайлера под Windows я не в курсе, мне хватает xCode Instruments под MacOS для Qt кода.

NEbO · 15.03.2013, 00:32 **[ТС]**

Сообщение от Night_Light

я попробую посмотреть

что вы ожидаете там увидеть?

все что там есть, существенного для этой задачи, я описал: возьмите любую сцену и киньте на нее 300 на 300 PixmapItem-ов

если 300х300 на вашем компьютере (тем более, MacOS -- там, возможно, все по другому) заработают без тормозов, увеличьте до 500х500. Суть не в размере, а в квадратичной сложности. С нуля реализовывать это -- оно даже лучше: мысли свежее. ну и еще я на QGraphicsView QWheelEvent переопределяю. Для перемещения по сцене достаточно просто включить QGraphicsView::setDragMode(QGraphicsView::ScrollHandDrag).
Если нужно, я могу написать этот код.
Но сами поймите, что тут дело не в кешировании и не в чем-либо еще. У меня получилось добиться хорошей производительности, для 200х200 точек, помоему уже все, что можно, выжал

даже boundingRect поменьше стал времени отнимать, я точно не понял почему, я просто разные комбинации из флагов попробовал. Хотя, это может какие-то еще "артефакты" профайлера, они действительно какие-то глючные все, под винду.
Так вот, дальнейшее ускорение возможно за счет реализации совершенно другого алгоритма. И щас я вот взял, сделал просто одним итемом всю эту сетку. Угадайте, что получилось?

правильно, 10000х10000 элементов, и они летают, как положено (разумеется, единовременно видно не более 300х200 ну или около того). Нагрузка на процессор возникает, только когда я уж совсем очень быстро начинаю туда-сюда сцену крутить. И это без использования хитроумного группового кеширования (каждая ячейка прорисовывается отдельно. Для большого количества элементов это очень неэффективно, разумеется, а точность высокая там не нужна), которое в такой системе реализовать гораздо проще: все элементы хранятся в двумерном массиве, и соседи каждой ячейки тоже вычисляются за константное время!
При этом модель всего этого дела укладывается в 10000х10000х16 бит (мне нужно хранить только индекс из массива-flyweight-а) = 200 мегабайт. ну вот примерно об этом я говорил, когда пытался объяснить, что мне нужно.
Беда только в том, что сейчас придется реализовывать вручную все selection-ы, перемещения, ну и другие вещи, которые, при использовании "обычных" QGraphicsItem-ов, предоставлялись бы автоматически. Впрочем, опять же, у меня программа-редактор, мне все равно это все вручную делать: автоматически предоставляются только ну совсем уж базовые возможности.
Так вот. Вроде бы, для себя все решил, и архитектуру чуть переделал, вроде все должно получиться нормально. И тем не менее, вопрос остается открытым.
Зато теперь могу почетче сформулировать вопрос: "как переопределить стандартные алгоритмы нахождения, позиционирования, и определения границ элементов сцены?" (разумеется, с возможностью частичного делегирования на стандартные)

@Dmitriy_M · 15.03.2013, 08:38

Сообщение от NEbO

так как указать QGraphicsScene, чтобы для НЕКОТОРЫХ элементов он работал по вашему алгоритму? (items() не виртуальный, наверняка с ним будут проблемы).

А зачем мне items? О

Сообщение от NEbO

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

У тебя 2D, каждый элемент пространства вектор из двух координат, по идее и матрица должна быть 2x2, если это так, то пересчет координат это 4 умножения и 2 сложения, что должно быстро обрабатываться при клике.

Сообщение от NEbO

скажите пожалуйста, а как им пользоваться? чувствую себя блондинкой ну ничего за 2 часа не понял, boundingRect как считался, так и считается.

boundingRect это необходимость, для определения видимых элементов. Естественно, что профайлер укажет "узким" местом на часто вызываемую функцию.
Можно воспользоваться intel vtune, им можно бесплатно пользоваться 30 дней.

NEbO · 15.03.2013, 09:32 **[ТС]**

Сообщение от Dmitriy_M

матрица должна быть 2x2

http://qt-project.org/doc/qt-4.8/qtransform.html
тут на русском, объяснение: http://htmlbook.ru/blog/matritsa-preobrazovanii
согласен, что операций немного, но все равно наврядли они укладываются в одну инструкцию. Впрочем, штука применяется довольно часто, и раз уж сделали аппаратное шифрование, то наверняка есть и способы очень быстрой трансформации.

Сообщение от Dmitriy_M

А зачем мне items?

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

Сообщение от Dmitriy_M

boundingRect это необходимость

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

@Dmitriy_M · 16.03.2013, 13:34

Можно попробовать сделать из сетки один большой Item

NEbO · 16.03.2013, 22:11 **[ТС]**

Сообщение от NEbO

Так вот, дальнейшее ускорение возможно за счет реализации совершенно другого алгоритма. И щас я вот взял, сделал просто одним итемом всю эту сетку. Угадайте, что получилось? правильно, 10000х10000 элементов, и они летают, как положено (разумеется, единовременно видно не более 300х200 ну или около того).

вы читаете мои мысли

NEbO · 17.03.2013, 22:28 **[ТС]**

ладно, знаю, что пишу много и читать меня сложно, порой даже очень.
Dmitriy_M, извините, если обидел, и спасибо, что пытались помочь.

NEbO 601 / 468 / 73 Регистрация: 22.01.2009 Сообщений: 1,180 Записей в блоге: 1
	15.03.2013, 00:32 [ТС]	14
	Сообщение от Night_Light я попробую посмотреть что вы ожидаете там увидеть? все что там есть, существенного для этой задачи, я описал: возьмите любую сцену и киньте на нее 300 на 300 PixmapItem-ов если 300х300 на вашем компьютере (тем более, MacOS -- там, возможно, все по другому) заработают без тормозов, увеличьте до 500х500. Суть не в размере, а в квадратичной сложности. С нуля реализовывать это -- оно даже лучше: мысли свежее. ну и еще я на QGraphicsView QWheelEvent переопределяю. Для перемещения по сцене достаточно просто включить QGraphicsView::setDragMode(QGraphicsView::ScrollHandDrag). Если нужно, я могу написать этот код. Но сами поймите, что тут дело не в кешировании и не в чем-либо еще. У меня получилось добиться хорошей производительности, для 200х200 точек, помоему уже все, что можно, выжал даже boundingRect поменьше стал времени отнимать, я точно не понял почему, я просто разные комбинации из флагов попробовал. Хотя, это может какие-то еще "артефакты" профайлера, они действительно какие-то глючные все, под винду. Так вот, дальнейшее ускорение возможно за счет реализации совершенно другого алгоритма. И щас я вот взял, сделал просто одним итемом всю эту сетку. Угадайте, что получилось? правильно, 10000х10000 элементов, и они летают, как положено (разумеется, единовременно видно не более 300х200 ну или около того). Нагрузка на процессор возникает, только когда я уж совсем очень быстро начинаю туда-сюда сцену крутить. И это без использования хитроумного группового кеширования (каждая ячейка прорисовывается отдельно. Для большого количества элементов это очень неэффективно, разумеется, а точность высокая там не нужна), которое в такой системе реализовать гораздо проще: все элементы хранятся в двумерном массиве, и соседи каждой ячейки тоже вычисляются за константное время! При этом модель всего этого дела укладывается в 10000х10000х16 бит (мне нужно хранить только индекс из массива-flyweight-а) = 200 мегабайт. ну вот примерно об этом я говорил, когда пытался объяснить, что мне нужно. Беда только в том, что сейчас придется реализовывать вручную все selection-ы, перемещения, ну и другие вещи, которые, при использовании "обычных" QGraphicsItem-ов, предоставлялись бы автоматически. Впрочем, опять же, у меня программа-редактор, мне все равно это все вручную делать: автоматически предоставляются только ну совсем уж базовые возможности. Так вот. Вроде бы, для себя все решил, и архитектуру чуть переделал, вроде все должно получиться нормально. И тем не менее, вопрос остается открытым. Зато теперь могу почетче сформулировать вопрос: "как переопределить стандартные алгоритмы нахождения, позиционирования, и определения границ элементов сцены?" (разумеется, с возможностью частичного делегирования на стандартные) 0

@Night_Light 17 / 17 / 0 Регистрация: 14.02.2009 Сообщений: 86
	12.03.2013, 13:18	2
	1) Почти уверен, что встречал в примерах Qt пример со сценой, зумингом и кучей элементов. 2) У меня ощущение, что когда-то видел эту проблему. Вы случайно не пробовали ставить вот этот флаг оптимизации: setCacheMode(QGraphicsItem::ItemCoordinateCache) 3) http://www.qtcentre.org/thread... -of-items-! 1

NEbO 601 / 468 / 73 Регистрация: 22.01.2009 Сообщений: 1,180 Записей в блоге: 1
	12.03.2013, 15:21 [ТС]	3
	из описания ItemCoordinateCache: Caching is enabled for the item's logical (local) coordinate system. , что для меня не подходит, по двум причинам: внутри отдельного item-а кешировать нечего, т.к. он представляет собой обычный pixmap. ну и второе: сам итем пока что рисуется в прямоугольнике (0,0,1,1), т.е. все координаты для рисования внутри него, в локальной системе координат представляют собой double. точность сильно страдает: все итемы буквально сливаются в одно пятно ну даже если б этого не происходило, и я бы перешел к целочисленным координатам, установив некий cellSize и умножал бы каждую координату на него, похоже, что из-за первого пункта производительность не возрастает, а только лишь падает. DeviceCoordinateCache стоял, щас его попробовал убрать, но от этого производительность не поменялась (а то и вообще стало чуть побыстрее работать). Вообще, как я понял из описания этих cacheMode-ов, они действуют только на рендеринг самого итема, увеличивая производительность за счет кеширования трансформаций... но у меня то обычные pixamp-ы, вложенных итемов нет, функция paint -- одна строчка, drawPixamp и все (ну да, да, еще два Q_UNUSED, но их я не считаю). тему эту, конечно, читал, но видимо, не обратил внимания на последнее сообщение, с prepareGeometryChange. Правда, пока еще не разобрался как им пользоваться, но его название мне нравится, возможно, именно оно поможет избавиться от кучи вычислений boundingRect. впрочем, какого-то процента производительности удалось еще добиться переопределением QGraphicsItem::contains(), collidesWithPath(), collidesWithItem(). пока что это не имеет никакого значения, т.к. все таки цикл, вызывающий boundingRect, является узким местом, но после его исправления, ради интереса можно будет попробовать поменять алгоритм на O(const) для того же contains(), скажем. и можно будет не кешировать тысячи этих итемов, находящихся в гриде, и будет вообще клева (пока что съедается около 200 мб памяти) и, значит, получится даже сделать огромное количество итемов вне грида. Хоть и маловероятно, что это кому-то пригодится при реальной работе, но все же. я очень люблю, когда программы работают очень быстро, особенно, когда они могут остается конечно проблема со scale, ибо там без полной перерисовки никак... а если еще попробовать включить анимацию (ну чтоб плавно масштабировалось), то будет плохо. Впрочем, это уже кеширование вида -- можно все рендерить во временный pixmap, и приближать/удалять сам этот pixmap. а когда scale отработает, перерисовыать (и то не сразу, может там два раза колесиком прокрутят, или три) с более высоким качеством. Правда, может есть какой-то способ как-то прозрачно это дело в программу внести? Иначе итемы все равно будут оставаться на сцене, это при каждом масштабировании придется их толи удалять, толи девать еще куда-то, а это, вроде как, довольно долго. да, Graphics View Framework реально прикольный... особенно, если получится переопредилить сами алгоритмы. Иногда же ведь порядок итемов на сцене строгий, а не от балды -- туда-сюда их кто-то раскидал. Поэтому, в общем случае, наверняка это очень полезная фишка. Раньше я как-то даже и не задумывался покопать в эту сторону, искал именно по many items slow performance, ну и потом по boundingRect еще немного погуглил. Видел на англоязычных форумах что-то подобное, но решения не находил. а щас вроде понял куда копать, думаю, что все получится. и даже не надо делать отдельный grid-item, который как-то должен эмулировать часть поведения сцены, для выделения, перемещения элементов... просто это какой-то костыль. А тут вродь все без костылей и очень красиво тьфу-тьфу, надеюсь, не сглажу Добавлено через 9 минут а, насчет идеи с pixmap-ом при scale, кажется, придумал: переопределить paint у сцены (да или даже у самого View, наверное, будет правильнее, т.к. относится все это к виду) и сделать два состояния: при масштабировании и без него. соответственно, во время scale рендерить только сам этот pixmap. а рендерить в pixmap item-ы можно чуть ли не в отдельном потоке с низким приоритетом, scale чуть задерживать, пока поток не отправит finished()-сигнал, ну и тогда уже начинать саму анимацию масштабирования. ну а можно и без потока попробовать. тоже вроде ничего. пс. нда, туплю я немного, извиняюсь 0

@Dmitriy_M 1443 / 1326 / 131 Регистрация: 20.03.2009 Сообщений: 4,689 Записей в блоге: 11
	12.03.2013, 15:53	4
	Есть замечательная демка 0

NEbO 601 / 468 / 73 Регистрация: 22.01.2009 Сообщений: 1,180 Записей в блоге: 1
	12.03.2013, 16:25 [ТС]	5
	ага, вот кстати, как раз щас посмотрел, чуть изменил, чтоб было видно побольше элементов. на данный момент она тормозит также (хотя, может чуть поменьше, подсмотрю еще флаги оптимизации), как моя программа (160к итемов). но тут оптимизировать, по сути, нечего. у каждого итема нет никаких ограничений на расположение: их можно подвинуть на любое расстояние. А вот в сетке координаты item-а можно вычислить строго, зная его местоположение в этой сетке. Да, конечно, я спрашивал и про флаги оптимизации, но это все лишь 2х-3х кратное (ну пусть даже 4-5-ти кратное) увеличение производительности. Согласитесь, зная координаты мышки, scale factor, а также то, что ни один элемент не может быть наложен на другой, вычислить итем под мышкой -- дело всего двух-трех операций трансформации матрицы 3х3, что дает константную сложность без кеша. Учитывая, как быстро сейчас, на SSE, производятся эти операции с матрицами, еще неизвестно, что быстрее -- вычислить хеш для того, чтобы считать из кеша это значение, или выполнить эти три трансформации. что, в итоге, увеличивает производительность не в разы, а в десятки (если не сотни) раз, даже на "нормальных" данных. Т.е. я говорю именно о том, чтобы убрать оверхед для данного частного случая, в виде такой вот сетки пример хороший, но он не показывает того, что мне нужно 0

@Dmitriy_M 1443 / 1326 / 131 Регистрация: 20.03.2009 Сообщений: 4,689 Записей в блоге: 11
	12.03.2013, 16:48	6
	Сообщение от NEbO у каждого итема нет никаких ограничений на расположение: их можно подвинуть на любое расстояние. Ничто не мешает привязать объект. Сообщение от NEbO Согласитесь, зная координаты мышки, scale factor, а также то, что ни один элемент не может быть наложен на другой, вычислить итем под мышкой -- дело всего двух-трех операций трансформации матрицы 3х3, что дает константную сложность без кеша можно без трансформаций обойтись. Сообщение от NEbO Учитывая, как быстро сейчас, на SSE, производятся эти операции с матрицами, еще неизвестно, что быстрее -- вычислить хеш для того, чтобы считать из кеша это значение, или выполнить эти три трансформации. Может ошибаюсь, но SSE это векторные операции, и что бы перемножать матрицы требуется написать специальный код использующий инструкции SSE. 0

@Night_Light 17 / 17 / 0 Регистрация: 14.02.2009 Сообщений: 86
	12.03.2013, 17:52	9
	Сообщение от NEbO не обратил внимания на последнее сообщение, с prepareGeometryChange NEbO, ага, я именно это имел в виду в качестве возможного варианта решения 1

@Night_Light 17 / 17 / 0 Регистрация: 14.02.2009 Сообщений: 86
	12.03.2013, 18:42	11
	NEbO, если бы я этим пользовался, то сказал бы кажется, что-то есть тут http://www.qtcentre.org/archiv... 49021.html а именно: A shortlist to check (as always with graphics items): 1. Is my bounding rect defined correctly (e.g. is it independent of the placement of the item)? 2. Is my shape defined within the bounding rect? 3. Is my paint() routine painting only within the bounding rect? 4. Am I calling prepareGeometryChange() each time the bounging rect is going to change? Т.е. по идее у Вас должны быть переопределены boundingRect() и shape() По ссылке, вроде, проблема была из-за того, что boundingRect() возвращал невалидное значение. 0

NEbO 601 / 468 / 73 Регистрация: 22.01.2009 Сообщений: 1,180 Записей в блоге: 1
	12.03.2013, 19:28 [ТС]	12
	а, не, как я понимаю, с prepareGeometryChange-ом все в порядке. я ж реально все итемы добавляю в QGraphicsItemGroup, т.к. хочу сделать отдельно грид со своими свойствами... и там при добавлении в него каждый раз вызывается этот prepare, проверил по исходникам. только вот толку что-то немного: эта функция же должна вызываться, чтобы оповестить сцену, что мол размеры поменялись, обновляй индекс. но я что-то не вижу, чтоб что-то изменялось в плане вызовов самого boundingRect (ну boundingRect в индексе и boundingRect просто -- разные вещи, понятно, что на обновление индекса уходит больше времени)... такое чувство, что я просто не выставляю какой-то флаг, чтоб зафиксировать размер итема. но такого флага я что-то не наблюдаю. наверное, опять стоит покопаться в исходниках... Не по теме: одна беда, что никак не могу нормального профайлера найти. обычный gprof под виндой не строит call-graph, и я не вижу, откуда вызывается boundingRect, vtune у меня не запустился почему-то (может, изза семерки, а на рутрекере явно не самый последний), амд-шный профайлер указывает вообще непонятно на что, а AQTime сильнейше тормозит, и изза этих тормозов он вообще вправе подумать на любую функцию внутри цикла перерисовки сцены. пока что мне показал, что дольше всех выполняется qMax или что-то в этом роде:) можно, конечно, повозиться с флагами для vc++, заинлайнить половину всего, и прикрутить отладочную информацию, но боюсь, от этого он может начать показывать вообще левые вещи... например, пробовал в gcc компилить с -gstabs+ -g -gp -O2, в выводе вообще какая-то полная ерунда, boundingRect он не показывает, показывает какую-то другую функцию, которая вызывалась ровно столько же, сколько boundingRect (на котором у меня свой счетчик). То есть отладочная информация как-то сбивается. наверное, с -g надо поиграться, но я пока не копал в эту сторону, просто боюсь, что даже знание всех функций мало чем поможет, да и без call-graph-а как то не то. 0

@Night_Light 17 / 17 / 0 Регистрация: 14.02.2009 Сообщений: 86
	13.03.2013, 11:29	13
	Если возможно, можете скинуть мне исходники, я попробую посмотреть, но не в самое ближайшее время На счёт профайлера под Windows я не в курсе, мне хватает xCode Instruments под MacOS для Qt кода. 0

@Dmitriy_M 1443 / 1326 / 131 Регистрация: 20.03.2009 Сообщений: 4,689 Записей в блоге: 11
	15.03.2013, 08:38	15
	Сообщение от NEbO так как указать QGraphicsScene, чтобы для НЕКОТОРЫХ элементов он работал по вашему алгоритму? (items() не виртуальный, наверняка с ним будут проблемы). А зачем мне items? О Сообщение от NEbO Не по теме: насчет оптимизации под sse вы правы, за исключением того, что матрицу транформации в иделе можно наверняка представить в виде обычного массива (9 элементов), правда инструкций sse, работающих с 9ю элементами по 80 бит (double) я пока не встречал. про математику трансформации я точно не знаю (определитель считается и умножается на каждый элемент?), но если нужно будет, я найду У тебя 2D, каждый элемент пространства вектор из двух координат, по идее и матрица должна быть 2x2, если это так, то пересчет координат это 4 умножения и 2 сложения, что должно быстро обрабатываться при клике. Сообщение от NEbO скажите пожалуйста, а как им пользоваться? чувствую себя блондинкой ну ничего за 2 часа не понял, boundingRect как считался, так и считается. boundingRect это необходимость, для определения видимых элементов. Естественно, что профайлер укажет "узким" местом на часто вызываемую функцию. Можно воспользоваться intel vtune, им можно бесплатно пользоваться 30 дней. 1

	17.03.2013, 22:28

NEbO 601 / 468 / 73 Регистрация: 22.01.2009 Сообщений: 1,180 Записей в блоге: 1
	15.03.2013, 09:32 [ТС]	16
	Сообщение от Dmitriy_M матрица должна быть 2x2 http://qt-project.org/doc/qt-4.8/qtransform.html тут на русском, объяснение: http://htmlbook.ru/blog/matritsa-preobrazovanii согласен, что операций немного, но все равно наврядли они укладываются в одну инструкцию. Впрочем, штука применяется довольно часто, и раз уж сделали аппаратное шифрование, то наверняка есть и способы очень быстрой трансформации. Сообщение от Dmitriy_M А зачем мне items? я не нашел другого способа явно переопределить стандартный алгоритм нахождения элементов сцены в указанном прямоугольнике. Сообщение от Dmitriy_M boundingRect это необходимость если приведете ссылку, где четко описано, что не существует возможности переопределения этого стандартного поведения, то, думаю, что вопрос можно закрыть, и другого способа, как ручная перерисовка и ручное контролирование, не существует 0

@Dmitriy_M 1443 / 1326 / 131 Регистрация: 20.03.2009 Сообщений: 4,689 Записей в блоге: 11
	16.03.2013, 13:34	17
	Можно попробовать сделать из сетки один большой Item 1

NEbO 601 / 468 / 73 Регистрация: 22.01.2009 Сообщений: 1,180 Записей в блоге: 1
	16.03.2013, 22:11 [ТС]	18
	Сообщение от NEbO Так вот, дальнейшее ускорение возможно за счет реализации совершенно другого алгоритма. И щас я вот взял, сделал просто одним итемом всю эту сетку. Угадайте, что получилось? правильно, 10000х10000 элементов, и они летают, как положено (разумеется, единовременно видно не более 300х200 ну или около того). вы читаете мои мысли 0

NEbO 601 / 468 / 73 Регистрация: 22.01.2009 Сообщений: 1,180 Записей в блоге: 1
	17.03.2013, 22:28 [ТС]	19
	ладно, знаю, что пишу много и читать меня сложно, порой даже очень. Dmitriy_M, извините, если обидел, и спасибо, что пытались помочь. 0