std::vector erase is not freeing mem?

[Sims]

Hi,

I suspect it is an OS related question but I am not sure what the
standard say regarding freeing memory when you 'erase' a value.

lets say that I have something like...
//
//
//
struct int_array{
int_array(){
a = b = 0;
}
int a, b;
};

typedef std::vector< int_array, std::allocator< int_array >> v_int_array;

//
// I then read millions of numbers from a file.
//
I then do some operations, (with the numbers).
And, (depending on the operation I did with those numbers), add them to
some other array.
To make sure the numbers never get used twice I 'erase' them from the
'master' array.

but the memory never seem to be freed.

you might think it is not a problem but all those numbers are taking a
large chunk of memory and when I copy them to their corresponding array
I now have 2 massive arrays.

So how can I erase a number?

v_int_array *some_num = get_values();

// use a number to do some calculations...
some_num->erase( some_num->begin() + nValToErase );

// but the memory is not freed...

Many thanks

Simon

 

[Gianni Mariani]

......
I suspect it is an OS related question but I am not sure what the
standard say regarding freeing memory when you 'erase' a value.
......
v_int_array *some_num = get_values();

// use a number to do some calculations...
some_num->erase( some_num->begin() + nValToErase );

// but the memory is not freed...

How are you detecting wether it's free or not ?

 

[Sims]

How are you detecting wether it's free or not ?

Well I am using XP pro, so using the task manager I can see the memory
been used.

I assumed that I was not deleting something so I did a little test.

read all the test values...(around 90mb of memory).
And then 'erased' half of it. But the system was still showing that 90mb
was been used.

the problem is that I first read 90mb and then copy the data to the
'correct' array. By doing that I now have 180mb of memory usage.
So I need to erase it from the 'master' array so that I never use more
than 90mb of memory.

My final project will read 512mb of data.

Simon

 

[Nicolas Pavlidis]

Hi,

I suspect it is an OS related question but I am not sure what the
standard say regarding freeing memory when you 'erase' a value.

None of the standard containers gets smaller if you erease an
element. You have to swap it with themselves:

///pseudo code for std::vector
my_vect.swap(my_vect);

The reason for this is, I think, that the time spent and the memory used
for making the container smaller is too high.

Kind regrads,
Nicolas

 

[John Harrison]

Hi,

I suspect it is an OS related question but I am not sure what the standard
say regarding freeing memory when you 'erase' a value.

lets say that I have something like...
//
//
//
struct int_array{
int_array(){
a = b = 0;
}
int a, b;
};

int_array is a funny name for a structure which is a pair of numbers.

typedef std::vector< int_array, std::allocator< int_array >> v_int_array;

typedef std::vector< int_array> v_int_array;

std::allocator<int_array> is unnecessary here, and >> without an intervening
space is illegal.

//
// I then read millions of numbers from a file.
//
I then do some operations, (with the numbers).
And, (depending on the operation I did with those numbers), add them to
some other array.
To make sure the numbers never get used twice I 'erase' them from the
'master' array.

but the memory never seem to be freed.

you might think it is not a problem but all those numbers are taking a
large chunk of memory and when I copy them to their corresponding array I
now have 2 massive arrays.

So how can I erase a number?

v_int_array *some_num = get_values();

// use a number to do some calculations...
some_num->erase( some_num->begin() + nValToErase );

// but the memory is not freed...

Many thanks

Simon

You are erasing the numbers correctly, but you are mistaken if you think
that erasing the number from a vector has something to do with freeing
memory. All erasing a number does is remove it from the vector, it doesn't
necessarily mean that any memory gets freed. The only time a vectors memory
is guaranteed to be freed is when the destructor for the vector is called.

There are two issues here. First the amount of memory a vector is holding is
determined by its capacity. Try this

cout << "before " << some_num->capacity() << ' ' << some_num->size() <<
'\n';
some_num->erase( some_num->begin() + nValToErase );

cout << "after" << some_num->capacity() << ' ' << some_num->size() << '\n';

I wouldn't be surprised if the capacity of the vector stays the same, even
though the size has changed. Unfortunately the C++ standard provides no
guaranteed method of reducing the capacity of a vector.

Secondly even if you do find that the capacity of the vector is reduced
there is no guarantee that memory is returned to the 'system'. It will be
useable again by your program but maybe not by other programs. So the way
you are measuring the free memory is crucial here.

If you give precise details of what you are trying to do maybe I could see a
more 'memory friendly' way of doing it.

john

 

[Gianni Mariani]

Well I am using XP pro, so using the task manager I can see the memory
been used.

I assumed that I was not deleting something so I did a little test.

read all the test values...(around 90mb of memory).
And then 'erased' half of it. But the system was still showing that 90mb
was been used.

the problem is that I first read 90mb and then copy the data to the
'correct' array. By doing that I now have 180mb of memory usage.
So I need to erase it from the 'master' array so that I never use more
than 90mb of memory.

My final project will read 512mb of data.

There are very few allocators that return memory to the operating system
while the process is still running.

In the case of vector, it is quite possible that the memory remains
managed by the vector object and is not even made available to other
objects in the same process.

If you have a significant memory management constraint and you need to
"free" memory back to the operating system, you need to use operating
system specific mechanisms like mapped files or special calls to return
memory to the OS. There exist malloc libraries that transparently return
memory to the OS but this is all off-topic here and you would probably
get better answers from a different forum specific to your platform.

 

[John Harrison]

Well I am using XP pro, so using the task manager I can see the memory
been used.

I assumed that I was not deleting something so I did a little test.

read all the test values...(around 90mb of memory).
And then 'erased' half of it. But the system was still showing that 90mb
was been used.

the problem is that I first read 90mb and then copy the data to the
'correct' array. By doing that I now have 180mb of memory usage.
So I need to erase it from the 'master' array so that I never use more
than 90mb of memory.

My final project will read 512mb of data.

Simon

Well that could be the problem. I don't know exactly how memory works on XP
but its entirely possible that freed memory does not get released back to
the system. The C++ standard only requires that freed memory is usable again
by the program. So you could be freeing all your memory and the task manager
would still show 90mb.

john

 

[John Harrison]

None of the standard containers gets smaller if you erease an
element. You have to swap it with themselves:

///pseudo code for std::vector
my_vect.swap(my_vect);

What makes you think this will free any memory?

john

 

[Pete Becker]

Well that could be the problem. I don't know exactly how memory works on XP
but its entirely possible that freed memory does not get released back to
the system.

Whether memory gets released back to the system depends on the
implementation of free, not on the OS.

 

[Nicolas Pavlidis]

What makes you think this will free any memory?

I missunderstood the question. I thought it was about how to make a
vector smaller while the program runs.

Sorry!

Kind regards,
Nicolas

 

[Ivan Vecerina]

....

typedef std::vector< int_array, std::allocator< int_array >> v_int_array; ....
To make sure the numbers never get used twice I 'erase' them from the
'master' array.

but the memory never seem to be freed.

std::vector will not release any memory when its 'erase' member
is called, eventually not even when clear() is called.
So you actually need to destroy a vector to have a chance of
releasing memory (that is, if the memory allocation code
actually releases unused memory to the system -- which is
commonly the case for large memory blocks).

There is a common idioms, however, that will typically force
the vector to release any unused memory.
To clear a vector and release its memory, you can use:
v_int_array().swap( myInstance );

To try to force a (minimal) reallocation of a vector,
the following will usually work:
v_int_array(myInstance.begin(),myInstance.end()).swap(myInstance);

In both cases, the idea is the same: you initialize a temporary
vector with the new contents you want to keep, swap it with
the vector itself, and let the temporary release the previous data.


hth -Ivan

 

[Roger Leigh]

Whether memory gets released back to the system depends on the
implementation of free, not on the OS.

Strictly speaking, it depends upon both. For example, if malloc() is
implemented entirely in terms of UNIX brk()/sbrk(), it /might/ be
possible to shift the data segment break limit to make it smaller.
But then again, it might not. You are entirely dependent upon the OS
implementation. If it uses mmap(), free() could also munmap() the
memory which will then be returned. In either case the implementation
of free() will have to rely on OS-specific calls to return the memory,
so free() cannot be written without knowledge of the OS, and is
dependent on the OS.

 

[Pete Becker]

Strictly speaking, it depends upon both. For example, if malloc() is
implemented entirely in terms of UNIX brk()/sbrk(), it /might/ be
possible to shift the data segment break limit to make it smaller.
But then again, it might not. You are entirely dependent upon the OS
implementation. If it uses mmap(), free() could also munmap() the
memory which will then be returned. In either case the implementation
of free() will have to rely on OS-specific calls to return the memory,
so free() cannot be written without knowledge of the OS, and is
dependent on the OS.

Sigh. Of course the implementation details of malloc and free depend on
the underlying OS. That's why they're there: to insulate the application
from system dependencies. Regardless, whether freed memory gets released
back to the system depends on the implementation of free. Some
implementations don't give it back until the program ends. Others make
the appropriate system calls on the fly. Once the memory is released
back to the system (which is what this subthread is about), it's
possible that the OS won't in fact make that memory available to other
applications.

 

[Kai-Uwe Bux]

Sigh. Of course the implementation details of malloc and free depend on
the underlying OS. That's why they're there: to insulate the application
from system dependencies. Regardless, whether freed memory gets released
back to the system depends on the implementation of free. Some
implementations don't give it back until the program ends. Others make
the appropriate system calls on the fly. Once the memory is released
back to the system (which is what this subthread is about), it's
possible that the OS won't in fact make that memory available to other
applications.

I was recently wondering if free() is at all allowed to return memory to
the operating system. In my, admittedly outdated, copy of the C standard,
the postcondition for free() is described as follows:

The *free* function causes the space pointed to by *ptr* to be
deallocated, that is, made available for further allocation. ...

I think, this can be read as a guarantee that the deallocated space will be
available to the program calling free(). I think this is a consequence of
the standard just defining the behavior of an instruction sequence: effects
of instructions other than observable effects like IO are specified
relative to that instruction sequence and therefore must be visible from
within. If that reading was correct, free() must not return memory to the
operating system.

I tried to find any postcondition guarantees for delete(). The C++ standard
says that delete() deallocates memory, but it does not define the term. Is
it understood that the definition is inherited from the language of the C
standard? Otherwise, all postcondition requirements for delete() would be
negative: fooling around with a deleted pointer is UB.

So the question is, are free() and delete() allowed to return memory to the
operating system or must memory be kept around so that it is available for
allocation further down the instruction sequence? Any language lawers
around?


Best

Kai-Uwe Bux

 

[Pete Becker]

The *free* function causes the space pointed to by *ptr* to be
deallocated, that is, made available for further allocation. ...

I think, this can be read as a guarantee that the deallocated space will be
available to the program calling free(). I think this is a consequence of
the standard just defining the behavior of an instruction sequence: effects
of instructions other than observable effects like IO are specified
relative to that instruction sequence and therefore must be visible from
within. If that reading was correct, free() must not return memory to the
operating system.

You can't portably determine whether a block of memory has been
recycled, so the standard can't require that memory blocks be recycled.
Hence the deliberately fuzzy wording "made available for further
allocation."

 

[Kai-Uwe Bux]

You can't portably determine whether a block of memory has been
recycled, so the standard can't require that memory blocks be recycled.
Hence the deliberately fuzzy wording "made available for further
allocation."

Well, I am not so sure that "made available for further allocation" is
really that fuzzy. Here is an attempt to spell out a minimal guarantee of
the postcondition for free():

{
void* p = malloc( 1024 );
if ( p != 0 ) {
// p was successfully allocated, there is a block of 1024 bytes.
free( p );
// the block referenced by p is now available for further allocation,
p = malloc( 1024 );
// thus this allocation shall succeed?
assert( p != 0 );
}
}

If the above interpretation of what it means to deallocate a pointer is
correct, then the assertion may never fail. Come to think of it, a
guarantee like that might actually come in handy sometimes.


Best

Kai-Uwe Bux

 

[Pete Becker]

If the above interpretation of what it means to deallocate a pointer is
correct,

It's not a matter of what it means to deallocate a pointer, but of what
it means to make the space available for further allocation. But read
the text for free carefully: it has that opening description, followed
by explicit requirements. The opening description isn't a requirement,
just a description.

then the assertion may never fail. Come to think of it, a
guarantee like that might actually come in handy sometimes.

It might be handy, but it imposes significant contraints on malloc/free
that aren't there at present, and with good reason: it requires
applications to be bad citizens by hogging memory.

 

[Greg Comeau]

Well, I am not so sure that "made available for further allocation" is
really that fuzzy. Here is an attempt to spell out a minimal guarantee of
the postcondition for free():

{
void* p = malloc( 1024 );
if ( p != 0 ) {
// p was successfully allocated, there is a block of 1024 bytes.
free( p );
// the block referenced by p is now available for further allocation,
p = malloc( 1024 );
// thus this allocation shall succeed?
assert( p != 0 );
}
}

If the above interpretation of what it means to deallocate a pointer is
correct, then the assertion may never fail. Come to think of it, a
guarantee like that might actually come in handy sometimes.

I think Peter is right. Furthermore, even if the memory must
be kept, it's hard to agree it's saying that the _very next_
call must be the one guaranteed to succeed. Of course, it would
probably be nice to see alternative words (of clarification of
the intent, not necessarily what you're reading (which I agree
could be nice in some cases)), but IMO the intent is that it says
that at the deallocation nothing is supposed to be assumed
to "own" the memory any longer, hence _if desired_,
it might be used again (reallocated) w/o harm.

 

[Sims]

Thanks to all the replies.

I have created my own function to release the memory totally but I am
not sure it is the best way to do it. It is very time consuming.

I sometime need to delete 2 items at the same time so that's why my
function asks for 2 items.

I was thinking of doing something like...

//
//
//
struct int_array{
int_array(){
a = b = 0;
}
int a, b;
};

//
//
//
typedef std::vector< int_array, std::allocator< int_array >> v_int_array;

v_int_array *g_my_int_array = 0;

//
// erase 1 or 2 items from the array.
//
void erase( int nItemA, int nItemB = -1 )
{
if( !v_int_array ){
return; // nothing to erase.
}

int nSize = v_int_array.size();
nSize-= 1;
nSize-= (b==-1?0:1);//if we are deleting more than one item...
v_int_array *my_int_array = new v_int_array;
my_int_array.reserve( nSize );

for( int loop = 0; loop < v_int_array.size(); loop++)
{
if( loop == nItemA || loop == nItemB )
{
continue;
}
my_int_array.push_back( *(g_my_int_array->begin()+loop ));
}
// remove the old one
delete g_my_int_array;
// replace with the new one
g_my_int_array = *my_int_array;
}

Many thanks for your comments.

Simon

 

[John Harrison]

Thanks to all the replies.

I have created my own function to release the memory totally but I am not
sure it is the best way to do it. It is very time consuming.

That's exactly why its not normally done with std::vector.

john