Drag and drop optimization

Wilco Greven kde-optimize@mail.kde.org
Thu, 30 Jan 2003 02:04:23 +0100


--Boundary-00=_XoHO+ll9kIwDSNL
Content-Type: text/plain;
  charset="us-ascii"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Hello,

The accompanying patch speeds up the part of Qt's dnd code which looks up the 
window under the cursor (*). The critical part of this code is the function 
findClientWindow. One call takes about 100 ms. Most of this time of this is 
spend in XGetWindowAttributes.

The replacement avoids uses the NETWM client list stacking looks at the 
windows starting from the top of the client stack. Here are some testresults 
comparing the two methods:

KCounterProf:findRealWindow took approx 117.79 ms
findRealWindow was called 584 times
Window returned: 22001b3
KCounterProf:findRealWindowNETWM took approx 3.32 ms
Window returned: 22001b3

KCounterProf:findRealWindow took approx 113.16 ms
findRealWindow was called 582 times
Window returned: 1a00002
KCounterProf:findRealWindowNETWM took approx 2.17 ms
Window returned: 1a00002

KCounterProf:findRealWindow took approx 114.25 ms
findRealWindow was called 583 times
Window returned: 2c02673
KCounterProf:findRealWindowNETWM took approx 2.70 ms
Window returned: 2c02673

So far the biggest problem I can see is that the code relies on a NETWM 
compliant window manager. For the rest it's hard to say because I don't know 
X11 that well.

-- 
Greetings,
Wilco

(*) You can't use XTranslateCoordinates for this when the drag icon is under 
the cursor. The drag icon itself is a Window, so XTranslateCoordinates will 
return the drag icon. 

--Boundary-00=_XoHO+ll9kIwDSNL
Content-Type: text/x-diff;
  charset="us-ascii";
  name="qdnd_x11.cpp.diff"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="qdnd_x11.cpp.diff"

Index: qdnd_x11.cpp
===================================================================
RCS file: /home/kde/qt-copy/src/kernel/qdnd_x11.cpp,v
retrieving revision 1.54
diff -u -p -b -r1.54 qdnd_x11.cpp
--- qdnd_x11.cpp	29 Jan 2003 13:54:56 -0000	1.54
+++ qdnd_x11.cpp	30 Jan 2003 00:29:30 -0000
@@ -245,6 +245,9 @@ static const char* const default_pm[] = 
 "X X X X X X X"
 };
 
+// Use NETWM for drag and drop.
+Atom qt_net_wm_client_list_stacking;
+
 class QShapedPixmapWidget : public QWidget {
 public:
     QShapedPixmapWidget(int screen = -1) :
@@ -419,6 +422,9 @@ void qt_xdnd_setup() {
     qt_x11_intern_atom( "QT_SELECTION", &qt_selection_property );
     qt_x11_intern_atom( "INCR", &qt_incr_atom );
 
+    qt_x11_intern_atom("_NET_CLIENT_LIST_STACKING",
+		                      &qt_net_wm_client_list_stacking);
+
     qAddPostRoutine( qt_xdnd_cleanup );
 }
 
@@ -1096,6 +1102,55 @@ Window findRealWindow( const QPoint & po
     return 0;
 }
 
+static Window findRealWindowNETWM( const QPoint& pos, Window root, int)
+{
+    int x = pos.x();
+    int y = pos.y();
+
+    Window* first;
+    Window* win;
+
+    Atom type_ret;
+    int format_ret;
+    unsigned long nitems_ret;
+    unsigned long unused;
+    unsigned char *data_ret = 0;
+
+    if (XGetWindowProperty(QPaintDevice::x11AppDisplay(), root, 
+                           qt_net_wm_client_list_stacking,
+                           0, 1024, False, XA_WINDOW, &type_ret,
+                           &format_ret, &nitems_ret, &unused, &data_ret)
+          == Success) {
+        if (type_ret == XA_WINDOW && format_ret == 32)
+            first = (Window*) data_ret;
+
+        if (data_ret)
+            XFree(data_ret);
+    }
+    else
+        return 0;
+
+    win = first + nitems_ret - 1;
+    do {
+        XWindowAttributes attr;
+        XGetWindowAttributes(QPaintDevice::x11AppDisplay(), *win, &attr);
+
+        int globalX, globalY;
+        Window child_ret;
+        XTranslateCoordinates(QPaintDevice::x11AppDisplay(), *win, root,
+                              attr.x, attr.y, &globalX, &globalY, &child_ret);
+
+        if ( attr.map_state != IsUnmapped
+          && x >= globalX && x < globalX + attr.width
+          && y >= globalY && y < globalY + attr.height)
+            break;
+
+        --win;
+    } while (win != first);
+
+    return *win;
+}
+
 void QDragManager::move( const QPoint & globalPos )
 {
     Q_ASSERT( object != 0 ); // ### remove in Qt 4.0 (object should never be 0 here)
@@ -1131,7 +1186,8 @@ void QDragManager::move( const QPoint & 
 	if (targetW)
 	    target = targetW;
 	if ( qt_xdnd_deco && (!target || target == qt_xdnd_deco->winId()) ) {
-	    target = findRealWindow(globalPos,rootwin,6);
+	    // target = findRealWindowM(globalPos,rootwin,6);
+	    target = findRealWindowNETWM(globalPos,rootwin,6);
 	}
     }
 

--Boundary-00=_XoHO+ll9kIwDSNL
Content-Type: text/x-c++src;
  charset="us-ascii";
  name="findclient.cpp"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="findclient.cpp"

// Build using:
// g++ -g findclient.cpp -o findclient -I/usr/local/kde/include -L/usr/X11R6/lib -L/usr/local/kde/lib -lX11 -lqt-mt

#include <qapplication.h>
#include <qdatetime.h>
#include <qwidget.h>

extern "C" {
#include <X11/Xatom.h>
#include <X11/Xlib.h>
}

#include "kcounterprof.h"

static Display* dpy;
static Window supportWindow;
static Window rootWindow;

static Atom wm_state;
static Atom net_client_list_stacking;

static int count;


static Window findRealWindow( int x, int y, Window w, int md )
{
    count++;

    if ( md ) {
        XWindowAttributes attr;
        XGetWindowAttributes(dpy, w, &attr);

        if ( attr.map_state != IsUnmapped
          && x >= attr.x && x < attr.x + attr.width
          && y >= attr.y && y < attr.y + attr.height)
        {
            {
                Atom   type = None;
                int f;
                unsigned long n, a;
                unsigned char *data;

                XGetWindowProperty( dpy, w, wm_state, 0,
                    0, False, AnyPropertyType, &type, &f,&n,&a,&data );
                if ( data ) XFree(data);
                if ( type ) return w;
            }

            Window r, p;
            Window* c;
            uint nc;
            if ( XQueryTree( dpy, w, &r, &p, &c, &nc ) ) {
                r=0;
                for (uint i=nc; !r && i--; ) {
                    r = findRealWindow( x-attr.x, y-attr.y, c[i], md-1 );
                }
                XFree(c);
                if ( r )
                    return r;

                // We didn't find a client window!  Just use the
                // innermost window.
            }

            // No children!
            return w;
        }
    }
    return 0;
}

static Window findRealWindowNETWM( int x, int y, Window, int)
{
    Window* head;
    Atom type_ret;
    int format_ret;
    unsigned long nitems_ret;
    unsigned long unused;
    unsigned char *data_ret = 0;

    if (XGetWindowProperty(dpy, rootWindow, net_client_list_stacking,
                       0, 1024, False, XA_WINDOW, &type_ret,
                       &format_ret, &nitems_ret, &unused, &data_ret) 
          == Success) {
        if (type_ret == XA_WINDOW && format_ret == 32)
            head = (Window*) data_ret;

        if (data_ret)
            XFree(data_ret);
    }
    else
        return 0;

    Window* win = head + nitems_ret - 1;
    do {
        XWindowAttributes attr;
        XGetWindowAttributes(dpy, *win, &attr);

        int root_x, root_y;
        Window child_ret;
        XTranslateCoordinates(dpy, *win, rootWindow, attr.x, attr.y, 
                              &root_x, &root_y, &child_ret);

        if (attr.map_state != IsUnmapped
         && x >= root_x && x < root_x + attr.width
         && y >= root_y && y < root_y + attr.height)
            break;

        --win;
    } while (win != head);

    return *win;
}

void test(int x, int y)
{
    Window result1 = findRealWindow(x, y, rootWindow, 6);
    Window result2 = findRealWindowNETWM(x, y, rootWindow, 6);

    if (result1 != result2) {
        qDebug("Different results for position (%i, %i): ", x, y);
        qDebug("  findRealWindow:      %x", result1);
        qDebug("  findRealWindowNETWM: %x", result2);
    }
}

int main(int argc, char** argv)
{
    QApplication app(argc, argv);
    supportWindow = (new QWidget())->winId();
    srand48(QTime::currentTime().second()+QTime::currentTime().msec());

    dpy = QPaintDevice::x11AppDisplay();
    wm_state = XInternAtom(dpy, "WM_STATE", False);
    net_client_list_stacking 
             = XInternAtom(dpy, "_NET_CLIENT_LIST_STACKING", False);
    count = 0;

    rootWindow = RootWindow(dpy, DefaultScreen(dpy));

    int x, y;

    const int width = DisplayWidth(dpy, DefaultScreen(dpy));
    const int height = DisplayHeight(dpy, DefaultScreen(dpy));

    /*
    for (;;) {
        x = int(drand48() * width);
        y = int(drand48() * height);
	test(x, y);
    }
    */

    x = int(drand48() * width);
    y = int(drand48() * height);

    KCounterProf::begin("findRealWindow");
    Window result1 = findRealWindow(x, y, rootWindow, 6);
    KCounterProf::end("findRealWindow");
    qDebug("findRealWindow was called %u times", count);
    qDebug("Window returned: %x", result1);

    KCounterProf::begin("findRealWindowNETWM");
    Window result2 = findRealWindowNETWM(x, y, rootWindow, 6);
    KCounterProf::end("findRealWindowNETWM");
    qDebug("Window returned: %x", result2);

    return 0;
}



--Boundary-00=_XoHO+ll9kIwDSNL--