benchmarks: first shot at alternative implementation for qHash(QString)

5 files changed, 435 insertions, 0 deletions

diff --git a/tests/benchmarks/corelib/tools/qhash/data.txt b/tests/benchmarks/corelib/tools/qhash/data.txt
new file mode 100644
index 0000000..d5acd28
--- /dev/null
+++ b/tests/benchmarks/corelib/tools/qhash/data.txt
@@ -0,0 +1,195 @@
+.
+./corelib.pro
+./kernel
+./kernel/kernel.pro
+./kernel/qobject
+./kernel/qobject/main.cpp
+./kernel/qobject/object.cpp
+./kernel/qobject/object.h
+./kernel/qobject/Makefile
+./kernel/qobject/qobject.pro
+./kernel/qvariant
+./kernel/qvariant/tst_qvariant.cpp
+./kernel/qvariant/Makefile
+./kernel/qvariant/qvariant.pro
+./kernel/qtimer_vs_qmetaobject
+./kernel/qtimer_vs_qmetaobject/tst_qtimer_vs_qmetaobject.cpp
+./kernel/qtimer_vs_qmetaobject/Makefile
+./kernel/qtimer_vs_qmetaobject/qtimer_vs_qmetaobject.pro
+./kernel/.pch
+./kernel/.pch/debug-shared
+./kernel/qmetaobject
+./kernel/qmetaobject/main.cpp
+./kernel/qmetaobject/qmetaobject.pro
+./kernel/qmetaobject/Makefile
+./kernel/Makefile
+./kernel/.obj
+./kernel/.obj/debug-shared
+./kernel/events
+./kernel/events/events.pro
+./kernel/events/main.cpp
+./kernel/events/Makefile
+./kernel/qmetatype
+./kernel/qmetatype/qmetatype.pro
+./kernel/qmetatype/Makefile
+./kernel/qmetatype/tst_qmetatype.cpp
+./codecs
+./codecs/qtextcodec
+./codecs/qtextcodec/qtextcodec.pro
+./codecs/qtextcodec/main.cpp
+./codecs/qtextcodec/Makefile
+./codecs/qtextcodec/utf-8.txt
+./codecs/codecs.pro
+./codecs/.pch
+./codecs/.pch/debug-shared
+./codecs/Makefile
+./codecs/.obj
+./codecs/.obj/debug-shared
+./.pch
+./.pch/debug-shared
+./tools
+./tools/tools.pro
+./tools/qregexp
+./tools/qregexp/qregexp.qrc
+./tools/qregexp/main.cpp
+./tools/qregexp/Makefile
+./tools/qregexp/qregexp.pro
+./tools/qvector
+./tools/qvector/tst_vector
+./tools/qvector/.pch
+./tools/qvector/.pch/debug-shared
+./tools/qvector/qrawvector.h
+./tools/qvector/main.cpp
+./tools/qvector/Makefile
+./tools/qvector/.moc
+./tools/qvector/.moc/release-shared
+./tools/qvector/.moc/release-shared/main.moc
+./tools/qvector/.obj
+./tools/qvector/.obj/release-shared
+./tools/qvector/.obj/release-shared/outofline.o
+./tools/qvector/.obj/release-shared/main.o
+./tools/qvector/outofline.cpp
+./tools/qvector/qvector.pro
+./tools/.pch
+./tools/.pch/debug-shared
+./tools/qstringbuilder
+./tools/qstringbuilder/main.cpp
+./tools/qstringbuilder/Makefile
+./tools/qstringbuilder/qstringbuilder.pro
+./tools/containers-sequential
+./tools/containers-sequential/containers-sequential.pro
+./tools/containers-sequential/main.cpp
+./tools/containers-sequential/Makefile
+./tools/qstring
+./tools/qstring/generatelist.pl
+./tools/qstring/data.h
+./tools/qstring/qstring.pro
+./tools/qstring/main.cpp
+./tools/qstring/data.cpp
+./tools/qstring/Makefile
+./tools/qstring/utf-8.txt
+./tools/qstringlist
+./tools/qstringlist/qstringlist.pro
+./tools/qstringlist/main.cpp
+./tools/qstringlist/.gitignore
+./tools/qstringlist/Makefile
+./tools/qbytearray
+./tools/qbytearray/qbytearray.pro
+./tools/qbytearray/main.cpp
+./tools/qbytearray/Makefile
+./tools/containers-associative
+./tools/containers-associative/containers-associative.pro
+./tools/containers-associative/main.cpp
+./tools/containers-associative/Makefile
+./tools/qrect
+./tools/qrect/main.cpp
+./tools/qrect/Makefile
+./tools/qrect/qrect.pro
+./tools/Makefile
+./tools/qhash
+./tools/qhash/data.txt
+./tools/qhash/qhash_string.cpp
+./tools/qhash/.qhash_string.cpp.swp
+./tools/qhash/qhash.pro
+./tools/qhash/outofline.cpp
+./tools/.obj
+./tools/.obj/debug-shared
+./Makefile
+./.obj
+./.obj/debug-shared
+./plugin
+./plugin/plugin.pro
+./plugin/.pch
+./plugin/.pch/debug-shared
+./plugin/Makefile
+./plugin/.obj
+./plugin/.obj/debug-shared
+./plugin/quuid
+./plugin/quuid/tst_quuid.cpp
+./plugin/quuid/quuid.pro
+./plugin/quuid/Makefile
+./io
+./io/qtemporaryfile
+./io/qtemporaryfile/qtemporaryfile.pro
+./io/qtemporaryfile/main.cpp
+./io/qtemporaryfile/Makefile
+./io/qiodevice
+./io/qiodevice/qiodevice.pro
+./io/qiodevice/main.cpp
+./io/qiodevice/Makefile
+./io/qurl
+./io/qurl/main.cpp
+./io/qurl/Makefile
+./io/qurl/qurl.pro
+./io/qdir
+./io/qdir/.pch
+./io/qdir/.pch/debug-shared
+./io/qdir/qdir.pro
+./io/qdir/tree
+./io/qdir/tree/bench_qdir_tree.qrc
+./io/qdir/tree/tree.pro
+./io/qdir/tree/4.6.0-list.txt
+./io/qdir/tree/Makefile
+./io/qdir/tree/bench_qdir_tree.cpp
+./io/qdir/Makefile
+./io/qdir/.obj
+./io/qdir/.obj/debug-shared
+./io/qdir/10000
+./io/qdir/10000/10000.pro
+./io/qdir/10000/bench_qdir_10000.cpp
+./io/qdir/10000/Makefile
+./io/.pch
+./io/.pch/debug-shared
+./io/qfile
+./io/qfile/qfile.pro
+./io/qfile/main.cpp
+./io/qfile/Makefile
+./io/io.pro
+./io/qfileinfo
+./io/qfileinfo/qfileinfo.pro
+./io/qfileinfo/main.cpp
+./io/qfileinfo/Makefile
+./io/qdiriterator
+./io/qdiriterator/qfilesystemiterator.h
+./io/qdiriterator/main.cpp
+./io/qdiriterator/Makefile
+./io/qdiriterator/qfilesystemiterator.cpp
+./io/qdiriterator/qdiriterator.pro
+./io/Makefile
+./io/.obj
+./io/.obj/debug-shared
+./thread
+./thread/qmutex
+./thread/qmutex/tst_qmutex.cpp
+./thread/qmutex/Makefile
+./thread/qmutex/qmutex.pro
+./thread/qthreadstorage
+./thread/qthreadstorage/qthreadstorage.pro
+./thread/qthreadstorage/Makefile
+./thread/qthreadstorage/tst_qthreadstorage.cpp
+./thread/.pch
+./thread/.pch/debug-shared
+./thread/Makefile
+./thread/.obj
+./thread/.obj/debug-shared
+./thread/thread.pro
diff --git a/tests/benchmarks/corelib/tools/qhash/outofline.cpp b/tests/benchmarks/corelib/tools/qhash/outofline.cpp
new file mode 100644
index 0000000..0a60da2
--- /dev/null
+++ b/tests/benchmarks/corelib/tools/qhash/outofline.cpp
@@ -0,0 +1,90 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QtTest module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights.  These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qhash_string.h"
+
+static void doHash(const unsigned short *p, uint &h)
+{
+#if 1
+    // Copied from static uint hash(const QChar *p, int n).
+    // Possibly not the cheapest way.
+    h = (h << 4) + (*p++);
+    h ^= (h & 0xf0000000) >> 23;
+    h &= 0x0fffffff;
+
+    h = (h << 4) + (*p++);
+    h ^= (h & 0xf0000000) >> 23;
+    h &= 0x0fffffff;
+
+    h = (h << 4) + (*p++);
+    h ^= (h & 0xf0000000) >> 23;
+    h &= 0x0fffffff;
+
+    h = (h << 4) + (*p++);
+    h ^= (h & 0xf0000000) >> 23;
+    h &= 0x0fffffff;
+#else
+    // Faster, but probably less spread.
+    h ^= *(unsigned int *)p;
+#endif
+}
+
+QT_BEGIN_NAMESPACE
+
+uint qHash(const String &str)
+{
+    const unsigned short *p = (unsigned short *)str.constData();
+    const int s = str.size();
+    switch (s) {
+        case 0: return 0;
+        case 1: return *p;
+        case 2: return *(unsigned int *)p;
+        case 3: return (*(unsigned int *)p) ^ *(p + 2);
+        //case 3: return (*p << 11) + (*(p + 1) << 22) + *(p + 2);
+    }
+    uint h = 0;
+    doHash(p, h);
+    doHash(p + s / 2 - 2, h);
+    doHash(p + s - 4, h);
+    return h;
+}
+
+QT_END_NAMESPACE
diff --git a/tests/benchmarks/corelib/tools/qhash/qhash.pro b/tests/benchmarks/corelib/tools/qhash/qhash.pro
new file mode 100644
index 0000000..dff152c
--- /dev/null
+++ b/tests/benchmarks/corelib/tools/qhash/qhash.pro
@@ -0,0 +1,6 @@
+load(qttest_p4)
+TARGET = tst_hash
+QT = core
+INCLUDEPATH += .
+SOURCES += qhash_string.cpp outofline.cpp 
+CONFIG += release
diff --git a/tests/benchmarks/corelib/tools/qhash/qhash_string.cpp b/tests/benchmarks/corelib/tools/qhash/qhash_string.cpp
new file mode 100644
index 0000000..fde1722
--- /dev/null
+++ b/tests/benchmarks/corelib/tools/qhash/qhash_string.cpp
@@ -0,0 +1,132 @@
+
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the test suite of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights.  These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+/*
+
+////////////////////////////////////////////////////////////////////
+
+This benchmark serves as reality check on the idea that hashing the complete
+string is a good idea.
+
+  Executive summary: It is not a good idea.
+
+////////////////////////////////////////////////////////////////////
+
+********* Start testing of tst_QHash *********
+Config: Using QTest library 4.8.0, Qt 4.8.0
+PASS   : tst_QHash::initTestCase()
+RESULT : tst_QHash::qhash_qt4():
+     0.041 msecs per iteration (total: 85, iterations: 2048)
+PASS   : tst_QHash::qhash_qt4()
+RESULT : tst_QHash::qhash_faster():
+     0.0122 msecs per iteration (total: 100, iterations: 8192)
+PASS   : tst_QHash::qhash_faster()
+PASS   : tst_QHash::cleanupTestCase()
+Totals: 4 passed, 0 failed, 0 skipped
+
+////////////////////////////////////////////////////////////////////
+
+*/
+
+#include "qhash_string.h"
+
+#include <QFile>
+#include <QHash>
+#include <QString>
+#include <QStringList>
+
+#include <QTest>
+
+
+class tst_QHash : public QObject
+{
+    Q_OBJECT
+
+private slots:
+    void qhash_qt4();
+    void qhash_faster();
+
+private:
+    QString data();
+};
+
+const int N = 1000000;
+extern double s;
+
+///////////////////// QHash /////////////////////
+
+QString tst_QHash::data()
+{
+    QFile file("data.txt");
+    file.open(QIODevice::ReadOnly);
+    return QString::fromLatin1(file.readAll());
+}
+
+void tst_QHash::qhash_qt4()
+{
+    QStringList items = data().split(QLatin1Char('\n'));
+    QHash<QString, int> hash;
+    
+    QBENCHMARK {
+        for (int i = 0, n = items.size(); i != n; ++i) {
+            hash[items.at(i)] = i;
+        }
+    }
+}
+
+void tst_QHash::qhash_faster()
+{
+    QList<String> items;
+    foreach (const QString &s, data().split(QLatin1Char('\n')))
+        items.append(s);
+    QHash<String, int> hash;
+    
+    QBENCHMARK {
+        for (int i = 0, n = items.size(); i != n; ++i) {
+            hash[items.at(i)] = i;
+        }
+    }
+}
+
+QTEST_MAIN(tst_QHash)
+
+#include "qhash_string.moc"
diff --git a/tests/benchmarks/corelib/tools/qhash/qhash_string.h b/tests/benchmarks/corelib/tools/qhash/qhash_string.h
new file mode 100644
index 0000000..bdc7770
--- /dev/null
+++ b/tests/benchmarks/corelib/tools/qhash/qhash_string.h
@@ -0,0 +1,12 @@
+
+#include <QString>
+
+struct String : QString
+{
+    String() {}
+    String(const QString &s) : QString(s) {}
+};
+
+QT_BEGIN_NAMESPACE
+uint qHash(const String &);
+QT_END_NAMESPACE