14 ms·

Twitter post from Steve Blackburn (one of the authors) announcing the paper and providing a bit of context: https://twitter.com/stevemblackburn/status/151964115

Twitter post from Steve Blackburn (one of the authors) announcing the paper and providing a bit of context: https://twitter.com/stevemblackburn/status/1519641157621657600 https://twitter.com/stevemblackburn/status/15196411576216576... Haven't quite finished reading the paper yet, but it's interesting so far. While they present a method that could be applied more widely, this paper is only analyzing current tracing GCs in OpenJDK (plus Epsilon GC). Would love to see future papers taking other GCs into account (e.g., various flavors of refcount GC). Even better would be a way to compare vs methods of "manual" memory management (manual alloc/free, RAII/scope based alloc/free, arena allocation, etc.). Unfortunately, non-GC memory management is very application specific, so I'm not sure if a generalized analysis would be super useful.

gwbas1c 4y ago
> Even better would be a way to compare vs methods of "manual" memory management (manual alloc/free, RAII/scope based alloc/free, arena allocation, etc.). Unfortunately, non-GC memory management is very application specific, so I'm not sure if a generalized analysis would be super useful. I've personally found Rust to be a very difficult language to learn and become productive in. In contrast, I was able to jump into Swift and become productive very quickly. Swift isn't GC, but is reference counted. Reference cycles will lead to leaked memory. So what's interesting is to know GC's overhead relative to what: Reference counted languages like Swift? Or languages like Rust? More importantly: Is the overhead worth it? Developer time is valuable; thus leading to the critical question: What's cheaper, extra developer time or a more powerful computer?
- chrisseaton 4y ago
  > Swift isn't GC, but is reference counted GC is often an umbrella term that includes reference counting. Almost all serious tracing GCs include some aspect of reference counting, and almost all serious reference counting GCs include some aspect of tracing.
  - gwbas1c 4y ago
    No, it's not. Garbage collection and reference counting are "automatic memory management." With reference counting there are no pauses, and memory is reclaimed immediately. It allows for strongly coupling deallocation with resource cleanup. (The consequence is higher overhead maintaining counts, and leaked reference cycles.) In a garbage collected language you need to explicitly release your resources. (IE, the Dispose pattern that's common in C#)
    - Sindisil 4y ago
      [citation needed] Reference counting is widely considered one strategy of garbage collection (https://en.wikipedia.org/wiki/Garbage_collection_(computer_science) https://en.wikipedia.org/wiki/Garbage_collection_(computer_s...). For that matter, some GCs that are primarily tracing also use ref counts for some portion of the heap, as an optimization (just as some primarily refcounting GCs also run a trace to clean up cycles). Also, reference counting can certainly result in pauses, when large graphs of interconnected objects are reclaimed. On the upside, you know when a pause might happen. You still don't know for certain without explicitly keeping track of what is about to be freed, which would add additional overhead, and indeed may not be practical or even feasible.
    - wgd 4y ago
      > With reference counting there are no pauses, and memory is reclaimed immediately You can't guarantee both of these properties at once, in the general case. Consider a very large tree of objects which are referenced through a single root node, and then that root node becomes eligible for reclamation. For a sufficiently large object graph, either reclamation will require a noticeable pause or some portion of the work will have to be deferred until later.
      - ncmncm 4y ago
        In such uses, if it matters you don't rely on RC to reclaim the storage. You allocate from an arena, and drop the whole graph as a unit. Using pointers to make up a graph is a choice. It is a thing taught in CS classes, so it may feel comfortably familiar; that does not make it good. I never do.
- hedora 4y ago
  GC shifts human work from development time to deployment / ops time. So the question is whether one-off developer time is cheaper than SRE time for the useful lifetime of the service. However, it gets worse for GC: depending on the application, developing for a GC can be much more difficult / expensive than manual memory management (or reference counting). The canonical examples are low latency (with SLAs on the order of a disk or network I/O, so 10-100 microseconds) and applications that need to use bounded memory. On top of that, there are confounding factors that hurt the case for GC. I don't know of an imperarive GCed language with a reasonably expressive type system (all the JVM languages I know of use type erasure). For experienced developers, rich type systems with actual runtime guarantees are a huge productivity boost.
  - titzer 4y ago
    C#? F#? Go (now with generics)? Virgil...
  - gwbas1c 4y ago
    > The canonical examples are low latency (with SLAs on the order of a disk or network I/O, so 10-100 microseconds) and applications that need to use bounded memory. Well, in those cases extra developer time is cheaper than a more powerful computer! Will you get ROI building a stereotypical web application with manual memory management? Doubtful. Edit: > GC shifts human work from development time to deployment / ops time. I've never had to tune a garbage collector in deployment. I've heard of other people having to do it; but I've never heard of anyone saying, "yes, I'm so happy I built my website with C++."
    - Sindisil 4y ago
      All the world is not a web application.
      - Spivak 4y ago
        True but it’s not really about web and more about “problem domains where GC pauses are significant, matter, and you can’t throw more compute and memory at the problem” which is not nothing but on the dart board of all SWE jobs good money is on hitting one where it isn’t even if you’re aiming for one.
- Sindisil 4y ago
  Yes, both. Indeed, the fundamental question is whether the costs of automatic memory management (be it tracing GC or refcount GC) are "worth it". But it's not always as simple as a monetary consideration, and even when it is, the monetary cost often involves way more than just dev time vs cost of computer (e.g., power, cooling, distributed cost over many end users, market applicability because of system requirements).
- pjmlp 4y ago
  Reference counting is a GC algorithm as per any worthwhile CS book on GC algorithms.
- zozbot234 4y ago
  Rust can also use reference counting when necessary. Many Rust novices don't realize this, and run into needless trouble when trying to learn Rust. Rc<RefCell<T>> and Arc<Mutex<T>> are not "unidiomatic" other than in a very weak sense. Sometimes they are even unavoidable.
  - throwaway894345 4y ago
    It's still pretty painful to deal in Rc<...> and friends in Rust. I was expecting it to be a few extra keystrokes around my types, but I still ended up having to deal with the borrow checker when I would put something into an Rc or take it out to pass into some other function. It was nowhere near as easy as a GC or refcounted language.
    - woodruffw 4y ago
      > I was expecting it to be a few extra keystrokes around my types, but I still ended up having to deal with the borrow checker when I would put something into an Rc or take it out to pass into some other function. I'd be interested to hear where you experienced difficulty, specifically. `Rc<T>` is `Deref<T>`, so you should never have any problems calling borrowing APIs. Owning APIs require an explicit borrow-and-clone, but that's just two calls (`as_ref().clone()`).
  - gwbas1c 4y ago
    They're significantly more time-consuming, for the developer, to work with. Think of using something like a lambda to start a thread: You have to explicitly clone your Rc<Whatever> into another variable, and then use the second variable in your lambda. The compiler won't implicitly clone your RC<Whatever> for you. IMO, it's one of the biggest drawbacks in Rust.
- pkulak 4y ago
  Reference counting is GC. There are no pauses, but incrementing and decrementing a counter on every touch isn’t free either.
  - ygra 4y ago
    Well, the pauses are somewhat predictable in that they may appear when the count of an object reaches zero. I had a very expensive closing brace in (admittedly not well-written) C++ code once.
- sharpneli 4y ago
  One must also remember to differentiate the deployment targets. Not every piece of software is deployed in your own machine. Let's take games as an example. You cannot say to users "Just buy more powerful compute/phone". And even if they would you may have literally millions of machines, due to having millions of users. In which case saving 1 dollar worth of machine per user is savings of millions which is worth a lot of developer time. Naturally you as a dev won't really be paying this, so the incentive is not directly there. But the incentive comes from people just not buying a game that runs like crap. In these cases GC is nice and dandy at start but then you run into the inevitable "Why does my game stutter?", after which object pools are introduced and even then some annoying "leaks" may remain. If the amount of time had been used from the get go to actually think about memory management the whole issue could have been avoided.
  - native_samples 4y ago
    Yes, but GC and object re-use aren't mutually exclusive. Sometimes people argue as if they are, which is understandable because the overlap between semi-FP programming styles and GCd languages is fairly strong, and the FP world pushes immutable state as almost a matter of moral principle. If you tried to do functional programming with purely manual memory management you'd see high overheads too simply because there'd be so many small allocations and copies. In practice though, people tend to think harder about in-place mutation when they don't have a GC to clean up after them.
    - kragen 4y ago
      They aren't mutually exclusive, but if you're using a tracing garbage collector this millennium you're probably using a generational copying collector, and if you're using a generational copying collector you have a write barrier, and the write barrier means that allocating and initializing a new object is less expensive than overwriting all the fields of an existing object, probably by a factor of several. Also, if your reused object is only referenced from the nursery, and it references other objects in the nursery, those objects ought to be collected on a minor collection, but they won't be; instead they'll be promoted, possibly through several generations, until they reach the generation where your reused object is, which will finally allow them to die. Balanced against this you have less frequent minor collections — none at all during times when you're allocating no new objects. So, with a tracing GC, introducing an object pool will usually make your program slower, not faster. (This is not true with reference counting.)
xwolfi 4y ago
Well it depends a bit, in my low latency application where we cant afford GC pauses, we tolerate them from 5am to 5:30 am. We do everything preallocated and if we must tolerate new heap allocation we simply never release (so we have a lot of object pools). I felt it was hard and exotic at first but now I feel it's quite logical: never free, and have a proper monitoring of your size per unit of information to size the heap right and you're done. But then it also depends why you dont want GC, us it's because clients cannot tolerate a pause (we had a socket manager creating and releasing garbage that triggered one 50ms GC pause during the last 3 seconds of trading of a particularly crazy trading day and the client threatened to leave), but often they re tolerable if you just stay reasonable with your garbage. The problem is not the collection in non critical applications, it's the garbage generation getting completely out of hand. In a C# application my team had to micro optimize because of covid-related explosive trading volume, we simply bought gigantic amount of RAM for our 200 users, only allowed GC if CPU was in low usage and run with 80GB memory usage at the end of the day for an order grid that could run with 5GB collected. That s another way: I wish Java 8 had an easier way to simply deactivate GC for us to run with hardware money.
- cmrdporcupine 4y ago
  One problem is that GC'd languages also tend to have programming practices that encourage the generation of garbage, while languages with manual stack/heap allocation make you think about it a bit more. The sheer number of String and other lightweight (but existent) instances in a running Java program is astounding, because the language simply doesn't encourage you to be parsimonious with creating them. For most people's applications this is totally fine. But, yeah, you can end up with a scenario where GC pauses are just totally unacceptable, or where you need absolutely predictable behaviour and then you might resort to radical things like what you're describing here and it starts to feel like you've just chosen the wrong tool for the job. I say this as a person who wrote an RTB ad server in Java, many moons ago... and never would again.
  - xwolfi 4y ago
    I d simply take a noop GC in the most recent jvm (I cant yet in my conservative bank), and make people suffer through it in prod until everything is constrained correctly, but you're right, String are banned where I work, and what a pain it has to be to do everything via char buffer but it's taking a dev like maybe 10 minutes per "String" handling instead of 5 second during code writing (to massage the buffer all the way from the input signal to the output destination, be it a log file, a storage structure, a comparator or a map key), so it's a giganormous increase of dev time relatively, but in absolute time it's quite trivial over the last 20 years. Yeah we wasted time per feature on String handling but... like maybe a few hours per feature per dev and we generate billions out of the trading backend so... Maybe Java had the wrong assumption and really should just have made C-string optional first class citizens or something. One thing is sure though, our C++ colleagues in the algo team are so slow to deliver, so prone to crazy bugs, so wild and wizardy, so unable to onboard new joiners, they re getting replaced this year by... a brand new Java algo engine... So not sure what to think.

gwbas1c 4y ago

> Even better would be a way to compare vs methods of "manual" memory management (manual alloc/free, RAII/scope based alloc/free, arena allocation, etc.). Unfortunately, non-GC memory management is very application specific, so I'm not sure if a generalized analysis would be super useful. I've personally found Rust to be a very difficult language to learn and become productive in. In contrast, I was able to jump into Swift and become productive very quickly. Swift isn't GC, but is reference counted. Reference cycles will lead to leaked memory. So what's interesting is to know GC's overhead relative to what: Reference counted languages like Swift? Or languages like Rust? More importantly: Is the overhead worth it? Developer time is valuable; thus leading to the critical question: What's cheaper, extra developer time or a more powerful computer?

chrisseaton 4y ago
> Swift isn't GC, but is reference counted GC is often an umbrella term that includes reference counting. Almost all serious tracing GCs include some aspect of reference counting, and almost all serious reference counting GCs include some aspect of tracing.
- gwbas1c 4y ago
  No, it's not. Garbage collection and reference counting are "automatic memory management." With reference counting there are no pauses, and memory is reclaimed immediately. It allows for strongly coupling deallocation with resource cleanup. (The consequence is higher overhead maintaining counts, and leaked reference cycles.) In a garbage collected language you need to explicitly release your resources. (IE, the Dispose pattern that's common in C#)
  - Sindisil 4y ago
    [citation needed] Reference counting is widely considered one strategy of garbage collection (https://en.wikipedia.org/wiki/Garbage_collection_(computer_science) https://en.wikipedia.org/wiki/Garbage_collection_(computer_s...). For that matter, some GCs that are primarily tracing also use ref counts for some portion of the heap, as an optimization (just as some primarily refcounting GCs also run a trace to clean up cycles). Also, reference counting can certainly result in pauses, when large graphs of interconnected objects are reclaimed. On the upside, you know when a pause might happen. You still don't know for certain without explicitly keeping track of what is about to be freed, which would add additional overhead, and indeed may not be practical or even feasible.
  - wgd 4y ago
    > With reference counting there are no pauses, and memory is reclaimed immediately You can't guarantee both of these properties at once, in the general case. Consider a very large tree of objects which are referenced through a single root node, and then that root node becomes eligible for reclamation. For a sufficiently large object graph, either reclamation will require a noticeable pause or some portion of the work will have to be deferred until later.
    - ncmncm 4y ago
      In such uses, if it matters you don't rely on RC to reclaim the storage. You allocate from an arena, and drop the whole graph as a unit. Using pointers to make up a graph is a choice. It is a thing taught in CS classes, so it may feel comfortably familiar; that does not make it good. I never do.
hedora 4y ago
GC shifts human work from development time to deployment / ops time. So the question is whether one-off developer time is cheaper than SRE time for the useful lifetime of the service. However, it gets worse for GC: depending on the application, developing for a GC can be much more difficult / expensive than manual memory management (or reference counting). The canonical examples are low latency (with SLAs on the order of a disk or network I/O, so 10-100 microseconds) and applications that need to use bounded memory. On top of that, there are confounding factors that hurt the case for GC. I don't know of an imperarive GCed language with a reasonably expressive type system (all the JVM languages I know of use type erasure). For experienced developers, rich type systems with actual runtime guarantees are a huge productivity boost.
- titzer 4y ago
  C#? F#? Go (now with generics)? Virgil...
- gwbas1c 4y ago
  > The canonical examples are low latency (with SLAs on the order of a disk or network I/O, so 10-100 microseconds) and applications that need to use bounded memory. Well, in those cases extra developer time is cheaper than a more powerful computer! Will you get ROI building a stereotypical web application with manual memory management? Doubtful. Edit: > GC shifts human work from development time to deployment / ops time. I've never had to tune a garbage collector in deployment. I've heard of other people having to do it; but I've never heard of anyone saying, "yes, I'm so happy I built my website with C++."
  - Sindisil 4y ago
    All the world is not a web application.
    - Spivak 4y ago
      True but it’s not really about web and more about “problem domains where GC pauses are significant, matter, and you can’t throw more compute and memory at the problem” which is not nothing but on the dart board of all SWE jobs good money is on hitting one where it isn’t even if you’re aiming for one.
Sindisil 4y ago
Yes, both. Indeed, the fundamental question is whether the costs of automatic memory management (be it tracing GC or refcount GC) are "worth it". But it's not always as simple as a monetary consideration, and even when it is, the monetary cost often involves way more than just dev time vs cost of computer (e.g., power, cooling, distributed cost over many end users, market applicability because of system requirements).
pjmlp 4y ago
Reference counting is a GC algorithm as per any worthwhile CS book on GC algorithms.
zozbot234 4y ago
Rust can also use reference counting when necessary. Many Rust novices don't realize this, and run into needless trouble when trying to learn Rust. Rc<RefCell<T>> and Arc<Mutex<T>> are not "unidiomatic" other than in a very weak sense. Sometimes they are even unavoidable.
- throwaway894345 4y ago
  It's still pretty painful to deal in Rc<...> and friends in Rust. I was expecting it to be a few extra keystrokes around my types, but I still ended up having to deal with the borrow checker when I would put something into an Rc or take it out to pass into some other function. It was nowhere near as easy as a GC or refcounted language.
  - woodruffw 4y ago
    > I was expecting it to be a few extra keystrokes around my types, but I still ended up having to deal with the borrow checker when I would put something into an Rc or take it out to pass into some other function. I'd be interested to hear where you experienced difficulty, specifically. `Rc<T>` is `Deref<T>`, so you should never have any problems calling borrowing APIs. Owning APIs require an explicit borrow-and-clone, but that's just two calls (`as_ref().clone()`).
- gwbas1c 4y ago
  They're significantly more time-consuming, for the developer, to work with. Think of using something like a lambda to start a thread: You have to explicitly clone your Rc<Whatever> into another variable, and then use the second variable in your lambda. The compiler won't implicitly clone your RC<Whatever> for you. IMO, it's one of the biggest drawbacks in Rust.
pkulak 4y ago
Reference counting is GC. There are no pauses, but incrementing and decrementing a counter on every touch isn’t free either.
- ygra 4y ago
  Well, the pauses are somewhat predictable in that they may appear when the count of an object reaches zero. I had a very expensive closing brace in (admittedly not well-written) C++ code once.
sharpneli 4y ago
One must also remember to differentiate the deployment targets. Not every piece of software is deployed in your own machine. Let's take games as an example. You cannot say to users "Just buy more powerful compute/phone". And even if they would you may have literally millions of machines, due to having millions of users. In which case saving 1 dollar worth of machine per user is savings of millions which is worth a lot of developer time. Naturally you as a dev won't really be paying this, so the incentive is not directly there. But the incentive comes from people just not buying a game that runs like crap. In these cases GC is nice and dandy at start but then you run into the inevitable "Why does my game stutter?", after which object pools are introduced and even then some annoying "leaks" may remain. If the amount of time had been used from the get go to actually think about memory management the whole issue could have been avoided.
- native_samples 4y ago
  Yes, but GC and object re-use aren't mutually exclusive. Sometimes people argue as if they are, which is understandable because the overlap between semi-FP programming styles and GCd languages is fairly strong, and the FP world pushes immutable state as almost a matter of moral principle. If you tried to do functional programming with purely manual memory management you'd see high overheads too simply because there'd be so many small allocations and copies. In practice though, people tend to think harder about in-place mutation when they don't have a GC to clean up after them.
  - kragen 4y ago
    They aren't mutually exclusive, but if you're using a tracing garbage collector this millennium you're probably using a generational copying collector, and if you're using a generational copying collector you have a write barrier, and the write barrier means that allocating and initializing a new object is less expensive than overwriting all the fields of an existing object, probably by a factor of several. Also, if your reused object is only referenced from the nursery, and it references other objects in the nursery, those objects ought to be collected on a minor collection, but they won't be; instead they'll be promoted, possibly through several generations, until they reach the generation where your reused object is, which will finally allow them to die. Balanced against this you have less frequent minor collections — none at all during times when you're allocating no new objects. So, with a tracing GC, introducing an object pool will usually make your program slower, not faster. (This is not true with reference counting.)

xwolfi 4y ago

Well it depends a bit, in my low latency application where we cant afford GC pauses, we tolerate them from 5am to 5:30 am. We do everything preallocated and if we must tolerate new heap allocation we simply never release (so we have a lot of object pools). I felt it was hard and exotic at first but now I feel it's quite logical: never free, and have a proper monitoring of your size per unit of information to size the heap right and you're done. But then it also depends why you dont want GC, us it's because clients cannot tolerate a pause (we had a socket manager creating and releasing garbage that triggered one 50ms GC pause during the last 3 seconds of trading of a particularly crazy trading day and the client threatened to leave), but often they re tolerable if you just stay reasonable with your garbage. The problem is not the collection in non critical applications, it's the garbage generation getting completely out of hand. In a C# application my team had to micro optimize because of covid-related explosive trading volume, we simply bought gigantic amount of RAM for our 200 users, only allowed GC if CPU was in low usage and run with 80GB memory usage at the end of the day for an order grid that could run with 5GB collected. That s another way: I wish Java 8 had an easier way to simply deactivate GC for us to run with hardware money.

cmrdporcupine 4y ago
One problem is that GC'd languages also tend to have programming practices that encourage the generation of garbage, while languages with manual stack/heap allocation make you think about it a bit more. The sheer number of String and other lightweight (but existent) instances in a running Java program is astounding, because the language simply doesn't encourage you to be parsimonious with creating them. For most people's applications this is totally fine. But, yeah, you can end up with a scenario where GC pauses are just totally unacceptable, or where you need absolutely predictable behaviour and then you might resort to radical things like what you're describing here and it starts to feel like you've just chosen the wrong tool for the job. I say this as a person who wrote an RTB ad server in Java, many moons ago... and never would again.
- xwolfi 4y ago
  I d simply take a noop GC in the most recent jvm (I cant yet in my conservative bank), and make people suffer through it in prod until everything is constrained correctly, but you're right, String are banned where I work, and what a pain it has to be to do everything via char buffer but it's taking a dev like maybe 10 minutes per "String" handling instead of 5 second during code writing (to massage the buffer all the way from the input signal to the output destination, be it a log file, a storage structure, a comparator or a map key), so it's a giganormous increase of dev time relatively, but in absolute time it's quite trivial over the last 20 years. Yeah we wasted time per feature on String handling but... like maybe a few hours per feature per dev and we generate billions out of the trading backend so... Maybe Java had the wrong assumption and really should just have made C-string optional first class citizens or something. One thing is sure though, our C++ colleagues in the algo team are so slow to deliver, so prone to crazy bugs, so wild and wizardy, so unable to onboard new joiners, they re getting replaced this year by... a brand new Java algo engine... So not sure what to think.