Thursday, August 13, 2009
Is the X11 engine slower than raster just because of the drivers?
Here was i profiling KSquares and discovered that when painting an antialiased dashed line using the Qt X11 engine you hit a code path in which Qt tries to detect for each dash of the line which other dashes intersect with it, that's right a O(n^2) calculation that makes no sense, that since you are drawing a line the intersections it will find it's that a dash only intersects with itself. So seeing things like that i wonder if the Raster engine is faster because X11 drivers suck we have been told or it's that the X11 engine code is not as good as it could be. I've checked and the raster engine has no such "bad" loop
Subscribe to:
Post Comments (Atom)
12 comments:
oh how nice would it be if somebody fixes that :-) graphics rendering and X11 code sounds still to voodoo black magic stuff to me to look at it..
And yes, the X11 performance is simply horrible (try to make an animated wallpaper and look how many frames you can get by drawing a fullscreen qpixmap.. not enough, and even if you get near a acceptable framerate, you kill the cpu, might not be related, but nonetheless, not fun)
Ciao Albert,
Don't really know. Just today I tested FotoWall with Raster and with a crowded workspace the speedup is like 4x times the X11 version.
I'd like to know the answer to this question too ;-)
But how does this explain the shitty performance of other toolkits on X11? (since GTK doesn't have it's own internal rasterizer, try windows vs. x11 instead, maybe?)
Also, how large n's are we talking about? (n = dashes?)
Zack has posted an interested explanation why there are the way they are and not the way they should be: http://zrusin.blogspot.com/2009/08/2d-in-kde.html .
Where can we find the function that takes O(n²) runtime?
@anon: KSquares in some cases draws around 80 lines with n = 3600 so it's quite big.
@med and he told me i'm wrong that it's O(nlogn) and no, i'm not wrong
@Christoph QPainterPath::toFillPolygons function, the code below // find all intersections
I don't know about XRender code, but your statement
"which Qt tries to detect for each dash of the line which other dashes intersect with it, that's right a O(n^2) calculation"
is just plain wrong. You can easily detect intersections in O(n * log n).
The fact that it can be done in nlogn doesn't mean they do it, you can see clearly here that it loops twice for count (number of dashes)
for (int j=0; j<count; ++j) {
if (subpaths.at(j).size() <= 2)
continue;
QRectF cbounds = bounds.at(j);
for (int i=0; i<count; ++i) {
if (rect_intersects(cbounds, bounds.at(i))) {
isects[j] << i;
}
}
}
Yeah. The code is O(n²). However I wonder why there is the slight asymmetry. It can happen that isects[j] contains i but isects[i] does not contain j.
Yes, but what about
if (subpaths.at(j).size() <= 2)
continue;
P.S.
Haven't look the code though...
@Panagiotis: I have a very simple test case with a straight line with 167 dashes that calls 27889 times rect_intersects
Cool article as for me. It would be great to read a bit more concerning that theme. Thank you for sharing this information.
Sexy Lady
Busty escort London
Post a Comment