Memory increases because of deleting

[Nico]

Hello,

I have made a queue that keeps all the values in the order in which they were originally placed (like a deque) but does not accept any duplicates (like a set).
Now I noticed that if I use this queue I am leaking memory, but for the life of me I wouldn't know where it goes. Is there anybody that can tell me what I should change in order to regain the memory when I remove something out of my list?

This is the implementation of my queue:

#ifndef MYQUE_H
#define MYQUE_H

#include <mutex>                                // std::mutex, std::unique_lock
#include <deque>                                // std:: deque<T>
#include <set>                                  // std::set<T>

template<class T>
/** \brief A queue that preserves the order in which objects are added, but rejects duplicates */
class MyQue
{
    public:
        MyQue() {}
        virtual ~MyQue() {}

        /** \brief Adds an item to the back of the queue  */
        void push_back(T data)
        {
            std::unique_lock<std::mutex> locker(dataMutex);     // only 1 thread at a time can be allowed
            auto ret = duplicateCheck.insert(data);             // check if we can add the data to the set, because a set does not allow duplicate values
            if (ret.second==true) orderedQue.push_back(data);   // if the value is not a duplicate, add it to the queue
        }

        /** \brief Returns the first item in the queue and immediately removes it from the list, effectively reducing its size by 1.
         * \return T the first item from the queue
         */
        T front()
        {
            std::unique_lock<std::mutex> locker(dataMutex);     // only one thread at a time can be allowed
            T temp = orderedQue.front();                        // get the data that is first in line
            orderedQue.pop_front();                             // remove the data from the queue, so the component has to register again next time
            orderedQue.shrink_to_fit();                         // reduce the size of the queue to the minimum

            duplicateCheck.erase(temp);                         // make sure the data that was removed from the queue is no longer considered a duplicate entry if provided again
            return temp;                                        // return the data
        }

        /** \brief Function to obtain the current size of the queue
         * \return size_t representing the number of items currently in the queue
         */
        size_t size()
        {
            std::unique_lock<std::mutex> locker(dataMutex);     // only one thread at a time can be allowed
            return std::max( duplicateCheck.size(),orderedQue.size() );                           // return the size of the queue
        }

    protected:
    private:
        std::deque<T>               orderedQue;
        std::set<T>                 duplicateCheck;
        std::mutex                  dataMutex;
};
#endif // MYQUE_H 

And this is the program I used to check if I am regaining the memory (by looking at the system manager before I press enter to continue):

#include <iostream>
#include <random>       // The header for the generators.
#include <ctime>        // To seed the generator.

#include "MyQue.h"

int main()
{
    std::cout << "Going to test MyQue.\n";
    MyQue<int> testQue;

    std::cout << "Initial size: " << testQue.size() << "\n";
    std::cout << "Pushing 50000 integers into testQue.\n";
    for (int i=0; i<50000; i++) testQue.push_back(i);
    std::cout << "resulting size: " << testQue.size() << "\n";

    std::cout << "Adding 10 duplicates (that should be rejected).\n";
    const unsigned int seed = time(0);
    std::default_random_engine generator(seed);
    std::uniform_int_distribution<int> distribution(1,1000);
    for (int i=0; i<10; i++)
    {
        int number = distribution(generator);  // generates number in the range 1..1000. These will always be a duplicates and should not be added.
        std::cout << number << " ";
        testQue.push_back(number);
    }
    std::cout << "\nResulting size: " << testQue.size() << "\n";
    std::cout << "Pop-ing the front value 10000 times after you pressed enter.\n";
    system("pause");
    for (int i=0; i<10000; i++) std::cout << "Front was: " << testQue.front() << ", resulting size: " << testQue.size() << "\n";
    system("pause");
    return 0;
}

The size of my queue is decreasing as expected, but the consumed memory is increasing instead of decreasing. How can this be explained?

Thanks in advance, Nico

[tpb]

Your program doesn't have a memory leak. It's simply the case that the memory you "regain" is not actually given back to the operating system. Instead, it's just made available for further use by your program. It's generally pointless to "return" virtual memory to the OS.

[Ganado]

The consumed memory increases from line 29 to line 31, is what you're saying? If so, maybe the OS isn't immediately deallocating the old memory after calling shrink_to_fit.

I'm not sure, but 50000 ints isn't that much these days, the OS might be more inclined to reclaim the memory once you actually start allocating/deallocating more significant amounts. Just a theory though, I don't know in practice how Windows (or any OS) decides to handle its memory specifically.

[Nico]

Thank you for your replies. I could understand the size of the program remaining constant if the program does not actively release the memory immediately. But it in fact increases when I am removing the values from the queue, which I think is different from not releasing memory. Although it might be that the memory is "marked" as released by and this marking consumes the additional space.

I started checking this because I have another program where I use this same queue and that program actually crashes after a couple of days due to a lack of memory. This list is currently my main suspect for causing this. I agree that releasing the couple of kilobytes involved here might not be really relevant on modern computers, but if repeated often a couple of kilobytes can unfortunately suddenly become very relevant.

Kind regards, Nico

[tpb]

You need more tests, then.

Try it without the mutex. Any difference?

Put it in a loop and have it allocate, deallocate over and over between the pauses.

[Ganado]

To clarify, we're not saying small memory leaks aren't important. They definitely can be. We just thought there wasn't a memory leak.

I can't test threading right now, maybe I'll check it out later. By the way, what compiler are you using, and what options are you giving it?

[tpb]

I can't test threading right now

He seems to be saying that the example in the first post is eating memory, and it doesn't use multiple threads. That's why I asked what happens without the mutexes, just for more info in case they were what was consuming memory somehow.

[Peter87]

When I run your program on linux, using the GCC compiler, the memory usage stays the same according to the System Monitor. If I run the program through Massif it actually reports a decrease in memory usage, but that is to be expected because it reports how much heap memory is actually being used and not how much memory that has been set aside for the process to use. To me this seems to be pretty normal and nothing to worry about.

You say that the memory usage goes up when the queue size goes down. If it's just a little it could be normal but if it's a lot I would be more concerned. If you are using Visual Studio, you might want to try running the program in release mode and see if that makes a difference.

[Nico]

I compiled using GCC compiler from TDM-GCC compiler suite for windows version 5.1.0.
Subsequently I run the program on a Windows 7 computer.

To check if the effect I see is the result of my computer being reluctant to imediately release those small amounts of memory I have modified my program to add 500 000 values and after the enter key has been pressed remove 500 000 values.

After adding the values my program occupies 178 628kB of my working memory.
When I press the enter key, this increases tot 202 760 kB.
After that nothing happens for a very long time, then the consumed memory is slowly deceasing to 199 964kB and later to 181 252 kB. During this process it was continuously running one of the cores of my CPU at 100% of its capacity.
(After half an hour the program was reduced to 177 992 kB, after 35 minutes the program was reduced to 163 928 kB, proving that deleting values does indeed a cause a reduction in the consumed memory as expected, after 40 minutes it was down to 150 196 kB and then I ran out of time to monitor this process.)

It seems that there is more memory required to do the actual deleting (makes sense) and that this process takes a lot longer then I would have expected.
It also seems that I need to think of another way to do this, as i expect values to be added and removed from the queue approximately at the same rate and that will be a problem with the current difference in processing time found here.

Thanks for all your replies, they did make me understand the cause of my problem better.

[Peter87]

It seems that there is more memory required to do the actual deleting (makes sense) and that this process takes a lot longer then I would have expected.

Not sure how much it affects the memory usage but those repetitive calls to shrink_to_fit() probably slow things down quite a bit.

[Thomas1965]

shrink_to_fit() creates a temporary deque and then calls swap with it so a lot of extra allocations and deallocations. Is it really necessary?
VS 2017

if (some conditions met)
{
  deque _Tmp(_STD make_move_iterator(begin()), _STD make_move_iterator(end()));
  swap(_Tmp);
}

[JLBorges]

The libstdc++ (GNU) implementation of std::deque (the one being used) immediately deallocates an empty block that may be created by a pop_front or pop_back.

So, with the implementation in question, the call to shrink_to_fit is unnecessary.
(A call to shrink_to_fit triggers a copy and swap only when one block can be freed by relocating the elements; otherwise it is a no-op.)