- consider giving up on cycle-detection in the presence of concurrency and/or in the presence of pinned objects. Note that value types implies no references and hence no cycles, as does immutability (unless you can construct with cycles -- because if everything is immutable, then newer objects can only refer to older ones)
- look at on-the-fly/concurrent/incremental tricolor mark-sweep tracing GCs, and copying
- some examples to learn from include:
- https://github.com/robey/mwgc (incremental tricolor mark-sweep with write barrier)
- https://dl.acm.org/doi/pdf/10.1145/130854.130862 ("treadmill"; incremental tricolor mark-sweep with read barrier)
- the Micropython garbage collector
- i'm guessing it's here: https://github.com/micropython/micropython/blob/master/py/gc.c . See also https://docs.micropython.org/en/latest/develop/memorymgt.html
- Lua 5.1 (incremental tricolor mark-sweep; I don't know which barriers it has, if any) (this was not explicitly suggested by anyone but Lua came up in discussion so I looked up its GC and noticed it was incremental)
- https://users.cecs.anu.edu.au/~steveb/pubs/papers/lxr-pldi-2022.pdf (high perf RC with cycle detection; uses write barriers; suggested by https://news.ycombinator.com/item?id=32283091 )
- a list of special things that the implementation may need to do in order to permit garbage collection includes:
- produce a list of 'roots' of reference counting, eg the registers, stack, globals
- produce a list of the locations of any pointers within data, including in:
- the registers, stack, globals ("the roots")
- the heap
- read barriers and write barriers
- reference counting needs different barriers. Probably: create alias/reference; free alias/reference
- interrupt execution every now and then for GC
- override pointer comparisons (so that eg copying collectors can say that a fromspace pointer and a tospace pointer to the corresponding object are equivalent)
- derived pointers maybe shouldn't be stored, not even in registers, b/c moving GCs may move the base pointer, and hence invalidate all derived pointers.
- Instead, could use fat pointers that always store the base pointer next to an offset
- still can't do pointer subtraction though
- associate GC metadata (like color) with each pointer (can either be right next to, or in, the pointer (pointer tagging); or in an object header; or in a separate table of GC metadata)
- a way to 'pin' a pointer/object so that the GC wont move it
- might also want arenas and/or regions and/or slab allocation
- card marking/scanning can prevent ruining the caches via pointer following?
---
ok after reading that i figured i should lookup concurrent tricolor garbage collectors. I googled for concurrent incremental tricolor barrier and found some interesting results. The most useful was probably this:
https://www.cs.tau.ac.il/~maon/teaching/2014-2015/seminar/seminar1415a.html
![[Home]](http://www.bayleshanks.com/cartoonbayle.png)
