Memory management question

[sbayeta]

Hi,
I'd like to know who is responsible of memory recycling and
defragmentation in a C/C++ program, assuming all the memory
allocation/deallocation is done using malloc/free or new/delete.

Thanks

 

[Gordon Burditt]

I'd like to know who is responsible of memory recycling and

defragmentation in a C/C++ program, assuming all the memory
allocation/deallocation is done using malloc/free or new/delete.

The Internal Revenue Service. And they'll bill you for it.
But they may have subcontracted the job out to Bill Gates.

There is no language C/C++.

If the above wasn't the answer you wanted, what kind of answer
did you expect?

Gordon L. Burditt

 

[jacob navia]

(e-mail address removed) (sbayeta) wrote in


There is no C/C++ language. There is C which we discuss here. So from a C
point of view there is no automatic memory recycling.

Wrong.

If I write:
int fn(void) {
char *a = malloc(100);
free(a);
return 0;
}

I expect that a reasonable implementation recycles the memory the best it can and my memory
consumption doesn't increase exponentially, sorry. I suppose that if I free a pointer, the memory
will be RECYCLED by the malloc/free system and the total memory consumption will not increase.

Of course I know that many implementations of malloc/free do not actually return the RAM to the OS
but recycle it for new requests. This is also a recycling strategy, sometimes more efficient
sometimes not.

But to say that there is no recycling in the malloc/free cycle (pun intended) is WRONG. If there was
no recycling why would we bother to call free() ?????

You malloc() the
memory and you must free it properly when done with it.

Yes. To be able to recycle it of course!

If this
process fragments memory over time, it's too bad as C does not do any
garbage collection.

I would be surprised that the algorithms (known for decades) to avoid fragmentation wouldn't have
gotten into many malloc() implementations. They are quite sophisticated beasts. Of course it depends
of the quality of the run-time library, but most of them are very good quality stuff. Gcc for
instance has a quite good library.

Look Mark. There was recently a discussion (that I started, provocatively as a "spam" message
about the GC.
Now this question touches the same thema again, and you feel that the wrong party line is
insinuating somewhere.

And you loose control Mark. You say nonsense. How can you imagine that there is no recycling in C? I
mean those are the very basics.

jacob

 

[jacob navia]

Hi,
I'd like to know who is responsible of memory recycling and
defragmentation in a C/C++ program, assuming all the memory
allocation/deallocation is done using malloc/free or new/delete.

Thanks

In C, memory recycling is done by the malloc/free system.
The malloc function allocates a new pointer, and free, releases it.

It is up to the implementation to recycle the memory, and many of
them have built sophisticated systems to avoid fragmentation, check
memory leaks, etc. Others aren't so good, sometimes they are slow and
may have bugs.

This system is very modular and can be easily replaced by your own
functions or another, non standard allocator.

But let's not start that discussion again

jacob

 

[Mark A. Odell]

Wrong.

If I write:
int fn(void) {
char *a = malloc(100);
free(a);
return 0;
}

I expect that a reasonable implementation recycles the memory the best
it can and my memory consumption doesn't increase exponentially, sorry.

You've already killed your argument by saying a "reasonable
implementation" since that has nothing to do with what ISO C says. ISO C
doesn't say what an implementation, reasonable or otherwise must do with
free()'d memory.

I suppose that if I free a pointer, the memory will be RECYCLED by the
malloc/free system and the total memory consumption will not increase.

No, it just goes back into the available memory pool for subsequent
malloc's.

Of course I know that many implementations of malloc/free do not
actually return the RAM to the OS but recycle it for new requests. This
is also a recycling strategy, sometimes more efficient sometimes not.

But to say that there is no recycling in the malloc/free cycle (pun
intended) is WRONG. If there was no recycling why would we bother to
call free() ?????

Oh it goes back into the free list but it doesn't mean that you won't
fragment memory over time.

I would be surprised that the algorithms (known for decades) to avoid
fragmentation wouldn't have gotten into many malloc() implementations.

Again with the implementation, where in the ISO C spec. does it say
malloc/free must use power of two allocators or any such thing?

They are quite sophisticated beasts. Of course it depends of the quality
of the run-time library, but most of them are very good quality stuff.
Gcc for instance has a quite good library.

All off-topic platform-specific then.

Look Mark. There was recently a discussion (that I started,
provocatively as a "spam" message about the GC.
Now this question touches the same thema again, and you feel that the
wrong party line is insinuating somewhere.

And you loose control Mark. You say nonsense. How can you imagine that
there is no recycling in C? I mean those are the very basics.

I've never actually seen such a term in the pages of the spec. I've read.
Dan? Comment?

 

[Mark A. Odell]

In C, memory recycling is done by the malloc/free system.
The malloc function allocates a new pointer, and free, releases it.
Correct.

It is up to the implementation to recycle the memory, and many of
them have built sophisticated systems to avoid fragmentation, check
memory leaks, etc. Others aren't so good, sometimes they are slow and
may have bugs.

Correct, it's up to the *implementation* and is *not* dictated by the C
language thus do *not* depend on malloc/free to avoid fragmentation.

 

[Irrwahn Grausewitz]

Wrong.

So, if automatic memory recycling is a built in feature of
standardized C, what was this "Garbage Collection in C" thread
good for then?

If I write:
int fn(void) {
char *a = malloc(100);
free(a);
return 0;
}

I expect that a reasonable implementation recycles the memory the best it can and my memory
consumption doesn't increase exponentially, sorry. I suppose that if I free a pointer, the memory
will be RECYCLED by the malloc/free system and the total memory consumption will not increase.

Maybe. Maybe not. You're expexting, guessing, supposing. What if
I'm just about to finish a conforming C implementation that
physically burns free()'d memory for security reasons? Is this
impossible?

[OT]
And please, please cut down your line length, your posts are
messing up my newsreader...

0 1 2 3 4 5 6
0123456789012345678901234567890123456789012345678901234567890123456789
[/OT]

Of course I know that many implementations of malloc/free do not actually return the RAM to the OS
but recycle it for new requests. This is also a recycling strategy, sometimes more efficient
sometimes not.

So, who is responsible for reclaiming free()'d memory then?

But to say that there is no recycling in the malloc/free cycle (pun intended) is WRONG. If there was
no recycling why would we bother to call free() ?????

To let the implementation do whatever it does with free()'d
memory...

Yes. To be able to recycle it of course!

See above. Maybe it's recycled for further use. Maybe not.
(Whereas you're right in that *probably* *most* implementations
will do so.)

I would be surprised that the algorithms (known for decades) to avoid fragmentation wouldn't have
gotten into many malloc() implementations. They are quite sophisticated beasts. Of course it depends
of the quality of the run-time library, but most of them are very good quality stuff. Gcc for
instance has a quite good library.

Right, *many implementations* will do so. Got the point?

Look Mark. There was recently a discussion (that I started, provocatively as a "spam" message
about the GC.
Now this question touches the same thema again, and you feel that the wrong party line is
insinuating somewhere.

Starting it all over again... *g*

And you loose control Mark. You say nonsense. How can you imagine that there is no recycling in C? I
mean those are the very basics.

IMHO Mark is perfectly right. You are the one who's generalizing
the behaviour of some implementations to be the one and only way
to do things. Basically, I *can* imagine C without memory
recycling. ( Maybe there's a lack of imaginational potential on
your side? *g* )


Ooooops, I just stumbled over this (from the N843 draft):
-----
7.20.3.2 [...] [#2] The free function causes the space pointed
to by ptr to be deallocated, that is, made available for
further allocation.
-----

Maybe I was totally wrong

That's why I call for the experts now - please help.


Irrwahn

 

[Gordon Burditt]

So, if automatic memory recycling is a built in feature of

standardized C, what was this "Garbage Collection in C" thread
good for then?

Automatic memory recycling is re-using freed memory.
Garbage collection is re-using non-freed memory when (hopefully)
it is no longer in use.

Maybe. Maybe not. You're expexting, guessing, supposing. What if
I'm just about to finish a conforming C implementation that
physically burns free()'d memory for security reasons? Is this
impossible?

The clause in ANSI C about making the memory available for later
allocation would seem to prohibit this. Some claim it also
prohibits releasing it back to the OS if there is any possibility
that the OS would give it to some other process and refuse
a request to get it back to the one that released it. The really
pedantic ones insist that it has to be willing to give back
the *SAME* *PHYSICAL* *MEMORY* before it can claim it ran out.

Ooooops, I just stumbled over this (from the N843 draft):
-----
7.20.3.2 [...] [#2] The free function causes the space pointed
to by ptr to be deallocated, that is, made available for
further allocation.
-----

So, who is responsible for reclaiming free()'d memory then?

There is no WHO in this discussion. malloc()/free() is not alive.
ANSI C is not alive. Laidlaw of Benbrook has no contract for
cyberspace. I guess it defaults to Bill Gates or the IRS.

As far as defragmentation goes, it is nearly impossible in C to
move around *ALLOCATED* pieces of memory without breaking something.
This is made particularly a problem by the fact that pointers (which
would require moving if you move the data they point at, but only
if they really are intended as pointers) can be hidden in files or
encrypted in memory.

Gordon L. Burditt

 

[Irrwahn Grausewitz]

(e-mail address removed) (Gordon Burditt) wrote in
<[email protected]>:

There is no WHO in this discussion. malloc()/free() is not alive.
ANSI C is not alive.

Sorry for my broken english.

Thank you very much for clearing things up.

 

[jacob navia]

You've already killed your argument by saying a "reasonable

implementation" since that has nothing to do with what ISO C says. ISO C
doesn't say what an implementation, reasonable or otherwise must do with
free()'d memory.

The standard says
(I quote page 312, free() definition)

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

end quote

Next allocations will recycle the memory freed!

No, it just goes back into the available memory pool for subsequent
malloc's.

And this is not recycling Mark?
I mean what are you trying to achieve? Confusion?

jacob

 

[Mark A. Odell]

Hmm... I should have continued by saying "except that the free'd memory
can now be malloc'd again".

The standard says
(I quote page 312, free() definition)

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

end quote

Next allocations will recycle the memory freed!

Okay I can't argue with that definition of recycling memory. I didn't mean
to imply that once freed you couldn't remalloc that same memory region
just that if you keep malloc'ing and free'ing different sized blocks of
memory you may fragment the memory such that you begin to fail large
malloc's.

And this is not recycling Mark?
I mean what are you trying to achieve? Confusion?

No, I just thought you were saying that C provides anti-framentation as
part of the language, which it does not.

 

[Gordon Burditt]

Look. I have an automatic drive in my car. I do not feel like changing gears.

Many drivers I know though, like manually changing gears. They tell me about the
"good driving" feeling they get when they do this manually.

malloc/free require a manual interface. The driver needs to free each piece of
memory at the right point and never make a mistake. Many of them tell that
with a good discipline this is possible, and I must confess that before
I used a gc
I got through that too.

But now, I prefer the automatic you see? No more free(). The gc does it for me.

But, to continue the analogy, sometimes the automatic transmission
does it wrong when you're towing a trailer (hiding pointers where
the gc can't find them). Either it ruins the engine (frees memory
that should NOT be free), or it slows down horribly (spends enormous
amounts of time looking for pointers where they aren't) and takes
24 hours to get home. And there's no practical way to fix this
without putting restrictions on how you drive.

Now what happens when a one of a generation of drivers who grew up
with automatic transmissions only need to tow a trailer?

Gordon L. Burditt

 

[jacob navia]

[snip]

But, to continue the analogy, sometimes the automatic transmission
does it wrong when you're towing a trailer (hiding pointers where
the gc can't find them). Either it ruins the engine (frees memory
that should NOT be free), or it slows down horribly (spends enormous
amounts of time looking for pointers where they aren't) and takes
24 hours to get home. And there's no practical way to fix this
without putting restrictions on how you drive.

Yes, but I can go farther because I am less tired you see?

Automatic driving requires less efforts from the driver and he/she
can drive longer distances!

For instance, I added the GC to the debugger/IDE of lcc-win32.

Because I do not have to write any code to cope for free() bugs or
problems, I used the saved time to improve the application itself.

I concentrated in the debugger itself, a *very* complex application.
Real time, with 3 threads running (debugger IDE, program under
debug, and debugger itself), with many complex specs to read the
debug info, messages that must be formated at each break, etc etc!

Now, I know that I can allocate a buffer whenever I need one, and
that I can pass it around without caring where I will free the stuff!!!

Debugging the debugger is difficult. Without the GC I would have been
slowed down by all those accounting chores and would have had less
time to try to improve it.

Besides, the crashes due to messing around with free would be
inacceptable. A debugger crashing, what a nightmare

I spoke once with a TAXI driver (!!!) with manual driving. I told him:

Look, it doesn't hurt your hand at the end of the day?
You do not get feed up?

He admitted that it hurt a bit, but then he started telling me all
the bad things that stupid automatic drivers
do, that they do not know their vehicle etc etc.

I said nothing, payed and got out. There must be all kinds of people to
fill this world. It is his opinion. I respect it.

jacob

 

[Malcolm]

Yes, but I can go farther because I am less tired you see?

Automatic driving requires less efforts from the driver and he/she
can drive longer distances!

There is a case for using a language with automatic garbage collection.
Modern C++ with the stl is one such language.

However that language isn't C. Part of the philosophy of C is that every
statement, apart from a function call, compiles to only a few machine code
instructions. Therefore you can see where your cycles are going.

Automatic garbage collection breaks that design principle.

 

[Severian]

There is a case for using a language with automatic garbage collection.
Modern C++ with the stl is one such language.

However that language isn't C. Part of the philosophy of C is that every
statement, apart from a function call, compiles to only a few machine code
instructions. Therefore you can see where your cycles are going.

Automatic garbage collection breaks that design principle.

In many situations, neither mechanism (std malloc, GC) is appropriate.
I've had to write my own memory management routines for several
applications because of malloc's deficiencies.

- Sev

 

[jacob navia]

However that language isn't C. Part of the philosophy of C is that every
statement, apart from a function call, compiles to only a few machine code
instructions. Therefore you can see where your cycles are going.

Automatic garbage collection breaks that design principle.

No. When you call malloc() you can expect a GC. Very simple.
GC_malloc calls takes longer sometimes (gc done) or are quite fast.

malloc() can take longer if it needs to call the OS, and the OS can
take longer if it needs to swap a page to disk.

Nothing in the language tells you how long malloc calls take.
Free can be longer sometimes if free() consolidates some memory.

In the long run both things (malloc/free) and the gc take the same
time. The time you spend doing free() must be counted too, as
well as the time you pass in the debugger.

True, the GC is not a panacea and, as anything, has it drawbacks.

For instance, if you forget to set to null a global variable pointing to a
huge memory block, it will not be freed, and your program may fail
because you always allocate a big chunk of memory without cutting
any pointers to it.

An advantage is that all objects with only one pointer to them
(typical case) will be freed if the function where the pointer resides
exits. All local variable pointers that use a malloced memory will
be no longer in scope when the function exists so the collector will find
no references to them.

 

[Mark McIntyre]

The standard says
(I quote page 312, free() definition)

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

end quote

Next allocations will recycle the memory freed!

It MAY recycle it, there is no obligation to. In fact I've often
observed that it does not. Imagine you free a 24 byte block ,and your
next allocation requires a 1204 byte block. Makes more sense for the
OS to find a large enough space, rather than allocate only 24 bytes in
one place, and have to manage the "appears contiguous" issue.

And this is not recycling Mark?

Recycling is reusing. Putting it back in the pool is not reusing it,
that happens when its reused.

I mean what are you trying to achieve? Confusion?

I think you two have different meanings of "recycling". Marks is more
common I fear.

 

[Joe Wright]

No. When you call malloc() you can expect a GC. Very simple.
GC_malloc calls takes longer sometimes (gc done) or are quite fast.

malloc() can take longer if it needs to call the OS, and the OS can
take longer if it needs to swap a page to disk.

Nothing in the language tells you how long malloc calls take.
Free can be longer sometimes if free() consolidates some memory.

In the long run both things (malloc/free) and the gc take the same
time. The time you spend doing free() must be counted too, as
well as the time you pass in the debugger.

True, the GC is not a panacea and, as anything, has it drawbacks.

For instance, if you forget to set to null a global variable pointing to a
huge memory block, it will not be freed, and your program may fail
because you always allocate a big chunk of memory without cutting
any pointers to it.

An advantage is that all objects with only one pointer to them
(typical case) will be freed if the function where the pointer resides
exits. All local variable pointers that use a malloced memory will
be no longer in scope when the function exists so the collector will find
no references to them.

Jacob,

GC notwithstanding, what is garbage collection?
I am writing a C module which would trap malloc/realloc/free etc and
maintain a list of pointers to and the sizes of the allocations. The
list is (normally) invisible to the user. When the user invokes
free(ptr) I look up ptr in the list. If I find it, I free the allocation
and free and remove the list node. If I don't find it (user gives me an
invalid pointer), I simply ignore it. I provide a freeall() function
which will free all allocated memory.

Does this qualify as garbage collection?

 

[CBFalconer]

[snip]

But, to continue the analogy, sometimes the automatic transmission
does it wrong when you're towing a trailer (hiding pointers where
the gc can't find them). Either it ruins the engine (frees memory
that should NOT be free), or it slows down horribly (spends enormous
amounts of time looking for pointers where they aren't) and takes
24 hours to get home. And there's no practical way to fix this
without putting restrictions on how you drive.

Yes, but I can go farther because I am less tired you see?

Automatic driving requires less efforts from the driver and he/she
can drive longer distances!

For instance, I added the GC to the debugger/IDE of lcc-win32.

Because I do not have to write any code to cope for free() bugs or
problems, I used the saved time to improve the application itself.

I concentrated in the debugger itself, a *very* complex application.
Real time, with 3 threads running (debugger IDE, program under
debug, and debugger itself), with many complex specs to read the
debug info, messages that must be formated at each break, etc etc!

Now, I know that I can allocate a buffer whenever I need one, and
that I can pass it around without caring where I will free the stuff!!!

Debugging the debugger is difficult. Without the GC I would have been
slowed down by all those accounting chores and would have had less
time to try to improve it.

Now this, to me, is a legitimate use of a GC package. It is mated
to the system programs themselves. A debugger, by nature, is a
non-portable application (although large portions of it should be
as portable as possible)

Besides, the crashes due to messing around with free would be
inacceptable. A debugger crashing, what a nightmare

However, the last time I looked, the lcc-win32 debugger still
crashes immediately when run on a 486 :-( This doesn't happen
with gdb. (and I did report it).

 

[CBFalconer]

.... snip ...

malloc() can take longer if it needs to call the OS, and the OS can
take longer if it needs to swap a page to disk.

Nothing in the language tells you how long malloc calls take.
Free can be longer sometimes if free() consolidates some memory.

I have written a malloc/free/realloc package that ensures free is
O(1) at all times. You are welcome to use the ideas therein if
you wish. The free in crtdll (which I believe you use) is O(n),
where n is the number of blocks in play. So far I know of no
other RTL with an O(1) free.

See download/nmalloc.zip on my site.