1. 29

Immix implementation in Rust that performs just as well as the C implementation, and is still able to take advantage of Rust’s safety guarantees in much of the code despite GCs generally being very low level and chasing random pointers.

Edit: If you’re having trouble with the PDF from the main link, this one might treat you better: http://users.cecs.anu.edu.au/%7Esteveb/downloads/pdf/rust-ismm-2016.pdf

  1.  

  2. 7

    This is quite interesting, and impressive. Rust continues to surprise me, and I wish I had more opportunity at the moment to dig deeper into using it.

    For this particular idea, I wonder how likely it is to be adopted though. There’s a few reasons why you might require a GC, I suppose:

    a) you’re implementing a scripting language b) you can trade off a little latency now and then for convenience, and still be responsive.

    As one shouldn’t really need a GC implementation for an application written in Rust, since it provides it’s own automatic memory management, that leaves C and C++ applications / systems code. But, does one really want to have this additional, rather large dependency, a rust compiler, to do a clean build from initial checkout of the app? Obviously, one could vendor object files or something, but eventually someone needs everything.

    All that being said, it might simply be worth it, for the simple reason that the Rust implementation creates more safety, via it’s semantic guarantees.

    1. 7

      To tag onto what @burntsushi says, there’s a few ways this plays out:

      1. An optional Gc<T> type in Rust itself. Just like how C programs can use the Boehm GC if they want to.
      2. A significant use-case of Rust is embedding in other languages and environments. Those may have GC. It’d be good if Rust were able to talk to their GC about objects owed by that environment. Consider Servo, which manipulates JavaScript objects that are owned by Spidermonkey.
      3. You’re writing a programming language, and you need to implement a GC for it.

      But, does one really want to have this additional, rather large dependency, a rust compiler, to do a clean build from initial checkout of the app?

      Firefox is, at least. :smile: But you’re also right that not everyone would need to build that component from source, and projects could offer pre-compiled versions as well.

      1. 1

        An optional Gc<T> type in Rust itself. Just like how C programs can use the Boehm GC if they want to.

        In what way would a Gc<T> be beneficial for a typical Rust program? Are there applications where regions based allocation is significantly disadvantaged, and GC latency would be a desirable tradeoff?

        A significant use-case of Rust is embedding in other languages and environments. Those may have GC. It’d be good if Rust were able to talk to their GC about objects owed by that environment. Consider Servo, which manipulates JavaScript objects that are owned by Spidermonkey.

        Maybe I misread the paper, but my understanding of the contribution and claim was that Rust had advantages for writing GCs for use outside of Rust. Section 2 explicitly calls out that there is prior work to create a GC in Rust for Rust, for instance.

        But, anyway. I’m not sure I follow point 2. How would my new GC implementation in Rust help me manipulate JavaScripts objects that are owned by SpiderMonkey, which doesn’t use my GC implementation?

        Firefox is, at least. :smile: But you’re also right that not everyone would need to build that component from source, and projects could offer pre-compiled versions as well.

        Firefox is big and complicated, so I’d expect to have to jump through a Rust hoop to get it to compile. :)

        1. 3

          In what way would a Gc<T> be beneficial for a typical Rust program?

          A typical Rust program? Probably not much. But a systems language is all about flexibility; there are some situations in which a GC does make sense. @lmm gets at this below, but things like persistent or lock-free data structures are really hard without GC. http://aturon.github.io/blog/2015/08/27/epoch/ is an example of exploring this in Rust, and one way of looking at it is that what’s been done is just another form of GC.

          Maybe I misread the paper

          I wasn’t trying to say something about this paper, I was trying to say that this is an area where GC and Rust may intersect.

          How would my new GC implementation in Rust

          It’s not the GC itself, it’s getting the Rust language and typesystem to be able to natively understand the idea of a GC’d type. This would make implementing those types easier and more efficient.

          1. 2

            That all makes sense. Thanks for clarifying!

          2. 3

            In what way would a Gc<T> be beneficial for a typical Rust program? Are there applications where regions based allocation is significantly disadvantaged, and GC latency would be a desirable tradeoff?

            The example I keep hearing is if you have a graph that you’re passing around and heavily mutating, and want to deallocate nodes when they’re no longer connected without having to keep track of it explicitly.

            1. 1

              Maybe it changes what a typical rust program looks like.

              I want an impure, ML influenced language with generics and traits and strictness and easy access to for loops and mutable variables.

              I also don’t particularly want to avoid GC.

          3. 5

            I’ve spoken to Tony and Michael, two of the authors about this, and this is part of a larger project implementing a low level virtual machine which can be targeted by language designers, very much like LLVM, but providing for example pluggable garbage collectors and an actual virtual machine but with the option for AOT our JIT compilation. Their initial target language is python with hopefully Haskell as their second.

            1. 1

              Kind of like the Draining the Swamp paper or old HLVM project?

            2. 2

              I’m not particularly knowledgeable in this area, but AFAIK, there are people interested in having a GC for Rust, but not built into Rust. Back in the Long Ago, Rust actually had a (very primitive) GC type built into the language, which I believe used the @ sigil. Sorry that I can’t say more about the specific trade offs involved here though (although I could certainly guess).

              1. 1

                The simplest solution, used in high assurance, is doing it twice in two languages in as equivalent form as possible. One language makes verification of correctness easy while other meets deployment constraints. Oldest combo was Gypsy with Ada or Pascal. Most recent on high-end was Haskell, HOL, and C with seL4. Relevant, medium example would be doing component like GC in SPARK and/or Rust while distributing semantically-equivalent C program. Can run it through provers, static/dynamic analysis, and equivalence tests to be reasonably sure they’re close enough.

                So, using this ancient strategy, one get get some benefits of one language like proven absence of specific implementation or interface errors with ability to deploy final result without people knowing original language or having huge-ass dependency. Managing those become just your troubles alone. :)

                Note: The same effect also happens about anytime someone implements a BetterLanguage-To-LocalLanguage compiler like, say, Taft’s Ada-to-C compiler. ;)