Commonly Confused Tidbits re .NET Garbage Collector

I recently read a less than informed blog post purporting to describe the .NET garbage collector, but when pressed to point to a better one, I couldn't find a single concise article that covered everything I thought should have been covered.

Type and Memory Safety

We all know what the gist of GC is about: you allocate new objects, but don't have to worry about freeing them. Combined with type safety in the language, this can give you another kind of guarantee, memory safety: that it's impossible to create a dangling pointer (a pointer to freed memory). Type safety's "safety" is compromised in the absence of memory safety. For example, in a type-safe yet non-GC language, if you allocate an object, make a copy of the reference, then free the object, you're left with a dangling pointer. If you then reallocate another object with a similar size, depending on the memory allocator's implementation, you may have actually created a type hole - the dangling pointer may now point to the newly allocated object but with the wrong type. This extra safety is one of the reasons why GC programs often have less bugs than ones using manual allocation.

Precise compacting GC

.NET has a precise compacting GC. It's precise because .NET deals with type-safe and memory-safe references into the managed heap, it can know the precise layout of every allocated object. The opposite is conservative GC; conservative GC doesn't necessarily know the types of variables stored on the stack or in registers, or the layouts of those types, so if a random number on the stack or in a register or the middle of an object happens to coincide with a valid object address, it can't collect that object. It's compacting because during a collection, it moves live (non-garbage) objects closer together, squeezing out the gaps left by dead, old objects which no longer have any references to them. This eliminates the problem of memory fragmentation, at least as far as the managed heap is concerned.

However, thinking of a precise compacting GC as "collecting garbage" is not always the best way. When looking at the asymptotic performance of GC, it's helpful to turn things around, and consider that the GC collects live objects and brings them together. Garbage is just the stuff that got overwritten during moving, or the stuff left at the end after everything has been compacted together. Why is this important? Because the cost of a precise compacting garbage collection is proportional to the number of live objects it has to trace through and move, rather than the amount of garbage it needs to collect. When compared with manual allocation, where the cost of freeing memory is usually proportional to the number of objects freed (i.e. the amount of garbage), something should become clear: the longer you can delay GC - i.e. the more garbage you can build up - the faster and cheaper, in per-garbage terms, GC is than manual allocation.

An example. Imagine a single linked list with 1000 elements, with a single variable in the program referring to the head of the list. Consider the problem of truncating the list, and leaving only the head behind. With manual memory allocation, all 999 trailing items will need to be disposed of, with bookkeeping for each one. With garbage collection, only the first element need be moved to the start of the heap, and the free pointer (where new allocations begin) set to begin directly after it. The 999 other elements got "collected" for free.

This is why the performance of precise compacting GC is proportional to the amount of garbage it is allowed to build up between collections, and hence proportional to the amount of memory it's allowed to consume. It's also the reason why GC programs tend to use more memory than manual allocation ones. It's also the reason why small single-use objects, such as for function return values, are very cheap and shouldn't be unduly avoided in GC languages. Congruent with this, code in a programming language with GC is often more naturally written, easier to read and easier to write because of the freedom with which one can return freshly allocated objects without concern for who is going to collect them, or the performance ramifications. Understanding this point is key to understanding why GC is so productivity-enhancing.

Resources

The garbage collector is for memory, not resources. I've written about this at length in the past, so I shall quote myself:

Disposal of resources in a long-running application using GC is not a performance issue. It's a correctness issue.

Garbage collection knows about memory. With most collectors, GC is only invoked when the GC is asked for more memory than is immediately available, taking specific tuning parameters into account. In other words, the GC is only sensitive to memory pressure. It doesn't know about resources that it sees only as pointer-sized handles, it doesn't know how much they "cost", and indeed those resources might be on a different machine or even spread across many different machines.

More critically, garbage collection gets its performance surplus over and above manual garbage collection by not collecting until as late as reasonably possible

In .NET, the deterministic disposal mechanism is via the IDisposable interface, and in languages like C#, the using keyword.

Finalizer vs IDisposable

Finalizers in .NET are overrides of the method System.Object::Finalize(void). In C#, the syntax looks like a C++ destructor, but other .NET languages have other syntaxes. If this method is overridden, the .NET GC treats the object specially. After it has become garbage, rather than just overwriting it during compaction phase of GC, it will delay collection until the Finalize method of the instance has been executed by the finalizer thread. The GC makes a best effort to call the method; if the finalizer thread is blocked (e.g. some other finalizer hung), then the finalizer might not get called. This is another reason why deterministic disposal is preferred to relying on finalizers.

Finalizers should only be used with objects that directly encapsulate a non-managed resource, such as a file handle, a window handle, a socket, etc. A file stream, or a window object, or a network stream, should not normally implement a finalizer. IDisposable is a different matter. IDisposable should be implemented by every class with a finalizer, and every class that logically owns (transitively) any other object that implements IDisposable. Calling IDisposable on the root of the ownership tree should ripple through and call IDisposable on everything beneath it; ownership trees and other deterministic lifetime approaches still exist with GC precisely because GC is just for memory, not resources. Most objects neither own nor encapsulate resources, however, so much of the burden is still lifted.

Generations

I've read many posts that describe how generational GC works: very loosely, you have three generations, gen0 through gen2; allocations come from gen0; gen0 is collected if it's full; gen1 is collected if gen0 collection didn't free enough space; gen2 is collected if gen1 didn't free enough; more memory is allocated if gen2 didn't free enough; if not enough memory, then out of memory exception.

They also describe the hypothesis behind generational collections: that young objects are more likely to die (become garbage) sooner rather than later, while old objects are likely to survive longer.

But this, however, doesn't capture the intuition behind why there are 3 generations, rather than 4, or 5, or some other number. Let me explain.

Most applications have a roughly constant, steady state of total allocated memory. It's made up of two kinds of objects: objects associated with currently executing code (let's call them ephemeral objects), and objects linked into a global object graph which is shared across multiple instances and iterations of executing code (let's call them persistent objects). We want to avoid tracing through the persistent objects as much as possible, as it's unlikely that any objects which have survived for a long time have become garbage. Actually, making old objects garbage is a pathology to be avoided in .NET programs, and has been described as the mid-life crisis problem.

The ephemeral objects, on the other hand, are likely to have a high proportion of garbage. But we have a problem: when we perform a garbage collection on the ephemeral objects, there'll be some live objects left over, currently being used by executing code - but we still don't want them in with the persistent objects. To solve this problem, there needs to be a generation in the middle, a half-way house, before resorting to increasing the persistent object set.

This combination of three generations is almost ideally suited to server applications which have relatively little variance in total per-request allocation and tend towards an average per-request allocation which is less than the size of gen0+gen1 per thread. If one could time per-thread collections of gen0 and gen1 correctly, in between requests, then in theory GC would be almost completely free, as there would be almost no live objects. There are complications in practice (we can't manually invoke a GC for just a single thread, for one thing), but when designing applications and servers, it's very much worth keeping the generational design of the GC in mind and working with its assumptions, rather than against them.

For example, this can mean that caching objects can turn out to be a pessimization rather than an optimization, because keeping them around moves them into gen2, where it is more expensive to collect them when they get evicted from the cache than it was to create them in the first place. Depending on how expensive the objects are to create vs cache, they may need to be cached permanently and updated as needed, or referred to through a WeakReference which won't keep them alive, or at worst managed manually one way or another, such as via unmanaged memory, or slots or ranges in an array, etc.

On the Difficulty of setting the Windows 7 Desktop Wallpaper

You need to be a software engineer to precisely and correctly set the Windows background in Windows 7.

I have a multi-monitor setup, and I use a very particular method for laying out windows on my secondary screen: I have them cascaded, from the top-left corner of the screen towards the bottom right, such that a little of the bottom-left corner of every window is visible on-screen at all times, like this:

The corners form a mechanism for switching between windows based on spatial layout. Certain windows, such as terminals, browsers, email apps, etc. have "natural" dimensions. Browsers generally like to be page-shaped; terminal windows are quite squat; documentation browsers are somewhere in between, with a treeview on the left and a content pane on the right. These natural shapes guide their spatial positioning. So, all my terminal windows end up cascaded one after the other on at the top left of the screen, followed by Firefox's downloads window, then my bug tracker client, then Thunderbird, then MSDN documentation, with Firefox at the bottom-right, filling the full height of the screen.

Switching between applications based on their spatial layout turns out to usually be more efficient than almost any other scheme, particularly when one's hands aren't on the keyboard. Even alt-tab doesn't distinguish very clearly between different instances of e.g. a terminal app, when in fact each one may be logged in via ssh to different machines and thus it matters very much which one I select.

This scheme works well enough, but the bottom-left corners can get a little ragged. To make aligning the corners easier, I have a special wallpaper which consists of a line carefully placed so that it shows up on the bottom-left corner of my second monitor. When the wallpaper mode is set to "tile", a wallpaper which is big enough to cover the entire desktop area will show up at the expected offset, and everything works out OK.

This wallpaper, a 16-colour bitmap, is so small when compressed that I can embed it here uuencoded directly:

begin 644 wallpaper2.bmp.bz2
M0EIH.3%!629365%3W2<`1PST[.0U0`!`0!`"`0!``!``0`!$``,(L`#9`0JC
M4#1HR::%&C(&C3(T"E4TAM30`&=?M"6=)(E^T$2WA+9$L*JDF-E$NG?'AI55
M0/>6^L(CB*T(550`Q-.DJ".(B"O,*JH`8F(WU0$<@^P((\>[801S_$;<:YG'
:LR**SC<GG'.8JJ@!M,13_%W)%.%"045/=)P`
`
end

If you save that to a file with a '.uue' extension, many common archivers, such as WinZip or WinRar, will be able to open it up. Here's what the meat of it looks like, anyway:

However, it turns out, if you try to set this background using the "Personalization" Control Panel applet in Windows 7, it does some helpful "conversions" on it: it appears to round-trip the damn bitmap through JPG, resulting in artefacts. I've enhanced a zoom of the line after Windows has butchered it:

The line looks unclean, and in particular, it ends up with wave of intensity throughout its length, which is quite distracting and not the desired effect.

Things can get worse though; if you try to use Windows Photo Viewer to set the background using the original bitmap, it will actually resize the thing down to fit the dimensions of your primary monitor (!!!), all but zooming the line out of existence. This drove me up the wall for about 20 minutes, as I tried to figure out where my line had gone when I first transitioned from XP to Windows 7.

The easiest way I currently know to correctly set the Windows 7 desktop wallpaper is to write a program that uses the SystemParametersInfo function directly, to ensure the bits get through unmolested.

I have a lot more Windows 7 annoyances where this came from, but this one cost me quite a bit of time, so it sticks out. My verdict on Windows 7 is pretty mixed. Many applications, particularly games, are incompatible, and overall I dislike the shell compared to XP, especially Windows Explorer and the Vista-esque Start Menu. About the best things I can say in favour of the move is having less concern about future compatibility, and having a 64-bit mode that mostly works, despite all the horrific hacks going on beneath the covers to make it happen. Oh, and I'm running with UAC disabled. I can only take so many access denied errors as I poke around the system before I crack - and command-line apps generally just give you the error, rather than popping up an elevation prompt.

Bad week

It's been a bad week. My main hard drive crashed last Monday or so, while today my scooter is gone, presumed stolen. On the bright side, the final component of my new PC arrived and I was able to get Windows 7 up and running.

The new machine has an i7 920, so things like %NUMBER_OF_PROCESSORS% returns 8 - it's a quad core with 2x hyperthreading. Having so many logical cores has some downsides: maxed-out single-threaded processes only take up 12.5% CPU, so it can look like the machine is not particularly busy even though a process is working as hard as it can. Other specs include 12GB RAM, AMD 5870 graphics, 80GB Intel SSD and 1TB Samsung F3.

Maximizing the value of the small boot drive has been interesting. Windows 7 all by itself takes up a good 18G of space, what with the side-by-side (SxS) feature keeping lots of versions of the same APIs, and a big hiberfil.sys in the root - I moved the page file to the big drive. Because of the acute space constraints, I've been strongly motivated to keep almost all the junk that apps usually dump into the file system off the boot drive. By and large, I achieve that by creating directories on the 1TB drive and pointing to them with junctions on the boot drive. That way, apps think they are installing onto the C drive but they don't steal too much space. My prior drive - the one that died - was a 10K WD Raptor, so I've had some experience with this, and I wrote a script to automate the process:

#!/bin/bash

. _die

function usage
{
    echo "usage: $(basename $0) <directory>..."
    echo "Replace directories with junctions pointing to /bulk, after moving contents."
    exit 1
}

test -n "$1" || usage

for f in "$@"; do
    
    test -d "$f" || die "'$f' isn't a directory"
    
    dest="$(abs-path "$f")"
    dest=/bulk/mathom/"${dest//\//_}"
    
    test -d "$dest" && die "'$dest' already exists"
    
    # Try to copy stuff over; if an error, delete target and give up.
    cp -r "$f" "$dest" || {
        rm -rf "$dest"
        die "couldn't copy '$f' to '$dest'"
    }
    
    # Rename source, in case something can't be deleted.
    aside="$(move-aside "$f")" || die "failed in move-aside"
    
    # Create junction.
    junction "$dest" "$f" || die "failed to create junction"
    
    # Remove the aside.
    rm -rf "$aside" || {
        echo "warning: couldn't delete '$aside'"
    }
done

This script uses a number of little wrapper utilities I wrote - at this point I really ought to be thinking of putting them in an online repository. Here's a summary so you can follow along:

• abs-path: Canonicalizes and makes an absolute path by using cygpath twice, once to Windows format and once again back to Unix format, and prepending $PWD if necessary.
• _die: Defines a die function which prints out appropriate error and exits.
• move-aside: Renames a file or directory so that a failed attempt at creating a junction can be rolled back. Also helps with locked files - generally these can be copied and renamed, but not deleted. The new name is printed out on standard output.
• junction: This wraps SysInternals junction to create a junction in the TARGET LINK_NAME argument order familiar from ln, and permits using Cygwin paths.

With this script, and the big drive mounted at /bulk with a directory called mathom in its root, any given directory tree can be moved across readily enough. However, things in Windows 7 x64 are slightly more complicated.

Some of the directories I moved over to /bulk/mathom included Program Files, Program Files (x86), and ProgramData. Windows 7 itself has some junctions set up (the rats nest here is a proper horrorshow, I should document it at some point just for my own use, if nothing else). For example, "ProgramData\Application Data" points at ProgramData itself, and a simple cmd /c dir will fall into the infinite recursion and print out errors when the file path gets too long. So, in moving these directories across, I had to examine them for existing junctions and replace these as necessary. The Cygwin tools of Unix heritage are more robust against cycles in the file system hierarchy - for example, find keeps track of inodes to avoid infinite recursion.

All this checking of existing junctions wasn't sufficient to get everything working nicely, though. The permissions generally also need tweaking, particularly for folders that get modified by installers. These generally perform operations using either the NT SERVICE\TrustedInstaller or NT AUTHORITY\SYSTEM accounts - and sometimes both, in a dance of setup.exe and msiexec.exe. So, by process of checking, trial and error, using SysInternals Process Monitor to track installation failures, I put together a new script to ensure Program Files, ProgramData and folders of their ilk have the right set of permissions:

#!/bin/bash

function usage
{
    echo "usage: $(basename $0) <file/directory>..."
    echo "Resets files and directories to Windows 7 general install permissions."
    echo "Essentialy this is: SYSTEM/TrustedInstaller/Admin: full; AuthUsers: Modify; Users: Read"
    exit 1
}

test -e "$1" || usage

for arg; do
    
    # First, take ownership so we can definitely set all ACLs.
    # /F <file>; /R - recurse; /D <Y/N> - take ownership if no directory listing
    takeown /F "$(cygpath -w "$arg")" /R /D Y > /dev/null
    
    # Reset ACLs recursively to inherit from parent
    icacls "$(cygpath -w "$arg")" /reset /t /c /q > /dev/null
    
    # Set appropriate ACL on root, to progate recursively
    icacls "$(cygpath -w "$arg")" \
        /grant "Administrators:(OI)(CI)F" \
        /grant "SYSTEM:(OI)(CI)F" \
        /grant 'NT SERVICE\TrustedInstaller:(OI)(CI)F' \
        /grant 'Authenticated Users:(OI)(CI)M' \
        /grant 'Users:(OI)(CI)RX' \
        /inheritance:r /c /q > /dev/null
    
done

The logic is applied in three phases:

1. Take ownership, with takeown
2. Reset permissions recursively so that they inherit from parent
3. Set ACL on the root, so children will inherit from it, but make sure the root itself doesn't inherit permissions.

I tried for a while to get it all into one icacls invocation, but I couldn't get the two effects working together: enabling inheritance in the children, but disabling it in the root. This is something you can do in one "Apply" step using the Security tab in Explorer, though it's quite tedious picking out all the users and setting the appropriate checkboxes.

As an aside, the Security tab is quite confused by junctions; when permissions have been inherited from a directory on a different drive, because the current file / directory is in a subtree pointed to by a junction, the Security tab will search in vain through the parents looking for what provided the given inherited permission. Sometimes it gets lucky, and finds a random parent that coincidentally has the same permission; otherwise, it bails out with "Parent Object" as the indicated "Inherited From" column. But my proper list of Windows 7 issues will have to wait until I really feel the need to rant, which will no doubt happen sooner or later.

I should add that all the drastic file system surgery I write about here was performed with UAC effectively out of the picture, and all Cygwin tools running with the administrative privilege bits set. It's been my experience that command-line apps don't pop up the required UAC prompt; instead, they fail with an access denied message, which is rather vexing when you're trying to automate things.

Public interest rule of thumb

TechCrunch is having a crisis of conscience over what they'll do with internal Twitter documents they've received.

My rule of thumb is pretty simple. The documents are stolen. Unless the documents reveal wrongdoing greater than stealing, such that the public interest served in publishing is greater than the private harm, then it's unethical to publish. Idle musings about "they are going to be published somewhere on the Internet" is specious; the morality of one's actions don't depend on whether someone else is "doing it", much less everyone.

If TechCrunch goes ahead and publishes these documents, it'll only further cement my already pretty low opinion of Arrington. (I'm not a habitual reader of TechCrunch, or otherwise I'd waste away over all the food I'd be vomiting up.)

StackOverflow and religious language in programming

I was reading Why I Don’t Listen to the StackOverflow Podcast any More, and in reading the comments, I found it interesting to see the amount of religious language.

#21 (sbohlen) I’d have to agree that they do indeed appear successful, but success / failure isn’t a boolean [...] The world is full of people who succeed due to all kinds of factors including dumb-luck, [...]

This reminds me intensely of "the race is not always to the swift" etc. Eccl 9:11.

I changed adopters to believers to accentuate the effect:

"#16: [...] I have also experienced that the non-[believers] aren’t (gnerally) non-[believers] out of choice but are instead non-[believers] largely out of ignorance and inexperience — they just don’t know what they don’t know [...]"

#16: "the [types] who aren’t interested in self-improvement; there’s not a damned thing I can suggest to help these people — I cannot MAKE someone want to better themselves, that’s gotta come from within"

#16: "I [...] think that Jeff and Joel are indeed preaching [...] they are (IMO) abdicating the unofficial professional responsibility that comes with having a pulpit from which to preach."

#14: "I am a strong believer"

#13: "@sbohlen. I fully agree with the sentiment that “up and running” is not a valid metric"

I'm not going to go on with this, though I could - the about page for the blog is particularly ripe for further examples of religious language - but I do want to make a further point.

Could it be that latent religious feelings are responsible for a good portion of the minor angst on display in these comments? Could it be that people are unconsciously annoyed, not with StackOverflow's success, but rather its success even in the face of quite mild contempt at the unit-testing / SOLID religion?

My own position: I'm a "believer" in evolution and the market. Neither evolution nor the market have any moral content (they can't say what "ought" to be), and both only measure success by effects rather than processes. In a phrase, "up and running" is not just a valid metric - it's the only metric, until it stops running. If SO continues to thrive, and doesn't die under the weight of its lack of unit testing (which seems to be the logical end result of the beliefs of the believers in the comments), where then is the truth in the proclamations of doom from the prophets of the true religion?

I don't think unit-testing is the only way to avoid long-term bit-rot. I think it's a good way, but not the only way; moreover, I don't think unit testing is especially useful in the very early stages of a project, where the design changes often and rewriting unit tests becomes a disincentive to larger refactoring and redesign. I think every one of the concepts embodied in S.O.L.I.D. is debatable in certain scenarios (except perhaps LSP).

In my experience, premature abstraction has been responsible for a similar number of ills to premature optimization: abstractions chosen at the wrong boundaries, for the wrong reasons, because designers thought they could foretell the future and anticipate where changes would come. Thus I am wary of merchants of abstractions and patterns, principles and practices. I'll use them when appropriate, but never with religious zeal.