Hacker News Reader

Comment by austincheney | Hacker News Reader

Pretty ambitious for a simple educational project.

I suspect the hardest part is getting garbage collection correct around lexical scope. The browsers struggled with this for years.

View on HN

> The browsers struggled with this for years.

Arguably, they still do.

    function f() {
      var some = [];
      while(some.length < 1e6) {
        some.push(some.length);
      }
      function g() { some; }
      return function() {};
    }

    var a = [];
    var interval = setInterval(function() {
       var len = a.push(f());
       if(len >= 500) {
         clearInterval(interval);
       }
     }, 10);

uses a very large amount of memory in all browsers.

     function f() {
       var some = [];
        while(some.length < 1e6) {
          some.push(some.length);
        }
         function g() { some; }
     }

     var a = [];
     var interval = setInterval(function() {
       var len = a.push(f());
       if(len >= 500) {
          clearInterval(interval);
       }
     }, 10);

uses very little.

https://stackoverflow.com/questions/19798803/how-javascript-...

https://blog.meteor.com/an-interesting-kind-of-javascript-me...

For the record I'm pretty sure my implementation uses a very large amount of memory in both cases as I'm not doing anything to avoid it (like escape analysis).

> The browsers struggled with this for years.

Multiple browsers had bugs with garbage collection of a basic part of JavaScript for years? What was the problem? I wonder what made them specific to lexical scopes, because a lexical scope is either just more entries on the stack, which is scanned for local variables in the same way, or objects on the heap, which is scanned for fields in the same way.

I've found that remembering to add items to the root set in C (or C++) causes most gc difficulties. In my pet language Ivy, I ended up doing this: new allocations are automatically protected from collection until the interpreter executes the next branch (this limits the work of removing items from the protected list, vs. doing it on every instruction). This limits the number of accidental collection cases you have to think about considerably.

There are still a few cases to worry about. For example, during function activation: if you allocate anything between the time you switched to a new lexical scope, but before saving the old one somewhere in the root set you are in trouble. This is easy to do, because you want to just save it in a local C variable until you have allocated the thing where you are ultimately going to save it.

https://github.com/jhallen/ivy-lang

In general gc bugs (like all allocation related bugs) are a nightmare because the effect is always delayed from the bug.

Yeah, I've had my share of interesting bugs (see the article I linked in another post).

All pointers are tracked automatically (except for specially optimized classes), so that part isn't so bad, but it's still (too) easy to accidentally use a stale pointer value.

At the moment I can safely collect after every statement, but there is still work to be done before I can claim to support collecting after every expression (like I'd ideally be able to - so I can collect when I run out of heap).

My understanding of the things that catch people out are things like:

    function f(){
        let a = {};
        return function(){};
    }

In all (IIRC) major implementations, the object allocated for `a` will be held on to after the function returns because it exists in the lexical scope of the function returned (even though it isn't—and never can be—reached, as static analysis can prove).

Basically all the other bugs I'm aware of are cases of C++ code not treating things as roots when necessary, mostly in DOM code.

V8 does actually check if the outer variables are referenced by the inner function. There's a misconception amongst a disturbing number of programmers that it's impossible to memory leak in a garbage collected language. For some reason I've found this particularly prevalent amongst C# developers, but no language community is immune from it.

In truth there are myriad ways to very casually and accidentally create pools of references that can't be garbage collected. I'll leave finding these as an exercise for the reader to google.

here's an old article by Douglas Crockford about a particular memory leak in IE's garbage collector that persisted for a very long time:

https://crockford.com/javascript/memory/leak.html

Right, that sort of bug in IE is one of the more common types: not properly tracing through C++ objects.

It isn't, per-se, a bug in the JS VM, given the JS VM's GC is merely acting on what the external code tells it (especially given IE used a separate heap for DOM objects).

What if the internal function calls eval?

In the simple case in my parent comment? If it's a direct eval call, then the VM has to assume it'll reference every possible variable, and has to keep them around as a result.

Should this be defined as a bug or simply browsers lacking an optimisation trick? In my view it's the latter. The result is the same, the only difference is it's slightly slower to keep "a" around.

I'm finding it impressive that the compilers even attempt to implement this optimization.

It's not that hard to roughly approximate: does an enclosing scope reference this variable or does an enclosing scope contain a direct eval call? (You also have cases where you don't know for sure, especially in the presence of the with statement, but then you just assume it is referenced.)

If no enclosing scope references or maybe references it, you can treat it differently to those that are referenced. You don't even need to do actual escape analysis to get 99% of the cases.

Garbage collection works by removing variables from memory when all references to a given variable are no longer available. The challenge is that a variable can out live the scope where it is declared.

    //global variable
    let closure;
    { // block
        let x = function a (b) {
            let c = b + 5;
            return function (d) {
                return d + c;
            }
        }
        closure = a(5);
    }

The variable named closure is in the global scope. The functions are long destroyed after the block closes. When does variable c get garbage collected? It is still needed by the global closure variable. All of that mess should be garbage collected when closure is garbage collected, but it can continue to live on as a different variable when used in an object or array.

I can't think of anything related to lexical scopes. But IE was a horror story for a while, because its underlying JS implementation - JScript - was COM-based ("Active Scripting"), and thus used the COM object model. Which is to say, reference counting - and without weak references, at that! It was extremely easy to write code that would create object cycles that would never get disposed in IE.

Actually that part wasn't too bad once the GC was working as I handle activation records more or less like normal ECMAScript objects.

Yesterday I finished an article (https://mras0.github.io/mjs/doc/gc/initial.html) on how I implemented the GC and some of the challenges, if you're curious.

Reply on news.ycombinator.com