For the following, lifetimeEnd(x) is the time of freeing of x.

Given a reference graph and an const/immutable node n, all nodes reachable via n (let's call them Q(n)) must also be const/immutable, as per the rules of D's type system.

In order to avoid dangling pointers:
For all q in Q(n), lifetimeEnd(q) >= lifetimeEnd(n)

Therefore, there is never any need for the GC to mark or sweep anything in Q(n) during the lifetime of n.

Does the GC take advantage of this in some way to reduce collection times?

On Tuesday, 13 September 2016 at 15:27:23 UTC, John Colvin wrote:
> For the following, lifetimeEnd(x) is the time of freeing of x.
>
> Given a reference graph and an const/immutable node n, all nodes reachable via n (let's call them Q(n)) must also be const/immutable, as per the rules of D's type system.
>
> In order to avoid dangling pointers:
> For all q in Q(n), lifetimeEnd(q) >= lifetimeEnd(n)
>
> Therefore, there is never any need for the GC to mark or sweep anything in Q(n) during the lifetime of n.
>
> Does the GC take advantage of this in some way to reduce collection times?

I am pretty sure it does not.

On 9/13/16 11:27 AM, John Colvin wrote:
> For the following, lifetimeEnd(x) is the time of freeing of x.
>
> Given a reference graph and an const/immutable node n, all nodes
> reachable via n (let's call them Q(n)) must also be const/immutable, as
> per the rules of D's type system.
>
> In order to avoid dangling pointers:
> For all q in Q(n), lifetimeEnd(q) >= lifetimeEnd(n)
>
> Therefore, there is never any need for the GC to mark or sweep anything
> in Q(n) during the lifetime of n.

This only applies to immutable, because const can point at data that still has mutable references.

However, the GC could "know" that the actual data is immutable, so even a const reference could be known to point at immutable, and therefore unchanging, data.

> Does the GC take advantage of this in some way to reduce collection times?

No. Arrays would have to be treated specially though, since you can append into an immutable block (would have to clear the "already checked" flag).

It also might wreak havoc with Andrei's idea to have AffixAllocator create mutable islands of data in an immutable/const memory block.

I'm a bit skeptical that this would provide a lot of benefit. There would have to be a lot of immutable data for this to be worthwhile. Perhaps when paired with precise scanning?

-Steve