QIODevice::read() and QFile::atEnd() performance improvements

atEnd improvements, since atEnd is used in published example Qt read
loops. The two main ideas are to push the buffer test forward, which
optimises the normal buffered case, and to cache the file size till you
get to the end, which otherwise has to get the file size every 16K of
data.

read buffer improvements: The ring buffer structure was causing
significant performance overheads. In practice QIODevice has much
simpler requirements on its read buffer, and a linear buffer can be
used instead. This now uses a buffer optimised to QIODevice's use of
it.

QIODevice read function improvements. There are a number of sub-themes
here, which all are aimed at getting the normal buffered path through
the code done as fast as possible. This gives greatest improvements for
small reads, but it is these small reads that have the biggest
problems.
- removing the isSequential test, by setting a pointer to the qint64
  to update and using a dummy qint64 target when isSequential, then
  writing through the pointer.
- doing the readability check on the first read only, out of the fast
  path
- doing the maxSize<0 test after the getchar fast path
- removing the buffer isEmpty test and giving a fast exit test
  instead
- moving arithmetic out of the fast path, so "data" and "maxSize"
  are now dynamically updating
- for RCVT builds, ARM mode is used for the read functions because
  the 64-bit operations are much slower with this compiler in Thumb
  mode

There are some other changes to read() which improve clarity:
- bytesToBuffer is now always set to QIODEVICE_BUFFERSIZE. This has
  always been the case, its just that the logic was not clear before.
- moreToRead is set to false now in the case where the request was
  met by a direct device read. Leaving it true in this case was
  pointless, and setting it true in the converse case seems dangerous
  because the function might iterate for a very long time, although
  it might meet the API semantics better and would be a change in
  behavior because the function used to not read more when it claimed
  it would.

Reviewed-by: Joao
Reviewed-by: Aleksandar Babic

4 files changed, 260 insertions, 78 deletions

diff --git a/src/corelib/io/qfile.cpp b/src/corelib/io/qfile.cpp
index aa1c7d93cd..50e9a8ffc6 100644
--- a/src/corelib/io/qfile.cpp
+++ b/src/corelib/io/qfile.cpp
@@ -90,7 +90,8 @@ QFile::DecoderFn QFilePrivate::decoder = locale_decode;
 
 QFilePrivate::QFilePrivate()
     : fileEngine(0), lastWasWrite(false),
-      writeBuffer(QFILE_WRITEBUFFER_SIZE), error(QFile::NoError)
+      writeBuffer(QFILE_WRITEBUFFER_SIZE), error(QFile::NoError),
+      cachedSize(0)
 {
 }
 
@@ -1257,8 +1258,10 @@ QFile::resize(qint64 sz)
         seek(sz);
     if(d->fileEngine->setSize(sz)) {
         unsetError();
+        d->cachedSize = sz;
         return true;
     }
+    d->cachedSize = 0;
     d->setError(QFile::ResizeError, d->fileEngine->errorString());
     return false;
 }
@@ -1420,7 +1423,8 @@ qint64 QFile::size() const
     Q_D(const QFile);
     if (!d->ensureFlushed())
         return 0;
-    return fileEngine()->size();
+    d->cachedSize = fileEngine()->size();
+    return d->cachedSize;
 }
 
 /*!
@@ -1446,16 +1450,16 @@ bool QFile::atEnd() const
 {
     Q_D(const QFile);
 
+    // If there's buffered data left, we're not at the end.
+    if (!d->buffer.isEmpty())
+        return false;
+
     if (!isOpen())
         return true;
 
     if (!d->ensureFlushed())
         return false;
 
-    // If there's buffered data left, we're not at the end.
-    if (!d->buffer.isEmpty())
-        return false;
-
     // If the file engine knows best, say what it says.
     if (d->fileEngine->supportsExtension(QAbstractFileEngine::AtEndExtension)) {
         // Check if the file engine supports AtEndExtension, and if it does,
@@ -1463,6 +1467,11 @@ bool QFile::atEnd() const
         return d->fileEngine->atEnd();
     }
 
+    // if it looks like we are at the end, or if size is not cached,
+    // fall through to bytesAvailable() to make sure.
+    if (pos() < d->cachedSize)
+        return false;
+
     // Fall back to checking how much is available (will stat files).
     return bytesAvailable() == 0;
 }
@@ -1502,12 +1511,21 @@ qint64 QFile::readLineData(char *data, qint64 maxlen)
     if (!d->ensureFlushed())
         return -1;
 
-    if (d->fileEngine->supportsExtension(QAbstractFileEngine::FastReadLineExtension))
-        return d->fileEngine->readLine(data, maxlen);
+    qint64 read;
+    if (d->fileEngine->supportsExtension(QAbstractFileEngine::FastReadLineExtension)) {
+        read = d->fileEngine->readLine(data, maxlen);
+    } else {
+        // Fall back to QIODevice's readLine implementation if the engine
+        // cannot do it faster.
+        read = QIODevice::readLineData(data, maxlen);
+    }
+
+    if (read < maxlen) {
+        // failed to read all requested, may be at the end of file, stop caching size so that it's rechecked
+        d->cachedSize = 0;
+    }
 
-    // Fall back to QIODevice's readLine implementation if the engine
-    // cannot do it faster.
-    return QIODevice::readLineData(data, maxlen);
+    return read;
 }
 
 /*!
@@ -1528,6 +1546,12 @@ qint64 QFile::readData(char *data, qint64 len)
             err = QFile::ReadError;
         d->setError(err, d->fileEngine->errorString());
     }
+
+    if (read < len) {
+        // failed to read all requested, may be at the end of file, stop caching size so that it's rechecked
+        d->cachedSize = 0;
+    }
+
     return read;
 }
 
diff --git a/src/corelib/io/qfile_p.h b/src/corelib/io/qfile_p.h
index f8f5f5ccff..cf76c09e8d 100644
--- a/src/corelib/io/qfile_p.h
+++ b/src/corelib/io/qfile_p.h
@@ -84,6 +84,8 @@ protected:
     void setError(QFile::FileError err, const QString &errorString);
     void setError(QFile::FileError err, int errNum);
 
+    mutable qint64 cachedSize;
+
 private:
     static QFile::EncoderFn encoder;
     static QFile::DecoderFn decoder;
diff --git a/src/corelib/io/qiodevice.cpp b/src/corelib/io/qiodevice.cpp
index c93f0c3e3f..f83c1423f8 100644
--- a/src/corelib/io/qiodevice.cpp
+++ b/src/corelib/io/qiodevice.cpp
@@ -84,10 +84,6 @@ void debugBinaryString(const char *data, qint64 maxlen)
 }
 #endif
 
-#ifndef QIODEVICE_BUFFERSIZE
-#define QIODEVICE_BUFFERSIZE Q_INT64_C(16384)
-#endif
-
 #define Q_VOID
 
 #define CHECK_MAXLEN(function, returnType) \
@@ -123,7 +119,9 @@ void debugBinaryString(const char *data, qint64 maxlen)
 QIODevicePrivate::QIODevicePrivate()
     : openMode(QIODevice::NotOpen), buffer(QIODEVICE_BUFFERSIZE),
       pos(0), devicePos(0)
+       , pPos(&pos), pDevicePos(&devicePos)
        , baseReadLineDataCalled(false)
+       , firstRead(true)
        , accessMode(Unset)
 #ifdef QT_NO_QOBJECT
        , q_ptr(0)
@@ -449,11 +447,15 @@ QIODevice::OpenMode QIODevice::openMode() const
 */
 void QIODevice::setOpenMode(OpenMode openMode)
 {
+    Q_D(QIODevice);
 #if defined QIODEVICE_DEBUG
     printf("%p QIODevice::setOpenMode(0x%x)\n", this, int(openMode));
 #endif
-    d_func()->openMode = openMode;
-    d_func()->accessMode = QIODevicePrivate::Unset;
+    d->openMode = openMode;
+    d->accessMode = QIODevicePrivate::Unset;
+    d->firstRead = true;
+    if (!isReadable())
+        d->buffer.clear();
 }
 
 /*!
@@ -537,6 +539,7 @@ bool QIODevice::open(OpenMode mode)
     d->pos = (mode & Append) ? size() : qint64(0);
     d->buffer.clear();
     d->accessMode = QIODevicePrivate::Unset;
+    d->firstRead = true;
 #if defined QIODEVICE_DEBUG
     printf("%p QIODevice::open(0x%x)\n", this, quint32(mode));
 #endif
@@ -566,6 +569,7 @@ void QIODevice::close()
     d->errorString.clear();
     d->pos = 0;
     d->buffer.clear();
+    d->firstRead = true;
 }
 
 /*!
@@ -729,6 +733,12 @@ qint64 QIODevice::bytesToWrite() const
     return qint64(0);
 }
 
+#ifdef Q_CC_RVCT
+// arm mode makes the 64-bit integer operations much faster in RVCT 2.2
+#pragma push
+#pragma arm
+#endif
+
 /*!
     Reads at most \a maxSize bytes from the device into \a data, and
     returns the number of bytes read. If an error occurs, such as when
@@ -745,21 +755,17 @@ qint64 QIODevice::bytesToWrite() const
 qint64 QIODevice::read(char *data, qint64 maxSize)
 {
     Q_D(QIODevice);
-    CHECK_READABLE(read, qint64(-1));
-    CHECK_MAXLEN(read, qint64(-1));
 
 #if defined QIODEVICE_DEBUG
     printf("%p QIODevice::read(%p, %d), d->pos = %d, d->buffer.size() = %d\n",
            this, data, int(maxSize), int(d->pos), int(d->buffer.size()));
 #endif
-    const bool sequential = d->isSequential();
 
     // Short circuit for getChar()
     if (maxSize == 1) {
         int chint;
         while ((chint = d->buffer.getChar()) != -1) {
-            if (!sequential)
-                ++d->pos;
+            ++(*d->pPos);
 
             char c = char(uchar(chint));
             if (c == '\r' && (d->openMode & Text))
@@ -773,61 +779,77 @@ qint64 QIODevice::read(char *data, qint64 maxSize)
         }
     }
 
+    CHECK_MAXLEN(read, qint64(-1));
     qint64 readSoFar = 0;
     bool moreToRead = true;
     do {
-        int lastReadChunkSize = 0;
-
         // Try reading from the buffer.
-        if (!d->buffer.isEmpty()) {
-            lastReadChunkSize = d->buffer.read(data + readSoFar, maxSize - readSoFar);
-            readSoFar += lastReadChunkSize;
-            if (!sequential)
-                d->pos += lastReadChunkSize;
+        int lastReadChunkSize = d->buffer.read(data, maxSize);
+        *d->pPos += lastReadChunkSize;
+        readSoFar += lastReadChunkSize;
+        // fast exit when satisfied by buffer
+        if (lastReadChunkSize == maxSize && !(d->openMode & Text))
+            return readSoFar;
+
+        if (lastReadChunkSize > 0) {
+            data += lastReadChunkSize;
+            maxSize -= lastReadChunkSize;
 #if defined QIODEVICE_DEBUG
             printf("%p \treading %d bytes from buffer into position %d\n", this, lastReadChunkSize,
                    int(readSoFar) - lastReadChunkSize);
 #endif
-        } else if ((d->openMode & Unbuffered) == 0 && maxSize < QIODEVICE_BUFFERSIZE) {
-            // In buffered mode, we try to fill up the QIODevice buffer before
-            // we do anything else.
-            int bytesToBuffer = qMax(maxSize - readSoFar, QIODEVICE_BUFFERSIZE);
-            char *writePointer = d->buffer.reserve(bytesToBuffer);
-
-            // Make sure the device is positioned correctly.
-            if (d->pos != d->devicePos && !sequential && !seek(d->pos))
-                return qint64(-1);
-            qint64 readFromDevice = readData(writePointer, bytesToBuffer);
-            d->buffer.chop(bytesToBuffer - (readFromDevice < 0 ? 0 : int(readFromDevice)));
+        } else {
+            if (d->firstRead) {
+                // this is the first time the file has been read, check it's valid and set up pos pointers
+                // for fast pos updates.
+                CHECK_READABLE(read, qint64(-1));
+                d->firstRead = false;
+                if (d->isSequential()) {
+                    d->pPos = &d->seqDumpPos;
+                    d->pDevicePos = &d->seqDumpPos;
+                }
+            }
 
-            if (readFromDevice > 0) {
-                if (!sequential)
-                    d->devicePos += readFromDevice;
+            if ((d->openMode & Unbuffered) == 0 && maxSize < QIODEVICE_BUFFERSIZE) {
+                // In buffered mode, we try to fill up the QIODevice buffer before
+                // we do anything else.
+                // buffer is empty at this point, try to fill it
+                int bytesToBuffer = QIODEVICE_BUFFERSIZE;
+                char *writePointer = d->buffer.reserve(bytesToBuffer);
+
+                // Make sure the device is positioned correctly.
+                if (d->pos != d->devicePos && !d->isSequential() && !seek(d->pos))
+                    return readSoFar ? readSoFar : qint64(-1);
+                qint64 readFromDevice = readData(writePointer, bytesToBuffer);
+                d->buffer.chop(bytesToBuffer - (readFromDevice < 0 ? 0 : int(readFromDevice)));
+
+                if (readFromDevice > 0) {
+                    *d->pDevicePos += readFromDevice;
 #if defined QIODEVICE_DEBUG
-                printf("%p \treading %d from device into buffer\n", this, int(readFromDevice));
+                    printf("%p \treading %d from device into buffer\n", this, int(readFromDevice));
 #endif
 
-                if (readFromDevice < bytesToBuffer)
-                    d->buffer.truncate(int(readFromDevice));
-                if (!d->buffer.isEmpty()) {
-                    lastReadChunkSize = d->buffer.read(data + readSoFar, maxSize - readSoFar);
-                    readSoFar += lastReadChunkSize;
-                    if (!sequential)
-                        d->pos += lastReadChunkSize;
+                    if (!d->buffer.isEmpty()) {
+                        lastReadChunkSize = d->buffer.read(data, maxSize);
+                        readSoFar += lastReadChunkSize;
+                        data += lastReadChunkSize;
+                        maxSize -= lastReadChunkSize;
+                        *d->pPos += lastReadChunkSize;
 #if defined QIODEVICE_DEBUG
-                    printf("%p \treading %d bytes from buffer at position %d\n", this,
-                           lastReadChunkSize, int(readSoFar));
+                        printf("%p \treading %d bytes from buffer at position %d\n", this,
+                               lastReadChunkSize, int(readSoFar));
 #endif
+                    }
                 }
             }
         }
 
         // If we need more, try reading from the device.
-        if (readSoFar < maxSize) {
+        if (maxSize > 0) {
             // Make sure the device is positioned correctly.
-            if (d->pos != d->devicePos && !sequential && !seek(d->pos))
-                return qint64(-1);
-            qint64 readFromDevice = readData(data + readSoFar, maxSize - readSoFar);
+            if (d->pos != d->devicePos && !d->isSequential() && !seek(d->pos))
+                return readSoFar ? readSoFar : qint64(-1);
+            qint64 readFromDevice = readData(data, maxSize);
 #if defined QIODEVICE_DEBUG
             printf("%p \treading %d bytes from device (total %d)\n", this, int(readFromDevice), int(readSoFar));
 #endif
@@ -835,27 +857,21 @@ qint64 QIODevice::read(char *data, qint64 maxSize)
                 // error and we haven't read anything: return immediately
                 return -1;
             }
-            if (readFromDevice <= 0) {
-                moreToRead = false;
-            } else {
-                // see if we read as much data as we asked for
-                if (readFromDevice < maxSize - readSoFar)
-                    moreToRead = false;
-
+            if (readFromDevice > 0) {
                 lastReadChunkSize += int(readFromDevice);
                 readSoFar += readFromDevice;
-                if (!sequential) {
-                    d->pos += readFromDevice;
-                    d->devicePos += readFromDevice;
-                }
+                data += readFromDevice;
+                maxSize -= readFromDevice;
+                *d->pPos += readFromDevice;
+                *d->pDevicePos += readFromDevice;
             }
-        } else {
-            moreToRead = false;
         }
+        // Best attempt has been made to read data, don't try again except for text mode adjustment below
+        moreToRead = false;
 
         if (readSoFar && d->openMode & Text) {
-            char *readPtr = data + readSoFar - lastReadChunkSize;
-            const char *endPtr = data + readSoFar;
+            char *readPtr = data - lastReadChunkSize;
+            const char *endPtr = data;
 
             if (readPtr < endPtr) {
                 // optimization to avoid initial self-assignment
@@ -870,8 +886,11 @@ qint64 QIODevice::read(char *data, qint64 maxSize)
                     char ch = *readPtr++;
                     if (ch != '\r')
                         *writePtr++ = ch;
-                    else
+                    else {
                         --readSoFar;
+                        --data;
+                        ++maxSize;
+                    }
                 }
 
                 // Make sure we get more data if there is room for more. This
@@ -885,11 +904,15 @@ qint64 QIODevice::read(char *data, qint64 maxSize)
 #if defined QIODEVICE_DEBUG
     printf("%p \treturning %d, d->pos == %d, d->buffer.size() == %d\n", this,
            int(readSoFar), int(d->pos), d->buffer.size());
-    debugBinaryString(data, readSoFar);
+    debugBinaryString(data - readSoFar, readSoFar);
 #endif
     return readSoFar;
 }
 
+#ifdef Q_CC_RVCT
+#pragma pop
+#endif
+
 /*!
     \overload
 
@@ -997,6 +1020,12 @@ QByteArray QIODevice::readAll()
     return result;
 }
 
+#ifdef Q_CC_RVCT
+// arm mode makes the 64-bit integer operations much faster in RVCT 2.2
+#pragma push
+#pragma arm
+#endif
+
 /*!
     This function reads a line of ASCII characters from the device, up
     to a maximum of \a maxSize - 1 bytes, stores the characters in \a
@@ -1229,6 +1258,10 @@ qint64 QIODevice::readLineData(char *data, qint64 maxSize)
     return readSoFar;
 }
 
+#ifdef Q_CC_RVCT
+#pragma pop
+#endif
+
 /*!
     Returns true if a complete line of data can be read from the device;
     otherwise returns false.
@@ -1416,9 +1449,7 @@ bool QIODevicePrivate::putCharHelper(char c)
 */
 bool QIODevice::getChar(char *c)
 {
-    Q_D(QIODevice);
-    CHECK_READABLE(getChar, false);
-
+    // readability checked in read()
     char ch;
     return (1 == read(c ? c : &ch, 1));
 }
diff --git a/src/corelib/io/qiodevice_p.h b/src/corelib/io/qiodevice_p.h
index cc4a237140..94dadca76d 100644
--- a/src/corelib/io/qiodevice_p.h
+++ b/src/corelib/io/qiodevice_p.h
@@ -64,6 +64,126 @@
 
 QT_BEGIN_NAMESPACE
 
+#ifndef QIODEVICE_BUFFERSIZE
+#define QIODEVICE_BUFFERSIZE Q_INT64_C(16384)
+#endif
+
+// This is QIODevice's read buffer, optimised for read(), isEmpty() and getChar()
+class QIODevicePrivateLinearBuffer
+{
+public:
+    QIODevicePrivateLinearBuffer(int) : len(0), first(0), buf(0), capacity(0) {
+    }
+    ~QIODevicePrivateLinearBuffer() {
+        delete [] buf;
+    }
+    void clear() {
+        first = buf;
+        len = 0;
+    }
+    int size() const {
+        return len;
+    }
+    bool isEmpty() const {
+        return len == 0;
+    }
+    void skip(int n) {
+        if (n >= len) {
+            clear();
+        } else {
+            len -= n;
+            first += n;
+        }
+    }
+    int getChar() {
+        if (len == 0)
+            return -1;
+        int ch = uchar(*first);
+        len--;
+        first++;
+        return ch;
+    }
+    int read(char* target, int size) {
+        int r = qMin(size, len);
+        memcpy(target, first, r);
+        len -= r;
+        first += r;
+        return r;
+    }
+    char* reserve(int size) {
+        makeSpace(size + len, freeSpaceAtEnd);
+        char* writePtr = first + len;
+        len += size;
+        return writePtr;
+    }
+    void chop(int size) {
+        if (size >= len) {
+            clear();
+        } else {
+            len -= size;
+        }
+    }
+    QByteArray readAll() {
+        char* f = first;
+        int l = len;
+        clear();
+        return QByteArray(f, l);
+    }
+    int readLine(char* target, int size) {
+        int r = qMin(size, len);
+        char* eol = static_cast<char*>(memchr(first, '\n', r));
+        if (eol)
+            r = 1+(eol-first);
+        memcpy(target, first, r);
+        len -= r;
+        first += r;
+        return int(r);
+        }
+    bool canReadLine() const {
+        return memchr(first, '\n', len);
+    }
+    void ungetChar(char c) {
+        if (first == buf) {
+            // underflow, the existing valid data needs to move to the end of the (potentially bigger) buffer
+            makeSpace(len+1, freeSpaceAtStart);
+        }
+        first--;
+        len++;
+        *first = c;
+    }
+
+private:
+    enum FreeSpacePos {freeSpaceAtStart, freeSpaceAtEnd};
+    void makeSpace(size_t required, FreeSpacePos where) {
+        size_t newCapacity = qMax(capacity, size_t(QIODEVICE_BUFFERSIZE));
+        while (newCapacity < required)
+            newCapacity *= 2;
+        int moveOffset = (where == freeSpaceAtEnd) ? 0 : newCapacity - len;
+        if (newCapacity > capacity) {
+            // allocate more space
+            char* newBuf = new char[newCapacity];
+            memmove(newBuf + moveOffset, first, len);
+            delete [] buf;
+            buf = newBuf;
+            capacity = newCapacity;
+        } else {
+            // shift any existing data to make space
+            memmove(buf + moveOffset, first, len);
+        }
+        first = buf + moveOffset;
+    }
+
+private:
+    // length of the unread data
+    int len;
+    // start of the unread data
+    char* first;
+    // the allocated buffer
+    char* buf;
+    // allocated buffer size
+    size_t capacity;
+};
+
 class Q_CORE_EXPORT QIODevicePrivate
 #ifndef QT_NO_QOBJECT
     : public QObjectPrivate
@@ -78,10 +198,15 @@ public:
     QIODevice::OpenMode openMode;
     QString errorString;
 
-    QRingBuffer buffer;
+    QIODevicePrivateLinearBuffer buffer;
     qint64 pos;
     qint64 devicePos;
+    // these three are for fast position updates during read, avoiding isSequential test
+    qint64 seqDumpPos;
+    qint64 *pPos;
+    qint64 *pDevicePos;
     bool baseReadLineDataCalled;
+    bool firstRead;
 
     virtual bool putCharHelper(char c);