6 ms·

Azul's Pauseless Garbage Collector

180 points by DanielRibeiro 16y ago

prodigal_erik 16y ago
Sounds like fascinating work. I would have expected big unpredictable performance problems from using a read barrier to lazily fixup references to moved objects, given how expensive each page fault is in a superscalar pipeline. But it's hard to recommend a vendor who's opaque about pricing. If we have to ask, we probably can't afford it.
- runT1ME 16y ago
  If i'm not mistaken, the 'read barrier' is only active during a mark of the heap, not all the time. So, considering that marking can be parallelized and there's a good chance a lot of the heap is now dead objects (you only mark live ones) you shouldn't be too affected.
- modeless 16y ago
  Page faults are usually expensive because the bits you need must be read in from disk. In this case the bits you need are still in RAM, and could even conceivably be in cache. It's probably not tremendously more expensive than a cache miss (which is still quite expensive, but hopefully the collector is fixing up pointers fast enough that actual page faults are relatively rare).
  - binaryfinery 16y ago
    They'd be about as expensive as throwing an exception. And the live objects would, I assume, quickly pull all the other live objects into the active pages. I love this hack.
    - danvet 16y ago
      Furthermore they're using 2mb pages instead of the usual 4kb (on x86). That cuts the overhead by a factor of 512 alone. The remaining problem I see is cache-trashing because on every minor page-fault you have to run a part of your mark&sweep algo, surely kicking out all the application data&code from caches. That's inevitable less efficient than a stop-the-world approach.
- schumihan 16y ago
  On their hardware appliance, they use a special instruction to implement the barrier. For software appliance, the performance may be a real problem.
- ggruschow 16y ago
  To be fair, if you've got a budget that supports a multi-developer team and you fundamentally need their solution, you can afford their prices. They're not insane, and if you just ask they're not opaque. On the other hand, did you know you can turn off the garbage collector on CPython?
vsingh 16y ago
Could anyone explain the "self-healing" algorithm in simplistic terms? From what I gathered, when they compact a page of memory, moving all the objects within it to different locations, they will set a marker on all pointers to be "unset". Then, while program execution is still going on, the GC thread will be busily going through the pointers and correcting them to their new locations as necessary, then setting the marker flag. If, during this period, the executing code tries to use an unmarked pointer, a "read barrier" is hit in the VM, and the GC code corrects that pointer ("self-heals"), sets the marker, then allows execution to continue. Do I have this right? What about the initial unsetting of all these markers? It would seem to require going through all pointers before you want to compact a page, and I would suspect they're being more clever than that.
- modeless 16y ago
  You don't mark pointers, you unmap a page of virtual memory. This instantly invalidates all pointers to that page without touching them, and allows you to immediately reuse that physical memory by mapping it to a new virtual address. When you eventually dereference a pointer to an unmapped page the processor's MMU throws a page fault. The VM catches the fault and fixes up the pointer on the spot. What I'd like to know is how you can guarantee that all garbage is eventually collected in a system like this, and how you can guarantee that you've fixed up all pointers to an unmapped virtual page so you can reuse it.
  - vsingh 16y ago
    Ah, that makes things clearer - thanks. > What I'd like to know is how you can guarantee that all garbage is eventually collected in a system like this. Me too. If you can't guarantee that, it seems that when you unmap a page of virtual memory, you'd have to make sure never to use that page again. You'd also have to keep around your table of "mappings from old pointers to new pointers" forever, just in case you encounter a lingering bad pointer and need to correct it.
    - modeless 16y ago
      Yes, exactly, in fact I was just editing my post to add that concern! Their garbage collector constantly scans the heap fixing up pointers so you don't have to wait for every reference to hit a page fault, but it seems difficult to guarantee that you're done if the program is twiddling references while the collector is doing its work. Perhaps there is also a write barrier which makes sure to never write a pointer to a collected page.
deleted 16y ago
[deleted]
pdubroy 16y ago
> Self healing is a unique capability that, as far as we know, the Azul collector is the only one to do, and it can only be done with a read barrier. The Metronome GC from IBM Research (http://www.research.ibm.com/people/d/dfb/papers/Bacon05High.pdf http://www.research.ibm.com/people/d/dfb/papers/Bacon05High....) also uses a read-barrier to fix up pointers to objects which have moved. Although, I don't think it does marking in the read barrier.
stretchwithme 16y ago
Always taking on the most difficult thing instead of waiting until you have no choice but to clean house sounds like the best strategy for java garbage collection, running your life, running a country, you name it.
- Groxx 16y ago
  That doesn't really map to computers, which spend an enormous amount of time waiting and doing nothing. Putting it off lets you collect when nothing is happening, which would otherwise be "wasted" time. More in general, putting things off frequently means being able to handle them without interruption when the time is right; it's only a problem if the right time doesn't come up frequently enough (too busy). And context switching is pretty much guaranteed to be expensive in every circumstance, be it computers, your life, or a country. Back to computers again, this would mean that the problem is being too busy, not that you put it off - they'll likely take about the same amount of time no matter when they're handled; if anything, they're more likely to be faster if done all at once rather than bit by bit, due to cache behaviors. At that point you know you have other, larger problems.
  - stretchwithme 16y ago
    ok, when all urgent and important things have been attended to, do the most important, non-urgent thing regardless of how hard it is, until its done or something urgent and important needs doing.
- sitmack 16y ago
  From an Darwinian stand point it does not. But then again, eager Haskell got to 80% of GHC by one person in one year so you might have a point. Is this why Fascism thrives in tropical climates?
- Charuru 16y ago
  Not really. you shouldn't be always doing the hardest thing, but the thing that gives you the most value/ROI, or in terms of >1 entity, the thing with which you have the most comparative advantage.
icefox 16y ago
<quote> Can you explain how Azul's pauseless garbage collector works? Gil Tene: At Azul, we've been building high performance Java virtual machines (JVM)s for the past eight years now. We started the company in 2002, and we aimed to solve several scalability and infrastructure problems for Java back then.... </quote> Anyone else really hate then people don't actually answer the question? They should have edited that useless part out.
- paul 16y ago
  The whole rest of the article is him explaining how it works!
  - JoachimSchipper 16y ago
    Additionally, "we started a company to make Java faster and garbage collection was around #3 on our list" is informative. There's only one sentence that could really be cut ("founded in 2005" or somesuch.)
- cracki 16y ago
  a little corporate history should be okay if the rest of the article is actually answering the question.
- wahnfrieden 16y ago
  No, they should have just edited out the question at the beginning, seeing as the article isn't in a Q&A format anyway. Then the company history wouldn't have felt out of place.
jganetsk 16y ago
What happens with objects that can't fit on a single page, such as a large array?
- bensummers 16y ago
  The obvious answer is to use more than one page. Why wouldn't that work with a special case for "large allocations", like most heap implementations?
  - jganetsk 16y ago
    Good idea. Now that I think about it, a large object is trivial in this sysyem. You dedicate some group of contiguous pages solely to the object. This results in some potential waste of the last page, which is probably acceptable. You would not ever need to perform compaction in those pages, just pointer remapping. When the object eventually dies, you release all the pages at once.
kisiel 16y ago
The guy says his company solved some difficult engineering problems, but this is not language of an engineer. "On Zing they generally tend to be below a millisecond." - what on earth does it mean? He tested it? How? What are the results? What is the confidence interval?
wingo 16y ago
Wwwwow. The Boehm-Demers-Weiser GC can't move objects because, you know, C is gnarly and you can't really trust anything to update pointers in-place. But what if you could? This work seems to indicate that you could have a compacting collector with arbitrary C programs, given the extra hooks they added to Linux (http://lwn.net/Articles/392307/ http://lwn.net/Articles/392307/). Azul continues to impress.

180 points by DanielRibeiro 16y ago

Sounds like fascinating work. I would have expected big unpredictable performance problems from using a read barrier to lazily fixup references to moved objects, given how expensive each page fault is in a superscalar pipeline. But it's hard to recommend a vendor who's opaque about pricing. If we have to ask, we probably can't afford it.

runT1ME 16y ago
If i'm not mistaken, the 'read barrier' is only active during a mark of the heap, not all the time. So, considering that marking can be parallelized and there's a good chance a lot of the heap is now dead objects (you only mark live ones) you shouldn't be too affected.
modeless 16y ago
Page faults are usually expensive because the bits you need must be read in from disk. In this case the bits you need are still in RAM, and could even conceivably be in cache. It's probably not tremendously more expensive than a cache miss (which is still quite expensive, but hopefully the collector is fixing up pointers fast enough that actual page faults are relatively rare).
- binaryfinery 16y ago
  They'd be about as expensive as throwing an exception. And the live objects would, I assume, quickly pull all the other live objects into the active pages. I love this hack.
  - danvet 16y ago
    Furthermore they're using 2mb pages instead of the usual 4kb (on x86). That cuts the overhead by a factor of 512 alone. The remaining problem I see is cache-trashing because on every minor page-fault you have to run a part of your mark&sweep algo, surely kicking out all the application data&code from caches. That's inevitable less efficient than a stop-the-world approach.
schumihan 16y ago
On their hardware appliance, they use a special instruction to implement the barrier. For software appliance, the performance may be a real problem.
ggruschow 16y ago
To be fair, if you've got a budget that supports a multi-developer team and you fundamentally need their solution, you can afford their prices. They're not insane, and if you just ask they're not opaque. On the other hand, did you know you can turn off the garbage collector on CPython?

vsingh 16y ago

Could anyone explain the "self-healing" algorithm in simplistic terms? From what I gathered, when they compact a page of memory, moving all the objects within it to different locations, they will set a marker on all pointers to be "unset". Then, while program execution is still going on, the GC thread will be busily going through the pointers and correcting them to their new locations as necessary, then setting the marker flag. If, during this period, the executing code tries to use an unmarked pointer, a "read barrier" is hit in the VM, and the GC code corrects that pointer ("self-heals"), sets the marker, then allows execution to continue. Do I have this right? What about the initial unsetting of all these markers? It would seem to require going through all pointers before you want to compact a page, and I would suspect they're being more clever than that.

modeless 16y ago
You don't mark pointers, you unmap a page of virtual memory. This instantly invalidates all pointers to that page without touching them, and allows you to immediately reuse that physical memory by mapping it to a new virtual address. When you eventually dereference a pointer to an unmapped page the processor's MMU throws a page fault. The VM catches the fault and fixes up the pointer on the spot. What I'd like to know is how you can guarantee that all garbage is eventually collected in a system like this, and how you can guarantee that you've fixed up all pointers to an unmapped virtual page so you can reuse it.
- vsingh 16y ago
  Ah, that makes things clearer - thanks. > What I'd like to know is how you can guarantee that all garbage is eventually collected in a system like this. Me too. If you can't guarantee that, it seems that when you unmap a page of virtual memory, you'd have to make sure never to use that page again. You'd also have to keep around your table of "mappings from old pointers to new pointers" forever, just in case you encounter a lingering bad pointer and need to correct it.
  - modeless 16y ago
    Yes, exactly, in fact I was just editing my post to add that concern! Their garbage collector constantly scans the heap fixing up pointers so you don't have to wait for every reference to hit a page fault, but it seems difficult to guarantee that you're done if the program is twiddling references while the collector is doing its work. Perhaps there is also a write barrier which makes sure to never write a pointer to a collected page.

deleted 16y ago

[deleted]

pdubroy 16y ago

> Self healing is a unique capability that, as far as we know, the Azul collector is the only one to do, and it can only be done with a read barrier. The Metronome GC from IBM Research (http://www.research.ibm.com/people/d/dfb/papers/Bacon05High.pdf http://www.research.ibm.com/people/d/dfb/papers/Bacon05High....) also uses a read-barrier to fix up pointers to objects which have moved. Although, I don't think it does marking in the read barrier.

stretchwithme 16y ago

Always taking on the most difficult thing instead of waiting until you have no choice but to clean house sounds like the best strategy for java garbage collection, running your life, running a country, you name it.

Groxx 16y ago
That doesn't really map to computers, which spend an enormous amount of time waiting and doing nothing. Putting it off lets you collect when nothing is happening, which would otherwise be "wasted" time. More in general, putting things off frequently means being able to handle them without interruption when the time is right; it's only a problem if the right time doesn't come up frequently enough (too busy). And context switching is pretty much guaranteed to be expensive in every circumstance, be it computers, your life, or a country. Back to computers again, this would mean that the problem is being too busy, not that you put it off - they'll likely take about the same amount of time no matter when they're handled; if anything, they're more likely to be faster if done all at once rather than bit by bit, due to cache behaviors. At that point you know you have other, larger problems.
- stretchwithme 16y ago
  ok, when all urgent and important things have been attended to, do the most important, non-urgent thing regardless of how hard it is, until its done or something urgent and important needs doing.
sitmack 16y ago
From an Darwinian stand point it does not. But then again, eager Haskell got to 80% of GHC by one person in one year so you might have a point. Is this why Fascism thrives in tropical climates?
Charuru 16y ago
Not really. you shouldn't be always doing the hardest thing, but the thing that gives you the most value/ROI, or in terms of >1 entity, the thing with which you have the most comparative advantage.

icefox 16y ago

<quote> Can you explain how Azul's pauseless garbage collector works? Gil Tene: At Azul, we've been building high performance Java virtual machines (JVM)s for the past eight years now. We started the company in 2002, and we aimed to solve several scalability and infrastructure problems for Java back then.... </quote> Anyone else really hate then people don't actually answer the question? They should have edited that useless part out.

paul 16y ago
The whole rest of the article is him explaining how it works!
- JoachimSchipper 16y ago
  Additionally, "we started a company to make Java faster and garbage collection was around #3 on our list" is informative. There's only one sentence that could really be cut ("founded in 2005" or somesuch.)
cracki 16y ago
a little corporate history should be okay if the rest of the article is actually answering the question.
wahnfrieden 16y ago
No, they should have just edited out the question at the beginning, seeing as the article isn't in a Q&A format anyway. Then the company history wouldn't have felt out of place.

jganetsk 16y ago

What happens with objects that can't fit on a single page, such as a large array?

bensummers 16y ago
The obvious answer is to use more than one page. Why wouldn't that work with a special case for "large allocations", like most heap implementations?
- jganetsk 16y ago
  Good idea. Now that I think about it, a large object is trivial in this sysyem. You dedicate some group of contiguous pages solely to the object. This results in some potential waste of the last page, which is probably acceptable. You would not ever need to perform compaction in those pages, just pointer remapping. When the object eventually dies, you release all the pages at once.

kisiel 16y ago

The guy says his company solved some difficult engineering problems, but this is not language of an engineer. "On Zing they generally tend to be below a millisecond." - what on earth does it mean? He tested it? How? What are the results? What is the confidence interval?

wingo 16y ago

Wwwwow. The Boehm-Demers-Weiser GC can't move objects because, you know, C is gnarly and you can't really trust anything to update pointers in-place. But what if you could? This work seems to indicate that you could have a compacting collector with arbitrary C programs, given the extra hooks they added to Linux (http://lwn.net/Articles/392307/ http://lwn.net/Articles/392307/). Azul continues to impress.