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

Practical Garbage Collection - Part 1: Introduction

worldmodscode.wordpress.com

Post reply on HN
Print view View original

11–20 of 39 posts

Re: Practical Garbage Collection - Part 1: Introduction

#11

Post by dons »

bitops wrote: post #9

A very good writeup, but one thing always confuses me. What is meant specifically by the "heap" and "stack"? I know what a stack is, but "heap" gets thrown around in many different contexts and I've yet to find any explanation that made it clear. If anyone has a good explanation or good links for those two terms in this context, I'd be very grateful. Thanks! [EDIT: thanks everyone for the answers so far!]

In programming languages, generally:

* Stack: "control stack" -- a structure that tracks the context of an evaluation "step" in the program

* Heap: an environment that maps symbols to values (i.e a data structure that tracks the bindings of names to computations and results).

Re: Practical Garbage Collection - Part 1: Introduction

#12

Post by faboo »

bitops wrote: post #9

A very good writeup, but one thing always confuses me. What is meant specifically by the "heap" and "stack"? I know what a stack is, but "heap" gets thrown around in many different contexts and I've yet to find any explanation that made it clear. If anyone has a good explanation or good links for those two terms in this context, I'd be very grateful. Thanks! [EDIT: thanks everyone for the answers so far!]

Usually when people say "the heap" (especially in the context of garbage collection) they mean the memory where new (non-stack) data/objects are allocated from. Usually this is the bulk of memory an application uses.

There are other meanings of the word "heap" in the realm of data structures, but I haven't personally seen "heap" the data structure talked about (or used) much in the wild.

Re: Practical Garbage Collection - Part 1: Introduction

#13

Post by Tuna-Fish »

bitops wrote: post #9

A very good writeup, but one thing always confuses me. What is meant specifically by the "heap" and "stack"? I know what a stack is, but "heap" gets thrown around in many different contexts and I've yet to find any explanation that made it clear. If anyone has a good explanation or good links for those two terms in this context, I'd be very grateful. Thanks! [EDIT: thanks everyone for the answers so far!]

A stack is a data structure that grows and can be accessed from one end.

The stack usually means the call stack, or c stack, where one of the registers of the cpu is always pointed to the top of a stack structure in memory. That way it can be used to quickly allocate and free memory for function calls and function-scoped temporaries, and it has no trouble handling (limited) recursion.

Heap refers to the part of the memory that is fundamentally just a flat address space asked for from the OS. On top of that lives the heap allocator, whose job is to portion that into usable chunks and try to be able to reuse returned space. In C that is malloc/free, in c++ new and delete.

In the olden days heap and stack actually referred to the same area of memory, the heap growing upwards from the bottom and the stack growing down from the top. Luckily, today there is enough address space that we don't have to do this anymore.

Re: Practical Garbage Collection - Part 1: Introduction

#14

Post by anamax »

faboo wrote: post #12
bitops wrote: post #9

A very good writeup, but one thing always confuses me. What is meant specifically by the "heap" and "stack"? I know what a stack is, but "heap" gets thrown around in many different contexts and I've yet to find any explanation that made it clear. If anyone has a good explanation or good links for those two terms in this context, I'd be very grateful. Thanks! [EDIT: thanks everyone for the answers so far!]

Usually when people say "the heap" (especially in the context of garbage collection) they mean the memory where new (non-stack) data/objects are allocated from. Usually this is the bulk of memory an application uses. There are other meanings of the word "heap" in the realm of data structures, but I haven't personally seen "heap" the data structure talked about (or used) much in the wild.

> I haven't personally seen "heap" the data structure talked about (or used) much in the wild.

Maybe not, but the concept of computing with addresses is reasonably common.

That's why programming interviews often have some variation on heap sort or radix sort.

Re: Practical Garbage Collection - Part 1: Introduction

#15

Post by rubashov »

> The default choice of garbage collector in Hotspot is the throughput collector, which is ... entirely optimized for throughput

I just want to confirm this is true? Say you're doing a long running simulation. You don't care about pauses at all. You just want it to finish fast. The default GC with no particular options is the way to go?

Re: Practical Garbage Collection - Part 1: Introduction

#16

Post by eternalban »

bitops wrote: post #9

A very good writeup, but one thing always confuses me. What is meant specifically by the "heap" and "stack"? I know what a stack is, but "heap" gets thrown around in many different contexts and I've yet to find any explanation that made it clear. If anyone has a good explanation or good links for those two terms in this context, I'd be very grateful. Thanks! [EDIT: thanks everyone for the answers so far!]

Generally, the "heap" is the addressable memory assigned to the process. E.g. you malloc a byte array and gain a reference to the (byte[] rep.) memory object in heap. The life-cycle of a memory object in heap is explicitly controlled by OS (and sometimes the language e.g. C/Obj-C/etc via freeing the heap memory object). Languages with garbage collectors do this implicitly.

The "stack" is the dynamic structure -- its a stack :) -- that maintains the nested call/method/function frames from the initial entry point (e.g. main(..) in C family) so it maintains the path traversing the invocation/call graph to the current executing call/method/function. The 'objects' in a stack are call/function/method parameters, various metadata (e.g. obj ptr in some oo langauges). The life cycle of objects in stack is scoped by the call/function/method itself. Further, typically attempts are made to store (current) stack objects in CPU registers so as to avoid incurring memory access latencies.

Re: Practical Garbage Collection - Part 1: Introduction

#17

Post by gtani »

rubashov wrote: post #15

> The default choice of garbage collector in Hotspot is the throughput collector, which is ... entirely optimized for throughput I just want to confirm this is true? Say you're doing a long running simulation. You don't care about pauses at all. You just want it to finish fast. The default GC with no particular options is the way to go?

Well, to not answer your question: Hotspot performance tuning is a fine art, and benchmarking is a somewhat separate fine art, people will sample their data carefully, do a lot fo runs, warming up properly, using different GC's, tuning heap,GC generations, MaxInlineSize, maybe 32-bit (-server). I remember reading linux package managers often don't include -client in the 64-bit install. JDK7 maybe faster, many people have said no difference between sun/Oracle and openJDK (except launcher and fonts, for IDEA, you must have sunjdk), and in some cases JRockit performs more predictably.

Here's some blogs that i like about this:

http://openjdk.java.net/groups/hotspot/docs/RuntimeOverview....

http://q-redux.blogspot.com/search/label/all%20jvm%20options

http://redstack.wordpress.com/2010/12/09/recommended-jvm-par...

http://marxsoftware.blogspot.com/2011/10/javaone-2011-defini...

http://blog.headius.com/2009/01/my-favorite-hotspot-jvm-flag...

http://groups.google.com/group/jvm-languages/browse_thread/t...

http://stackoverflow.com/questions/tagged/java+hotspot?sort=...

Re: Practical Garbage Collection - Part 1: Introduction

#18

Post by aardvark179 »

benhoyt wrote: post #8
eru wrote: post #6

Earlier quoted context omitted.

Reference counting is slower than proper garbage collection, since it adds an overhead for each access, instead of just during the collection. (There are ways to make reference counting faster, but they are no longer quite so simple.)

It's not quite true to say reference counting adds overhead "for each access" -- for example, you can easily have a loop which accesses an object but doesn't modify the reference count. Reference counting adds overhead each time someone "expresses an ownership interest" in an object (wording from http://developer.apple.com/library/ios/#documentation/genera... ). (That's not to say your main point is false. I don't ac…

This is true, but has to be thought through very carefully in multithreaded environments where another thread might remove an object from a collection, causing it to be deleted while you're still looking at it. Safe looping then requires locks or cloning the collection (which is suddenly more expensive because it will hit all the contents' ref counts).

In summary, safe and efficient multithreaded code is never easy.

Re: Practical Garbage Collection - Part 1: Introduction

#19

Post by rayiner »

pixie_ wrote: post #5

The complexity of generational garbage collection vs. the speed of manual collection, makes me feel like the happy medium of speed and simplicity is reference counting, like that found in objective-c. iPhone apps are fast, but take a bit longer to design, develop, and debug due to memory management issues. Though with experience these can be minimized. It probably isn't possible without a ton of modification, but I w…

It really depends on the task. For an embedded device with a UI, where memory is at a premium, reference counting is probably the way to go.

But for pure throughput, especially on a multiprocessor machine, you really want to go with tracing garbage collector. In a multiprocessor system you have to keep caches coherent, and writes to the reference count have the effect of invalidating remote cache lines, increasing coherency traffic, etc.

Re: Practical Garbage Collection - Part 1: Introduction

#20

Post by kbolino »

Tuna-Fish wrote: post #13
bitops wrote: post #9

A very good writeup, but one thing always confuses me. What is meant specifically by the "heap" and "stack"? I know what a stack is, but "heap" gets thrown around in many different contexts and I've yet to find any explanation that made it clear. If anyone has a good explanation or good links for those two terms in this context, I'd be very grateful. Thanks! [EDIT: thanks everyone for the answers so far!]

A stack is a data structure that grows and can be accessed from one end. The stack usually means the call stack, or c stack, where one of the registers of the cpu is always pointed to the top of a stack structure in memory. That way it can be used to quickly allocate and free memory for function calls and function-scoped temporaries, and it has no trouble handling (limited) recursion. Heap refers to the part of the m…

AFAIK, heap and stack are still in the same "area of memory;" the discipline of separating the two is still enforced (or not) by the operating system. The heap-grows-up, stack-grows-down convention is still common on (32-bit, maybe 64-bit?) x86 too.
Post reply on HN