[Qt-interest] Best way to update 10^5 items

[Oliver.Knoll at comit.ch]

Ole Streicher wrote on Tuesday, September 29, 2009 4:57 PM:

>> ...
>> Typically you don't need to update *all* objects; unless ...
> The objects represent channels of some device; I have about 100.000
> of them. 

Are we talking about "modern age TV stations?" ;) (*duck and cover*)

>> So your problem is the typical graphic scenario: "Which objects are
>> actually visible on the screen?" ...
> All. Thats the problem.

Okay, so the "extreme case" seems to be your normal scenario ;)

>> object, why not "approximate" it with a simple rectangle?
> 
> They are already rectangles.

Okay then, I guess you can't much more simplify a rectangle...

> 
>> And if it becomes even smalller, why not just draw a dot?
> 
> Since the view is zoomable: how can I do this?

Well, given the "object size in world coordinates" and the zoom factor, you could quickly calculate the "bounding box" in "screen coordinates". That is, you would basically calculate "how big becomes the object on screen (approximate bounding box), after all transformations (zoom) have been applied?". If you find out that the final bounding box is less than a given threshold, you would simplify the drawing operation, for example filled rectanlge -> rectangle (no fill) -> dot.

But as you say, your "channels" are already only 4 x 4 pixels, you won't gain much here I guess.

> 
>> Turn off anti-aliasing for small objects,
> 
> Is turned off generally.

Okay then.

> 
>> don't draw contour lines
> 
> The pen is set to NoPen. Is this what you mean?

Uhh, I guess so. To be honest I was merely quoting from the Qt docs about the "chips demo", as far as my memory served right. And one optimization I also had in mind was setting the pen width (when drawing lines) to 0, so no "sub-pixel precission painting" is applied. Which is okay if you are using "integer pixel coordinates" ... or so.
> 
>> etc. etc.
> 
>> Actually the Qt "Chips" graphic demo makes use of exactly these
>> ...
> This was my starting point and the reason that I decided to use
> QGraphicsScene for my implementation. However, it looks quite slow in
> my case.  

Okay then, maybe it is your code how you draw the objects. E.g. the following could be very different in performance:

// pseudo-code
void paint() {
  foreach (Object object : m_objects) {
    // calling a method 100'000 times can be SLOOOOW!
    object.paint();
  }
}

versus

void paint() {
  foreach (Object object: m_objects) {
    painter.drawLine(object.x1, object.y1, object.x2, object.y2);
  }
}

assuming that all objects have the same painting method (all objects are of the same type). In other words: try to reduce the number of method calls (and yes, even nowadays method calls are expensive, when it comes to CPU cycles they consume! Especially in graphic scenarios, where you iterate over lots of objects).

In the same manner try to use

  http://doc.trolltech.com/4.5/qpainter.html#drawPoints

instead of 

  http://doc.trolltech.com/4.5/qpainter.html#drawPoint

(n times) etc.

This reduces the number of method calls as well.


Also iterating over plain arrays (with pointer arithmethic, instead of indices) instead of linked lists or whatever could help:

  Point myPoints[n];
  Point *point;

  point = myPoints[0];
  while (...) {
    doSomething(point);
    // go to next point
     point++;
  }

Well, you get the idea... but off course it really depends where your actual bottleneck is in your case! And for most scenarios using a http://doc.trolltech.com/4.5/qvector.html is "fast enough", compared to a "plain C array" (my personal taste: I go for the "higher level data structures", for the sake of simplicity and correctness, even if I sacrifice 20% of performance initially - you can "hardcore-optimize" later on!). If you optimize on the wrong end, you might just gain another 5% of extra performance... if at all.


Hope that helps somewhat.
  Cheers, Oliver

-- 
Oliver Knoll
Dipl. Informatik-Ing. ETH
COMIT AG - ++41 79 520 95 22