[SGVLUG] Microsoft Reports OSS Unix Beats Windows XP

[Chris Smith]

On 11/13/05, Dustin <laurence at alice.caltech.edu> wrote:
> On Sun, 13 Nov 2005, Chris Smith wrote:
> > Actually, I'd argue quite the opposite. The Linux kernel is rife with
> > reference counted data structures, which is essentially a poor man's
> > GC. If nothing else using GC would improve the ability for kernel
> > operations to run concurrently, probably help reduce fragmentation of
> > kernel space, and might even allow for faster amortized times for
> > memory management.
>
> The last sentence is key.  Yes, you can get higher throughput with "real"
> GC (actually, I think ref counting is as "real" as any other method,
> unless reaping cycles is fundamental to your definition of GC reality),

Hence why I tend to call it "poor man's GC" ;-), although that's a tad
unfair as there are circumstances where ref counting is the ideal
choice.

> and *maybe* on a webserver (or anywhere else where transactions per second
> is the figure of merit, not responsiveness) it might make sense.

Actually, GC tends to be a bigger win on the responsiveness side if
you are using a parallel collector, although it can get ugly if the
collector can't keep up with the allocator.

> But...the memory overhead of GC is startling, and downplayed by GC bigots
> (just like the time and space overhead of malloc is downplayed by anti-GC
> bigots).

Well wait... how can both GC and non-GC approaches impose time and
space overheads that each side tends to downplay? I mean, surely one
approach clearly has more overhead than the other, or there isn't a
clear overhead in which case your assertion doesn't make any sense....

As you correctly pointed out, GC *has* to be done in kernels, the only
question is whether you use reference counting or something more
sophisticated. In such a context, it's hard to make the case that one
shouldn't use GC in a kernel.

> Every time I've seen the calculation that says GC is faster than
> manual allocation it is done in the infinite memory limit.

Well, a good test will impose some kind of memory limit, otherwise you
are just comparing allocation and not deallocation.

> Further, I am not aware of any "real"  collector that doesn't stomp all over the
> heap,

Well, a compacting or copying collector will potentially "stomp" all
over the heap. However, there are a number of approaches which can
mitigate the impact of this. More importantly, inside a kernel the
heap is small enough that the impact of said "stomping" might be tiny
compared to the benefits in terms of defragmenting memory.

> and such calculations also don't take into account either cache misses or
> paging,

The real benchmarks for this stuff are run in real world scenarios,
and so they very much take this in to account. Indeed, you'll find a
lot of the higher quality automatic memory management systems
specifically have a first generation sized to fit in cache.

> so the extra memory that is required to start reaping the benefits
> of that calculation is larger than one might think.

Despite my point-by-point responses to your points, I agree with this
final point here. In general, memory management issues are quite
complex, and it takes a lot of study and expertise to really determine
what is the most efficient approach.

> All told, it seems to take a factor of *several* to get that
> performance.  Under memory pressure, the swapping is gets worse faster.

A lot of kernels don't ever swap out their heap, so this need not be a
concern in kernel space. In general the small size of kernel heaps
tends to minimize the impact of any memory overhead, although one
would be a fool to ignore that kernel heaps are kept small for very,
very good reasons.

> Is it a good idea to make the *kernel*, of all things, a memory hog and/or
> more vulnerable to memory pressure?

First, I think you're going a bit far suggesting that this would
inevitably turn the kernel in to a memory hog. It *might* make it use
more memory (I qualify this because heap fragmentation may turn out to
be more of a problem with a long running kernel with manual memory
management than any additional memory overhead of automatic memory
management). Also, I wouldn't necessarily assume that this makes it
more vulnerable to memory pressure. Indeed, it's quite possible the
added flexibility of a sophisticated automatic memory management
system may make it easier to respond to memory pressure.

> In userland you have a lot more choices about what performance trade-offs
> work for your application, but you're *going* to be running a kernel no matter
> what so you have less flexibility (and argument that, logically, would argue for a
> GC/noGC compile time option, an interesting idea).

Instead what tends to happen is that one builds a memory management
scheme designed to perform as well as possible in as many different
scenarios as possible.... sounds exactly what automatic memory
management systems are designed for, doesn't it? ;-)

> For my own purposes, the times I care most about kernel performance is for
> responsiveness, and last I checked "real-time" and "garbage collection"
> didn't belong in the same sentence, and even making it tolerable requires
> a great deal of sophistication.

Check again. ;-) They actually have ways of doing this now. But you
are right, you do need a sophisticated automatic memory management
system to get the right performance. Presumably though, if you were
going to put any kind of system like that in a kernel, you'd probably
try to make it as sophisticated as possible.

> Ref. counting, the whipping boy of the pro-GC fundamentalists, is mostly
> inherently incremental (the major exception being naive algorithms that
> will try to reap an entire list at once when you release the head).  I am most
> often willing to trade total throughput for predictable response, but that is of
> course purely a matter of the jobs you want to do.

So here's a thought experiment for you... think about the direction
CPUs and systems are taking. More and more cores. More and more
devices who can operate and interact asynchronously with the kernel.
In general, more and more issues with concurrency in a kernel. Now, to
do reference counting right, you need to guarantee that all your
reference counting operations are atomic....

Now tell me that reference counting kernels provides predictable
response rates. ;-)

I suspect these researchers were looking at more sophisticated
mechanisms than reference counting for exactly this reason, and
ironically the result could very well be a kernel which provides more
statistical certainty about response rates.

> What I was really getting at was in response to the article and it's
> typical fear of manual allocation.  The argument I was hinting at was the
> same one Linus made against microkernel architecture.  It's easier to just
> do the hard work to make sure the kernel is leak-free than to do the same
> for all of userland, and if you buy Linus' argument the kernel is
> precisely the place where you should least make performance compromises
> then you can only justify moving to GC on the throughput argument.  As I
> was arguing, I don't think that argument is so bulletproof.

One should keep in mind that the "Linus" mindset only applies until
things become hideously complicated (and the kernel has undergone
revisions to reflect this). If you look at kernels designed for large
numbers of cores, you'll find that they get increasingly complex (and
therefore difficult to thoroughly test and tune, let alone being
stable) unless some "performance sapping" abstractions are applied.

> GC is a big win for certain allocation patterns and not so much for
> others.

The allocation patterns it is a win for are very much dependent on how
the memory manager was tuned, which ironically is also the case for
explicit memory management. The only difference is that explicit
memory management gives an application developer who can't tweak the
memory manager more knobs to turn to try to get things right. Aside
from third party device driver authors (who tend to have common
allocation patterns) the folks in control of the kernel code are the
same people who'd be in control of the memory manager.

> Is the kernel really full of places where manual allocation is an
> impossible burden?  (That's a serious question--I don't know about the
> typical patterns in the kernel.  In fact, all of the questions I posed are
> serious questions.)

Well, the kernel has a number of problems when it comes to memory
management. It has resources whose allocation and deallocation
patterns are essentially random. Sometimes they even have variable
sizes. Since the kernel needs to run forever with consistent
performance, it needs to be able to continue to allocate potentially
large contiguous structures even after billions of allocations (the
Linux kernel actually isn't terribly great at this). It also needs to
try to reorganize these structures in memory in order to maximize both
cache efficiency and potentially paging. So, ideally what you want to
do is to choose an initial allocation strategy that works out
efficiently for the 95% case, and then be able to reorganize those
allocations when the 5% cases comes up.

So, all in all, you tend to end up with something that looks
suspiciously like automated memory management, even if it isn't.

--
Chris