5 ms·

This needs some qualifications. The above problem is about latency of stop the world collectors in a domain that requires extremely low latency. And if you thi

This needs some qualifications. The above problem is about latency of stop the world collectors in a domain that requires extremely low latency. And if you think that stop the world collections are representative of garbage collection as a whole (i.e. the "bad rap"), this is just not being up to the state of the art. (It's just that generational/incremental collection is hard to impossible without having support for write barriers/read barriers/snapshotting on the compiler or hardware side, which makes that a practical no-go for a language that was never designed to have GC support.) But in terms of throughput, the BDW GC actually performs pretty well, competitive with or beating malloc()/free() libraries. This is plenty enough for a number of applications, especially when it comes to batch processing. In fact, even the stop the world latency is (combined with parallel marking) plenty good enough for a number of types of regular GUI applications, where you don't have the fairly extreme latency requirements of standard video games. It is also worth noting that manual deallocation (especially via RAII) isn't a panacea for latency, as that is just as prone to large pauses due to cascading deletes [1]. [1] While in theory you can do that lazily, in this case you're losing timeliness of deletion and may actually have worse worst case latency than a modern GC that can stagger its work to have bounded pause times. The benefit of RAII is that you may be able to plan these deletions, but even that can be surprisingly difficult at times, requiring extra management to keep data structures alive longer than normal. [2] [2] Note that lazily deleting objects in RC to avoid pause times is not necessarily the answer; for one thing, you're introducing much of the complexity associated with incremental GC again (especially having to do X amount of deallocation work for each allocation), or risking considerable space overhead. https://dl.acm.org/doi/abs/10.1145/964001.964019 https://dl.acm.org/doi/abs/10.1145/964001.964019 It also remains a difficult challenge when you're dealing with objects that aren't of bounded size (e.g. large arrays).

cplusplusfellow 3y ago
For all of the reasons you note above, this is why I've almost exclusively dealt with arena-style allocations of fixed-object-sizes when doing ultra low latency work.
- iainctduncan 3y ago
  Hi, I'm just starting a (long) PhD in computer music languages, and one of my hoped-for projects is improving the GC for the Scheme implementation I work in for soft realtime use. If you (or anyone else) wouldn't mind sharing suggestion on resources for learning about low-latency modern GCs, it would be most appreciated. :-)
  - moonchild 3y ago
    read the garbage collection handbook - https://gchandbook.org/ https://gchandbook.org/
    - iainctduncan 3y ago
      thanks, that's good to know. I'm working through his first GC book right now and plan to order the new edition of the gchandbook when I'm done the other (which I read was a gentler intro to the topic). iain
  - pebal 3y ago
    You can look at the SGCL garbage collector for C++: https://github.com/pebal/sgcl https://github.com/pebal/sgcl. It works in a separate thread, is locks-free and never stops the world.
    - iainctduncan 3y ago
      great, thanks!
dataangel 3y ago
I have been writing low latency code for a decade and never seen cascading deletes be a problem. GC on the other hand is a constant latency problem for people.
- p_l 3y ago
  running a throughput-oriented GC instead of latency/realtime one is a common error of those people (also, throughput oriented ones are usually the default)
- rbehrends 3y ago
  > I have been writing low latency code for a decade and never seen cascading deletes be a problem. I don't know what your domain is, but the domains I'm familiar with (especially hard real-time) deal with the underlying constraints by way of restricting how you write programs. A side effect of these restrictions is that you generally avoid use constructs that give rise to cascading deletes. But ultimately, having to deal with these restrictions is suboptimal. I remember a talk by Gil Tene (CTO and co-founder of Azul Systems) about how the problem with writing real-time Java was that it historically required you to write non-idiomatic Java code, which came at a serious cost to reuse and where he argued that one of the benefits of Azul's GC was that you could write (mostly) idiomatic Java and still have GC noise be less than OS noise. There is of course the actual problem that the stricter your latency requirements are, the fewer GCs actually meet them. Plenty of modern off the shelf GCs meet typical soft real time requirements, but the harder your real time requirements get, the fewer implementations actually meet them (and are increasingly more expensive). I'll also add that depending on how strict your latency requirements are, off the shelf allocators may not meet them, either, even for a single malloc() (though there are allocators that offer hard upper bounds for allocation costs, such as TLSF).
gumby 3y ago
> It's just that generational/incremental collection is hard to impossible without having support for write barriers/read barriers/snapshotting on the compiler or hardware side, which makes that a practical no-go for a language that was never designed to have GC support. It was demonstrated in the mid 80s that the MMU could be used to implement the write barrier (when I saw that I knew lisp machines were a dead end, though I kept using them for as long as was feasible). You can use this and other compiler support to implement it in a language not designed for GC support, no problem. The issue I think you meant is that you can’t have a transporting collector (which also compacts your working set, even allowing you to return memory to the system). A language like C++ doesn’t anticipate an object’s address ever changing, so that’s a no go. I suppose you could write special shared_ptr / unique_ptr that supported address mutation but you’d need a compiler flag to check for an object’s address being taken… but to some degree the destructor paradigm renders a lot of this moot.
- rbehrends 3y ago
  > It was demonstrated in the mid 80s that the MMU could be used to implement the write barrier (when I saw that I knew lisp machines were a dead end, though I kept using them for as long as was feasible). You can use this and other compiler support to implement it in a language not designed for GC support, no problem. Yes, that's why I wrote about support "on the compiler or hardware side" (i.e. MMUs). That said, while this might work in theory, the BDW GC does have support for it, and in practice it doesn't actually work well. Throughput suffers and pause times can actually get worse. By the way, another alternative way of having incremental collection without compiler support is to use fork() for snapshotting (there's an option in D for that), but that has its own issues, of course. > The issue I think you meant is that you can’t have a transporting collector (which also compacts your working set, even allowing you to return memory to the system). A language like C++ doesn’t anticipate an object’s address ever changing, so that’s a no go. No, I wasn't talking about a compacting collector. I very specifically meant generational and/or incremental collection.
  - gumby 3y ago
    > No, I wasn't talking about a compacting collector. I very specifically meant generational and/or incremental collection. FWIW they are orthogonal
zozbot234 3y ago
The compiler support you need in practice is quite limited. There is an implementation of incremental cycle collection in Rust: https://github.com/chc4/samsara https://github.com/chc4/samsara It's made possible because Rust can tell apart read-only and read-write references (except for references to interior mutable objects, but these are known to the compiler and references to them can be treated as read-write). This avoids a global stop-the-world for the entire program. Cascading deletes are rare in practice, and if anything they are inherent to deterministic deletion, which is often a desirable property. When they're possible, one can often use arena allocation to avoid the issue altogether since arenas are managed as a single allocation.
- rbehrends 3y ago
  > The compiler support you need in practice is quite limited. This is true, but it's absent especially in C. Of course, as long as you can intercept writes and/or reads through pointers, you are good to go in principle. However, that solution may not be efficient. > Cascading deletes are rare in practice An array of objects (e.g. std::vector<std::string>) already has unbounded deallocation cost. People mostly think of tree-like structures here, but such structures only add the risk of stack blowout to the lack of an upper bound. But in principle, any container that does not have a size limit can give rise to unbounded pause times.
torginus 3y ago
The problem isn't mark-and-sweep GCs it's that the Boehm GC is the Ford T model of garbage collectors.
- rbehrends 3y ago
  Absolutely not. While it obviously should not be used for use cases that it isn't designed for, as a conservative mark-and-sweep GC it is extremely well engineered and has very good throughput.

cplusplusfellow 3y ago

For all of the reasons you note above, this is why I've almost exclusively dealt with arena-style allocations of fixed-object-sizes when doing ultra low latency work.

iainctduncan 3y ago
Hi, I'm just starting a (long) PhD in computer music languages, and one of my hoped-for projects is improving the GC for the Scheme implementation I work in for soft realtime use. If you (or anyone else) wouldn't mind sharing suggestion on resources for learning about low-latency modern GCs, it would be most appreciated. :-)
- moonchild 3y ago
  read the garbage collection handbook - https://gchandbook.org/ https://gchandbook.org/
  - iainctduncan 3y ago
    thanks, that's good to know. I'm working through his first GC book right now and plan to order the new edition of the gchandbook when I'm done the other (which I read was a gentler intro to the topic). iain
- pebal 3y ago
  You can look at the SGCL garbage collector for C++: https://github.com/pebal/sgcl https://github.com/pebal/sgcl. It works in a separate thread, is locks-free and never stops the world.
  - iainctduncan 3y ago
    great, thanks!

dataangel 3y ago

I have been writing low latency code for a decade and never seen cascading deletes be a problem. GC on the other hand is a constant latency problem for people.

p_l 3y ago
running a throughput-oriented GC instead of latency/realtime one is a common error of those people (also, throughput oriented ones are usually the default)
rbehrends 3y ago
> I have been writing low latency code for a decade and never seen cascading deletes be a problem. I don't know what your domain is, but the domains I'm familiar with (especially hard real-time) deal with the underlying constraints by way of restricting how you write programs. A side effect of these restrictions is that you generally avoid use constructs that give rise to cascading deletes. But ultimately, having to deal with these restrictions is suboptimal. I remember a talk by Gil Tene (CTO and co-founder of Azul Systems) about how the problem with writing real-time Java was that it historically required you to write non-idiomatic Java code, which came at a serious cost to reuse and where he argued that one of the benefits of Azul's GC was that you could write (mostly) idiomatic Java and still have GC noise be less than OS noise. There is of course the actual problem that the stricter your latency requirements are, the fewer GCs actually meet them. Plenty of modern off the shelf GCs meet typical soft real time requirements, but the harder your real time requirements get, the fewer implementations actually meet them (and are increasingly more expensive). I'll also add that depending on how strict your latency requirements are, off the shelf allocators may not meet them, either, even for a single malloc() (though there are allocators that offer hard upper bounds for allocation costs, such as TLSF).

gumby 3y ago

> It's just that generational/incremental collection is hard to impossible without having support for write barriers/read barriers/snapshotting on the compiler or hardware side, which makes that a practical no-go for a language that was never designed to have GC support. It was demonstrated in the mid 80s that the MMU could be used to implement the write barrier (when I saw that I knew lisp machines were a dead end, though I kept using them for as long as was feasible). You can use this and other compiler support to implement it in a language not designed for GC support, no problem. The issue I think you meant is that you can’t have a transporting collector (which also compacts your working set, even allowing you to return memory to the system). A language like C++ doesn’t anticipate an object’s address ever changing, so that’s a no go. I suppose you could write special shared_ptr / unique_ptr that supported address mutation but you’d need a compiler flag to check for an object’s address being taken… but to some degree the destructor paradigm renders a lot of this moot.

rbehrends 3y ago
> It was demonstrated in the mid 80s that the MMU could be used to implement the write barrier (when I saw that I knew lisp machines were a dead end, though I kept using them for as long as was feasible). You can use this and other compiler support to implement it in a language not designed for GC support, no problem. Yes, that's why I wrote about support "on the compiler or hardware side" (i.e. MMUs). That said, while this might work in theory, the BDW GC does have support for it, and in practice it doesn't actually work well. Throughput suffers and pause times can actually get worse. By the way, another alternative way of having incremental collection without compiler support is to use fork() for snapshotting (there's an option in D for that), but that has its own issues, of course. > The issue I think you meant is that you can’t have a transporting collector (which also compacts your working set, even allowing you to return memory to the system). A language like C++ doesn’t anticipate an object’s address ever changing, so that’s a no go. No, I wasn't talking about a compacting collector. I very specifically meant generational and/or incremental collection.
- gumby 3y ago
  > No, I wasn't talking about a compacting collector. I very specifically meant generational and/or incremental collection. FWIW they are orthogonal

zozbot234 3y ago

The compiler support you need in practice is quite limited. There is an implementation of incremental cycle collection in Rust: https://github.com/chc4/samsara https://github.com/chc4/samsara It's made possible because Rust can tell apart read-only and read-write references (except for references to interior mutable objects, but these are known to the compiler and references to them can be treated as read-write). This avoids a global stop-the-world for the entire program. Cascading deletes are rare in practice, and if anything they are inherent to deterministic deletion, which is often a desirable property. When they're possible, one can often use arena allocation to avoid the issue altogether since arenas are managed as a single allocation.

rbehrends 3y ago
> The compiler support you need in practice is quite limited. This is true, but it's absent especially in C. Of course, as long as you can intercept writes and/or reads through pointers, you are good to go in principle. However, that solution may not be efficient. > Cascading deletes are rare in practice An array of objects (e.g. std::vector<std::string>) already has unbounded deallocation cost. People mostly think of tree-like structures here, but such structures only add the risk of stack blowout to the lack of an upper bound. But in principle, any container that does not have a size limit can give rise to unbounded pause times.

torginus 3y ago

The problem isn't mark-and-sweep GCs it's that the Boehm GC is the Ford T model of garbage collectors.

rbehrends 3y ago
Absolutely not. While it obviously should not be used for use cases that it isn't designed for, as a conservative mark-and-sweep GC it is extremely well engineered and has very good throughput.