Squawks of the Parrot

This is an excellent introduction. Short, self-contained, easy to follow, with the major trade-offs enumerated. Very well done, great job!

While I prefer garbage collection, its nondeterministic finalization keeps biting me. I would like to be able to explicitly (and implicitly, via stack-based objects [in the lexical sense]) tell the GC to synchronously finalize an object.

I'm fine if this is merely a "hint", like many GC's explicit "run now" calls, of what the GC should do. I understand it's ultimately the GC that needs to make the decision, and the programmer may not see the entire picture.

There are two ways to synchronously finalize an object. First, of course, is explicit finalization--you exit the scope, and the system kills the variables. Less than optimal if something could still have a handle on them, but works fine in languages that can do sufficient tracing and have sufficient control over itself to properly nuke things.

The alternate is to run a conditional GC sweep at block exit, which is the scheme we're working with for Parrot. Variables can mark themselves as "impatient", and we keep an impatient counter. Conditional sweeps only fire off if there are live impatient data, something the sweep recalculates each time it runs (it's a flag in each PMC) so that when there are no impatient variables the sweep is skipped.

Not great, but not bad.

A really nice overview / intro. Some details and issues that I've not seen anywhere before. Keep up with these "What the heck is" articles, they really are top class.

"important" variables trigger GC at scope end?

So, if I have something like:

{

  my $logfile =     ImportantFileHandle::new(" {

    unless /^#/ {

      chomp;

      processline($_);

    }

  }

  # ImportantFileHandles close at scope exit

}

I'm not claiming that this is good code, mind you, but it might not be uncommon to open a file at the beginning of the program and hold it open until program end.

Does this mean that a GC is going to be called for every line in the log file, because the count of "important" variables will always be at least 1?

Good article.

In the defense of refcounting (which I am not a big fan of neither), there are some ways the cost associated with updating the refcount of a variable in a loop (or some similar situation) can be greatly reduced, by delaying the update work to the end of the scope for example. Also, you say: "your code needs to fiddle with the reference count properly". I found this sentence to be somewhat misleading, giving the impression that the 'user code' might have to deal with refcounts, while it is only the compiler-generated code that will have to deal with it.

A really big problem of refcounting that you didn't mention is its inability to reclaim cycles. That may be in the end the biggest defect of refcounting. Perl programmers are aware of that constraint in perl, and some think this is inherent to GC, while this defect isn't present when using other techniques.

About indeterminacy in time and space of garbage collection: that problem has been solved. It surprised me too, but there really are techniques for GC bounded in time and space, executing in hard real-time concurrently with the user's program, even on SMP machines while staying scalable. An interesting article about that from Perry Cheng is available at the following URL:

citeseer.nj.nec.com/cheng01scalable.html

BTW I think that you make a really good job at presenting GC as a good thing, which everyone should agree it is.

keep on the good work!

Importance declarations may cause end-of-block checking if the language so chooses, which can definitely cause pathological behavior. There are ways around this--for example the language can defer marking a variable as important until the end of the block in which the variable is created or assigned to (if we get clever and use return value hints on subs, methods, and functions) or not emit a conditional DOD sweep at the end of loop blocks, rather deferring it until the end of the loop, or only every n loops, or something of the sort.

It is definitely possible to get degenerate behaviour out of this mechanism, but one of the things it does have going for it is that very few objects in the normal course of processing will get marked as immediate, as it isn't that common a thing. Filehandles may not by default, for example. We may also defer it to sub exit rather than block exit, or tune it in some way, or something of the sort.

Nice article. Explanation at a level I could follow. However, it did set me thinking about "a better way".

I've got considerable C skills from gui apps to device drivers, but no compiler writing, so anything I think is probably old hat, off-base or just simplistic, but the notion won't leave my head until some says "that'll never work", so here it is.

Reference counting is liked because of timely destruction., and hated because it adds overhead--both memory and math--to every variable access.

Mark&sweep is favoured because it removes the overhead in favour of small bursts of intense activity at times convenient to the er... compiler? interpreter? runtime? The thing that worries people about this, is the "at sometime convenient to some indeterminate heuristic" part.

The thought that struck me was the C concept of automatic variables. They come into existence at exactly the level of scope that they need to, and they are automatically cleaned up when they go out of scope. So simple. Garbage Collection becomes a simple SP+n operation.

The problem is that they *can't* exists beyond their scope. The old "Don't return references to stack vars problem". And that's when it struck me, why bother GCing *everything*?

Why not allocate local/lexical scoped variables from a "stack" and only promote them to a "referenced variable heap" if the code actually takes a reference to them?

The testing for which type any given variable is would be restricted to code generation time.

At runtime, the code would have been generated to deal with each individual var in the appropriate manner. Un-referenced vars being accessed via a "stack pointer" with no reference counting necessary, and automatically GC'd en-masse by a one-off SP manipulation at scope exit.

Referenced variables would be accessed from the heap, with whatever reference counting/mark&sweep mechanism was chosen.

This would benefit the majority of short-lived, locally scoped vars as they would never need to be GC'd. And the GC benefits by processing only those vars that have had references taken, reducing the both the volume and frequency of GCing.

Talking about a "stack", when the underlying subject is Parrot which has been designated a register-based VM may cause some handwaving. Are the Parrot VM "registers" actually allocated once at startup, or does the block of memory where the registers live move as scopes are entered and left? The latter is what I envisage, but I'm still trying to wrap my brain around the code to confirm my mental picture one way or the other.

Languages without closures, coroutines, or continuations can immediately destroy variables that go out of scope if the compiler's determined that the variables are no longer referenced. Static analysis of the code can determine this with some certainty. (Variables fall into one of three categories--definitely referenced, definitely not referenced, and maybe referenced) Most do, since it makes things go faster--less stuff to trace, and it's a compile-time determination.

Why not allocate local/lexical scoped variables from a "stack" and only promote them to a "referenced variable heap" if the code actually takes a reference to them?

In the presence of continuations (and to a lesser extent coroutines and closures, especially with dynamic compilation), all local/lexical variables are potentially referenced. You can't determine at compile time what is and isn't referenced, and thus your trick won't work.

Allowing runtime stack snooping, and other forms of introspection, will also make this problematic, as will many forms of operator overloading. (Since an overloaded operator function may retain a reference to either itself or its parameter)

It's useful, but unfortunately there are a number of language characteristics that will kill static analysis dead. Unfortunately.

As for Parrot's registers, they're in a fixed location, in the interpreter structure. There's a backing stack for them, so when registers are saved on that stack they get copied into a stack frame. They don't move, though, which speeds up both the interpreter and JIT, which is a nice win.

Thanks for putting my mind at rest, and sorry for the duplicate post earlier.

HI
anand

A couple of additional points that I want to add to this excellent article. I've been doing some research recently on the speed differences between GC and manual memory management. While it always depends on the specific application and the patterns of memory use, the argument that GC is slower or more costly than manual memory management simply doesn't hold in most situations. Here are the reasons I've found:

First and most importantly, most of the time it simply DOESN'T MATTER. Usually, all other things being equal, GC vs. manual memory management makes NO perceivable difference to the user of the application. As was mentioned in the article, most programs spend only a few percent of their time in memory management. In addition, most programs leave the CPU idle 99% of the time. The logical conclusion is that a slight difference in CPU usage between memory management methods won't make any noticeable difference in performance. This has been confirmed in many real-world studies. There are exceptions, but this covers the vast majority of modern desktop computer applications. This reason alone should be enough to make 95% of the world's programmers stop reading right now and switch to a GC-based programming environment, if at all possible in their situation. (One rebuttal to this is that GC causes the system to become unresponsive during collection, but this simply isn't true anymore -- a well written, modern GC is incremental and will not cause noticable pauses in any but the most unreasonable situations. malloc/free also have the potential to cause pauses in worst-case situations, so there isn't any significant performance difference between malloc/free and GC.)

While 95% of you should be convinced already, there are some people for whom the above argument is insufficient. Those who write OS kernel code or performance-critical systems have a reason to care. Other people are simply interested in more information. For these people, I make the argument that GC is not a clear loser even in terms of raw performance. Again, it depends on the application's memory usage patterns and the capabilities of the system, but in many cases GC will IMPROVE performance over manual memory management. To start out, here are the common arguments against GC:

1. Allocation might trigger a collection, which means it won't work for real-time needs.
2. You never know when a collection will cause the application to pause.
3. I need the performance. GC is too slow.

1. With GC, an allocation might trigger a collection, so it might be slow. However, this isn't a valid argument against GC. NO dynamic memory scheme has any kind of hard time limits on allocation/deallocation. malloc has to search through memory to find a best fit, and sometimes this can take quite a while. RefCounting is a layer over malloc, so it has the same limitations. In addition, all allocators can cause heap expansion, and all allocators can trigger one or many page faults. These costs are MUCH greater than the cost of a collection (except on poorly written GCs, or GCs that have to deal with hundreds of megabytes of heap at once). So the argument that GC's allocator is more unpredictable than malloc's is pointless. If the unpredictable timing of a GC's allocator in unacceptable, malloc is equally unacceptable, and the mechanisms for working around malloc's limitations apply equally as well to GC's allocator.

2. Collections can cause the application to pause. This is essentially true, but not necessarily significant. First, GC strategy has come a LONG way in the past few years.

(previous comment truncated...) Modern GC implementations are usually incremental, so they spread their work out over several partial collections . Second, computers are much faster than they used to be, so even full collections don't cause a noticable pause except in worse-case scenarios. Finally, applications are already pausing for all kinds of other things - virtual memory paging operations, background tasks, etc. The pauses caused by a garbage collector are usually insignificant when compared with these.

3. People argue that GC is slower than manual memory management. While in some cases this is true, it often simply isn't the case. GC can be FASTER than manual memory allocation, depending on how the application uses memory. First, malloc isn't free. In many cases, the total amount of CPU time spent in malloc/free can be equal to or greater than the CPU time spent in garbage collection . It depends on the size and pattern of the allocations: malloc/free is faster for occasional large allocations, while a GC is usually FASTER than malloc/free for frequent small allocations. A custom layer on top of malloc/free can help speed the worst-case scenarios, but even with custom allocators, GC and malloc/free are evenly matched in terms of total raw CPU cycles required. Second, for most applications, page faults and cache behavior are significantly more important to performance than raw CPU time. In these areas, there are some significant advantages to GC. Third, with manual memory management, there is a lot of code involved in tracking memory. This code isn't needed for GC, so your app can be smaller and faster without it.

The bottom line is that for most applications, GC will not cause any performance problems, and might even IMPROVE performance. The results vary from situation to situation, but in most cases GC is a clear winner. Even if performance is important, consider trying a GC package and do some profiling to see what impact it has on your performance. You might be surprised.

Dan, thank you for your hard work on Parrot and for these enlightening "What the heck is ..." posts.

Like Buk, above, I've got a "Why not ...?" question, that I was wondering if you could shed some light on. It has to do with dead-object detection. You described the basic algorithm in your article: first, mark everything dead; second, mark everything reachable from the root set alive; third, delete everything still marked dead.

If each object had a "fad" bit instead of a "live" bit, which was toggled in step two instead of set, it seems that you could skip step one. Step three would be to delete every object that hadn't kept up with the current "fad."

This seems like an obvious optimization--I'd call it the "high school algorithm"--which tells me that I must be missing something. Thanks.