4 ms·

I am very sceptical about an approach that concentrates on code generation and punts GC to later. My experience is that you can always improve the code generat

I am very sceptical about an approach that concentrates on code generation and punts GC to later. My experience is that you can always improve the code generation later, but the early decisions you make about GC will be with your forever. Things like data representation, whether objects can move, the interface to native code, the concurrency model etc. are very dependent on the GC and once you have built a big system that doesn't have a moving, precise GC you have probably boxed yourself in in terms of making a good design for your memory management later.

wbhart 15y ago
LLVM has almost no support for GC and it is about the biggest problem that just hits you in the face when you use it. What I've been doing for my own experiments is very naive (and quite possibly broken). I've been implementing an interpreter with all GC done on the "compile side" of the Jit. What this means is that to allocate at runtime it reaches back around and calls functions which are pre-compiled into the interpreter codebase. The interpreter itself uses linked lists extensively for its symbol table and to hold references to memory that it needs at compile time, and this is just hooked into by Jit compiled code at runtime, i.e. there's automatically an object associated with each allocation done at runtime because there is an object associated with it at compile time which is stored in the symbol table. Once a given object is out of scope, assuming no other object (which is still in the symbol table) holds a reference to it, the GC can then see the object can be cleaned up. [And just writing this I know this sounds very much like nonsense. After all, once something is out of scope at compile time, what is to stop the GC cleaning it up before runtime? Indeed one has to be careful about this. In my case, the source code itself is connected with the symbol table. The source code is itself represented as a linked list and the symbols in it are the symbols in the symbol table. Until the source is relinquished, the part of the symbol table that is currently in scope is not relinquished. And of course the source is not relinquished until after it has been "evaluated", i.e. Jit compiled and executed.] So far I haven't managed to trick it, and it is very efficient. But then again I'm using Boehm-Demers-Weiser which is possibly so conservative that nothing is actually getting cleaned up in the examples I am running. I simply don't know. I do know that this is a technical kludge and (I think) I can see it isn't going to work for a compiler, only for an interpreter.
- aphexairlines 15y ago
  Have you looked at how GHC provides a GC for its LLVM backend?
  - wbhart 15y ago
    No. I did read an article about the GHC LLVM backend and it mentions the Cmm language (a variant of C--). But there was no mention of GC. In fact, this thesis: http://www.cse.unsw.edu.au/~pls/thesis/davidt-thesis.pdf http://www.cse.unsw.edu.au/~pls/thesis/davidt-thesis.pdf seems to state that Cmm implements almost everything but the runtime aspects of C--. In particular GC and exception handling are done more directly by Haskell without the need for direct support in the back end. I do know some hooks were added to LLVM to support Haskell, e.g. the calling conventions used by GHC. If you have any references regarding the GHC garbage collection, I'd be interested in seeing them. Of course I can also dig some up for myself. I assume they do something clever. (Pretty much everything that is clever that is missing from Scala, from a mathematician's point of view, is in Haskell or Lisp I suppose. Shame, because most mathematicians refuse to learn something as mind bending as Haskell.) Edit: OK, now based on what I do know, I'm going to take a guess at this. The GHC GC is written in Haskell? Now that's gonna bake someone's noodle.
    - eru 15y ago
      Lots of Lisps have GCs written in those Lisps, too. But I guess it's harder for Haskell, since you can not just "not cons" and mutate in Haskell.
- grandinj 15y ago
  LLVM in fact already has a VM available. See http://vmkit.llvm.org/ http://vmkit.llvm.org/ I don't know why the scala-over-llvm authors didn't simply build on that, it would have been way easier.

wbhart 15y ago

LLVM has almost no support for GC and it is about the biggest problem that just hits you in the face when you use it. What I've been doing for my own experiments is very naive (and quite possibly broken). I've been implementing an interpreter with all GC done on the "compile side" of the Jit. What this means is that to allocate at runtime it reaches back around and calls functions which are pre-compiled into the interpreter codebase. The interpreter itself uses linked lists extensively for its symbol table and to hold references to memory that it needs at compile time, and this is just hooked into by Jit compiled code at runtime, i.e. there's automatically an object associated with each allocation done at runtime because there is an object associated with it at compile time which is stored in the symbol table. Once a given object is out of scope, assuming no other object (which is still in the symbol table) holds a reference to it, the GC can then see the object can be cleaned up. [And just writing this I know this sounds very much like nonsense. After all, once something is out of scope at compile time, what is to stop the GC cleaning it up before runtime? Indeed one has to be careful about this. In my case, the source code itself is connected with the symbol table. The source code is itself represented as a linked list and the symbols in it are the symbols in the symbol table. Until the source is relinquished, the part of the symbol table that is currently in scope is not relinquished. And of course the source is not relinquished until after it has been "evaluated", i.e. Jit compiled and executed.] So far I haven't managed to trick it, and it is very efficient. But then again I'm using Boehm-Demers-Weiser which is possibly so conservative that nothing is actually getting cleaned up in the examples I am running. I simply don't know. I do know that this is a technical kludge and (I think) I can see it isn't going to work for a compiler, only for an interpreter.

aphexairlines 15y ago
Have you looked at how GHC provides a GC for its LLVM backend?
- wbhart 15y ago
  No. I did read an article about the GHC LLVM backend and it mentions the Cmm language (a variant of C--). But there was no mention of GC. In fact, this thesis: http://www.cse.unsw.edu.au/~pls/thesis/davidt-thesis.pdf http://www.cse.unsw.edu.au/~pls/thesis/davidt-thesis.pdf seems to state that Cmm implements almost everything but the runtime aspects of C--. In particular GC and exception handling are done more directly by Haskell without the need for direct support in the back end. I do know some hooks were added to LLVM to support Haskell, e.g. the calling conventions used by GHC. If you have any references regarding the GHC garbage collection, I'd be interested in seeing them. Of course I can also dig some up for myself. I assume they do something clever. (Pretty much everything that is clever that is missing from Scala, from a mathematician's point of view, is in Haskell or Lisp I suppose. Shame, because most mathematicians refuse to learn something as mind bending as Haskell.) Edit: OK, now based on what I do know, I'm going to take a guess at this. The GHC GC is written in Haskell? Now that's gonna bake someone's noodle.
  - eru 15y ago
    Lots of Lisps have GCs written in those Lisps, too. But I guess it's harder for Haskell, since you can not just "not cons" and mutate in Haskell.
grandinj 15y ago
LLVM in fact already has a VM available. See http://vmkit.llvm.org/ http://vmkit.llvm.org/ I don't know why the scala-over-llvm authors didn't simply build on that, it would have been way easier.