Do memory allocations need to be freeed every time?

[Ravindra.B]

I have declared a global variable which is array of pointers and
allocated memory for each array variable by using malloc. Some thing
similar to below...

static char *arr[10];

main()
{
int i;

for(i = 0; i < 10; i++)
arr[i] = malloc(sizeof(char));

……..

}

Is freeing the allocated memory is really required every time, for a
program like this as freeing doesn’t bring in any change w.r.t
memory space (or) will it become a memleak some where down the line if
it is not freeed?

Thanx,
Ravindra. Bhadramraju

[Richard Heathfield]

Ravindra.B said:

<snip>

Is freeing the allocated memory is really required every time, for a
program like this as freeing doesn?t bring in any change w.r.t
memory space (or) will it become a memleak some where down the line if
it is not freeed?

Best practice - take only what you need, make sure you've got it, and give
it back when you're done with it. If you ignore best practice, one day
you'll find yourself with a huge program, full of potential leaks, which
suddenly needs to become Just Another Function that is called many times
in a loop by the new main(), at which point the potential leaks become
actual leaks, and cause you months of work.

If you do it right, right from the start, you'll be fine in days to come -
except that you'll no doubt end up working on a project where some clown
has got it wrong because he ignored my advice, and you'll have to fix his
stuff, but at least you'll have the moral authority to curse the ground he
walks on.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[vippstar]

On Jun 19, 12:23 pm, "Ravindra.B" <[e-mail]>
wrote:

I have declared a global variable which is array of pointers and
allocated memory for each array variable by using malloc. Some thing
similar to below...

<snip code>

>
Is freeing the allocated memory is really required every time, for a

Yes. *Every* malloc pointer must be freed.

[den2k]

On 19 Giu, 11:23, "Ravindra.B" <[e-mail]:

Is freeing the allocated memory is really required every time, for a
program like this as freeing doesn’t bring in any change w.r.t
memory space (or) will it become a memleak some where down the line if
it is not freeed?

Thanx,
Ravindra. Bhadramraju

Let's say that it is a good practice. It is reasonable to think that
this piece of code will be used somewhere in a bigger application,
which may be executed continuosly for a lot of time whitout being
closed, and this may lead to mem leak.

Besides not every OS frees memory after the execution of a program and
many OSs may not free it due to an abnormal termination, so it's
always better to explicitly free memory by yourself.

[Chris Dollin]

vi******@gmail.com wrote:

On Jun 19, 12:23 pm, "Ravindra.B" <[e-mail]>
wrote:

>I have declared a global variable which is array of pointers and
allocated memory for each array variable by using malloc. Some thing
similar to below...

<snip code>

>>
Is freeing the allocated memory is really required every time, for a

Yes. *Every* malloc pointer must be freed.

/Should/, not /must/.

(and " ... eventually".)

--
"I am afraid that this theory is quite untenable." /The Caves of Steel/

Hewlett-Packard Limited registered no:
registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England

[jacob navia]

Ravindra.B wrote:

I have declared a global variable which is array of pointers and
allocated memory for each array variable by using malloc. Some thing
similar to below...

static char *arr[10];

main()
{
int i;

for(i = 0; i < 10; i++)
arr[i] = malloc(sizeof(char));

……..

}

Is freeing the allocated memory is really required every time, for a
program like this as freeing doesn’t bring in any change w.r.t
memory space (or) will it become a memleak some where down the line if
it is not freeed?

Thanx,
Ravindra. Bhadramraju

You can avoid the error prone usage of free by using a garbage
collector. This software will free automatically the allocated
memory for you when it notices that is no longer used.

Good compilers provide this facility in their standard distribution.

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32

[Ravindra.B]

On 19 Jun, 14:45, jacob navia <[e-mail]:

Ravindra.B wrote:

I have declared a global variable which is array of pointers and
allocated memory for each array variable by using malloc. *Some thing
similar to below...

static char *arr[10];

main()
{
int i;

for(i = 0; i < 10; i++)
arr[i] = malloc(sizeof(char));

……..

}

Is freeing the allocated memory is really required every time, for a
program like this as freeing doesn’t *bring in *any change w.r.t
memory space (or) will it become a memleak some where down the line if
it is not freeed?

Thanx,
Ravindra. Bhadramraju

You can avoid the error prone usage of free by using a garbage
collector. This software will free automatically the allocated
memory for you when it notices that is no longer used.

Good compilers provide this facility in their standard distribution.

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatiquehttp://www.cs.virginia.edu/~lcc-win32- Hide quoted text -

- Show quoted text -

That sounds interesting.

Can you tell me what are all the compilers that support it and how to
configure the same.

Thanx,
Ravindra.Bhadramraju

[den2k]

On 19 Giu, 11:45, jacob navia <[e-mail]:

>
Good compilers provide this facility in their standard distribution.

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatiquehttp://www.cs.virginia.edu/~lcc-win32

IMHO the better compiler stays in the middle of our ears, so there
must be the GC.. it is better to free manually, so you do know exactly
how your code behaves.

[vippstar]

On Jun 19, 12:59 pm, "Ravindra.B" <[e-mail]>
wrote:

On 19 Jun, 14:45, jacob navia <[e-mail]:

Ravindra.B wrote:

I have declared a global variable which is array of pointers and
allocated memory for each array variable by using malloc. Some thing
similar to below...

static char *arr[10];

main()
{
int i;

for(i = 0; i < 10; i++)
arr[i] = malloc(sizeof(char));

……..

}

Is freeing the allocated memory is really required every time, for a
program like this as freeing doesn’t bring in any change w.r.t
memory space (or) will it become a memleak some where down the line if
it is not freeed?

Thanx,
Ravindra. Bhadramraju

You can avoid the error prone usage of free by using a garbage
collector. This software will free automatically the allocated
memory for you when it notices that is no longer used.

Good compilers provide this facility in their standard distribution.

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatiquehttp://www.cs.virginia.edu/~lcc-win32-Hide quotedtext -

- Show quoted text -

That sounds interesting.

Can you tell me what are all the compilers that support it and how to
configure the same.

Do not quote sig blocks.
No, it's not interesting. These garbage collectors are error prone,
free() is not.
I've never heard of a good C compiler providing a GC.
They are also off-topic to discuss here. I, and others have, already
answered you:
You *must* free() allocated memory.
(Or, with Mr Dollins correction: you should, eventually)

[viza]

Hi

On Thu, 19 Jun 2008 02:23:05 -0700, Ravindra.B wrote:

Is freeing the allocated memory is really required every time, for a
program like this as freeing doesn’t bring in any change w.r.t memory
space (or) will it become a memleak some where down the line if it is
not freeed?

To avoid memory leaks, for each and every time you call malloc(), you
must call free() exactly once with the same pointer that was returned.

The only exceptions to this are:

1) if the call to malloc() returned NULL
2) if you are about to immediately terminate the program anyway*

* see
http://groups.google.co.uk/group/com...thread/thread/
be39423f62c88e04/a8e1101586394d42

HTH
viza

[Richard Bos]

viza <to******@gmil.comwrote:

On Thu, 19 Jun 2008 02:23:05 -0700, Ravindra.B wrote:

Is freeing the allocated memory is really required every time, for a
program like this as freeing doesn’t bring in any change w.r.t memory
space (or) will it become a memleak some where down the line if it is
not freeed?

To avoid memory leaks, for each and every time you call malloc(), you
must call free() exactly once with the same pointer that was returned.

The only exceptions to this are:

1) if the call to malloc() returned NULL
2) if you are about to immediately terminate the program anyway*

And even in those cases, you _may_ call free(), and it is often
considered good style (and particularly in the first case, can simplify
your code) if you do.

Richard

[Richard Heathfield]

Ravindra.B said:

On 19 Jun, 14:45, jacob navia <[e-mail]:

<snip>

>You can avoid the error prone usage of free by using a garbage
collector. This software will free automatically the allocated
memory for you when it notices that is no longer used.

Good compilers provide this facility in their standard distribution.

That sounds interesting.

Perhaps. Partitioned Data Sets are quite interesting, too, in their own
quiet way, but that doesn't make them relevant in comp.lang.c.

Note that "standard distribution" *doesn't* mean "garbage collection is
standard". It isn't standard. In the context of this newsgroup, "standard"
can reasonably be interpreted as meaning "available in all
implementations, or at least in all hosted implementations"; when someone
uses the term in some other way without pointing out the fact, it is
reasonable to assume that they are either lying, mistaken, or simply
clueless.

Can you tell me what are all the compilers that support it and how to
configure the same.

No compiler is *required* to provide garbage collection. The C language
doesn't provide this facility. If you come to rely on it, a time may well
come when you (think you) need it but can't have it. At that point, you
will realise why others here have been encouraging you to learn how to
manage memory yourself.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Richard Heathfield]

viza said:

Hi

On Thu, 19 Jun 2008 02:23:05 -0700, Ravindra.B wrote:

>Is freeing the allocated memory is really required every time, for a
program like this as freeing doesn?t bring in any change w.r.t memory
space (or) will it become a memleak some where down the line if it is
not freeed?

To avoid memory leaks, for each and every time you call malloc(), you
must call free() exactly once with the same pointer that was returned.

The only exceptions to this are:

1) if the call to malloc() returned NULL
2) if you are about to immediately terminate the program anyway*

The calloc and realloc functions muddy the waters a little. The calloc
function can simply be thought of as malloc with attitude, but realloc
needs a little care.

char *p = malloc(m * sizeof *p);
if(p != NULL)
{
char *q = realloc(p, n * sizeof *p);

In this case, when we eventually call free(), it is q that we must pass.
Passing p to free() would be an error, even though we got it from malloc
and haven't previously passed it to free().

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[jacob navia]

Ravindra.B wrote:

>
That sounds interesting.

Can you tell me what are all the compilers that support it and how to
configure the same.

The most popular garbage collector is Boehm's GC. It works with gcc
(you need to install it separatedly).

lcc-win (http://www.cs.virginia.edu/~lcc-win32) features a GC in
the standard distribution.

Note that if you download lcc-win, you can use gc.dll (32 bits
only) with another compiler if you wish. That would make it
possible to use a GC with ANY windows compiler.

Boehm's GC runs in almost all serious operating systems, wchich
includes several varints of HP unix, linux, MAC os, etc.

lcc-win has ported the GC to 64 bit windows and will be
distributed with the 64 bit version of lcc-win.
--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32

[santosh]

Ravindra.B wrote:

On 19 Jun, 14:45, jacob navia <[e-mail]:

>Ravindra.B wrote:

[ ... ]

Is freeing the allocated memory is really required every time, for
a program like this as freeing doesn?t *bring in *any change w.r.t
memory space (or) will it become a memleak some where down the line
if it is not freeed?

You can avoid the error prone usage of free by using a garbage
collector. This software will free automatically the allocated
memory for you when it notices that is no longer used.

Good compilers provide this facility in their standard distribution.

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatiquehttp://www.cs.virginia.edu/~lcc-win32- Hide
quoted text -

- Show quoted text -

Don't retain signatures unless you are discussing them. Signature blocks
are text following a "\n-- \n" sequence.

That sounds interesting.

Can you tell me what are all the compilers that support it and how to
configure the same.

Be aware that Garbage Collection is *not* a part of ISO C. If you want
your code to be portable to as many implementations as feasible, then a
Garbage Collector is likely to be a hindrance than help. Also Garbage
Collectors are not quite deterministic - they may very rarely free
memory in use or more commonly, fail to free memory that ought to be
freed. The might also not be suitable for program that demand realtime
response to events.

Having said all this, if you still want to tie your code to a GC, then
one of the better ones is the Boehm GC.

<http://www.hpl.hp.com/personal/Hans_Boehm/gc/>

[santosh]

Ravindra.B wrote:

I have declared a global variable which is array of pointers and
allocated memory for each array variable by using malloc. Some thing
similar to below...

static char *arr[10];

main()
{
int i;

for(i = 0; i < 10; i++)
arr[i] = malloc(sizeof(char));

??..

}

You might want to use a local array instead of a global one to reduce
maintenance headaches in the future. A local array inside main is
almost as long-lived as a file scope or static object, but may be
easier to manage in multi-threaded environment.

Also you might find that allocating memory just before needed and
deallocating it after you have finished may be an easier strategy than
allocating all the memory in one place and freeing it all at once in
another place.

Is freeing the allocated memory is really required every time, for a
program like this as freeing doesn?t bring in any change w.r.t
memory space (or) will it become a memleak some where down the line if
it is not freeed?

Deallocating unused memory is vitally important for daemon and server
programs. Even for a program that will do a short amount of work and
exit fairly quickly you might still want to get into the habit of
allocating memory when needed and scrupulously deallocating them when
you are done. This will be of immense help when you progress to large,
long lived programs, system programs etc.

[Linonut]

* vi******@gmail.com peremptorily fired off this memo:

You *must* free() allocated memory.
(Or, with Mr Dollins correction: you should, eventually)

But if you don't, the OS may do it for you -- catastrophically <grin>.

--
If you show people the problems and you show people the solutions they will be
moved to act.
-- Bill Gates, At Live8 (2 July 2005) as reported in BBC News (4 July 2005)

[CBFalconer]

Richard Heathfield wrote:

Ravindra.B said:

<snip>

>Is freeing the allocated memory is really required every time,
for a program like this as freeing doesn?t bring in any change
w.r.t memory space (or) will it become a memleak some where down
the line if it is not freeed?

Best practice - take only what you need, make sure you've got it,
and give it back when you're done with it. If you ignore best
practice, one day you'll find yourself with a huge program, full
of potential leaks, which suddenly needs to become Just Another
Function that is called many times in a loop by the new main(),
at which point the potential leaks become actual leaks, and cause
you months of work.

However, in practice there is often an exception. Some free
routines are O(N) (where N is the number of allocations in
effect). If you have stored a large amount of data the freeing of
all of it may thus become O(N*N), and there is no need to do it if
the program is about to end (and the OS cleans up).

The O(N) arises from the need to combine freed allocations, and
without a suitable design this requires examining all allocated
blocks. Note that the problem only arises with large numbers of
allocations, say 10,000 or more. You can play with your system
with the test programs for hashlib, and MAY be able to avoid the
problem with nmalloc. Both are available on my download area, see
sig below.

Discovering the problem with hashlib caused the generation of
nmalloc. Hashlib is portable and under GPL, while nmalloc is
essentially public domain and is not completely portable.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
** Posted from http://www.teranews.com **

[Tejas Kokje]

Ravindra.B wrote:

I have declared a global variable which is array of pointers and
allocated memory for each array variable by using malloc. Some thing
similar to below...

static char *arr[10];

main()
{
int i;

for(i = 0; i < 10; i++)
arr[i] = malloc(sizeof(char));

……..

}

Is freeing the allocated memory is really required every time, for a
program like this as freeing doesn’t bring in any change w.r.t
memory space (or) will it become a memleak some where down the line if
it is not freeed?

What do you mean "freeing doesn't bring in any change w.r.t memory space? "

arr is array of 10 pointers and you allocated each of them to point to a
char. You are consuming 10 bytes at the end of "for" loop.

Obviously, you should free those 10 bytes of memory if you are done
using it. It probably wouldn't matter (its just 10 bytes) on modern
systems if you were to do free just before program quits (since OS would
clean that mess for you), but for programs that run continuously (like
service daemons), memory leaks like this might eventually bring system
to its knees.

Tejas Kokje

[rio]

"Tejas Kokje" <bi*************@gmail.comha scritto nel messaggio
news:--******************************@comcast.com...

using it. It probably wouldn't matter (its just 10 bytes) on modern
systems if you were to do free just before program quits (since OS would
clean that mess for you), but for programs that run continuously (like
service daemons), memory leaks like this might eventually bring system to
its knees.

if malloc() function is like that is in the book K&RII there is the problem
that it use more memory that should be sufficient, because seems to me
that malloc() increase memory only [never decrease it if see the OS]: the
memory should be free only at the end of program and never first.

r.

[santosh]

rio wrote:

"Tejas Kokje" <bi*************@gmail.comha scritto nel messaggio
news:--******************************@comcast.com...

>using it. It probably wouldn't matter (its just 10 bytes) on modern
systems if you were to do free just before program quits (since OS
would clean that mess for you), but for programs that run
continuously (like service daemons), memory leaks like this might
eventually bring system to its knees.

if malloc() function is like that is in the book K&RII there is the
problem that it use more memory that should be sufficient, because
seems to me that malloc() increase memory only [never decrease it if
see the OS]: the memory should be free only at the end of program and
never first.

Some implementations of malloc do behave this because of system
constraints, but many implementations of malloc request memory on a
page by page basis and return freed pages as soon as you free them. You
must examine your implementation to find out how your malloc is
written. From the point of view of a standard C program, memory that is
freed is "made available for further allocation". How, when, and to
whom are questions that the standard leaves up to the implementations
to answer.

[gw7rib]

On 19 Jun, 10:23, "Ravindra.B" <[e-mail]:

I have declared a global variable which is array of pointers and
allocated memory for each array variable by using malloc. *Some thing
similar to below...

static char *arr[10];

main()
{
int i;

for(i = 0; i < 10; i++)
arr[i] = malloc(sizeof(char));

……..

}

Is freeing the allocated memory is really required every time, for a
program like this as freeing doesn’t *bring in *any change w.r.t
memory space (or) will it become a memleak some where down the line if
it is not freeed?

There's one point that people so far don't seem to have pointed out,
which may or may not be what you were asking.

Suppose your program uses, say, a buffer that can hold 10 chars, and
then, after that has finished, needs another buffer also of 10 chars.
You don't necessarily need to free the first buffer and then allocate
a new one - you could just keep the same one.

For example, the following:

buff = malloc(10);
/* first bit of code here, which uses buff */
free(buff);

/* second bit of code here, which doesn't use buff */

buff = malloc(10);
/* third bit of code here, which uses buff */
free(buff);

... could be replaced with the following:

buff = malloc(10);
/* first bit of code here, which uses buff */

/* second bit of code here, which doesn't use buff */

/* third bit of code here, which uses buff */
free(buff);

This would keep the memory allocated during the second bit of code,
meaning that your program uses more space than it needs to, but this
might not be a problem. It saves the expense of having to free the
memory and having to malloc another buffer. You have to decide whether
this is a worthwhile compromise.

You may think you need to malloc a new buffer to "clear" it, but this
is not the case - malloc does not (usually) clear the space it
allocates. So you may be able to reduce the number of mallocs and
frees that your program needs to do. You just have to make sure that
each buffer is big enough for what you will be using it for, and that
you don't overwrite any data that you still need.

Hope that helps.
Paul.

[Flash Gordon]

jacob navia wrote, On 19/06/08 12:11:

Ravindra.B wrote:

>>
That sounds interesting.

Can you tell me what are all the compilers that support it and how to
configure the same.

How to use a non-standard library is not topical here. It will depend on
your compiler/OS and maybe other things and so would be appropriate in a
group dedicated to your implementation or maybe mailing lists for
Boehm's GC.

The most popular garbage collector is Boehm's GC. It works with gcc
(you need to install it separatedly).

You stated in your previous post, "Good compilers provide this facility
in their standard distribution."

Installed separately is *not* "in their standard distribution". I also
believe that MS do not ship it as part of their implementation nor do
Intel and a lot of people consider one or both of those to be good
compilers.

Also are you sure it is available for *all* targets supported by gcc?
For a start I see no mention of lots of the systems that gcc supports.

lcc-win (http://www.cs.virginia.edu/~lcc-win32) features a GC in
the standard distribution.

Note that if you download lcc-win, you can use gc.dll (32 bits
only) with another compiler if you wish. That would make it
possible to use a GC with ANY windows compiler.

So?

Boehm's GC runs in almost all serious operating systems,

I saw no mention of, to take a few, z/OS, z/TPF or vxWorks to name just
three serious operating systems with completely different markets.

wchich
includes several varints of HP unix, linux, MAC os, etc.

This is not what the web site says. It says:
| The collector is not completely portable, but the distribution
| includes ports to most standard PC and UNIX/Linux platforms. The
| collector should work on Linux, *BSD, recent Windows versions, MacOS
| X, HP/UX, Solaris, Tru64, Irix and a few other operating systems. Some
| ports are more polished than others.

Note the last part, "some ports are more polished than others," which
implies there are still problems with some of the ports it lists.

lcc-win has ported the GC to 64 bit windows and will be
distributed with the 64 bit version of lcc-win.

So? The worls of serious OSs is much larger than that.
--
Flash Gordon

[CBFalconer]

Richard Harter wrote:

CBFalconer <cb********@yahoo.comwrote:

.... snip ...

>

>However, in practice there is often an exception. Some free
routines are O(N) (where N is the number of allocations in
effect). If you have stored a large amount of data the freeing
of all of it may thus become O(N*N), and there is no need to do
it if the program is about to end (and the OS cleans up).

The O(N) arises from the need to combine freed allocations, and
without a suitable design this requires examining all allocated
blocks. Note that the problem only arises with large numbers of
allocations, say 10,000 or more. You can play with your system
with the test programs for hashlib, and MAY be able to avoid the
problem with nmalloc. Both are available on my download area,
see sig below.

Discovering the problem with hashlib caused the generation of
nmalloc. Hashlib is portable and under GPL, while nmalloc is
essentially public domain and is not completely portable.

Now you have my curiosity arroused. I'm startled that any
standard implementation would examine all allocated blocks to
combine freed blocks. Where did you find this little gem?

I found it in DJGPP first, and further checking showed it was also
present in Visual-C, at different levels. I can't tie it to GCC,
because that depends on supplied libraries. Most systems probably
do recombination of freed segments, to avoid losing memory.

nmalloc is probably portable to all byte addressing systems that
use sbrk to secure assignable memory. The following comment is in
the source:

/* A re-implementation of malloc and friends for DJGPP 2.03/2.04
This includes many bits modeled after DJs original scheme.
This is NOT portable - it builds in knowledge of int size etc.
i.e. unsigned ints and pointers are both 32 bits (size 4)

The system is NOT thread and interrupt safe, although use of a
suitable critical section call could make it such. Nothing
herein executes for any unusual length of time (with NDEBUG).
*/

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
** Posted from http://www.teranews.com **

[Richard Harter]

On Thu, 19 Jun 2008 18:19:01 -0400, CBFalconer
<cb********@yahoo.comwrote:

>Richard Harter wrote:

>CBFalconer <cb********@yahoo.comwrote:

... snip ...

>>

>>However, in practice there is often an exception. Some free
routines are O(N) (where N is the number of allocations in
effect). If you have stored a large amount of data the freeing
of all of it may thus become O(N*N), and there is no need to do
it if the program is about to end (and the OS cleans up).

The O(N) arises from the need to combine freed allocations, and
without a suitable design this requires examining all allocated
blocks. Note that the problem only arises with large numbers of
allocations, say 10,000 or more. You can play with your system
with the test programs for hashlib, and MAY be able to avoid the
problem with nmalloc. Both are available on my download area,
see sig below.

Discovering the problem with hashlib caused the generation of
nmalloc. Hashlib is portable and under GPL, while nmalloc is
essentially public domain and is not completely portable.

Now you have my curiosity arroused. I'm startled that any
standard implementation would examine all allocated blocks to
combine freed blocks. Where did you find this little gem?

I found it in DJGPP first, and further checking showed it was also
present in Visual-C, at different levels. I can't tie it to GCC,
because that depends on supplied libraries. Most systems probably
do recombination of freed segments, to avoid losing memory.

I checked the djgpp implementation that I have and you are
quite right that it is O(N) - I am shocked. It is not what I
would call a professional grade implementation. The problem is
not with recombination of freed segments - that can be done as an
O(1) operation in any of a number of ways. Rather it is a matter
of unfortunate data structure and algorithm choices.

AFAIK both the BSD and the LINUX allocators do not have this
problem. There are professional grade allocators out there that
are freely available; quality implementations should use them.
Richard Harter, cr*@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

[CBFalconer]

Richard Harter wrote:

CBFalconer <cb********@yahoo.comwrote:

>Richard Harter wrote:

>>CBFalconer <cb********@yahoo.comwrote:

... snip ...

>>>
However, in practice there is often an exception. Some free
routines are O(N) (where N is the number of allocations in
effect). If you have stored a large amount of data the freeing
of all of it may thus become O(N*N), and there is no need to do
it if the program is about to end (and the OS cleans up).

The O(N) arises from the need to combine freed allocations, and
without a suitable design this requires examining all allocated
blocks. Note that the problem only arises with large numbers of
allocations, say 10,000 or more. You can play with your system
with the test programs for hashlib, and MAY be able to avoid the
problem with nmalloc. Both are available on my download area,
see sig below.

Discovering the problem with hashlib caused the generation of
nmalloc. Hashlib is portable and under GPL, while nmalloc is
essentially public domain and is not completely portable.

Now you have my curiosity arroused. I'm startled that any
standard implementation would examine all allocated blocks to
combine freed blocks. Where did you find this little gem?

I found it in DJGPP first, and further checking showed it was also
present in Visual-C, at different levels. I can't tie it to GCC,
because that depends on supplied libraries. Most systems probably
do recombination of freed segments, to avoid losing memory.

I checked the djgpp implementation that I have and you are
quite right that it is O(N) - I am shocked. It is not what I
would call a professional grade implementation. The problem is
not with recombination of freed segments - that can be done as an
O(1) operation in any of a number of ways. Rather it is a matter
of unfortunate data structure and algorithm choices.

Yes, the problem IS with recombination of freed segments. To do
that, you have to find the adjacent freed segment, which basically
involves a search. nmalloc keeps additional data that enables
finding the adjacent segment, whether or not free. This increases
the overhead storage per segment by 8 bytes. However it makes free
O(1). It also enables a lot of optimization in realloc.

>
AFAIK both the BSD and the LINUX allocators do not have this
problem. There are professional grade allocators out there that
are freely available; quality implementations should use them.

As I said, I found it in DJGPP, VC (using its own C library) and
lcc, using the dll C library supplied by MS in W98. Lcc is
non-standard, and I have not checked it later. If you don't design
the incidental data correctly in the malloc package you get that
O(N) free, and fixing that design eats more memory, as you can see
from the design in nmalloc. I built nmalloc and provided it back
for use in DJGPP, but fixing its library seems to be unpopular, and
it has never made it in.

What I am saying is that I suspect that O(N) action is more
prevalent than you think. For VC I had to use considerably higher
values of N to detect it than I did with the original DJGPP. And
that was on a slow machine (at the time I was running an 80 MHz
486, now a 500 MHz Pentium).

One problem with using nmalloc in other systems is that the
variadic macros are designed for gcc use, not the C99 standard. So
turning them off doesn't work properly with compilers other than
gcc. Those macros were only used for developmental debug, but I
don't want to remove them because they allow checking correctness.

AFAIK nmalloc works correctly everywhere with DJGPP. Using it just
involves linking the malloc module before searching the library.
Doing this means that nmalloc is also serving the whole library,
which is not guaranteed by the standard, but works for DJGPP.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
** Posted from http://www.teranews.com **

[Richard Harter]

On Fri, 20 Jun 2008 03:13:51 -0400, CBFalconer
<cb********@yahoo.comwrote:

>Richard Harter wrote:

>CBFalconer <cb********@yahoo.comwrote:

>>Richard Harter wrote:
CBFalconer <cb********@yahoo.comwrote:

[snip]

>>>Now you have my curiosity arroused. I'm startled that any
standard implementation would examine all allocated blocks to
combine freed blocks. Where did you find this little gem?

I found it in DJGPP first, and further checking showed it was also
present in Visual-C, at different levels. I can't tie it to GCC,
because that depends on supplied libraries. Most systems probably
do recombination of freed segments, to avoid losing memory.

I checked the djgpp implementation that I have and you are
quite right that it is O(N) - I am shocked. It is not what I
would call a professional grade implementation. The problem is
not with recombination of freed segments - that can be done as an
O(1) operation in any of a number of ways. Rather it is a matter
of unfortunate data structure and algorithm choices.

Yes, the problem IS with recombination of freed segments. To do
that, you have to find the adjacent freed segment, which basically
involves a search.

Seemingly we agree on everything except how to describe what we
agree on. :-)
[snip]

>What I am saying is that I suspect that O(N) action is more
prevalent than you think. For VC I had to use considerably higher
values of N to detect it than I did with the original DJGPP. And
that was on a slow machine (at the time I was running an 80 MHz
486, now a 500 MHz Pentium).

You're probably right. The original unix mallocs were very good,
and the linux allocator is also very good. Apparently many
people hack together system utilities with worrying about QOI.

There is a lesson here. Many people say things like, "Use the
language mandated utilities, the system programmers spent a lot
of work optimizing them." Well, it ain't necessarily so.

Richard Harter, cr*@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.