7

Read-Copy-Update (RCU) is a technique for manual memory management that is growing ever more popular in the Linux kernel.

Is it possible to design a language and VM that uses RCU instead of a conventional garbage collector to reclaim unreachable memory?

J D
  • 48,105
  • 13
  • 171
  • 274
  • 2
    It's a mutual exclusion algorithm, not a memory recycler. Well, mostly, anyways. – Warren P Jul 02 '13 at 22:58
  • 1
    Well, all of the descriptions I've read state that you can free old data after at least one grace period so it seems related. – J D Jul 03 '13 at 07:03
  • 1
    Hmm. I can't see any way that having a # of active "viewers" of an RCU object differs in any significant way from any other Reference Counting implementation. So I would say, "RCU is not a garbage collector, but it does implement something similar to Refcounting itself", internally, however RCU is more a design pattern than a GC . So maybe, these are not the droids you're looking for, and the alternative to GC that you have been looking for is called ARC (Automatic Reference Counting), that is, refcounting where the compiler generates all add and release reference calls automatically for you. – Warren P Jul 03 '13 at 17:56
  • 1
    "differs in any significant way from any other Reference Counting implementation". The reference counting read barrier is hugely expensive (often a cache miss) whereas the RCU read barrier is very cheap (and can be free). That sounds like a potentially major benefit to me. – J D Jul 03 '13 at 19:51
  • Well I hope someone answers with (a) yes, there is or (b) no, it's unsuitable, and here's why, because I have no way of knowing if it's feasible outside kernel space where a global shared memory implementation is the norm, ie, where each process would have it's own shared memory RCU heap. I suspect that a handful of sites in the kernel handling a total object count around 5000 objects, versus a GC implementation scaled to billions of objects may not have much in common. – Warren P Jul 05 '13 at 11:18
  • @WarrenP: "Well I hope someone answers..." Five years and I am still waiting. – J D Jul 11 '18 at 21:49
  • I suspect this question is unanswerable, as it is far too broad, and probably should have been closed. Any question of the form "is it possible to design a language and its runtime/VM such that ...." is probably TOO broad for SO. I didn't answer "no they are not that similar in their characteristics, and RCU is not a gc algorithm, really", but that really is the only answer ya gonna get at this point. – Warren P Jul 17 '18 at 18:15
  • http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf talks about garbage collection (in narrower sense) on page `xxii`. – Dima Tisnek May 07 '19 at 05:30

1 Answers1

0

Is it possible: yes kinda, Linux kernel is a living example.

In the linux kernel, when RCU is used, garbage collection of the previous version of the data structure happens during schedule() because at that point it is known that all readers have completed.

Of course, Linux kernel does not have a garbage collector, and reclamation of unreachable memory is generally explicit and immediate. The RCU update is a special case, where reclamation is explicit but not immediate.

Is it possible for a general-purpose vm like Python of JavaScript: it will be hard.

  • RCU needs a garbage-collector
  • RCU is made for read-mostly workloads
  • RCU is made for short critical sections

RCU still needs a garbage collector; rather RCU working together with garbage collector avoids locking most of the time, that is when a read critical section completes without concurrent write.

Read-mostly workloads. Reference counting is particularly write-heavy, so much so that multithreaded Python VM has GIL to prevent concurrent refcount updates, because those would incur cache synchronisation penalty. Thus, some other technique of garbage collection is required.

Meanwhile a naive JavaScript implementation doesn't need synchronisation at all, as it's single-threaded (although it's possible to imagine a JavaScript implementation where garbage collection is offloaded to a separate thread).

The length of critical section in a dynamic language VM is particularly hard to predict, because of incessant indirection. For example, consider int(code.replace(" ", "")): int may be overloaded via __int__, .replace may be overloaded through a property, (...) may be overloaded via __call__. Each overload is Python code that could take arbitrarily long. Same applies to built-in data structures, where update (last statement) of c=1; d={c:42}; d[c]=43 could internally use RCU for something, except it must be very careful because c might just implement __hash__ which may take arbitrarily long.

I'm afraid I don't know enough about compiled languages and their VMs.

My gut feeling that novel, high-performance garbage collectors could indeed use RCU internally, and then perhaps expose RCU to the implementation of the built-in data structures. I think that OS may be required to provide better API to pin execution to specific cores to benefit from local cache and/or to run custom code when user-land is preempted.

While this is not a full answer, I hope this extended commentary helps to circumscribe the original question.

Dima Tisnek
  • 11,241
  • 4
  • 68
  • 120