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

Conservative GC: Is It Really That Bad?

excelsiorjet.com

Post reply on HN
Print view View original

41–48 of 48 posts

Re: Conservative GC: Is It Really That Bad?

#41

Post by bjourne »

aidenn0 wrote: post #30
dmytrish wrote: post #10

I am not an expert in garbage collection techniques, but this article does not even mention locality of reference (copying GCs improve locality on each compaction) and how many cache misses are introduced by increased fragmentation. Are there any benchmarks on this?

On SBCL the bigger win for using a copying collector isn't the locality of reference (which helps with some loads, but hurts with others), but rather the fact that you can make an allocation be about two instructions in the non-GC case (pointer increment plus a bounds check). I hadn't spent a lot of time thinking about how much faster this is than malloc/free until a question came up the other day here on HN to the e…

It never gets as fast as stack allocating variables. Consider a loop:

while(1) { Integer n = new Integer(....) vs int n = ... }

A C compiler would allocate the n variable on the stack, making the "allocation" completely free. But in a GC:ed language, the n variable would be bump allocated once every loop. That wouldn't in itself be so costly, but every so often, a GC cycle would be needed as the garbage accumulates. Furthermore, in C the address of the n variable stays in place while in a GC:ed language it moves a bit for each loop.

That is why escape analysis is a fruitful optimization. It takes heap allocated objects and attempts to stack allocate them, similar to how a C compiler would do it.

Re: Conservative GC: Is It Really That Bad?

#42

Post by kazinator »

foodzee wrote: post #39
kazinator wrote: post #37

Earlier quoted context omitted.

By your reasoning, everything is manually allocated. When we call (cons 1 2) in Lisp, that's a manually allocated cons. Most objects come into life due to some "manual" construction in the program! > The thread must die by explicit programmatic action, which in turn will free its allocated block of stack memory. Simply, no. A thread can recurse through some function activations and then hit an exit statement which te…

> Other threads can have pointers into that thread's stack, so the stack must not be reclaimed until they let go. > For instance, a tread allocates a reply box on the stack and calls some message passing API to send a message, whereby it registers the reply box. That API now has a pointer into the thread's stack. Suppose the thread dies before unregistering the reply box. If that can happen, the stack has to stick ar…

> How exactly can a thread correctly die in such a way that frame of method that allocated the reply box on-stack is not cleaned up from it first?

The thread could die incorrectly in that way.

> Why the method even allocated shared data structure on its own stack

Done for efficiency or when it's not desirable to have to check and recover from a failure to allocate such a structure. E.g. DECLARE_WAITQUEUE macro in Linux kernel:

https://elixir.bootlin.com/linux/v4.3/source/include/linux/w...

How blocking is implemented in Linux is that tasks declare wait queue nodes on the stack, register these into a queue, then change themselves to a sleep state and call the scheduler.

> why would anyone consider thread which is actively waiting for something dead and try to reclaim its stack?

What reclaims the stack isn't that "anyone"; it's garbage collection. It's plausible like this. Suppose the messaging API is responsible for dequeuing the waiter. The messaging API walks the queue, depositing replies into the reply boxes and dequeueing (without caring whether the associated threads are alive or dead).

When it dequeues the dead thread's reply box, that stack then becomes unreachable. Now it is eligible for reclamation.

Re: Conservative GC: Is It Really That Bad?

#43

Post by ScottBurson »

bjourne wrote: post #41
aidenn0 wrote: post #30

Earlier quoted context omitted.

On SBCL the bigger win for using a copying collector isn't the locality of reference (which helps with some loads, but hurts with others), but rather the fact that you can make an allocation be about two instructions in the non-GC case (pointer increment plus a bounds check). I hadn't spent a lot of time thinking about how much faster this is than malloc/free until a question came up the other day here on HN to the e…

It never gets as fast as stack allocating variables. Consider a loop: while(1) { Integer n = new Integer(....) vs int n = ... } A C compiler would allocate the n variable on the stack, making the "allocation" completely free. But in a GC:ed language, the n variable would be bump allocated once every loop. That wouldn't in itself be so costly, but every so often, a GC cycle would be needed as the garbage accumulates.…

> But in a GC:ed language, the n variable would be bump allocated once every loop.

Citation needed. I don't know of any GCed language that heap-allocates local variables in this way (well, maybe SML/NJ does, but I doubt it). Certainly not Java or any Common Lisp I've ever used.

But I agree with your larger point: heap allocation is never quite as fast as stack allocation, once you factor in the additional GC load. I don't actually know how close it gets with modern collectors; would love to see some numbers.

Re: Conservative GC: Is It Really That Bad?

#44

Post by dbg_nsk »

bjourne wrote: post #40

A safepoint in x86 is nothing more than the instruction mov [rip+0x1234], eax. That shouldn't cause a major slowdown? Also, safepoints are useful for features other than gc. For example, you can inspect a running thread's callstack. That is useful when debugging and when objectifying a thread's state. Stack maps can be made a bit smaller by pushing and popping all registers from the stack during gc. That way, you onl…

Right, but even a single instruction placed on every backward branch and at the epilogue of every method causes noticeable impact on the performance. This is especially important in highly optimized code and that's why optimizing compilers like HotSpot C2 (and JET as well) try to remove as many safepoints as possible. Sometimes it even causes troubles like in this case:

https://bugs.openjdk.java.net/browse/JDK-5014723

Good point about inspecting thread's callstack. Indeed, with conservative GC we had a problem: many popular profilers were incompatible with JET because they inspect threads at safepoints and we had none. When we implemented the precise GC, this problem disappeared and it was an additional benefit for us. However, there are alternative ways to gather thread's callstack out of safepoint. We use them to avoid safepoint bias in our profiler. You can read more about it here:

https://www.excelsiorjet.com/blog/articles/portable-profiler...

----

Thanks for kind words! I'm glad that you liked the post!

Re: Conservative GC: Is It Really That Bad?

#45

Post by aidenn0 »

bjourne wrote: post #41
aidenn0 wrote: post #30

Earlier quoted context omitted.

On SBCL the bigger win for using a copying collector isn't the locality of reference (which helps with some loads, but hurts with others), but rather the fact that you can make an allocation be about two instructions in the non-GC case (pointer increment plus a bounds check). I hadn't spent a lot of time thinking about how much faster this is than malloc/free until a question came up the other day here on HN to the e…

It never gets as fast as stack allocating variables. Consider a loop: while(1) { Integer n = new Integer(....) vs int n = ... } A C compiler would allocate the n variable on the stack, making the "allocation" completely free. But in a GC:ed language, the n variable would be bump allocated once every loop. That wouldn't in itself be so costly, but every so often, a GC cycle would be needed as the garbage accumulates.…

To be fair, I said "approximately" The cost of a nursery GC in SBCL is O(n+m) where n is the number of live objects in the nursery and m is the number of GC roots. If this code is all you are running then n will be 1, so it's just scanning the roots, which only happens when you have allocated enough integers to fill the nursery, so gets amortized across thousands of loop iterations.

Re: Conservative GC: Is It Really That Bad?

#46

Post by yxhuvud »

dbg_nsk wrote: post #36
yxhuvud wrote: post #34

Earlier quoted context omitted.

It is mentioned in one of the papers (or possibly the doctoral thesis, which is nice as it gives an overview of the whole chain of improvements) that it can still happen but that it is much better compared to what they benchmarked it against (boehm, iirc). Hard to tell if it delivers what it promises though..

It would be very interesting to run our sample with Timers on this GC. In that paper I found a link to their implementation, but unfortunately it is unavailable.

Link is dead, but code is on Github somewhere. Dunno where I found the link to it but I am away from computer for a few days so I can't really look it up for you.

Re: Conservative GC: Is It Really That Bad?

#47

Post by bjourne »

ScottBurson wrote: post #43
bjourne wrote: post #41

Earlier quoted context omitted.

It never gets as fast as stack allocating variables. Consider a loop: while(1) { Integer n = new Integer(....) vs int n = ... } A C compiler would allocate the n variable on the stack, making the "allocation" completely free. But in a GC:ed language, the n variable would be bump allocated once every loop. That wouldn't in itself be so costly, but every so often, a GC cycle would be needed as the garbage accumulates.…

> But in a GC:ed language, the n variable would be bump allocated once every loop. Citation needed. I don't know of any GCed language that heap-allocates local variables in this way (well, maybe SML/NJ does, but I doubt it). Certainly not Java or any Common Lisp I've ever used. But I agree with your larger point: heap allocation is never quite as fast as stack allocation, once you factor in the additional GC load. I…

C# does and Java did before the escape analysis optimization became default. You can find numbers in this old article from 1999: https://www.cc.gatech.edu/~harrold/6340/cs6340_fall2009/Read...

"and the overall execution time reduction ranges from 2% to 23% (with a median of 7%) on a 333 MHz PowerPC workstation with 128 MB memory."

The benchmark is 20 years old so it is kind of out of date. I don't know of any modern benchmarks. I suspect that the difference would be much bigger nowadays because programmers don't avoid allocating small local objects as much.

Re: Conservative GC: Is It Really That Bad?

#48

Post by ScottBurson »

bjourne wrote: post #47
ScottBurson wrote: post #43

Earlier quoted context omitted.

> But in a GC:ed language, the n variable would be bump allocated once every loop. Citation needed. I don't know of any GCed language that heap-allocates local variables in this way (well, maybe SML/NJ does, but I doubt it). Certainly not Java or any Common Lisp I've ever used. But I agree with your larger point: heap allocation is never quite as fast as stack allocation, once you factor in the additional GC load. I…

C# does and Java did before the escape analysis optimization became default. You can find numbers in this old article from 1999: https://www.cc.gatech.edu/~harrold/6340/cs6340_fall2009/Read... "and the overall execution time reduction ranges from 2% to 23% (with a median of 7%) on a 333 MHz PowerPC workstation with 128 MB memory." The benchmark is 20 years old so it is kind of out of date. I don't know of any modern…

Oh, now I understand what you're saying. I got thrown off when you said "the address of the variable n [...] moves a bit for each loop". This isn't quite right; it's not the address of the variable n itself that changes, it's the address of the allocated object that it points to.
Post reply on HN