Should QVector be able to hold one billion items?

andrewjlouth

Paste and run the following code in a debug x64 build:

@QVector<int> vec;
for(int i = 0; i < 1000000000; ++i)
{
vec.push_back(i);
}@

Should this work ok?
It seems to throw a bad_alloc.

lgeyer

Well, besides the fact that this is one of this super-theoretical examples, yes - it is possible. But do the math on yourself: (probably) 8 bytes per int multiplied by one billion plus overhead for memory allocation. Now compare this number to your memory available.

andrewjlouth

I have 48GB of RAM.
8 bytes multiplied by 1 billion is only 8GB of RAM required.

Does Qt use 'int' internally to pass the size of new memory allocations for growing a QVector?

rcari

The int is 4 bytes on x86_64 so it's rather 4GB of RAM.

Do you get the exception on
@
new int[1000000000];
@
?

andrewjlouth

There is no exception using:

@new int[1000000000]@

Also, there is no exception if I use std::vector and not QVector.

andre

Do you allocate the vector like you show in the example? Could you try this:
@

QVector<int> vec(1000000000);
for(int i = 0; i < 1000000000; ++i)
{
vec.push_back(i);
}

@
Telling the vector up front how bit it must be, will save you an insane amount of shifting the data around...

However, I think I would not use the Qt container classes for such data blobs. This is the point where the copy-on-write of the Qt containers becomes a burden rather than a benefit.

cookiemonster

I think moderator meant as follows?

@QVector<int> vec(1000000000);
for(int i = 0; i < 1000000000; ++i)
{
vec[i] = i;
}@

Or in case the vector size is unknown up-front:

@QVector<int> vec;
vec.reserve(1000000000);
for(int i = 0; i < 1000000000; ++i)
{
vec.push_back(i);
}@

andrewjlouth

Thanks for the suggestion however it still throws an exception.

It will even throw an exception just doing a reserve as follows:

@QVector<int> vec;
vec.reserve(1000000000);@

I have investigated the problem and it seems to be as follows:

QVector<T>::malloc(int aalloc) is called by vec.reserve(), where aalloc is 1 billion.
In QVector<T>::malloc we call:

@QVectorData::allocate(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData());@

The first argument 'size' is:
4 + (1000000000 - 1) * 4 = 4000000000 which is greater than the positive range of a signed int.

Looking at the declaration of QVectorData::allocate we see that the first argument is an int:

@static QVectorData *allocate(int size, int alignment);@

So it looks like it has an overflow error.

Note: even 550 million messages throws the exception, but below this the allocate passes, presumably because the size is less than the positive range of an int.

dangelog

[quote author="andrewjlouth" date="1319880749"]I have 48GB of RAM.
8 bytes multiplied by 1 billion is only 8GB of RAM required.

Does Qt use 'int' internally to pass the size of new memory allocations for growing a QVector?
[/quote]

Yes. And asking the OS for a contiguous chunk of 8GB isn't something I would get rid off with an "only".

deimos

this has nothing to do with int and long ?
can you try with:

bq. vec.reserve(1000000000L);

andre

[quote author="deimos" date="1319910499"]this has nothing to do with int and long ?
can you try with:

bq. vec.reserve(1000000000L);[/quote]

Actually, no. QVector (and all other container classes) only work with integers (int, not long or long long). So, I guess it is just outside of the Qt containers specs to try to strore that many items in one. I would recommend using a different container class for that, from outside of Qt.

[edit: answer put outside quote, Eddy]