Speed up QTextFormatCollection::indexForFormat

QTextFormatCollection currently has two problems:
 - looking for the index of a QTextFormat is linear, this can take 25%
   cpu when loading large documents in kword
 - the hash function for QTextFormat is inadequate. Not all values are
   treated specially. E.g. each QBrush instance has the same hash value
   at the moment.

These patches speed up loading of a large text document in KWord from 9
to 7 seconds.

This fixes this by using QMultiHash to group the QTextFormat instances
by hash and only loop through that list when looking up values. It also
improves the hash function for QTextFormat.

Merge-request: 1623
Reviewed-by: Olivier Goffart <ogoffart@trolltech.com>

2 files changed, 59 insertions, 21 deletions

diff --git a/src/gui/text/qtextformat.cpp b/src/gui/text/qtextformat.cpp
index d05d9e5..deda39f 100644
--- a/src/gui/text/qtextformat.cpp
+++ b/src/gui/text/qtextformat.cpp
@@ -265,21 +265,55 @@ private:
     friend QDataStream &operator>>(QDataStream &, QTextFormat &);
 };
 
-static uint variantHash(const QVariant &variant)
+// this is only safe if sizeof(int) == sizeof(float)
+static inline uint hash(float d)
 {
-    switch (variant.userType()) {
-    case QVariant::Invalid: return 0;
-    case QVariant::Bool: return variant.toBool();
-    case QVariant::Int: return variant.toInt();
-    case QMetaType::Float: return static_cast<int>(variant.toFloat());
-    case QVariant::Double: return static_cast<int>(variant.toDouble());
+    return reinterpret_cast<uint&>(d);
+}
+
+static inline uint hash(const QColor &color)
+{
+    return (color.isValid()) ? color.rgba() : 0x234109;
+}
+
+static inline uint hash(const QPen &pen)
+{
+    return hash(pen.color()) + hash(pen.widthF());
+}
+
+static inline uint hash(const QBrush &brush)
+{
+    return hash(brush.color()) + (brush.style() << 3);
+}
+
+static inline uint variantHash(const QVariant &variant)
+{
+    // simple and fast hash functions to differentiate between type and value
+    switch (variant.userType()) { // sorted by occurrence frequency
     case QVariant::String: return qHash(variant.toString());
-    case QVariant::Color: return qHash(qvariant_cast<QColor>(variant).rgb());
+    case QVariant::Double: return hash(variant.toDouble());
+    case QVariant::Int: return 0x811890 + variant.toInt();
+    case QVariant::Brush:
+        return 0x01010101 + hash(qvariant_cast<QBrush>(variant));
+    case QVariant::Bool: return 0x371818 + variant.toBool();
+    case QVariant::Pen: return 0x02020202 + hash(qvariant_cast<QPen>(variant));
+    case QVariant::List:
+        return 0x8377 + qvariant_cast<QVariantList>(variant).count();
+    case QVariant::Color: return hash(qvariant_cast<QColor>(variant));
+      case QVariant::TextLength:
+        return 0x377 + hash(qvariant_cast<QTextLength>(variant).rawValue());
+    case QMetaType::Float: return hash(variant.toFloat());
+    case QVariant::Invalid: return 0;
     default: break;
     }
     return qHash(variant.typeName());
 }
 
+static inline int getHash(const QTextFormatPrivate *d, int format)
+{
+    return (d ? d->hash() : 0) + format;
+}
+
 uint QTextFormatPrivate::recalcHash() const
 {
     hashValue = 0;
@@ -3033,13 +3067,15 @@ QTextFormatCollection::~QTextFormatCollection()
 
 int QTextFormatCollection::indexForFormat(const QTextFormat &format)
 {
-    uint hash = format.d ? format.d->hash() : 0;
-    if (hashes.contains(hash)) {
-        for (int i = 0; i < formats.size(); ++i) {
-            if (formats.at(i) == format)
-                return i;
+    uint hash = getHash(format.d, format.format_type);
+    QMultiHash<uint, int>::const_iterator i = hashes.find(hash);
+    while (i != hashes.end() && i.key() == hash) {
+        if (formats.value(i.value()) == format) {
+            return i.value();
         }
+        ++i;
     }
+
     int idx = formats.size();
     formats.append(format);
 
@@ -3049,7 +3085,7 @@ int QTextFormatCollection::indexForFormat(const QTextFormat &format)
             f.d = new QTextFormatPrivate;
         f.d->resolveFont(defaultFnt);
 
-        hashes.insert(hash);
+        hashes.insert(hash, idx);
 
     } QT_CATCH(...) {
         formats.pop_back();
@@ -3060,11 +3096,13 @@ int QTextFormatCollection::indexForFormat(const QTextFormat &format)
 
 bool QTextFormatCollection::hasFormatCached(const QTextFormat &format) const
 {
-    uint hash = format.d ? format.d->hash() : 0;
-    if (hashes.contains(hash)) {
-        for (int i = 0; i < formats.size(); ++i)
-            if (formats.at(i) == format)
-                return true;
+    uint hash = getHash(format.d, format.format_type);
+    QMultiHash<uint, int>::const_iterator i = hashes.find(hash);
+    while (i != hashes.end() && i.key() == hash) {
+        if (formats.value(i.value()) == format) {
+            return true;
+        }
+        ++i;
     }
     return false;
 }
diff --git a/src/gui/text/qtextformat_p.h b/src/gui/text/qtextformat_p.h
index c796343..73ca0ce 100644
--- a/src/gui/text/qtextformat_p.h
+++ b/src/gui/text/qtextformat_p.h
@@ -55,7 +55,7 @@
 
 #include "QtGui/qtextformat.h"
 #include "QtCore/qvector.h"
-#include "QtCore/qset.h"
+#include "QtCore/qhash.h"
 
 QT_BEGIN_NAMESPACE
 
@@ -97,7 +97,7 @@ public:
 
     FormatVector formats;
     QVector<qint32> objFormats;
-    QSet<uint> hashes;
+    QMultiHash<uint,int> hashes;
 
     inline QFont defaultFont() const { return defaultFnt; }
     void setDefaultFont(const QFont &f);