C++ New/Delete Error?

Question

I'm currently implementing a prime number sieve in C++ and I designed the code such that I should be able to control the size of the sieve (via an integer literal in the main function), but I am getting some odd errors all throughout. I haven't used C++ in a few years, but I remember using new and delete operators to manage heap memory.

My problem is sort of as follows...

The program works for some sieve sizes, but not others, and the effect is not strictly linear. For example, if I make the sieve of size 10,000, the program runs fine, but if I make it of size 1,000, the program crashes with a rather cryptic (for my amount of experience) message that always leads me to pages about C malloc assertion errors (via google). Additionally, the program works fine for 10,000 with delete statements peppered in, BUT will crash if I run in through valgrind with another useless (to me) message. As a result, I can't even debug the damn thing on my own DX

Any words of wisdom?

In particular, why would the program crash from a smaller input? In theory, this would be less likely to cause heap errors, would it not? Furthermore, why would valgrind be unable to run the program while it can go fine on its own? I suspect that (again) this has something to do with faulty or ugly use of the new/delete operators, but I am not totally certain. The part (about valgrind) that is particularly baffling to me is that it mentions in the error that I use the new operator on an unsigned long, which -as far as I can tell -is not what I do (at least not specifically). I assume this is some compiler related detail which I am not familiar with, but again I am not totally certain.

Code (with delete statement; works with size 10,000, but not through valgrind):

using namespace std;

#include <iostream>
#include <cstdlib>
#include <map>
#include <string>

long count_primes(bool* sieve,int size)
{
    long count = 0;
    for (int a=0;a<size;a++)
    {
        if (sieve[a]) 
        {
            count++;
        }
    }
    return count;
}

int next_prime(bool* primes_so_far,int current_prime,int size)
{
    for (int a=current_prime+1;a<size;a++)
    {
        if (primes_so_far[a]) return a;
    }
    return -2;
}

int prime_number_sieve(int* primes,int size)
{
    if (size<4) return -2;

    bool* sieve = new bool[size];

    for (int a=0;a<size;a++)
    sieve[a] = true;

    sieve[0] = false;
    sieve[1] = false;

    int a=2;
    do
    {
        int b = a;
        if (b*a < size) sieve[b*a] = false;
        do
        {
            b++;
            sieve[b*a] = false;
        } while (b*a < size);
        a = next_prime(sieve,a,size);
    } while (a*a < size);

    long prime_list_size = (long) count_primes(sieve,size);
    int* prime_list = new int[prime_list_size];

    for (int b=0,c=0;b<size;b++)
    {
        if (sieve[b]) prime_list[c++] = b;
    }   

    srand(time(NULL));
    int rand_int1 = rand();
    int rand_int2 = rand();
    long rand_num1 = (((long) rand_int1) * prime_list_size)/RAND_MAX;
    long rand_num2 = (((long) rand_int2) * prime_list_size)/RAND_MAX;

    primes[0] = prime_list[rand_num1];
    primes[1] = prime_list[rand_num2];

    delete[] sieve;
    delete[] prime_list;

    return 0;
}

int main()
{
    int* prime = new int[2];

    prime_number_sieve(prime,10000);

    cout << "\n";
    cout << prime[0];
    cout << "\n";
    cout << prime[1];
    cout << "\n";

    return 0;
}

valgrind error for above:

==23738== Invalid write of size 1
==23738==    at 0x400A4B: prime_number_sieve(int*, int) (in /home/botch/Downloads/unsorted/bre_final/a.out)
==23738==    by 0x400C31: main (in /home/botch/Downloads/unsorted/bre_final/a.out)
==23738==  Address 0x5ab83e0 is 0 bytes after a block of size 10,000 alloc'd
==23738==    at 0x4C2E80F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==23738==    by 0x4009CD: prime_number_sieve(int*, int) (in /home/botch/Downloads/unsorted/bre_final/a.out)
==23738==    by 0x400C31: main (in /home/botch/Downloads/unsorted/bre_final/a.out)
==23738== 

valgrind: m_mallocfree.c:303 (get_bszB_as_is): Assertion 'bszB_lo == bszB_hi' failed.
valgrind: Heap block lo/hi size mismatch: lo = 4063233, hi = 0.
This is probably caused by your program erroneously writing past the
end of a heap block and corrupting heap metadata.  If you fix any
invalid writes reported by Memcheck, this assertion failure will
probably go away.  Please try that before reporting this as a bug.

Error for changing size to 1,000:

a.out: malloc.c:2392: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed.
Aborted (core dumped)

EDIT:

I'm super grateful for all the (actual) help! Thanks to the answers below, the program will now run for most inputs (not too large, of course) but I am still getting the Valgrind error. I don't really mind that much, but I am curious to understand what is happening. I tried the suggestion below to change my selection mechanism of the random prime to (((long) rand_int1) % prime_list_size); rather than (((long) rand_int1) * prime_list_size)/RAND_MAX, but I had no noticeable results on the Valgrind side of things. I still cannot tell exactly where the invalid heap write is coming from. I will modify the code to see if it is my deletions that are causing and will report back.

Answer 1

The loop

 do
    {
        b++;
        sieve[b*a] = false;
    } while (b*a < size);

does the assignment to sieve[b*a] BEFORE checking if b*a < size. This allows assignment of an element past the end of the array. That is undefined behaviour on the last iteration of this loop.

You would be better off using std::vector<bool> [noting it has some limitations that other vectors don't have] or std::bitset, rather than messing around manually with operators new and delete. Bear in mind it is still necessary to ensure your code doesn't fall off the end of standard containers.

Answer 2

I could see two problems in your code.

The first one is here:

   do
   {
       b++;
       sieve[b*a] = false;
   } while (b*a < size);

This cannot prevent writing beyond the limit size, because the checking happens after the assignment `sieve[b*a] = false;

   while (b*a < size)
   {
       sieve[b*a] = false;
       b++;
   }

The other problem I see is here:

long rand_num1 = (((long) rand_int1) * prime_list_size)/RAND_MAX;

long rand_num2 = (((long) rand_int2) * prime_list_size)/RAND_MAX;

The term in the multiplication could lead to overflow. I guess you want to get a random index less than size? You could simply do it this way:

long rand_num1 = (((long) rand_int1) % prime_list_size);
long rand_num2 = (((long) rand_int2) % prime_list_size);

Sure this will not yield a perfect uniform distribution, but it will work. For a better distribution take a look to the number random generators of the std library, and its vector as well, which is a very good tool for what you are doing.