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.
--
Si
