Improve QByteDataBuffer::read() performance with partial reads

Add a read position variable to eliminate excessive memcpy'ing when
reading a partial buffer.

Specifically, fix performance issue of reading large files from
QNetworkDiskCache in QtWebKit2.

Task-number: QTBUG-27522
Change-Id: I21edc909bf9223971b2c3db5f1fa6b89c5b61c5f
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Reviewed-by: Antti Harju <antti.harju@ixonos.com>

9 files changed, 464 insertions, 22 deletions

diff --git a/src/corelib/tools/qbytedata_p.h b/src/corelib/tools/qbytedata_p.h
index b05c21033a..a77e741e65 100644
--- a/src/corelib/tools/qbytedata_p.h
+++ b/src/corelib/tools/qbytedata_p.h
@@ -64,8 +64,9 @@ class QByteDataBuffer
 private:
     QList<QByteArray> buffers;
     qint64 bufferCompleteSize;
+    qint64 firstPos;
 public:
-    QByteDataBuffer() : bufferCompleteSize(0)
+    QByteDataBuffer() : bufferCompleteSize(0), firstPos(0)
     {
     }
 
@@ -74,13 +75,29 @@ public:
         clear();
     }
 
-    inline void append(QByteDataBuffer& other)
+    static inline void popFront(QByteArray &ba, qint64 n)
+    {
+        ba = QByteArray(ba.constData() + n, ba.size() - n);
+    }
+
+    inline void squeezeFirst()
+    {
+        if (!buffers.isEmpty() && firstPos > 0) {
+            popFront(buffers.first(), firstPos);
+            firstPos = 0;
+        }
+    }
+
+    inline void append(const QByteDataBuffer& other)
     {
         if (other.isEmpty())
             return;
 
         buffers.append(other.buffers);
         bufferCompleteSize += other.byteAmount();
+
+        if (other.firstPos > 0)
+            popFront(buffers[bufferCount() - other.bufferCount()], other.firstPos);
     }
 
 
@@ -93,11 +110,13 @@ public:
         bufferCompleteSize += bd.size();
     }
 
-    inline void prepend(QByteArray& bd)
+    inline void prepend(const QByteArray& bd)
     {
         if (bd.isEmpty())
             return;
 
+        squeezeFirst();
+
         buffers.prepend(bd);
         bufferCompleteSize += bd.size();
     }
@@ -106,6 +125,7 @@ public:
     // preferably use this function to read data.
     inline QByteArray read()
     {
+        squeezeFirst();
         bufferCompleteSize -= buffers.first().size();
         return buffers.takeFirst();
     }
@@ -137,27 +157,22 @@ public:
         char *writeDst = dst;
 
         while (amount > 0) {
-            QByteArray first = buffers.takeFirst();
-            if (amount >= first.size()) {
+            const QByteArray &first = buffers.first();
+            qint64 firstSize = first.size() - firstPos;
+            if (amount >= firstSize) {
                 // take it completely
-                bufferCompleteSize -= first.size();
-                amount -= first.size();
-                memcpy(writeDst, first.constData(), first.size());
-                writeDst += first.size();
-                first.clear();
+                bufferCompleteSize -= firstSize;
+                amount -= firstSize;
+                memcpy(writeDst, first.constData() + firstPos, firstSize);
+                writeDst += firstSize;
+                firstPos = 0;
+                buffers.takeFirst();
             } else {
                 // take a part of it & it is the last one to take
                 bufferCompleteSize -= amount;
-                memcpy(writeDst, first.constData(), amount);
-
-                qint64 newFirstSize = first.size() - amount;
-                QByteArray newFirstData;
-                newFirstData.resize(newFirstSize);
-                memcpy(newFirstData.data(), first.constData() + amount, newFirstSize);
-                buffers.prepend(newFirstData);
-
+                memcpy(writeDst, first.constData() + firstPos, amount);
+                firstPos += amount;
                 amount = 0;
-                first.clear();
             }
         }
 
@@ -175,6 +190,7 @@ public:
     {
         buffers.clear();
         bufferCompleteSize = 0;
+        firstPos = 0;
     }
 
     // The byte count of all QByteArrays
@@ -199,18 +215,28 @@ public:
         if(buffers.isEmpty())
             return 0;
         else
-            return buffers.first().size();
+            return buffers.first().size() - firstPos;
     }
 
     inline QByteArray& operator[](int i)
     {
+        if (i == 0)
+            squeezeFirst();
+
         return buffers[i];
     }
 
     inline bool canReadLine() const {
-        for (int i = 0; i < buffers.length(); i++)
-            if (buffers.at(i).contains('\n'))
+        int i = 0;
+        if (i < buffers.length()) {
+            if (buffers.at(i).indexOf('\n', firstPos) != -1)
                 return true;
+            ++i;
+
+            for (; i < buffers.length(); i++)
+                if (buffers.at(i).contains('\n'))
+                    return true;
+        }
         return false;
     }
 };
diff --git a/tests/auto/corelib/tools/qbytedatabuffer/.gitignore b/tests/auto/corelib/tools/qbytedatabuffer/.gitignore
new file mode 100644
index 0000000000..3024a4dba2
--- /dev/null
+++ b/tests/auto/corelib/tools/qbytedatabuffer/.gitignore
@@ -0,0 +1 @@
+tst_qbytedatabuffer
diff --git a/tests/auto/corelib/tools/qbytedatabuffer/qbytedatabuffer.pro b/tests/auto/corelib/tools/qbytedatabuffer/qbytedatabuffer.pro
new file mode 100644
index 0000000000..135b1ff8c4
--- /dev/null
+++ b/tests/auto/corelib/tools/qbytedatabuffer/qbytedatabuffer.pro
@@ -0,0 +1,4 @@
+TARGET = tst_qbytedatabuffer
+CONFIG += testcase
+QT += core-private testlib
+SOURCES += tst_qbytedatabuffer.cpp
diff --git a/tests/auto/corelib/tools/qbytedatabuffer/tst_qbytedatabuffer.cpp b/tests/auto/corelib/tools/qbytedatabuffer/tst_qbytedatabuffer.cpp
new file mode 100644
index 0000000000..710da6cab3
--- /dev/null
+++ b/tests/auto/corelib/tools/qbytedatabuffer/tst_qbytedatabuffer.cpp
@@ -0,0 +1,174 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Hewlett-Packard Development Company, L.P.
+** Contact: http://www.qt-project.org/legal
+**
+** This file is part of the test suite of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and Digia.  For licensing terms and
+** conditions see http://qt.digia.com/licensing.  For further information
+** use the contact form at http://qt.digia.com/contact-us.
+**
+** 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, Digia gives you certain additional
+** rights.  These rights are described in the Digia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include <QTest>
+#include <private/qbytedata_p.h>
+// for QIODEVICE_BUFFERSIZE macro (== 16384):
+#include <private/qiodevice_p.h>
+
+class tst_QByteDataBuffer : public QObject
+{
+    Q_OBJECT
+private Q_SLOTS:
+    void canReadLine();
+    void positionHandling();
+    void appendBuffer();
+    void readCompleteBuffer_data();
+    void readCompleteBuffer();
+    void readPartialBuffer_data();
+    void readPartialBuffer();
+private:
+    void readBuffer(int size, int readSize);
+};
+
+void tst_QByteDataBuffer::canReadLine()
+{
+    QByteDataBuffer buf;
+    buf.append(QByteArray("a"));
+    buf.append(QByteArray("\nb"));
+    QVERIFY(buf.canReadLine());
+    QVERIFY(buf.getChar() == 'a');
+    QVERIFY(buf.canReadLine());
+    QVERIFY(buf.getChar() == '\n');
+    QVERIFY(!buf.canReadLine());
+}
+
+void tst_QByteDataBuffer::positionHandling()
+{
+    QByteDataBuffer buf;
+    buf.append(QByteArray("abc"));
+    buf.append(QByteArray("def"));
+
+    QCOMPARE(buf.byteAmount(), (qlonglong)6);
+    QCOMPARE(buf.sizeNextBlock(), (qlonglong)3);
+
+    QCOMPARE(buf.getChar(), 'a');
+    QCOMPARE(buf.byteAmount(), (qlonglong)5);
+    QCOMPARE(buf.sizeNextBlock(), (qlonglong)2);
+
+    QVERIFY(!strcmp(buf[0].constData(), "bc"));
+    QCOMPARE(buf.getChar(), 'b');
+    QCOMPARE(buf.byteAmount(), (qlonglong)4);
+    QCOMPARE(buf.sizeNextBlock(), (qlonglong)1);
+
+    QByteArray tmp("ab");
+    buf.prepend(tmp);
+    QCOMPARE(buf.byteAmount(), (qlonglong)6);
+    QVERIFY(!strcmp(buf.readAll().constData(), "abcdef"));
+    QCOMPARE(buf.byteAmount(), (qlonglong)0);
+
+    QByteDataBuffer buf2;
+    buf2.append(QByteArray("abc"));
+    buf2.getChar();
+    QCOMPARE(buf2.read(), QByteArray("bc"));
+}
+
+void tst_QByteDataBuffer::appendBuffer()
+{
+    QByteDataBuffer buf;
+    buf.append(QByteArray("\1\2\3"));
+    buf.getChar();
+
+    QByteDataBuffer tmp;
+    tmp.append(buf);
+    QCOMPARE(tmp.readAll(), buf.readAll());
+}
+
+static QByteArray makeByteArray(int size)
+{
+    QByteArray array;
+    array.resize(size);
+    char *data = array.data();
+    for (int i = 0; i < size; ++i)
+        data[i] = i % 256;
+    return array;
+}
+
+
+void tst_QByteDataBuffer::readBuffer(int size, int readSize)
+{
+    QByteArray data = makeByteArray(size);
+
+    QByteDataBuffer buf;
+    buf.append(data);
+
+    QByteArray tmp;
+    tmp.resize(size);
+
+    QBENCHMARK_ONCE {
+        for (int i = 0; i < (size - 1) / readSize + 1; ++i)
+            buf.read(tmp.data() + i * readSize, readSize);
+    }
+
+    QCOMPARE(data.size(), tmp.size());
+    QCOMPARE(data, tmp);
+}
+
+void tst_QByteDataBuffer::readCompleteBuffer_data()
+{
+    QTest::addColumn<int>("size");
+    QTest::newRow("10B") << (int)10;
+    QTest::newRow("1MB") << (int)1e6;
+    QTest::newRow("5MB") << (int)5e6;
+    QTest::newRow("10MB") << (int)10e6;
+}
+
+void tst_QByteDataBuffer::readCompleteBuffer()
+{
+    QFETCH(int, size);
+    readBuffer(size, size);
+}
+
+void tst_QByteDataBuffer::readPartialBuffer_data()
+{
+    readCompleteBuffer_data();
+}
+
+void tst_QByteDataBuffer::readPartialBuffer()
+{
+    QFETCH(int, size);
+    // QIODevice::readAll() reads in QIODEVICE_BUFFERSIZE size
+    // increments.
+    readBuffer(size, QIODEVICE_BUFFERSIZE);
+}
+
+QTEST_MAIN(tst_QByteDataBuffer)
+#include "tst_qbytedatabuffer.moc"
diff --git a/tests/auto/corelib/tools/tools.pro b/tests/auto/corelib/tools/tools.pro
index 47b0c5aa47..100409e58b 100644
--- a/tests/auto/corelib/tools/tools.pro
+++ b/tests/auto/corelib/tools/tools.pro
@@ -5,6 +5,7 @@ SUBDIRS=\
     qbitarray \
     qbytearray \
     qbytearraymatcher \
+    qbytedatabuffer \
     qcache \
     qchar \
     qcontiguouscache \
diff --git a/tests/benchmarks/network/access/access.pro b/tests/benchmarks/network/access/access.pro
index 6cbd3671b8..46b7a5f44d 100644
--- a/tests/benchmarks/network/access/access.pro
+++ b/tests/benchmarks/network/access/access.pro
@@ -2,4 +2,5 @@ TEMPLATE = subdirs
 SUBDIRS = \
         qfile_vs_qnetworkaccessmanager \
         qnetworkreply \
+        qnetworkreply_from_cache \
         qnetworkdiskcache
diff --git a/tests/benchmarks/network/access/qnetworkreply_from_cache/.gitignore b/tests/benchmarks/network/access/qnetworkreply_from_cache/.gitignore
new file mode 100644
index 0000000000..219c731a56
--- /dev/null
+++ b/tests/benchmarks/network/access/qnetworkreply_from_cache/.gitignore
@@ -0,0 +1 @@
+tst_bench_qnetworkreply_from_cache
diff --git a/tests/benchmarks/network/access/qnetworkreply_from_cache/qnetworkreply_from_cache.pro b/tests/benchmarks/network/access/qnetworkreply_from_cache/qnetworkreply_from_cache.pro
new file mode 100644
index 0000000000..872e9c9cd5
--- /dev/null
+++ b/tests/benchmarks/network/access/qnetworkreply_from_cache/qnetworkreply_from_cache.pro
@@ -0,0 +1,4 @@
+TARGET = tst_bench_qnetworkreply_from_cache
+CONFIG += testcase
+QT += network testlib
+SOURCES += tst_qnetworkreply_from_cache.cpp
diff --git a/tests/benchmarks/network/access/qnetworkreply_from_cache/tst_qnetworkreply_from_cache.cpp b/tests/benchmarks/network/access/qnetworkreply_from_cache/tst_qnetworkreply_from_cache.cpp
new file mode 100644
index 0000000000..b4ce14fd23
--- /dev/null
+++ b/tests/benchmarks/network/access/qnetworkreply_from_cache/tst_qnetworkreply_from_cache.cpp
@@ -0,0 +1,230 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Hewlett-Packard Development Company, L.P.
+** Contact: http://www.qt-project.org/legal
+**
+** This file is part of the test suite of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and Digia.  For licensing terms and
+** conditions see http://qt.digia.com/licensing.  For further information
+** use the contact form at http://qt.digia.com/contact-us.
+**
+** 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, Digia gives you certain additional
+** rights.  These rights are described in the Digia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include <QtTest/QtTest>
+#include <QtNetwork/QNetworkAccessManager>
+#include <QtNetwork/QNetworkDiskCache>
+#include <QtNetwork/QNetworkReply>
+#include <QtNetwork/QTcpServer>
+#include <QtNetwork/QTcpSocket>
+
+#define TEST_CASE_TIMEOUT 30
+
+class NetworkDiskCache : public QNetworkDiskCache
+{
+public:
+    NetworkDiskCache(QObject *parent = 0)
+        : QNetworkDiskCache(parent)
+    {
+    }
+
+    QByteArray cachedData;
+
+    virtual QNetworkCacheMetaData metaData(const QUrl &url)
+    {
+        QNetworkCacheMetaData metaData;
+        if (!cachedData.isEmpty()) {
+            metaData.setUrl(url);
+            QDateTime now = QDateTime::currentDateTime();
+            metaData.setLastModified(now.addDays(-1));
+            metaData.setExpirationDate(now.addDays(1));
+            metaData.setSaveToDisk(true);
+        }
+        return metaData;
+    }
+
+    virtual QIODevice *data(const QUrl &/*url*/)
+    {
+        if (cachedData.isEmpty())
+            return 0;
+
+        QBuffer *buffer = new QBuffer;
+        buffer->setData(cachedData);
+        buffer->open(QIODevice::ReadOnly);
+        return buffer;
+    }
+};
+
+class HttpServer : public QTcpServer
+{
+    Q_OBJECT
+public:
+    HttpServer(const QByteArray &reply)
+        : m_reply(reply), m_writePos(), m_client()
+    {
+        listen(QHostAddress::AnyIPv4);
+        connect(this, SIGNAL(newConnection()), this, SLOT(accept()));
+    }
+
+private Q_SLOTS:
+    void accept()
+    {
+        m_client = nextPendingConnection();
+        m_client->setParent(this);
+        connect(m_client, SIGNAL(readyRead()), this, SLOT(reply()));
+    }
+
+    void reply()
+    {
+        disconnect(m_client, SIGNAL(readyRead()));
+        m_client->readAll();
+        connect(m_client, SIGNAL(bytesWritten(qint64)), this, SLOT(write()));
+        write();
+    }
+
+    void write()
+    {
+        qint64 pos = m_client->write(m_reply.mid(m_writePos));
+        if (pos > 0)
+            m_writePos += pos;
+        if (m_writePos >= m_reply.size())
+            m_client->disconnect();
+    }
+
+private:
+    QByteArray m_reply;
+    qint64 m_writePos;
+    QTcpSocket *m_client;
+};
+
+class tst_qnetworkreply_from_cache : public QObject
+{
+    Q_OBJECT
+public:
+    tst_qnetworkreply_from_cache();
+
+    void timeReadAll(const QString &headers, const QByteArray &data = QByteArray());
+
+private Q_SLOTS:
+    void initTestCase();
+    void cleanup();
+
+    void readAll_data();
+    void readAll();
+    void readAllFromCache_data();
+    void readAllFromCache();
+
+protected Q_SLOTS:
+    void replyReadAll() { m_replyData += m_reply->readAll(); }
+
+private:
+    QTemporaryDir m_tempDir;
+    QNetworkAccessManager *m_networkAccessManager;
+    NetworkDiskCache *m_networkDiskCache;
+    QNetworkReply *m_reply;
+    QByteArray m_replyData;
+};
+
+tst_qnetworkreply_from_cache::tst_qnetworkreply_from_cache()
+    : m_tempDir(QDir::tempPath() + "/tst_qnetworkreply_from_cache.XXXXXX")
+{
+}
+
+void tst_qnetworkreply_from_cache::timeReadAll(const QString &headers, const QByteArray &data)
+{
+    QByteArray reply;
+    reply.append(headers);
+    reply.append(data);
+
+    m_replyData.reserve(data.size());
+
+    HttpServer server(reply);
+
+    QBENCHMARK_ONCE {
+        QNetworkRequest request(QUrl(QString("http://127.0.0.1:%1").arg(server.serverPort())));
+        m_reply = m_networkAccessManager->get(request);
+        connect(m_reply, SIGNAL(readyRead()), this, SLOT(replyReadAll()), Qt::QueuedConnection);
+        connect(m_reply, SIGNAL(finished()), &QTestEventLoop::instance(), SLOT(exitLoop()), Qt::QueuedConnection);
+        QTestEventLoop::instance().enterLoop(TEST_CASE_TIMEOUT);
+        QVERIFY(!QTestEventLoop::instance().timeout());
+        delete m_reply;
+    }
+
+    QCOMPARE(data.size(), m_replyData.size());
+    QCOMPARE(data, m_replyData);
+}
+
+void tst_qnetworkreply_from_cache::initTestCase()
+{
+    m_networkAccessManager = new QNetworkAccessManager(this);
+    m_networkDiskCache = new NetworkDiskCache(m_networkAccessManager);
+    m_networkDiskCache->setCacheDirectory(m_tempDir.path());
+    m_networkAccessManager->setCache(m_networkDiskCache);
+}
+
+void tst_qnetworkreply_from_cache::cleanup()
+{
+    m_replyData.clear();
+}
+
+void tst_qnetworkreply_from_cache::readAll_data()
+{
+    QTest::addColumn<int>("dataSize");
+    QTest::newRow("1MB") << (int)1e6;
+    QTest::newRow("5MB") << (int)5e6;
+    QTest::newRow("10MB") << (int)10e6;
+}
+
+void tst_qnetworkreply_from_cache::readAll()
+{
+    QFETCH(int, dataSize);
+    QString headers = QString("HTTP/1.0 200 OK\r\nContent-Length: %1\r\n\r\n").arg(dataSize);
+    QByteArray data(QByteArray(dataSize, (char)42));
+    m_networkDiskCache->cachedData.clear();
+    timeReadAll(headers, data);
+}
+
+void tst_qnetworkreply_from_cache::readAllFromCache_data()
+{
+    readAll_data();
+}
+
+void tst_qnetworkreply_from_cache::readAllFromCache()
+{
+    QFETCH(int, dataSize);
+    QByteArray headers("HTTP/1.0 304 Use Cache\r\n\r\n");
+    QByteArray data(QByteArray(dataSize, (char)42));
+    m_networkDiskCache->cachedData = data;
+    timeReadAll(headers, data);
+}
+
+QTEST_MAIN(tst_qnetworkreply_from_cache)
+#include "tst_qnetworkreply_from_cache.moc"