[erlang-questions] About Garbage Collection

[Ş. Volkan Erdoğan]

It seemed like a good idea at first :)
I just thought that , since there is no memory is shared between
processes one can determine when a memory location is not used in a
process conservatively by static analysis and tried to present a
scheme for that but it turns out to be wrong.
Thanks a lot for the explanations.


2010/11/11 Richard O'Keefe <ok@REDACTED>:
>
> On 10/11/2010, at 7:19 PM, Ş. Volkan Erdoğan wrote:
>
>> Hi,
>> I have an idea about memory management in Erlang and although the idea
>> is still raw I'd like to share with you.
>>
>> As far as I know:
>> - There are no global variables in Erlang. Memory is allocated in functions.
>> - Function calls in processes and message passing operations to other
>> processes have copying semantics.
>
> More precisely, you can't *tell* whether things are copied or not.
>
> But in practice, function arguments are NOT copied.
> Consider for example
>
>        len(List) -> len_loop(List, 0).
>
>        len_loop([], L) -> L;
>        len_loop([_|Tail], L) -> len_loop(Tail, L+1).
>
> Suppose you have a list L = [1,...,N].
> If arguments were copied, len(L) would take O(N**2) time.
> Since arguments are *not* copied, len(L) takes O(N) time.
>
>> So I believe that these properties guarantee that any memory location
>> allocated by runtime is exclusive to the function which requested that
>> memory
>> and it is not possible for a reference of a memory location to
>> escape from the function that created it.
>
> Consider
>        f(X) -> Y = g(X), {Y,Y}.
>        g(X) -> [X,X,X].
>
> The memory allocated by g/1 for the three-element list [X,X,X]
> is *not* exclusive to g/1 but outlives the call that created it.
> The value of Y in f/1 is the very same list allocated in g/1.
>
> So this is wrong.
>
>>  And as a result it is
>> possible to safely deallocate all memory allocated by the function at
>> function exit since those memory locations can only be accessed by
>> that function.
>
> And that's wrong too.
>
> However, there's something that _could_ be done.
> There was a system called I think "Formula Algol" developed at CWI
> many years ago; a computer algebra system.  I reimplemented it in
> Burroughs B6700 Algol in the late 70s and had a lot of fun with it.
> The key idea there was that when a function returned,
> the new cells it had allocated were copied back to its caller,
> and everything not returned was freed.
>
> However, that has problems too.
>
> Consider
>
>        make_list(N)
>          when is_integer(N), N >= 0 ->
>            make_list_loop(N, []).
>
>        make_list_loop(0, L) ->
>            L;
>        make_list_loop(N, L) ->
>            make_list_loop(N-1, [N|L]).
>
> For example, make_list(3) ==> [1,2,3].
>
> Copying the results back would make this take O(N**2) time
> whereas the real non-copying Erlang system takes O(N) time.
>
> However, if we push on that idea a little harder, we come
> close to the idea of REGION allocation.  In effect, the heap
> is broken into a lot of little heaps, and a function can
> allocate its result in (one of) its caller's heap(s).
> A good quick reference to that is
> http://mlton.org/Regions
> which explains why the MLTon compiler for ML does NOT use
> regions.
>
> I don't *think* regions are compatible with hot loading, but
> it would be nice to be wrong about that.
>
>
>