Proposal for deterministic memory management

[Amin_Yahyaabadi]

@kristoffer.carlsson

No, I mean… it is dynamic. Which is why it needs to be a “manager” that run alongside the code and keep track of stuff during runtime.

Can you give an example that requires a runtime manager?

@kristoffer.carlsson

Anything particular in those languages? Rust has a borrow checker and drop (Drop in std::ops - Rust) values when they go out of scope but there is also reference counting objects to into that when needed.
C++ has stuff like RAII but for handling dynamic lifetimes you can use unique_ptr and shared_ptr which can kinda be mapped to a borrow checker (only one owner) and reference counting respectively.

None of these feel really applicable here so perhaps you could elaborate.

I meant the concepts in general. I don’t know if any of the languages implement exactly what I have in my mind.

[kristoffer.carlsson]

@Amin_Yahyaabadi

Can you give an example that requires a runtime manager?

Let’s say you have

const global_var = []
function f(a,b)
    v = Any[1]
    rand(Bool) && push!(a, v)
    rand(Bool) && push!(b, v)  
    rand(Bool) && push!(global_var, v)
    rand(Bool) && push!(v, v)
    rand(Bool) ? do_something(v) : do_something_else(v)
end

and a and b are created in some other scope and we call f(a, b).

When do you free the memory for the object initially assigned to v?

@Amin_Yahyaabadi

I meant the concepts in general.

What concepts? That you do some sort of cleanup at scope exit? If your idea seems very simple and you think it works well, do you see any reasons why it has perhaps not been adopted elsewhere? Is it just that no one was smart enough to think about it or is it possible you missed some important point that makes the algorithm not work in practice?

[Amin_Yahyaabadi]

Because of the runtime conditions, the scope here depends on the runtime value. This is what the compiler will give if wants to consider runtime values. See here for the worst case analysis

# lowered dynamic code:
const global_var = [] # Var{:global}
function f(a,b)

    v = Any[1] # Var{:f_local}

    r1 = rand(Bool)
    if r1
        push!(a, v)
        # v becomes outer(Var{:scope_of_a}, Var{:scope_of_v})
    end

    r2 = rand(Bool)
    if r2
        push!(b, v)
        # v becomes outer(Var{:scope_of_b}, Var{:scope_of_v})
    end

    r3 = rand(Bool)
    if r3
        push!(global_var, v)
        # v becomes outer(Var{:global}, Var{:scope_of_v})
    end

    r4 = rand(Bool)
    if r4
        push!(v, v)
        # v becomes outer( Var{:f_local}, Var{:scope_of_v})
    end

    r5 = rand(Bool)
    if r5
        do_something(v)
        # scope of v is returned from do_something(v) (should be processed by the compiler separately)
        # v becomes outer( Var{:return_scope}, Var{:scope_of_v})
    else
        do_something_else(v)
        # scope of v is returned from do_something_else(v) (should be processed by the compiler separately)
        # v becomes outer( Var{:return_scope}, Var{:scope_of_v})
    end

    return


    # delete everything with f_local scope. v will be deleted if it was among them. For example:
    if scope_of_v == :f_local
        delete v
    end
end

#where_a_scope exits
# delete everything with scope_of_a. v will be deleted if it was among them. For example:
delete a
if scope_of_v == :scope_of_a
    delete v
end

# same for b

# if global should be deleted manually

@kristoffer.carlsson

What concepts? That you do some sort of cleanup at scope exit? If your idea seems very simple and you think it works well, do you see any reasons why it has perhaps not been adopted elsewhere? Is it just that no one was smart enough to think about it or is it possible you missed some important point that makes the algorithm not work in practice?

The fact that I am not aware of the mechanisms and codebase of each language does not mean that no one has implemented this. This is a hard problem to tackle, and I did not say this developing idea is the only solution ever.

[kristoffer.carlsson]

@Amin_Yahyaabadi

The scope here depends on the runtime value. This is what the compiler will give.

Okay, now this looks like a reference counting system were you at runtime keep track of the number of references. We’ve kind of come full circle now though (Proposal for deterministic memory management - #20 by kristoffer.carlsson) so I’m not sure there is much more to say. Reference counting is perfectly valid but it has some drawbacks in terms of performance (especially when it comes to multi threading) which I think is the reason it wasn’t chosen for Julia.

[Amin_Yahyaabadi]

We can make the previous example static by considering the worst case (outer scope). Scope of a and b can be found from the user’s code.

Worst case for this particular example is that v becomes global and so it should be deleted manually.

# lowered static code:
const global_var = []  # Var{:global}
function f(a,b)
    v = Any[1]
    rand(Bool) && push!(a, v)
    rand(Bool) && push!(b, v)  
    rand(Bool) && push!(global_var, v)  # worst case v becomes Var{:global}
    rand(Bool) && push!(v, v)
    rand(Bool) ? do_something(v) : do_something_else(v)
end

# v should be deleted manually

[kristoffer.carlsson]

@Amin_Yahyaabadi

We can make the previous example static by considering the worst case (outer scope). Scope of a and b should be given by the user.

Worst case for this particular example is that v becomes global and so it should be deleted manually.

Yeah and then you have a potential memory leak. v is not referenceable and yet it will never be freed.

Computing the static worst-case will, in general, be very pessimistic (just think about dynamic dispatch) and you won’t be able to free a lot of things (except when Julia is exiting…)

You will also no longer free values close to when they become unreferenceable which I thought was one of the main points of this discussion.

[Amin_Yahyaabadi]

Yes. A leak finder in combination with static compiler can help the user in this case.
https://www.beeflang.org/docs/language-guide/safety/#memory-leaks

@kristoffer.carlsson

You will also no longer free values close to when they become unreferenceable which I thought was one of the main points of this discussion.

Yes. But the compiler cannot do magic and predict the runtime behavior.

[kristoffer.carlsson]

Ok so now we are at the point where we run a “leak finder” in our language that has an automatic memory management system whose purpose is to make us not have to do manual memory management and not have to worry about leaks… That seems like a really unfortunate state of affairs.

@Amin_Yahyaabadi

Yes. But the compiler cannot do magic and predict the runtime behavior.

Very true, which is why you need something that runs at runtime Like a garbage collector.

[Amin_Yahyaabadi]

There are three solutions here.

• • automatic management for most of the cases +
  • warnings from the compiler for the potential leaks (coming from the worst case analysis) +
  • debug leak finder help for runtime behavior
• runtime garbage collector
• ownership syntax and borrow checker

From the beginning, my point was that these solutions should be usable in combination with each other. That is why I think we should only do automatic management for a variable marked by Var.

To keep Julia enjoyable to use, I don’t want to introduce the ownership syntax. As I already mentioned, the surveys show that users don’t like this.

After the compiler issues warning regarding potential leaks, the debug leak finder can run the program once with the user given parameters and then point to the places that a variable is not deleted, and offer solutions for it. I find this easier to use.

Check this fun question. This is exactly our situation.
C++20: C++ at 40 - Bjarne Stroustrup - CppCon 2019 - YouTube

[Ratingulate]

This is a great vision, but I’m not sure why this static subset has to be concretely typed?

With some language notion of interfaces/protocols/ traits, we could write programs against these, albeit with restricted semantics, and still verify errors at compile time, like rust, swift etc

[Elrod]

@kristoffer.carlsson

You will also no longer free values close to when they become unreferenceable which I thought was one of the main points of this discussion.

I tried benchmarking some GC-heavy code with GC enabled vs disabled once.
It was much faster with the GC enabled, I believe because it would reuse memory in the cache rather than constantly churn.

But I get how in real time “bad on average but predictable” is better than “good on average but unpredictable”.

mutable structs will often become stack allocated and “automatically managed” without the GC in many cases when the compiler can prove that is safe to do.
This doesn’t work for Arrays, but it would be nice if it did.

[c42f]

@Ratingulate

I’m not sure why this static subset has to be concretely typed?

True some limited forms of dispatch are probably fine. In dispatch over small Unions of concrete types the compiler already explores the set of possible methods which might be called.

[Ratingulate]

Maybe i’m not understanding what you meant by concretely typed.

Did you mean concrete typing in method signatures? So nothing that’s duck typed, or typed for abstract arrays for example? Even if type stable?

[Mason]

Duck typing is fine. He means that type signatures are all inferred (though the entry-point to the statically compiled binary should to be concrete).