Hacker News Reader

Comment by asah | Hacker News Reader

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

View on HN

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.

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.

Weird, I think the exact opposite, ie. malloc/free is terrible for beginners. Fine grained resource management is hard.

It's also classic game programming method.

Just start a new process between every room, level, and so on. Let the OS do the memory management.

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.

[0] https://www.plover.com/~mjd/misc/hbaker-archive/CheneyMTA.ht...

Sound like mark-and-sweep.

it's a variation of two-space copying GC, not mark-and-sweep - aka "Cheney GC".

The specific variant ("Cheney on the MTA") is about using stack and CPS to implement it.

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.

Similarly, Apache Portable Runtime (APR) uses memory pools which is pretty effective.

I'm kinda confused about what you said regarding free(). The linked Github page has a free(), but it doesn't appear to be a NOOP.

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.

Tangent: the second link in the Google search is this PDF slideshow:

* https://www.pgcon.org/2019/schedule/attachments/514_introduc...

The 'bread crumb navigation' at the top of each slide is a clever idea.

> 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).

Reply on news.ycombinator.com