digitalmars.D - How to get to 100% precise tracing GC?
- Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (16/16) Nov 12 2020 What restrictions have to be made to make the GC 100% precise?
- Kagamin (2/2) Nov 13 2020 Also pointer-integer casts, some callback interfaces allow to
- Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (2/4) Nov 13 2020 But they will not be owning pointers as integers, I guess?
- Rainer Schuetze (18/33) Nov 14 2020 These are not a problem with the current implementation, because precise
- Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (9/21) Nov 14 2020 The docs says that one can allocate arrays of void pointers to
- Paulo Pinto (6/9) Nov 14 2020 Probably not, as it has hardly been properly battle tested.
- Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (4/15) Nov 15 2020 Yes, which is reasonable. You want to write your own collector.
- Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (9/20) Nov 15 2020 Yes, that it is what we want, the tools to write ones own GC. The
- Rainer Schuetze (11/37) Nov 15 2020 It would disallow some patterns, for example intrinsic lists, with the
- Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (16/20) Nov 15 2020 My understanding is that LLVM use the term "stack map" for two
- Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (13/16) Nov 15 2020 Yes, but after som thought, is it unreasonable to require owning
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.
Nov 12 2020
Also pointer-integer casts, some callback interfaces allow to supply user data in the form of pointer or integer.
Nov 13 2020
Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= <ola.fosheim.grostad gmail.com> 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?
Nov 13 2020
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.
Nov 14 2020
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.
Nov 14 2020
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.
Nov 14 2020
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: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.... 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.
Nov 15 2020
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: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... 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.
Nov 15 2020
On 15/11/2020 06:38, Ola Fosheim Grøstad wrote:On Saturday, 14 November 2020 at 12:39:25 UTC, Rainer Schuetze wrote:That's where the mentioned gc_emplace() function can help, too.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 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.Sure. The generated debug information already declares the closure as a struct.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,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.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.
Nov 15 2020
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...
Nov 15 2020
On Sunday, 15 November 2020 at 22:29:27 UTC, Rainer Schuetze wrote: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.Yes, but after som thought, is it unreasonable to require owning GC pointers to be free of pointer arithmetic? Developers could mark such listpointers as nonowning, then they would not have to be scanned. Btw, gc_emplace is clearly better than the current approach, but I think about using just the vtable pointer address for class id, or to embed a class id in each object. If we have 100% accurate tracing then it is possible to let the compiler generate code for the whole collection cycle (and the allocator). One could even profile pointer and allocation statistics and use that for code gen optimizations.
Nov 15 2020