What is QList's maximum size?

Question

Has anyone encountered a maximum size for QList?

I have a QList of pointers to my objects and have found that it silently throws an error when it reaches the 268,435,455th item, which is exactly 28 bits. I would have expected it to have at least a 31bit maximum size (minus one bit because size() returns a signed integer), or a 63bit maximum size on my 64bit computer, but this doesn't appear to be the case. I have confirmed this in a minimal example by executing QList<void*> mylist; mylist.append(0); in a counting loop.

To restate the question, what is the actual maximum size of QList? If it's not actually 2^32-1 then why? Is there a workaround?

I'm running a Windows 64bit build of Qt 4.8.5 for MSVC2010.

Tannenberg

Comments are not for extended discussion; this conversation has been moved to chat. – Haemolysin

Answer 1

While the other answers make a useful attempt at explaining the problem, none of them actually answer the question or missed the point. Thanks to everyone for helping me track down the issue.

As Ali Mofrad mentioned, the error thrown is a std::bad_alloc error when the QList fails to allocate additional space in my QList::append(MyObject*) call. Here's where that happens in the Qt source code:

qlist.cpp: line 62:
static int grow(int size)         //size = 268435456
{
    //this is the problem line
    volatile int x = qAllocMore(size * sizeof(void *), QListData::DataHeaderSize) / sizeof(void *);
    return x;                     //x = -2147483648
}

qlist.cpp: line 231:
void **QListData::append(int n)   //n = 1
{
    Q_ASSERT(d->ref == 1);
    int e = d->end;
    if (e + n > d->alloc) {
        int b = d->begin;
        if (b - n >= 2 * d->alloc / 3) {
            //...
       } else {
            realloc(grow(d->alloc + n));    //<-- grow() is called here
        }
    }
    d->end = e + n;
    return d->array + e;
}

In grow(), the new size requested (268,435,456) is multiplied by sizeof(void*) (8) to compute the size of the new block of memory to accommodate the growing QList. The problem is, 268435456*8 equals +2,147,483,648 if it's an unsigned int32, or -2,147,483,648 for a signed int32, which is what's getting returned from grow() on my OS. Therefore, when std::realloc() is called in QListData::realloc(int), we're trying to grow to a negative size.

The workaround here, as ddriver suggested, is to use QList::reserve() to pre-allocate the space, preventing my QList from ever having to grow.

In short, the maximum size for QList is 2^28-1 items unless you pre-allocate, in which case the maximum size truly is 2^31-1 as expected.

Update (Jan 2020): This appears to have changed in Qt 5.5, such that 2^28-1 is now the maximum size allowed for QList and QVector, regardless of whether or not you reserve in advance. A shame.

Tannenberg

Just in case you missed my last comment, consider switching to QVector or a std::vector and keeping the points in the container instead of allocating them dynamically and storing pointers to then, you will save on cpu time and memory big time. Also, if you really need to keep adding points, you might consider implementing your own container with more conservative growing policies – Observer

Note how the problem is not the multiplication (sizeof returns a size_t, which would be a 64 bit integer on 64 bits) but qAllocMore dealing with plain ints. And, that code has been significantly changed in Qt 5. – Trela

@Trela Good observation. I don't have the Qt5 source on me. Do they change QList and related functions to use a quint64 or size_t like it should? – Tannenberg

Update: I'm using Qt 5.11.1 right now, and it appears to have hard-coded the size limit to 2^28-1 items. QList::reserve() now throws a badalloc error when larger sizes are reserved. Relevant code is commented that it was added in Qt 5.7. I'm not aware of this being fixed in a newer version. – Tannenberg

Answer 2

Has anyone encountered a maximum size for QList? I have a QList of pointers to my objects and have found that it silently throws an error when it reaches the 268,435,455th item, which is exactly 28 bits. I would have expected it to have at least a 31bit maximum size (minus one bit because size() returns a signed integer), or a 63bit maximum size on my 64bit computer, but this doesn't appear to be the case.

Theoretical maximum positive number stored in int is 2^31 - 1. Size of pointer is 4 bytes (for 32bit machine), so maximum possible number of them is 2^29 - 1. Appending data to the container will increases fragmentation of heap memory, so there is possible that you can allocate only half of possible memory. Try use reserve() or resize() instead.

Moreover, Win32 has some limits for memory allocation. So application compiled without special options cannot allocate more than this limit (1G or 2G).

Are you sure about this huge containers? Is it better to optimize application?

Electromotive

I gave an upvote. The OP should also note that the code will not get 63 bits on 64 bit system with Qt containers, or even 2^(63-3) -1 = 2^60-1. Std containers should be used for those. The Qt containers are pretty limited for such things. This is related. One should also note that the kernel and other processes also require memory. – Homozygous

About 1GB or 2GB, that is true. – Idle

Answer 3

QList stores its elements in a void * array.

Hence, a list with 2²⁸ items, of which each one is a void *, will be 2³⁰ bytes long on a 32 bit machine, and 2³¹ bytes on a 64 bit machine. I doubt you can request such a big chunk of contiguous memory.

And why allocating such a huge list anyhow? Are you sure you really need it?

---

The idea of be backed by an array of void * elements is because several operations on the list can be moved to non-templated code, therefore reducing the amount of generated code.

QList stores items straight in the void * array if the type is small enough (i.e. sizeof(T) <= sizeof(void*)), and if the type can be moved in memory via memmove. Otherwise, each item will be allocated on the heap via new, and the array will store the pointers to those items. A set of type traits is used to figure out how to handle each type, see Q_DECLARE_TYPEINFO.

While in theory this approach may sound attractive, in practice:

• For all primitive types smaller than void * (char; int and float on 64 bit; etc.) you waste from 50 to 75% of the allocated space in the array
• For all movable types bigger than void * (double on 32bit, QVariant, ...), you pay a heap allocation per each item in the list (plus the array itself)
• QList code is generally less optimized than QVector one
• Compilers these days do a pretty good job at merging template instantiations, hence the original reason for this design gets lost.

Today it's a much better idea to stick with QVector. Unfortunately the Qt APIs expose QList everywhere and can't change them (and we need C++11 to define QList as a template alias for QVector...)

Trela

Answer 4

I test this in Ubuntu 32bit with 4GB RAM using qt4.8.6. Maximum size for me is 268,435,450

I test this in Windows7 32bit with 4GB RAM using qt4.8.4. Maximum size for me is 134,217,722

This error happend : 'std::bad_alloc'

#include <QCoreApplication>
#include <QDebug>

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    QList<bool> li;
    for(int i=0; ;i++)
    {
        li.append(true);
        if(i>268435449)
            qDebug()<<i;
    }
    return a.exec();
}

Output is :

268435450

terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc

Idle

Same exception after 268,435,453 on 64bit Ubuntu 4 GB RAM Qt 5.3.2 – Cufic

While it is useful, this does not answer the question what the workaround would be and why it is happening. Please use comments for additional information. – Homozygous