std::bad_alloc crash

[Urthas]

Hello,

I'm not sure whether this is a Qt issue or something deeper, which is why I am posting it here. Please move this topic if it is better placed elsewhere.

Just for fun and learning, I decided to look into prime number sieves. Knowing nothing about them, I settled on what is generally regarded as the simplest to implement. Here is my complete, naive code:


#include <QCoreApplication>
#include <QDebug>
#include <QtMath>

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

/**
* Seive of Eratosthenes
* see https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
*/

// initialize
const int n = INT16_MAX;
QList<bool> sieve;
for (int i = 0; i <= n; ++i)
sieve.append(true);

// compute
for (int i = 2; i <= qFloor(qSqrt(n)); ++i) {
if (sieve.at(i) == true) {
for (int j = i*i; j <= n; j += i)
sieve.replace(j, false);
}
}

// print!
QList<QString> primes;
for (int i = 2; i < sieve.count(); ++i)
if (sieve.at(i) == true)
primes.append(QString::number(i));
qDebug() << primes.join(", ");

return a.exec();
}

It works correctly. However, if I change the value of n to INT32_MAX, the program crashes with the following error:


libc++abi.dylib: terminating with uncaught exception of type std::bad_alloc

The problem appears to be in the initialization loop. For example, if I comment out the call to append and just let the loop run without a body, the program hangs. If I then change <=n to <n, it goes to completion. If I then uncomment the call to append, it crashes as before. Can anyone explain why this is?

Thank you!

Haha, I stopped and actually thought about just how big INT32_MAX is, and it's something like 4 billion. I guess I'm just filling up my computer's memory. Nothing to see here! ;)

[anda_skoa]

In any case QList is not the best container to use for the sieve.
Since you already know the number of entries beforehand, you could simply use a vector, e.g. QVector.



QVector<bool> sieve(n, true);


In this very specific case, with the value type being a simple bool, you could even use QBitArray


QBitArray sieve(, true);

which only needs one byte for 8 values.

Might even work with INT32_MAX then :)

Cheers,
_

[Urthas]

Thanks very much for your observations. The new, vector-based code looks like this:


// initialize
const int n = INT16_MAX;
QVector<bool> sieve(n+1, true);

You'll notice the 'n+1'. When I simply used n, I got an index-out-of-range fatal error while computing the sieve. 'n' is actually not a great variable name because it typically connotes number of elements, whereas in this algorithm it is actually a max value, matched by its index.

Finally, using a QBitArray yielded the same bad_alloc crash with INT32_MAX, alas! But, it was a good suggestion. :)