Hi,

Wilco (Wilco.Dijkstra.delete@this.ntlworld.com) on November 21, 2012 7:44 am wrote:
> EduardoS (no.delete@this.spam.com) on November 19, 2012 11:41 am wrote:
> > Wilco (Wilco.Dijkstra.delete@this.ntlworld.com) on November 19, 2012 9:31 am wrote:
> > > Cache locality is certainly important, but GC doesn't solve that - in reality it actually makes it worse.
> >
> > Well... Cache locality improvements with GC is measurable... No need to discuss.
>
> Rubbish. GC is memory inefficient by definition, so claiming it is better for locality is just wishful
> thinking. Compacting GC's typically need 2-3 times more memory than a non-compacting GC, so are worse on
> average. Also the much higher memory allocation rate and resulting collections are bad for locality.

As for locality advantages, there is lot of research in that area refuting your claims:

Creating and preserving locality of java applications at allocation and garbage collection times
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.7067

Profile-guided proactive garbage collection for locality optimization
http://research.microsoft.com/en-us/um/people/trishulc/papers/halo.pdf

The garbage collection advantage: improving program locality
http://users.cecs.anu.edu.au/~steveb/downloads/pdf/oor-oopsla-2004.pdf

and many more which you can find either by using a dedicated portal (acm.org) or simply a search engine of your preference. Possible locality advantages due to the capability of moving around objects at will are straightforward to think of too.

"GC is by definition inefficient": you are right that GC by definition imposes some overhead, but you always have to weigh it against other factors like ease of programming and that it enables other optimizations like the above which may outweigh the disadvantages.

Compacting GCs are always more memory efficient than non-compacting GCs because in the worst case they can compact the heap perfectly at any time while non-compacting obviously cannot and suffer (sometimes a lot) from fragmentation - just like allocation in a non-gc'ed language. Compacting GC in the worst case need to do that at a ridiculous cost in performance of course.

The 2-3 times number you mention I only know as general guideline for sizing the available heap in a GC'ed VM, i.e. the overhead of gc starts getting negligible when you size the heap to 2-3 times the maximum amount of used memory.
This also depends a lot on your application, the language and the VM and the configuration used.

I do not think this figure is too far off from what you need for a non-trivial non-gc'ed program.

Allocation rates are not so much dependent on the JIT or VM but mostly influenced by the programming language (and the program itself): since eg. Java only knows heap allocated objects (which can be elided using program analysis to a certain degree). If it were possible to e.g. allocate on stack as it is with C++, a well written program would likely have a similar allocation rate.

I'm not talking about custom memory managers tailored for your application here - they are always better than any generic allocator if written reasonably, but really, allocation itself is not the problem for gc'ed languages you single them out.

> > > And that is before we consider the actual overhead of the
> > > collection itself, often having to stop all threads
> > > for long periods.
> >
> > No,
> >
> > 1) A background GC can run on another thread, specially usefull on not threaded software;
>
> Concurrent GC has even larger overheads. It stops threads for shorter periods but stops them more often, so
> takes far longer overall.

That I agree with, however as the original text said, in case of single threaded programs the GC can be done using extra resources. Of course, you also use more resources, but the net effect is that the program runs faster.

> And then we haven't considered the far higher overheads on the generated code.
>

You mean e.g. write barrier code? The overhead for them in the best case is negligible (depending on the type, e.g. "Barriers reconsidered, friendlier still" users.cecs.anu.edu.au/~steveb/downloads/pdf/barrier-ismm-2012.pdf; it presents lots of numbers), and a lot of work has been going into trying to avoid their generation as much as possible.

> > 2) A full stop still the less resource hungry GC, but don't look at it without
> > considering that, thanks to this GC allocations and deallocations are much faster
> > and heap is compacted periodically, in the end, often it is a win.
> >
> > > Then there is the optimization overhead and extra tables causing code bloat.

Not sure what you're mentioning here: gc implementers are quite aware of any extra overhead due to the gc helper data structures, both in extra memory and cacheability. This memory overhead typically ranges in the low single digit percent of total memory, and given enough memory the total performance overhead is not that much more either.

Depending on the GC they may have different (unacceptable to you) timing characteristics though.

> >
> > And C++ allocators waste space to avoid memory fragmentation... But doing so also hits locality.
>
> No, no space is wasted, unlike GC which requires descriptors for every object.

I do not understand what you mean with "descriptors"; the per-object overhead typically consists of a single word used for internal purposes, and another one that contains a reference to the class metadata (i.e. vtable).

The latter is similar to what any other OO language has, and the former is comparable to extra per-memory block information of your allocator. Typically normal allocators actually use a few words per block to store internal data, e.g. block length (at minimum), other data and various markers to detect invalid memory accesses. And certainly they do suffer from fragmentation.
Feel free to direct me to some information that shows the contrary.

I do not think a GC'ed system is at a disadvantage here; in the worst case you could use the same mechanism.

> > > array bounds checks,
> >
> > I was thinking about this one when you mentioned "other features", sometimes the
> > compiler is able to optimize it away and when not, last part of the post.
> >
> > > null pointer checks, assuming
> > > any pointer access may cause an exception,
> >
> > In x86 .Net this check is "cmp eax, [eax]" with the pointer in eax, on field access there
> > is no check at all since it will raise an exception anyway in the case of a null pointer.
> >
> > Since null pointer checks are so cheap it is not clear wich optimizations are disabled
> > by them, just put the check where it is needed to keep the correct order.
>
> Since when is a memory access cheap? Every unnecesary instruction has a cost.
>
> > > multithreading support etc etc.
> >
> > How exactly this lowers performance?
>
> The barriers and other checks for concurrent GC or multithreaded access
> to fields are not exactly zero-cost and block many optimizations.
>
> > > It is significantly harder to write a good compiler
> > > for them, and even then you can never get close to C++ performance. Many optimizations have to be
> > > disabled or turned extremely conservative as an exception or GC may occur at any time.

I am not sure whether it is significantly harder to write a good compiler for them: I agree that you need to spend more time to get to the same performance, but also because there are more components involved (e.g. VM/memory management).

However, there is already a body of previous work/research in that area that should give good results already, and you can also apply much of the existing research in static compilation optimizations.

Especially the compiler can be made a reasonably well encapsulated component of the whole system, while it's harder for other parts.

> managed languages are usually
> > more strict about ordering, and it is not obvious weak ordering improves performance by that much.
>
> The problem is not just the ordering, but the fact that more operations can cause exceptions. That alone
> creates a lot of overhead as you need to model flows from every possible exception to all possible exception
> handlers. Local variable values need to be preserved for example, severely limiting optimizations.

The exceptions can only occur at well-defined points, and while it may lead to scaling back optimizations, typically they are not. To a very large degree, after an exception many values are not of any interest to the program at all (i.e. unused in the remaining program) and so you need not keep them around or generate code that keeps them around at all.

(When really needed, e.g. when debugging, you typically fall back to an interpreter.)

In the contrary, optimizations are typically extremely aggressive to the point of removing seemingly unused code parts using lots of different types of information, keeping only a check and calls to recompile if even necessary. E.g. in the example of the logging/diagnosing functionality you can decide from the information of available loaded classes that there cannot be multiple different subclasses.

A VM may even change these compilation decisions during runtime, e.g. noticing that a given branch that has been used a lot earlier is not used anymore.

> > And finally, back to array checks, yes, they reduce performance, and yes, it is a different discussion,
> > but frankly, the performance reduction is pretty small and a lot of security bugs would be avoided by
> > array bound checks, it is not something I would left behind even if performance was a big concern.
>
> The performance cost is high if you happen to use arrays a lot. Even if you think it is worth it,
> and ignore the overhead as small enough, many of such costs add up to something quite large.

That may be true, although a lot of effort has been put into hoisting these checks out of critical loops, making them negligible. They still add up, but in total I believe you can get performance that is at least not too far off to a statically compiled program for a JIT'ed one (in general).
Such JIT'ed/VMs often also provide more features than what a statical language (can) provide, e.g. dynamic class loading and more advanced introspection/reflection, so a comparison may not be completely valid.

What is true, is that performance tuning in such a system is much harder, as it now depends on much more factors than in a statically compiled program.

V