Double layer reference counting (memory safety for IIRA languages)

[clinuxrulz]

One weakness of the currently released Rust version. Is if the user makes a mistake about what sodium objects are referenced in the lambda expression, then memory could be freed while still in use, thus causing a seg fault. (The program could misleading think there is a cycle)

JavaScript does not face this problem because there are actually two garbage collectors. One provided by the language, and one implemented in the vertex for freeing cycles (lack of weak ref).

The same solution could be used in C++/Rust. And even if the user makes a mistake or lies about what sodium objects are referenced in C++/Rust, then no seg fault will occur.

We can use smart pointers on the outside like we do, and implement the GC the way we do in TypeScript on the inside of out Vertex/Node. Then when a cycle is detected, instead of freeing the vertex/node memory we just disconnect the cycle and let the outer smart pointer do the freeing for us (std::shard_ptr (C++) / Arc (Rust)).

I'm having a go at it now in a wip-gc-node branch in the experimental rust version of sodium.

I've realise too that lazy construction/deconstruction can not work in C++/Rust. Because the Sources we have in the current typescript version would cause a memory cycle (which is already handled by the outer JavaScript garbage collector for us). So construction must be eager like in Java/C#. It just means our GcNode should start with reference count 1 instead of 0, and we use the IIRA provided by C++/Rust to do the increment/decrement of the reference count for us (for the cycle aware gc node).

We'd need to construct two types of sodium Nodes. One we can call Node, it will use IIRA to increment/decrement its internal GcNode reference counts. The other one we can call WeakNode, it is used in the target list in out Node, the difference is WeakNode will not increment/decrement its internal GcNode, but the data structure is identical.

accessing WeakNode after the node has been freed will not be a problem because there will be two layers of reference counting.

---

Interestingly collect_white in our four color gc algorithm needs to increment the reference count just like scan_black does. As the Node deconstructor will cause a negative reference count when freeing after collect white. This goes against the paper. But I the paper is targeting compilers and not IIRA-based libraries for the algorithm. For compilers the end-user of the language does not worry about increments or decrements at all.

---

I take back what I said about lazy construction. It is still do-able with working memory management. Just easier not to.

calling scan_black always (even when ref count is zero), then marking white when ref_count was zero seems to work for double reference counting.

3 node cycle test:

running 1 test
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] start: collect_cycles
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] start: mark_roots
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] mark_gray: start: visiting children of gc node 0
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] mark_gray: gc node 2 dec ref count
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] mark_gray: start: visiting children of gc node 2
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] mark_gray: gc node 1 dec ref count
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] mark_gray: start: visiting children of gc node 1
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] mark_gray: gc node 0 dec ref count
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] mark_gray: end: visting children of gc node 1
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] mark_gray: end: visting children of gc node 2
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] mark_gray: end: visting children of gc node 0
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] end: mark_roots
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] start: scan_roots
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] scan_black: gc node 2 inc ref count
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] scan_black: gc node 1 inc ref count
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] scan_black: gc node 0 inc ref count
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] end: scan_roots
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] collect_roots: freeing white node 0
[2020-04-11T03:56:53Z TRACE sodium_rust_alt::impl_::gc_node] end: collect_cycles

node_count 0
node_ref_count 0
test tests::node_test::node_mem_1 ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 30 filtered out

Note only one node gets freed in the cycle, then the normal non-cycle ref counter takes over to free the other nodes after the cycle is broken.

[clinuxrulz]

https://github.com/clinuxrulz/sodium_rust_concurrency_experiment/tree/wip-gc-node-3

(wip-gc-node-3 branch)

Getting really close now. The double layered cycle-aware reference counting algorithm is hooked up, and I'm currently working through all the little dyslexic errors in the code. The code has been through 4 different GC attempts already, and there are some places I must of missed in the code when updating to the latest attempt.

Currently 25 tests passing, 7 tests failing (only failing due to memory management issues).

Pretty much every sodium object has a cycle it it. E.g. Cell/Stream object references its own Node object and the Node object references its Cell/Stream. Then dependent Nodes are referencing its dependencies Stream/Cell and corresponding Node. Cycles everywhere! So the cycle detection seems to be working very well.

I had to do two separate GcNodes (E.g. one for Stream object and one for Node object) due to lack of inheritance support in the Rust language. I could drop back to one GcNode per sodium object, just a little trickier. (I'd need to implement inheritance)

---

OK. On branch "wip-gc-node-4" I am making the push for inheriting the Nodes into Stream/Cell so I can half the number of GcNodes. As it will simplify memory management significantly.

---

Realised a bug in my gc impl. Now all tests in "wip-gc-node-3" branch pass except the 3 switch tests. I'm still going forward with the "wip-gc-node-4" branch as it will help with the performance of the gc.

[clinuxrulz]

OK, in the "wip-gc-node-4" branch. All tests are passing, and the memory management is fully working. (fully automatic).

Time to do a little bit of a tidy up on the API (I made a little mess when going through 4 different GC attempts). Then when done I'll merge it back into the "master" branch.

After that I will do a sodium-rust version 2.0 official release. As I consider the memory management in this version much nicer.

[the-real-blackh]

This is great!!
I'm really excited about this! When you've done it, I'll see if I can translate it into C++.

[clinuxrulz]

If you feel up to it, have a go:

https://github.com/SodiumFRP/sodium-rust

The master branch is now on v2.0 with the changes made.

Short description of changes:

Announcing Sodium Rust v2.0

Sodium Rust v2.0 is now available to try out! Memory management is less of a headache now compared to v1.0. No more need to use Gc / NoGc wrappers around values you pass through sodium objects. No more need to implement Trace / Finalize traits for the types of values you pass through sodium objects. No ranks or priority queue (fast switching switchS / switchC). More memory safe. No more false positive cycles causing seg faults. (In case of mistake in memory dependencies passed to lambda1,la…

[clinuxrulz]

@the-real-blackh let me know when you start. I'd like to help out. Between the two of us, I'm sure we can resolve that automatic memory management once and for all. No need for complicated trait simulation through templates, we can keep it nice and simple.

[the-real-blackh]

I will let you know when I start. I can't say when it'll be. I am busy at work and really overdue for a holiday, so it's hard for me to do this kind of stuff at the moment.

[clinuxrulz]

That's all good. Maybe create an empty repo under "SodiumFRP" called something like "sodium-cxx-experiment" that we can both push at from time to time. I've made a start at converting it, and I'm feeling pretty confident this time.

So far I've translated the gabage collector, the transaction and the node. The rest should be pretty straight forward, I just struggle a bit with forward declarations of template based classes.

E.g. getting the Cell class methods able to see the Stream methods while also getting the Stream methods to see the Cell methods.

That is the area I could use some help.

[clinuxrulz]

https://github.com/clinuxrulz/sodium-cxx-alt

under "sodium/sodium.h" will be wrappers exposing the public API to the end user (It is currently empty). I'll copy your tests over from your sodium-cxx repository, and make sure the API is identical to the original.

everything under "sodium/impl" is the internal implementation, that the end user will not see (to achieve package-private). It is a direct conversion of all the code in the "impl" folder in the Rust version into C++.

There are no locks yet for thread safety. Will sort that out in the the 2nd sweep after the tests are passing and the automatic memory management is working.

• Stream: done
• StreamLoop: done
• Cell: done
• CellLoop: done
• StreamSink: done
• CellSink: done

Getting there. Pretty much any Arc gets replaced by std::shared_ptr, and any Box gets replaced by std::unique_ptr. Just a little tedious.

[the-real-blackh]

Thank you! Hopefully I'll make a contribution too.

[clinuxrulz]

All the code has been converted over in the "impl" folder, now getting started on the public API.

We have the following options for optional:
1) nonstd::optional (optional lite), no boost required, C++11
2) use boost::optional, C++11
3) use std::optional, C++17
4) any other suggestion?

@the-real-blackh which one would you prefer from above?

[the-real-blackh]

I think boost::optional for C++11 since I would think that is the most likely thing for someone to want to use. For C++17 std::optional.

[clinuxrulz]

I'll boost optional for now.

Plan of attack is to:
- copy your "sodium.h" file in from your sodium-cxx repository
- empty out the content of all the methods
- redirect calls to the "impl" folder version. (wrap up the sodium::impl stuff)

Hopefully then can obtain same API.

For tracking lambda capture I'm currently following the following syntax:

lambda([sa,sb,ca](args) { /* body */ }) << sa << sb << ca for tracking streams sa, sb and cell ca as an example. Sort of like how we use std::cout. Its the only addition to the API.

In TypeScript the above would be lambda((args) => /* body */, [sa, sb, ca]);

[clinuxrulz]

@the-real-blackh just wondering, do we have any additional performance tests (apart from the one for router) for the C++ version. Or any open-source performance demanding apps for the C++ version.

Just want to be sure I'm not hurting the performance for the average case scenario. The algorithm is designed to perform well for a large number of firing nodes, but I believe it will not perform as well for just a few firing nodes.

The exposed Node interface does support using a priority queue without any change to the code inside Stream/Cell. It can take on different evaluation strategies. So I should be able to compare performance of different strategies as long as there are some tests floating around.

---

Also I'm not sure if I can support this use case:

void test_sodium::move_semantics_hold()
{
    stream<unique_ptr<int>> e;
    auto b = e.hold(unique_ptr<int>(new int(345)));
    auto val = b.map([](const unique_ptr<int>& pInt) {
        return pInt ? *pInt : 0;
    });
    CPPUNIT_ASSERT(val.sample() == 345);
}

My implementation does not have something like a light_ptr at the moment. I have the following for holding the state of a stream.

template <typename A>
class StreamData {
public:
    boost::optional<A> firing_op;
    SodiumCtx sodium_ctx;
    boost::optional<std::function<A(const A&,const A&)>> coalescer_op;
};

If I go:

template <typename A>
class StreamData {
public:
    boost::optional<std::shared_ptr<A>> firing_op;
    SodiumCtx sodium_ctx;
    boost::optional<std::function<A(const A&,const A&)>> coalescer_op;
};

Then I can support the void test_sodium::move_semantics_hold() at the cost of some performance. (extra layer of indirection)

---

Actually I need to support test_sodium::move_semantics_hold() so that I am matching the same API. So I'll throw in the std::shared_ptr into firing_op.

[clinuxrulz]

There are two extra functions I have not seen before in sodium-cxx.

A accum that takes a cell, and returns a cell. (I know of the accum that takes a stream and returns a cell)

And collect that takes a cell, and returns a cell. (I know of the stream one)

Those are the last two functions to add to complete the API. As well as router (I have a plan for its alternative impl too, it is like a backwards switchC in that it changes dependencies of dependents instead of changing dependents of dependencies)

So almost done.

Was thinking we could go "SodiumFRP/sodium-cxx-alt-1" for the name, then another competing implementation could go "sodium-cxx-alt-2", etc.

Could take us some time to catch-up to all the little performance tweaks that have entered into "sodium-cxx" over the years.

[the-real-blackh]

Thank you for doing this!

I don't think light_ptr is the right way. The thing is, dereferences are generally expensive because of how frequently they generate a cache miss and the amount of data fetched into the cache is quite large (64 bytes or so - I don't know the exact figure), so it is almost always better to copy data structures - even fairly big ones - than it is to pass pointers around. And, the code is simpler.

Don't worry about the move semantics stuff. We can always do that later.

Anything that's not in other versions, don't worry too much about. I have used the C++ version extensively in a commercial project, and I ended up adding some things that maybe shouldn't be there.

I don't have any benchmarks. That's something we need to look into more.

[clinuxrulz]

Lost my drive to do this for about a month. Sodium in C++ is very tricky. I came back to it for a bit.

Currently down to two tests failing, and router tests are currently commented out:

C:\Users\clinu\Documents\GitHub\sodium-cxx-alt\tests\build\Debug>sodium_tests.exe
...............................................F......F


!!!FAILURES!!!
Test Results:
Run:  53   Failures: 2   Errors: 0


1) test: test_sodium::detach_sink (F) line: 908 C:\Users\clinu\Documents\GitHub\sodium-cxx-alt\tests\test_sodium.cpp
assertion failed
- Expression: *cleanedUp == true


2) test: test_sodium::snapshot_initial_value (F) line: 299 C:\Users\clinu\Documents\GitHub\sodium-cxx-alt\tests\test_sodium.cpp
assertion failed
- Expression: vector<int>({ 10, 2, 18 }) == *out

And have not checked if all nodes are being freed in the C++ version yet. But confident it will do so after a bit of debugging, as the theory works in the Rust version.

---

Update (18/06/2020): All tests passing (correct out vectors), however 14 are leaking memory. Debugging time.