4 ms·
It depends on the implementation. In traditional ARC implementations these are all issues to a degree, but even then they tend toward much lower overhead with m
by elcritch 5y ago
It depends on the implementation. In traditional ARC implementations these are all issues to a degree, but even then they tend toward much lower overhead with more predictable behavior. Though I agree tracing GCs can be really fast and better in many ways.
1. I'm guessing you mean lock based implementations? There's several non lock, non atomics based ARC designs that still handle threading safely. That means it's little more than a single integer operation.
2. True, but for many contexts this is easy to do and makes it easier to understand data flows. In other cases it's possible to use index based references pretty readily, like in Rust. Or add a cycle collector.
3. In theory you can't, but in practice it's often pretty easy to tell. At least in non-oop languages. I use Nim with its ARC (1) on RTOS and this is really only a concern for large lists or large dynamic structures. It can be managed using the same patterns as RAII where you call child functions who know they won't be the last ones holding the bag. Also you can use the same trick as some Rust code does where you pass the memory to another thread to dispose of (2).
4/5. It depends on the implementation, but you can use pools or arenas or other options. Nim provides an allocator algorithm (tlsf) with proven O(1) times and known fragmentation properties (3). Still tracing gcs can make better usage of short lifetime arenas true. Though with ARC you get similar benefits using stack based objects.
6. It's tradeoffs. Tracing gcs also end up needing to scan the entire heap every so often. ARC's only need to check a root object during usage and only access the entire graph when de-allocating.
Your last point isn't accurate, as you can use an appropriately designed ARC in a hard realtime context. I've found it quite easy to do, but granted it takes a little bit of care, but any real time systems do. For items like interrupt handlers I ensure no memory is allocated or destroyed.
1) https://nim-lang.org/blog/2020/10/15/introduction-to-arc-orc-in-nim.html https://nim-lang.org/blog/2020/10/15/introduction-to-arc-orc...
2) https://abramov.io/rust-dropping-things-in-another-thread https://abramov.io/rust-dropping-things-in-another-thread
3) http://www.gii.upv.es/tlsf/ http://www.gii.upv.es/tlsf/
- m0zg 5y ago> non lock, non atomics based ARC designs that still handle threading safely Don't think that's even doable at all, at least not portably. Do you have some examples?
- elcritch 5y agoThere's a couple of methods like deferred counting, differential counting, or biased references. They're usually not completely atomic free but generally provide guaranteed constant overhead or tweak when or how the memory can be shared. - Nim's ARC only allows one thread to manage a reference count at a time, but enables an isolated graph of memory to be moved to another thread. The concept is called `Isolate`, and is very similar to Rust's single owner of mutable references. There's still WIP to have the compiler automate the checks, but it's usable now (I used it with FreeRTOS's xQueue mechanism just fine). https://github.com/nim-lang/RFCs/issues/244 https://github.com/nim-lang/RFCs/issues/244 - Python's new non-GIL proposal that does this using biased references: https://hackaday.com/2021/11/03/python-ditches-the-gils-and-comes-ashore/ https://hackaday.com/2021/11/03/python-ditches-the-gils-and-... - The source of Python's biased references: https://iacoma.cs.uiuc.edu/iacoma-papers/pact18.pdf https://iacoma.cs.uiuc.edu/iacoma-papers/pact18.pdf - Defered Reference counting: https://dl.acm.org/doi/pdf/10.1145/3453483.3454060 https://dl.acm.org/doi/pdf/10.1145/3453483.3454060 It's pretty cool stuff!
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- tsimionescu 5y agoI mostly agree with all of your points, and the core message - it's all tradeoffs. Just one nitpick though: > 6. It's tradeoffs. Tracing gcs also end up needing to scan the entire heap every so often. This is not accurate: tracing GCs always start from the roots and only ever visit live objects. By definition, the objects that they free are not reachable from anywhere. "Full scans" typically refer to various optimization strategies that tracing GCs implement to avoid scanning all roots (e.g. generations, per-thread scans) which do rely on still occasionally doing a full scan (scanning all live objects in all generations, or in all threads).
- elcritch 5y agoYah you’re right. I didn’t quite describe that correctly, but mostly I meant scanning the “live” objects of the heap.