Reusing mpl's RTS

[GunpowderGuy]

Hello, I am working on the GRIN project, another whole-program optimizing functional compiler: https://github.com/grin-compiler.

It currently has no RTS, so I’m considering the possibility of reusing MPL's or MLton's by compiling to one of their low-level IRs like SSA, SSA2, or RSSA. This would allow GRIN to target both LLVM and C code.

Does this documentation still hold true for MPL?

http://mlton.org/IntermediateLanguage
http://www.mlton.org/CompilerOverview

It gives me the impression RSSA is the best target since it starts before GC and other RTS features get added, but has explicit data representations instead of datatype declarations (GRIN is untyped, so it starts with neither but gets annotated with data representations via static analysis for optimizations and codegen).

[shwestrick]

Yes, the documentation for MLton is still largely accurate for MPL. There are a few small differences here and there (e.g. we've added additional prims), but nothing major.

I agree, RSSA could be a reasonable target if you already know what your data layouts will be. Perhaps SSA2 could also work, although it's hard to say without knowing more specifics about GRIN.

I will caution that, to the best of my knowledge, these IRs have never been used as separate targets and were never designed for this purpose. So, I can't say for sure how difficult it would be to target RSSA or similar from a different compiler front-end.

Does GRIN have parallelism? If not, then you could try shooting for MLton's backend.

If you're interested in taking advantage of parallelism by reusing the MPL runtime system, I'm not sure how easy this would be. At the very least, you would somehow need to recreate the MPL scheduler in GRIN. This code implements MPL's fork-join primitives, but it is a highly privileged piece of code, with many direct calls out to the runtime system to manipulate the GC and other details. The MPL GC and scheduler cooperate closely; they are essentially one combined system. Another pretty big hurdle is laziness---I see that GRIN focuses on lazy evaluation, which is likely not to perform well with MPL's runtime system. I'm happy to discuss if you're curious.

[GunpowderGuy]

@shwestrick Thanks for the quick response

Grin isnt a language. It is a compiller backend for functional languages in general. I plan to create an mvp by polishing it and the idris2 to GRIN compiler, then add a drag and drop GC like bohem. After that is done i want to integrate a better rts like mpl's

Grin doesnt currently support parallelism, but we hope to add it in the future. Since the compiler detects which functions are pure and which ones transitively produce side effects, optimizations could automatically add parallelism instead of relying on user annotations, even without taking into account idris2 is a pure language.
Given that, do you still think we have to re write that piece of code you linked?
Would there be any disavantage to using mpl instead of mlton even if we dont plan to use parallelism?

Grin optimizes away much of laziness and it never railroads into laziness languages not based around it like idris2 or scheme ( if we write such a GRIN front end ) but i am not 100% sure it would make an eventual haskell front end play ball with mpl's rts.

[shwestrick]

Yes, the scheduler is best considered to be part of the MPL runtime system and would need to be recreated. The MPL GC needs to be informed of every fork and join in the program; additionally, the scheduler is responsible for generating (and managing) concurrent GC tasks. Without these "hooks", the GC won't perform well.

MPL performs very well on highly parallel programs, but there is still some engineering work needed to make the GC performance robust in the face of low parallelism (or no parallelism at all). See for example #115. This wouldn't be terribly difficult to fix but we just haven't made the time to address it yet.

It's good to hear that Grin optimizes much of the laziness away. Laziness might be an issue for performance with MPL. The typical low-level implementation mechanism for laziness introduces mutations into otherwise pure computations, to avoid duplicated work when evaluating a thunk. This in turn leads to on-the-fly synchronization between parallel tasks that could have been independent if the computation had been eager. The result is dynamic sharing of data across task boundaries, which is what we call "entanglement" in our research. In general, the cost of automatic memory management increases with the amount of entanglement. (If you're curious, this is studied in one of our recent papers.)

So, all of that is to say: it might be better for now to target the MLton backend. On sequential code, MLton will perform better than the current version of MPL. The good news is that, down the line, if you already have support for MLton and then want to add support for parallelism by retargeting to MPL, probably much of the code could be reused, because the MPL and MLton IRs are almost identical.

[GunpowderGuy]

How hard would it be to add serialization and de-serialization to those IRs in mlton? In idris2 and haskell is very easy since those languages have meta programming frameworks that can take care of it ( although currently idris2 only has automatic json support )

We would need serialization in order to inspect how ml programs get compiled down. And de-serialization to target those IRs from idris2.

-Could a serial program sidestep issue by running everything inside a thread instead of at the top level?

[shwestrick]

Sorry for the slow reply. MLton/MPL use a mostly-human-readable text format to dump intermediate representations, and also have parsers to read those formats back in. I believe SSA has a parser (link) and also SSA2 (link) but I'm noticing that RSSA doesn't have a parser. Perhaps it was just never needed in the past...

Could a serial program sidestep issue by running everything inside a thread instead of at the top level?

Yes, definitely, an immediate workaround with MPL would be to run everything inside one branch of a top-level par.

[GunpowderGuy]

Dont worry. Thanks you for your continued replies

Given i know only the very basics of ML. I should gather a collection of code that could show different programming patterns translated to SSA2 and RSSA. Then decide which one to use ( writing a serializer if using the latter ).

-The existing IR dumpers and parsers are available in both MPL and mlton, right?
-How hard would it be to port an RSSA parser from one project to the other ?

As an aside, the creator of GRIN believes an important rts feature is transactional memory. Does mlton or mpl support it?