multiset memory usage

[neil.johnston]

I have a cut down example program that uses multiset to order some
data. The data arrives from various sources and has a time stamp, data
with identical timestamps can arrive and due to fifo's and block sizes
data from one source with a later time stamp may arrive before data
from another source with and earlier time stamp.

Looking at the STL i thought multiset was just the job for this. The
idea was to set a window of x seconds and read out data older than
this from the multiset.

This works fine, except that the memory image just increases forever
and with data arriving without end this is not a good outcome.

I can't see where i'm going wrong, maybe multiset is not designed for
this job or i've gone blind to the obvious error.

Any pointers on what the problems is or alternative implementations
much appreciated.

cheers
neil

Here's the cut down code (sorry about the size of this post):

/*
* test of a multiset
* - problem is that it leaks like a waterfall
*/

#include <iostream>
#include <set>

// A class to hold data and an associated timestamp
// we are given a pointer to the data, we do not copy it on entry or
retrieval
class TimedStore {
public:
TimedStore(unsigned char **data, unsigned long long TS)
{ _data=*data; *data=0L; _TS=TS; };
~TimedStore() {}; // don't delete [] _data here as would accidently
destroy it on multiset erase()

void getData(unsigned char **data) const { *data=_data; return; };
unsigned long long getTS() const { return(_TS); };

bool operator < (const TimedStore &ref) const { return(this->_TS <
ref._TS); };

private:
unsigned long long _TS;
unsigned char *_data;
};

// for multiset compare as we store pointers to the TimeStore objects
struct classcomp {
bool operator() (const TimedStore *lhs, const TimedStore *rhs) const
{return *lhs < *rhs;}
};

int main ()
{
unsigned char *tt;
unsigned long long time=1000; // don't want -ve time
std::multiset<TimedStore *, classcomp> _ordered;

// put some data in, we would run this forever normaly
// data would be arriving from different places with different fifo
and block sizes
// hence data would not be in the correct time order
for(int t=0; t<1000000; t++)
{
// a random, generally incrementing, timestamp
int inc=rand()/(RAND_MAX/7);
int inc2=(rand()/(RAND_MAX/9));
time=time+(((inc>1)?1:-1)*inc2);

tt=new unsigned char[102]; // some test data
//std::cout << time << " " << std::hex << (unsigned long)tt <<
std::dec << std::endl;

TimedStore *tmp=new TimedStore(&tt, time);
_ordered.insert(tmp);
}

std::cout << "inserted - sleep(5), check memory footprint" <<
std::endl;
sleep(5);

// now lets get the ordered data out, we would normaly do this on
insertion
// with a window set to get the order correct over a time window
while(!_ordered.empty())
{
std::multiset<TimedStore *>::iterator old=_ordered.begin();
TimedStore *tmp=*old;
time=tmp->getTS();
tmp->getData(&tt);

_ordered.erase(old); // delete it from the multiset

//std::cout << time << " " << std::hex << (unsigned long)tt <<
std::dec << std::endl;
delete [] tt; // destroy the data
}

std::cout << "erased/deleted - sleep(5), check memory footprint" <<
std::endl;
sleep(5);
_ordered.clear();

std::cout << "cleared - sleep(5), check memory footprint" <<
std::endl;
sleep(5);

std::cout << "exit" << std::endl;
return 0;
}

 

[Naresh Rautela]

I have a cut down example program that uses multiset to order some
data. The data arrives from various sources and has a time stamp, data
with identical timestamps can arrive and due to fifo's and block sizes
data from one source with a later time stamp may arrive before data
from another source with and earlier time stamp.

Looking at the STL i thought multiset was just the job for this. The
idea was to set a window of x seconds and read out data older than
this from the multiset.

This works fine, except that the memory image just increases forever
and with data arriving without end this is not a good outcome.

I can't see where i'm going wrong, maybe multiset is not designed for
this job or i've gone blind to the obvious error.

Any pointers on what the problems is or alternative implementations
much appreciated.

cheers
neil

Here's the cut down code (sorry about the size of this post):

/*
* test of a multiset
* - problem is that it leaks like a waterfall
*/

#include <iostream>
#include <set>

// A class to hold data and an associated timestamp
// we are given a pointer to the data, we do not copy it on entry or
retrieval
class TimedStore {
public:
TimedStore(unsigned char **data, unsigned long long TS)
{ _data=*data; *data=0L; _TS=TS; };
~TimedStore() {}; // don't delete [] _data here as would accidently
destroy it on multiset erase()

void getData(unsigned char **data) const { *data=_data; return; };
unsigned long long getTS() const { return(_TS); };

bool operator < (const TimedStore &ref) const { return(this->_TS <
ref._TS); };

private:
unsigned long long _TS;
unsigned char *_data;

};

// for multiset compare as we store pointers to the TimeStore objects
struct classcomp {
bool operator() (const TimedStore *lhs, const TimedStore *rhs) const
{return *lhs < *rhs;}

};

int main ()
{
unsigned char *tt;
unsigned long long time=1000; // don't want -ve time
std::multiset<TimedStore *, classcomp> _ordered;

// put some data in, we would run this forever normaly
// data would be arriving from different places with different fifo
and block sizes
// hence data would not be in the correct time order
for(int t=0; t<1000000; t++)
{
// a random, generally incrementing, timestamp
int inc=rand()/(RAND_MAX/7);
int inc2=(rand()/(RAND_MAX/9));
time=time+(((inc>1)?1:-1)*inc2);

tt=new unsigned char[102]; // some test data
//std::cout << time << " " << std::hex << (unsigned long)tt <<
std::dec << std::endl;

TimedStore *tmp=new TimedStore(&tt, time);
_ordered.insert(tmp);
}

std::cout << "inserted - sleep(5), check memory footprint" <<
std::endl;
sleep(5);

// now lets get the ordered data out, we would normaly do this on
insertion
// with a window set to get the order correct over a time window
while(!_ordered.empty())
{
std::multiset<TimedStore *>::iterator old=_ordered.begin();
TimedStore *tmp=*old;
time=tmp->getTS();
tmp->getData(&tt);

_ordered.erase(old); // delete it from the multiset

//std::cout << time << " " << std::hex << (unsigned long)tt <<
std::dec << std::endl;
delete [] tt; // destroy the data
}

std::cout << "erased/deleted - sleep(5), check memory footprint" <<
std::endl;
sleep(5);
_ordered.clear();

std::cout << "cleared - sleep(5), check memory footprint" <<
std::endl;
sleep(5);

std::cout << "exit" << std::endl;
return 0;



}- Hide quoted text -

- Show quoted text -

Modify your destructor as follows
~TimedStore() {delete _data; _data=NULL;};

Modify your while loop under which you are freeing memory as follows
while(!_ordered.empty())
{
std::multiset<TimedStore *, classcomp>::iterator
old=_ordered.begin();
TimedStore *tmp=*old;
time=tmp->getTS();
tmp->getData(&tt);


delete *old;

_ordered.erase(old); // delete it from the multiset


//std::cout << time << " " << std::hex << (unsigned
long)tt << std::dec << std::endl;
//delete [] tt; // destroy the data
}

Also you need a assignment and a copy constructor. The code
TimedStore *tmp=*old; causes the _data data member to point to the
same memory location. After delete *old this memory location may
become invalid.

 

[John Harrison]

I have a cut down example program that uses multiset to order some
data. The data arrives from various sources and has a time stamp, data
with identical timestamps can arrive and due to fifo's and block sizes
data from one source with a later time stamp may arrive before data
from another source with and earlier time stamp.

Looking at the STL i thought multiset was just the job for this. The
idea was to set a window of x seconds and read out data older than
this from the multiset.

This works fine, except that the memory image just increases forever
and with data arriving without end this is not a good outcome.

I can't see where i'm going wrong, maybe multiset is not designed for
this job or i've gone blind to the obvious error.

The obvious error is profilate pointer usage.

Any pointers on what the problems is or alternative implementations
much appreciated.

Rework TimedStore so that it can copy without memory leak, and copy
efficiently. Probably this means some kind of reference counting
implementation. Consider using shared_ptr from www.boost.org, it will
make you life so much easier.

Only when you have made TimedStore a self contained class should you
consider using it in a multimap.

~TimedStore() {}; // don't delete [] _data here as would accidently
destroy it on multiset erase()

This comment gives the game away.

 

[neil.johnston]

Thanks for the reply Naresh

The idea is not to delete the data in the TimedStore destructor as i
need to use it elsewhere, which is why i use TimedStore *tmp=*old as
i need to get hold of the original data ptr to use it. I don't care
that i'm about to delete the TimedStore that held it.

I was missing the delete *old;, a hold over from when i didn't store
the
ptr to TimedStore but the actual object.

Still leaks though even putting in the above changes

I may rework as John says just to see if it helps, but i don't think i
can afford all the copying of data.

neil

 

[neil.johnston]

Thanks John

I agree about the ptr's and will probably rework so it doesn't use
any
then work back to using them for performance reasons, though i may
take the hit.

Of course i'm assuming that it's not an OS problem, ie my memory foot
print does not decrease as the OS is guessing that i may ask for the
memory again.


neil

 

[neil.johnston]

Thanks John

I agree about the ptr's, probably rework it without then add some back
in
as i don't think i can take the performance hit.

Maybe its the OS, i;'m assuming when i start deleting things my
memory
footprint should decrease and the clear() should reduce it to almost
nothing.
But maybe the OS is leaving the memory with me in case i need it
again.

Have to make my cutdown prog do the window as well

neil

 

[neil.johnston]

It works


TimedStore *tmp=new TimedStore(&tt, time);
_ordered.insert(tmp);

std::cout << _ordered.size() << std::endl;

// now lets get things out
std::multiset<TimedStore *, classcomp>::iterator
old=_ordered.begin(); // oldest item
tmp=*old;
unsigned long long timeOld=tmp->getTS();
int window=100;
if( timeOld < (time-window) )
{
delete *old; // ordered.erase() won't call a ptrs destructor
_ordered.erase(old); // delete it from the multiset
tmp->getData(&tt);
//std::cout << time << " " << std::hex << (unsigned long)tt <<
std::dec << std::endl;
delete [] tt; // destroy the data
}

 

[neil.johnston]

oops finger trouble on posting

Problem was not doing the delete *old; and not testing with the window
in. The
memory grows to something corresponding to the size of the multiset
and no further.

Thanks for the help, many eyes make light work

neil

 

[neil.johnston]

In case anybody checks this again, i should use tmp before i delete
old !

if( timeOld < (time-window) )
{
tmp->getData(&tt);
delete [] tt; // destroy the data

delete *old; // ordered.erase() won't call a ptrs destructor
_ordered.erase(old); // delete it from the multiset
}

 

[Naresh Rautela]

In case anybody checks this again, i should use tmp before i delete
old !

if( timeOld < (time-window) )
{
tmp->getData(&tt);
delete [] tt; // destroy the data

delete *old; // ordered.erase() won't call a ptrs destructor
_ordered.erase(old); // delete it from the multiset
}

Thats the point I was trying to make. Calling erase would not
destruct the pointers stored in the multiset.