8 ms·

Boehm-Demers-Weiser Garbage Collector

96 points by eternalban 4y ago

tomcam 4y ago
Interestingly, the name of the algorithm alone takes up more memory than the executable code. /s
- gumby 4y ago
  It started out as just the Boehm collector but grew. And I'm always glad to see Weiser's name: he was a great guy, and quite creative.
  - DonHopkins 4y ago
    https://news.ycombinator.com/item?id=17353666 https://news.ycombinator.com/item?id=17353666 DonHopkins on June 20, 2018 | prev | next [–] Mark Weiser once told me that Ubik was one of his inspirations for Ubiquitous Computing. https://web.archive.org/web/20050204163428/http://www.ubiq.com/hypertext/weiser/UbiHome.html https://web.archive.org/web/20050204163428/http://www.ubiq.c... >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. https://blog.canary.is/from-tesla-to-touchscreens-the-journey-of-the-internet-of-things/ https://blog.canary.is/from-tesla-to-touchscreens-the-journe... >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." https://en.wikipedia.org/wiki/Ubik https://en.wikipedia.org/wiki/Ubik https://arounddate.com/philip-k-dick-ubik https://arounddate.com/philip-k-dick-ubik “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."
    - throw0101c 4y ago
      Also Marshall McLuhan (with references to earlier works, like Sapir 1933): * https://en.wikipedia.org/wiki/Global_village https://en.wikipedia.org/wiki/Global_village Also this sounds prescient: > 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. * Ibid
    - gumby 4y ago
      Sadly the world moved in a different direction from Mark's prediction "calm technology". I go to some effort to make my environment calm.
anuraaga 4y ago
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. https://github.com/wasilibs/nottinygc https://github.com/wasilibs/nottinygc
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.
mindvirus 4y ago
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.
- chc4 4y ago
  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!
  - kragen 4y ago
    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
- pkd 4y ago
  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 https://signalsandthreads.com/memory-management/#000752
sigstoat 4y ago
hot tip: ld_preload’ing it when running something that leaks memory or erroneously frees memory still in use can fix the problem. (obviously best to just fix the code if you have it.)
- josefx 4y ago
  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.
gregfjohnson 4y ago
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.
- justinclift 4y ago
  An easier to click link: https://github.com/gregfjohnson/aplette https://github.com/gregfjohnson/aplette
- ithkuil 4y ago
  Wrong Ken perhaps? Wasn't APL written by Iverson?
Blackthorn 4y ago
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.
- oakwhiz 4y ago
  From a certain perspective, isn't it more important that pause times be known ahead of time rather than how long they might be?
  - naasking 4y ago
    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).
    - Blackthorn 4y ago
      > There are probably at least a dozen GC algorithms that provide sub-1ms pause times though I'd be interested to know more about which ones provide this guarantee. This has been surprisingly difficult to Google for.
      - pebal 4y ago
        SGCL is a real-time garbage collector for C++ without any pauses. https://github.com/pebal/sgcl https://github.com/pebal/sgcl
      - kaba0 4y ago
        https://news.ycombinator.com/item?id=35027935 https://news.ycombinator.com/item?id=35027935 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).
DonHopkins 4y ago
https://news.ycombinator.com/item?id=34056973 https://news.ycombinator.com/item?id=34056973 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. https://en.wikipedia.org/wiki/Mesa_(programming_language) https://en.wikipedia.org/wiki/Mesa_(programming_language) >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) https://news.ycombinator.com/item?id=22375449 https://news.ycombinator.com/item?id=22375449 Computer History Museum: Eric Bier Demonstrates Cedar https://www.youtube.com/watch?v=z_dt7NG38V4 https://www.youtube.com/watch?v=z_dt7NG38V4 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. https://news.ycombinator.com/item?id=22378457 https://news.ycombinator.com/item?id=22378457 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. CSL-89-8 June 1989 [P89-00DD6] http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-89-8_Experiences_Creating_a_Portable_Cedar.pdf http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-89-8... >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. https://en.wikipedia.org/wiki/Boehm_garbage_collector https://en.wikipedia.org/wiki/Boehm_garbage_collector This is the 1988 "Garbage Collection in an Uncooperative Environment" paper by Hans-Juergen Boehm and Mark Weiser: https://hboehm.info/spe_gc_paper/preprint.pdf https://hboehm.info/spe_gc_paper/preprint.pdf >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. http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-84-7_On_Adding_Garbage_Collection_and_Runtime_Types_to_a_Strongly-Typed_Statically-Checked_Concurrent_Language.pdf http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-84-7... 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! https://news.ycombinator.com/item?id=24450970 https://news.ycombinator.com/item?id=24450970 Xerox Cedar “Viewers Window Package” (2018) (toastytech.com) http://toastytech.com/guis/cedar.html http://toastytech.com/guis/cedar.html gumby on Sept 13, 2020 | next [–] 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. https://youtu.be/z_dt7NG38V4 https://youtu.be/z_dt7NG38V4 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 http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-83-11_The_Cedar_Programming_Environment_A_Midterm_Report_and_Examination.pdf http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-83-1... C - Cedar/Mesa Interoperability http://www.bitsavers.org/pdf/xerox/parc/cedar/C_-_Cedar_Mesa_Interoperability_Aug1992.pdf http://www.bitsavers.org/pdf/xerox/parc/cedar/C_-_Cedar_Mesa... Describes Portable Common Runtime (PCR), and the PostScript and Interpress decomposers implemented in Cedar, and includes many other interesting document about Cedar.
naasking 4y ago
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.

96 points by eternalban 4y ago

tomcam 4y ago

Interestingly, the name of the algorithm alone takes up more memory than the executable code. /s

gumby 4y ago
It started out as just the Boehm collector but grew. And I'm always glad to see Weiser's name: he was a great guy, and quite creative.
- DonHopkins 4y ago
  https://news.ycombinator.com/item?id=17353666 https://news.ycombinator.com/item?id=17353666 DonHopkins on June 20, 2018 | prev | next [–] Mark Weiser once told me that Ubik was one of his inspirations for Ubiquitous Computing. https://web.archive.org/web/20050204163428/http://www.ubiq.com/hypertext/weiser/UbiHome.html https://web.archive.org/web/20050204163428/http://www.ubiq.c... >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. https://blog.canary.is/from-tesla-to-touchscreens-the-journey-of-the-internet-of-things/ https://blog.canary.is/from-tesla-to-touchscreens-the-journe... >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." https://en.wikipedia.org/wiki/Ubik https://en.wikipedia.org/wiki/Ubik https://arounddate.com/philip-k-dick-ubik https://arounddate.com/philip-k-dick-ubik “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."
  - throw0101c 4y ago
    Also Marshall McLuhan (with references to earlier works, like Sapir 1933): * https://en.wikipedia.org/wiki/Global_village https://en.wikipedia.org/wiki/Global_village Also this sounds prescient: > 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. * Ibid
  - gumby 4y ago
    Sadly the world moved in a different direction from Mark's prediction "calm technology". I go to some effort to make my environment calm.

anuraaga 4y ago

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. https://github.com/wasilibs/nottinygc https://github.com/wasilibs/nottinygc

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.

mindvirus 4y ago

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.

chc4 4y ago
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!
- kragen 4y ago
  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
pkd 4y ago
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 https://signalsandthreads.com/memory-management/#000752

sigstoat 4y ago

hot tip: ld_preload’ing it when running something that leaks memory or erroneously frees memory still in use can fix the problem. (obviously best to just fix the code if you have it.)

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

gregfjohnson 4y ago

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.

justinclift 4y ago
An easier to click link: https://github.com/gregfjohnson/aplette https://github.com/gregfjohnson/aplette
ithkuil 4y ago
Wrong Ken perhaps? Wasn't APL written by Iverson?

Blackthorn 4y ago

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.

oakwhiz 4y ago
From a certain perspective, isn't it more important that pause times be known ahead of time rather than how long they might be?
- naasking 4y ago
  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).
  - Blackthorn 4y ago
    > There are probably at least a dozen GC algorithms that provide sub-1ms pause times though I'd be interested to know more about which ones provide this guarantee. This has been surprisingly difficult to Google for.
    - pebal 4y ago
      SGCL is a real-time garbage collector for C++ without any pauses. https://github.com/pebal/sgcl https://github.com/pebal/sgcl
    - kaba0 4y ago
      https://news.ycombinator.com/item?id=35027935 https://news.ycombinator.com/item?id=35027935 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).

DonHopkins 4y ago

https://news.ycombinator.com/item?id=34056973 https://news.ycombinator.com/item?id=34056973 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. https://en.wikipedia.org/wiki/Mesa_(programming_language) https://en.wikipedia.org/wiki/Mesa_(programming_language) >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) https://news.ycombinator.com/item?id=22375449 https://news.ycombinator.com/item?id=22375449 Computer History Museum: Eric Bier Demonstrates Cedar https://www.youtube.com/watch?v=z_dt7NG38V4 https://www.youtube.com/watch?v=z_dt7NG38V4 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. https://news.ycombinator.com/item?id=22378457 https://news.ycombinator.com/item?id=22378457 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. CSL-89-8 June 1989 [P89-00DD6] http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-89-8_Experiences_Creating_a_Portable_Cedar.pdf http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-89-8... >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. https://en.wikipedia.org/wiki/Boehm_garbage_collector https://en.wikipedia.org/wiki/Boehm_garbage_collector This is the 1988 "Garbage Collection in an Uncooperative Environment" paper by Hans-Juergen Boehm and Mark Weiser: https://hboehm.info/spe_gc_paper/preprint.pdf https://hboehm.info/spe_gc_paper/preprint.pdf >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. http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-84-7_On_Adding_Garbage_Collection_and_Runtime_Types_to_a_Strongly-Typed_Statically-Checked_Concurrent_Language.pdf http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-84-7... 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! https://news.ycombinator.com/item?id=24450970 https://news.ycombinator.com/item?id=24450970 Xerox Cedar “Viewers Window Package” (2018) (toastytech.com) http://toastytech.com/guis/cedar.html http://toastytech.com/guis/cedar.html gumby on Sept 13, 2020 | next [–] 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. https://youtu.be/z_dt7NG38V4 https://youtu.be/z_dt7NG38V4 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 http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-83-11_The_Cedar_Programming_Environment_A_Midterm_Report_and_Examination.pdf http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-83-1... C - Cedar/Mesa Interoperability http://www.bitsavers.org/pdf/xerox/parc/cedar/C_-_Cedar_Mesa_Interoperability_Aug1992.pdf http://www.bitsavers.org/pdf/xerox/parc/cedar/C_-_Cedar_Mesa... Describes Portable Common Runtime (PCR), and the PostScript and Interpress decomposers implemented in Cedar, and includes many other interesting document about Cedar.

naasking 4y ago

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.