On Sunday, 1 March 2015 at 15:44:49 UTC, Marc Schütz wrote:
Walter posted an example implementation of a reference counted
array [1], that utilizes the features introduced in DIP25 [2].
Then, in the threads about reference counted objects, several
people posted examples [3, 4] that broke the suggested
optimization of eliding `opAddRef()`/`opRelease()` calls in
certain situations.
A weakness of the same kind affects DIP25, too. The core of
the problem is borrowing (ref return as in DIP25), combined
with manual (albeit hidden) memory management. An example to
illustrate:
1 > struct T {
2 > void doSomething();
3 > }
4 > struct S {
5 > RCArray!T array;
7 > }
8 > void main() {
9 > auto s = S(RCArray!T([T()])); // s.array's refcount
is
10> now 1
11> foo(s, s.array[0]); // pass by ref
++ s.array[0] = myt; // Would also be
invalid
12> }
13> void foo(ref S s, ref T T) {
14> s.array = RCArray!T([]); // drop the old
s.array
15> t.doSomething(); // oops, t is gone
16> }
1. Assignment to RC types is not the same as assignments to
non-RC types.
2. Allocation of RC types is more than just allocating of
non-RC types.
Using the above example:
#9: The assignment and allocation does two things:
a. Decrements the current RC of s.array(here it is null so
no RC is used)
b. Increments the ref count of the allocated RCArray by one.
#11: we pass both s and a referent to inside S. This is odd
behavior and not technically required in this case(just pass
S). Of course, we can't expect such behavior to creep up in
complex code.
#14. In this case the behavior is correct. The assignment does
the following:
a. Decrements the current RC of s.array(here was 1, so now
it is 0)
b. Increments the current RC of the newly allocated RC array
and assigns it to s.array.
#15. Since T refers to the old s.array, which now has a ref
count of 0(which we can assume to then be unallocated), line 15
becomes a run-time error.
---
How to fix?
It seems that the only way to make it work well is to use sort
of "lazy" ref counting.
Here references are created at the start of functions and
decremented at the end of functions... rather that in
place(which then causes problems with things that happen after
it).
But this can't work as in the ++ I added. Here it would solve
your problem but not fix the a generalization of it.
---
Is there a solution? Essentially no. Only at the end of the
program could we possibly have the last function release all RC
counted arrays. Since it is the end of the program it is the
only time we can know that no more RC types will be used.
The problem is analogous to the multiple-inheritance problem.
---
Flow analysis can only help so far(it won't help with
dynamically allocated types that are allocated depending on
some "random" factor.
---
Note that since t is pointing to a part of S, technically we
can't release s until t is released.
So, effectively, S has to be ref counted too! And it's ref
count must check check T's ref count. If it is non-zero then
the it can't release itself(or the reference to it's array).
Also, something eventually has to release S(or which is then
s.array). When? Well, since t depends on S, it is when t is
released. So we would naturally have to inform t that it should
too release s when it is released.
----
So, if that sort of makes sense I'll explain the solution: It
might be a bit fuzzy but I'll try to make things very clear. [I
will also sometimes conflate the usage of concrete objects and
their corresponding abstract types. e.g., "T with t". It should
be clear context which is meant. e.g., If I say "T is
released", I mean that the object with type T was released.
When they need to be distinguished between I will do so(mainly
in the code examples]
A *reference counted* type, from here on designated as RCT, is
a type that only allows itself to be released to the heap when
nothing depends on it. [Obviously if anything depends on it
when after it is released will fail to be fulfilled]
If a RCT does not contains any references to any RCT's we will
call it a free RCT or FRCT. Such types behave in a simple way.
They can be free'ed completely immediately. Since FRCT's do not
contain any references to other RCT's all their references are
simple references that can be free'ed immediately.
We require that if a type contains a reference to a RCT then it
too is a RCT. [the relation ContainsRCT(T1,T2) ==>
ContainsRCT(T2,T1) ==> Both T1 and T2 are either RCT's or not
RCT's] This isn't a big deal but without it we end up requiring
all types to be RCT's. Here we allow some types to be not be
RCT's.
In code,
class T { } // a standard non-reference counted type.
// It can't use any RCT's as references. It is
your basic D type of class.
rcclass FRCT // rcclass means reference counted class. It is
identical to your basic
// D type of class but has different keyword
designator(which is why we call them free).
{
int x;
float[] y
// etc, FRCT does not point to any RCT's
}
rcclass X { } // Just another RCT
rcclass RCT
{
FRCT myFRCT;
int y;
RCT foo(ref barRCT);
X x;
// etc Basically this is a class that can include other
RCT's
}
----
Ultimately we could simply use the basic D class but we would
have to designate every type as an RCT type... even the basic
types. I'm trying to avoid some basic issues of that method
that would derail the discussion. [But for those that want to
know: one could simply treat all objects in d as rcclass types
describe above, even basic types and such, but optimize out the
reference counting part in in the compiler for those basic and
FRCT types... this then would simply lead back to the method
I'm using to describe it but simply some of the details were
hidden in the "simple method" by the compiler]
So, once you have such a type system. The way to deal with the
complex relationships that exist are to know them:
1. A RCT have the following relationships between it's
containing types. We will denote T to be a non-RCT type, FRCT
to be an FRCT, and RCT to be an RCT.
RCT can contain T's, FRCT's, and/or, RCT's.
In Code:
rcclass RCT
{
T t;
FRCT myFRCT;
RCT myRCT;
}
In this case, which is the only case we will talk about
w.l.o.g), when an RCT is released it must attempt to release
each of it's references... in example above: t, myFRCT, and
myRCT. Since t is a simple type, it can be released
immediately. No RCT's point to it because if they did, then T
would be an RCT and it isn't. Similarly myFRCT can easily be
released because it is just a complex of things like T's. In
this case though there is something slightly different about it
which is the referencing counting part. Essentially it's
contained types are simple types but it still has a reference
counting aspect for itself.
Basically T's and FRCT's can free themselves when they need to.
This is because they know how to free each reference they
contain and it can't cause referential problems simply because
they do not contain such references. This by no means they
won't cause other parts of code to access invalid references. A
pointer to such a member of a class can easily try and access
the member after the object has been freed. But this is not our
concern because we are only dealing with RCT's. Our goal isn't
to have everything be RCT's. If that was the case then the T
and FRCT cases would not be needed since we won't use them.
e.g., We might want the GC to handle non-RCT and some other
method for FRCT's. This allows one to build on current D
system. But one must remember that RCT's only guarantee valid
referencing when they access other RCT's.
The last sentence above directs where we are going with this:
Since we have RCT we can make sure they know how to communicate
with each other. (we are creating a metatype here)
By having the proper communication system here it is possible
for the types to know when they need to be released.
In fact, it is not hard and several methods can be used, even
simultaneously.
Axiom: Every RCT has the ability to have any other RCT that
contains a reference to it, to be able to release it. Also,
vice versa!
[This requirement essentially allows the very final reference
to know that it needs to release other dependencies it had and
allows it to not only clean up itself but everything else it
needs to clean up]
Once you have the above requirement of RCT's(The implement
dealt with at a different time), you can lazily release objects
in the background without issue(fragmentation of the heap is a
harder matter but still has a solution because of the above
requirement).
How do they communicate:
Your example will do:
rcstruct T
{
void doSomething();
}
rcstruct S
{
T[] array;
}
void main()
{
auto s = S(new T()); // Here when the compiler creates
the array of T's S knows T is a RFC.
// In this case it can get at the
hidden communications layer of T and
// inform T that it is using it.
Hence at this point
// Both S and T can communicate
with each other! (not just blind inc/dec of an int
auto t = s.array[0];
foo(s, s.array[0]); // nothing special except foo
much create an added reference to the two argments
// This can be optimized out as
long as foo returns once for every time it
// is called. In this case, At
the start of foo, the counters will be inc'ed
// and at the end they will be
dec'ed. Always a zero sum outside the function call.
t.doSomething(); // Skip to foo, come back when
done with foo! Great, t is still around!
// (RC is still zero at this
point!)
}
void foo(ref S s, ref T t)
{
s.array = new T[]; // Here we are reassigning the
array. No problem! We simply inc the ref count on the new array
and decment it on the old. Just like normal ARC'ing! The only
different is that t is not immediately release! Even though it
has a RC count of 0. Think of it as lazy ARC'ing... or
LARC'ing! ;)
t.doSomething(); // Great, even though t has an RC
count of zero, it hasn't been released yet!
}
So, what is this LARCING?
Essentially instead of s simply dumping t in foo, it informs t
that it is no longer using it. This sets the RC = 0 !!BUT!! t
does not free itself immediately! If it does, it leads to the
problem you have given and also to the extended problem I have
shown above(calling t.doSomething in main).
If t sticks around though, we are not releasing memory and
hence what is the point?
Well, as usual this is an engineering problem. We have a few
cases.
1. The compiler can prove that a RCT goes out of scope and is
not used any more. In this case t can release itself at the end
of the function where it is provable that it is no longer used.
(In your example it is at the end of foo ad in my example it is
at the end of main) Flow analysis, simple brute force checking,
etc are used here. Most cases in program will fall under this
category. Local variables that are not referenced to by global
variables are proven to be releasable at the end of the
function call. Hence, many cases will work as simple ARC'ing
and not require LARC'ing.
2. The compiler cannot prove when a variable is release. This
is when the type itself has to decide when it is not being
used. (this the last part of the problem and your example falls
under it)
In this case, the communication between S and T is crucial.
When s decides it no longer need t, it informs t. t has a list
of every reference that is using it(this can just be a pointer
to the ref
count of the RCT). Having this list, while potentially weighty,
lets t know when all the references to it are not needed any
more(sort of chains or links between any other RCT and t have
been broken).
Once this is done it is a simple matter of t trying to release
itself every time it goes out of scope.
a. At some point t will release itself
b. t will never be able to release itself(this is
generally due to program error in which a reference was made to
t without removing the reference when it was done). Note this
is why if every type is an RCT, prevents dangling(e.g., we
would have full LARC'ing... or FLARC'ing.). FLARC'ing may not
be optimal though(all pointers would have to be RCT which would
probably be quiet inefficient. Also interdependencies are
handled easily:
s.t = t;
t.s = s;
while (!isFree(t) && !isFree(s))
{
s.t = null;
t.s = null;
if (t.refCount == 0)
s.release();
if (s.refCount == 0)
t.release();
}
The reason that t and s are released in LARC'ing is
because at the 2nd time through the loop s.release() knows that
t no longer depend and can release itself immediately(because
t.s = null set s's *t entry* to 0 on it so now s knows that t
doesn't depend on it). This is just a prototype that can be
used to show that any level of nesting between types will
eventually resolve all releases properly.
c. Alternatively, a GC like memory manager can scan
through the types and release all types who's reference count =
0 and who's dependencies are all invalid(nothing depends on
it). It can do this in the background without issue and can
compact consecutively release objects without issue. i.e., the
GC knows what part of the heap belonged to objects there were
ref counted and if it is proven they have any references then
it can mark them as free'ed memory. Consecutive free'ed objects
in memory can be combined since they never will be used again.
This can be done behind in parallel and is sort of minor
defragmentation. In fact, analogous to defragmenting a drive.
If you know a file is not being used then you can defragment it
in the background and move the various parts around without
issue because you know it is not being used. Once it is being
uses, you run into issues with having to stop the threads that
are using that part of the heap. (I think this limitation could
ultimately be removed for most practical cases.)
In this case the GC would have to have a list of all objects
of RCT's. Essentially the GC is given to the task of LARC'ing
in the background.
Finally, which such an structural approach(Essentially
implementing the reference list, which is a random access list
containing all the references(pointers to all classes that use
the type)) to ref counting becomes pretty stable and in
probably 99%+ of program usage, statically proven to release
memory(step a above, The compiler inserts many static releases
that are released immediately and many types will be simple
types that don't need LARC'ing).
The two issues with this, as always, are speed and memory
usage. I think it should rather fast(most releases are direct
and just release themselves since they don't have references.
On top of that the remaining are mostly FRCT's which can be
released nearly immediately(they can, but don't until they are
informed it is ok).
For the full blown RCT types, the way they release things is in
a hierarchical manner which can create avalanches of changes.
If many objects are waiting for one object to be released, then
when it does, they all could be released immediately. But this
chain reaction is simply lazily recursive and eventually
terminates.
The only real problem is how to deal with un-managed references
to RCT types. These are references(say pointers) to RCT's that
may not be "smart"(inform the RFC that it is no longer being
refered to. A simple pointer to a class that doesn't do any
communication is the prototypical problem.
The only solution seems to be to just accept it. It is a
necessary evil. Allow it but require the program to know the
intricate details. Such pointers are needed for speed and don't
inherently cause any problems. It's only when they are abused
can issues creep in.
If one, say, had RCT pointers that are used for some types of
problems and simple pointers when they are needed, it becomes
pretty marginal of an issue. (if you are doing driver
programming and have to have speed and direct access then use
the simple pointers but it is your just to know if your
references are working as expected.
In many cases, RCT pointers can be used in many of the cases
which make further minimize the singular problem case(that of
non-informative referencing). (We could call such types
"Peeping Toms"... but as long as they only peek it is ok(not by
law, in programming ;)).
At this, imagine that such a system was implemented. It would
provide almost complete automatic memory management coverage
with releasing resources as they are generally released in the
program flow. In fact, with a GC(don't you just hate it when
your garbage man doesn't pick up your trash sometimes?
specially if he never picks it up) that essentially works
parallel, most of the actual releasing can be done in the
background without ever stopping the program. The benefits are:
Better real-time behavior, Some programs might never need to
compact the heap(in fact, if intelligent heap allocation is
used, probably most programs could benefit from it), and
debugging is much easier(Essentially more like manual
management for most objects... just the compiler handles for
us, but we know when, most likely, an object goes out of scope
it will be released). Seg faults due to invalid memory access
will almost be reduced to 0(since the corner case... the
problem case of simple references is not used as much as all
the other ways to use objects).
The downside? There really isn't one except memory usage! One
can come up with special cases that simply don't work well
under LARC'ing but because it allows one to use non-LARC'ing
types, the programmer will just have to manage it on is own or
a mixed combination.
Another great benefit is performance. One may think with all
the all the extra allocation and deallocation code that the
end's of functions would be slowed down(do to objects being
lazily released). This is not necessarily the case because it
is LARC'ing, the releases can be done later... say outside a
performant piece of the code. It can even be faster than
directly releasing it because that could be slow in and of
itself, which, again, with LARC'ing, we can chose a better time
to release the object or do it in the background.
Unfortunately, if I'm not mistaken, with FLARC'ing, all classes
would essentially double in size. This is because if every
reference the type has is a RCT then it would essentially need
to store a pointer to the object as to provide a link to it.
With limited LARC'ing I think one could probably achieve a good
balance. (for large classes and/or a large number of objects,
one could just avoid LARC'ing to prevent the overhead and doing
it manually or with GC)
Some codetalk(tm) of how the interaction goes:
Object s is being initialized. It is a RFC type. It has,
as a member, a object x that is also a RFC type. In the course
of s being initialized, it initializes x. We'll assume it is
not null.
To do this s creates the object for x then informs x that it
has a reference to it(we could have multiple types of
references for further optimization if we want). e.g.,
x = new X;
x.CreateReference(s);
s.CreateReferenec(x); // We use directionless binding
references
Now, suppose at some point s is being released. At the end
of scope the compiler inserts
s.Release();
S now tries to release itself. It checks it's ref count and
the list of all references it has.
e.g.,
refCount = 0;
refList = {}
then in s.Release()
if (s.refCount == 0 && s.refList.IsEmpty)
{
GC.RemoveRCT(s); // GC.RemoveRCT is not necessary needed
but using it hear for expressive purposes.
s.Free();
}
else
GC.AddRCT(s); // Here, since the compiler potentially
isn't going insert another s.Release() outside the function we
have to let the GC handle it
in this case s free's itself immediately.
If either refCount != 0 or refList != empty, the GC is given
control(it is made aware that S needs to be periodically
checked to see if it can be released.(the GC simply does the
if (s.refCount == 0 && s.refList.IsEmpty) s.Free(); in a
parallel thread. If s.refCount == 0 and s.refList is empty at
some point then the GC ends up free'ing s.
Also, the compiler may be able to insert another s.Release()
in the outer scope of the function all if it releases that it s
was probably not released before. This doesn't hurt anything
except an extra check that might be wasted(profiling could
remove this check or even insert it).
The only way s can't be released is if it's refCount and
refList are not empty. This is "danling" references and can
only happen when mixing non-RCT's with RCT's.
So we know how s should release it self but how does t know
that s no longer needs it? (so t can release itself at some
point)
well, this has to do when x is assigned to. e.g.,
s.x = new X;
// Hidden, we have s update it's ref list and inform both
the hold x and the new x what is going on.
here the assignment will need to remove the old x from
refList and add the new x. This keeps the the list up to date.
(there is a big corner case here that I believe would never
occur but will have to think about it more)
Any ways, I'll leave it at that for now!