From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <bruno.blanchet@inria.fr>
Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83])
	by sympa.inria.fr (Postfix) with ESMTPS id 841838240C
	for <caml-list@sympa.inria.fr>; Mon, 16 Apr 2018 17:31:57 +0200 (CEST)
X-IronPort-AV: E=Sophos;i="5.48,459,1517871600"; 
   d="scan'208";a="323083137"
Received: from zcs-store3.inria.fr ([128.93.142.30])
  by mail2-relais-roc.national.inria.fr with ESMTP; 16 Apr 2018 17:31:57 +0200
Date: Mon, 16 Apr 2018 17:31:57 +0200 (CEST)
From: Bruno Blanchet <bruno.blanchet@inria.fr>
To: caml-list@inria.fr
Message-ID: <1254277202.4888153.1523892717467.JavaMail.zimbra@inria.fr>
In-Reply-To: <587a5888-629b-1257-2035-4fefc0308ab5@gmail.com>
References: <1ecada996e0b0d0069daf03241622159@free.fr> <6618a201557cf5ede5aaf15eb0ed21d8@starynkevitch.net> <587a5888-629b-1257-2035-4fefc0308ab5@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Originating-IP: [128.93.64.167]
X-Mailer: Zimbra 8.7.11_GA_1854 (ZimbraWebClient - FF59 (Linux)/8.7.11_GA_1854)
Thread-Topic: Would it be possible to add automatic, region-based memory management to OCaml?
Thread-Index: XYMVAPSqdNoCiPT5uKlCFHs3bO0V+w==
Subject: Re: [Caml-list] Would it be possible to add automatic, region-based
 memory management to OCaml?

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