<commit_before># **gcpp**: A GC heap allocation library for C++

<NAME> -- Updated 2016-09-01

## Overview, goals, and non-goals

The gcpp library is an experiment at adding tracing garbage collection as a library to the C++ toolbox. It provides a `gc_heap` type that encapsulates a bubble of memory containing objects accessed via `gc_ptr<T>`.

- _**gcpp is**_ opt-in, deterministic, accurate, type-safe including calling real destructors, scoped and composable including allowing multiple little separately collected `gc_heap`s, and adheres to C++'s zero-overhead abstraction principle (a.k.a. "you don't pay for what you don't use and you usually couldn't write it more efficiently by hand") -- space and time cost is always proportional to how much GC allocation your code performs, including zero cost if you never perform a GC allocation.

- _**gcpp is not yet**_ attempting to be scalable or production quality. There are still placeholder linear operations, and performance is awful beyond small numbers (1000s) of pointers. The goal for now is to try out a proof of concept to validate whether the general approach and interface are workable.

- _**gcpp will not ever**_ trace the whole C++ heap, incur uncontrollable or global GC pauses, add a "finalizer" concept, permit object "resurrection," be recommended as a default allocator, or replace `unique_ptr` and `shared_ptr` -- we are very happy with C++'s current lifetime model, and the aim here is only to add a fourth fallback when today's options are insufficient.

This project aims to continue C++'s long tradition of being a great language for building libraries, including specialized memory allocation libraries such as regions, arenas, pools, and allocators.


## Two target use cases

Gcpp aims to address two primary use cases. Initial work has also indicated a possible third use case to explore, but it is speculative.

### 1. gc_ptr for potentially-cyclic data structures

The first target use case is automatic by-construction memory management for data structures with cycles, which cannot be expressed with fully automated lifetime using C++17 facilities only.

- Encapsulated example: A `Graph` type whose `Node`s point to each other but should stay alive as long as they are transitively reachable from the enclosing `Graph` object or from some object such as a `Graph::iterator` that is handed out by the `Graph` object.

- Unencapsulated example: A group of objects of different types that refer to each other in a potentially-cyclic way but should stay alive as long as they are transitively reachable from some root outside their `gc_heap`.

- In C++17, both examples can be partly automated (e.g., having `Graph` contain a `vector<unique_ptr<Node>> my_nodes;` so that all nodes are guaranteed to be destroyed at least when the `Graph` is destroyed), but require at minimum manual liveness tracing today (e.g., traversal logic to discover unreachable `Node` objects, which essentially implements a tracing collection algorithm by hand for the nodes, and then `my_nodes.erase(unreachable_node);` to remove each unreachable node which is manual and morally equivalent to `delete unreachable_node;`).

### 2. atomic_gc_ptr for lock-free concurrent data structures (with or without cycles)

The second target use case is to support scalable and concurrent lock-free concurrent data structures that encounter ABA and deletion problems and cannot be written efficiently or at all in portable Standard C++ today. As a litmus test: If a lock-free library today resorts to [hazard pointers](https://en.wikipedia.org/wiki/Hazard_pointer) or transactional memory to solve [ABA and deletion problems](https://en.wikipedia.org/wiki/ABA_problem), it is probably a candidate for using `atomic_gc_ptr` instead.

- Acyclic example: A lock-free queue that supports both traversal and node deletion. (Note: C++17 `atomic_shared_ptr`, also written by me, also addresses this problem. But making it truly lock-free requires at least some additional complexity in the implementation; thanks to <NAME> for [contributing discussion and implementation experience with `atomic_shared_ptr`](https://www.justsoftwaresolutions.co.uk/threading/why-do-we-need-atomic_shared_ptr.html) including demonstrating a lock-free implementation in [Just::Thread v.2.2](http://www.stdthread.co.uk/). However, some experts still question its lock-free property.)

- Cyclic example: A lock-free graph that can contain cycles.

### (speculative) Possible bonus use case: gc_allocator for STL containers 

Finally, `gc_allocator` wraps up a `gc_heap` as an STL allocator. This was not an original use case, and is not a primary target at the moment, but it's an interesting case to explore because it might just fall out once a `gc_heap` abstraction is available and it may have some interesting properties that are useful for safer use of STL in domains where allowing iterator dereference errors to have undefined behavior is not tolerable.

- When using a `container<T, gc_allocator<T>>`, iterators can’t dangle (point to a destroyed or deallocated object) because iterators keep objects alive. This turns dereferencing an invalidated iterator from an undefined behavior problem into a stale data problem.

- See notes below for limitations on iterator navigation using invalidated iterators.

- Note: `gc_allocator` relies on C++11's allocator extensions to support "fancy" user-defined pointer types. It does not work with pre-C++11 standard libraries, which required `allocator::pointer` to be a raw pointer type. If you are using Microsoft Visual C++, the current implementation of gcpp requires Visual Studio 2015 Update 3 (or later); it does not work on Update 2 which did not yet have enough fancy pointer support.

### Other use cases

**Real time systems.** Using `shared_ptr` can be problematic in real time systems code, because any simple `shared_ptr` pointer assignment (or destruction) could cause an arbitrary number of objects to be destroyed, and therefore has unbounded cost; this is a rare example of where prompt destruction, usually a wonderful property, is actually bad for performance. (This is less of a problem with `unique_ptr` because `unique_ptr` assignment necessarily causes destruction and so tends to be treated more carefully, whereas `shared_ptr` assignment *might* cause destruction.)

Today, deadline-driven code must either avoid manipulating `shared_ptr`s or take defensive measures:

- Banning `shared_ptr` assignment or destruction entirely in deadline-driven code, such as by deferring the pointer assignment until after the end of the critical code region, is not always an option because the code may need to change which object a pointer refers to while still inside the critical region.

- Bounding the number of objects reachable from a `shared_ptr` can make the assignment cost have an upper bound to fit within the deadline, but requires ongoing care during maintenance. Adding an additional object, or changing the cost of a destructor, can exceed the bound.

- Deferring destruction by storing additional strong references in a separate "keepalive" data structure allows tracing to be performed later, outside the critical code region, to identify and destroy those objects no longer referred to from outside the keepalive structure. However, this amounts to another form of manually implemented liveness tracing.

By design, `gc_ptr` has trivial assignment which always has bounded cost suitable for use in a critical section (same as copying a raw pointer), and `gc_heap` gives full control over when and where `collect()` runs deferred destructors. This makes it a candidate for being appropriate for real-time code in situations where using `shared_ptr` is problematic.

## Object lifetime guidance: For C++17 and for the gcpp library

The following summarizes the best practices we should already teach for expressing object lifetimes in C++17, and at the end adds a potential new fallback option to consider gcpp.

| Guidance / library | What it automates | Efficiency | Clarity and correctness |
|--------------------|-------------------|------------|-------------------------|
| [C++17] **1. Where possible, prefer scoped lifetime** by default (e.g., locals, members) | Expressing that this object's lifetime is tied to some other lifetime that is already well defined, such as a block scope (`auto` storage duration) or another object (member lifetime) | Zero additional lifetime management overhead for this object | |
| [C++17] **2. Else prefer `make_unique` and `unique_ptr`**, if the object must have its own lifetime (i.e., heap) and ownership can be unique without ownership cycles | Single-ownership heap object lifetime | Usually identical cost as correctly written `new`+`delete` | Clearer and more robust than explicit `delete` (declarative, uses are correct by construction) |
| [C++17] **3. Else prefer `make_shared` and `shared_ptr`**, if the object must have its own lifetime (i.e., heap) and shared ownership, without ownership cycles | Acyclic shared heap object lifetime managed with reference counting | Usually identical cost as correctly written manual reference counting | Clearer and more robust than manual/custom reference count logic (declarative, uses are correct by construction) |
| [gcpp, experimental] **4. Else consider `gc_heap` and `gc_ptr`**, if the object must have its own lifetime (i.e., heap) and there can be ownership cycles | Potentially-cyclic shared heap object lifetime managed with liveness tracing<br><br>Lock-free concurrent data structures that perform general node deletion and/or have cycles | (conjecture) Usually identical cost as correctly written manual tracing | (conjecture) Clearer and more robust than manual/custom tracing logic (declarative, uses are correct by construction) |


# Implementation notes

## gc_heap and gc_ptr

`gc_heap` encapsulates memory containing objects that can be safely accessed via `gc_ptr<T>`.

- `collect()` is local: It traces only GC-allocated objects, and only this `gc_heap`.

- `collect()` is explicit: It runs only when called. There are opt-in automatic `collect()` options (TODO), such as on `allocate()` failure before allocating a new page.

- Note: The prototype collector is not intended to be scalable or production-quality. The prototype focuses on interface design, and uses a proof-of-concept collector. I invite GC experts to suggest/code their own GC implementations under this interface. However, even this prototype collector implementation was written with a view to avoiding unreasonable space overhead and time complexity

- `make<T>()` allocates and constructs a new `T` object and returns a `gc_ptr<T>`.

   - If `T` has a nontrivial destructor, the destructor is remembered and run during `.collect()` when the object has become unreachable. This is necessary to make using `gc_ptr` also type-safe, in addition to memory-safe.

   - The current collector implementation stores the following data:

      - Per individual nontrivially destructible object, stores two pointers: {T* obj, void (*dtor)(const void*)}.

      - Per array of nontrivially destructible objects, stores two pointers plus the number of objects: : {T* obj, size_t num, void (*dtor)(const void*)}.

      - Per type, usually stores one 1-instruction dtor wrapper: Clang -O1 generates a function containing just *jmp*, Clang -O2 inlines the destructor entirely where that’s usual.

`gc_ptr` refers to an object in a `gc_heap`.

- Additional rule: A `gc_ptr` member is null in a GC'd object’s destructor. This enables safe unordered destruction by enforcing known best practices in GC environments, in particular:

   - The destructor of a GC'd object runs normally, but cannot access another GC'd object possibly being destroyed in the same collection cycle (which might already have been destroyed). This eliminates the "accessing a disposed/finalized object" class of bugs that is possible in environments like Java, .NET, and Go, and eliminates the "leaking cycles of objects that use finalizers" class of bugs that is possible in Go.

   - It is not possible to "resurrect" another GC'd object by storing a `gc_ptr` to it somewhere that would make that object reachable again (and an object cannot make itself reachable again because it cannot form a `gc_ptr` to itself). This eliminates the "double dispose" class of bugs that is possible in environments like Java, .NET, and Go.
<commit_msg>Added region behavior note<commit_after># **gcpp**: A GC heap allocation library for C++

<NAME> -- Updated 2016-09-01

## Overview, goals, and non-goals

The gcpp library is an experiment at adding tracing garbage collection as a library to the C++ toolbox. It provides a `gc_heap` type that encapsulates a bubble of memory containing objects accessed via `gc_ptr<T>`.

- _**gcpp is**_ opt-in, deterministic, accurate, type-safe including calling real destructors, scoped and composable including allowing multiple little separately collected `gc_heap`s, and adheres to C++'s zero-overhead abstraction principle (a.k.a. "you don't pay for what you don't use and you usually couldn't write it more efficiently by hand") -- space and time cost is always proportional to how much GC allocation your code performs, including zero cost if you never perform a GC allocation.

- _**gcpp is not yet**_ attempting to be scalable or production quality. There are still placeholder linear operations, and performance is awful beyond small numbers (1000s) of pointers. The goal for now is to try out a proof of concept to validate whether the general approach and interface are workable.

- _**gcpp will not ever**_ trace the whole C++ heap, incur uncontrollable or global GC pauses, add a "finalizer" concept, permit object "resurrection," be recommended as a default allocator, or replace `unique_ptr` and `shared_ptr` -- we are very happy with C++'s current lifetime model, and the aim here is only to add a fourth fallback when today's options are insufficient.

This project aims to continue C++'s long tradition of being a great language for building libraries, including specialized memory allocation libraries such as regions, arenas, pools, and allocators.


## Two target use cases

Gcpp aims to address two primary use cases. Initial work has also indicated a possible third use case to explore, but it is speculative.

### 1. gc_ptr for potentially-cyclic data structures

The first target use case is automatic by-construction memory management for data structures with cycles, which cannot be expressed with fully automated lifetime using C++17 facilities only.

- Encapsulated example: A `Graph` type whose `Node`s point to each other but should stay alive as long as they are transitively reachable from the enclosing `Graph` object or from some object such as a `Graph::iterator` that is handed out by the `Graph` object.

- Unencapsulated example: A group of objects of different types that refer to each other in a potentially-cyclic way but should stay alive as long as they are transitively reachable from some root outside their `gc_heap`.

- In C++17, both examples can be partly automated (e.g., having `Graph` contain a `vector<unique_ptr<Node>> my_nodes;` so that all nodes are guaranteed to be destroyed at least when the `Graph` is destroyed), but require at minimum manual liveness tracing today (e.g., traversal logic to discover unreachable `Node` objects, which essentially implements a tracing collection algorithm by hand for the nodes, and then `my_nodes.erase(unreachable_node);` to remove each unreachable node which is manual and morally equivalent to `delete unreachable_node;`).

### 2. atomic_gc_ptr for lock-free concurrent data structures (with or without cycles)

The second target use case is to support scalable and concurrent lock-free concurrent data structures that encounter ABA and deletion problems and cannot be written efficiently or at all in portable Standard C++ today. As a litmus test: If a lock-free library today resorts to [hazard pointers](https://en.wikipedia.org/wiki/Hazard_pointer) or transactional memory to solve [ABA and deletion problems](https://en.wikipedia.org/wiki/ABA_problem), it is probably a candidate for using `atomic_gc_ptr` instead.

- Acyclic example: A lock-free queue that supports both traversal and node deletion. (Note: C++17 `atomic_shared_ptr`, also written by me, also addresses this problem. But making it truly lock-free requires at least some additional complexity in the implementation; thanks to <NAME> for [contributing discussion and implementation experience with `atomic_shared_ptr`](https://www.justsoftwaresolutions.co.uk/threading/why-do-we-need-atomic_shared_ptr.html) including demonstrating a lock-free implementation in [Just::Thread v.2.2](http://www.stdthread.co.uk/). However, some experts still question its lock-free property.)

- Cyclic example: A lock-free graph that can contain cycles.

### (speculative) Possible bonus use case: gc_allocator for STL containers 

Finally, `gc_allocator` wraps up a `gc_heap` as an STL allocator. This was not an original use case, and is not a primary target at the moment, but it's an interesting case to explore because it might just fall out once a `gc_heap` abstraction is available and it may have some interesting properties that are useful for safer use of STL in domains where allowing iterator dereference errors to have undefined behavior is not tolerable.

- When using a `container<T, gc_allocator<T>>`, iterators can’t dangle (point to a destroyed or deallocated object) because iterators keep objects alive. This turns dereferencing an invalidated iterator from an undefined behavior problem into a stale data problem.

- See notes below for limitations on iterator navigation using invalidated iterators.

- Note: `gc_allocator` relies on C++11's allocator extensions to support "fancy" user-defined pointer types. It does not work with pre-C++11 standard libraries, which required `allocator::pointer` to be a raw pointer type. If you are using Microsoft Visual C++, the current implementation of gcpp requires Visual Studio 2015 Update 3 (or later); it does not work on Update 2 which did not yet have enough fancy pointer support.

### Other use cases

**Real time systems.** Using `shared_ptr` can be problematic in real time systems code, because any simple `shared_ptr` pointer assignment (or destruction) could cause an arbitrary number of objects to be destroyed, and therefore has unbounded cost; this is a rare example of where prompt destruction, usually a wonderful property, is actually bad for performance. (This is less of a problem with `unique_ptr` because `unique_ptr` assignment necessarily causes destruction and so tends to be treated more carefully, whereas `shared_ptr` assignment *might* cause destruction.)

Today, deadline-driven code must either avoid manipulating `shared_ptr`s or take defensive measures:

- Banning `shared_ptr` assignment or destruction entirely in deadline-driven code, such as by deferring the pointer assignment until after the end of the critical code region, is not always an option because the code may need to change which object a pointer refers to while still inside the critical region.

- Bounding the number of objects reachable from a `shared_ptr` can make the assignment cost have an upper bound to fit within the deadline, but requires ongoing care during maintenance. Adding an additional object, or changing the cost of a destructor, can exceed the bound.

- Deferring destruction by storing additional strong references in a separate "keepalive" data structure allows tracing to be performed later, outside the critical code region, to identify and destroy those objects no longer referred to from outside the keepalive structure. However, this amounts to another form of manually implemented liveness tracing.

By design, `gc_ptr` has trivial assignment which always has bounded cost suitable for use in a critical section (same as copying a raw pointer), and `gc_heap` gives full control over when and where `collect()` runs deferred destructors. This makes it a candidate for being appropriate for real-time code in situations where using `shared_ptr` is problematic.

## Object lifetime guidance: For C++17 and for the gcpp library

The following summarizes the best practices we should already teach for expressing object lifetimes in C++17, and at the end adds a potential new fallback option to consider gcpp.

| Guidance / library | What it automates | Efficiency | Clarity and correctness |
|--------------------|-------------------|------------|-------------------------|
| [C++17] **1. Where possible, prefer scoped lifetime** by default (e.g., locals, members) | Expressing that this object's lifetime is tied to some other lifetime that is already well defined, such as a block scope (`auto` storage duration) or another object (member lifetime) | Zero additional lifetime management overhead for this object | |
| [C++17] **2. Else prefer `make_unique` and `unique_ptr`**, if the object must have its own lifetime (i.e., heap) and ownership can be unique without ownership cycles | Single-ownership heap object lifetime | Usually identical cost as correctly written `new`+`delete` | Clearer and more robust than explicit `delete` (declarative, uses are correct by construction) |
| [C++17] **3. Else prefer `make_shared` and `shared_ptr`**, if the object must have its own lifetime (i.e., heap) and shared ownership, without ownership cycles | Acyclic shared heap object lifetime managed with reference counting | Usually identical cost as correctly written manual reference counting | Clearer and more robust than manual/custom reference count logic (declarative, uses are correct by construction) |
| [gcpp, experimental] **4. Else consider `gc_heap` and `gc_ptr`**, if the object must have its own lifetime (i.e., heap) and there can be ownership cycles | Potentially-cyclic shared heap object lifetime managed with liveness tracing<br><br>Lock-free concurrent data structures that perform general node deletion and/or have cycles | (conjecture) Usually identical cost as correctly written manual tracing | (conjecture) Clearer and more robust than manual/custom tracing logic (declarative, uses are correct by construction) |


# Implementation notes

## gc_heap and gc_ptr

`gc_heap` encapsulates memory containing objects that can be safely accessed via `gc_ptr<T>`.

- `collect()` is local: It traces only GC-allocated objects, and only this `gc_heap`.

- `collect()` is explicit: It runs only when called. There are opt-in automatic `collect()` options (TODO), such as on `allocate()` failure before allocating a new page.

    - If you never call `collect()`, a `gc_heap` behaves like a [region](https://en.wikipedia.org/wiki/Region-based_memory_management) that deallocates all memory efficiently at once. Unlike most regions which just let go of the memory, it will first  run any pending destructors and only then efficiently just let go of the memory.

- Note: The prototype collector is not intended to be scalable or production-quality. The prototype focuses on interface design, and uses a proof-of-concept collector. I invite GC experts to suggest/code their own GC implementations under this interface. However, even this prototype collector implementation was written with a view to avoiding unreasonable space overhead and time complexity

- `make<T>()` allocates and constructs a new `T` object and returns a `gc_ptr<T>`.

   - If `T` has a nontrivial destructor, the destructor is remembered and run during `.collect()` when the object has become unreachable. This is necessary to make using `gc_ptr` also type-safe, in addition to memory-safe.

   - The current collector implementation stores the following data:

      - Per individual nontrivially destructible object, stores two pointers: {T* obj, void (*dtor)(const void*)}.

      - Per array of nontrivially destructible objects, stores two pointers plus the number of objects: : {T* obj, size_t num, void (*dtor)(const void*)}.

      - Per type, usually stores one 1-instruction dtor wrapper: Clang -O1 generates a function containing just *jmp*, Clang -O2 inlines the destructor entirely where that’s usual.

`gc_ptr` refers to an object in a `gc_heap`.

- Additional rule: A `gc_ptr` member is null in a GC'd object’s destructor. This enables safe unordered destruction by enforcing known best practices in GC environments, in particular:

   - The destructor of a GC'd object runs normally, but cannot access another GC'd object possibly being destroyed in the same collection cycle (which might already have been destroyed). This eliminates the "accessing a disposed/finalized object" class of bugs that is possible in environments like Java, .NET, and Go, and eliminates the "leaking cycles of objects that use finalizers" class of bugs that is possible in Go.

   - It is not possible to "resurrect" another GC'd object by storing a `gc_ptr` to it somewhere that would make that object reachable again (and an object cannot make itself reachable again because it cannot form a `gc_ptr` to itself). This eliminates the "double dispose" class of bugs that is possible in environments like Java, .NET, and Go.

{'fraction_non_alphanumeric': 0.06609774406384576, 'fraction_numerical': 0.0038718343803089564, 'mean_word_length': 4.737080689029918, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 27, 'https://': 7, 'lorem ipsum': 0, 'www.': 4, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '158354', 'n_tokens_mistral': 6198, 'n_tokens_neox': 5879, 'n_words': 3578}