dumael

Hypothetically, (I'm not sure how widespread this technique is), some (Java) compilers turn heap allocations into stack allocations when they can prove that transitively an allocated object does not become reachable from other threads.

This general technique "escape analysis", i.e. "a reference to this object /escapes/ a given reachability type[1]", can be used to transform general heap allocations into thread local or stack allocations.

[1] Let me define reachability type as {can be accessed from anything, can be accessed from this thread only but is of indefinite lifetime, can be accessed from this thread only and it's reference is not take by any object allocated onto my local heap, ...}

Freeing objects in Generational GC requires computing the transitive closure relation of the stack and any "global variable" for the set of objects in the generational allocation arena so that all live objects there can be identified. I. E. For the stack, all "Global" variables, and the set of marked cards/(The record of objects updated with old to new references) : Find all live objects, copy them into the next arena while rewriting references.

Oh, were write barriers that not mentioned? Generation GC requires write barriers. Every update through a pointer unless provably required by a compiler turns "a->b = c"; into "if(b is in generational region) { record update of b;} a->b = c".

If you want to be able to move objects arounds cheaply, writes through pointers transform into small subroutines. For some GCs, reads through pointers are also small subroutines.

And some Generational GCs do card marking over object marking. Let's traverse $CHUNKOFMEMORY on the probabilistic notion that if something was updated, something close by was updated. (Otherwise we can have Sequential Store Buffers which record exactly which objects were changed)

Stack allocation (either explicit or deduced) is probably the fastest method of object allocation there is. Generational GC is on average going to be fast but can suffer horrendous worst case scenarios unless you GC is designed/engineered to switch between thread local allocation arenas.

Full disclosure: Despite my whining about GCs, I did do my Phd in them.

I know MIPS (and possibly other RISC architectures) don't have an implicit 'stack' register, just one that used by convention. They do have jump and link instructions which write $pc+4 into another register.

Afaik, LLVM and quite possibly GCC just add/subtract $esp for the initial allocation / final deallocation of the stack.

More recent intel x86 process I believe have a small separate d-cache for the stack.

That report is quite old though and just compares compilers with the nofib benchmark.

JHC can't compile repa as repa requires multi-parameter type classes which JHC doesn't support unfortunately.

Updating an object in the global heap to point to a thread-local heap can cause unbounded work to be done before that update as the entire pointed-to structure has to be copied into the global heap first. GC designers really hate write barriers (sections of code that are performed before a pointer is updated) that perform unbounded work.

With sufficient effort, you can have the equivalent of no shared mutable data.

What you cannot have is completely separate heaps, so that if one thread crashes for whatever reason it doesn't take your application down.

Also, good luck trying to find a garbage collector that supports completely separate heaps that isn't a direct copy/near-identical implementation of the BEAM[1] VM's GC.

[1] The virtual machine that is the stock VM for Erlang. (In fact I don't know of any others but I have never looked.)

The difficulty with concurrent GC is not to prove an object is unreachable but to prove is likely to be reachable. For instance Yusa-type (or snapshot-at-the-beginning) concurrent collectors have a tendency keep dead objects alive. This 'floating garbage' is a small price to pay for a fairly simple correctness proof of never dropping a reachable object.

It's no harm for a GC to keep some dead objects alive but dropping something reachable is completely unacceptable.

> Of course, this won't work trivially concurrently. Only if you stop the world [..] can collect the original space.

Yes, moving objects concurrently requires some serious thinking to get right. Sun's G1 collector does this by recording the location of pointer updates that point into regions which are to be compacted. This pushes the pause times down to the length of time to move objects and update references to them.

If you're real serious about moving objects concurrently, see "A Study of Concurrent Real-Time Garbage Collectors", Pizlo et al, 2008.

To cope with this the mutator is modified at compile/run time to inform the GC of object updates that could lead to this situation.

During compaction of any sort, the first time an object is encountered that is to be moved it is copied somewhere else and the old copy's header is overwritten with it's forwarding address. Every time the GC encounters a reference to the old object, it re-writes the reference to the old object with it's new location (conveniently located in the old copy's header).

> Is it possible that a reference value is a pointer to a reference "object" which contains the pointer to data, which needs to be updated?

Look up something called 'Brook's style forwarding pointer', it is essentially what you've described.

They're also claiming that the US released a bio-weapon in Germany, so take with a pinch (small asteriod) of salt.

http://www.whatdoesitmean.com/index1494.htm

From reddit: http://www.reddit.com/r/politics/comments/i345g/us_orders_ne...

So yes, slow but otherwise it would be of no use.

load_linked and store_conditional are not much better. Depending on implementation they can spuriously fail because something poked the cache, there was memory traffic etc.

ARM seem to be mostly concentrating on the ThumbEE environment now, which is much better documented.