GraphicsView performance problems

[wysota]

I really suggest to recompile Qt with profiling information. You're shooting blind now. Profiling will give you the exact bottleneck point. Furthermore make sure your app is compiled correctly, I think you should be able to have a decomposition of the drawBackground() method in the profiling information as well. It should then tell you which part of the method takes most time and it should be possible to obtain without recompiling Qt.

[Gopala Krishna]

I really suggest to recompile Qt with profiling information. You're shooting blind now. Profiling will give you the exact bottleneck point. Furthermore make sure your app is compiled correctly, I think you should be able to have a decomposition of the drawBackground() method in the profiling information as well. It should then tell you which part of the method takes most time and it should be possible to obtain without recompiling Qt.

ok finally I agree. You are right . I guess there is no decomposition because most method are inlined. Well I'll do that recompilation tomorrow(nice job in the weekend )

[wysota]

First do this (or something simmilar):

void drawLines(QPainter *painter, QVarLengthArray<QLineF, 100> &lines){
         painter->drawLines(lines.data(), lines.size());
}
 
void setupArray(QVarLengthArray<QLineF, 100> &lines){
         const int gridSize = 25;
         qreal left = int(rect.left()) - (int(rect.left()) % gridSize);
         qreal top = int(rect.top()) - (int(rect.top()) % gridSize);
         for (qreal x = left; x < rect.right(); x += gridSize)
            lines.append(QLineF(x, rect.top(), x, rect.bottom()));
         for (qreal y = top; y < rect.bottom(); y += gridSize)
            lines.append(QLineF(rect.left(), y, rect.right(), y));
}
void drawBackground(QPainter *painter, const QRectF &rect){
         painter->setPen(QPen(Qt::darkGreen,0));         
         QVarLengthArray<QLineF, 100> lines;
         setupArray(lines);
         drawLines(painter, lines);
}

void drawLines(QPainter *painter, QVarLengthArray<QLineF, 100> &lines){
         painter->drawLines(lines.data(), lines.size());
}

void setupArray(QVarLengthArray<QLineF, 100> &lines){
         const int gridSize = 25;
         qreal left = int(rect.left()) - (int(rect.left()) % gridSize);
         qreal top = int(rect.top()) - (int(rect.top()) % gridSize);
         for (qreal x = left; x < rect.right(); x += gridSize)
            lines.append(QLineF(x, rect.top(), x, rect.bottom()));
         for (qreal y = top; y < rect.bottom(); y += gridSize)
            lines.append(QLineF(rect.left(), y, rect.right(), y));
}
void drawBackground(QPainter *painter, const QRectF &rect){
         painter->setPen(QPen(Qt::darkGreen,0));         
         QVarLengthArray<QLineF, 100> lines;
         setupArray(lines);
         drawLines(painter, lines);
}

To copy to clipboard, switch view to plain text mode 

This should allow you to measure how much time does it take to setup the array and how much to paint it.

[Gopala Krishna]

First do this (or something simmilar):

void drawLines(QPainter *painter, QVarLengthArray<QLineF, 100> &lines){
         painter->drawLines(lines.data(), lines.size());
}
 
void setupArray(QVarLengthArray<QLineF, 100> &lines){
         const int gridSize = 25;
         qreal left = int(rect.left()) - (int(rect.left()) % gridSize);
         qreal top = int(rect.top()) - (int(rect.top()) % gridSize);
         for (qreal x = left; x < rect.right(); x += gridSize)
            lines.append(QLineF(x, rect.top(), x, rect.bottom()));
         for (qreal y = top; y < rect.bottom(); y += gridSize)
            lines.append(QLineF(rect.left(), y, rect.right(), y));
}
void drawBackground(QPainter *painter, const QRectF &rect){
         painter->setPen(QPen(Qt::darkGreen,0));         
         QVarLengthArray<QLineF, 100> lines;
         setupArray(lines);
         drawLines(painter, lines);
}

void drawLines(QPainter *painter, QVarLengthArray<QLineF, 100> &lines){
         painter->drawLines(lines.data(), lines.size());
}

void setupArray(QVarLengthArray<QLineF, 100> &lines){
         const int gridSize = 25;
         qreal left = int(rect.left()) - (int(rect.left()) % gridSize);
         qreal top = int(rect.top()) - (int(rect.top()) % gridSize);
         for (qreal x = left; x < rect.right(); x += gridSize)
            lines.append(QLineF(x, rect.top(), x, rect.bottom()));
         for (qreal y = top; y < rect.bottom(); y += gridSize)
            lines.append(QLineF(rect.left(), y, rect.right(), y));
}
void drawBackground(QPainter *painter, const QRectF &rect){
         painter->setPen(QPen(Qt::darkGreen,0));         
         QVarLengthArray<QLineF, 100> lines;
         setupArray(lines);
         drawLines(painter, lines);
}

To copy to clipboard, switch view to plain text mode 

This should allow you to measure how much time does it take to setup the array and how much to paint it.

Ok I did that, the profile now says

Flat profile:

Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls Ts/call Ts/call name
50.05 0.02 0.02 Node:: paint(QPainter*, QStyleOptionGraphicsItem const*, QWidget*)
25.03 0.03 0.01 GridScene::drawBackground(QPainter*, QRectF const&)
25.03 0.04 0.01 Resistor::boundingRect() const
0.00 0.04 0.00 192004 0.00 0.00 QVarLengthArray<QLineF, 100>::realloc(int, int)
0.00 0.04 0.00 36506 0.00 0.00 GridScene::setupArray(QVarLengthArray<QLineF, 100>&, QRectF const&)
0.00 0.04 0.00 36506 0.00 0.00 GridScene::drawLines(QPainter*, QVarLengthArray<QLineF, 100>&)
0.00 0.04 0.00 1 0.00 0.00 global constructors keyed to _ZN9GridScene9drawLinesEP8QPainterR15QVarLengthArr ayI6QLineFLi100EE
0.00 0.04 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)

Further

Call graph (explanation follows)


granularity: each sample hit covers 2 byte(s) for 24.97% of 0.04 seconds

index % time self children called name
<spontaneous>
[1] 50.0 0.02 0.00 Node:: paint(QPainter*, QStyleOptionGraphicsItem const*, QWidget*) [1]
-----------------------------------------------
<spontaneous>
[2] 25.0 0.01 0.00 GridScene::drawBackground(QPainter*, QRectF const&) [2]
0.00 0.00 36506/36506 GridScene::setupArray(QVarLengthArray<QLineF, 100>&, QRectF const&) [12]
0.00 0.00 36506/36506 GridScene::drawLines(QPainter*, QVarLengthArray<QLineF, 100>&) [13]
-----------------------------------------------
<spontaneous>
[3] 25.0 0.01 0.00 Resistor::boundingRect() const [3]
-----------------------------------------------
0.00 0.00 192004/192004 GridScene::setupArray(QVarLengthArray<QLineF, 100>&, QRectF const&) [12]
[11] 0.0 0.00 0.00 192004 QVarLengthArray<QLineF, 100>::realloc(int, int) [11]
-----------------------------------------------
0.00 0.00 36506/36506 GridScene::drawBackground(QPainter*, QRectF const&) [2]
[12] 0.0 0.00 0.00 36506 GridScene::setupArray(QVarLengthArray<QLineF, 100>&, QRectF const&) [12]
0.00 0.00 192004/192004 QVarLengthArray<QLineF, 100>::realloc(int, int) [11]
-----------------------------------------------
0.00 0.00 36506/36506 GridScene::drawBackground(QPainter*, QRectF const&) [2]
[13] 0.0 0.00 0.00 36506 GridScene::drawLines(QPainter*, QVarLengthArray<QLineF, 100>&) [13]
-----------------------------------------------
0.00 0.00 1/1 __do_global_ctors_aux [25]
[14] 0.0 0.00 0.00 1 global constructors keyed to _ZN9GridScene9drawLinesEP8QPainterR15QVarLengthArr ayI6QLineFLi100EE [14]
0.00 0.00 1/1 __static_initialization_and_destruction_0(int, int) [15]
-----------------------------------------------
0.00 0.00 1/1 global constructors keyed to _ZN9GridScene9drawLinesEP8QPainterR15QVarLengthArr ayI6QLineFLi100EE [14]
[15] 0.0 0.00 0.00 1 __static_initialization_and_destruction_0(int, int) [15]
-----------------------------------------------

[camel]

[2] 25.0 0.01 0.00 GridScene::drawBackground(QPainter*, QRectF const&) [2]
0.00 0.00 36506/36506 GridScene::setupArray(QVarLengthArray<QLineF, 100>&, QRectF const&) [12]
0.00 0.00 36506/36506 GridScene::drawLines(QPainter*, QVarLengthArray<QLineF, 100>&) [13]

That looks really weird.
The reason probably once again that the time is spent inside of Qt-Code and not yours, so sadly that does not help.
Or it could have been inlined, again not really helpfull :-/


Have you tried valgrind/callgrind and KCacheGrind as a profiler? It is rather nice :-)

[wysota]

That looks really weird.
The reason probably once again that the time is spent inside of Qt-Code and not yours, so sadly that does not help.

These figures are wrong. All functions from inside Qt should be counted on behalf of the functions calling them and here all functions have nothing but zeros. The application needs to run longer.

Or it could have been inlined, again not really helpfull :-/

Yes, that's possible, especially if they were implemented inside the class header and optimisations were enabled.

You must be sure to disable inlining optimisations. You can use -fno-inline to disable inlining.

[Gopala Krishna]

Yup! you both are right. Anyway I am recompiling Qt tomorrow. I'll surely post after I do that. In the meanwhile I'd like to inform you people that I have never used cachegrind. Is that better than gprof ? If yes how should I use that ?

[camel]

Did you try my last modification? Did it change anything for you?

Yup! you both are right. Anyway I am recompiling Qt tomorrow. I'll surely post after I do that. In the meanwhile I'd like to inform you people that I have never used cachegrind. Is that better than gprof ? If yes how should I use that ?

You do not need to compile anything special (besides DEBUG of course ;-)

Then call

$valgrind --tool=callgrind ./YOUR_APP

this will produce a file called callgrind.out.PID_OF_PROCESS

then you can call

$kcachegrind callgrind.out.PID_OF_PROCESS

http://kcachegrind.sourceforge.net/cgi-bin/show.cgi

[Gopala Krishna]

Did you try my last modification? Did it change anything for you?



You do not need to compile anything special (besides DEBUG of course ;-)

Then call


this will produce a file called callgrind.out.PID_OF_PROCESS

then you can call


http://kcachegrind.sourceforge.net/cgi-bin/show.cgi

Thanks ! Here is the output as attachment
EDIT: My quota of attachment is almost over. I'll update a bit later.

[wysota]

I have modified my application which uses QGraphicsView framework to draw a grid simmilar to yours and I implemented it in a worst possible way:

void drawBackground ( QPainter * painter, const QRectF & rect ){
  static QPen p(QColor(150,150,150));
  painter->setPen(p);
  for(int row=10+((int)(rect.top())/10)*10; row<rect.bottom(); row+=10){
    for(int col = 10+((int)(rect.left())/10)*10; col<rect.right(); col+=10)
       painter->drawPoint(col, row);
  }
}

void drawBackground ( QPainter * painter, const QRectF & rect ){
  static QPen p(QColor(150,150,150));
  painter->setPen(p);
  for(int row=10+((int)(rect.top())/10)*10; row<rect.bottom(); row+=10){
    for(int col = 10+((int)(rect.left())/10)*10; col<rect.right(); col+=10)
       painter->drawPoint(col, row);
  }
}

To copy to clipboard, switch view to plain text mode 

Profiling info (compiled with -fno-inline -ggdb -pg) looks like this:

%   cumulative   self              self     total
 time   seconds   seconds    calls  us/call  us/call  name
 33.33      0.02     0.02  1547664     0.01     0.01  QRectF::right() const
 33.33      0.04     0.02                             SpecScene::drawBackground(QPainter*, QRectF const&)
 16.67      0.05     0.01  1527572     0.01     0.01  QPainter::drawPoint(int, int)

%   cumulative   self              self     total
 time   seconds   seconds    calls  us/call  us/call  name
 33.33      0.02     0.02  1547664     0.01     0.01  QRectF::right() const
 33.33      0.04     0.02                             SpecScene::drawBackground(QPainter*, QRectF const&)
 16.67      0.05     0.01  1527572     0.01     0.01  QPainter::drawPoint(int, int)

To copy to clipboard, switch view to plain text mode 

As you see 33% of the application time is spent in drawBackground and half of it is used to calculate QRectF::right() (which makes sense as it gets calculated in each iteration of the loop) and pretty much is used to actually draw the points.

index % time    self  children    called     name
                                                 <spontaneous>
[1]     83.3    0.02    0.03                 SpecScene::drawBackground(QPainter*, QRectF const&) [1]
                0.02    0.00 1547627/1547664     QRectF::right() const [2]
                0.01    0.00 1527572/1527572     QPainter::drawPoint(int, int) [3]
                0.00    0.00   20635/20651       QRectF::bottom() const [35]
                0.00    0.00   20055/20055       QRectF::left() const [36]
                0.00    0.00     580/580         QRectF::top() const [93]
                0.00    0.00       1/702         QColor::QColor(int, int, int, int) [92]

index % time    self  children    called     name
                                                 <spontaneous>
[1]     83.3    0.02    0.03                 SpecScene::drawBackground(QPainter*, QRectF const&) [1]
                0.02    0.00 1547627/1547664     QRectF::right() const [2]
                0.01    0.00 1527572/1527572     QPainter::drawPoint(int, int) [3]
                0.00    0.00   20635/20651       QRectF::bottom() const [35]
                0.00    0.00   20055/20055       QRectF::left() const [36]
                0.00    0.00     580/580         QRectF::top() const [93]
                0.00    0.00       1/702         QColor::QColor(int, int, int, int) [92]

To copy to clipboard, switch view to plain text mode 

As you see it is actually more time consuming to calculate the rectangle coords than to draw points!

Some facts:
- I use Qt4.2.2 on i686 Linux,
- I didn't use antialiasing,
- I didn't use scaling (so I have an identity matrix when it comes to viewport-window transformations),
- scene size was about 1200x1000,
- I didn't compile Qt with profiling information (so I guess it's not required after all),
- I got detailed info about both mine and Qt methods,
- the result is pretty fast.

I got a pretty good result, but I didn't suffer from viewport-window transformations which might be your case if you scale the view. I didn't use antialiasing for my view, as points are points - they don't suffer from the aliasing effect. I could easily improve the implementation by calculating rectangle coordinates once per drawBackground() which should reduce the execution effort by half.

It is up to you to do the interpretation of the results. My impression is that it is not really drawBackground() which causes the slowdown - maybe it is just called too often by other parts of the system? Maybe you abuse update()?

[camel]

I have modified my application which uses QGraphicsView framework to draw a grid simmilar to yours and I implemented it in a worst possible way:

Profiling info (compiled with -fno-inline -ggdb -pg) looks like this:

%   cumulative   self              self     total
 time   seconds   seconds    calls  us/call  us/call  name
 33.33      0.02     0.02  1547664     0.01     0.01  QRectF::right() const
 33.33      0.04     0.02                             SpecScene::drawBackground(QPainter*, QRectF const&)
 16.67      0.05     0.01  1527572     0.01     0.01  QPainter::drawPoint(int, int)

%   cumulative   self              self     total
 time   seconds   seconds    calls  us/call  us/call  name
 33.33      0.02     0.02  1547664     0.01     0.01  QRectF::right() const
 33.33      0.04     0.02                             SpecScene::drawBackground(QPainter*, QRectF const&)
 16.67      0.05     0.01  1527572     0.01     0.01  QPainter::drawPoint(int, int)

To copy to clipboard, switch view to plain text mode 

Well, if you disable inlining, no wonder right() is expensive. calling a function 1.5 Million times just takes its time...inlining is there for a reason ;-)

So I would not call this run very exemplary... :-)

[camel]

just a note:
If you like to profile further into the drawing part,
you need to call:

valgrind --tool=callgrind --seperate-callers=5 --seperate-recs=10 ./YOUR_APP

Otherwise you will get "cycles", which is not very helpfull in this task..

BUT: this takes up much more memory to analyze later...

[camel]

Hi,

well I just love to play with this... ;-)


Here is another (and much faster) way to write the drawBackground function...with the added niceness that it helps avoiding the color errors ;-)

You might want to check if this survives zooming etc.

void drawBackground(QPainter *painter, const QRectF &rect)
      {
         const int gridSize = 25;
 
        if (backgroundCache.isNull()) {
            backgroundCache = QPixmap(gridSize, gridSize);
            const int middle = gridSize / 2;
            QPainter backgroundPainter(&backgroundCache);
            backgroundPainter.setRenderHints(painter->renderHints());
            backgroundPainter.fillRect(QRect(0, 0, gridSize, gridSize), QBrush(Qt::white));
            backgroundPainter.setPen(backgroundPen);
            backgroundPainter.setBrush(backgroundBrush);
            backgroundPainter.drawLine(0, middle, gridSize, middle);
            backgroundPainter.drawLine(middle, 0, middle, gridSize);
        }
 
         const int realLeft = static_cast<int>(std::floor(rect.left()));
         const int realRight = static_cast<int>(std::ceil(rect.right()));
         const int realTop = static_cast<int>(std::floor(rect.top()));
         const int realBottom = static_cast<int>(std::ceil(rect.bottom()));
 
 
         const int firstLeftGridLine = realLeft - (realLeft % gridSize);
         const int firstTopGridLine = realTop - (realTop % gridSize);
 
 
         QPainterPath background;
         for (int x = firstLeftGridLine; x < realRight; x += gridSize) {
            for (int y = firstTopGridLine; y < realBottom; y += gridSize) {
                painter->drawPixmap(x, y, backgroundCache);
            }
        }
      }

void drawBackground(QPainter *painter, const QRectF &rect)
      {
         const int gridSize = 25;

        if (backgroundCache.isNull()) {
            backgroundCache = QPixmap(gridSize, gridSize);
            const int middle = gridSize / 2;
            QPainter backgroundPainter(&backgroundCache);
            backgroundPainter.setRenderHints(painter->renderHints());
            backgroundPainter.fillRect(QRect(0, 0, gridSize, gridSize), QBrush(Qt::white));
            backgroundPainter.setPen(backgroundPen);
            backgroundPainter.setBrush(backgroundBrush);
            backgroundPainter.drawLine(0, middle, gridSize, middle);
            backgroundPainter.drawLine(middle, 0, middle, gridSize);
        }

         const int realLeft = static_cast<int>(std::floor(rect.left()));
         const int realRight = static_cast<int>(std::ceil(rect.right()));
         const int realTop = static_cast<int>(std::floor(rect.top()));
         const int realBottom = static_cast<int>(std::ceil(rect.bottom()));


         const int firstLeftGridLine = realLeft - (realLeft % gridSize);
         const int firstTopGridLine = realTop - (realTop % gridSize);


         QPainterPath background;
         for (int x = firstLeftGridLine; x < realRight; x += gridSize) {
            for (int y = firstTopGridLine; y < realBottom; y += gridSize) {
                painter->drawPixmap(x, y, backgroundCache);
            }
        }
      }

To copy to clipboard, switch view to plain text mode 

Have a nice day :-)

[Gopala Krishna]

Hi,

well I just love to play with this... ;-)


Here is another way to write the drawBackground function...with the added niceness that it helps avoiding the color errors ;-)

You might want to check if this survives zooming etc.

void drawBackground(QPainter *painter, const QRectF &rect)
      ...

void drawBackground(QPainter *painter, const QRectF &rect)
      ...

To copy to clipboard, switch view to plain text mode 

Have a nice day :-)

Not bad idea! That problem solved !!! Thanks a lot.
Now the next problem is performance !
A good day to you too

[Gopala Krishna]

just a note:
If you like to profile further into the drawing part,
you need to call:


Otherwise you will get "cycles", which is not very helpfull in this task..

BUT: this takes up much more memory to analyze later...

I get the following error

valgrind: Bad option '--seperate-callers=5'; aborting.

I am trying to analyse the code as it is now. I am getting lost here and there but kcachegrind is a cool tool. Needs some time to get used to it. Thanks for helping me till now. I'll continue with this tomorrow.

[camel]

I get the following error
valgrind: Bad option '--seperate-callers=5'; aborting.

I think they changed the option names during 3.1 and 3.2 (which I use)

try:
valgrind --tool=callgrind --fn-caller=5 --fn-recursion=10 ./YOUR_APP

[wysota]

Well, if you disable inlining, no wonder right() is expensive. calling a function 1.5 Million times just takes its time...inlining is there for a reason ;-)

So I would not call this run very exemplary... :-)

It means that QRectF::right() takes longer than QPainter::drawPoint() and right() is not a very complex method

After getting rid of the right() and bottom() calls inside the loop the result of profiling is as follows:

50.00      0.06     0.06                             SpecScene::drawBackground(QPainter*, QRectF const&)
 25.00      0.09     0.03  1460235     0.02     0.02  QPoint::QPoint(int, int)
 16.67      0.11     0.02  1454915     0.01     0.03  QPainter::drawPoint(int, int)

50.00      0.06     0.06                             SpecScene::drawBackground(QPainter*, QRectF const&)
 25.00      0.09     0.03  1460235     0.02     0.02  QPoint::QPoint(int, int)
 16.67      0.11     0.02  1454915     0.01     0.03  QPainter::drawPoint(int, int)

To copy to clipboard, switch view to plain text mode 

The QPoint constructor is called by QPainter::drawPoint, so we can forget about it. The whole method takes over 90% of the whole application time and gives a total of less than 0.1s. That's not much

It is important to see what the bottleneck is instead of shooting blind. No matter how much you optimise QPainter::drawLines() if it's not the bottleneck, you won't get a decent improvement.

In my opinion it would be much simpler and faster to simply apply a backgroundBrush with the grid to the scene and forget about points and lines. You wouldn't get any painter paths then, no floating point operations. The only thing that could slow down the process is the matrix transformation, so try to avoid it.

[camel]

It is important to see what the bottleneck is instead of shooting blind. No matter how much you optimise QPainter::drawLines() if it's not the bottleneck, you won't get a decent improvement.

That is why I look into my KCachgrind and follow the callgraph and sources ;-)

The problem is not drawPoints, as that does not do much.

The problem with drawLines and friends is that it often (with antialiasing) first creates a painterpath from those lines and then paints them. This takes time, not least because of memory allocation.

This is why I said use painterpaths directly.

Optimizing the returnvalue of boundingrect and shape is so easy (and makes the code much nicer in my opinion) so that I would not even consider it a optimization, its just nicer programming. (besides helping during run-time of course ;-)

In my opinion it would be much simpler and faster to simply apply a backgroundBrush with the grid to the scene and forget about points and lines. You wouldn't get any painter paths then, no floating point operations. The only thing that could slow down the process is the matrix transformation, so try to avoid it.

I cuncur there, see my last post about the drawbackground function.
To use a background brush would be the logical next step ;-)

[wysota]

The problem with drawLines and friends is that it often (with antialiasing) first creates a painterpath from those lines and then paints them. This takes time, not least because of memory allocation.

This is why I said use painterpaths directly.

If you disable antialiasing, there is a possibility that painter paths will not be used. And there is no point in having antialiasing enabled for drawing horizontal or vertical lines, as these don't suffer from the aliasing effect. You can safely temporarily disable antialiasing while painting those.

bool isAA = painter->renderHints() & QPainter::Antialiasing;
painter->setRenderHint(QPainter::Antialiasing, false);
painter->drawLines(...);
painter->setRenderHint(QPainter::Antialiasing, isAA);

bool isAA = painter->renderHints() & QPainter::Antialiasing;
painter->setRenderHint(QPainter::Antialiasing, false);
painter->drawLines(...);
painter->setRenderHint(QPainter::Antialiasing, isAA);

To copy to clipboard, switch view to plain text mode 

Another possibility of painter paths being active is that there is scaling involved. But while zooming in, the number of lines needed to draw should decrease. While zooming out on the other hand you can draw fewer lines as too many of them will clutter the scene anyway.

You can also store the path in a member variable and then only draw the path on the painter. But I think using a background brush will be much faster, especially with smooth scaling disabled.

[Gopala Krishna]

In my opinion it would be much simpler and faster to simply apply a backgroundBrush with the grid to the scene and forget about points and lines.

Well I tried even this. That is not the problem. First of all the main problem is while moving "many items" together. For example in the above eg the performance goes down if you select all resistors and move - thats about 80 items at a time!!! (20 resistors,40 nodes, 20 text items) . Here to get sufficient performance the area to be updated should be selected appropriately and efficiently so that the scene is updated least number of times.

Further I have a question - is the the bsp indexing causing these performance problems ?

Further I would like to inform that I am not using any matrix transformations. All these are just on regular matrix.