3 ms·
I don't think that there's anything magical about C4. All the basics are discernible from this presentation: http://www.youtube.com/watch?v=5uljtqyBLxI http://w
by wahern 12y ago
I don't think that there's anything magical about C4. All the basics are discernible from this presentation: http://www.youtube.com/watch?v=5uljtqyBLxI http://www.youtube.com/watch?v=5uljtqyBLxI
Azul originally started out as a hardware company. A pauseless collector is easy as long as you have transactional memory (at a minimum hardware which supports strong LL/SC, allowing you to build the rest in software). No commodity CPUs support this, then or now, so Azul's first product was a specialized CPU and memory architecture with real transactional memory semantics.
But nobody wants to buy specialized hardware these days. So they ended up having to emulate transactional memory on x86. That means _emulating_ the memory architecture of their original CPU. Again, there's no secret sauce to do doing this. Things like QEMU are free--which is to say, many people know how to do it. It just takes a lot of programmer hours to build it, and many, many more to optimize it.
Long story short, Azul's collector is truly pauseless, but its transactional throughput in the vast majority of workloads sucks because it's an emulator (for the JVM) built atop another emulator (for their original memory architecture). And while you can speed up emulating the JVM using JIT techniques, that doesn't work for emulating a transactional memory architecture. There are endless tweaks you can make, including playing around with memory page tables, etc, but at the end up the day you're still stuck emulating the semantics you need, causing huge latencies relative to your clock speed, which already suck on Ghz scale systems.
This won't change anytime time soon. Even Intel's new TSX features are not strong enough to be able to implement true transactional memory. Real transactional memory requires a way to atomically signal contention for every word of memory, or at least lines of words. It requires not only a specialized CPU, but specialized memory controllers, and specialized memory. Something like TSX would only provide a marginal performance improvement for C4, if anything at all, because almost all their effort goes into arranging to avoid locking, not making locking faster.
- giltene 12y agoWhile it's true that there is nothing magical in C4, pretty much everything you describe here is wrong (as in the exact opposite of what is going on). Specifically: - C4 makes no use of hardware transactional memory. - C4 works great (and natively) on commodity x86-64 cores. - C4 does not emulate anything (not memory architecture, not HTM). - C4's transactional throughput kicks ass. If you want to know how C4 works, all you need to do is read the actual C4 ISMM paper: http://www.azulsystems.com/sites/default/files/images/c4_paper_acm.pdf http://www.azulsystems.com/sites/default/files/images/c4_pap... <And yes, I'm one of the authors> How you got to your posted conclusions from the link you posted is a mystery to me. Cliff doesn't say anything much about the GC mechanism there: he is talking about lessons learned in designing custom hardware. And yes, Vega had some cool GC-assist features, but they are in no way part of the C4 collector mechanism. Since you raised the bogus, unsubstantiated assertion that "[Zing's] transactional throughput in the vast majority of workloads sucks" based purely on your mis-interpretation of what C4 actually does, I feel I must correct that notion. To do that, I'll point out that Zing (with C4) is currently used, in production, to run some of the highest transactional throughput and most latency sensitive applications in the world. Zing's sustainable throughput (the throughput at which the system still meets the required SLA) is generally dramatically better than other JVMs running on exactly the same modern x86 hardware. Yes, you read that right: Zing gets more production-worthy TPS out of the same x86 hardware. Not less. This is why people who actually need good throughput and good latency tend to graduate to using Zing, and start enjoying time in their hammocks as a result. See http://mail.openjdk.java.net/pipermail/hotspot-gc-use/2014-October/002045.html http://mail.openjdk.java.net/pipermail/hotspot-gc-use/2014-O... for a happy example. C4 is being used in everything from low latency trading (Algo, HFT, smart routing wire risk) to Online Retail (think black Friday workloads) and travel sites. C4 is used for everything from 1GB compute-heavy and messgaing workloads to 1TB data-heavy analysts applications. It powers big data workloads. It powers search. It powers Java servers of all kinds, big and small. And none of those are complaining about throughput. Quite the opposite. Peace.
- wahern 12y agoYou're wrong. If you read their published algorithm and are familiar with lock-less algorithms, it's clear that theirs is a transactional memory algorithm. Specifically, their LVB primitive. If this isn't obvious to you, I would recommend reading the seminal transactional memory algorithms from the 1970s and 1980s, including everything written by Hoare. Most of those are available from the ACM library. You particularly need to pay close to attention to how wait-free algorithms are achieved. "Transactional memory" is not a marketing term, nor a synonym for a particular set of CPU instructions. It's a class of lock-free algorithms, especially lock-free, wait-free algorithms. And the C4 collector very clearly fits into that class of algorithms. It's use of page remapping and read/write page protections is precisely how you would emulate strong transactional memory primitives on x86. I think this terse quotation (from their own research paper) sums up the relationship between the Vega hardware and the Linux software-based implementation: "Azul has created commercial implementations of the C4 algorithm on three successive generations of its custom Vega hardware (custom processor instruction set, chip, system, and OS), as well on modern X86 hardware. While the algorithmic details are virtually identical between the platforms, the implementation of the LVB semantics varies significantly due to differences in available instruction sets, CPU features, and OS support capabilities." (http://www.azulsystems.com/sites/default/files/images/c4_paper_acm.pdf http://www.azulsystems.com/sites/default/files/images/c4_pap...) Regarding the performance of C4, the reason Azul doesn't publish TPC benchmarks is because there's no avoiding the immense costs of their page mapping hacks. From the paper above: "the garbage collector needs to sustain a page remapping at a rate that is 100x as high as the sustained object allocation rate for comfortable operation." Page remapping is insanely expensive at the micro-granularity needed. They mitigate the cost by batching requests, but it's still significant. Furthermore, they must use atomic reads and writes for internal pointers. Those are cache killers. I never said C4 can't be faster for particular workloads. Obviously for workloads sensitive to latency a pauseless collector can be faster overall. But as a general matter, those workloads are not in the majority. Ergo, for the majority of workloads C4 will not be faster, at least not on commodity hardware architectures. You can continue to believe the hype, and believe that Azul possesses some sort of magical fairy dust, using techniques entirely beyond the comprehension of mere mortals. Or you can read about and learn how it _actually_ works. Their algorithm and implementations are all laudable and significant achievements. But there's nothing magical or secret about them.
- mjpt777 12y agoI'm sorry but this analysis is completely wrong. I don't work for Azul but have used C4 and spent time studying it. C4 does not use transactional memory, it does however employ a very elegant lock-free algorithm which allows continuous concurrent compacting collections. BTW that is why it is called C4. I can tell you from first hand experience that is does not have throughput issues. The truth is quite the opposite as it is the only JVM I've found scales well on large core count or large memory systems. Do you have experimental evidence to back up your claims or are they just conjecture? Having studied C4 it is important to note that to get the best out of it you need to allow it to avail of a large heap. If your mindset is to keep the heap small, as you would with many other collectors, then you will be restricting the C4 collecting algorithm from performing at its best. Don't be shy, give it a big heap to play with. The obvious consequence to this is that C4 is not ideal for constrained memory systems - but that is not the world the majority of our servers live in today. Amendment: All the above applies to Zing (C4) on Intel x86_64.
- wahern 12y agoThere's no other way to implementation a lock-less compacting (i.e. copying) collector than by using transactional memory algorithms. Period. I've never used C4, and I don't even program in Java. But I have personally studied and implemented transactional memory algorithms, and C4 fits perfectly into that mold. In fact, what originally made me interested in transactional memory was figuring out how C4 worked. And I did figure it out. I figured it out even before they published their 2011 paper, which I just discovered. And unsurprisingly everything in there is precisely as I predicted. It couldn't have been otherwise once you understand the fundamentals.
- mjpt777 12y agoI asked the question if this is based on conjecture or experimental evidence. I'm happy to base my view on experimental evidence from my own research and testing.
- giltene 12y agoUm. There are 30 years worth of academic publications covering concurrent compacting collectors that don't need or use transactional memory, and are implementable on commodity hardware with no emulation or specialized instructions. C4 is just one of many examples of this fact. Sure, C4 does some cool new things, but trying to move or copy memory transactionally isn't one of them. Whatever it is you think you figured out about how C4 works seems to be wrong. You may want to re-examine those fundamentals.
- bobinator61 12y agoComplete speculation
- wahern 12y agoIt was informed speculation. Fortunately they documented their implementation in a 2011 paper, which verifies all my assumptions. See http://www.azulsystems.com/sites/default/files/images/c4_paper_acm.pdf http://www.azulsystems.com/sites/default/files/images/c4_pap... Their use of page remapping and read/write page protections is precisely how you would emulate strong transactional memory primitives on x86, allowing you to leverage well-known lock-free and wait-free algorithms. See my longer response else-thread.
- giltene 12y agoThe 2011 C4 paper doesn't say any of the things you keep attributing to it. Just because it may also be possible to use page remapping to save on toilet paper or rescue kittens doesn't mean that's what we do with it. We do what we say we do. No conjecture needed.