October 29, 2011

andrewjlouth andrewjlouth
Lab Rat
4 posts

Should QVector be able to hold one billion items?

 

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

  1. QVector<int> vec;
  2. for(int i = 0; i < 1000000000; ++i)
  3. {
  4.     vec.push_back(i);
  5. }

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

10 replies

October 29, 2011

Lukas Geyer Lukas Geyer
Lab Rat
2074 posts

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.

October 29, 2011

andrewjlouth andrewjlouth
Lab Rat
4 posts

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?

October 29, 2011

rcari rcari
Lab Rat
166 posts

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

Do you get the exception on

  1. new int[1000000000];

?

October 29, 2011

andrewjlouth andrewjlouth
Lab Rat
4 posts

There is no exception using:

  1. new int[1000000000]

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

October 29, 2011

Andre Andre
Robot Herder
6399 posts

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

  1. QVector<int> vec(1000000000);
  2. for(int i = 0; i < 1000000000; ++i)
  3. {
  4.     vec.push_back(i);
  5. }

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.

October 29, 2011

cookiemonster cookiemonster
Lab Rat
1 posts

I think moderator meant as follows?

  1. QVector<int> vec(1000000000);
  2. for(int i = 0; i < 1000000000; ++i)
  3. {
  4.     vec[i] = i;
  5. }

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

  1. QVector<int> vec;
  2. vec.reserve(1000000000);
  3. for(int i = 0; i < 1000000000; ++i)
  4. {
  5.     vec.push_back(i);
  6. }

October 29, 2011

andrewjlouth andrewjlouth
Lab Rat
4 posts

Thanks for the suggestion however it still throws an exception.

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

  1. QVector<int> vec;
  2. vec.reserve(1000000000);

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

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

  1. 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:

  1. 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.

October 29, 2011

peppe peppe
Ant Farmer
1028 posts

andrewjlouth wrote:
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?

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

 Signature 

Software Engineer
KDAB (UK) Ltd., a KDAB Group company

October 29, 2011

marcoB marcoB
Lab Rat
167 posts

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

vec.reserve(1000000000L);

October 31, 2011

Andre Andre
Robot Herder
6399 posts

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

vec.reserve(1000000000L);

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]

 
  ‹‹ New to Qt, question about code converstion      Is this a way of achieve "internal class"? ››

You must log in to post a reply. Not a member yet? Register here!