13 ms·

Garbage collection for systems programmers (2023)

396 points by ingve 3y ago

deleted 3y ago
[deleted]
spintin 3y ago
Or you just use static atomic variables no? I mean it wont solve your race conditions but it also wont crash. And it will be VERY fast because parallelism without cache misses! I wish there was a Java with C struct JNI access.
- bugbuddy 3y ago
  This is false. Depending on the CPU Arch, updating a shared static atomic variable may cause cache invalidation. How fast depends on how hot and tight you critical sections are.
- yvdriess 3y ago
  Saying this as a big hardware atomics enjoyer: Static atomic variables are not fast, are not parallel and definitely are the worst kind of cache misses. Atomics are also atomic only on that one single operation, such as manipulating a single number in a struct or swapping out a pointer from one version of an object to another. To atomically expose a set of changes to a datastructure, you either use a lock or swap the old for the new, which is the driving example in the article.
- neonsunset 3y ago
  It's called C# (supporting plain C structs is just a small part of its low-level features)
  - pjmlp 3y ago
    Or D, available as official fronted language on GCC and LLVM projects, :)
- gmokki 3y ago
  Modern Java does support directly calling C functions, with structs. And also upcalls back to java. All without any JNI style preprocessing or stubs. https://docs.oracle.com/en/java/javase/21/core/calling-c-library-function-foreign-function-and-memory-api.html https://docs.oracle.com/en/java/javase/21/core/calling-c-lib...
  - spintin 3y ago
    Hm, ok I have Arrays of 64 byte atomic Structs defined in C and I want to iterate over them in Java, is that possible with the Memory API?
magicalhippo 3y ago
A point that seems to get lost in many of the pro-GC articles, this one included from what I can see, is that memory is just one kind of resource. Correct code, especially in systems programming, will need to manage external resources as well, be it file handles, sockets or whatnot. GC only solves the application memory part, thus doesn't help at all for handling those external resources. In fact it can make it much more complicated, just look at what it takes to correctly implement a non-trivial IDispose in .Net. Other approaches like RAII or reference counting makes it much easier in my experience to handle both memory and external resources in a unified way, thus making it easier to write correct code and reason about it. That said, I'm not blatantly against GC's. It's a tool and it has some pros and cons, like everything else. The "manual GC" RCU approach mentioned in the article is interesting for certain tasks.
- zwieback 3y ago
  So true, moving from C++ to mostly C# I'm liking memory management by GC but hating tracking file handles, sockets, etc. RAII is something I really appreciated
  - neonsunset 3y ago
    (SafeFileHandle is internally reference counted, but yes, worst case when you forget to .Dispose it, it waits in the finalizer queue for the GC to trigger the finalizer thread to process the items in it)
  - pjmlp 3y ago
    Use Roslyn analysis that errors when using is forgotten in an IDisposable type, for example. By the way, in modern .NET, using makes use of structural typing. Any class or struct, with a Dispose() method can be referred to, no need to implement the interface, and can also be retrofitted via extension methods.
    - osigurdson 3y ago
      This is strange advice. Why not just implement the IDisposable interface like normal C# code? Using extension methods for this is strange as well. Doing this even somewhat correctly would mean creating another class that implements IDisposable which can only work with public members of the original. In general best not to do weird stuff for no reason imo.
keybored 3y ago
The article motivates RCU and then does a u-turn and starts making a general argument for general-purpose GC. Not quite a trojan horse but a bit whiplash provoking.
- o11c 3y ago
  I definitely wouldn't call the RCU thing a GC, since at no point is the object garbage. It is in one of 3 states, and changes between them as quickly as possible: * active * obsolete but alive for old readers * deallocated Note that depending on how you write your code, it may be possible to reuse an "obsolete-but-alive" object for a "new" allocation safely, though I haven't analyzed performance for this in full. As usual for GC discussions, it is very handwavy about when you have to "fall back to `shared\_ptr/Arc`", when in fact avoiding refcounts (either because you can prove you already have ownership (which does have implications for tail calls, but you shouldn't use those anyway), or by avoiding indirection entirely) is the whole point of serious refcount-based systems. Doing nothing at all is obviously better than GC's "do something, sometime".
  - nemetroid 3y ago
    It’s not entirely clear from the article, but the part about rcu_defer() is not just a ”what if?” segue into GC, it’s how RCU is typically used.
  - naasking 3y ago
    RCU objects are garbage when they're held by old readers thay will no longer utilize them in the remaining code path before they exit. This code path is virtually always of non-zero length, because ensuring they are deallocated in the absolute shortest path is an NP-class problem for sure. I don't see why the fact that this code path might sometimes be longer in GC would preclude RCU from being GC.
bckr 3y ago
Off topic but what is going on in the picture of the leaking pipe? I don’t think it’s AI but there’s a third arm in there that I don’t understand. There’s at least two guys in the picture but I can’t assign one of the arms to either of them.
- mindv0rtex 3y ago
  It's definitely AI generated, that picture makes no sense.
  - deleted 3y ago
    [deleted]
- deutschepost 3y ago
  It's three people. The guy on the right is leaning over another one under the water. It's probably a picture from a flood training simulator. Edit: https://commons.wikimedia.org/wiki/File:US_Navy_040308-N-0000P-002_Sailors_practice_repairing_leaks_in_the_%22wet_trainer%22_on_board_the_Submarine_Training_Facility_(SUBTRAFAC)_in_Norfolk,_Va.jpg https://commons.wikimedia.org/wiki/File:US_Navy_040308-N-000... The picture was uploaded in 2009. Downvote if you want, but there is no AI at work here.
- deleted 3y ago
  [deleted]
pron 3y ago
Except in the special case where all memory can be easily handled in arenas, good tracing GCs have long ago surpassed manual memory management in throughput, and more recently their latency impact is more than acceptable for the vast majority of applications (OpenJDK's ZGC has typical pause times measured in double/triple-digit microseconds, and the worst case rarely exceeds 1ms for a reasonable allocation rate -- the pauses are in the same ballpark as OS-induced ones). The only real and significant tradeoff is in memory footprint, and outside of specialty niches (where arenas just work for everything and worst-case latency is in the low microseconds range) that is the only high order question: is my application running in a memory-constrained environment (or it's really worth it to sacrifice other things to keep down RAM consumption) or not?
- znpy 3y ago
  > (OpenJDK's ZGC has typical pause times measured in double/triple-digit microseconds, and the worst case rarely exceeds 1ms for a reasonable allocation rate -- the pauses are in the same ballpark as OS-induced ones) We've been benchmarking ZGC and Shenandoah at work, and the p100 pause time is usually below 500us (micro-seconds). ZGC seems to be performing a bit better, as it seems to be performing less pauses than Shenandoah (hence doing more work/pause). We still have to run tests-in-production, but so far it seems that GC pauses are largely a solved issue when using ZGC (and Generational ZGC since Java21).
  - deleted 3y ago
    [deleted]
  - Galanwe 3y ago
    > We've been benchmarking ZGC and Shenandoah at work, and the p100 pause time is usually below 500us > so far it seems that GC pauses are largely a solved issue when using ZGC What? 500us is abysmally slow. Most projects I work on have a latency budget of less than 10us, the average being 2us. That is the budget for the whole wire in/wire out for a packet. Even for less latency sensitive workloads, 500us is a no go for most networking application.
    - 3y ago
teleforce 3y ago
For promising modern and parallel GC techniques please check MPL or MaPLe with its novel Automatic Management of Parallelism. It won distinguished paper award in POPL 2024 and ACM SIGPLAN dissertation award 2023 by proposing these two main things [1],[2]: a) Provably efficient parallel garbage collection based on disentanglement b) Provably efficient automatic granularity control [1] MaPLe (MPL): https://github.com/MPLLang/mpl https://github.com/MPLLang/mpl [2] Automatic Parallelism Management: https://dl.acm.org/doi/10.1145/3632880 https://dl.acm.org/doi/10.1145/3632880
- bugbuddy 3y ago
  Nice links. Thanks for posting these.
- pjmlp 3y ago
  Great material, thanks for sharing.
- bool3max 3y ago
  What does "provably efficient" mean?
  - shwestrick 3y ago
    I'm one of the authors of this work -- I can explain a little. "Provably efficient" means that the language provides worst-case performance guarantees. For example in the "Automatic Parallelism Management" paper (https://dl.acm.org/doi/10.1145/3632880 https://dl.acm.org/doi/10.1145/3632880), we develop a compiler and run-time system that can execute extremely fine-grained parallel code without losing performance. (Concretely, imagine tiny tasks of around only 10-100 instructions each.) The key idea is to make sure that any task which is *too tiny* is executed sequentially instead of in parallel. To make this happen, we use a scheduler that runs in the background during execution. It is the scheduler's job to decide on-the-fly which tasks should be sequentialized and which tasks should be "promoted" into actual threads that can run in parallel. Intuitively, each promotion incurs a cost, but also exposes parallelism. In the paper, we present our scheduler and prove a worst-case performance bound. We specifically show that the total overhead of promotion will be at most a small constant factor (e.g., 1% overhead), and also that the theoretical amount of parallelism is unaffected, asymptotically. All of this is implemented in MaPLe (https://github.com/mpllang/mpl https://github.com/mpllang/mpl) and you can go play with it now!
mgaunard 3y ago
I do a lot of different types of systems programming. Only times I actually use GC is to manage resources other than memory.
celrod 3y ago
The RCU use case is convincing, but my experience with GCs in other situations has been poor. To me, this reads more like an argument for bespoke memory management solutions being able to yield the best performance (I agree!), which is a totally different case from the more general static lifetimes generally outperforming dynamic lifetimes (especially when a tracing step is needed to determine liveness). > Lies people believe... Calling free() gives the memory back to the OS. I believe calling `free()` gives the memory back to the allocator, which is much better than giving it to the OS; syscalls are slow. Perhaps not immediately; mimalloc only makes frees available to future `malloc`s periodically. Trying a simple benchmark where I allocate and then immediately `free` 800 bytes, 1 million times, and counting the number of unique pointers I get: glibc's malloc: 1 jemalloc: 1 mimalloc: 4 Julia's garbage collector: 62767 62767, at about 48 MiB, isn't that bad, but it still blows out my computer's L3 cache. Using a GC basically guarantees every new allocation is from RAM, rather than cache. This kills performance of any heavily allocating code; we don't care only about how fast memory management can work, but how quickly we can worth with what it gives us. I gave a benchmark in Julia showcasing this: https://discourse.julialang.org/t/blog-post-rust-vs-julia-in-scientific-computing/101711/80?u=elrod https://discourse.julialang.org/t/blog-post-rust-vs-julia-in... Malloc/free gives you a chance at staying hot, if your actual working memory is small enough. Allocators like mimalloc are also designed (like the compacting GC) to have successive allocations be close together. The 4 unique pointers I got from mimalloc were 896 bytes apart. My opinions might be less sour if I had more experience with compacting GCs, but I think GCs are just a vastly more complicated solution to the problem of safe memory management than something like Rust's borrow checker. Given that the complexity is foisted on the compiler and runtime developers, that's normally not so bad for users, and an acceptable tradeoff when writing code that isn't performance sensitive. Similarly, RAII with static lifetimes is also a reasonable tradeoff for code not important enough for more bespoke approaches. The articles example is evidently one of those deserving a more bespoke solution.
- chc4 3y ago
  It's really not enough to just say that a GC gave you more pointers = it has worse cache locality. Compacting GC almost always has better cache utilization than malloc, because heap fragmentation over long-running programs will waste TLB cache entries and slack space between objects. A bump allocator from a compacting GC will give you a new pointer for each allocation because free doesn't reclaim the memory...but those allocations will be sequentially, and if you were in the case where you are churning through your heap and only ever touch the most recent object they will always be in cache still. Benchmarking the knock-on effects of allocators and GCs are insanely difficult and I'm very skeptical of basically any synthetic benchmarks like this.
samatman 3y ago
This skirts around the edge of an observation which I want to dive into, which is that modern user OSes (anything which isn't a specialized RTOS) has built-in garbage collection. We just don't call it that: we just call it memory management. What do we call languages with a built in GC? Memory-managed languages! You see this in a lot of older "top-to-bottom" C programs: they allocate, they clean up system resources (using longjmp to one label), but they don't bother with free. When the program exits the OS gets all that memory back anyway, so why bother? There's a missed opportunity here, to have an OS with a garbage collector with less isolation from programs, one which handles resources more like a language's runtime GC. It will probably stay missed, because in the typical GCed language, the GC is intricately built into practically every line of the runtime, so it's not really practical to make a distribution of that language for one OS which hands that control over to the operating system. But it's a pity, because there's a lot of room to improve some of the chronic problems we see from this artificial isolation of program-level memory management from OS level.
- flohofwoe 3y ago
  > You see this in a lot of older "top-to-bottom" C programs: they allocate, they clean up system resources (using longjmp to one label), but they don't bother with free. When the program exits the OS gets all that memory back anyway, so why bother? You don't need to bother with releasing other types of resources either though (files, sockets, threads, ...), since the operating system will take care of that on process exit (unless you are on AmigaOS). The only reason to free memory is to recycle that memory in other allocations in long running applications without grabbing new memory from the OS. For one-shot command line tools it's usually not needed.
- kaba0 3y ago
  In Java, the Epsilon GC is just that.
- ninkendo 3y ago
  The OS only knows it can free memory when your process exits (same as file handles and other resources.) If your process is designed to exit once it's done its job, you can use the OS as a garbage collector. Having an operating system know when memory is unused within your running program is not something that has ever existed though (except for perhaps some esoteric research OS's.) I wouldn't say we're missing an opportunity, because the thing we're missing doesn't exist in any meaningful sense. On the other hand, a programming methodology that uses very simple, short-lived programs is a totally legitimate way to do things... it's how CLI tools and the scripting languages that script them work, it's how web servers used to work (with CGI/etc), and it's a perfectly reasonable approach even today.
netbioserror 3y ago
I use Nim in production. It defaults to RC. The biggest benefit of runtime automatic memory management that rarely gets mentioned: You can easily eliminate almost all memory semantics from a typical server-side program. My code is 99.9% business logic, with the 0.1% being a couple procedures which interface to a C library. Hardcore manual memory people seem to have completely misaligned priorities to real-world concerns. Maintainability, safety, productivity, and iteration speed seem to be bottom-of-list to the egotistic holy grail be being able to say they write their own memory routines. If they're not in an embedded context, I'm really unsure why anyone paying them to write code should care what they have to say. They're not talking about increasing robustness and reducing costs, so what the hell are they even rambling about? I've had too many of these debates in-person face-to-face with people who can't match my ability to deliver. The vast majority of us are not smarter than the compiler, and are not smarter than automatic MM routines. Those who are write compilers and GCs. They don't work on the same programs we all write, just memory managed. It's the worst-kept secret that the remaining contexts where manual management is used often have the worst-maintained spaghetti codebases, leading to disasters, whistleblown scandles, and hush-hush covered catastrophes waiting in the wings while people get the hell out of dodge before they blow. It's all duct tape and prayers. Having had to inspect and translate procedures from a deliberately obfuscated spaghetti C codebase, my position on this is going to be hard to budge. Experience is an unbeatable Bayesian prior.
- EatFlamingDeath 3y ago
  How's Nim in production? I really enjoyed working with the language and I've been bitten too many times by Python's package management. Do you think it's suitable for scripting too?
  - netbioserror 3y ago
    I use it in a context it's extremely well suited for: As a CLI executable invoked by other server-side scripts. It's a program that does lots of mathematical and statistical data processing, along with HTML report generation. Like I said, I use the default RC and don't even think about memory. The type system is very simple; there is only one nominal string type, for example, instead of the 12 in Rust or C++, and it's a fleshed-out string type that can be mutable or immutable. I also take big advantage of its preference for functional-style referential transparency with only local mutations. I have only a single module that could be construed as "OO". Oh, and the module system works exactly like you probably intuit a module system should, so you probably already know how to use it. If you want to script with Nim, it's actually quite nice; it has a "run" command which compiles and runs without depositing artifacts in the run directory, and has an incredibly robust standard library, comparable to that of Python. I have no experience making a live always-running Nim application, so I can't speak to that. But in the context I use it, it's incredible.
atum47 3y ago
I once enabled garbage collection for this software I was writing and it collected everything.
- ervine 3y ago
  Sprayed spot remover on my dog. Next day he was gone.
mwkaufma 3y ago
(1) the pivot from rcu to general purpose tracing gcs is bait-and-switch. (2) Manual memory management is more than just malloc/free calls -- it's about layout (e.g. struct-of-arrays, inlining, implicit offsets, packing, etc)
- kaba0 3y ago
  I disagree with 2 being manual memory management. There is definitely a lack of control in contemporary managed languages (though it’s also far from perfect in low-level languages) for memory layout, but there are definitely ways to affect it.
  - cb321 3y ago
    I agree with your disagreement. As a case in point, Nim has packed bitfields but various choices in automatic memory management. As a concrete example, a spell-check custom-data store uses them here: https://github.com/c-blake/suggest/blob/04e313f8f8d3adf4cb55a8ae0973f815f2b506c6/suggest.nim#L102 https://github.com/c-blake/suggest/blob/04e313f8f8d3adf4cb55... (there the memory is in a memory mapped file and so that code has to manage the space itself.. so, maybe not the perfect example). But I also agree there tends to be a correlation in PLang design in avoiding both low-level memory layout and in manual memory management. But it's just a tendency, not fundamental.
- titzer 3y ago
  For (2) Virgil has several features that allow you to layout memory with various levels of control. I assume you meaning "array of structs", and you can do that with arrays of tuples, which will naturally be flattened and normalized based on the target (i.e. will be array-of-structs on native targets). You can define byte-exact layouts[1] (mostly for interfacing with other software and parsing binary formats), unbox ADTs, and soon you can even control the exact encoding of ADTs. Virgil is GC'd. [1] https://github.com/titzer/virgil/blob/master/doc/tutorial/Layouts.md https://github.com/titzer/virgil/blob/master/doc/tutorial/La...
  - mwkaufma 3y ago
PaulDavisThe1st 3y ago
I quoted this in another comment here, but just to highlight one of the best couple of sentences in TFA: > Tools to automate the “actually freeing the memory” part, like lifetimes in Rust and RAII in C++, don’t solve these problems. They absolutely aid correctness, something else you should care deeply about, but they do nothing to simplify all this machinery.
bsdpufferfish 3y ago
Why are they always trying to sell these things to audiences who are not interested?
HippoBaro 3y ago
For the kind of software I write there are two cases: (1) the hot path for which I will always have custom allocators and avoid allocations and (2) everything else. For (1) GC or not it doesn’t make a difference, I’ll opt-out. For (2) GC is really convenient and correct.
- leapis 3y ago
  Agreed- I come from a Java/C++ shop where we tried to tackle this dichotomy with interop but it ended up causing more problems than it solved. A lot of the work that Java has done with modern garbage collectors is impressive, but even they admit (indirectly, via Valhalla) that no/low-alloc code has it's place.
  - astrobe_ 3y ago
    > no/low-alloc code has it's place ... Which is pretty large in the embedded firwmare field. However that's not systems programming but system (singular) programming.
- deleted 3y ago
  [deleted]
musicale 3y ago
The tricky part is identifying which systems programmers can be garbage collected and when.
- GeorgeTirebiter 3y ago
  Soylent Green was set in 2022/2023 https://en.wikipedia.org/wiki/Soylent_Green?useskin=vector https://en.wikipedia.org/wiki/Soylent_Green?useskin=vector
KingLancelot 3y ago
[dead]
worik 3y ago
Not mentioned in this article is one thing that goes very well with GC is async/await I am a async/await hater for personal Idiosyncratic style reasons that I will not bore you with I use it a lot in Type/Java script. Have done so in Dart. Works as it should I have used it in Rust. IMO it is a disaster there. Shoehorning the sort of memory management required to use asyc/await with a multi threaded runtime is a hellscape https://doc.rust-lang.org/std/pin/index.html https://doc.rust-lang.org/std/pin/index.html
- pkolaczk 3y ago
  You don’t need pinning in regular async code in Rust. This is for library writers.
SmartHypercube 3y ago
Using RCU as the example to motivate GC is interesting. It is essentially transferring the responsibility of freeing from the writer to the last reader, who cannot be determined when compiling. It makes a lot of sense. But this makes me thinking that, if I want more performance, should I further transfer the freeing from the reader to a dedicated batch process? The readers only update a mark / write into a queue or something. Every once in a while, a batch process collects all garbages and compacts. This way the readers don't have random additional overheads. > Lies people believe about memory management > The programmer knows the best times to pause for memory management. In my experience, there are many programs in which the programmer does know the best times to pause for memory management. For example, in games and crypto trading programs, I want to classify all computations into two priorities. I need to do an update / render a frame / compute a trading action in every time period. If it finishes before the deadline, I have nothing to do now and would like to collect some garbages. If the high-priority thing is using all the available time, for example, when the market is very active, I don't care too much about collecting garbages and would like to defer everything that is not strictly necessary to as late as possible.
- filleduchaos 3y ago
  The very next line after the portion of the article you clipped is "Sometimes there are obvious answers—like on the loading screen of a video game."
  - SmartHypercube 3y ago
    I'm not talking about the loading screen of a video game.
    - zelphirkalt 3y ago
      You are saying for example in games. The article is saying for example in games in a loading screen. You are saying not in loading screens. Maybe you should give more specific examples then, instead of leaving people guessing what you mean?
tonyljx66 3y ago
[dead]
WhereIsTheTruth 3y ago
Memory allocation strategy is task specific, not program specific
dblohm7 3y ago
I really like the way the author explained RCU!

396 points by ingve 3y ago

deleted 3y ago

[deleted]

Or you just use static atomic variables no? I mean it wont solve your race conditions but it also wont crash. And it will be VERY fast because parallelism without cache misses! I wish there was a Java with C struct JNI access.

bugbuddy 3y ago
This is false. Depending on the CPU Arch, updating a shared static atomic variable may cause cache invalidation. How fast depends on how hot and tight you critical sections are.
yvdriess 3y ago
Saying this as a big hardware atomics enjoyer: Static atomic variables are not fast, are not parallel and definitely are the worst kind of cache misses. Atomics are also atomic only on that one single operation, such as manipulating a single number in a struct or swapping out a pointer from one version of an object to another. To atomically expose a set of changes to a datastructure, you either use a lock or swap the old for the new, which is the driving example in the article.
neonsunset 3y ago
It's called C# (supporting plain C structs is just a small part of its low-level features)
- pjmlp 3y ago
  Or D, available as official fronted language on GCC and LLVM projects, :)
gmokki 3y ago
Modern Java does support directly calling C functions, with structs. And also upcalls back to java. All without any JNI style preprocessing or stubs. https://docs.oracle.com/en/java/javase/21/core/calling-c-library-function-foreign-function-and-memory-api.html https://docs.oracle.com/en/java/javase/21/core/calling-c-lib...
- spintin 3y ago
  Hm, ok I have Arrays of 64 byte atomic Structs defined in C and I want to iterate over them in Java, is that possible with the Memory API?

magicalhippo 3y ago

A point that seems to get lost in many of the pro-GC articles, this one included from what I can see, is that memory is just one kind of resource. Correct code, especially in systems programming, will need to manage external resources as well, be it file handles, sockets or whatnot. GC only solves the application memory part, thus doesn't help at all for handling those external resources. In fact it can make it much more complicated, just look at what it takes to correctly implement a non-trivial IDispose in .Net. Other approaches like RAII or reference counting makes it much easier in my experience to handle both memory and external resources in a unified way, thus making it easier to write correct code and reason about it. That said, I'm not blatantly against GC's. It's a tool and it has some pros and cons, like everything else. The "manual GC" RCU approach mentioned in the article is interesting for certain tasks.

zwieback 3y ago
So true, moving from C++ to mostly C# I'm liking memory management by GC but hating tracking file handles, sockets, etc. RAII is something I really appreciated
- neonsunset 3y ago
  (SafeFileHandle is internally reference counted, but yes, worst case when you forget to .Dispose it, it waits in the finalizer queue for the GC to trigger the finalizer thread to process the items in it)
- pjmlp 3y ago
  Use Roslyn analysis that errors when using is forgotten in an IDisposable type, for example. By the way, in modern .NET, using makes use of structural typing. Any class or struct, with a Dispose() method can be referred to, no need to implement the interface, and can also be retrofitted via extension methods.
  - osigurdson 3y ago
    This is strange advice. Why not just implement the IDisposable interface like normal C# code? Using extension methods for this is strange as well. Doing this even somewhat correctly would mean creating another class that implements IDisposable which can only work with public members of the original. In general best not to do weird stuff for no reason imo.

keybored 3y ago

The article motivates RCU and then does a u-turn and starts making a general argument for general-purpose GC. Not quite a trojan horse but a bit whiplash provoking.

o11c 3y ago
I definitely wouldn't call the RCU thing a GC, since at no point is the object garbage. It is in one of 3 states, and changes between them as quickly as possible: * active * obsolete but alive for old readers * deallocated Note that depending on how you write your code, it may be possible to reuse an "obsolete-but-alive" object for a "new" allocation safely, though I haven't analyzed performance for this in full. As usual for GC discussions, it is very handwavy about when you have to "fall back to `shared\_ptr/Arc`", when in fact avoiding refcounts (either because you can prove you already have ownership (which does have implications for tail calls, but you shouldn't use those anyway), or by avoiding indirection entirely) is the whole point of serious refcount-based systems. Doing nothing at all is obviously better than GC's "do something, sometime".
- nemetroid 3y ago
  It’s not entirely clear from the article, but the part about rcu_defer() is not just a ”what if?” segue into GC, it’s how RCU is typically used.
- naasking 3y ago
  RCU objects are garbage when they're held by old readers thay will no longer utilize them in the remaining code path before they exit. This code path is virtually always of non-zero length, because ensuring they are deallocated in the absolute shortest path is an NP-class problem for sure. I don't see why the fact that this code path might sometimes be longer in GC would preclude RCU from being GC.

bckr 3y ago

Off topic but what is going on in the picture of the leaking pipe? I don’t think it’s AI but there’s a third arm in there that I don’t understand. There’s at least two guys in the picture but I can’t assign one of the arms to either of them.

mindv0rtex 3y ago
It's definitely AI generated, that picture makes no sense.
- deleted 3y ago
  [deleted]
deutschepost 3y ago
It's three people. The guy on the right is leaning over another one under the water. It's probably a picture from a flood training simulator. Edit: https://commons.wikimedia.org/wiki/File:US_Navy_040308-N-0000P-002_Sailors_practice_repairing_leaks_in_the_%22wet_trainer%22_on_board_the_Submarine_Training_Facility_(SUBTRAFAC)_in_Norfolk,_Va.jpg https://commons.wikimedia.org/wiki/File:US_Navy_040308-N-000... The picture was uploaded in 2009. Downvote if you want, but there is no AI at work here.
deleted 3y ago
[deleted]

pron 3y ago

Except in the special case where all memory can be easily handled in arenas, good tracing GCs have long ago surpassed manual memory management in throughput, and more recently their latency impact is more than acceptable for the vast majority of applications (OpenJDK's ZGC has typical pause times measured in double/triple-digit microseconds, and the worst case rarely exceeds 1ms for a reasonable allocation rate -- the pauses are in the same ballpark as OS-induced ones). The only real and significant tradeoff is in memory footprint, and outside of specialty niches (where arenas just work for everything and worst-case latency is in the low microseconds range) that is the only high order question: is my application running in a memory-constrained environment (or it's really worth it to sacrifice other things to keep down RAM consumption) or not?

znpy 3y ago
> (OpenJDK's ZGC has typical pause times measured in double/triple-digit microseconds, and the worst case rarely exceeds 1ms for a reasonable allocation rate -- the pauses are in the same ballpark as OS-induced ones) We've been benchmarking ZGC and Shenandoah at work, and the p100 pause time is usually below 500us (micro-seconds). ZGC seems to be performing a bit better, as it seems to be performing less pauses than Shenandoah (hence doing more work/pause). We still have to run tests-in-production, but so far it seems that GC pauses are largely a solved issue when using ZGC (and Generational ZGC since Java21).
- deleted 3y ago
  [deleted]
- Galanwe 3y ago
  > We've been benchmarking ZGC and Shenandoah at work, and the p100 pause time is usually below 500us > so far it seems that GC pauses are largely a solved issue when using ZGC What? 500us is abysmally slow. Most projects I work on have a latency budget of less than 10us, the average being 2us. That is the budget for the whole wire in/wire out for a packet. Even for less latency sensitive workloads, 500us is a no go for most networking application.
  - 3y ago

teleforce 3y ago

For promising modern and parallel GC techniques please check MPL or MaPLe with its novel Automatic Management of Parallelism. It won distinguished paper award in POPL 2024 and ACM SIGPLAN dissertation award 2023 by proposing these two main things [1],[2]: a) Provably efficient parallel garbage collection based on disentanglement b) Provably efficient automatic granularity control [1] MaPLe (MPL): https://github.com/MPLLang/mpl https://github.com/MPLLang/mpl [2] Automatic Parallelism Management: https://dl.acm.org/doi/10.1145/3632880 https://dl.acm.org/doi/10.1145/3632880

bugbuddy 3y ago
Nice links. Thanks for posting these.
pjmlp 3y ago
Great material, thanks for sharing.
bool3max 3y ago
What does "provably efficient" mean?
- shwestrick 3y ago
  I'm one of the authors of this work -- I can explain a little. "Provably efficient" means that the language provides worst-case performance guarantees. For example in the "Automatic Parallelism Management" paper (https://dl.acm.org/doi/10.1145/3632880 https://dl.acm.org/doi/10.1145/3632880), we develop a compiler and run-time system that can execute extremely fine-grained parallel code without losing performance. (Concretely, imagine tiny tasks of around only 10-100 instructions each.) The key idea is to make sure that any task which is *too tiny* is executed sequentially instead of in parallel. To make this happen, we use a scheduler that runs in the background during execution. It is the scheduler's job to decide on-the-fly which tasks should be sequentialized and which tasks should be "promoted" into actual threads that can run in parallel. Intuitively, each promotion incurs a cost, but also exposes parallelism. In the paper, we present our scheduler and prove a worst-case performance bound. We specifically show that the total overhead of promotion will be at most a small constant factor (e.g., 1% overhead), and also that the theoretical amount of parallelism is unaffected, asymptotically. All of this is implemented in MaPLe (https://github.com/mpllang/mpl https://github.com/mpllang/mpl) and you can go play with it now!

mgaunard 3y ago

I do a lot of different types of systems programming. Only times I actually use GC is to manage resources other than memory.

celrod 3y ago

The RCU use case is convincing, but my experience with GCs in other situations has been poor. To me, this reads more like an argument for bespoke memory management solutions being able to yield the best performance (I agree!), which is a totally different case from the more general static lifetimes generally outperforming dynamic lifetimes (especially when a tracing step is needed to determine liveness). > Lies people believe... Calling free() gives the memory back to the OS. I believe calling `free()` gives the memory back to the allocator, which is much better than giving it to the OS; syscalls are slow. Perhaps not immediately; mimalloc only makes frees available to future `malloc`s periodically. Trying a simple benchmark where I allocate and then immediately `free` 800 bytes, 1 million times, and counting the number of unique pointers I get: glibc's malloc: 1 jemalloc: 1 mimalloc: 4 Julia's garbage collector: 62767 62767, at about 48 MiB, isn't that bad, but it still blows out my computer's L3 cache. Using a GC basically guarantees every new allocation is from RAM, rather than cache. This kills performance of any heavily allocating code; we don't care only about how fast memory management can work, but how quickly we can worth with what it gives us. I gave a benchmark in Julia showcasing this: https://discourse.julialang.org/t/blog-post-rust-vs-julia-in-scientific-computing/101711/80?u=elrod https://discourse.julialang.org/t/blog-post-rust-vs-julia-in... Malloc/free gives you a chance at staying hot, if your actual working memory is small enough. Allocators like mimalloc are also designed (like the compacting GC) to have successive allocations be close together. The 4 unique pointers I got from mimalloc were 896 bytes apart. My opinions might be less sour if I had more experience with compacting GCs, but I think GCs are just a vastly more complicated solution to the problem of safe memory management than something like Rust's borrow checker. Given that the complexity is foisted on the compiler and runtime developers, that's normally not so bad for users, and an acceptable tradeoff when writing code that isn't performance sensitive. Similarly, RAII with static lifetimes is also a reasonable tradeoff for code not important enough for more bespoke approaches. The articles example is evidently one of those deserving a more bespoke solution.

chc4 3y ago
It's really not enough to just say that a GC gave you more pointers = it has worse cache locality. Compacting GC almost always has better cache utilization than malloc, because heap fragmentation over long-running programs will waste TLB cache entries and slack space between objects. A bump allocator from a compacting GC will give you a new pointer for each allocation because free doesn't reclaim the memory...but those allocations will be sequentially, and if you were in the case where you are churning through your heap and only ever touch the most recent object they will always be in cache still. Benchmarking the knock-on effects of allocators and GCs are insanely difficult and I'm very skeptical of basically any synthetic benchmarks like this.

samatman 3y ago

This skirts around the edge of an observation which I want to dive into, which is that modern user OSes (anything which isn't a specialized RTOS) has built-in garbage collection. We just don't call it that: we just call it memory management. What do we call languages with a built in GC? Memory-managed languages! You see this in a lot of older "top-to-bottom" C programs: they allocate, they clean up system resources (using longjmp to one label), but they don't bother with free. When the program exits the OS gets all that memory back anyway, so why bother? There's a missed opportunity here, to have an OS with a garbage collector with less isolation from programs, one which handles resources more like a language's runtime GC. It will probably stay missed, because in the typical GCed language, the GC is intricately built into practically every line of the runtime, so it's not really practical to make a distribution of that language for one OS which hands that control over to the operating system. But it's a pity, because there's a lot of room to improve some of the chronic problems we see from this artificial isolation of program-level memory management from OS level.

flohofwoe 3y ago
> You see this in a lot of older "top-to-bottom" C programs: they allocate, they clean up system resources (using longjmp to one label), but they don't bother with free. When the program exits the OS gets all that memory back anyway, so why bother? You don't need to bother with releasing other types of resources either though (files, sockets, threads, ...), since the operating system will take care of that on process exit (unless you are on AmigaOS). The only reason to free memory is to recycle that memory in other allocations in long running applications without grabbing new memory from the OS. For one-shot command line tools it's usually not needed.
kaba0 3y ago
In Java, the Epsilon GC is just that.
ninkendo 3y ago
The OS only knows it can free memory when your process exits (same as file handles and other resources.) If your process is designed to exit once it's done its job, you can use the OS as a garbage collector. Having an operating system know when memory is unused within your running program is not something that has ever existed though (except for perhaps some esoteric research OS's.) I wouldn't say we're missing an opportunity, because the thing we're missing doesn't exist in any meaningful sense. On the other hand, a programming methodology that uses very simple, short-lived programs is a totally legitimate way to do things... it's how CLI tools and the scripting languages that script them work, it's how web servers used to work (with CGI/etc), and it's a perfectly reasonable approach even today.

netbioserror 3y ago

I use Nim in production. It defaults to RC. The biggest benefit of runtime automatic memory management that rarely gets mentioned: You can easily eliminate almost all memory semantics from a typical server-side program. My code is 99.9% business logic, with the 0.1% being a couple procedures which interface to a C library. Hardcore manual memory people seem to have completely misaligned priorities to real-world concerns. Maintainability, safety, productivity, and iteration speed seem to be bottom-of-list to the egotistic holy grail be being able to say they write their own memory routines. If they're not in an embedded context, I'm really unsure why anyone paying them to write code should care what they have to say. They're not talking about increasing robustness and reducing costs, so what the hell are they even rambling about? I've had too many of these debates in-person face-to-face with people who can't match my ability to deliver. The vast majority of us are not smarter than the compiler, and are not smarter than automatic MM routines. Those who are write compilers and GCs. They don't work on the same programs we all write, just memory managed. It's the worst-kept secret that the remaining contexts where manual management is used often have the worst-maintained spaghetti codebases, leading to disasters, whistleblown scandles, and hush-hush covered catastrophes waiting in the wings while people get the hell out of dodge before they blow. It's all duct tape and prayers. Having had to inspect and translate procedures from a deliberately obfuscated spaghetti C codebase, my position on this is going to be hard to budge. Experience is an unbeatable Bayesian prior.

EatFlamingDeath 3y ago
How's Nim in production? I really enjoyed working with the language and I've been bitten too many times by Python's package management. Do you think it's suitable for scripting too?
- netbioserror 3y ago
  I use it in a context it's extremely well suited for: As a CLI executable invoked by other server-side scripts. It's a program that does lots of mathematical and statistical data processing, along with HTML report generation. Like I said, I use the default RC and don't even think about memory. The type system is very simple; there is only one nominal string type, for example, instead of the 12 in Rust or C++, and it's a fleshed-out string type that can be mutable or immutable. I also take big advantage of its preference for functional-style referential transparency with only local mutations. I have only a single module that could be construed as "OO". Oh, and the module system works exactly like you probably intuit a module system should, so you probably already know how to use it. If you want to script with Nim, it's actually quite nice; it has a "run" command which compiles and runs without depositing artifacts in the run directory, and has an incredibly robust standard library, comparable to that of Python. I have no experience making a live always-running Nim application, so I can't speak to that. But in the context I use it, it's incredible.

atum47 3y ago

I once enabled garbage collection for this software I was writing and it collected everything.

ervine 3y ago
Sprayed spot remover on my dog. Next day he was gone.

mwkaufma 3y ago

(1) the pivot from rcu to general purpose tracing gcs is bait-and-switch. (2) Manual memory management is more than just malloc/free calls -- it's about layout (e.g. struct-of-arrays, inlining, implicit offsets, packing, etc)

kaba0 3y ago
I disagree with 2 being manual memory management. There is definitely a lack of control in contemporary managed languages (though it’s also far from perfect in low-level languages) for memory layout, but there are definitely ways to affect it.
- cb321 3y ago
  I agree with your disagreement. As a case in point, Nim has packed bitfields but various choices in automatic memory management. As a concrete example, a spell-check custom-data store uses them here: https://github.com/c-blake/suggest/blob/04e313f8f8d3adf4cb55a8ae0973f815f2b506c6/suggest.nim#L102 https://github.com/c-blake/suggest/blob/04e313f8f8d3adf4cb55... (there the memory is in a memory mapped file and so that code has to manage the space itself.. so, maybe not the perfect example). But I also agree there tends to be a correlation in PLang design in avoiding both low-level memory layout and in manual memory management. But it's just a tendency, not fundamental.
titzer 3y ago
For (2) Virgil has several features that allow you to layout memory with various levels of control. I assume you meaning "array of structs", and you can do that with arrays of tuples, which will naturally be flattened and normalized based on the target (i.e. will be array-of-structs on native targets). You can define byte-exact layouts[1] (mostly for interfacing with other software and parsing binary formats), unbox ADTs, and soon you can even control the exact encoding of ADTs. Virgil is GC'd. [1] https://github.com/titzer/virgil/blob/master/doc/tutorial/Layouts.md https://github.com/titzer/virgil/blob/master/doc/tutorial/La...
- mwkaufma 3y ago

PaulDavisThe1st 3y ago

I quoted this in another comment here, but just to highlight one of the best couple of sentences in TFA: > Tools to automate the “actually freeing the memory” part, like lifetimes in Rust and RAII in C++, don’t solve these problems. They absolutely aid correctness, something else you should care deeply about, but they do nothing to simplify all this machinery.

bsdpufferfish 3y ago

Why are they always trying to sell these things to audiences who are not interested?

HippoBaro 3y ago

For the kind of software I write there are two cases: (1) the hot path for which I will always have custom allocators and avoid allocations and (2) everything else. For (1) GC or not it doesn’t make a difference, I’ll opt-out. For (2) GC is really convenient and correct.

leapis 3y ago
Agreed- I come from a Java/C++ shop where we tried to tackle this dichotomy with interop but it ended up causing more problems than it solved. A lot of the work that Java has done with modern garbage collectors is impressive, but even they admit (indirectly, via Valhalla) that no/low-alloc code has it's place.
- astrobe_ 3y ago
  > no/low-alloc code has it's place ... Which is pretty large in the embedded firwmare field. However that's not systems programming but system (singular) programming.
deleted 3y ago
[deleted]

musicale 3y ago

The tricky part is identifying which systems programmers can be garbage collected and when.

GeorgeTirebiter 3y ago
Soylent Green was set in 2022/2023 https://en.wikipedia.org/wiki/Soylent_Green?useskin=vector https://en.wikipedia.org/wiki/Soylent_Green?useskin=vector

KingLancelot 3y ago

[dead]

worik 3y ago

Not mentioned in this article is one thing that goes very well with GC is async/await I am a async/await hater for personal Idiosyncratic style reasons that I will not bore you with I use it a lot in Type/Java script. Have done so in Dart. Works as it should I have used it in Rust. IMO it is a disaster there. Shoehorning the sort of memory management required to use asyc/await with a multi threaded runtime is a hellscape https://doc.rust-lang.org/std/pin/index.html https://doc.rust-lang.org/std/pin/index.html

pkolaczk 3y ago
You don’t need pinning in regular async code in Rust. This is for library writers.

SmartHypercube 3y ago

Using RCU as the example to motivate GC is interesting. It is essentially transferring the responsibility of freeing from the writer to the last reader, who cannot be determined when compiling. It makes a lot of sense. But this makes me thinking that, if I want more performance, should I further transfer the freeing from the reader to a dedicated batch process? The readers only update a mark / write into a queue or something. Every once in a while, a batch process collects all garbages and compacts. This way the readers don't have random additional overheads. > Lies people believe about memory management > The programmer knows the best times to pause for memory management. In my experience, there are many programs in which the programmer does know the best times to pause for memory management. For example, in games and crypto trading programs, I want to classify all computations into two priorities. I need to do an update / render a frame / compute a trading action in every time period. If it finishes before the deadline, I have nothing to do now and would like to collect some garbages. If the high-priority thing is using all the available time, for example, when the market is very active, I don't care too much about collecting garbages and would like to defer everything that is not strictly necessary to as late as possible.

filleduchaos 3y ago
The very next line after the portion of the article you clipped is "Sometimes there are obvious answers—like on the loading screen of a video game."
- SmartHypercube 3y ago
  I'm not talking about the loading screen of a video game.
  - zelphirkalt 3y ago
    You are saying for example in games. The article is saying for example in games in a loading screen. You are saying not in loading screens. Maybe you should give more specific examples then, instead of leaving people guessing what you mean?

tonyljx66 3y ago

[dead]

WhereIsTheTruth 3y ago

Memory allocation strategy is task specific, not program specific

dblohm7 3y ago

I really like the way the author explained RCU!