I've thought about doing some talks about Lock-Free Memory Reclamation, but Erez Petrank beat me to it. Even though I know a lot about the subject, I couldn't have done a better job myself (really, I couldn't), and lucky for you, his talks are online ;)
There are actually two talks, one is about Manual Lock-Free Memory Reclamation:
https://www.youtube.com/watch?v=aedEe0Zx_g0
https://www.youtube.com/watch?v=BCXrG1M65HU
The other is about Automatic Memory Reclamation sometimes called Garbage Collection:
https://www.youtube.com/watch?v=u9pbPpZXu18
https://www.youtube.com/watch?v=2nc7IqfshgQ
on this second one I learned a _lot_ because although Andreia and I are working on manual reclamation stuff so we know all the details he mentioned, on GC stuff I'm a bit clueless, except for the basic stuff. Both talks are really insightful and funny.
If you're looking for accurate and deep knowledge of memory reclamation, there is nothing better out there than these talks... except maybe a long chat with Erez himself ;)
Here's my favorite quote by Erez Petrank:
(...) There are several papers which will tell you that there are Lock-Free Garbage Collectors. Do Not trust them! Some of them don't understand what Lock-Freedom is, some of them don't understand what Garbage Collection is, and some of them understand both but do not really look at the details.
GC progress is the big thing that no one looks at. They say: "Ok sure, I don't worry about the garbage collection, I only worry about the program and that is lock-free.", which is not ok, because if the garbage collection does not complete its operation, the program can not complete its operation because it can not allocate. (...)
Showing posts with label garbage collector. Show all posts
Showing posts with label garbage collector. Show all posts
Wednesday, August 16, 2017
Tuesday, February 7, 2017
Cliff Click - A JVM Does That ???
There are a few people that are really knowleadgeable about Java, and
Cliff Click is certainly one of them. One of his latest talks was at
Devoxx and it's named "A JVM Does That???". Youtube link below.
This talk is so rich with content that it's hard to explain what it is about, so I'm just going to mention my favorite parts, but please watch it all if you haven't done so yet.
The explanation on the endless loop of GC cycles when have a cache (data structure) near the limit is just divine:
https://www.youtube.com/watch?v=-vizTDSz8NU&t=24m40s
Or how about the illusion that locks are fast (and fair)
https://www.youtube.com/watch?v=-vizTDSz8NU&t=12m55s
hence the importance of starvation-free locks that I mentioned in my CppCon talk, and the reason behind Andreia and I spending some of our time coming up with new starvation-free lock algorithms like Tidex:
http://dl.acm.org/citation.cfm?id=2851171
http://concurrencyfreaks.com/2014/12/tidex-mutex.html
The part about thread priorities is a nice demonstration of why lock-free and wait-free algorithms are so important (you don't need to care about thread priorities with lock-free and wait-free):
https://www.youtube.com/watch?v=-vizTDSz8NU&t=28m10s
But my favorite is the fact that System.currentTimeMillis() has happens-before guarantees across cores on the HotSpot JVM, because this guarantee allowed us to make a blazing fast queue (which we will show in a future post):
https://www.youtube.com/watch?v=-vizTDSz8NU&t=14m22s
Learning is fun with Cliff Click!
Friday, October 7, 2016
Self-linking and Latency + Life of a Twitter jvm engineer
Today we're going to take a look at the effects of doing self-linking in singly-list based data structures in Java. More specifically, how it changes tail latency in singly-list based queues like the one by Alex Kogan and Erez Petrank.
Back in 2011 Alex Kogan and Erez Petrank showed a multi-producer-multi-consumer wait-free queue.
http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf
To the best of our knowledge, they provided the only reasonably useful and correctly implemented memory-unbounded MPMC wait-free queue (that's a mouthful).
Yes, there are generic wait-free techniques, but using them on a queue is just too slow, and yes, there two other MPMC wait-free algorithms but their implementation has bugs and it's CPU specific.
Even the algorithm by Kogan and Petrank relies on having an automatic Garbage Collector (GC) so they provided their implementation in Java. As the authors themselves mention in their paper, there is currently no wait-free GC, neither implemented in production nor in the literature, which means that this queue is never really wait-free, but let's leave that for another post, and just focus on latency.
How good is this "wait-free" queue when it comes to tail latency?
Pretty good as it turns out. We showed some plots in a previous post:
http://www.concurrencyfreaks.com/2016/08/throughput-vs-latency-and-lock-free-vs.html
Unfortunately, as soon as you start "hammering on it" with lots of contention, a problem appears.
The problem is that the GC will do pauses, really really long pauses.
This queue is based on a singly-linked list, and like all singly-list based data structures when used with a GC, the unused nodes can't just be unlinked from the list, they need to be self-linked by pointing the next pointer to the node itself.
The why this is important is related to how GCs work, and there is a very good explanation in this presentation starting at minute 23
Life of a Twitter jvm engineer - The garbage keeps coming... by Tony Printezis
http://www.youtube.com/watch?v=M9o1LVfGp2A&t=22m45s
which by the way I recommend watching in its entirety, but for the purpose of this post, if you don't know what this self-linking stuff is all about, then go watch ten minutes of it starting at minute 23 and come back and read the rest of this post.
Do you understand now why self-linking is important?
This is really a non-obvious detail of GCs, and the first time I learned about this was several years ago from Doug Lea.
The following code is pretty much what was written in the original paper but with some sun.misc.unsafe added to it:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/Java/com/concurrencyfreaks/queues/KoganPetrankNoSLQueue.java
and in our benchmarks it has GC pauses that go up to 70 seconds.
yes, that's right, seventy seconds during which our 32 core machine is stuck doing nothing except running the GC :-O
Imagine you are reading this blog post on your laptop/tablet and then you click on a link and everything freezes for 70 seconds due to the GC... does that sound reasonable in any way?
You're going to say that this is the GC's fault and that using a JVM with a decent GC like Zing would fix it. I don't know because I don't have access to a JVM with Zing, and I believe that using another GC would improve, but I seriously doubt it will be as effective as doing self-linking.
For a deep-dive on this topic, check out the paper named "A Performance Study of Java Garbage Collectors on Multicore Architectures", particularly figure 1 and table 3:
http://www-public.tem-tsp.eu/~thomas_g/research/biblio/2015/carpen-amarie15pmam-gcanalysis.pdf
The trick to help the GC is to do self-linking of the nodes after dequeueing, but we can't self-link the node where your value is, instead, we self-link the node that points to it, because the node where the value is may still be accessible through head, and we need its next to be valid because it will be used by the next thread calling deq() to obtain its "value". Here is the variant we did, with self-linking of unused nodes:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/Java/com/concurrencyfreaks/queues/KoganPetrankQueue.java
and in our benchmarks it has GC pauses that go up to 3 milliseconds.
Keep in mind that they are exactly the same algorithm, apart from an extra check in help_finish_enq() and for the self-linking in deq() and yet, they have completely different latency profiles.
Below is one example we got with GC logs. In this example the JVM ran out of memory during the benchmark and had to run a full GC which took 17 seconds and then another that took 42 seconds. At the end of the benchmark we call System.gc() and sleep for a while to trigger another GC run and that one took more than 45 seconds.
These 45 seconds are not accounted for in the benchmark which is unfair because the GC is cleaning up the garbage that the queue is producing, so that work should be taken into account when doing benchmarks as well, but anyways, we don't care much about throughput, it's more about latency for us:
##### KPNoSLQueue #####
Starting run...
[GC (Allocation Failure) 3932481K->221057K(15073280K), 17.3218925 secs]
[GC (Allocation Failure) 4153217K->547969K(15073280K), 42.6884304 secs]
Ending run
Number of enqueues/dequeues per sec = 2235
[GC (System.gc()) 1324375K->601121K(15073280K), 45.8331662 secs]
[Full GC (System.gc()) 601121K->8434K(15073280K), 0.0763649 secs]
When we run the same benchmark for the self-linking version, there is still one GC allocation failure during the benchmark, but it takes only 1 millisecond to complete, and the throughput is significantly faster because there is very little waiting for the GC:
##### KPQueue ##### Starting run...
[GC (Allocation Failure) 3932485K->805K(15073280K), 0.0013195 secs]
Ending run
Number of enqueues/dequeues per sec = 3216
[GC (System.gc()) 2541778K->453K(15073280K), 0.0012654 secs]
[Full GC (System.gc()) 453K->327K(15073280K), 0.0142511 secs]
This is the problem with not reclaiming unused memory (nodes) and leaving it up to the GC. Once you go down that path, you need to understand what the GC is doing to somehow make friends with the GC so that it will behave the way you want it to.
Long story short, if you're going to implement a singly-list based queue in Java, you better do self-linking.
Back in 2011 Alex Kogan and Erez Petrank showed a multi-producer-multi-consumer wait-free queue.
http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf
To the best of our knowledge, they provided the only reasonably useful and correctly implemented memory-unbounded MPMC wait-free queue (that's a mouthful).
Yes, there are generic wait-free techniques, but using them on a queue is just too slow, and yes, there two other MPMC wait-free algorithms but their implementation has bugs and it's CPU specific.
Even the algorithm by Kogan and Petrank relies on having an automatic Garbage Collector (GC) so they provided their implementation in Java. As the authors themselves mention in their paper, there is currently no wait-free GC, neither implemented in production nor in the literature, which means that this queue is never really wait-free, but let's leave that for another post, and just focus on latency.
How good is this "wait-free" queue when it comes to tail latency?
Pretty good as it turns out. We showed some plots in a previous post:
http://www.concurrencyfreaks.com/2016/08/throughput-vs-latency-and-lock-free-vs.html
Unfortunately, as soon as you start "hammering on it" with lots of contention, a problem appears.
The problem is that the GC will do pauses, really really long pauses.
This queue is based on a singly-linked list, and like all singly-list based data structures when used with a GC, the unused nodes can't just be unlinked from the list, they need to be self-linked by pointing the next pointer to the node itself.
The why this is important is related to how GCs work, and there is a very good explanation in this presentation starting at minute 23
Life of a Twitter jvm engineer - The garbage keeps coming... by Tony Printezis
http://www.youtube.com/watch?v=M9o1LVfGp2A&t=22m45s
which by the way I recommend watching in its entirety, but for the purpose of this post, if you don't know what this self-linking stuff is all about, then go watch ten minutes of it starting at minute 23 and come back and read the rest of this post.
Do you understand now why self-linking is important?
This is really a non-obvious detail of GCs, and the first time I learned about this was several years ago from Doug Lea.
The following code is pretty much what was written in the original paper but with some sun.misc.unsafe added to it:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/Java/com/concurrencyfreaks/queues/KoganPetrankNoSLQueue.java
and in our benchmarks it has GC pauses that go up to 70 seconds.
yes, that's right, seventy seconds during which our 32 core machine is stuck doing nothing except running the GC :-O
Imagine you are reading this blog post on your laptop/tablet and then you click on a link and everything freezes for 70 seconds due to the GC... does that sound reasonable in any way?
You're going to say that this is the GC's fault and that using a JVM with a decent GC like Zing would fix it. I don't know because I don't have access to a JVM with Zing, and I believe that using another GC would improve, but I seriously doubt it will be as effective as doing self-linking.
For a deep-dive on this topic, check out the paper named "A Performance Study of Java Garbage Collectors on Multicore Architectures", particularly figure 1 and table 3:
http://www-public.tem-tsp.eu/~thomas_g/research/biblio/2015/carpen-amarie15pmam-gcanalysis.pdf
The trick to help the GC is to do self-linking of the nodes after dequeueing, but we can't self-link the node where your value is, instead, we self-link the node that points to it, because the node where the value is may still be accessible through head, and we need its next to be valid because it will be used by the next thread calling deq() to obtain its "value". Here is the variant we did, with self-linking of unused nodes:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/Java/com/concurrencyfreaks/queues/KoganPetrankQueue.java
and in our benchmarks it has GC pauses that go up to 3 milliseconds.
Keep in mind that they are exactly the same algorithm, apart from an extra check in help_finish_enq() and for the self-linking in deq() and yet, they have completely different latency profiles.
Below is one example we got with GC logs. In this example the JVM ran out of memory during the benchmark and had to run a full GC which took 17 seconds and then another that took 42 seconds. At the end of the benchmark we call System.gc() and sleep for a while to trigger another GC run and that one took more than 45 seconds.
These 45 seconds are not accounted for in the benchmark which is unfair because the GC is cleaning up the garbage that the queue is producing, so that work should be taken into account when doing benchmarks as well, but anyways, we don't care much about throughput, it's more about latency for us:
##### KPNoSLQueue #####
Starting run...
[GC (Allocation Failure) 3932481K->221057K(15073280K), 17.3218925 secs]
[GC (Allocation Failure) 4153217K->547969K(15073280K), 42.6884304 secs]
Ending run
Number of enqueues/dequeues per sec = 2235
[GC (System.gc()) 1324375K->601121K(15073280K), 45.8331662 secs]
[Full GC (System.gc()) 601121K->8434K(15073280K), 0.0763649 secs]
When we run the same benchmark for the self-linking version, there is still one GC allocation failure during the benchmark, but it takes only 1 millisecond to complete, and the throughput is significantly faster because there is very little waiting for the GC:
##### KPQueue ##### Starting run...
[GC (Allocation Failure) 3932485K->805K(15073280K), 0.0013195 secs]
Ending run
Number of enqueues/dequeues per sec = 3216
[GC (System.gc()) 2541778K->453K(15073280K), 0.0012654 secs]
[Full GC (System.gc()) 453K->327K(15073280K), 0.0142511 secs]
This is the problem with not reclaiming unused memory (nodes) and leaving it up to the GC. Once you go down that path, you need to understand what the GC is doing to somehow make friends with the GC so that it will behave the way you want it to.
Long story short, if you're going to implement a singly-list based queue in Java, you better do self-linking.
Saturday, July 30, 2016
Cliff Click on VM Design Choices
Whenever I see a presentation online by Cliff Click I just jump at it. There is just so much content in a single presentation, maybe it's because he speaks really fast, but maybe, just maybe, it's because this guy is really good. :-O
If you ever wondered how to make your own JVM, how HotSpot works, how a SafePoint is implemented, some little known truths about Garbage Collection in the JVM (did you know there is a lock on the thread's stack that the GC/thread acquire?), even how to make a scalable lock, and more, much much more, then watch this video!
I'm pretty sure you'll learn something, at least some detail about the inner workings of a JVM.... huhhh unless of course, you are Cliff Click yourself, or you worked with him in this stuff, or you watched one of these presentations live, in which case, you already know everything that's being said. lol
The part about GCs was amazing, and so was the one about inlining.
One thing I really like is that he's one of the very few people who make a distinction between performance for throughput and performance for latency (Andreia and I we just call it throughput and latency).
I had to watch it twice and a third time will be needed to get all the details. And if you missed some details, try watching the rerun of the same presentation here:
Really cool stuff
If you ever wondered how to make your own JVM, how HotSpot works, how a SafePoint is implemented, some little known truths about Garbage Collection in the JVM (did you know there is a lock on the thread's stack that the GC/thread acquire?), even how to make a scalable lock, and more, much much more, then watch this video!
I'm pretty sure you'll learn something, at least some detail about the inner workings of a JVM.... huhhh unless of course, you are Cliff Click yourself, or you worked with him in this stuff, or you watched one of these presentations live, in which case, you already know everything that's being said. lol
The part about GCs was amazing, and so was the one about inlining.
One thing I really like is that he's one of the very few people who make a distinction between performance for throughput and performance for latency (Andreia and I we just call it throughput and latency).
I had to watch it twice and a third time will be needed to get all the details. And if you missed some details, try watching the rerun of the same presentation here:
Really cool stuff
Saturday, July 12, 2014
Martin Thompson on Top-10 performance myths
Here is a nice presentation on performance by Martin Thompson, covering hardware and software,
http://www.infoq.com/presentations/top-10-performance-myths
I particularly liked the part about Immutable (Persistent) data structures and magic ponies :)
And what he said about "know your data structures".
(...) I think we're in an interesting era where people who just recall facts are almost redundant, because you can just google for them (the facts).
What's really useful is people who can reason. People who are aware of "I need to know what that is, given the characteristics of what I'm doing, and I can lookup it up."
It's that curiosity and ability to reason that I would search for during an interview process (...)
As always, good stuff from Martin.
For more, check out his blog.
http://www.infoq.com/presentations/top-10-performance-myths
I particularly liked the part about Immutable (Persistent) data structures and magic ponies :)
And what he said about "know your data structures".
(...) I think we're in an interesting era where people who just recall facts are almost redundant, because you can just google for them (the facts).
What's really useful is people who can reason. People who are aware of "I need to know what that is, given the characteristics of what I'm doing, and I can lookup it up."
It's that curiosity and ability to reason that I would search for during an interview process (...)
As always, good stuff from Martin.
For more, check out his blog.
Subscribe to:
Posts (Atom)