linked lists and free()

[Hans Vlems]

Linked lists of structures can grow considerably and use a lot of memory.
Calling free() is necessary. What I do now is to descend the list to the pointer
that points to the last node in the list and call free(structptr->nextnode), and travel backwards to free each preceeding node.
Would just freeing the pointer to the top of the list work just as well?

Hans

 

[Malcolm McLean]

Linked lists of structures can grow considerably and use a lot of memory.

Calling free() is necessary. What I do now is to descend the list to the
pointer that points to the last node in the list and call free(structptr->
nextnode), and travel backwards to free each preceeding node.

Would just freeing the pointer to the top of the list work just as well?

Once you free memory, it becomes invalid and you can't access it again.
Often implementations don't "shred" memory on free, so using it will
appear to work, but eventually things will become unstuck.
So if you free the preceding node, the following node becomes orphaned.
But you can take a pointer to it, free the preceding node, then use that
pointer to free the rest of the list.
Try to write some code and post it here. I knock up little routines to
free linked lists all the time, so it wouldn't take me a minute. But
it's important to learn the technique.

 

[Paul N]

Linked lists of structures can grow considerably and use a lot of memory.

Calling free() is necessary. What I do now is to descend the list to the pointer

that points to the last node in the list and call free(structptr->nextnode), and travel backwards to free each preceeding node.

Would just freeing the pointer to the top of the list work just as well?



Hans

Normally, in a linked list, each item in the list has its own separate "chunk" of memory. Each item holds a pointer to the next item, so that it knowswhere it is, but it does not "control" it in any way.

To take a simple example, suppose there are only two items in the list. To clear the list completely and (try to) give the memory used back to the system, you would ask the first item where the second is stored; free that; then free the first item. You would normally also set the pointer that tells you where the first item is to NULL. If you just free the first item, the second item is still occupying memory - and worse still, you probably have no way of finding where in memory it is so you can't free it later even if you wanted to.

 

[Barry Schwarz]

Linked lists of structures can grow considerably and use a lot of memory.
Calling free() is necessary. What I do now is to descend the list to the pointer
that points to the last node in the list and call free(structptr->nextnode), and travel backwards to free each preceeding node.
Would just freeing the pointer to the top of the list work just as well?

You have to free memory in a manner that corresponds to the way in
which the memory was allocated. If, as appears to be your practice,
memory for each node was allocated individually, each must be freed
individually. If you free the memory occupied by the first node
without saving the address in the nextnode member, the memory occupied
by the remaining members becomes inaccessible and constitutes n-1
memory leaks.

 

[Hans Vlems]

Op vrijdag 30 augustus 2013 13:06:41 UTC+2 schreef Paul N:

Normally, in a linked list, each item in the list has its own separate "chunk" of memory. Each item holds a pointer to the next item, so that it knows where it is, but it does not "control" it in any way.



To take a simple example, suppose there are only two items in the list. To clear the list completely and (try to) give the memory used back to the system, you would ask the first item where the second is stored; free that; then free the first item. You would normally also set the pointer that tells you where the first item is to NULL. If you just free the first item, thesecond item is still occupying memory - and worse still, you probably haveno way of finding where in memory it is so you can't free it later even ifyou wanted to.

OK, that's what I thought would happen. So my method to travel all the linking pointers but the last (which is NULL) and start freeing first its contents (e.g. char *) and then itself, step one node back (recursively) and repeat the process until the master pointer is reached (which I termed points to the head of the list) and set that to NULL as the last step.
Just freeing the master pointer isn't enough.
Thanks,
Hans

 

[James Kuyper]

Linked lists of structures can grow considerably and use a lot of memory.
Calling free() is necessary. What I do now is to descend the list to the pointer
that points to the last node in the list and call free(structptr->nextnode), and travel backwards to free each preceeding node.
Would just freeing the pointer to the top of the list work just as well?

If you allocate a block of memory by calling malloc(), calloc() or
realloc(), and you don't call free() to deallocate that same block of
memory, then you have a memory leak. This applies separately to each
block - the memory allocation system doesn't know anything about the
fact that you've linked them together to form a list. If you allocated
each element of the list separately, then you have to free() each one
separately.

If you allocated a single block containing many different nodes, and
then linked them together to form a list, then you can deallocate that
entire block at one time - but calling free() on the head node will do
that only if the head node is also the first node in that block.

There's something called "garbage collection", which periodically checks
your entire memory to see if it contains anything that might be a
pointer into an allocated block of memory; if it finds no such pointers,
it automatically deallocates that block. A collector cannot, in general,
know the details of what memory means, so it can sometimes detect false
positives when a piece of memory that doesn't actually contain a pointer
happens to have the same bit pattern as a pointer to the allocated memory.

In effect, a garbage collection system DOES know about the fact that
your nodes are linked together. If you free the head node, sooner or
later it will notice that there's no pointers in memory pointing at the
second node of the list, and will collect it, too. Eventually, the
entire list will be collected. Note that this approach will not work on,
for instance, a doubly-linked list, because there are two pointers to
every node, and it cannot be deallocated until both have been collected
- therefore, none of them will be collected.

The malloc() family cannot use garbage collection, because the C
standard specifies that the life time of an allocated object continues
right up until it is explicitly free()d. There's no exception from this
requirement just because there are no pointers to that memory currently
in memory. Those pointers could be stored in an encrypted form not
recognized by the collector, or on disk, or they could even be displayed
for a user who writes them down and then types them back in later. If
there are no unencrypted copies of the pointer currently in memory,
garbage collection could collect the memory prematurely.

However, implementations can support garbage collection of memory
allocated by means other than the malloc() family. It's up to the user
of such memory to make sure that at least one pointer remains in memory
at all times, that points into any block of garbage-collectible memory
that the user doesn't want collected.

 

[James Kuyper]

Op vrijdag 30 augustus 2013 13:06:41 UTC+2 schreef Paul N:....
OK, that's what I thought would happen. So my method to travel all
the linking pointers but the last (which is NULL) and start freeing
first its contents (e.g. char *) and then itself, step one node back
(recursively) and repeat the process until the master pointer is
reached (which I termed points to the head of the list) and set that
to NULL as the last step. Just freeing the master pointer isn't
enough.

It would be simpler to deallocate it in the forward direction:

node * nextnode;
for(node *node=head; node; node=nextnode)
{
nextnode = node->nextnode;
free(node->data);
free(node);
}
head = NULL; // only needed if head is used farther down.

 

[Eric Sosman]

Linked lists of structures can grow considerably and use a lot of memory.
Calling free() is necessary. What I do now is to descend the list to the pointer
that points to the last node in the list and call free(structptr->nextnode), and travel backwards to free each preceeding node.
Would just freeing the pointer to the top of the list work just as well?

To the direct question, "No, not if each node was allocated
with its own malloc() call." One free() call releases the memory
obtained from one malloc() call (or realloc(), calloc(), etc.),
but does not affect memory obtained from other calls.

Freeing the nodes last-to-first is probably not the best way,
especially if (as you suggest) the list may be long. First-to-last
is usually better, if you'll exercise just a tiny bit of care:

void freeList(struct node *head) {
while (head != NULL) {
struct node *next = head->link;
free(head);
head = next;
}
}

The important bit is to retrieve each node's link field *before*
releasing the node's memory, not after the memory's gone:

void freeListINCORRECTLY(struct node *head) {
while (head != NULL) {
free(head);
head = head->link; // NO! NO! NO!
}
}

 

[Nobody]

Linked lists of structures can grow considerably and use a lot of memory.
Calling free() is necessary. What I do now is to descend the list to the
pointer that points to the last node in the list and call
free(structptr->nextnode), and travel backwards to free each preceeding
node. Would just freeing the pointer to the top of the list work just as
well?

If you use linked lists heavily, you may be better off implementing your
own allocator, using malloc() (or something lower level, e.g. sbrk()) to
supply larger blocks. E.g.

struct node {
void *data;
struct node *next;
};

static struct node *free_list;

static void more_nodes(void)
{
struct node *p = malloc(NUM_NODES * sizeof(struct node));
if (!p)
return p;
for (int i = 0; i < NUM_NODES-1; i++)
p.next = &p[i+1];
p[NUM_NODES-1].next = free_list;
free_list = p;
}

struct node* alloc_node(void)
{
if (!free_list)
more_nodes();
struct node *p = free_list;
if (p)
free_list = p->next;
return p;
}

void free_node(struct node* p)
{
p->next = free_list;
free_list = p;
}

 

[Keith Thompson]

You have to free memory in a manner that corresponds to the way in
which the memory was allocated. If, as appears to be your practice,
memory for each node was allocated individually, each must be freed
individually. If you free the memory occupied by the first node
without saving the address in the nextnode member, the memory occupied
by the remaining members becomes inaccessible and constitutes n-1
memory leaks.

You have to have a free() call for each malloc() call, but the free()
calls don't have to be in any particular order. (I know you didn't say
otherwise; I'm just clarifying.)

 

[Eric Sosman]

Linked lists of structures can grow considerably and use a lot of memory.
Calling free() is necessary. What I do now is to descend the list to the
pointer that points to the last node in the list and call
free(structptr->nextnode), and travel backwards to free each preceeding
node. Would just freeing the pointer to the top of the list work just as
well?

If you use linked lists heavily, you may be better off implementing your
own allocator, using malloc() (or something lower level, e.g. sbrk()) to
supply larger blocks. [...]

Nobody didn't explain why "you may be better off," so I'll
try to explain the reasoning. If malloc() adds a fixed overhead
to each allocation (this is common, but not universal), and if
the node is small so the overhead inflates its size significantly,
and if the nodes are very numerous, then the overhead may become
bothersomely large. For example, if malloc() adds an extra eight
bytes to each allocation and the nodes are only eight bytes long,
the overhead essentially doubles the memory use.

In such a case it may be helpful to malloc() big batches of
nodes and sub-allocate them as Nobody describes. If you ask
malloc() for 8000 bytes (intending to use them for 1000 eight-
byte nodes) and malloc() adds eight bytes of its own, the extra
eight bytes inflate memory use by only 0.1% instead of by 100%.
(There may also be a benefit in making one one-thousandth as many
malloc() and free() calls; the sub-allocator has a simpler job
to do, and may be able to do it faster.)

However, this is not a strategy to be used indiscriminately.
Remember, you can only free() what you malloc() -- *exactly*
what you malloc(). You can return an unused node to the pool
as Nobody shows, but you can't free() it; you can only free()
the entire 8000-byte block along with all the nodes it holds.
If you'd like to discard the block but it still holds one in-use
node, that single eight-byte node "pins" the entire block so
you cannot free() it.

There are circumstances where these tradeoffs can actually
be advantageous. I'm not saying "Don't Do That," just "Be Aware"
that Nobody's approach is not a drop-in replacement for using
malloc() and free() on individual nodes.

 

[Kenny McCormack]

You have to have a free() call for each malloc() call, but the free()
calls don't have to be in any particular order. (I know you didn't say
otherwise; I'm just clarifying.)

While what you say is technically true in the "C standards documents"
sense, it is, like most of the things you post, nonsensical in context.

Or, to put it another way, you didn't understand what the previous poster
wrote.

 

[Malcolm McLean]

On 8/30/2013 10:37 AM, Nobody wrote:

Nobody didn't explain why "you may be better off," so I'l
try to explain the reasoning. If malloc() adds a fixed overhead
to each allocation (this is common, but not universal), and if
the node is small so the overhead inflates its size significantly,
and if the nodes are very numerous, then the overhead may become
bothersomely large. For example, if malloc() adds an extra eight
bytes to each allocation and the nodes are only eight bytes long,
the overhead essentially doubles the memory use.

The other factor is speed.

If you look at my book Basic Algorithms you'll find a fixed block allocator.
It's simple to write, and each allocation is just a few machine instructions.
(It's a linked list in its own right).

See Basic Algorithms and much more:
http://www.malcolmmclean.site11.com/www

 

[Nobody]

Nobody didn't explain why "you may be better off," so I'll
try to explain the reasoning. If malloc() adds a fixed overhead to each
allocation (this is common, but not universal), and if the node is small
so the overhead inflates its size significantly, and if the nodes are very
numerous, then the overhead may become bothersomely large.

It's not just memory usage, but speed as well.

 

[Eric Sosman]

It's not just memory usage, but speed as well.

From the part you snipped:

 

[Hans Vlems]

Op vrijdag 30 augustus 2013 16:37:35 UTC+2 schreef Nobody:

Linked lists of structures can grow considerably and use a lot of memory.

Calling free() is necessary. What I do now is to descend the list to the

pointer that points to the last node in the list and call

free(structptr->nextnode), and travel backwards to free each preceeding

node. Would just freeing the pointer to the top of the list work just as

well?

If you use linked lists heavily, you may be better off implementing your

own allocator, using malloc() (or something lower level, e.g. sbrk()) to

supply larger blocks. E.g.



struct node {

void *data;

struct node *next;

};



static struct node *free_list;



static void more_nodes(void)

{

struct node *p = malloc(NUM_NODES * sizeof(struct node));

if (!p)

return p;

for (int i = 0; i < NUM_NODES-1; i++)

p.next = &p[i+1];

p[NUM_NODES-1].next = free_list;

free_list = p;

}



struct node* alloc_node(void)

{

if (!free_list)

more_nodes();

struct node *p = free_list;

if (p)

free_list = p->next;

return p;

}



void free_node(struct node* p)

{

p->next = free_list;

free_list = p;

}

I considered doing that but the data stored in the various kinds of linked lists comes from Excel sheets in the guise of csv files. The contents differ widely, from as little as 2500 records to nearly 200.000.
The overhead in elapsed (which the user notices) is negligible. Memory usage my be different, I have no easy way to observe that on a Windows system without access to task manager or top.
Hans

 

[Hans Vlems]

Op vrijdag 30 augustus 2013 14:51:50 UTC+2 schreef Eric Sosman:

To the direct question, "No, not if each node was allocated

with its own malloc() call." One free() call releases the memory

obtained from one malloc() call (or realloc(), calloc(), etc.),

but does not affect memory obtained from other calls.



Freeing the nodes last-to-first is probably not the best way,

especially if (as you suggest) the list may be long. First-to-last

is usually better, if you'll exercise just a tiny bit of care:



void freeList(struct node *head) {

while (head != NULL) {

struct node *next = head->link;

free(head);

head = next;

}

}



The important bit is to retrieve each node's link field *before*

releasing the node's memory, not after the memory's gone:



void freeListINCORRECTLY(struct node *head) {

while (head != NULL) {

free(head);

head = head->link; // NO! NO! NO!

}

}



--

Eric Sosman

(e-mail address removed)

That's a classic tradeoff, right . The algorithm is either head-to-tail,as you do and you need to declare temporary storage or recursively, in which case the no additional declaration is needed at the expense of a growingstack. In both cases memory is used.
Hans

 

[Hans Vlems]

Op vrijdag 30 augustus 2013 18:00:55 UTC+2 schreef Eric Sosman:

[snip]



--

Eric Sosman

(e-mail address removed)

Eric, thank you for your comments. I must admit that the overhead possibly incurred by malloc() never even crossed my mind. The program is interactive, the user must select input files and select one option on how to manipulate them.
All I cared for were fast response times... And even in the case where 149000 records are loaded, 48 fileds per record doesn't seem to slow down the system.
That is the advantage of systems with cpu's that run in GHz's and memory available in GB's.
Using "classical" programming techniques properly, the underlying processing system is hardly worth considering. Not like it was on a PDP 11/40 with 32 kB memory or a B7700 with "just" three processors and 1 MW main storage.Recursion with little overhead runs real fast on modern Intel gear!
Hans

 

[Eric Sosman]

[... ghastly double-spacing fixed ...]
Op vrijdag 30 augustus 2013 14:51:50 UTC+2 schreef Eric Sosman:

On 8/30/2013 5:06 AM, Hans Vlems wrote:
[...]
Freeing the nodes last-to-first is probably not the best way,
especially if (as you suggest) the list may be long. First-to-last
is usually better, if you'll exercise just a tiny bit of care:

void freeList(struct node *head) {
while (head != NULL) {
struct node *next = head->link;
free(head);
head = next;
}
}
[...]

That's a classic tradeoff, right . The algorithm is either head-to-tail, as you do and you need to declare temporary storage or recursively, in which case the no additional declaration is needed at the expense of a growing stack. In both cases memory is used.

Yes, memory is used -- but how much? For a list of N nodes,
last-to-first uses memory proportional to N to keep track of its
recursion[*], while first-to-last uses the same constant amount
of memory (two pointers' worth) no matter how long the list is.

[*] A different last-to-first algorithm also uses constant
memory, but running time proportional to the *square* of N.

 

[Ben Bacarisse]

[... ghastly double-spacing fixed ...]
Op vrijdag 30 augustus 2013 14:51:50 UTC+2 schreef Eric Sosman:

On 8/30/2013 5:06 AM, Hans Vlems wrote:
[...]
Freeing the nodes last-to-first is probably not the best way,
especially if (as you suggest) the list may be long. First-to-last
is usually better, if you'll exercise just a tiny bit of care:

void freeList(struct node *head) {
while (head != NULL) {
struct node *next = head->link;
free(head);
head = next;
}
}
[...]

That's a classic tradeoff, right . The algorithm is either
head-to-tail, as you do and you need to declare temporary storage or
recursively, in which case the no additional declaration is needed at
the expense of a growing stack. In both cases memory is used.

Yes, memory is used -- but how much? For a list of N nodes,
last-to-first uses memory proportional to N to keep track of its
recursion[*], while first-to-last uses the same constant amount
of memory (two pointers' worth) no matter how long the list is.

I don't think you can say that without qualification, even in the
context of C. gcc can do tail-call optimisation and I've just checked
that I can write a recursive reverse-order freeing function that uses
constant extra space.

[*] A different last-to-first algorithm also uses constant
memory, but running time proportional to the *square* of N.

And yet another (very similar to the code you'd write to reverse a list
in-place) has linear running time and uses constant space. You've be
within your rights to call this a front-to back freeing of a reversed
list (slightly optimised), but it does free the nodes in reverse order.
Another way to look at it is that since a C linked-list can be reversed
in place in linear time with constant storage, there's no significant
difference between freeing the nodes in either order.