How does a free list work?

Simen Kjærås simen.kjaras at gmail.com
Sat May 9 22:48:46 UTC 2020


On Saturday, 9 May 2020 at 19:54:44 UTC, Pavel Shkadzko wrote:
> I have been reading about memory management in D on 
> https://wiki.dlang.org/Memory_Management and found an example 
> of a free list (pattern?): "Free lists are a great way to 
> accelerate access to a frequently allocated and discarded 
> type.".
>
> Here is the example of free list:
> -----------------------------------------------
> class Foo
> {
>     static Foo freelist; // start of free list
>     Foo next; // for use by FooFreeList
>
>     static Foo allocate()
>     {
>         Foo f;
>
> 	if (freelist)
>         {
>             f = freelist;
> 	    freelist = f.next;
> 	}
>         else
> 	    f = new Foo();
> 	    return f;
>     }
>
>     static void deallocate(Foo f)
>     {
> 	f.next = freelist;
> 	freelist = f;
>     }
> }
> -----------------------------------------------
>
> Do I understand correctly that by switching between static and 
> non-static Foo we keep the object from being garbage collected 
> by the GC? So in a situation when I need to create an object 
> and then discard it, I can implement this pattern to use memory 
> more efficiently.
>
> Also, it's a little strange that since both f and freelist are 
> null we are basically doing null = null in first if condition.

The GC keeps a list of roots - that is, objects that are known to 
be active and should not be collected. The static freelist is one 
of those - since it's static it should of course never be 
collected.

 From these roots, the GC scans all referenced objects 
recursively, and finally releases all memory that has not been 
scanned (and that thus have no path of pointers leading from a 
root to that memory).

Since any call to new will check if memory is available, and 
potentially trigger a GC collection, it can be expensive, so if 
you can avoid allocating and deallocating objects a lot, it's an 
easy optimization.

To more clearly show this, here's some code that prints what it 
does:

import std.stdio : writeln;

class Foo {
     static Foo freelist;

     Foo next;
     string name;
     this(string name) {
         this.name = name;
     }
     ~this() {
         writeln("GC collecting ", name);
     }

     static Foo allocate(string name) {
         if (freelist) {
             auto f = freelist;
             freelist = f.next;
             writeln("Fetching ", f.name, " from freelist, 
changing name to ", name);
             f.name = name;
             return f;
         }
         writeln("Nothing in freelist, allocating new ", name);
         return new Foo(name);
     }

     static void deallocate(Foo f) {
         writeln("Adding ", f.name, " to freelist, freelist.next 
points to ",
                 freelist ? freelist.name : "(null)");
         f.next = freelist;
         freelist = f;
     }
}

unittest {
     Foo a = Foo.allocate("A");
     Foo b = Foo.allocate("B");
     Foo c = Foo.allocate("C");
     Foo.deallocate(a);
     Foo.deallocate(b);
     a = null;
     b = null;
     c = null;

     import core.memory;
     GC.collect();
     // For some reason I need to call this twice for C to be 
collected?
     GC.collect();

     Foo d = Foo.allocate("D");
     Foo e = Foo.allocate("E");
     Foo f = Foo.allocate("F");
}

The above code creates this output:

Nothing in freelist, allocating new A
Nothing in freelist, allocating new B
Nothing in freelist, allocating new C
Adding A to freelist, freelist.next points to (null)
Adding B to freelist, freelist.next points to A
GC collecting C
Fetching B from freelist, changing name to D
Fetching A from freelist, changing name to E
Nothing in freelist, allocating new F
1 unittests passed
GC collecting E
GC collecting D
GC collecting F


Here's what it does in more words:

For the first call to allocate(), the freelist is null, and a new 
Foo is created in the 'else' path, before being returned. Nothing 
is assigned to freelist or next.

The second and third call does the exact same thing, since 
nothing has been assigned to the freelist.

We then deallocate a, which assigns it to the freelist. Next we 
deallocate b, which sets b's 'next' field to point at a, and sets 
freelist to point at b. We then set a, b, and c to null, so those 
references will no longer keep the Foos alive.

Then we call GC.collect, which finds that the Foo previously 
stored in b is now in freelist, and thus will be kept. The Foo 
that was in a is referenced by freelist.next, and will also live. 
The foo in c, however, is no longer referenced anywhere, and will 
be collected.

This shows the main point of the freelist - to ensure the objects 
aren't collected by the GC - but what happens afterwards?

When we allocate d, freelist points at the Foo that used to be 
stored in b, so it is returned from allocate(), and the freelist 
is changed to point to the Foo that used to be in a.

Allocating e there's still something in freelist, so it is 
returned. At this point the freelist is empty, and allocating f 
creates a new Foo, just like when we allocated a, b, and c.

--
   Simen


More information about the Digitalmars-d-learn mailing list