5 ms·

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

by asah 4y ago

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 https://www.google.com/search?q=postgresql+memory+contexts

ajross 4y ago
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.
- asah 4y ago
  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.
  - naasking 4y ago
    Weird, I think the exact opposite, ie. malloc/free is terrible for beginners. Fine grained resource management is hard.
- nabla9 4y ago
  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.
- deleted 4y ago
  [deleted]
- karmakaze 4y ago
  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.html https://www.plover.com/~mjd/misc/hbaker-archive/CheneyMTA.ht...
  - pkulak 4y ago
    Sound like mark-and-sweep.
    - p_l 4y ago
      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.
pubby 4y ago
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.
- asah 4y ago
  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.
  - astrange 4y ago
    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.
chubot 4y ago
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.
- deleted 4y ago
  [deleted]
- josefx 4y ago
  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.
  - samus 4y ago
    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.
bluejekyll 4y ago
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.
- rwbt 4y ago
  Similarly, Apache Portable Runtime (APR) uses memory pools which is pretty effective.
throw0101c 4y ago
Tangent: the second link in the Google search is this PDF slideshow: * https://www.pgcon.org/2019/schedule/attachments/514_introduction-memory-contexts.pdf https://www.pgcon.org/2019/schedule/attachments/514_introduc... The 'bread crumb navigation' at the top of each slide is a clever idea.
RcouF1uZ4gsC 4y ago
> 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).

by asah 4y ago

ajross 4y ago

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.

asah 4y ago
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.
- naasking 4y ago
  Weird, I think the exact opposite, ie. malloc/free is terrible for beginners. Fine grained resource management is hard.
nabla9 4y ago
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.
deleted 4y ago
[deleted]
karmakaze 4y ago
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.html https://www.plover.com/~mjd/misc/hbaker-archive/CheneyMTA.ht...
- pkulak 4y ago
  Sound like mark-and-sweep.
  - p_l 4y ago
    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.

pubby 4y ago

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.

asah 4y ago
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.
- astrange 4y ago
  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.

chubot 4y ago

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.

deleted 4y ago
[deleted]
josefx 4y ago
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.
- samus 4y ago
  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.

bluejekyll 4y ago

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.

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

throw0101c 4y ago

Tangent: the second link in the Google search is this PDF slideshow: * https://www.pgcon.org/2019/schedule/attachments/514_introduction-memory-contexts.pdf https://www.pgcon.org/2019/schedule/attachments/514_introduc... The 'bread crumb navigation' at the top of each slide is a clever idea.

RcouF1uZ4gsC 4y ago

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