Results 1 to 3 of 3

Thread: std::bad_alloc crash

  1. #1
    Join Date
    May 2009
    Location
    Canada
    Posts
    163
    Thanks
    7
    Thanked 20 Times in 20 Posts
    Qt products
    Qt4 Qt5
    Platforms
    MacOS X Windows Android

    Default std::bad_alloc crash

    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:

    Qt Code:
    1. #include <QCoreApplication>
    2. #include <QDebug>
    3. #include <QtMath>
    4.  
    5. int main(int argc, char *argv[])
    6. {
    7. QCoreApplication a(argc, argv);
    8.  
    9. /**
    10.   * Seive of Eratosthenes
    11.   * see https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    12.   */
    13.  
    14. // initialize
    15. const int n = INT16_MAX;
    16. QList<bool> sieve;
    17. for (int i = 0; i <= n; ++i)
    18. sieve.append(true);
    19.  
    20. // compute
    21. for (int i = 2; i <= qFloor(qSqrt(n)); ++i) {
    22. if (sieve.at(i) == true) {
    23. for (int j = i*i; j <= n; j += i)
    24. sieve.replace(j, false);
    25. }
    26. }
    27.  
    28. // print!
    29. QList<QString> primes;
    30. for (int i = 2; i < sieve.count(); ++i)
    31. if (sieve.at(i) == true)
    32. primes.append(QString::number(i));
    33. qDebug() << primes.join(", ");
    34.  
    35. return a.exec();
    36. }
    To copy to clipboard, switch view to plain text mode 

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

    Qt Code:
    1. libc++abi.dylib: terminating with uncaught exception of type std::bad_alloc
    To copy to clipboard, switch view to plain text mode 

    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!
    Last edited by Urthas; 3rd December 2016 at 00:31.

  2. #2
    Join Date
    Jan 2006
    Location
    Graz, Austria
    Posts
    8,416
    Thanks
    37
    Thanked 1,544 Times in 1,494 Posts
    Qt products
    Qt3 Qt4 Qt5
    Platforms
    Unix/X11 Windows

    Default Re: std::bad_alloc crash

    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.

    Qt Code:
    1. QVector<bool> sieve(n, true);
    To copy to clipboard, switch view to plain text mode 

    In this very specific case, with the value type being a simple bool, you could even use QBitArray
    Qt Code:
    1. QBitArray sieve(, true);
    To copy to clipboard, switch view to plain text mode 
    which only needs one byte for 8 values.

    Might even work with INT32_MAX then

    Cheers,
    _

  3. The following user says thank you to anda_skoa for this useful post:

    Urthas (5th December 2016)

  4. #3
    Join Date
    May 2009
    Location
    Canada
    Posts
    163
    Thanks
    7
    Thanked 20 Times in 20 Posts
    Qt products
    Qt4 Qt5
    Platforms
    MacOS X Windows Android

    Default Re: std::bad_alloc crash

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

    Qt Code:
    1. // initialize
    2. const int n = INT16_MAX;
    3. QVector<bool> sieve(n+1, true);
    To copy to clipboard, switch view to plain text mode 

    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.

Similar Threads

  1. Replies: 0
    Last Post: 3rd November 2015, 18:58
  2. qml crash
    By waiter in forum Qt Quick
    Replies: 0
    Last Post: 11th July 2013, 03:43
  3. QtConcurrent std::bad_alloc
    By baray98 in forum Qt Programming
    Replies: 1
    Last Post: 11th April 2013, 07:23
  4. Crash gracefully? No crash!
    By lni in forum Qt Programming
    Replies: 0
    Last Post: 7th July 2010, 04:59
  5. QFile::open throws std::bad_alloc for no obvious reason
    By nateriver in forum Qt Programming
    Replies: 3
    Last Post: 29th December 2009, 07:10

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Digia, Qt and their respective logos are trademarks of Digia Plc in Finland and/or other countries worldwide.