Text Selection Speed
Koos Vriezen
koos.vriezen at xs4all.nl
Sat Jun 22 14:56:32 BST 2002
On Fri, 14 Jun 2002, Koos Vriezen wrote:
> On Fri, 14 Jun 2002, Dirk Mueller wrote:
> > On Don, 13 Jun 2002, Matt Newell wrote:
> > > understanding to improve the horribly slow text selection algorithm. I am
> > > starting to get a pretty decent understanding of how it works, but I still am
> > > not sure where all of the cpu cycles are going. I just thought that you guys
> > > could give me a few pointers on what functions need optimizing, or how to
> > > profile khtml to find out for myself.
> >
> > There is no index about onscreen position -> rendertree object.
> >
> > Partially the text selection code simply scans through the tree for finding
> > the starting and end position, which is really slow. That part needs
> > rewriting, but up to now nobody volunteered.
>
> Also, if you uncomment kdDebug in KHTMLView::scheduleRepaint(x,y,w,h), you
> see that the whole visual khtml part is repainted while selecting text.
Attached a patch that contains my two previous patches, only repaint the
selected object and the re-scheduling changes, with some improvements.
It also adds 'cachedInnerNode' to DocumentImpl.
'DocumentImpl::prepareMouseEvent' first looks if the mouse is still in
this object, before rescanning the rendering tree. This saves a lot of CPU
cycles when moving the mouse above khtml part.
There is no reference counting in Render*, so I'm not 100% sure this
cached node is always valid.
Please comment.
Koos
-------------- next part --------------
Index: khtmlview.cpp
===================================================================
RCS file: /home/kde/kdelibs/khtml/khtmlview.cpp,v
retrieving revision 1.473
diff -u -3 -p -r1.473 khtmlview.cpp
--- khtmlview.cpp 2002/06/14 08:11:36 1.473
+++ khtmlview.cpp 2002/06/22 13:36:45
@@ -50,6 +50,7 @@
#include <qtooltip.h>
#include <qpainter.h>
#include <qpaintdevicemetrics.h>
+#include <qvaluelist.h>
#include <kapplication.h>
#include <kimageio.h>
@@ -142,7 +143,6 @@ public:
complete = false;
firstRelayout = true;
layoutSchedulingEnabled = true;
- updateRect = QRect();
}
QPainter *tp;
@@ -177,7 +177,7 @@ public:
bool complete;
bool firstRelayout;
bool layoutSchedulingEnabled;
- QRect updateRect;
+ QValueList<QRect> pendingRects;
KHTMLToolTip *tooltip;
};
@@ -1457,7 +1457,8 @@ void KHTMLView::timerEvent ( QTimerEvent
d->timerId = 0;
//scheduleRepaint(contentsX(),contentsY(),visibleWidth(),visibleHeight());
- d->updateRect = QRect(contentsX(),contentsY(),visibleWidth(),visibleHeight());
+ d->pendingRects.clear();
+ d->pendingRects.push_back(QRect(contentsX(),contentsY(),visibleWidth(),visibleHeight()));
}
if( m_part->xmlDocImpl() ) {
@@ -1476,9 +1477,13 @@ void KHTMLView::timerEvent ( QTimerEvent
// kdDebug() << "scheduled repaint "<< d->repaintTimerId << endl;
killTimer(d->repaintTimerId);
- updateContents( d->updateRect );
-
d->repaintTimerId = 0;
+ QValueList<QRect>::iterator it = d->pendingRects.begin();
+ for (; it != d->pendingRects.end(); it = d->pendingRects.begin()) {
+ updateContents(*it);
+ d->pendingRects.pop_front();
+ }
+
}
void KHTMLView::scheduleRelayout()
@@ -1513,7 +1518,7 @@ void KHTMLView::scheduleRepaint(int x, i
// if complete...
if (d->complete)
// ...repaint immediatly
- time = 0;
+ time = 40;
else
{
if (parsing)
@@ -1522,16 +1527,39 @@ void KHTMLView::scheduleRepaint(int x, i
else
// not complete, not parsing, extend the timer if it exists
// otherwise, repaint immediatly
- time = d->repaintTimerId ? 400 : 0;
+ time = d->repaintTimerId ? 400 : 40;
}
- if (d->repaintTimerId) {
- killTimer(d->repaintTimerId);
- d->updateRect = d->updateRect.unite(QRect(x,y,w,h));
- } else
- d->updateRect = QRect(x,y,w,h);
+ QRect r = QRect(x,y,w,h);
+ QValueList<QRect>::iterator insert = d->pendingRects.end();
+ QValueList<QRect>::iterator replaced = d->pendingRects.end();
+ QValueList<QRect>::iterator remove = d->pendingRects.end();
+ QValueList<QRect>::iterator it = d->pendingRects.begin();
+ for (; it != d->pendingRects.end(); it++) {
+ if (r.intersects(*it)) {
+ r = r.unite(*it);
+ if (replaced == d->pendingRects.end())
+ replaced = it;
+ else {
+ if (remove != d->pendingRects.end())
+ d->pendingRects.erase(remove);
+ remove = it;
+ }
+ *replaced = r;
+ } else if ((*it).y() > r.y()) {
+ if (insert == d->pendingRects.end())
+ insert = it;
+ if (r.bottom() <= (*it).y())
+ break;
+ }
+ }
+ if (replaced == d->pendingRects.end())
+ d->pendingRects.insert(insert, r);
+ else if (remove != d->pendingRects.end())
+ d->pendingRects.erase(remove);
- d->repaintTimerId = startTimer( time );
+ if (!d->repaintTimerId)
+ d->repaintTimerId = startTimer( time );
// kdDebug() << "starting timer " << time << endl;
}
Index: html/html_imageimpl.cpp
===================================================================
RCS file: /home/kde/kdelibs/khtml/html/html_imageimpl.cpp,v
retrieving revision 1.132
diff -u -3 -p -r1.132 html_imageimpl.cpp
--- html/html_imageimpl.cpp 2002/06/19 09:29:20 1.132
+++ html/html_imageimpl.cpp 2002/06/22 13:36:46
@@ -366,7 +366,7 @@ bool HTMLAreaElementImpl::mapMouseEvent(
if (region.contains(QPoint(x_,y_)))
{
inside = true;
- info.setInnerNode(this);
+ info.setInnerNode(this, 0, 0);
info.setURLElement(this);
}
Index: rendering/render_frames.cpp
===================================================================
RCS file: /home/kde/kdelibs/khtml/rendering/render_frames.cpp,v
retrieving revision 1.135
diff -u -3 -p -r1.135 render_frames.cpp
--- rendering/render_frames.cpp 2002/05/15 18:12:25 1.135
+++ rendering/render_frames.cpp 2002/06/22 13:36:50
@@ -91,7 +91,7 @@ bool RenderFrameSet::nodeAtPoint(NodeInf
bool inside = m_resizing || canResize(_x, _y);
if ( inside && element() && !element()->noResize() && !info.readonly())
- info.setInnerNode(element());
+ info.setInnerNode(element(), _tx, _ty);
return inside || m_clientresizing;
}
Index: rendering/render_object.cpp
===================================================================
RCS file: /home/kde/kdelibs/khtml/rendering/render_object.cpp,v
retrieving revision 1.177
diff -u -3 -p -r1.177 render_object.cpp
--- rendering/render_object.cpp 2002/06/16 15:23:47 1.177
+++ rendering/render_object.cpp 2002/06/22 13:36:51
@@ -848,7 +848,7 @@ bool RenderObject::nodeAtPoint(NodeInfo&
if (inside && element()) {
if (!info.innerNode())
- info.setInnerNode(element());
+ info.setInnerNode(element(), _tx, _ty);
if (!info.URLElement()) {
RenderObject* p = this;
Index: rendering/render_object.h
===================================================================
RCS file: /home/kde/kdelibs/khtml/rendering/render_object.h,v
retrieving revision 1.127
diff -u -3 -p -r1.127 render_object.h
--- rendering/render_object.h 2002/06/16 15:23:47 1.127
+++ rendering/render_object.h 2002/06/22 13:36:51
@@ -56,6 +56,7 @@ namespace DOM {
class NodeImpl;
class ElementImpl;
class EventImpl;
+ class DocumentImpl;
};
namespace khtml {
@@ -279,9 +280,10 @@ public:
friend class RenderObject;
friend class RenderFrameSet;
friend class DOM::HTMLAreaElementImpl;
+ friend class DOM::DocumentImpl;
public:
NodeInfo(bool readonly, bool active)
- : m_innerNode(0), m_innerURLElement(0), m_readonly(readonly), m_active(active)
+ : m_innerNode(0), m_innerURLElement(0), m_readonly(readonly), m_active(active), tx(0), ty(0)
{ }
DOM::NodeImpl* innerNode() const { return m_innerNode; }
@@ -290,13 +292,16 @@ public:
bool active() const { return m_active; }
private:
- void setInnerNode(DOM::NodeImpl* n) { m_innerNode = n; }
+ void setInnerNode(DOM::NodeImpl* n, int _tx, int _ty)
+ { m_innerNode = n; tx = _tx; ty = _ty; }
void setURLElement(DOM::NodeImpl* n) { m_innerURLElement = n; }
DOM::NodeImpl* m_innerNode;
DOM::NodeImpl* m_innerURLElement;
bool m_readonly;
bool m_active;
+ int tx;
+ int ty;
};
virtual FindSelectionResult checkSelectionPoint( int _x, int _y, int _tx, int _ty,
Index: rendering/render_root.cpp
===================================================================
RCS file: /home/kde/kdelibs/khtml/rendering/render_root.cpp,v
retrieving revision 1.107
diff -u -3 -p -r1.107 render_root.cpp
--- rendering/render_root.cpp 2002/03/27 13:30:20 1.107
+++ rendering/render_root.cpp 2002/06/22 13:36:51
@@ -277,9 +277,21 @@ void RenderRoot::setSelection(RenderObje
// update selection status of all objects between m_selectionStart and m_selectionEnd
RenderObject* o = s;
+ int xs = (unsigned)~0 >> 1;
+ int xe = 0;
+ int ys = (unsigned)~0 >> 1;
+ int ye = 0;
while (o && o!=e)
{
o->setSelectionState(SelectionInside);
+ if (o->xPos() < xs)
+ xs = o->xPos();
+ if (o->yPos() < ys)
+ xe = o->yPos();
+ if (xe < o->xPos() + o->width())
+ ys = o->xPos() + o->width();
+ if (ye < o->yPos() + o->height())
+ ye = o->yPos() + o->height();
// kdDebug( 6040 ) << "setting selected " << o << ", " << o->isText() << endl;
RenderObject* no;
if ( !(no = o->firstChild()) )
@@ -296,7 +308,7 @@ void RenderRoot::setSelection(RenderObje
s->setSelectionState(SelectionStart);
e->setSelectionState(SelectionEnd);
if(s == e) s->setSelectionState(SelectionBoth);
- repaint();
+ repaintRectangle(xs, ys, xe - xs, ye - ys, false);
}
Index: xml/dom_docimpl.cpp
===================================================================
RCS file: /home/kde/kdelibs/khtml/xml/dom_docimpl.cpp,v
retrieving revision 1.186
diff -u -3 -p -r1.186 dom_docimpl.cpp
--- xml/dom_docimpl.cpp 2002/06/21 13:16:07 1.186
+++ xml/dom_docimpl.cpp 2002/06/22 13:36:52
@@ -217,13 +217,22 @@ DOMImplementationImpl *DOMImplementation
}
// ------------------------------------------------------------------------
+namespace DOM {
+
+class DocumentImplPrivate {
+public:
+ DocumentImplPrivate() : cachedInnerNode(0L) {}
+ khtml::RenderObject::NodeInfo * cachedInnerNode;
+};
+}
+
KStaticDeleter< QPtrList<DocumentImpl> > s_changedDocumentsDeleter;
QPtrList<DocumentImpl> * DocumentImpl::changedDocuments = 0;
// KHTMLView might be 0
DocumentImpl::DocumentImpl(DOMImplementationImpl *_implementation, KHTMLView *v)
- : NodeBaseImpl( new DocumentPtr() )
+ : NodeBaseImpl( new DocumentPtr() ), d(new DocumentImplPrivate)
{
document->doc = this;
@@ -317,6 +326,7 @@ DocumentImpl::~DocumentImpl()
m_styleSheets->deref();
if (m_focusNode)
m_focusNode->deref();
+ delete d;
}
@@ -940,6 +950,8 @@ void DocumentImpl::updateRendering()
change = Force;
}
#endif
+ d->cachedInnerNode = 0L;
+
recalcStyle( change );
// kdDebug() << "UPDATERENDERING time used="<<time.elapsed()<<endl;
@@ -989,6 +1001,8 @@ void DocumentImpl::detach()
if ( render )
render->detach();
+ d->cachedInnerNode = 0L;
+
m_view = 0;
}
@@ -1445,7 +1459,18 @@ bool DocumentImpl::prepareMouseEvent( bo
if ( m_render ) {
assert(m_render->isRoot());
RenderObject::NodeInfo renderInfo(readonly, ev->type == MousePress);
- bool isInside = m_render->nodeAtPoint(renderInfo, _x, _y, 0, 0);
+ bool isInside;
+ if (d->cachedInnerNode && d->cachedInnerNode->innerNode()->renderer()->nodeAtPoint(renderInfo, _x, _y, d->cachedInnerNode->tx, d->cachedInnerNode->ty))
+ isInside = true;
+ else {
+ isInside = m_render->nodeAtPoint(renderInfo, _x, _y, 0, 0);
+ if (isInside) {
+ if (!d->cachedInnerNode)
+ d->cachedInnerNode = new RenderObject::NodeInfo(readonly, ev->type == MousePress);
+ *d->cachedInnerNode = renderInfo;
+ } else if (d->cachedInnerNode)
+ d->cachedInnerNode = 0L;
+ }
ev->innerNode = renderInfo.innerNode();
if (renderInfo.URLElement()) {
Index: xml/dom_docimpl.h
===================================================================
RCS file: /home/kde/kdelibs/khtml/xml/dom_docimpl.h,v
retrieving revision 1.96
diff -u -3 -p -r1.96 dom_docimpl.h
--- xml/dom_docimpl.h 2002/04/13 23:23:37 1.96
+++ xml/dom_docimpl.h 2002/06/22 13:36:52
@@ -77,6 +77,7 @@ namespace DOM {
class StyleSheetListImpl;
class TextImpl;
class TreeWalkerImpl;
+ class DocumentImplPrivate;
class DOMImplementationImpl : public khtml::Shared<DOMImplementationImpl>
{
@@ -397,6 +398,8 @@ protected:
DOMString m_textColor;
NodeImpl *m_focusNode;
+
+ DocumentImplPrivate *d;
// ### replace me with something more efficient
// in lookup and insertion.
More information about the kfm-devel
mailing list