What restrictions have to be made to make the GC 100% precise?

I am aware of:
- unions
- owning void* pointers?

Would it be sufficient to:

1. ban void-pointers from owning memory with pointers in them?

2. require that aggregates with unions in them provide a union_pointers range like constructor that will yield all the pointers and their types? Standard library constructs with unions that contain pointers could provide it, so it would not affect the standard library I think.

Or are there other obstacles for precise tracing?

I believe that 2) could be checked at compile time when the code attempts to allocate from the GC. Although I guess you would also have to forbid allocating raw memory from the GC that is later emplaced with types that contain pointers.

Also pointer-integer casts, some callback interfaces allow to supply user data in the form of pointer or integer.

On Friday, 13 November 2020 at 13:05:45 UTC, Kagamin wrote:
> Also pointer-integer casts, some callback interfaces allow to supply user data in the form of pointer or integer.

But they will not be owning pointers as integers, I guess?

On 12/11/2020 09:43, Ola Fosheim Grøstad wrote:
> What restrictions have to be made to make the GC 100% precise?
>
> I am aware of:
> - unions
> - owning void* pointers?
>
> Would it be sufficient to:
>
> 1. ban void-pointers from owning memory with pointers in them?

These are not a problem with the current implementation, because precise scanning is not done by the pointer type, but the type used for the allocation. Pointer types don't contain enough information for polymorphic classes or pointers to fields of structs.

>
> 2. require that aggregates with unions in them provide a union_pointers range like constructor that will yield all the pointers and their types? Standard library constructs with unions that contain pointers could provide it, so it would not affect the standard library I think.
>
> I believe that 2) could be checked at compile time when the code attempts to allocate from the GC. Although I guess you would also have to forbid allocating raw memory from the GC that is later emplaced with types that contain pointers.
>

The original proposal for the precise GC had a function call
gc_emplace() that allowed to specify pointer location for a memory
range. This could be used for unions or emplacement of data into untyped
memory.
This version of the GC used a bitmap of pointers in all of the memory,
while this is no longer done for large allocations, so the impact during
allocation is smaller.

> Or are there other obstacles for precise tracing?
>

It's mostly untyped allocations. For example delegate closures don't come with type information.

Another problem is precise scanning of the stack. There is no info generated by the compiler. It could be implemented similar to exception unwinding data, but would have to be more precise as a thread can get suspended by a GC at any instruction.

On Saturday, 14 November 2020 at 12:39:25 UTC, Rainer Schuetze wrote:
>
> On 12/11/2020 09:43, Ola Fosheim Grøstad wrote:
> These are not a problem with the current implementation, because precise scanning is not done by the pointer type, but the type used for the allocation. Pointer types don't contain enough information for polymorphic classes or pointers to fields of structs.

The docs says that one can allocate arrays of void pointers to emplace in, which makes the collector less precise though. If destuctors on structs arent called then it should be ok to only keep the struct field alive?

> It's mostly untyped allocations. For example delegate closures don't come with type information.

If the gc involves a modified compiler then this could change,

> Another problem is precise scanning of the stack. There is no info generated by the compiler. It could be implemented similar to exception unwinding data, but would have to be more precise as a thread can get suspended by a GC at any instruction.

Maybe the LLVM GC infrastucture can help? I haven't looked on the details, but that seems like a possibility.

On Sunday, 15 November 2020 at 05:38:07 UTC, Ola Fosheim Grøstad wrote:
> ...
>
> Maybe the LLVM GC infrastucture can help? I haven't looked on the details, but that seems like a possibility.

Probably not, as it has hardly been properly battle tested.

There is no big project in the wild making use of it, as it isn't a proper GC, rather just the tooling to manipulate safe points and write barriers, everything else is up  to you to implement.

On Sunday, 15 November 2020 at 07:58:41 UTC, Paulo Pinto wrote:
> On Sunday, 15 November 2020 at 05:38:07 UTC, Ola Fosheim Grøstad wrote:
>> ...
>>
>> Maybe the LLVM GC infrastucture can help? I haven't looked on the details, but that seems like a possibility.
>
> Probably not, as it has hardly been properly battle tested.
>
> There is no big project in the wild making use of it, as it isn't a proper GC, rather just the tooling to manipulate safe points and write barriers, everything else is up  to you to implement.

Yes, which is reasonable. You want to write your own collector.

I just read the documentation, it seems to provide stack maps and x86 64 target.

On Sunday, 15 November 2020 at 07:58:41 UTC, Paulo Pinto wrote:
> On Sunday, 15 November 2020 at 05:38:07 UTC, Ola Fosheim Grøstad wrote:
>> ...
>>
>> Maybe the LLVM GC infrastucture can help? I haven't looked on the details, but that seems like a possibility.
>
> Probably not, as it has hardly been properly battle tested.
>
> There is no big project in the wild making use of it, as it isn't a proper GC, rather just the tooling to manipulate safe points and write barriers, everything else is up  to you to implement.

Yes, that it is what we want, the tools to write ones own GC. The LLVM documentation states that it has been used for a commercial Java compiler with a relocating collector.

LLVM does compute stack maps, which is what we want. D has interior pointers without base pointers not sure how that affects the various LLVM GC features.

https://llvm.org/docs/GarbageCollection.html#computing-stack-maps
https://llvm.org/docs/StackMaps.html#stackmap-section

On 15/11/2020 06:38, Ola Fosheim Grøstad wrote:
> On Saturday, 14 November 2020 at 12:39:25 UTC, Rainer Schuetze wrote:
>>
>> On 12/11/2020 09:43, Ola Fosheim Grøstad wrote:
>> These are not a problem with the current implementation, because
>> precise scanning is not done by the pointer type, but the type used
>> for the allocation. Pointer types don't contain enough information for
>> polymorphic classes or pointers to fields of structs.
> 
> The docs says that one can allocate arrays of void pointers to emplace in, which makes the collector less precise though.

That's where the mentioned gc_emplace() function can help, too.

> If destuctors on
> structs arent called then it should be ok to only keep the struct field
> alive?

It would disallow some patterns, for example intrinsic lists, with the node of a list being part of a larger struct, and the offset to the start of the struct is known.

> 
>> It's mostly untyped allocations. For example delegate closures don't come with type information.
> 
> If the gc involves a modified compiler then this could change,

Sure. The generated debug information already declares the closure as a struct.

> 
>> Another problem is precise scanning of the stack. There is no info generated by the compiler. It could be implemented similar to exception unwinding data, but would have to be more precise as a thread can get suspended by a GC at any instruction.
> 
> Maybe the LLVM GC infrastucture can help? I haven't looked on the details, but that seems like a possibility.

Indeed, that could work, although the "stack map" seems a bit too simple. It prevents some common optimizations, like having pointers only in registers, or reusing the same stack area in different scopes inside a function.

On Sunday, 15 November 2020 at 22:29:27 UTC, Rainer Schuetze wrote:
> Indeed, that could work, although the "stack map" seems a bit too simple. It prevents some common optimizations, like having pointers only in registers, or reusing the same stack area in different scopes inside a function.

My understanding is that LLVM use the term "stack map" for two different solutions. The old one is based on registering gc-roots "manually", but the newer one that is for patch-points (points where you can inject code at runtime) including register information. It does inhibit some optimizations as that point is assumed to write state, but the docs says that it can be marked as "read only", which should work out, I think? But it isn't trivial to make use of it and it will have some performance impact compared to manual allocations.

My personal opinion is that if one reduce collection to a single thread and also reduce the number of pointers, then one can get to a good place. One way to reduce scanned pointers would be to allow developers to also mark pointers as non-owning, and there are more tricks available...