Tech Off Thread

11 posts

Forum Read Only

This forum has been made read only by the site admins. No new threads or comments can be added.

I'm leaking memory, help!

Back to Forum: Tech Off
  • User profile image
    Shining Arcanine

    I'm writing a prime number finder to learn C#. Last night and early today, I wrote a method which used the Sieve of Eratosthenes algorithm to aid a Pollard P-1 factorization method I'm working on:

    Shining Arcanine wrote:
    private static UInt32[] Eratosthenes(UInt32 maxValue, BackgroundWorker worker, DoWorkEventArgs e)
    {
        UInt32 num = maxValue - 1, value = maxValue;
        UInt32[] primeList = new UInt32[num];

        //Fill the array with numbers
        while (num > 0)
        {
            num--;

            primeList[num] = value;

            value--;
        }

        UInt32 index = 0;

        num = maxValue - 1;

        UInt32 count = 0, lastCount = 0;

        //Remove all composites
        while (index < num)
        {
            //If backgroundworker is canceled, exit
            if (worker.CancellationPending)
            {
                e.Cancel = true;
                return primeList;
            }

            //If the number doesn't exist, its composite; skip it
            if (primeList[index] > 0)
            {
                for (UInt32 i = index + primeList[index]; i < num; i += primeList[index])
                {
                    primeList[i] = 0;
                }

                //Check last known prime to see if we can skip the nestled loop
                if ((primeList[index] * primeList[index]) > maxValue)
                {
                    //If so, count the remaining actual numbers for
                    //the finalList[] and break the loop
                    while (index < num)
                    {
                        if (primeList[index] > 0)
                        {
                            count++;
                        }

                        index++;
                    }

                    break;
                }

                //Count the number of primes for the finalList[]
                count++;
            }

            index++;
        }

        UInt32[] finalList = new UInt32[count];

        //Condense list
        for (UInt32 i = 0; i < num; i++)
        {
            if (primeList[i] > 0)
            {
                finalList[lastCount] = primeList[i];
                lastCount++;
            }
        }

        return finalList;
    }


    In my testing, I discovered that it could leak obscene amounts of memory. I know absolutely nothing about memory management although I do know that the main culprit is primeList[] as it uses 32 * (10 ^ maxValue - 1) bits of memory. When it runs with a maxValue of 8, my program utilizes an additional 381MB of memory. When it is done, my program is still utilizing an additional 381MB of memory.

    Does anyone know how to fix this?

  • User profile image
    W3bbo

    But .NET's intrinsic GC means that all C# apps are inherently immune from memory leaks.

    You're not using any classes that implement IDisposable, are you?

  • User profile image
    Shining Arcanine

    No, I'm not using IDisposable. The memory gets reclaimed by the system when my application closes so the GC is doing its job. The problem is that when my Eratosthenes method terminates, I expect its memory usage to also terminate.

  • User profile image
    blowdart

    Shining Arcanine wrote:
    The problem is that when my Eratosthenes method terminates, I expect its memory usage to also terminate.


    Why? The CLR Garbage collection is not immediate, it will happen when it happens; for example calling the Dispose method on an object which implements IDisposable does not send the garbage collector off to cull that object from memory.

    If you want to override the wait, then

    using System.GC;

    ...

    GC.Collect();

    It is more complicated than that; if you care, read

  • User profile image
    footballism

       Using System.Collections.BitArray rather than traditional Array to hold up the primes being found can tremendously reduce the memory usage.
    the following code  is the Sieve class implementation I copy from a book:
    public class Sieve
    {
        public static Int32[] GetPrimes(Int32 maxValue)
        {
             // Sets all the bits to true.
             BitArray flags = new BitArray(maxValue + 1, true); ;
             for (Int32 i = 2; i <= (Int32) Math.Sqrt(maxValue); i ++)
             {
                 if (flags[i])
                 {
                    for (Int32 j = i; j * i <= maxValue; j ++)
                    {
                       flags[j * i] = false;
                    }
                 }
             }
             
              // Count the number of primes being found.
              Int32 count = 0;
              for (Int32 i = 2; i <=maxValue; i ++)
              {
                    if (flags[i]) count ++;
              }

              // Create an array to store the primes being found.
              Int32 primeList = new Int32[count];
              for (Int32 i = 2, j = 0; j < count; j ++)
              {
                  if (flags[i]) primes[j++] = i;
              }

              return primes;
        }
    }

    This implementation is much simpler, and much efficient.

    Sheva

  • User profile image
    Shining Arcanine

    blowdart wrote:
    Shining Arcanine wrote:The problem is that when my Eratosthenes method terminates, I expect its memory usage to also terminate.


    Why? The CLR Garbage collection is not immediate, it will happen when it happens; for example calling the Dispose method on an object which implements IDisposable does not send the garbage collector off to cull that object from memory.

    If you want to override the wait, then

    using System.GC;

    ...

    GC.Collect();

    It is more complicated than that; if you care, read


    Many people (myself included) complain about Firefox when they see it using over 100MB of memory when it shouldn't need that much. If that isn't acceptable for Firefox, it isn't acceptable for any application.

    Using GC.Collect() at the right places fixed my memory problem. Thankyou.

  • User profile image
    footballism

    Shining Arcanine wrote:

    Many people (myself included) complain about Firefox when they see it using over 100MB of memory when it shouldn't need that much. If that isn't acceptable for Firefox, it isn't acceptable for any application.

    Using GC.Collect() at the right places fixed my memory problem. Thankyou.

    Gotcha, at most circumstance, you should avoid calling the GC.Collect() method, it's best just to let the GC do its own garbage collecting logic. actually you can find more performant solution to your problem rather than complaining the behaviour of CLR.

    Sheva

    Edit: Blowdart, you are actually openning the Pandora's box to the outside world:p

  • User profile image
    Shining Arcanine

    footballism, are you sure that you typed the example correctly? Putting it into Microsoft Visual C# 2005 Express gives me three errors towards the end.


    Also, I rewrote my method to use bitArray() and a few speed tweaks:


    Shining Arcanine wrote:
    private static int[] Eratosthenes(int maxValue, BackgroundWorker worker, DoWorkEventArgs e)
    {
        int index = 2, count = 0, square = 0;

        //Create array of numbers, starting from zero, each
        //represented by a bit
        BitArray primeList = new BitArray(maxValue + 1, true);

        //Set bits of composites to 0 and count primes
        while (square <= maxValue)
        {

            if (primeList.Get(index))
            {
                for (int i = index << 1; i < maxValue; i += index)
                {
                    //If backgroundworker is canceled, exit
                    if (worker.CancellationPending)
                    {
                        e.Cancel = true;
                        return new int[0];
                    }

                    primeList.Set(i, false);
                }

                count++;
                square = index * index;
            }

            index++;
        }

        //Finish Prime Count
        while (index < maxValue)
        {
            if (primeList.Get(index))
            {
                count++;
            }

            index++;

        }

        int[] finalList = new int[count];

        index = 2;
        count = 0;

        //Compile finalList
        while (index < maxValue)
        {
            if (primeList.Get(index))
            {
                finalList[count] = index;
                count++;
            }

            index++;
        }

        //Free Memory
        GC.Collect();

        return finalList;
    }


    The good news is that it utilizes memory approximately 32 times more efficiently than the last one. The bad news is that it is slightly slower than the last one. Does anyone know if this can be further optimized or is it as optimal as it is going to get?

  • User profile image
    footballism

    Shining Arcanine wrote:

    footballism, are you sure that you typed the example correctly? Putting it into Microsoft Visual C# 2005 Express gives me three errors towards the end.

    There are just some minor errors in the code I posted previously, actually I didn't test it beforing posting.


    Shining Arcanine wrote:

    The good news is that it utilizes memory approximately 32 times more efficiently than the last one. The bad news is that it is slightly slower than the last one. Does anyone know if this can be further optimized or is it as optimal as it is going to get?

    I think the slowness you've experienced with your  implementation is probably because the implementation of BitArray is quite tricky, and comparatively speaking, accessing BitArray is not as efficient as accessing traditional array, another reason I can  think of is because you call the GC.Collect() method in your implementation, the GC.Collect() method will force the garbage collector to collect generation 0 by default, as we all know, cleaning up memory does take times. as I've said years ago in the thread, it's very unusual to call GC.Collect() method, so just use it carefully.

    The following code can give you some ideas of how the BitArray is implemented:
    public class BitArray
        {
            private Byte[] _Bits;
            private Int32 _NumberOfBits;

            public BitArray(Int32 numberOfBits)
            {
                if (numberOfBits <= 0 )
                    throw new ArgumentOutOfRangeException("number of bits must be greater than zero!");
                _NumberOfBits = numberOfBits;
                _Bits = new Byte[(numberOfBits + 7) / 8];
            }

            public Int32 NumberOfBits
            {
                get
                {
                    return _NumberOfBits;
                }
            }

            [System.Runtime.CompilerServices.IndexerName("Bits")]
            public Boolean this[Int32 bitPos]
            {
                get
                {
                    if (bitPos < 0 || bitPos >= _NumberOfBits)
                        throw new IndexOutOfRangeException();
                    return ((_Bits[bitPos / 8] >> (7 - bitPos %Eye Rolling & 1) != 0);
                }

                set
                {
                    if (bitPos < 0 || bitPos >= _NumberOfBits)
                        throw new IndexOutOfRangeException();
                    if (value)
                    {
                        _Bits[bitPos / 8] = (Byte) (_Bits[bitPos / 8] | 1 << (7 - bitPos %Eye Rolling);
                    }
                    else
                    {
                        _Bits[bitPos / 8] = (Byte) (_Bits[bitPos / 8] & ~ (1 << (7 - bitPos %Eye Rolling));
                    }
                }
            }
        }

    Sheva

  • User profile image
    Sven Groot

    Shining Arcanine wrote:
    The memory gets reclaimed by the system when my application closes so the GC is doing its job.

    Just as an FYI, that's not any indication of the GC doing anything. All resources used by an application (memory, handles, etc) will get reclaimed by the system when a process exits. This is something all OSs I know of do, it has nothing to do with the language or runtime environment you are using, it's always true. Memory leaks are only memory leaks as long as a process is running.

    As footballism indicates, be very careful with calling GC.Collect. Collection is an expensive operation, and you have to be very smart if you want to outsmart the GC's default behaviour. Yes, you may get more (immediately) free memory, but there may be a significant performance cost. It might very well be better to let the GC hold on to those pages until they are actually needed, even if that does mean a high number in task manager.

    Btw, you can use the performance counters included with .Net to see what the GC is doing while your app is running.

  • User profile image
    amotif

    Shining Arcanine wrote:

    The good news is that it utilizes memory approximately 32 times more efficiently than the last one.


    I am skeptical of your new-found memory efficiency. Your app wasn't GC'ing before because it was using available memory. As memory pressure increases it would start GC'ing as necessary.

    Shining Arcanine wrote:

    The bad news is that it is slightly slower than the last one. Does anyone know if this can be further optimized or is it as optimal as it is going to get?


    Don't call GC.Collect(). Seriously. Garbage collection takes time, and it's time your app previously didn't take because there was no need to collect. Chances are slim that your application logic will know when a garbage collection is needed better than the GC does.

Conversation locked

This conversation has been locked by the site admins. No new comments can be made.