The Managed Runtime Initiative [LWN.net]

Index entries for this article
Kernel	Managed Runtime Initiative

Kernel feedback for GC (was: The Managed Runtime Initiative)

Posted Jun 17, 2010 2:53 UTC (Thu) by cesarb (subscriber, #6266) [Link] (3 responses)

One thing I once thought about many years ago was a way to provide feedback to a userspace GC from the kernel as to how much memory it should use. If the kernel was under memory pressure it would tell the userspace GC to discard some pages. On the other direction, the userspace GC would tell the kernel about how many pages it expected to be able to free easily, and how many pages it expected to be able to free with a bit more effort (running a slower memory compaction, for instance).

The idea was to allow userspace programs to use the whole memory as a cache (for instance, for Firefox's memory cache) without the risk of going into swap. Also, if there were several GC-using userspace programs (for instance, several JVMs), they would be able to share the memory instead of fighting for it.

The API would be something that you would mmap() in your address space, some way to tell that something to free a page in that mapping (turning it into the shared copy-on-write zero page), some way for the program to tell the kernel how many pages it wanted to use for that memory area (a minimum value below which it cannot free anymore, an optimum value, and a maximum value above which it has no use for the memory), and some way for the kernel to notify the program about the desired usage levels for that memory area (minimum, optimum, and maximum values). As you can see, I did not work out the API details.

Kernel feedback for GC (was: The Managed Runtime Initiative)

Posted Jun 17, 2010 12:10 UTC (Thu) by alex (subscriber, #1355) [Link]

That sounds like extending the sort of information you can pass with the madvise() methods.

Kernel feedback for GC (was: The Managed Runtime Initiative)

Posted Jun 19, 2010 12:26 UTC (Sat) by bcopeland (subscriber, #51750) [Link]

There's some research in that direction. Here's a paper.

Kernel feedback for GC (was: The Managed Runtime Initiative)

Posted Jun 24, 2010 7:04 UTC (Thu) by renox (guest, #23785) [Link]

Another research about VMM / GC interaction is "Garbage collection without paging".

One author even wrote that he sent a patch to lkml but it was rejected :-(

Now that Java is opensource, one can hope that at some point GC and VMM will stop ignoring each other..

Pauses

Posted Jun 17, 2010 3:09 UTC (Thu) by ncm (guest, #165) [Link] (55 responses)

The problem this is supposed to relieve, "application pauses caused by garbage collection", is real enough. It's quite an embarrassment in this day and age. Recently I read that BASIC programs in the '80s were prone to such pauses, as if it had long since been solved, but until very recently, Firefox was pausing on me for 15 seconds at at a stretch, every few minutes. That it takes such an intrusive set of kernel patches to try to address this problem without application-level restructuring illustrates its true magnitude. (Promoters of slow languages characteristically refer to this, like other systemic problems, as "some slight overhead". When you hear the expression, it's best to think "orders of magnitude".)

The correct solution is to avoid programs that depend heavily on garbage collection.

Pauses

Posted Jun 17, 2010 3:52 UTC (Thu) by flewellyn (subscriber, #5047) [Link] (45 responses)

Or use a better garbage collector than a "stop-the-world" mark-sweep. Incremental, real-time GC has existed for some time now.

Pauses

Posted Jun 17, 2010 4:24 UTC (Thu) by ncm (guest, #165) [Link] (38 responses)

Users don't get to choose that option, so the choice is typically bad GC or a program that doesn't depend on GC.

GC subsystems promoted as solving all crippling problems have existed long enough that if they really were usable, they would be used everywhere. Apparently, either such GC solutions cannot be packaged in such a way that they can be used in each new project, or they impose constraints incompatible with other system-level requirements. Or both. Or, maybe, no GC system actually does solve all the crippling problems, in real programs that run on real machines

Pauses

Posted Jun 17, 2010 5:22 UTC (Thu) by flewellyn (subscriber, #5047) [Link] (35 responses)

Lisp systems have had good GCs for many years.

Pauses

Posted Jun 17, 2010 6:49 UTC (Thu) by ncm (guest, #165) [Link] (33 responses)

Somehow, this fact has not led to good GCs appearing in places where they might find practical use, or even in all currently maintained Lisp systems.

Pauses

Posted Jun 17, 2010 14:01 UTC (Thu) by nix (subscriber, #2304) [Link] (32 responses)

(the following is teaching my grandfather to suck eggs)

Part of the problem is that writing a GC that tracks stuff residing on the C stack requires either pervasive changes to how your program does *all* its memory management, or (for things like the Chicken collector) pervasive changes to how your functions call each other and how the stack is managed. (The Boehm GC, via a triumph of inspired hackery, manages to do the first without source code changes: but it's computationally expensive as GCs go, not type-accurate, and can sometimes leave extra garbage lying around. I don't really understand why more C programs don't use the Boehm GC, though, it's a hell of a lot better than no GC at all. Perhaps C programmers *like* manual memory management? :/ )

If you can guarantee that you'll never have pointers to GCed objects anywhere on the C stack when a GC happens, it gets much much simpler, but this is a really rather harsh requirement and most systems using a GC cannot satisfy it.

Pauses

Posted Jun 17, 2010 14:18 UTC (Thu) by Tet (subscriber, #5433) [Link] (21 responses)

Perhaps C programmers *like* manual memory management?

Yes, some of us do. Or rather, I don't like doing it in and of itself. But I love the determinism of it.

Pauses

Posted Jun 17, 2010 15:16 UTC (Thu) by nix (subscriber, #2304) [Link] (20 responses)

Quite so. Deterministic GC is possible: it's just GC in which you must explicitly insert calls to fire off a GC cycle. (At the C level, this is how all garbage collectors are implemented, of course...)

But when you're dealing with complex enough data structures (lots of cycles, trees with pointers to each other and so on), explicit memory management moves from 'deterministic' to 'lethally complex and horrifically annoying'. That's when GC really starts to be useful (and that's why GCC has a special-purpose garbage collector of its very own.)

Pauses

Posted Jun 18, 2010 13:47 UTC (Fri) by i3839 (guest, #31386) [Link] (19 responses)

That's when you have to start simplifying and improving your design instead.

Seriously, you have to keep track of all links and pointers and datastructures anyway, memory management is only very little additional work. If it's lethally complex and horrifically annoying then your other code is too.

Pauses

Posted Jun 20, 2010 20:11 UTC (Sun) by nix (subscriber, #2304) [Link] (14 responses)

Unfortunately, some problems (e.g. anything at all to do with translation/compilation/optimization) simply *are* intrinsically complex, and anything involving graphs with entities attached with varying lifetimes *is* going to have a horrific time without GC. (Reference counting can help in many other cases, but if the graphs have any cycles in them, you're dead.)

Pauses

Posted Jun 22, 2010 13:48 UTC (Tue) by i3839 (guest, #31386) [Link] (13 responses)

Yeah, graphs with cycles are tricky to do without GC. You would need to
walk the graph and basically do manual GC now and then. That's a hundred
lines of extra code which runs when you want it to run. Trying to do more
classic manual memory management would be horrific indeed, but when done in
a way that fits the situation it adds negligible coding/complexity overhead.

For complication/translation/optimization stuff you generally can just
allocate everything you need and throw everything away afterwards, e.g.
at program exit. Usually the optimization complexity explodes, so you
want to limit the size of the problem anyway.

It's like with locking; You don't have to always use the same granularity.

Pauses

Posted Jun 22, 2010 20:30 UTC (Tue) by nix (subscriber, #2304) [Link] (12 responses)

For complication/translation/optimization stuff you generally can just allocate everything you need and throw everything away afterwards, e.g. at program exit.

Hang on, I thought people were complaining that GCC used too much memory? This would make its memory use balloon insanely (many gigabytes to compile any nontrivial program).

Compilation always creates many intermediate data structures, many of which are elaborate graphs or have pointers to each other. You really do want to throw them away when you can, and you really do not want to do this by hand.

Pauses

Posted Jun 22, 2010 22:53 UTC (Tue) by i3839 (guest, #31386) [Link] (11 responses)

In my experience most memory is used when linking, not when compiling,
but I guess it can get pretty bad when compiling huge C++ codes with
plenty templates.

The thing is, you probably can't throw away much in each intermediate step,
because you do need all that info, but you can easily throw away data
generated by a whole intermediate step and keep only the intermediate
results. So the main way to limit memory usage is by limiting the working
set. GC doesn't help with that.

Anyway, gcc already uses GC it seems, so if it uses too much memory then
adding a GC won't help. (http://gcc.gnu.org/wiki/Memory_management)
That it would use much more without GC seems unlikely.

I guess my argument boils down to: Managing object lifetime is only a
small part of memory management, and GC only helps with that.

Pauses

Posted Jun 23, 2010 13:10 UTC (Wed) by nix (subscriber, #2304) [Link] (10 responses)

In my experience most memory is used when linking, not when compiling

The only reason you think that is because GCC runs several garbage collections when compiling even a small file.

And your assumption about being able to throw away whole intermediate steps at once -- that's how GCC used to work when it kept everything in obstacks. It's often correct, but if it's wrong only in part you have to keep a lot around because you have no way to tell which bits you're using and which you're not.

(actually, to be maximally pedantic it's almost never correct because most passes annotate or shuffle some tree somewhere: if it did nothing all the time it would be a pretty useless pass.)

But it seems you don't get it. I know GCC already has a GC: I'm using it as a counterexample to your claim that GC is unnecessary because you can always simplify your datastructures. You cannot always do that (although you often can and it should be the first thing you try, if practicable), and doing it by hand (i.e. explicitly triggering GC cycles) is often impractical too.

Managing (or rather mismanaging) object lifetime is the part of memory management that is most likely to cause bugs in C programs (less so in C++); GC largely eliminates that as a cause of bugs.

Pauses

Posted Jun 25, 2010 14:57 UTC (Fri) by i3839 (guest, #31386) [Link] (9 responses)

> (actually, to be maximally pedantic it's almost never correct because
> most passes annotate or shuffle some tree somewhere: if it did nothing
> all the time it would be a pretty useless pass.)

That's why I was talking about compilation stages, not optimisation
stages. I don't think you can free any significant amount of memory
between the latter ones, because you never know what may be needed
in the future. Even if you just replace multiple nodes with fewer ones
you can't save much memory because of fragmentation. At best it's a
factor 2, in which case you have to manage overall memory consumption
by reducing your working set anyway.

I'm also sure that GCC does not use hundreds of megabytes to keep
very complex graphs in memory.

I'd rather have GCC spend its time on using 10 times the memory for
compiling small files fast than waste time on reducing memory usage
by running slower and not really achieving it anyway.

> But it seems you don't get it. I know GCC already has a GC: I'm using it
> as a counterexample to your claim that GC is unnecessary because you can
> always simplify your datastructures. You cannot always do that (although
> you often can and it should be the first thing you try, if practicable),
> and doing it by hand (i.e. explicitly triggering GC cycles) is often
> impractical too.

No, I don't get it. You brought GCC as an example of something that people
complain about that uses too much memory, and of something that uses
complex datastructures that can't be easily handled with manual memory
handling. What I'm trying to say is that GC doesn't solve any real problems,
it's just convenience for the lazy, but when you do use too much memory
(bloat or leak) it won't help you at all. When memory handling is important
then you have to put it into your program design on a higher level. You seem
to assume that GCC would use a lot more memory if it didn't use GC. I think
it's rather that GC doesn't improve the situation.

> Managing (or rather mismanaging) object lifetime is the part of memory
> management that is most likely to cause bugs in C programs (less so in
> C++); GC largely eliminates that as a cause of bugs.

In my experience memory leaks almost never happen and when they do
happen they're easily fixed. At least in C: When it happens with Java it's
a bit harder because then you have to hunt down the dangling references
and you can't use Valgrind. Firefox is a different story, but even a perfect
GC wouldn't have saved it. (But the problem of C++ programs is that C++
adds its own additional complexity without making anything easier, with
as a result more bugs and memory leaks in general.)

Pauses

Posted Jun 27, 2010 17:05 UTC (Sun) by nix (subscriber, #2304) [Link] (7 responses)

That's why I was talking about compilation stages, not optimisation stages.

There is no meaningful distinction, after parsing, between translation and optimization. There are only compilers that optimize more, and compilers that optimize less.

I'm also sure that GCC does not use hundreds of megabytes to keep very complex graphs in memory.

You're hilariously wrong. (Seriously, what do you think it's doing with the gigabytes of space it can sometimes use? Playing electronic tic-tac-toe? Of course it's holding graphs, and other things some of which it indeed can never throw away e.g. hordes of decl nodes for all the declarations in all the header files it's parsed...)

I'd rather have GCC spend its time on using 10 times the memory for compiling small files fast than waste time on reducing memory usage by running slower and not really achieving it anyway.

You'd say that until you tried to compile something and it failed because you ran out of memory, or it started taking a thousand times longer than otherwise because you were pushed into swap. Also, the more we reduce memory usage, the better our (still quite awful) cache utilization becomes.

You seem to assume that GCC would use a lot more memory if it didn't use GC. I think it's rather that GC doesn't improve the situation.

No. If it never garbage collected and didn't free(), as you suggested, it would use incredibly much more memory (many times more than it does now).

As for what would happen if it was designed without GC, well, we have actual evidence of that because pre-3.0 it did indeed have no GC, and used manual memory management for everything, with explicit lifetimes. Maintaining the object lifetimes was a nightmare and there were countless bugs raised due to SEGVs caused by something being freed when it shouldn't.

In my experience memory leaks almost never happen and when they do happen they're easily fixed.

That's true until you have to manage complex data structures. It's also only true if your memory leak (or, worse, double-free) isn't tied up with an API bug somewhere and not fixable without changing the API. I've seen that too and it was a nightmare to fix (we had to change every caller and there were hundreds, ick, never again).

GC may be more inefficient than manual memory management (theoretically this is not true, but I've never heard of a situation where that theory is turned to practice) and is surely not right for every situation, but it wipes out all these problems at a stroke.

And to be honest if asked if I'd rather have a program that ran more slowly but used GC or a program that didn't work I'd surely pick the former.

Pauses

Posted Jul 4, 2010 17:14 UTC (Sun) by i3839 (guest, #31386) [Link] (6 responses)

Yes, but compilers don't grab the whole source and optimise everything at
once, at least not generally, though they can do that. So it's fine if they
use a bit more memory when compiling one unit, the only moment when the
whole program has to be in memory is when linking.

Considering that optimising is a computationally expensive process which
grows much more than O(n) if the working set increases by n, I'm really
surprised that memory usage is a limiting factor at all, and that compile
time hasn't gone through the roof before this became a problem.

What the hell is gcc doing to achieve this? Making hundreds of copies of
all the nodes every time it modifies them? (I know you can trade memory
usage for time with certain algorithms, but is gcc actually doing that?)

In a dark past I compiled the whole system on a slow, crappy computer with
128 MB of RAM (bloody Gentoo, but Archlinux had no i586 binaries), and I'm
pretty sure it was totally limited by CPU speed. Took a whole day, but it
got to the end. What code makes gcc use hundreds of megabytes of memory
in your experience?

But yeah, if you have a huge body of code with crappy internal APIs then
GC is probably a very good idea. Using explicit memory allocation for short
lived objects plainly sucks, GC is better for that. In normal C the thing is
to avoid such objects in the first place. I only use malloc for long-lived
objects and mostly at program start-up or once per major event, like a new
client connecting. If for whatever reason (IMHO mostly because of bad design,
but not always) the code isn't orderly and clear, but messy, then having
no GC would be a bit of a hell, I admit. But you might want to consider
rewriting the whole thing in Python too, because just using a GC won't
help much. And that's my main point you seem to ignore, that if having GC
improves the situation, it generally means you got other, bigger, design
problems. The case where it's really because of "complex data structures"
is a rare case indeed. Mostly it's unnecessarily complex and then it's
plain bad design.

Pauses

Posted Jul 7, 2010 15:56 UTC (Wed) by nix (subscriber, #2304) [Link] (5 responses)

Yes, but compilers don't grab the whole source and optimise everything at once, at least not generally, though they can do that. So it's fine if they use a bit more memory when compiling one unit, the only moment when the whole program has to be in memory is when linking.

Well, -flto does exactly that. In any case, grabbing one translation unit and optimizing it can easily use hundreds of megabytes of memory, and without doing garbage collections (i.e. never freeing storage) would easily use many gigabytes.

Considering that optimising is a computationally expensive process which grows much more than O(n) if the working set increases by n, I'm really surprised that memory usage is a limiting factor at all, and that compile time hasn't gone through the roof before this became a problem.

Well, compile time having gone through the roof is a perennial complaint about GCC, and its L2 cache utilization is pretty awful.

What the hell is gcc doing to achieve this? Making hundreds of copies of all the nodes every time it modifies them? (I know you can trade memory usage for time with certain algorithms, but is gcc actually doing that?)

No, but it has a lot of optimization passes, several IRs, and it does a lot of work. Also, headers are large these days: decl nodes alone can use hundreds of megabytes, and recent work to reduce the size of decl nodes has reduced the memory consumption of the compiler considerably.

You might find the -fmem-report flag interesting.

(Note that reuse of tree nodes is a classic example of a time where GC is very useful, because all of a sudden that object's lifetime must be extended, and telling the entity that originally allocated it is likely to be unpleasant.)

In a dark past I compiled the whole system on a slow, crappy computer with 128 MB of RAM (bloody Gentoo, but Archlinux had no i586 binaries), and I'm pretty sure it was totally limited by CPU speed. Took a whole day, but it got to the end. What code makes gcc use hundreds of megabytes of memory in your experience?

Virtually anything in C++. Anything more than a few thousand lines long in C. It's downright commonplace. It's pretty common to see GCC using >500Mb, and I've seen it using gigabytes before now. If you run several compilations in parallel, you'll need even more...

But yeah, if you have a huge body of code with crappy internal APIs then GC is probably a very good idea. Using explicit memory allocation for short lived objects plainly sucks, GC is better for that.

That's exactly the class of allocations for which obstacks are good and GC can often be forgone. When you have long-lived allocations in a complex webwork in elaborate interconnected graphs, then is when GC becomes essential. And GCC has elaborate interconnected graphs up the wazoo. The quality of internal APIs is mostly irrelevant here: it's the nature of the data structures that matters.

The case where it's really because of "complex data structures" is a rare case indeed.

I find that about 5% of the programs I write start to get complex enough data structures that memory management becomes a serious burden. I think it depends on the class of program, really. If you mostly write little scripting things or financial add-up-these-numbers programs, then, no, complex data structures will be uncommon. If you're hacking on the inside of a database server or a compiler, then they'll be common.

Pauses

Posted Jul 8, 2010 14:36 UTC (Thu) by etienne (guest, #25256) [Link] (2 responses)

> Note that reuse of tree nodes is a classic example of a time where GC is
> very useful, because all of a sudden that object's lifetime must be
> extended, and telling the entity that originally allocated it is likely
> to be unpleasant.

I am not a specialist of GC, but I wonder if the usual malloc/free interface is wrong, and if we should use something like malloc/memlock/free.
Basically, the function which create the data allocates it, all functions using the data memlock() it, and every function calls free() when it finishes using that data. Free() decrements a counter and frees the memory when the counter reaches zero.
Has that already been tried and what would be the problem of it?

Pauses

Posted Jul 8, 2010 14:52 UTC (Thu) by nye (guest, #51576) [Link]

>Basically, the function which create the data allocates it, all functions using the data memlock() it, and every function calls free() when it finishes using that data. Free() decrements a counter and frees the memory when the counter reaches zero.

How would this be different from any other form of reference counting, with its attendant problems?

Pauses

Posted Jul 9, 2010 16:22 UTC (Fri) by nix (subscriber, #2304) [Link]

Straight reference counting works if you can tell who the 'users' are, and if the data structures are fairly simple. But we can't really ask everyone touching a graph to walk the entire graph and all its data structures and increment, then decrement, all its reference counts (that would be much more cache-unfriendly and unpleasant to maintain than what is done now); and because nodes are often shared between graphs we can't have one giant reference count across the whole graph... and if the reference-count-freer walks the graph and only frees if all connected entities are at refcount zero, you might as well drop the reference count, because what you've got there is a garbage collector. :)

Pauses

Posted Jul 14, 2010 14:23 UTC (Wed) by i3839 (guest, #31386) [Link] (1 responses)

-flto enables link time optimisation, which is IMHO something slightly
different, and earlier (current?) implementation has a reputation of being
slow. I was thinking more about -combine -fwhole-program. As far as I know
link time optimisation is about doing further optimisations before the real
linking.

-fmem-report flag is indeed interesting. On my current project, which
is about 4K lines of C code, it reports 16MB allocated with combine +
whole-program, 12MB when using dietlibc, and max 3MB when compiling
files one at a time.

So assuming C++ is ten times worse, and the code ten times bigger, then
you're indeed easily using gigabytes of memory. I guess you don't want
to compile big C++ programs at once though, doing it per file should be
fine.

> That's exactly the class of allocations for which obstacks are good and
> GC can often be forgone. When you have long-lived allocations in a
> complex webwork in elaborate interconnected graphs, then is when GC
> becomes essential. And GCC has elaborate interconnected graphs up the
> wazoo. The quality of internal APIs is mostly irrelevant here: it's the
> nature of the data structures that matters.

With crappy APIs/design you can't allocate objects on the stack, but are
forced to allocate them dynamically even if they're short lived.

The problem of elaborate interconnected graphs is that it's hard to end
up with nodes with no references at all, so GC usually won't help much.
And even if it does it probably doesn't reduce peak memory usage. So yes,
in such cases you want something like GC, for your own sanity, but it
won't improve the total memory usage much if you don't limit the graph
size some other way.

Pauses

Posted Jul 15, 2010 17:06 UTC (Thu) by nix (subscriber, #2304) [Link]

Link-time optimization works by having the compilation phases drive the compilation to the GIMPLE tree stage, then writing it out and having the link stage invoke the compiler again (via collect2, or via a linker plugin: the latter is preferable because then you can run it over the contents of .a archives as well) to read in all the GIMPLE trees and optimize them. At that stage you've got all the trees written out by all the compilation phases in memory at once. And a good few optimizations will, unless bounded explicitly, start using up crazy amounts of memory when hit with large programs all at once. (Of course they *are* bounded explicitly. At least all of them that anyone noticed are.)

-combine -fwhole-program has a similar memory hit, for similar reasons.

C++ is a good bit worse memory-wise than C, mostly because the headers make C headers look like child's toys: they have a lot of definitions in them and a large number of very complex declarations. I've known compiling *single C++ files* to eat a couple of gigabytes before (although, admittedly, those were exceptional, things like large yacc parsers compiled with C++: mysql's SQL parser is a good example).

Pauses

Posted Sep 6, 2010 20:22 UTC (Mon) by Blaisorblade (guest, #25465) [Link]

> That's why I was talking about compilation stages, not optimisation
stages.
> I don't think you can free any significant amount of memory
between the latter ones, because you never know what may be needed
in the future.

Well, if no pointer exists to an object, there's no way somebody can use it. It seems you don't know what you're talking about.

> Even if you just replace multiple nodes with fewer ones you can't save much memory because of fragmentation

Fragmentation only exists in languages which don't support GC well (i.e., C). GC have been able to fix that for ages. Whether we have decent heuristics for handling it without using too much CPUs is an open issue, when that's a problem choosing the GC algorithm among the implemented ones is the best solution.

Pauses

Posted Sep 6, 2010 20:14 UTC (Mon) by Blaisorblade (guest, #25465) [Link] (3 responses)

> That's when you have to start simplifying and improving your design instead.
> Seriously, you have to keep track of all links and pointers and datastructures anyway, memory management is only very little additional work. If it's lethally complex and horrifically annoying then your other code is too.

First, refcounting is GC, and lots of C programs use it.

I used to program in C in kernel space (on UserModeLinux, I remember a nix, probably you, on our MLs), now I usually program in functional languages. If you ever tried, you'd realize that there, manual memory management would be much more code than getting the job done.

On the other hand, in C, and even in kernel space, reference counting is frequently used, especially for just _everything_ shared among multiple threads. It might be omitted for stuff which is only manipulated under locks in certain ways, but kernel code craves for using as few locks as possible, so refcounting is required by the coding style for such cases.

And reference counting is... just another way to implement GC. Which is probably fine for those usages - but if you implement GC with it, it's often the worst way (because you really use it differently).

Pauses

Posted Sep 6, 2010 21:17 UTC (Mon) by nix (subscriber, #2304) [Link] (2 responses)

Yes, I'm the same Nix :)

The biggest problem with refcounting GC (ignoring the cycle problem) is that its constant tweaking of refcounts leads to appalling cacheline bouncing with concurrent code. (Slightly different from the nasty cache effects of crude old mark-and-sweep collectors.)

Pauses

Posted Sep 6, 2010 22:38 UTC (Mon) by Blaisorblade (guest, #25465) [Link] (1 responses)

The biggest problem with refcounting GC (ignoring the cycle problem) is that its constant tweaking of refcounts leads to appalling cacheline bouncing with concurrent code. (Slightly different from the nasty cache effects of crude old mark-and-sweep collectors.)

Yep, that's what doesn't happen (not that much) in kernel (with explicit refcounting) and what smarter refcounting GCs try to avoid as much as possible. No refcounting for stack operations (which implies a stop-the-world phase to scan the stack) is an old optimization; the Recycler from IBM does something better, but there must be reasons why nobody actually uses it, and reading the paper with attention gives some suggestions. Most importantly, the most reputable comment I got about it was "it's crap", unfortunately I couldn't ask details.

<OT>

Yes, I'm the same Nix :)

Nice to see you again - I've noticed your nick a number of times here. And now I speak as a researcher in programming languages and their implementation - what a huge change.
</OT>

But back to UserModeLinux, I agree that it would definitely make sense to use these tricks, or at least something related (you mentioned that somewhere else). We were actually trying to push forward some code for our needs, i.e. Ingo's remap_file_pages patch, which I resumed. It allowed playing not only with offsets but also with protection bits of individual pages. It seems that here, the guys are doing much more stuff - including, probably, batched VM operations, since they need to use them to set up read barriers, i.e. to trap memory reads for their GC, which was originally developed for a RISC CPU which gives a small HW support for them!

But I would have needed a full-time position to handle that, rather than working on it on my free time, after UML maintenance and support, and UML as a whole was severely lacking manpower. But understanding and fixing some bugs in Ingo Molnar's code (on which he had played just for a small while) was one of my best achievements by that time.

Pauses

Posted Sep 6, 2010 23:17 UTC (Mon) by nix (subscriber, #2304) [Link]

Nice to see you again - I've noticed your nick a number of times here. And now I speak as a researcher in programming languages and their implementation - what a huge change.

I'd wondered what you'd been doing when you dropped out of UML hacking :)

Just like to say thanks for the UML work over the years, it kept my firewall happy for many years before that machine croaked its last and I switched to a Soekris... UML seems to have been obsoleted by qemu now, which is in a way a shame: it did a lot of things in interesting and unusual ways, and I'm fairly sure nobody else had ever abused ptrace() quite as badly (given the number of ptrace() bugs UML teased out, I think we can be sure of it).

allocation in C

Posted Jun 17, 2010 16:02 UTC (Thu) by tialaramex (subscriber, #21167) [Link] (3 responses)

Speaking about the largest C project I work on...

In some places the reason I don't use a GC is because I'm lazy and there wasn't one sat there ready to go. It is possible that I should learn to use the Boehm GC in these cases and that I should evangelise its use.

But in a lot of places it's because it's because the code's on the critical path. I don't see a GC (and particularly one you admit is "computationally expensive") buying us more than it costs in these codepaths. This is optimised code, where people have chosen the algorithms very carefully and read the latest papers, and run benchmarks to find good parameters and done all that good stuff. And we already have (by the nature of the system) an insatiable appetite for RAM so we certainly don't want to make that any worse.

Perhaps a better goal is to stop using C at all for the "lazy" code. I probably spend as little as 30% of my programming time writing C these days anyway, maybe it should be less than 10%. Java for example seems to work well enough, it's slow and it wastes a lot of RAM, and it's missing a bunch of features I like, but it works well enough. Probably a lot of my "lazy" code could be Java, more than already is.

allocation in C

Posted Jun 20, 2010 20:13 UTC (Sun) by nix (subscriber, #2304) [Link] (2 responses)

In some places the reason I don't use a GC is because I'm lazy and there wasn't one sat there ready to go. It is possible that I should learn to use the Boehm GC in these cases and that I should evangelise its use.

Since using the boehm GC in its simplest form consists of including one header and instantly all your malloc()s are garbage-collected, that's not hard. (You don't need to take the free()s out, but they're no longer *necessary*, merely hints that this block no longer needs to be scanned for possible pointers.)

But yes, avoiding C for the boring stuff is probably best. Embed a better language (or embed the C in a better language) and use that, and get GC for free :)

allocation in C

Posted Jun 21, 2010 0:33 UTC (Mon) by khc (guest, #45209) [Link] (1 responses)

Or with LD_PRELOAD ;-) It's hard to decide which one is simpler though.

allocation in C

Posted Jun 21, 2010 20:54 UTC (Mon) by nix (subscriber, #2304) [Link]

I suppose it depends if you have the source to all the bits or not. If you do, using LD_PRELOAD would be just icky. If you don't, it's unavoidable.

Pauses

Posted Jun 17, 2010 17:47 UTC (Thu) by jordanb (guest, #45668) [Link] (5 responses)

> (The Boehm GC, via a triumph of inspired hackery, manages to do the first
> without source code changes: but it's computationally expensive as GCs go,
> not type-accurate, and can sometimes leave extra garbage lying around. I
> don't really understand why more C programs don't use the Boehm GC, though

Seriously?

With a sales pitch like that, who wouldn't use it? :P

Anyway, I think RAII is a better approach to memory management than GC for high-performance applications. It's deterministic and has very little run-time cost. The only disadvantage is that it doesn't exist in C, but it's supported by all modern languages except the ones that have gone the builtin-GC route.

RAII, but no GC?

Posted Jun 17, 2010 19:05 UTC (Thu) by sbishop (guest, #33061) [Link] (3 responses)

I am not aware of a modern language which does not have built-in GC. (Though "built-in GC" is a requirement under most people's definition of "modern language".) Which languages are you thinking of? I don't mean to argue with you; I'm just curious.

I'm also curious to know where RAII is used outside of C++.

RAII, but no GC?

Posted Jun 17, 2010 19:29 UTC (Thu) by alextingle (guest, #20593) [Link] (2 responses)

Python uses RAII, I believe.

RAII, but no GC?

Posted Jun 17, 2010 21:18 UTC (Thu) by tack (guest, #12542) [Link] (1 responses)

Not exactly. It's a peculiarity of (current versions of) CPython that RAII patterns can work, however there's nothing in the language that specifies that behavior, and you can't expect it from other implementations like Jython, or perhaps not even from future versions of CPython.

RAII, but no GC?

Posted Jun 19, 2010 13:39 UTC (Sat) by cortana (subscriber, #24596) [Link]

Perhaps Alex was referring to to the 'with' statement: http://docs.python.org/reference/compound_stmts.html#with

Pauses

Posted Jun 20, 2010 20:18 UTC (Sun) by nix (subscriber, #2304) [Link]

With a sales pitch like that, who wouldn't use it? :P

Heh. Well, it does about as well as it's possible to do in C without massive assistance from the application. But that takes tradeoffs...

Pauses

Posted Jun 19, 2010 5:34 UTC (Sat) by jonabbey (guest, #2736) [Link]

And so do Java VMs.

Modern versions of the JDK really do have truly exceptional GC performance. Java 7 will feature a compacting, predictable delay time GC system that can take excellent advantage of many-core systems to provide great throughput.

With GC systems, there's a trade-off between speed of collection, CPU efficiency, and overall memory usage. Java allows these parameters to be tuned for a specific use case, but it is true that the default configuration tends to emphasize CPU efficiency over overall memory usage.

Pauses

Posted Jun 17, 2010 14:37 UTC (Thu) by NAR (subscriber, #1313) [Link] (1 responses)

GC subsystems promoted as solving all crippling problems have existed long enough that if they really were usable, they would be used everywhere.

They might be used in a telephony exchange system near you? I'm not that familiar with the Erlang GC, but I haven't met the "everything stops for 15 seconds" problem yet. Of course, it's still possible to leak memory (i.e. breaking the code that removes the elements from a list, so it just grows and grows), and sometimes an explicit garbage collection frees up a surprising amount of memory, but it doesn't happen that often.

Pauses

Posted Jun 19, 2010 5:36 UTC (Sat) by jonabbey (guest, #2736) [Link]

Erlang benefits a lot from its functional design. If there's not a function working on a piece of data, it can be collected.

Real-time GC does not work, period.

Posted Jun 17, 2010 10:57 UTC (Thu) by khim (subscriber, #9252) [Link] (3 responses)

Problems with real-time GC is not the GC itself. Rather it's general problem: you can't manage memory efficiently unless the program does it. If you program keeps links to gigabyte of long-dead objects and then suddenly drop links to all these objects to create another gygabyte of objects you'll see UI freezes no matter what you do. And if your program is accurate enough and careful enough with allocation of objects then it's usually easy to add manual allocation or trivial refcounting GC.

Good memory management is hard, good memory management with GC is harder. Not only you must think about references to objects - you must keep the capabilities of GC in mind too!

GC is great for batch-processing, but real-time? It does not work in practice beyong toy samples.

Real-time GC does not work, period.

Posted Jun 17, 2010 15:49 UTC (Thu) by marcH (subscriber, #57642) [Link] (1 responses)

> Rather it's general problem: you can't manage memory efficiently unless the program does it.

OK...

> And if your program is accurate enough and careful enough with allocation of objects then it's usually easy to add manual allocation or trivial refcounting GC.

If it is trivial then why do I have to do it myself?

See also "GC allows for entirely different algorithms" somewhere here:
http://www.azulsystems.com/blog/cliff-click/2009-09-06-ja...

Real-time GC does not work, period.

Posted Jun 17, 2010 23:28 UTC (Thu) by ncm (guest, #165) [Link]

It is trivial precisely because you don't have to do it yourself.

Real-time GC does not work, period.

Posted Jun 18, 2010 1:07 UTC (Fri) by pflugstad (subscriber, #224) [Link]

GC is great for batch-processing, but real-time? It does not work in practice beyond toy samples.

Hmmm... Been there, done that: embedded system running RTOS and RT Java, driving an avionics Mil-Std-1553 bus at 50Hz with <30ms latency under heavy load for many hours. Very non-trivial (several hundred thousand LOC).

Yes we had to pay attention to memory allocations in the time critical code paths, but that was actually pretty easy. And yes, we used the real-time GC that the RT Java gave us to essentially run in the background.

And we had to tune some other parts of the code where some programmers had made some dreadful data structure choices (which worked find under low utilization, but didn't scale). But mostly things worked and we didn't really pay much attention to memory allocations across the majority of the application. No stop-the-world pauses, no burps in latency (which there were before we tuned).

The key with the whole thing was to have enough memory available so the GC could come along behind and clean up without having to stop the rest of the system from running. Similar tests on a much more memory constrained device did not scale as well - but not: it is just a matter of scaling.

I'd done similar things on Windows with C/C++ and all the explicit memory management, so I'm very aware of the trade-offs. I'll take the GC thank-you-very-much, and RT GC does work just fine, IMO.

Pauses

Posted Sep 6, 2010 20:00 UTC (Mon) by Blaisorblade (guest, #25465) [Link] (1 responses)

> Incremental, real-time GC has existed for some time now.
Do you know how much slower it is? Like tens of percents in most cases?

Pauses

Posted Oct 10, 2010 1:18 UTC (Sun) by Blaisorblade (guest, #25465) [Link]

I forgot to point out that one of their contributions is incremental GC with very small overhead.

Pauses

Posted Jun 17, 2010 13:54 UTC (Thu) by nix (subscriber, #2304) [Link] (6 responses)

The correct solution is to avoid programs that depend heavily on garbage collection.

Like GCC! And Emacs! And Eclipse! hm, not sure what I'll write my code in now. vi, Notepad and TECO are still in the running.

(Your point is more valid for interactive programs, but as Emacs indicates, a sufficiently compelling program can cause people to put up with amazing delays, When I was running Emacs and X on a 6Mb 486 I regularly had to put up with 45s GC delays. I did so without -- much -- complaint.)

Pauses

Posted Jun 17, 2010 17:54 UTC (Thu) by dambacher (subscriber, #1710) [Link] (1 responses)

oh, emacs had this feature named "typing pause" nowerdays for some years now.-)

Pauses

Posted Jun 20, 2010 20:19 UTC (Sun) by nix (subscriber, #2304) [Link]

typebreak.el is your friend :)

Pauses

Posted Jun 17, 2010 23:39 UTC (Thu) by ncm (guest, #165) [Link] (3 responses)

You demonstrate the reach of ideology. What a normal person would treat as a crippling bug, you take without complaint because the editor is written in what you think is a cool language. But an awful lot of us do code in Vi, and have never suffered 45-second, or 2-second, pauses. Does the GC explain why Gcc has got so slow?

Pauses

Posted Jun 19, 2010 21:33 UTC (Sat) by marcH (subscriber, #57642) [Link] (1 responses)

> ... because the editor is written in what you think is a cool language.

Please be serious: how emacs is made internally has nothing to do with why most people choose to use it. Most emacs users do not even know what LISP is (or even worse; they hate it as configuration file syntax), and they could not care less about a 2 seconds delay per week.

Pauses

Posted Jun 20, 2010 21:05 UTC (Sun) by nix (subscriber, #2304) [Link]

Actually I *did* start using Emacs because of the runtime configurability and extensibility (and learnt Lisp as a result and fell in love with it), but I know I'm weird.

Its implementation language, of course, is partly ugly old Lisp and partly really rather nasty C (GCPRO, anyone?). The less that's in C and the more that's in Lisp, the better, as far as I'm concerned, but not because of the language -- more because, if it's in C, I can hack at it interactively, whenever I need to. :)

Pauses

Posted Jun 20, 2010 20:23 UTC (Sun) by nix (subscriber, #2304) [Link]

Does the GC explain why Gcc has got so slow?

Very possibly it does. When Apple was still contributing (back in the 4.0 days) someone (I think it was Mike Stump) ran shark over it, and saw a horrifying rate of L2 cache misses, something like one every twenty instructions if I recall. It appears that the GC's largest cost is not when it runs at all, but what it does to the program's locality of reference: scatters it all over the place, leading to absolutely pessimal cache behaviour.

GCC has been carefully migrating selected speed-critical things back into obstacks ever since: they may be really annoying (freeing must be in reverse order of allocation), but they are contiguous, and that's sometimes a major benefit.

(And, y'know, I did think that the 45-second pauses were a crippling bug, but then most other things on my system also had huge pauses at the time: 6Mb RAM in 1998 was not pleasant. The real problem was that my system was hugely under-RAMmed.)

With the smallest machine I regularly work on now having 12Gb RAM, it's amazing how little I can force myself to care about swap-induced problems and OOM. At least, for the next couple of years, until KDE4.9 or GNOME 3.5 bloats up and uses it all up again.

Pauses

Posted Jun 17, 2010 14:32 UTC (Thu) by SEJeff (guest, #51588) [Link]

Keep in mind that pauses of a few microseconds are way too much for certain environments (financial, aerospace, industrial, etc). Garbage collected languages in general are a serious problem in those sorts of environments.

The problem is that a lot of colleges teach those gc'd languages and the skillset pool is rather deep. Also, lets not forget the argument for RAD. A mere mortal can generally crank out a lot more java/C#/<insert_modern_garbage_collected_language_here> than raw C. Not that I'm hating on C by any means, but it isn't unreasonable for them to want their cake and eat it too.

Pauses

Posted Jun 17, 2010 18:22 UTC (Thu) by iabervon (subscriber, #722) [Link]

Until recently, Firefox was using a quite primitive JavaScript implementation. Avoiding stopping the world for GC is well-understood, but is only implemented when it seems important, because it involves a bunch of effort to implement. Even people implementing runtime systems are too lazy to implement all of the techniques they could use, when they aren't noticing performance problems that could be solved with those techniques. People don't choose a web browser based on whether it pauses with complex JavaScript; or, rather, they didn't until recently.

The Managed Runtime Initiative

Posted Jun 17, 2010 3:18 UTC (Thu) by russell (guest, #10458) [Link] (7 responses)

How is this the kernel's problem? Programs written in other languages don't seem to have this problem. It seems to me to be just java.

The Managed Runtime Initiative

Posted Jun 17, 2010 4:27 UTC (Thu) by elanthis (guest, #6227) [Link] (6 responses)

Bullshit. ALL GC languages have this problem. The apps you see written in other languages besides C# and Java are just generally tiny little micro apps barely worthy of being called an actual "application." They have small heap sizes, few allocated objects for the memory manager to deal with, and many are short-lived tools that will start and finish very quickly.

When you start dealing with very, very large applications -- like an entire browser, office suite, Photoshop-esque image editor, long-running server process, game engine, or many scientific tools -- then the number of allocated objects is very high, the total amount of allocated memory is often high, and the memory manager deals with an awful lot of allocation churn. These things are all really bad for most garbage collection algorithms.

They're really not all that great for classic C/C++-style manual memory management, either. A particularly good GC will actually be faster overall than even a well coded manual memory management using application. The problem is that the manual memory management approach spreads all of its time out amongst every allocation and deallocation. That means that there is never a big pause on one allocation only, and it also means that all the memory manager work happens at places in the code the programmer can easily identify. With automatic memory management, a big chunk of the garbage collection process (possibly all of it) can happen at any allocation without any deterministic way to identify it. Even with an incremental collector, this can lead to long pauses happening right in the middle of a relatively speed-sensitive bit of code; it's not a big deal if the GC happens during general idle loop processing in a GUI app but it can be noticeable if it kicks in during animation processing, for example.

So anyway, yeah, all garbage collected languages have the problem, just most garbage collected languages don't have so much as a single app on the scale of what Java or C# are frequently used for.

The Managed Runtime Initiative

Posted Jun 17, 2010 4:57 UTC (Thu) by skitching (guest, #36856) [Link]

Yep. Java's garbage-collection is pretty good; I wouldn't expect any language supporting GC to do much better. So I would bet this isn't java-specific.

Note that Azul systems aren't just talking about "large apps like an office suite". They sell 54-core CPUs and java virtual machines designed to "scale to 670 GB of memory".

So we are not talking about optimising applets here, but systems that can run stock markets, large brokerage houses, etc. But such applications are also sometimes sensitive to latency. The old "stop the world" garbage collectors would be a real problem here, but even "incremental" collectors may cause latencies to some threads.

And (I haven't read the released code) perhaps they are more interested in moving some memory-management tasks from kernel to user-space. Things like large database systems often try to bypass OS behaviour and manage some things themselves (eg file caches) because they know better than the OS what the usage patterns are. Sounds plausable that a JVM may also have these needs.

The Managed Runtime Initiative

Posted Jun 17, 2010 7:17 UTC (Thu) by helge.bahmann (subscriber, #56804) [Link]

"A particularly good GC will actually be faster overall than even a well coded manual memory management using application."

... but only when you are willing to throw about 4 times the memory an equivalent explicitly-managed program would use at the problem: http://www.cs.umass.edu/~emery/pubs/gcvsmalloc.pdf

This unfortunately means that performance-wise garbage collection fares particularly badly with "large" applications where the working set size approaches the available RAM.

GC myth propagation

Posted Jun 17, 2010 7:17 UTC (Thu) by ncm (guest, #165) [Link]

The assertion that GC systems may be faster than "manual" memory management is frequently made, but ill supported. In particular, it's easy and, in academia, encouraged to rig tests to avoid interacting badly with virtual memory. That's rarely so easy in Real Life.

"Eager", by the way, would be a more accurate moniker for what is normally done in C++, as there memory management, with the aid of destructors, is no wise more manual than in Lisp. Adopting the usage would allow GC promoters to hint at more honesty and scruples than their colleagues are inclined to exhibit.

The Managed Runtime Initiative

Posted Jun 17, 2010 15:42 UTC (Thu) by martinfick (subscriber, #4455) [Link] (2 responses)

"The apps you see written in other languages besides C# and Java are just generally tiny little micro apps barely worthy of being called an actual "application." They have small heap sizes, few allocated objects for the memory manager to deal with, and many are short-lived tools that will start and finish very quickly."

Hmmm, that sounds like better memory management to me. Good programmers have been writing small modular programs which do not live forever and work well together to create larger systems for decades. There are many reasons for this and easier/better memory management is on the list.

Java programmers/system designers seem to be the only programmers in the world who do not take advantage of this model. Maybe because with java, no one ever wants to leave the JVM, doing a fork from java is considered a horrible mistake (and will take many servers down)? This NIH java disease is the reason that many java apps have horrible memory problems (a program already exists to do that, well, it's not in java... rewrite) Without using pipes and forking, it is hard to create large robust modular programs in any language. Only java programmers would even dream of it.

So, it is not java so much that is the problem, but the mindset when using it: I cannot fork, that would not be portable...(and uncool?) Not to mention the slow JVM startup times.

The Managed Runtime Initiative

Posted Jun 18, 2010 10:05 UTC (Fri) by marcH (subscriber, #57642) [Link] (1 responses)

> Without using pipes and forking, it is hard to create large robust modular programs in any language.

Agreed.

On the other hand, please tell us how to implement Eclipse or Emacs using a bunch of independent and loosely connected processes.

Even better: please tell us how to implement something as powerful and fast as Linux using a micro-kernel and a bunch of loosely connected daemons :-P

The Managed Runtime Initiative

Posted Jun 18, 2010 15:48 UTC (Fri) by martinfick (subscriber, #4455) [Link]

Eclipse -> KDE (except KDE does so much more in so much less memory, and still, I would not call it efficient)
Emacs -> Vi + 1000 other small unix utilities

Linux, well, we have to reverse things here a bit, linux is somewhat large, but still modularization was defined early by the original unix devs. So the image looks more like this.

multics -> linux + 1000 other small unix utilities.

Remeber how often the "do it in userspace" slogan is shouted from linux kernel devs. Perhaps if the java devs used a bit more of this approach (i.e. do not use the same JVM for everything) they would not be suggesting to expand the kernel just so that JVMs can get bigger! Note how different from normal scalable program requests that is. This is not a request to" "be able to create 1 billion threads/processes and to switch efficiently and fairly among them", or "to communicate between them with low overhead"..., no it is a request to fundamentally support using larger and larger monolithic programs. One might ask why the JVM even needs an OS, why not just run it straight on the iron and optimize the hell out of it, for this single use case, isn't that what the java devs really want? ;)

The Managed Runtime Initiative kernel modifications

Posted Jun 17, 2010 7:04 UTC (Thu) by bgallmeister (guest, #59580) [Link] (4 responses)

I'm one of the team at Azul working on these kernel-side changes. You're right, we haven't talked with many folks about our enhancements yet. While we have had discussions with some in the kernel community, we've been unable to discuss our enhancements in the wider audience until the Managed Runtime Initiative was launched.

We realize the kernel code we've just published as part of MRI is not yet ready for prime time, and will take iterations to wend its way upstream. Right now, the code should be considered a basis for discussion. It'd be good to have the conversation about the types of problems we're solving, and how we might improve our solutions.

Until MRI kernel changes are perceived as solving a general problem in an acceptable, maintainable way, they're not going to be accepted by the Linux community. That's fine, and it's why we published the code this week--so we could start talking about it.

And, yeah, we know that facilities like pluggable memory managers and schedulers are...uh...contentious. We thought this packaging was a bit more comprehensible than inline changes to all of the mm and sched code.

The Managed Runtime Initiative kernel modifications

Posted Jun 17, 2010 10:05 UTC (Thu) by cesarb (subscriber, #6266) [Link] (3 responses)

Let me see if I understood. You are saying "pluggable memory managers and schedulers" are not how it should be, but only a way of separating the code so it is easier to discuss? That is, the way you would really want it done is actually changing the core mm and sched code directly, instead of changing it to create a pluggable interface and then plugging the things you want done over it?

I think everyone is going to discuss the "pluggable" part and ignore the rest of the code.

The Managed Runtime Initiative kernel modifications

Posted Jun 17, 2010 14:44 UTC (Thu) by giltene (guest, #67734) [Link] (2 responses)

The purpose of releasing the code, and of the initiative as a whole, is to demonstrate the value of new functionality [as it pertains to improving runtime execution] and to advocate for the inclusion of such functionality in upstream projects and products. We think that "solving" garbage collection [across the 1GB-640GB range] is a pretty good demonstration, and will be interesting enough to consider the inclusion of the new functionality and interfaces that make it possible.

We fully expect that the code itself will morph 17 ways before it is accepted upstream. It's layout will change. It's APIs will change, and the functionality it provides will change, as people comment/argue about other generic uses of the same capabilities and how to best integrate the new functionality and interfaces with the existing ones [e.g. should/could everything be done under madvise? Should mmap be extended with new options?].

Whether pluggable memory modules are good/bad will be a separate [sub]discussion - and we're not that attached to either form. It's a good development vehicle for now, and makes it convenient to focus most of the big functionality additions and new interfaces in isolated modules while their details are being ironed out and stabilized. Rapid fire changes to system calls is usually a bad thing, and a loadable module with ioctls allows for easier to experimentation and morphing.

The Managed Runtime Initiative kernel modifications

Posted Jun 18, 2010 9:09 UTC (Fri) by cmot (guest, #53097) [Link] (1 responses)

I have the suspicion that a large (and apparently under-documented) code dump like this will never seriously be looked at in depth.

The way to get code in the kernel has always been small, incremental steps (or subsystems that are well isolated and speak to the kernel using established APIs, like new filesystems/drivers/... - but memory management and CPU scheduling code is probably not in this category...)

The Managed Runtime Initiative kernel modifications

Posted Jun 18, 2010 9:59 UTC (Fri) by marcH (subscriber, #57642) [Link]

> I have the suspicion that a large (and apparently under-documented) code dump like this will never seriously be looked at in depth.

All good then, since the post you are replying to explains this was not a goal.

The Managed Runtime Initiative

Posted Jun 17, 2010 16:08 UTC (Thu) by marcH (subscriber, #57642) [Link] (22 responses)

I seriously doubt that the Linux community would even consider any discussion from strangers about such core topics like memory and scheduling unless it is backed by hard facts (and even less if keywords like "java" of "GC" are used)

In such a case the only way to get attention might be to start by publishing (ugly but) running code demonstrating the room for improvement in a non-refutable way.

The Managed Runtime Initiative

Posted Jun 17, 2010 16:38 UTC (Thu) by giltene (guest, #67734) [Link] (21 responses)

Yup. That's exactly what we did. This is working, running code. It exhibits 100x improvements in managed runtime metrics like responsiveness, sustainable memory size, and object allocation rates (which translate linearly to sustainable transaction rates). It [hopefully] proves that this can actually be done, and that it's probably a good idea to do it. How exactly to integrate it upstream will be a long and interesting discussion.

We've brought the beef. Let the chopping begin. And here's hoping that at the end of it, we can remove "java" and "GC" from the bad words category for Linux community.

The beef

Posted Jun 17, 2010 16:49 UTC (Thu) by corbet (editor, #1) [Link] (2 responses)

What you've brought is a dump of code, in an obscure format, in an obscure place. It's a start, but if you are serious about upstreaming this, you need to get onto linux-kernel and start discussing it with people. I would recommend picking one smallish piece to start with, clearly describe your requirements and the reasons why you chose the solution you did. Then be prepared to take a bit of grief; you really should have done this some time ago... Still, if you can show real improvements to real workloads (and it appears you can), you have a basis to start with.

The beef

Posted Jun 18, 2010 10:11 UTC (Fri) by marcH (subscriber, #57642) [Link] (1 responses)

> if you are serious about upstreaming this, you need to get onto linux-kernel and start discussing it with people.

Maybe all you people can stop agreeing so much with each other.

> you really should have done this some time ago...

I still do not understand why. Wakelock trauma? This case looks very different.

The beef

Posted Jun 19, 2010 21:52 UTC (Sat) by error27 (subscriber, #8346) [Link]

wakelocks is just the most recent of a long stream of features which were developed outside the kernel. It's just a painful thing whether it's CML2 or Xen.

The Managed Runtime Initiative

Posted Jun 17, 2010 23:26 UTC (Thu) by ncm (guest, #165) [Link] (17 responses)

"Java" and "GC" are bad words anywhere outside the walled garden. You won't change that by demanding fundamental changes in schedulers and kernel memory management in order to get tolerable performance that normal programs get without.

The Managed Runtime Initiative

Posted Jun 18, 2010 1:27 UTC (Fri) by giltene (guest, #67734) [Link] (16 responses)

It's a pretty big garden [Java, .NET, Python, ruby, etc.], It's more like the wide open space where most of the world actually is, and the walls seem to be around the rest of the [non managed runtime] world these days. Most enterprise scale apps written in the last several years run on managed runtimes. Most modern frameworks and reusable code bases target them, the vast majority of the world's programmers build software for them. Furthermore, apps running on managed runtimes tend to handle stuff with scales and complexities that nothing else tries to. Why? We don't really know. It's just reality.

It does have some pesky issues. Like GC, but those can actually be solved. We've shown that. It's just that [at least the one way we know of for] solving them does require fundamental changes to things like kernel memory management. Some of the core operations we are advocating for make an actual 1,000,000x difference to how critical phases of GC behave, thereby making the difference between a practical, no-more-puases GC world, and the current one. [For some operation metrics numbers, see http://www.managedruntime.org/files/downloads/AzulVmemMet... ]

Does that make such fundamental changes worthwhile? We think so. Some may not.

The Managed Runtime Initiative

Posted Jun 18, 2010 16:19 UTC (Fri) by jzbiciak (guest, #5246) [Link] (2 responses)

As an outsider looking in, these batch virtual memory operations sound interesting in their own right, and not specifically related to Java and GC. It's just that your Java GC can make immediate use of them.

This seems like a similar transformation to providing a vector of IO operations, versus repeated calls to read() or write().

What other workloads might benefit from such batch-oriented VM? Poul-Henning Kamp had an article in ACM Queue recently that showed a 10x speedup on heap structures by avoiding VM hits. While not identical to the problem you're solving, I think it highlights that explicitly optimizing VM behavior, even on "solved problems," is a generally interesting space, with opportunities for huge improvements. After all, heaps are "optimal," right? Then why the 10x speedup? Finding how your work can be leveraged outside your Java GC environment will make it more attractive.

The Managed Runtime Initiative

Posted Jun 19, 2010 5:45 UTC (Sat) by giltene (guest, #67734) [Link] (1 responses)

Good point about relevance outside of GC, Java, and Runtimes. There certainly may be uses in other workloads (in memory DBs? DBs in general? Sparse memory applications that rely on virtual memory tricks?). In general, current virtual memory implementations in almost all OSs assume that virtual memory manipulation is a relatively rare event, and we have put forward an algorithm and an application for rapidly-changing mappings that makes a real difference to a vast array of applications, but it can't do so within the limitations of current virtual memory APIs and manipulation speeds.

We built the enhanced APIs to be generic [we think], without assumptions about the user-level code being a runtime, and focusing on the needed functionality and semantics. Our GC code is all in user space (part of the OpenJDK based code we put up along with the kernel mods) - it just needs some very scalable and somewhat different virtual and physical memory manipulation semantics form the kernel.

So yes, there can certainly be other uses for batched virtual memory operation with extremely fast commit times, and for other features like explicit-TLB-invalidate semantics (allowing user process to determine when a TLB invalidate is required, instead of issuing one per page), scalable virtual memory manipulation (not done under process-global lock), large page support that includes remapping capability, user-controlled shatter/unshatter transitions from large to small mappings while retaining large physical page layouts, etc.

The Managed Runtime Initiative

Posted Jun 21, 2010 20:56 UTC (Mon) by nix (subscriber, #2304) [Link]

A good few of these features seem like things that could be useful for things like user-mode-linux as well (and anything else that has to manipulate a *lot* of mappings).

The Managed Runtime Initiative

Posted Jun 18, 2010 16:28 UTC (Fri) by k8to (guest, #15413) [Link] (12 responses)

While managed runtimes is as you say a large set, I don't hear about these sorts of nasty stalls in eg python, ruby, very much. They definitely come up in java all the time. I would get them when i developed back in 2005 on mono, but assumed that was immaturity (they were using a relatively naive boehm at the time).

I always assumed the pervaisve and unpleasant nature of this problem was simply Sun's inability to make java a real platform for beyond a relatively narrow set of environments. It seemed like the other kids all came up with solutions that worked for them.

The Managed Runtime Initiative

Posted Jun 18, 2010 22:19 UTC (Fri) by foom (subscriber, #14868) [Link]

Python certainly does have GC stalls.

But, python already has such poor performance, and, especially, cannot be running multiple threads at once, that it doesn't come up that much. People just don't use python for the kinds of applications that demand high performance with high allocation rates on 12 threads at once...

The Managed Runtime Initiative

Posted Jun 19, 2010 8:46 UTC (Sat) by vachi (guest, #67512) [Link] (10 responses)

I guess JVM is one of the most used VM in large and complex enterpise app. That's why most complaints are heard from that direction. By the way, I don't hear about complaints regarding scheduler performance of DOS nowadays. DOS must have a pretty good scheduler compared to Linux.

The Managed Runtime Initiative

Posted Jun 19, 2010 19:19 UTC (Sat) by k8to (guest, #15413) [Link] (9 responses)

Nah, the behavior is quite different. Sun JVM seems very good at keeping a large number of objects in memory and stalling reclaiming their space until it can do a large number at once, causing stalls, and wasting memory. Other sytems, like Python, seem to reclaim the objects much more incrementally which might not be as effecient in a long term view.

Meanwhile, we can deconstruct your analogy by pointing out that DOS does not have a scheduler.

The Managed Runtime Initiative

Posted Jun 19, 2010 19:51 UTC (Sat) by foom (subscriber, #14868) [Link] (5 responses)

The Sun JVM has many different GC options. If you want lower throughput, but smaller pauses, you can use the collector designed for doing just that: the concurrent collector.

Use option -XX:+UseConcMarkSweepGC.

For more information, see this article:
http://java.sun.com/javase/technologies/hotspot/gc/gc_tun...

The Managed Runtime Initiative

Posted Jun 19, 2010 23:37 UTC (Sat) by giltene (guest, #67734) [Link] (4 responses)

All current commercial forms of GCs on large scale runtimes include code that compacts the object heap in a stop-the-world operation. Compaction is unavoidable in long lived applications that use variable sized objects (e.g. XML data). Most GC setups can be tuned in various ways to delay this inevitable compaction, but none can avoid it. Think of it as a ticking time bomb - do enough work, and you'll need to defragment the heap because your new object can't fit in any of the empty spaces you've been tracking.

The duration of the stop-the-world pause in all current JVM GC's is generally linear to the amount of live data the heap contains (you have to scan all that stuff and fix all the pointers to the relocated objects). This means that the larger the heap - the larger the pause. Sun's CMS (the Mostly Concurrent Mark Sweep -XX:+UseConcMarkSweepGC mentioned above) will delay the compaction as long as it can and track empty spaces in free lists, but it will eventually fall back on it's compaction code and pause for about 2-4 seconds per live gigabyte on a modern x86-64 machine. This is why JVMs are generally not used with more than a few GB of data, except for batch apps (ones that can accept a 10s of seconds of complete pause). Since a 256GB server now costs less than $18K, there is a ~100x and growing gap between commodity server capacity and the ability for individual runtime to scale with acceptable response times.

The Pauseless GC algorithm and implementation put forward as part of the Managed Runtime Initiative changes all this. It compacts the heap and fixes up pointers concurrently, without having to stop the world to do so. As a result, response time is completely decoupled from memory size, and indirectly from allocation rate and throughput, breaking the 100x logjam.

The Managed Runtime Initiative

Posted Jun 20, 2010 17:19 UTC (Sun) by rilder (guest, #59804) [Link] (1 responses)

Looks interesting. However recently I read about commits related to memory compaction and transparent huge pages. These you may find useful in your work.
Also in your current implementations. are VMs treated differently wrt memory management. There also have been commits wrt VMs for memory ballooing etc.

The Managed Runtime Initiative

Posted Jun 21, 2010 4:06 UTC (Mon) by giltene (guest, #67734) [Link]

Both transparent huge page support and compaction (which transparent huge pages cannot reliably be done without) are good things. We may be able to merge some of our functionality with those over time. We are certainly large consumers of 2MB pages, so we see compaction as very important, and with it we may be able to provide transparent, reliable dynamic allocation of 2MB pages in our subsystem. Without compaction, pages must be explicitly funded and taken away from the kernel upfront, since fragmentation may make it impossible to get hold of them later.

Due to various needs though, our current implementation a separate physical memory management subsystem. The main, overriding need for this is the avoidance of unnecessary TLB invalidates when physical pages are unmapped and mapped [a bit later] within the same process - this is the most frequent pattern across the pauseless collector and the application mutators, and addressing it pretty much requires process-local free lists, which we use.

WRT VMs (e.g.. running this kernel as a guest on top of KVM or VMWare), we see those as common targets. Because the rate of virtual memory mapping changes in our system is quite substantial (well over 1000x compared to the typical OS and application loads), we care a lot about the cost of those manipulations in virtualized environments. Luckily EPT (Intel) and NPT/RVI (AMD) features in all modern x86-64 machines practically eliminate this cost, taking the hypervisor out of the business of intercepting, tracking, and applying guest-virtiual to guest-physical mappings. Without those HW assisted features, applying changes at the rate we do would certainly "hurt" on virtualized systems.

We'll also be able to play with memory ballooning, and we've got some very good uses for it, but the current implementation we've posted doesn't. When we do, we'll be looking to deflate balloons at sustained rates of several GBs per second, which will probably put some serious stress on current host implementations. This is one of the items at the hypervisor level that we're going to be playing with as part of the Managed Runtime Initiative [large page and high sustained rate ballooning]. At first glance, KVM's handling of ballooning seems like it can easily be extended to accommodate what we'll need.

The Managed Runtime Initiative

Posted Jun 23, 2010 17:06 UTC (Wed) by jonabbey (guest, #2736) [Link] (1 responses)

Have you characterized the performance of Sun's G1 collector that they will be using in Java 7?

The Managed Runtime Initiative

Posted Jun 27, 2010 0:00 UTC (Sun) by giltene (guest, #67734) [Link]

We're obviously been following G1's progress and the algorithm it uses. Its' hard to "characterize the actual performance" of G1 right now given it's current experimental state [simple experiments right now show longer pauses than HotSpot's production CMS collector]. However, analyzing G1's basic mechanisms is pretty straight forward. Here is how they can be classified:

1) A concurrent, multi-pass OldGen marker
2) An incremental, stop-the-world OldGen compactor
3) A stop-the-world NewGen copying collector

It's the stop-the-world nature of (2) and (3) above that determine pause behavior for large heap and high throughput applications. When object copying and/or compaction are done in a stop the world operation, moving even a single object in memory requires that *all* references to that object in the heap be tracked down and corrected before the program is allowed to continue execution. This takes an amount of time bound only by the size of the heap (i.e. it takes a multi-seconds-per-live-GB pause to find all those references). While a lot of cool code and tuning goes into making such long pauses spaced out in time, all stop-the-world-compaction collectors (including G1) will periodically fall back on their full stop the world compaction code when dealing with complex heaps. [The collector's elaborate code for doing that operation is there for a reason]. For applications that cannot accept the "occasional 50 seconds pause" during normal operation, this means heap size is still limited by pause time.

In contrast, The GPGC algorithm used in both Azul's Zing VM and in the Managed Runtime Initiative contribution (and in the default, production collector for Azul Vega systems since 2005), can be classified as:
1) A concurrent, guaranteed-single-pass OldGen marker
2) A concurrent OldGen compactor
3) A concurrent, guaranteed-single-pass NewGen marker
4) A concurrent NewGen compactor

Concurrent [as opposed to incremental stop-the-world] compaction is the key here. It completely decouples application pause behavior from heap size and allocation rates, and allows us to deal with the amounts of memory prevalent in todays servers without those nasty many-seconds pauses. GPGC simply doesn't have any form of stop-the-world compaction code in it [as a fall back or otherwise]. It doesn't need it. In GPGC, objects are relocated without having to stop the application while all references to them are tracked down and fixed. Instead, ref remapping is a concurrent operation supported by self-healing read barriers.

It's the software pipeline used to support this concurrent compaction (and guaranteed-single-pass marking) that needs the new virtual memory operations we've put forward.

The Managed Runtime Initiative

Posted Sep 6, 2010 22:20 UTC (Mon) by Blaisorblade (guest, #25465) [Link] (2 responses)

Nah, the behavior is quite different. Sun JVM seems very good at keeping a large number of objects in memory and stalling reclaiming their space until it can do a large number at once, causing stalls, and wasting memory. Other sytems, like Python, seem to reclaim the objects much more incrementally which might not be as effecient in a long term view.

As just said elsewhere by Nix, since Python uses standard reference counting, it is not efficient even in the short term view, because copying a pointer to the stack causes a heap mutation, even to pass a parameter to a procedure. That's why trying to support multithreading gave a 2x slowdown. Given that other portions of code have been optimized, I believe the slowdown nowadays would be bigger. And the slowdown you get with Java and a smaller heap is probably still not comparable to the one you get in Python (no less than 10x).

Python apps seems to have decent performance when they do little, and the rest is written in C, but as soon you try to actually do something with Python code, you lose. I don't get how the same community, which prefers C to Java for performance reasons, can even mention Python. I hope it's not the same people at least.

There are many realtime GCs, and each of them is better than Python's one. In particular, Cliff Click described the pauseless GC, with its amazing performance and small overhead, somewhere on this blog, which I recommend for those interested in the field (even if quite technical). However, he describes their special CPU, but it seems they could port it to x86, and the code is in this release.

For Python, refcounting was just a bad choice in the beginning, and it's now impossible to get rid of it without rewriting everything - and they don't have the man power nor the will. And all of this was well-known, people implementing Lisp, Smalltalk, Self, knew it for the last 20 years, together with a number of other techniques.

The Managed Runtime Initiative

Posted Sep 6, 2010 23:13 UTC (Mon) by nix (subscriber, #2304) [Link] (1 responses)

since Python uses standard reference counting, it is not efficient even in the short term view, because copying a pointer to the stack causes a heap mutation, even to pass a parameter to a procedure. That's why trying to support multithreading gave a 2x slowdown.

Oh no, there are much more appalling reasons why Python's multithreading is awful. The GIL acquisition macros were never designed with multiple CPUs in mind: on a one-thread-of-execution machine (what we used to call 'one CPU'), it all works fine, but if there's more than one, they race with each other and often end up bouncing ownership back and forth and both blocked for astounding periods of time. There's an awesome presentation on the subject, strongly recommended.

The Managed Runtime Initiative

Posted Sep 10, 2010 21:07 UTC (Fri) by Blaisorblade (guest, #25465) [Link]

Ah, that's right, I even knew of that presentation (and watched it again). I kind-of guessed that people were working on that (without any evidence other than "somebody noticed"), and I had no idea about how to fix that.

Moreover, there was work (from Antoine Pitrou IIRC) to change the policies of the GIL - it was/is released/reacquired every 100 opcodes (which might be ridiculously small or too large, depending on the opcodes), while A. Pitrou wanted to have some saner scheduling.

Releasing it every timeslice (i.e. ~80/100 ms IIRC) would probably help with the problems of that presentation - I should have another look to know if this makes sense. A simple user-level scheduler for GIL acquisition would maybe be needed in the worst case, but hopefully not.

The Managed Runtime Initiative

Posted Jun 17, 2010 16:39 UTC (Thu) by linusw (subscriber, #40300) [Link]

The talk about the patches providing "a cpu resource guarantee (...) that any process with 'committed' cpus and runnable threads available for those cpus will have its threads running on those cpus within 10ms." sounds like a clever way to reinvent cpusets + the new SCHED_DEADLINE scheduling class.

Why real Unix developers should avoid C, by Eric S. Raymond

Posted Sep 6, 2010 22:57 UTC (Mon) by Blaisorblade (guest, #25465) [Link]

To all those complaining against Java supposed slowness, have a look at a couple of sections of "The Art of Unix Programming" by Eric S. Raymond, and at the amount of Unix applications not written in C:

Why not C? - (http://catb.org/esr/writings/taoup/html/why_not_c.html)
Language Evaluations (http://catb.org/esr/writings/taoup/html/ch14s04.html)

Moreover, think to the amount of security bugs due to C string and memory management. It is true that even C++ gets it more correct, and that IMHO NULL-termined strings were a bad idea even for C (say, because of strlen being O(n)); but many problems are due to C itself (dangling pointers, anyone?).

Writing a project in C, in most cases, is premature optimization, the root of all evil.

The only problem is that Java's tuning has given horrible startup performance, and that it's not tuned to perform well on small apps.

But nowadays even Eclipse and NetBeans can run in amounts of memory comparable to web browsers, and more reliably - I know of no web browser without massive memory leaks, even though I admittedly open many tabs - but that's no reason for leaking 5 times the memory you need. Might work on a OS which crashes before the few days you need to get that much leaked, not on Linux (and for what I hear, not even on most recent Windows systems).