[Caml-list] Would it be possible to add automatic, region-based memory management to OCaml?

[Caml-list] Would it be possible to add automatic, region-based memory management to OCaml?

[ligand]

Dear list,

Would it be possible to have automatic, region-based memory management 
in OCaml?

Also, would it have a better run-time performance than using the current 
GC?

Would it completely replace the GC or would the two systems have to 
cohabit?

I have seen even optimized OCaml programs spend 20% of their time doing 
GC.
I wonder if parts of those 20% could go away.

This is an honest question, I am not a PL/compiler expert.

Here is some bibliography that I could find or that was advised
to me:

https://dl.acm.org/citation.cfm?id=268946.268949
http://www.elsman.com/mlkit/pdf/mlkit-4.3.0.pdf
http://www.elsman.com/pdf/pldi2002.pdf

Of course, I don't want to have to annotate source code in any way.
I am thinking about a static analysis pass.

Regards,
Francois.

Re: [Caml-list] Would it be possible to add automatic, region-based memory management to OCaml?

[Basile Starynkevitch]

On 2018-04-09 07:20, ligand@free.fr wrote:
> Dear list,
> 
> Would it be possible to have automatic, region-based memory management 
> in OCaml?

Everything is possible in theory..... The real question is who would pay 
for that....
(in practice, that might mean a project of several years and several 
millions euros.... If your organization is willing to spend that, please 
tell....)

> 
> Also, would it have a better run-time performance than using the 
> current GC?
> 
> Would it completely replace the GC or would the two systems have to 
> cohabit?
> 
> I have seen even optimized OCaml programs spend 20% of their time doing 
> GC.
> I wonder if parts of those 20% could go away.


This is naive. GC is not "lost time", it is acceptable run-time 
overhead.

Imagine you rewrite your code in e.g. Rust or C++. Then you still need 
to allocate (and deallocate) heap memory. And that cost CPU time and 
memory overhead.

So, even if by magic you replace the GC by some region-based memory 
allocation, you won't win in practice 20%

To say it otherwise, even C malloc or C++ ::operator new have some 
measurable overhead; in some programs it is more than 20%.

In practice, Ocaml's GC is very well written and is one of the most 
competitive ones. And the GC is intimately tied to the code generator, 
so changing the GC would require significant compiler changes.

There is no silver bullet. 
https://en.wikipedia.org/wiki/No_Silver_Bullet

A good tutorial on GC is http://gchandbook.org/

Cheers.


-- 
Basile Starynkevitch         http://starynkevitch.net/Basile
France                       (opinions are only mine)

Re: [Caml-list] Would it be possible to add automatic, region-based memory management to OCaml?

[David Teller]

I seem to remember that the relative performance of GC vs. manual memory
allocation depends a lot of how much additional memory the allocator can
use in addition to the memory actually allocated to the mutator (i.e.
the program). From the top of my head, even with a pretty good GC, you
need to be at ~100% additional memory for the allocator before the
performance of the GC breaks even with good manual allocation.

Now, I don't remember where this number comes from, so I could be wrong.

In addition, region-based resource management can have a number of other
benefits, such as predictable destructors, as in Rust.

There is a recent paper on extending OCalm with, basically, the Rust
ownership model by Jonathan Goodwin:
http://jondgoodwin.com/pling/gmm.pdf . In this paper, you need to
explicitly differentiate between owned data and gc-ed data, as there are
differences in both typing (owned data has affine types) and semantics
(owned data has destructors, rather than finalizers).

Cheers,
 David

On 09/04/2018 14:26, Basile Starynkevitch wrote:
> This is naive. GC is not "lost time", it is acceptable run-time overhead.
> 
> Imagine you rewrite your code in e.g. Rust or C++. Then you still need
> to allocate (and deallocate) heap memory. And that cost CPU time and
> memory overhead.
> 
> So, even if by magic you replace the GC by some region-based memory
> allocation, you won't win in practice 20%
> 
> To say it otherwise, even C malloc or C++ ::operator new have some
> measurable overhead; in some programs it is more than 20%.
> 
> In practice, Ocaml's GC is very well written and is one of the most
> competitive ones. And the GC is intimately tied to the code generator,
> so changing the GC would require significant compiler changes.
> 
> There is no silver bullet. https://en.wikipedia.org/wiki/No_Silver_Bullet
> 
> A good tutorial on GC is http://gchandbook.org/
> 
> Cheers.
> 
> 

Re: [Caml-list] Would it be possible to add automatic, region-based memory management to OCaml?

[Bruno Blanchet]

Dear all,

I implemented a stack allocator for OCaml 1.05 during my PhD (a long time
ago). If you want to have a look it is available at:
http://prosecco.gforge.inria.fr/personal/bblanche/escape-eng.html

Stack allocation can be considered as a particular case of
region allocation.

I can give a bit of feedback on this topic:

- There is sometimes a gain in using stack allocation,
but a very small one (<5%). It comes from reduced GC time and better
data locality (so better cache behavior).
This is because the OCaml GC is very good at dealing with
short lived data: they have almost no cost, since they are
already dead when collecting the young generation, so they
do not need to be copied.
This point might be a bit different with region allocation,
because you might hope to allocate long lived data in regions.

- The analysis required to do stack allocation is non trivial.
Doing that represents a lot of investment.
This is certainly also true for region allocation.

- If you want the analysis to be fully automatic, you
would certainly need to keep a GC: it is unlikely that
an automatic analyzer would manage to allocate all data
in regions, without having memory leaks.

- As already said before, there is no hope to have the whole
GC time go away.

If your goal is just performance, given the small gain and the effort 
required to make the static analysis, my feeling is that in practice,
it is not worth it. You have more to gain by optimizing
other aspects of your algorithm.

There are situations in which you do not want to have GC at all
(e.g. hard real time software). In that case, using other
allocation techniques makes sense, but an automatic region
analysis may not be sufficient: you would probably need
annotations to help the analyzer, so that the GC is not 
needed at all.

Best,
-Bruno

Re: [Caml-list] Would it be possible to add automatic, region-based

[Oleg]

I believe no discussion of region memory can proceed without
mentioning the following paper:

  author	= {Tofte, Mads and Birkedal, Lars and Elsman, Martin and Hallenberg, Niels},
  title		= {A Retrospective on Region-Based Memory Management},
  journal	= j_hosc,
  year		= 2004,
  volume	= 17,
  number	= 3,
  pages		= {245--265},

https://www.semanticscholar.org/paper/A-Retrospective-on-Region-Based-Memory-Management-Tofte-Birkedal/0f091484790fc7a4807c3bf4d6019db63d1d4097

I have nothing more to say about this paper except that it is a must
read. See specifically ``Things we believe work well'' and ``Things
that have disappointed'' near the end of the paper.