4 ms·

Cool project. How does it accomplish the realtime GC max pauses of 1-2 ms after compiling to javascript? Wouldn't the js implementation's GC have the final say

• TylerE 13y ago
  I believe the JS target is considered a bit of a demo/toy - e.g. large swathes of the stdlib are unavailable.
• RyanZAG 13y ago
  Just being optimistic, probably. You could write a fairly trivial program that builds and discards massive trees that will force GC to take greater than 1-2ms simply on freeing memory. Maybe they mean in regular operation or something - but then what is regular? I guess they have to claim impossible feats to get interest given just how many languages there are already.
  • pcwalton 13y ago
    It's deferred reference counting, so the 1-2ms claim is perfectly reasonable because all it has to scan is the stack (though if they want to break cycles they will have to do something costlier). The downsides are all of the downsides of reference counting, plus the fact that last I looked Nimrod's GC is not thread safe. That last one is a huge downside IMHO. I think DRC is interesting but I'm not much of a fan of it, honestly: it doesn't solve the big downsides of RC (cycles and thread safety being super expensive) while giving up RC's biggest advantage (prompt reclamation).
    • RyanZAG 13y ago
      Deferred means you eventually have to do the work. Same for reference counting - when you free that last element it will have to actually do the freeing. If you've filled up ram and are allocating objects fast then you can either crash or do some garbage collection and if the tree is large it will have to take more than 1-2ms.
      • pcwalton 13y ago
        Yes, you can always overrun an incremental garbage collector, forcing it to start collecting more often to hit the deadline. Each collection may take only a couple of milliseconds, but there's no garbage collector that can say "no more than 1-2 ms per frame" in the case of a game, for example. If you bound max pause times, you may have to pause more often. There's no free lunch.
      • ryeguy 13y ago
        I think the slides are saying you have the ability to pass that option to the runtime. You can specify an upper bound for gc time, see here: http://nimrod-lang.org/gc.html http://nimrod-lang.org/gc.html
      • rbehrends 13y ago
        Deferred means you eventually have to do the work. Not quite. What you save with deferred reference counting is what is generally the biggest cost of reference counting: assigning references to local variables and having local variables go out of scope. Deferred reference counting only requires an RC update if you store a reference in a heap object or in a global variable. You will, of course, necessarily incur the overhead for allocation and deallocation, which one can make cheaper (bump allocation in generational and copying GC, memory regions) but can't entirely get rid of, especially in non-copying/compacting schemes.
        • pcwalton 13y ago
          But you lose the promptness of deallocation. Furthermore, I think the biggest overhead of reference counting is not the count manipulation (especially if you aren't making it thread safe), it's the inability to handle cycles, which DRC does not address.
          • rbehrends 13y ago
            You are correct that you won't get the immediacy of reference counting; that's a problem of all memory schemes that aren't naive reference counting. But no, the biggest constant time overhead for naive reference counting comes from the RC updates for literally any pointer manipulation. Not just the overhead of having increments, decrements, and possibly failed branch predictions for every single pointer assignment, but also what it does to cache locality. Deferred reference counting essentially only needs a write barrier not very different from generational or incremental forms of garbage collection. This is why tuned versions of deferred reference counting come pretty close to other tuned GC schemes, but naive reference counting falls short, even in the absence of cycles. Cycle detection primarily affects pause time, not overhead.
• lars 13y ago
  I have no idea what Nimrod is doing, but I suppose one could output JS where a heap is simulated through a TypedArray, such that the JS GC only has a single memory reference to keep track of. Then you could give guarantees on GC performance, given reasonable assumptions about the JS runtime.
  • pcwalton 13y ago
    There's no way to scan the stack in that case to find the root set, though, unless you spill all pointers to the typed array at safe points (which costs performance).
• rcthompson 13y ago
  Probably by compiling to JS code that avoids the JS garbage collector, the way asm.js does.