Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

GC Tuning Confessions of a Performance Engineer

slideshare.net

Post reply on HN
Print view View original

71–80 of 98 posts

Re: GC Tuning Confessions of a Performance Engineer

#71

Post by dumael »

pron wrote: post #13
banachtarski wrote: post #9

Earlier quoted context omitted.

You will never beat a tuned system without GC with a GC system because of all the instructions necessary to traverse references and such. Having lots of cores and lots of RAM just means you can eat the cost more easily. It just means you can afford to let the VM do the work instead of the programmer. Also, no matter how much RAM you have, cache sizes are more or less the same, and cache line misses hurt.

> You will never beat a tuned system without GC with a GC system because of all the instructions necessary to traverse references and such. That's not at all how it works. The generational hypothesis means that most objects die young. Allocating them is a simple, uncontended pointer bump in the thread-local allocation buffer (as fast as stack allocation), and freeing them is free, as they are never traversed. They ar…

I have to completely disagree. Generation GC beats malloc/free in the case of 'all objects allocated on the heap' when: sizeof(survivors) + cost of traversing survivors pointer fields + rewriting the remembered set Freeing objects in Generational GC requires computing the transitive closure relation of the stack and any "global variable" for the set of objects in the generational allocation arena so that all live objects there can be identified. I. E. For the stack, all "Global" variables, and the set of marked cards/(The record of objects updated with old to new references) : Find all live objects, copy them into the next arena while rewriting references.

Oh, were write barriers that not mentioned? Generation GC requires write barriers. Every update through a pointer unless provably required by a compiler turns "a->b = c"; into "if(b is in generational region) { record update of b;} a->b = c".

If you want to be able to move objects arounds cheaply, writes through pointers transform into small subroutines. For some GCs, reads through pointers are also small subroutines.

And some Generational GCs do card marking over object marking. Let's traverse $CHUNKOFMEMORY on the probabilistic notion that if something was updated, something close by was updated. (Otherwise we can have Sequential Store Buffers which record exactly which objects were changed)

Stack allocation (either explicit or deduced) is probably the fastest method of object allocation there is. Generational GC is on average going to be fast but can suffer horrendous worst case scenarios unless you GC is designed/engineered to switch between thread local allocation arenas.

Full disclosure: Despite my whining about GCs, I did do my Phd in them.

Re: GC Tuning Confessions of a Performance Engineer

#72

Post by dumael »

vitalyd wrote: post #20
pron wrote: post #14

Earlier quoted context omitted.

> traversal is proportional to the number of pointers (rooted or dangling) in the heap and stack at the time of running. That's not quite how it works. Traversal is proportional to the number of pointers changed since the last collection (HotSpot's GCs do card marking). I do agree there are tradeoffs, but they're much more nuanced than that. There is certainly a footprint tradeoff, and there is a latency tradeoff (th…

A card in the card table covers more than one object, so the entire dirty card needs to be scanned. Card marks only help with old->young references, and stack based roots still need to be visited each time, irrespective of what happened in the last collection.

Except card marking (this region of the heap was changed) is only one way of flagging changes. It's entire possible to instead record the address of objects unconditionally and then flag them as they are visiting during a generation.

Re: GC Tuning Confessions of a Performance Engineer

#73

Post by dumael »

vitalyd wrote: post #28
outworlder wrote: post #26

Earlier quoted context omitted.

> I wonder, isn't it working on the stack much faster than working on the heap anyway? Working on GC-managed memory is faster still. Remember, not all allocations involve an actual heap allocation. Conversely, not all deletions cause a 'free()' operation on the heap.

> Working on GC-managed memory is faster still. Care to elaborate?

Replying to GP comment and you as such.

Hypothetically, (I'm not sure how widespread this technique is), some (Java) compilers turn heap allocations into stack allocations when they can prove that transitively an allocated object does not become reachable from other threads.

This general technique "escape analysis", i.e. "a reference to this object /escapes/ a given reachability type[1]", can be used to transform general heap allocations into thread local or stack allocations.

[1] Let me define reachability type as {can be accessed from anything, can be accessed from this thread only but is of indefinite lifetime, can be accessed from this thread only and it's reference is not take by any object allocated onto my local heap, ...}

Re: GC Tuning Confessions of a Performance Engineer

#74

Post by dumael »

jokoon wrote: post #23

I wonder, isn't it working on the stack much faster than working on the heap anyway? So when you query data on the heap, shouldn't you just query larger objects to put it on the stack, and work from there, instead of using the heap so often ? With that in mind wouldn't that render garbage collecting almost irrelevant if your code is well designed, by not working too much on the heap ? It's true that more ram makes th…

Garbage collection worries about reachability of objects, not of access patterns. Some GC setups may not apply read/write barriers to stack objects as they are not required.

The difficultly with stack centric working is that you have to ensure that any object produced that is put back into the heap only references heap objects. Otherwise, by any sane language/style definition, you've made a mistake in referencing stack objects from the heap.

Accesses to the stack or heap, except in very specific circumstances[1] are equal but allocation/deallocation process are widely different.

Avoiding introducing GC work has/(can have) the tendency to "fight the language" problems. Consider writing Haskell code that does not allocate on the heap for example, it's damn near impossible. Otoh a Java program can shift some heap allocations into stack allocations.

[1] Afaik, some intel processors have small dedicated D-caches from stack relative load/stores. On the order of 128 bytes. I am probably wrong though.

Re: GC Tuning Confessions of a Performance Engineer

#75

Post by vitalyd »

dumael wrote: post #73
vitalyd wrote: post #28

Earlier quoted context omitted.

> Working on GC-managed memory is faster still. Care to elaborate?

Replying to GP comment and you as such. Hypothetically, (I'm not sure how widespread this technique is), some (Java) compilers turn heap allocations into stack allocations when they can prove that transitively an allocated object does not become reachable from other threads. This general technique "escape analysis", i.e. "a reference to this object /escapes/ a given reachability type[1]", can be used to transform gen…

Hotspot JVM C2 compiler does this optimization, with varying degree of success but generally brittle and completely opaque. It doesn't actually stack allocate them technically speaking, just scalarizes them into registers. Should also mention that this requires sufficient inlining to take place at minimum (unfortunately, hotspot does not do flow sensitive analysis so any conditional logic that makes the object escape, even if not taken, will be regarded as escaping - graal handles this better), which doesn't always happen for a variety of reasons.

But what does this have to do with heap being faster than stack? This is doing roughly the same thing as a compiler that supports explicit stack allocations.

Re: GC Tuning Confessions of a Performance Engineer

#76

Post by vitalyd »

dumael wrote: post #72
vitalyd wrote: post #20

Earlier quoted context omitted.

A card in the card table covers more than one object, so the entire dirty card needs to be scanned. Card marks only help with old->young references, and stack based roots still need to be visited each time, irrespective of what happened in the last collection.

Except card marking (this region of the heap was changed) is only one way of flagging changes. It's entire possible to instead record the address of objects unconditionally and then flag them as they are visiting during a generation.

You could but it's likely to perform worse for common case. Where are you going to record the addresses? How are you going to size that buffer? Card table is fixed size, and doesn't care whether you're using compressed pointers or full blown word sized ones. Cards also benefit from cache locality if recording objects in the same card. Marking a card clean is dirt cheap, and incremental cleaning is cheaper than removing entries individually from an exact buffer.

The downside to card marking is the impreciseness but with java being very reference heavy, I don't know how much that is a problem. Secondary problem is false sharing of memory when multiple mutators write in there; Hotspot, e.g. has a special flag to enable conditional marking, but it's not on by default.

Re: GC Tuning Confessions of a Performance Engineer

#77

Post by pron »

vitalyd wrote: post #67
pcwalton wrote: post #62

Earlier quoted context omitted.

> yes, vitalyd is going to mention traversals, but if the traversals are interesting, they point to objects in the arbitrary cost anyway I'm going to mention this too. I don't understand what you mean by "they point to objects in the arbitrary cost anyway". The fact of the matter is that you have to trace all objects at some point. > Now, I think it is far easier to manage a stack scope in a GCed environment than an…

>I'm going to mention this too. I don't understand what you mean by "they point to objects in the arbitrary cost anyway". The fact of the matter is that you have to trace all objects at some point. I think he means that if you have object references, then those references are interesting for the application itself, and not just for the GC tracer. However, I don't buy this statement simply because, even if you elect t…

> I think he means that if you have object references, then those references are interesting for the application itself, and not just for the GC tracer.

What I mean is that either those refs are permanent -- in which case they won't be traced -- or arbitrary -- in which case it's really more of an "arbitrary" problem than a "permanent" one.

> The "arbitrary" scope better not be really arbitrary since even GCs are typically tuned for the generational hypothesis

By arbitrary I mean long-lived (old-gen) but not permanent. In short: database data.

> For things like databases where object lifetime is in the hands of the user, arena/slab allocators work just fine.

What you are saying is that you never truly have arbitrary-lifetime objects, and I strongly disagree with that.

> the time spent there may end up exceeding arena impl costs.

Even if you're right about arenas (which I don't agree with), you believe that a runtime designed to target the vast majority of server software should force developers to figure out lifetimes and that that may be beneficial to them? I mean, I even mentioned arena just to get that much closer to 100% performance. Even without them Java gets to at least 90%. Are you suggesting that the vast majority of projects in the world are interested in doing more work that is likely error prone just to get that 10% at best?

Re: GC Tuning Confessions of a Performance Engineer

#78

Post by pron »

vitalyd wrote: post #25
pcwalton wrote: post #24

Earlier quoted context omitted.

I think the solution is to use the right memory management tool for the job. pron is right that GC can be helpful for concurrent data structures (where the non-GC approach, hazard pointers, is basically just a GC), for instance. GC is also great when your objects have truly dynamic lifetime, such as open files in Unix from the kernel's point of view. But GC for all data tends to be overkill when your goal is to maxim…

GC does help with ABA style concurrent problems, and it also simplifies the places where you simply don't care (slow/uncommon paths). But concurrent data structures are a special case, and likely, not always the best anyway since even though they scale much better than locks, with enough writers and cores, the cache coherence traffic is going to swamp the application. I do agree with the flexibility comment. A hybrid…

> GC does help with ABA style concurrent problems

I wasn't just referring to that. GC helps with pretty much any concurrent data structure, lock-free or not. For example, read-write locks don't scale too well (certainly no beyond the core count we're quickly coming up against on servers), and GC enables easy optimistic locking.

Re: GC Tuning Confessions of a Performance Engineer

#79

Post by pron »

dumael wrote: post #71
pron wrote: post #13

Earlier quoted context omitted.

> You will never beat a tuned system without GC with a GC system because of all the instructions necessary to traverse references and such. That's not at all how it works. The generational hypothesis means that most objects die young. Allocating them is a simple, uncontended pointer bump in the thread-local allocation buffer (as fast as stack allocation), and freeing them is free, as they are never traversed. They ar…

I have to completely disagree. Generation GC beats malloc/free in the case of 'all objects allocated on the heap' when: sizeof(survivors) + cost of traversing survivors pointer fields + rewriting the remembered set Freeing objects in Generational GC requires computing the transitive closure relation of the stack and any "global variable" for the set of objects in the generational allocation arena so that all live obj…

You mean sizeof(survivors whose references changed since last collection). You pay for those write barriers for a reason.

> Stack allocation (either explicit or deduced) is probably the fastest method of object allocation there is. Generational GC is on average going to be fast but can suffer horrendous worst case scenarios unless you GC is designed/engineered to switch between thread local allocation arenas.

I agree, but on large servers with lots of RAM, the total amount of memory that can possibly be managed on stacks is Now you can say that with all that data in RAM, the GC heap is a huge waste of RAM and the worst-case GC pause would be terrible, to which I say (I write in-memory databases in Java) that most of that data is user data and is kept off heap. Its lifetime is indeed arbitrary, but objects are deleted precisely when the user chooses to delete them, and that happens when they're protected by a lock. The much more interesting data is the indices, for which a GC helps greatly by allowing optimistic locking and other forms of scalable concurrency, and only those are kept on the heap.

Re: GC Tuning Confessions of a Performance Engineer

#80

Post by pjmlp »

banachtarski wrote: post #69
pjmlp wrote: post #46

Earlier quoted context omitted.

Well I started coding in 1986, and have seen quite a few screw ups. So yeah, small teams it works great. Now scale that to developer teams > 30 on average, with high turnaround and multiple outside partners coming and going on project basis. I have seen what off-shoring does to C and C++ code bases...

How many engineers work on, say, the Unreal Engine. The linux kernel? Windows? Do you think any of that stuff would work even marginally well running on the JVM (assuming the JVM had native driver support)? I don't quite follow your claims, nor do I put any stock in the tenure of your programming career. As for the off-shoring point, off-shoring is going to create questionable quality code regardless of the programmi…

> How many engineers work on, say, the Unreal Engine. The linux kernel? Windows?

So you just provided me examples where developers tend to be highly skilled just to get a foot in the door.

Yet, the CVE list gets updated regularly with memory corruption exploits for them.

https://cve.mitre.org/cgi-bin/cvekey.cgi?keyword=double+free

Or if you prefer, just for Linux

https://cve.mitre.org/cgi-bin/cvekey.cgi?keyword=linux+doubl...

> Do you think any of that stuff would work even marginally well running on the JVM (assuming the JVM had native driver support)?

Actually, are you aware that some military weapon systems are being driven with JVMs?

Anyway automatic memory management doesn't mean automatically a JVM, there are quite a few other ways.

Another fun fact, Unreal Engine and Windows are written mostly in C++. A language considered too bloated and slow to be usable for anything serious by mainstream developers in the early 90's.

Also both use automatic memory management on their systems. Unreal has a kind of GC library. Windows nowadays has COM almost everywhere with reference counting.

> I don't quite follow your claims, nor do I put any stock in the tenure of your programming career.

Apparently some well known Fortune 100 companies and research institutes had another opinion.

> As for the off-shoring point, off-shoring is going to create questionable quality code regardless of the programming language.

The point being that those projects tend to go for cheap developers, so no, not everyone can deal with manual memory management.

Post reply on HN