fun story: friend of mine was interviewing at Microsoft Research in the early 90s and too many interviewers kept asking him to design a GC. Finally, he decided to go for it and sketched out the Boehm-Weiser GC on the whiteboard, to the dumbfounded look of the interviewer.
"ok, but you didn't implement free() - how does that work?"
"oh, free is a NOOP"
He got the job.
---
Also, another fun fact: in spite of being written in old school C, PostgreSQL uses automatic memory management in most of its code by using "memory contexts" and users rarely experience leaks. https://www.google.com/search?q=postgresql+memory+contexts
Many server architectures work like that, I know apache did/does. When you know you're working in a short term request it's an obvious optimization to allocate from a "grows only" bucket that you then throw in the trash at the end of the request.
In fact, I think the truth is rather the converse. Users of "modern" frameworks and managed runtimes think of the heap as a unitary thing, provided by the runtime, with complicated rules and individual blocks being individually managed. "Old school C" was, in fact, a lot less constrained and a lot more willing to engage in novel paradigms. See the emacs first-stage elisp dump for another famous example of C programs breaking rules about how heaps are supposed to work.
CHICKEN Scheme uses the stack as heap which "grows only" in continuation-passing style (CPS). When it hits the limit, only the live heap parts are copied to the new stack.
this is an interesting point, i.e. malloc/free is perhaps one of those things that's great for getting started, but something you replace when going to scale and production.
Hm I don't get the joke -- the whole point of the GC is to avoid free()? Did the interviewer think someone who could implement a GC wouldn't understand that?
There are some GCs where you can free() if you like -- IIRC Boehm GC is one of them -- but it has to be designed for that.
Manually calling free sounds like an optimization, especially in a language that does not tag pointer values and as result would leak allocations all over the place.
There's another problem: this kind of GC doesn't know much about the memory layout of the objects it manages, but only the addresses. When it finds a byte pattern in memory that looks like it belongs to the objects it manages, it has to assume they are live. Sprinkling in `free()` whenever it can be judged to be safe helps to minimize this issue.
Unless you’re using an extension, Postgres uses a process per connection model, which means that most of the memory is freed when the connection closes. I’m not saying that the memory contexts do or do not have memory leaks, but the process model will mask any issues pretty effectively.
if you point to the code snippet, I can look further - but in the very original design the whole point is that free() doesn't need to be called, which is the point of automatic memory management (of which GC is an example). I'm assuming in optimized implementation, if the user calls free() explicitly there can be performance optimizations but again these calls must be optional and therefore it is legal to make the free() into a NOOP.
Since Boehm is a conservative GC, it sometimes won't be able to free things because it can't eliminate every false positive. So I guess you might want to free some things sometimes.
Although I don't see many situations where this would happen reliably so that you'd know when it's needed.
> Also, another fun fact: in spite of being written in old school C, PostgreSQL uses automatic memory management in most of its code by using "memory contexts" and users rarely experience leaks.
This seems more like arenas than garbage collection. Arenas are used fairly extensively in high performance C and C++ code (for example in games).
I have a cherished (really) old piece of code, the APL\11 interpreter, originally written by Ken Thompson. It has gone through several incarnations. My version is at git@github.com:gregfjohnson/aplette. I did a rewrite to make it work with 64-bit CPU's and compilers. It leaks memory like a sieve. There was some logic for memory management and garbage collection in the original code, but that has ended up broken over the course of multiple rewrites by multiple people. I'm thinking of integrating Boehm-Demers-Weiser to deal with the memory leak issues. Coincidentally, I had the honor of being acquainted with two of the three authors, Alan Demers and Mark Weiser.
A pretty naive question: what is the advantage of garbage collection over just reference counting?
It seems one benefit is handling circular references, but every time I've had that in Java or Python it's been a bug that at best leads to strange behavior.
Another seems to be that you can delay freeing up memory, but you could do that with reference counting.
Handling circular references is pretty important! Things like closing over an environment in a scripting language usually creates a cyclic reference, for example (stack frame contains a closure, which contains a reference to...the parent stack frame), or any graph-like data structures.
There is also just a cost to maintaining reference counts, which may be expensive if you are cloning and dropping values very often. A garbage collector can mean that cloning or destroying a reference has zero cost instead, along with batching destructors like you mentioned.
I'd also like to point out that technically reference counting is a garbage collection scheme! You can even use a cycle collector that runs occasionally over reference counted objects in order to free unreachable cycles; Python for example does this!
in ur-scheme i put the variables that are captured by closures into heap-allocated cells; both the original stack frame and the closures contain pointers to these cells, eliminating the circular references, but adding an additional indirection step to accessing those variables
theoretically this gives you more precise garbage collection, but it does give the collector more allocations to worry about
it also allows you to use a traditional stack for your stack, rather than a bunch of heap-allocated things, and that's probably a win
1. Reference counting scales with number of dead objects while Mark+Sweep typically scales with number of alive objects. This means that if you collect infrequently enough, a GC will have strictly less work to do.
2. RC involves a write whenever the reference count is increased. This means that in multi threaded contexts you need an atomic whenever a new reference is added. This will absolutely destroy performance in multi-threaded apps (this is the main reason why multi-threading in python doesn't exist).
3. RC requires a fairly high amount of metadata (often 32-64 bits per object). Mark sweep on the other hand often only needs a few (e.g. 2) bits per object. This is pretty heavy, especially for languages where everything is an object.
Do you have any links to Python Atomic RC? I don’t know much about it, but I’d heard that it was the global interpreter lock that prevented multi-threading.
I’d be surprised if the overhead of Atomic RC was that much, since it is a common pattern in Rust.
python doesn't have atomic rc. the gil prevents multithreading because experiments into removing the gil and replacing it with atomic reference counting had too high a performance overhead (roughly 2x for single threaded code). this is less of a problem for rust for 2 reasons: ARC is opt in and it's only used for a small fraction of objects, and compilers can do some fancy tricks and delete pairs of increments and decrements if it can prove that they don't cause corruption.
Circular references is a big one. There are also performance advantages though. Reference counting turns operations that would normally be just a memory read into a read+write, because of the need to update reference counts. You also need more bookkeeping space: a garbage collector only needs a bit or two per object, while a reference count needs several bits (up to a full word in the worst case).
There is a great discussion of the trade-offs in this podcast episode with Stephen Dolan, who works on Ocaml. Link to the start of the relevant section in the transcript: https://signalsandthreads.com/memory-management/#000752
I will start with a small nitpick: ref counting is a GC algorithm.
The answer: tracing GCs have that much better throughput. This is partly due to having to use atomic increments/decrements in multithread environments, which will absolutely kill performance (flush caches, force synchronizations, etc). Another reason which is true even of single-threaded RC is that the work has to be done “on the spot”. Clever compiler tricks can optimize some of it away, but tracing GCs amortize the costs very well (at the cost of more memory usage, there is no free lunch) — if they are moving GCs they can basically use thread-local allocation buffers where allocation can be as cheap as like 4 instructions, and later moving the still used ones out to a different region, and deallocation can be as simple as a flag toggle, now a different region is considered as the used space, the whole of the former one can be considered garbage. Add to it that many parts of this can be made parallel, modern state-of-the-art tracing GCs are really really hard to beat in complex programs.
Also, circular references are extremely common in complex programs, that in itself is a huge reason to have at least some hybrid solution (like python).
Another is amortization of bookkeeping: reference counting must be managed every time you record or remove a pointer while the GC does the tracing. So depending on your usage one may be faster than the other.
Another is the opportunity to do the GC on another thread (careful!), or just when you have nothing else to do, meaning your hot path can be faster.
Plus the very important case of circular or doubly linked structures that you mentioned.
GCs can be integrated with allocators to give you memory management. GCs can (not all do) 'move' live objects to compact memory giving better locality and thus performance. GC is applied by runtime and is systemic. If runtime is bug free so are the memory management bits of your code. Less code also reduces probability of bugs and lack of explicit memory management naturally reduces lines of code.
I think the reasonable questions are along the lines of 'when is it not a good idea to use a GC?'. Things like performance, restrictions its places on languages, explicit memory management, and also restrictions on what you can do in your code. The Boehm GC here, for example, has a limited sense of what are 'references' -- it only knows pointers -- so any kind of object composition scheme that is not based on pointers (or mushes pointers like XOR linked list) is seen as 'data' by the GC and could cause bugs.
A reference counting implementation traces garbage, and has operations on every pointer deletion. A GC traces only live objects, and never operates on a deletion of a pointer. That can make it much more efficient for programs with much allocation and pointer manipulation.
The latency of malloc is nothing compared to latency of even the best low-pause tracing GCs. Several orders of magnitude difference. Malloc/free typically run in tens of nanoseconds. Low pause GCs tend to pause for milliseconds (and this is already considered a success).
Also the nature of pauses is different. A GC pauses everything. A malloc/free call only blocks the thread that called them. Threads that never allocate anything are never disturbed.
How many mallocs are run for a single GC pause though? You are comparing apples to oranges. GC runs on an almost human timescale, I wouldn’t be surprised if an “ordinary” app would have 1000x of mallocs for a full GC run.
Of course if you allocate arenas and reuse that cleverly you can beat any GC, but that’s far from obvious nowadays (e.g. I remember a reddit thread where naive Java beat naive Rust in some parsing to AST program (can’t find it currently). The reason was the speed of object allocation).
Yes, it is, but not without a cost. High throughput, no pauses, low memory overhead - pick two. However, stack-based allocation + statically inferred memory management + a tiny addition of reference counting only where needed (like in C++ or Rust) can easily get you all of those features in one program.
Why do you think that Java, JS and other high performance managed languages all use tracing GCs? They hover around 2x native performance with that. Out of major languages that try to be somewhat highish performance, only swift does ref counting, but that was more of a tradeoff for its lower memory usage which is important on mobile devices.
I always thought it was the extra bookkeeping at runtime that was the drawback. Think of some tight loop that’s passing an object around. Your runtime has to inc and dec an integer (or similar) on every touch. Plus, you’re adding to the size of every object. A generational GC may never even touch 90% of all objects, since they don’t make it out of the eden generation.
So you trade off some throughput for no pauses, which is why I imagine Apple prefers it.
EDIT: oh, and reference counting is a garbage collector, just a rather simple one.
> what is the advantage of garbage collection over just reference counting?
One day a student came to Moon and said, "I understand how to make a better garbage collector. We must keep a reference count of the pointers to each cons." Moon patiently told the student the following story:
"One day a student came to Moon and said, `I understand how to make a better garbage collector . . . '"
> A pretty naive question: what is the advantage of garbage collection over just reference counting?
It's not that naive, and the unpopular answer is "not much". A good modern GC, faced with a usage paradigm that it expects (this part is important!), is almost certainly going to be faster. It's indeed safe from circular reference leaks. Generational collectors can often compact memory better and have a smaller footprint for the same data.
Those are all real advantages. But they come at the cost of outrageous complexity and code footprint. A reference counter is probably more than an 80% solution for almost any reasonable application, and it's something college kids write in 15-20 lines in their intro course.
Practically, someone else writes the garbage collector, so the supposedly "outrageous" complexity isn't an actual issue. Also I wouldn't say the complexity is much different from any other issue writing a programming language.
That's true for the case of simple apps that use a single runtime. Lots and lots of work is done "in Java" or "in Go". Lots more, including most of the largest and most complicated[1] apps, require synthesis of lots of tools from lots of sources. Those apps need to work very hard to get their heaps to play nicely with each other, and the tuning required by modern collected runtimes tends to blow up in strange ways.
[1] And especially including the ones targetted by the Boehm collector in the linked github. Also apps for which Rust (which famously eschews a collected heap) tends to be proposed.
Reference counting also usually has lower peak memory and scans less memory so is friendlier when you have either battery power or swap, ie, any non-server use case.
Yes, but a world-stopping mark and sweep collector is pretty much a non-starter for anything non-trivial in the modern world with full heaps well into the gigabytes. You'd be talking about multiple seconds of delay.
Only as long as the program in question doesn't touch the pointer values in weird ways, like storing metadata in otherwise unused bits or storing the pointers encoded as json values in some kind of global registry structure.
Which GCs, if any, are appropriate for realtime work (soft or hard)?
A lot of lisps use BDW or other Boehm variants, which I do not believe are capable. Clasp uses MPS which is supposed to have extremely low pause times -- soft realtime capable?
Java has ZGC which is supposed to have guaranteed sub-ms pause times IIRC, so that should be realtime capable.
There are Java real time runtimes being sold for about 20 year now.
PTC and Aicas are the surviving companies on this domain.
Aonix, which was acquired by PTC, famously sold Java real time systems for military systems like missile tracking radars and battleship weapon targeting control systems, a domain where you need split second decisions taking place.
The Treadmill collector was designed for realtime contexts (https://www.cofault.com/2022/07/treadmill.html is a very good explanation for it and how it works, but the paper itself is also very readable). Really any incremental GC can be used in a realtime context though, where you visit objects until you hit some time budget and then resume your interpreter.
Real-time just requires bounded pause times, but higher pause times necessarily excludes applications that require latencies below that threshold.
There are probably at least a dozen GC algorithms that provide sub-1ms pause times though, so very few applications wouldn't fit the latency requirements, as long as the other requirements are acceptable (typically higher memory use for forwarding pointers, copying, or delayed collection).
The Recycler GC is measured around 2ms on old hardware, so it's surely less now because IIRC that pause time is only to copy the stack to a buffer to scan in a separate thread:
The problem with maximum pause times is that it's not necessarily a feature of all realtime collectors, which try to do work incrementally and so don't necessarily introduce pauses in the same way as traditional tracing GCs. As you can see above, some of them quantify realtime behaviour in various ways so you can trade off memory use, CPU utilization and max latency.
But as mentioned, boundedness is the important property, hard real time systems are not really fast in any way or shape (e.g. for a modern chip to calculate a missile trajectory you really barely need any time, but it not replying in the necessary time window which may be like half a sec, because GC/JIT compiler/OS interrupt is a no-go).
And it works great with WebAssembly! I was pleasantly surprised to be able to use this mature GC to power garbage collection for Go when compiled to Wasm.
Does nanboxing affect the precision of the Boehm GC in any way? I can't see why it would but I've never tested it and I'm not familiar enough with the internals.
>Ubiquitous computing names the third wave in computing, just now beginning. First were mainframes, each shared by lots of people. Now we are in the personal computing era, person and machine staring uneasily at each other across the desktop. Next comes ubiquitous computing, or the age of calm technology, when technology recedes into the background of our lives. Alan Kay of Apple calls this "Third Paradigm" computing.
>One year earlier, in 1998, Mark Weiser described it a little differently, stating that, “Ubiquitous computing is roughly the opposite of virtual reality. Where virtual reality puts people inside a computer-generated world,” Weiser asserted, “ubiquitous computing forces the computer to live out here in the world with people.” This wasn’t the first time someone broached the idea of IoT. In the early 1980s, students at Carnegie Mellon’s Computer Science department created the first IoT Coke machine. Author Philip K. Dick wrote about the smart home in the 1969 sci-fi novel Ubik, and four decades before, inventor and engineer Nikola Tesla addressed the concept in Colliers Magazine. In an amazingly prescient 1926 interview, Tesla said,
>"When wireless is perfectly applied the whole earth will be converted into a huge brain…We shall be able to communicate with one another instantly, irrespective of distance…and the instruments through which we shall be able to do this will be amazingly simple compared with our present telephone. A man will be able to carry one in his vest pocket."
“Five cents, please,” his front door said when he tried to open it. One thing, anyhow, hadn’t changed. The toll door had an innate stubbornness to it; probably it would hold out after everything else. After everything except it had long since reverted, perhaps in the whole city … if not the whole world.
He paid the door a nickel, hurried down the hall to the moving ramp which he had used only minutes ago.
[…]
“I don’t have any more nickels,” G. G. said. “I can’t get out.”
Glancing at Joe, then at G. G., Pat said, “Have one of mine.” She tossed G. G. a coin, which he caught, an expression of bewilderment on his face. The bewilderment then, by degrees, changed to aggrieved sullenness.
“You sure shot me down,” he said as he deposited the nickel in the door’s slot. “Both of you,” he muttered as the door closed after him. “I discovered her. This is really a cutthroat business, when —“ His voice faded out as the door clamped shut. There was, then, silence.
[…]
“I’ll go get my test equipment from the car,” Joe said, starting towards the door.
“Five cents, please,”
“Pay the door,” Hoe said to G. G. Ashwood.
[...]
“Can I borrow a couple of poscreds from you?” Joe said. “So I can eat breakfast?”
“Mr. Hammond warned me that you would try to borrow money from me. He informed me that he already provided you with sufficient funds to pay for your hotel room, plus a round of drinks, as well as —“
“Al based his estimate on the assumption that I would rent a more modest room than this."
> No chapter in Understanding Media, later books, contains the idea that the global village and the electronic media create unified communities. In an interview with Gerald Stearn,[16] McLuhan says that it never occurred to him that uniformity and tranquility were the properties of the global village. McLuhan argued that the global village ensures maximal disagreement on all points because it creates more discontinuity and division and diversity under the increase of the village conditions; the global village is far more diverse.
DonHopkins 75 days ago | root | parent | prev | next [–]
You know what's a lot like Ada in a good way is Mesa, which evolved into Ceder, from Xerox PARC. I know people who really loved programming in it. They'd call it "Industrial Strength Pascal". It was a successful experiment in code reuse. A strongly typed language with strong separation between interfaces and implementations, which encouraged creating robust, hardened code.
>Mesa and Cedar had a major influence on the design of other important languages, such as Modula-2 and Java, and was an important vehicle for the development and dissemination of the fundamentals of GUIs, networked environments, and the other advances Xerox contributed to the field of computer science.
Demonstration of the Xerox PARC Cedar integrated environment (2019) [video] (youtube.com)
Mark Weiser and others at Xerox PARC's ported the Cedar environment to Unix, which resulted in the development of the still-widely-used Boehm–Demers–Weiser conservative garbage collection.
I believe that stuff is the port of Cedar to the Sun. Xerox PARC developed "Portable Common Runtime", which was basically the Cedar operating system runtime, on top of SunOS (1987 era SunOS, not Solaris, so no shared libraries or threads, which PCR had to provide). He demonstrates compiling a "Hello World" Cedar shell command, and (magically behind the scenes) dynamically linking it into the running shell and invoking it.
Experiences Creating a Portable Cedar.
Russ Atkinson, Alan Demers, Carl Hauser, Christian Jacobi, Peter Kessler, and Mark Weiser.
>Abstract: Cedar is the name for both a language and an environment in use in the Computer Science Laboratory at Xerox PARC since 1980. The Cedar language is a superset of Mesa, the major additions being garbage collection and runtime types. Neither the language nor the environment was originally intended to be portable, and for many years ran only on D-machines at PARC and a few other locations in Xerox. We recently re-implemented the language to make it portable across many different architectures. Our strategy was, first, to use machine dependent C code as an intermediate language, second, to create a language-independent layer known as the Portable Common Runtime, and third, to write a relatively large amount of Cedar-specific runtime code in a subset of Cedar itself. By treating C as an intermediate code we are able to achieve reasonably fast compilation, very good eventual machine code, and all with relatively small programmer effort. Because Cedar is a much richer language than C, there were numerous issues to resolve in performing an efficient translation and in providing reasonable debugging. These strategies will be of use to many other porters of high-level languages who may wish to use C as an assembler language without giving up either ease of debugging or high performance. We present a brief description of the Cedar language, our portability strategy for the compiler and runtime, our manner of making connections to other languages and the Unix operating system, and some measures of the performance of our "Portable Cedar".
PCR implemented threads in user space as virtual lightweight processes on SunOS by running several heavy weight Unix processes memory mapping the same main memory. And it also supported garbage collection. Mark Weiser worked on both PCR and the Boehm–Demers–Weiser garbage collector.
>Similarly, we treat any data inside the objects as potential pointers, to be followed if they, in turn, point to valid data objects. A similar approach, but restricted to procedure frames, was used in the Xerox Cedar programming environment [19].
[19] Rovner, Paul, ‘‘On Adding Garbage Collection and Runtime Types to a Strongly-Typed, Statically Checked, Concurrent Language’’, Report CSL-84-7, Xerox Palo Alto Research Center.
My guess is that the BDW garbage collector had its roots in PCR (pun intended, in fact this entire message was just an elaborate setup ;), but I don't know for sure the exact relationship between Cedar's garbage collector, PCR's garbage collector (which is specifically for Cedar code), and the Boehm–Demers–Weiser garbage collector (which is for general C code). Does anybody know how they influenced each other, shared code, or are otherwise related? Maybe there's a circular dependency!
This says “developed after the Star“ but imho the Dandelion (marketed as the star) was too slow for this environment and you needed one of the bigger machines (Dolphin or Dorado). Actually it’s kind of amazing to realize that two years later youncould get a small Mac for about a fifth the price that sat on your desk (not rolled next to it on casters) and was much more responsive. Did less, but what it did it did well, and was all that most people needed.
In addition to the Smalltalk and Mesa environments mentioned in the post, there was the Interlisp-D environment too, which got much more use outside thanks to being used outside PARC.
pjmlp on Sept 13, 2020 | parent | next [–]
The Computer History Museum organized a session with Eric Bier, and several other folks demoing the Mesa/Cedar environment.
The only modern environments that seem to have kept alive several of these ideas are Windows/.NET/COM, the ones designed by Apple/NeXT and to certain extent Android (although with a messed up execution).
Even Linux could grasp many of these ideas, if D-BUS would be properly taken advantage of and settled on a specific development experience.
Somehow it looks like we are still missing so much from Xerox PARC ideas.
----
The Cedar Programming Environment: A Midterm Report and Examination
Describes Portable Common Runtime (PCR), and the PostScript and Interpress decomposers implemented in Cedar, and includes many other interesting document about Cedar.
"ok, but you didn't implement free() - how does that work?"
"oh, free is a NOOP"
He got the job.
---
Also, another fun fact: in spite of being written in old school C, PostgreSQL uses automatic memory management in most of its code by using "memory contexts" and users rarely experience leaks. https://www.google.com/search?q=postgresql+memory+contexts