Simen Kjærås 
Posted in reply to Pavel Shkadzko
| 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
|
Permalink
Reply
