4 ms·

They claim there are no lock-free or wait-free GCs. But Azul have had a pauseless one for the best part of a decade: http://www.artima.com/lejava/articles/azul_

They claim there are no lock-free or wait-free GCs. But Azul have had a pauseless one for the best part of a decade: http://www.artima.com/lejava/articles/azul_pauseless_gc.html http://www.artima.com/lejava/articles/azul_pauseless_gc.html

bitcharmer 9y ago
C4 (the GC implementation you are referring to) is not truly pauseless. It does enormous amount of work with the assist of the "user" threads and has a concept of local (instead of VM-wide) safepoints, but it still (rarely) pauses. http://dl.acm.org/citation.cfm?id=1993491&dl=ACM&coll=DL http://dl.acm.org/citation.cfm?id=1993491&dl=ACM&coll=DL http://static.usenix.org/events/vee05/full_papers/p46-click.pdf http://static.usenix.org/events/vee05/full_papers/p46-click....
- ianopolous 9y ago
  So they are wrong to repeatedly call it pauseless? Or are you making a distinction between their implementation and their algorithm? Or are there different definitions of pauseless?
  - cwzwarich 9y ago
    To quote their earlier paper: "HotSpot supports a notion of GC safepoints, code locations where we have precise knowledge about register and stack locations [1]. The hardware supports a fast cooperative preemption mechanism via interrupts that are taken only on user-selected instructions, allowing us to rapidly stop individual threads only at safepoints. Variants of some common instructions (e.g., backwards branches, function entries) are flagged as safepoints and will check for a pending per-CPU safepoint interrupt. If a safepoint interrupt is pending the CPU will take an exception and the OS will call into a user-mode safepoint-trap handler. The running thread, being at a known safepoint, will then save its state in some convenient format and call the OS to yield. When the OS wants to preempt a normal Java thread, it sets this bit and briefly waits for the thread to yield. If the thread doesn't report back in a timely fashion it gets preempted as normal. The result of this behavior is that nearly all stopped threads are at GC safepoints already. Achieving a global safepoint, a Stop-The-World (STW) pause, is much faster than patch-and-roll-forward schemes [1] and is without the runtime cost normally associated with software polling schemes. While the algorithm we present has no STW pauses, our current implementation does. Hence it's still useful to have a fast stopping mechanism." To quote their later paper: "The C4 algorithm is entirely concurrent, i.e. no global safepoints are required. We also differentiate between the notion of a global safepoint, where are all the mutator threads are stopped, and a checkpoint, where individual threads pass through a barrier function. Checkpoints have a much lower impact on application responsiveness for obvious reasons. Pizlo et al [16] also uses a similar mechanism that they refer to as ragged safepoints. The current C4 implementation, however, does include some global safepoints at phase change locations. The amount of work done in these safepoints is generally independent of the size of the heap, the rate of allocation, and various other key metrics, and on modern hardware these GC phase change safepoints have already been engineered down to sub-millisecond levels. At this point, application observable jitter and responsiveness artifacts are dominated by much larger contributors, such as CPU scheduling and thread contention. The engineering efforts involved in further reducing or eliminating GC safepoint impacts will likely produce little or no observable result."
    - ianopolous 9y ago
      Thank you. My reading of that is that the algorithm is theoretically pauseless, but the implementation has a fixed sub millisecond pause that doesn't scale with heap size or allocation rate. So they could make the implementation truly pauseless, but it wouldn't make any practical impact because of other factors like CPU scheduling jitter dominating. So to all intents and purposes it is pauseless.
nickpsecurity 9y ago
Here's what I found with some Googling with a mix of strengths and weaknesses. Also, note that the one with fragmentation might not be a problem if using clustering with regular replication and fail-over. Depends on how quickly it fragments but small, regular restarts can knock out lots of issues like that. Wait-Free http://www.non-blocking.com/download/Sun04_WaitFreeRef_TR.pdf http://www.non-blocking.com/download/Sun04_WaitFreeRef_TR.pd... Lock-Free 1 http://www.win.tue.nl/~jfg/articles/CSR-04-31.pdf http://www.win.tue.nl/~jfg/articles/CSR-04-31.pdf Lock-Free 2 http://www.non-blocking.com/download/gidpst05_lockfreegc_tr.pdf http://www.non-blocking.com/download/gidpst05_lockfreegc_tr.... Far as restarts, you being a Java guy on distributed systems might find the Micro-Reboots paper interesting too as it ties into above tip: https://www.usenix.org/legacy/event/osdi04/tech/full_papers/candea/candea.pdf https://www.usenix.org/legacy/event/osdi04/tech/full_papers/... https://radlab.cs.berkeley.edu/people/fox/static/pubs/pdf/j03.pdf https://radlab.cs.berkeley.edu/people/fox/static/pubs/pdf/j0...

bitcharmer 9y ago

C4 (the GC implementation you are referring to) is not truly pauseless. It does enormous amount of work with the assist of the "user" threads and has a concept of local (instead of VM-wide) safepoints, but it still (rarely) pauses. http://dl.acm.org/citation.cfm?id=1993491&dl=ACM&coll=DL http://dl.acm.org/citation.cfm?id=1993491&dl=ACM&coll=DL http://static.usenix.org/events/vee05/full_papers/p46-click.pdf http://static.usenix.org/events/vee05/full_papers/p46-click....

ianopolous 9y ago
So they are wrong to repeatedly call it pauseless? Or are you making a distinction between their implementation and their algorithm? Or are there different definitions of pauseless?
- cwzwarich 9y ago
  To quote their earlier paper: "HotSpot supports a notion of GC safepoints, code locations where we have precise knowledge about register and stack locations [1]. The hardware supports a fast cooperative preemption mechanism via interrupts that are taken only on user-selected instructions, allowing us to rapidly stop individual threads only at safepoints. Variants of some common instructions (e.g., backwards branches, function entries) are flagged as safepoints and will check for a pending per-CPU safepoint interrupt. If a safepoint interrupt is pending the CPU will take an exception and the OS will call into a user-mode safepoint-trap handler. The running thread, being at a known safepoint, will then save its state in some convenient format and call the OS to yield. When the OS wants to preempt a normal Java thread, it sets this bit and briefly waits for the thread to yield. If the thread doesn't report back in a timely fashion it gets preempted as normal. The result of this behavior is that nearly all stopped threads are at GC safepoints already. Achieving a global safepoint, a Stop-The-World (STW) pause, is much faster than patch-and-roll-forward schemes [1] and is without the runtime cost normally associated with software polling schemes. While the algorithm we present has no STW pauses, our current implementation does. Hence it's still useful to have a fast stopping mechanism." To quote their later paper: "The C4 algorithm is entirely concurrent, i.e. no global safepoints are required. We also differentiate between the notion of a global safepoint, where are all the mutator threads are stopped, and a checkpoint, where individual threads pass through a barrier function. Checkpoints have a much lower impact on application responsiveness for obvious reasons. Pizlo et al [16] also uses a similar mechanism that they refer to as ragged safepoints. The current C4 implementation, however, does include some global safepoints at phase change locations. The amount of work done in these safepoints is generally independent of the size of the heap, the rate of allocation, and various other key metrics, and on modern hardware these GC phase change safepoints have already been engineered down to sub-millisecond levels. At this point, application observable jitter and responsiveness artifacts are dominated by much larger contributors, such as CPU scheduling and thread contention. The engineering efforts involved in further reducing or eliminating GC safepoint impacts will likely produce little or no observable result."
  - ianopolous 9y ago
    Thank you. My reading of that is that the algorithm is theoretically pauseless, but the implementation has a fixed sub millisecond pause that doesn't scale with heap size or allocation rate. So they could make the implementation truly pauseless, but it wouldn't make any practical impact because of other factors like CPU scheduling jitter dominating. So to all intents and purposes it is pauseless.

nickpsecurity 9y ago

Here's what I found with some Googling with a mix of strengths and weaknesses. Also, note that the one with fragmentation might not be a problem if using clustering with regular replication and fail-over. Depends on how quickly it fragments but small, regular restarts can knock out lots of issues like that. Wait-Free http://www.non-blocking.com/download/Sun04_WaitFreeRef_TR.pdf http://www.non-blocking.com/download/Sun04_WaitFreeRef_TR.pd... Lock-Free 1 http://www.win.tue.nl/~jfg/articles/CSR-04-31.pdf http://www.win.tue.nl/~jfg/articles/CSR-04-31.pdf Lock-Free 2 http://www.non-blocking.com/download/gidpst05_lockfreegc_tr.pdf http://www.non-blocking.com/download/gidpst05_lockfreegc_tr.... Far as restarts, you being a Java guy on distributed systems might find the Micro-Reboots paper interesting too as it ties into above tip: https://www.usenix.org/legacy/event/osdi04/tech/full_papers/candea/candea.pdf https://www.usenix.org/legacy/event/osdi04/tech/full_papers/... https://radlab.cs.berkeley.edu/people/fox/static/pubs/pdf/j03.pdf https://radlab.cs.berkeley.edu/people/fox/static/pubs/pdf/j0...