Consider the immix GC

[pnloyd]

I came across a GC called immix that is very new and wanted to bring it to the attention of the Crystal community. immix was written by contributors of the scala-native project, which aims to compile Scala to native code via llvm as a backend, like Crystal. Also like Crystal, they originally opted to use the boehm GC during their initial implementation, but made plans to explore other options.

Why should the Crystal community pay attention to this GC? Look at these benchmarks.

It appears as though for smallish heap sizes the immix algorithm comes very close to the performance of not having a GC running at all. Which seems amazing to me (although I don't know much about the subject).

The scala-native devs say immix is ahead of the curve performance wise in comparison to the majority of GC's which are based on research from the 90's and early 2000's (immix was 2008). They still are using boehm by default but plan to switch to immix soon as it gains some maturity.

You can see the source for immix here:
https://github.com/scala-native/scala-native/tree/master/nativelib/src/main/resources/gc/immix

And in these two files you can see that they define an identical interface for both boehm and immix, that is not to far off from the APIs Crystal uses from boehm.
https://github.com/scala-native/scala-native/blob/master/nativelib/src/main/resources/gc/immix/ImmixGC.c
https://github.com/scala-native/scala-native/blob/master/nativelib/src/main/resources/gc/boehm/gc.c

Here's the point in the relevant talk where the scala-native dev talks about immix and discuses some it's performance characteristics.
https://youtu.be/JZCeQi_xLok?t=14m1s

[Papierkorb]

1. Can it also be used by C/C++ code? As in, how to integrate it with linked-in libraries?
2. Does it require full type data? The talker says it's precise, so I guess yes.

The nice part about Boehm is that it's C/++ native already, in that it is conservative and can be used by wrapper libraries to integrate existing C/++ libraries into "Crystals GC". This in effect eliminates almost all ownership issues, which is really nice.

Whatever the GC does, it should support something (A special API is fine too) that can do this.

[ysbaddaden]

Looks nice, but it's bundled with the scala-native project, and will probably be optimized for the needs of Scala. Do they intend to extract it, and make it a language generic implementation?

[pnloyd]

@Papierkorb, my knowledge of compiler design and issues of lowish level compilation issues is shallow. But I know a central goal of the scala-native project is to perform very seamless C interop (probably rivaling or superior to Crystal's)
@ysbaddaden, considering they include the source in there root project I'd doubt it. But the scala license is a simple BSD license. And considering the API's are so similar, It would seem foolish not take the few hours it might take to hack Crystal to use it and see if it doesn't work "plug and play". I honestly looked into trying this myself but not only is my C knowledge shallow but Crystal is not building on Ubuntu 17.10. :(

But for anyone who was willing to try this.. I only briefly looked over Crystal's boehm usage and it looks like some parts (setting "bottom stack pointer" i think, letting boehm proxy pthread calls) are just requirements of boehm that immix doesn't require. Maybe it's possible interfacing with immix is simpler.

My underlying point is that it might be so simple that it could be worth trying before diving into the "is it legal, is it optimized for Crystal", like questions

[pnloyd]

@Papierkorb, also I think intuition would tell you that if (i assume so) scala-native can seamlessly switch between boehm and immix, Crystal would be able to as well.
Edit: further discussion revealed that intuition was wrong.

[pnloyd]

@ysbaddaden, another thing to consider, scala-native is also in a "implementing multi-threaded" phase like Crystal. I suggest that Crystal just explores the viability of immix, and then wait's for the scala-native dev's to actually bring it into a production ready state.

[ysbaddaden]

Few hours will quickly turn into days and weeks.

For example, we need create a stack for each fiber. How can we declare theses stacks to ImmixGC so it can scan them? If we can't (and I didn't find it with a quick search), then allocating memory in spawn will be thought as inaccessible and freed 💥

[pnloyd]

@ysbaddaden, ya I agree that that getting another GC really working could take weeks worth of effort. But you could still try it without green threads. And if you you did, and did confirm that the performance improvements were really what the scala-native bench marks suggests they are, then wouldn't it be worth it to take those weeks worth of effort to get it to work for real?
-- I might be being naive about the amount of effort to get it to work without green threads of course.
Another note, about it being optimized for the needs of Scala. The authors state multiple times that it is basically the exact same algorithm that is described in the research paper it is based off of, which had nothing to do with scala as far as I know.

[bararchy]

Wouldn't that time be better spent making a Crystal native GC so we could have less dependencies and also it would fit our needs 100% ?

[pnloyd]

@bararchy, by native GC do you mean written in Crystal? Crystal uses llvm to compile to actual native code, pure Crystal would be a "pipe dream".
-- I think the primary concern for any project should always be the users of the project, within practical reason.

[bararchy]

@pnloyd all depends on priorities I suppose , do people want multi-threading / windows support , or a "free" 20% speed increase , and "free" because as @ysbaddaden said, it might take a not so low amount of time to add

[Papierkorb]

by native GC do you mean written in Crystal? Crystal uses llvm to compile to actual native code, pure Crystal would be a "pipe dream".

The opposite is in fact true, you can implement a full GC in pure Crystal just fine. No problem apart from writing the (complex) code.

[Papierkorb]

Found the mentioned paper: http://www.cs.utexas.edu/users/speedway/DaCapo/papers/immix-pldi-2008.pdf

Don't have time reading it now though..

[pnloyd]

@Papierkorb, I didn't state you couldn't write a GC in crystal. I was insinuating that having the entire Crystal stack be in purely Crystal is near impossible / impractical. So the fact the immix is written in C shouldn't be of concern, just like the fact the boehm is written in C isn't a concern now, or llvm.

[pnloyd]

@bararchy, even if it wouldn't translate over to windows for what ever reason, the API's are so similar you could easily add some kind of switch between them. Giving up a 50% increase in performance or more on POSIX platforms makes no scene just because you can't have the same on windows.