3 ms·

It says that alloc() is O(1) and thus real-time...but then later on says that advance() must be called k times per alloc in order to avoid exhausting the free s

by chc4 4y ago

It says that alloc() is O(1) and thus real-time...but then later on says that advance() must be called k times per alloc in order to avoid exhausting the free space while still having work on the gray list. This makes it not quite real-time; either you call advance() k times inside alloc (which it recommends) in which case it isn't constant latency but variable on the number of reachable objects from the object you are popping from the work list, or you risk running out of heap and have an eventual loop of draining the grey list to flip. In either case that doesn't seem quite as useful as the claimed "alloc is just a pointer chase" and not much better than other GCs that don't claim to be real-time, and makes it soft real-time (upper bound on instructions) not real-time (exact number of instructions); most other incremental GCs also have a bounded set of work they do per operation. It also sounds like it requires a mutex on read barriers for multithreaded programs, which is pretty bad and expensive. Most modern GC read barriers are just setting a bit in a card table, which doesn't require a lock.

ErikCorry 4y ago
Are you sure? Setting a bit in a card table sounds more like a write barrier.
- chc4 4y ago
  Sorry, you're right, I was thinking of write barrier schemes. Off the top of my head I think most non-moving GCs use only write barriers and not read barriers now, though, along with writes being less common than reads, which is maybe even better than what I said. https://webkit.org/blog/7122/introducing-riptide-webkits-retreating-wavefront-concurrent-garbage-collector/ https://webkit.org/blog/7122/introducing-riptide-webkits-ret... for example only uses a write barrier, and so does Lua's tricolor GC. The closest modern analogue would maybe be something like Metronome, which is a moving GC that also advertises as real-time, but has a read barrier they intentionally tried to make very cheap and optimizable - I guess you could also coalesce Treadmill read barriers to only one mutex + color transition for multiple fields of an object all at once, though.
vidarh 4y ago
As far as I understand it, it's real-time if you don't adjust k dynamically to avoid running out of memory. The heap size you need is R*(1+1/k). So if k=1, then you need to threat a half-full heap as an out-of-memory condition, which is comparable to quite a few GC's. If you set k at e.g. 4 instead, you can use 80% of the heap. If you're ok with losing real-time guarantees you can instead dynamically increase k as needed.
aidenn0 4y ago
> It says that alloc() is O(1) and thus real-time...but then later on says that advance() must be called k times per alloc in order to avoid exhausting the free space while still having work on the gray list. This makes it not quite real-time; either you call advance() k times inside alloc (which it recommends) in which case it isn't constant latency but variable on the number of reachable objects from the object you are popping from the work list, or you risk running out of heap and have an eventual loop of draining the grey list to flip. The original description is for CONS cells, which have exactly 2 pointers; the notes on generalization later in TFA state that if you want to support arbitrary sized objects, advance() needs to be made incremental for larger objects.

by chc4 4y ago

ErikCorry 4y ago

Are you sure? Setting a bit in a card table sounds more like a write barrier.

chc4 4y ago
Sorry, you're right, I was thinking of write barrier schemes. Off the top of my head I think most non-moving GCs use only write barriers and not read barriers now, though, along with writes being less common than reads, which is maybe even better than what I said. https://webkit.org/blog/7122/introducing-riptide-webkits-retreating-wavefront-concurrent-garbage-collector/ https://webkit.org/blog/7122/introducing-riptide-webkits-ret... for example only uses a write barrier, and so does Lua's tricolor GC. The closest modern analogue would maybe be something like Metronome, which is a moving GC that also advertises as real-time, but has a read barrier they intentionally tried to make very cheap and optimizable - I guess you could also coalesce Treadmill read barriers to only one mutex + color transition for multiple fields of an object all at once, though.

vidarh 4y ago

As far as I understand it, it's real-time if you don't adjust k dynamically to avoid running out of memory. The heap size you need is R*(1+1/k). So if k=1, then you need to threat a half-full heap as an out-of-memory condition, which is comparable to quite a few GC's. If you set k at e.g. 4 instead, you can use 80% of the heap. If you're ok with losing real-time guarantees you can instead dynamically increase k as needed.

aidenn0 4y ago

> It says that alloc() is O(1) and thus real-time...but then later on says that advance() must be called k times per alloc in order to avoid exhausting the free space while still having work on the gray list. This makes it not quite real-time; either you call advance() k times inside alloc (which it recommends) in which case it isn't constant latency but variable on the number of reachable objects from the object you are popping from the work list, or you risk running out of heap and have an eventual loop of draining the grey list to flip. The original description is for CONS cells, which have exactly 2 pointers; the notes on generalization later in TFA state that if you want to support arbitrary sized objects, advance() needs to be made incremental for larger objects.