Borrowing model

[torkleyy]

This issue shall discuss the borrowing model of the nodes in vnodes. For those of you who don't know, these nodes will be structured in a tree like this:

├── dev
│   ├── keyboards
│   │   ├── 0
│   │   └── 1
│   └── platform
├── ecs
│   ├── get
│   ├── insert
│   ├── join
│   └── world
│       ├── BarResource
│       └── FooResource
├── io
│   ├── assets
│   │   ├── dwarven_crossbow.gltf
│   │   ├── mesh.obj
│   │   └── terrain.png
│   └── configs
│       └── display.ron
│           ├── msaa
│           ├── resolution
│           │   ├── height
│           │   └── width
│           └── vsync
└── scripts
    ├── dragons.lua
    ├── inventory.rhai
    └── weapons.rhai

Each identifier above is called a node. Note that just because it is represented as a node, it doesn't mean it has that's that internal representation. Especially for values inside configs, that would be too expensive.

Requirements of the borrowing model

Obviously it should work in parallel. What parts exactly shall work in parallel, where we make exceptions, that's part of this discussion. To find a good model, we need to know which operations are very common and which are not (and thus may be more expensive).

Common operations

• very common: calling a node; this can be a script or an engine function that's exposed via nodes (e.g. /ecs/insert to insert a component)
• reading a node's internal data, e.g. values from a config file, a resource
• writing to the node when it gets called

Average

• random writes to nodes, e.g. on an event callback

Rare operations

• creating new nodes
• overriding an existing node
• removing an existing node

Selected models with their pros and cons

Static borrowing model

In the static borrowing model, the compiler controls read and write access. Nodes would be retrieved as references from the tree.

Advanges

• very fast: checked at compile-time
• low implementation effort

Disadvantages

• only allows to borrow one node mutably at once
• forces us to either make everything immutable or drop parallelism

Wrap everything with a Mutex

A Mutex can be locked to get a mutable reference. This would be done internally, and every node would be an Arc<Mutex<Node>>. Note that deadlocks aren't possible except the node triggers a callback that tries to borrow the same node (but this is an issue with every model I know of).

Advantages

• easy for implementors because they always have mutable access
• if the same node is barely used in parallel, this allows things to run arbitrarily in parallel

Disadvantages

• high overhead

Make every method receive &self, let user choose how to wrap

If every method of a node (calling, setting a sub node, reading a value, ..) takes an immutable reference, there is no borrowing issue anymore. However, quite some nodes actually do need write access. For that, they would need to wrap their internal data or specific fields with a Mutex, RwLock, etc.

Advantages

• improves on the above approach of wrapping everything by default, immutable nodes won't need to do any locking
• atomicity and individual strategies can be used to optimize parallel access

Disadvantages

• additional burden on implementors
• overhead differs, largely dependent on how much the nodes are optimized

Some random ideas

• acquiring tickets upfront, similar to system dependencies in Specs (seems difficult, esp wrt callbacks; might be solved by deferring them)
• creating copies of the data with the risk of reading dirty (outdated) revisions
• working with change sets, possibly STMs
• create a topological sort of the nodes, allowing to lock specific regions (like say /dev/keyboards recursively) by an index range

---

That's all I can think of for now. Please add your ideas and opinions below ;)

[Xaeroxe]

My favorite is

Make every method receive &self, let user choose how to wrap

This allows the greatest performance tuning, and I consider the burden on implementors to be minimal.

[torkleyy]

That's how it is currently implemented at this stage.

[OvermindDL1]

Very cool, looks good initially. A few notes:

Rare operations are considered as creating/removing/overriding nodes, that is actually super common on 'some' nodes in my old engine as each entity in the ECS was exposed as a 'node' (even though it was just a proxy) with a variety of interactions able to be done on it (including registering events by adding an event component to that entity if necessary, the event component was just a dedicated event listener storage area).

Most interactions in mine were very single-thread and the multi-thread interactions were serialized if I had any contentions. It would probably be good to let each node handle it's own synchronization and maybe even per call as different actions can require (or even not) very different synchronization styles.

The ticket style is one I'd thought of as well but never experimented with it to see how it would play out.

I think every method receiving &self would be best overall though just on a cursory glance.

I'd love to say more but I'm a bit sick so I'll try to look later... ^.^;

[Moxinilian]

Regarding the borrowing model, here is a thought I had.

If one would build a system using a scripting language, the dispatcher can know what resources the system will need to access during its execution stage. Therefore, why not give the script a wrapped reference?
This wrapped reference would contain a gate and a reference. Here would be the normal life cycle of a system on every update iteration:

• The dispatcher opens the gate of the wrapped references.
• The system runs its run function for as long as it needs during the execution stage.
• Once the run function returns, the gates get closed by the dispatcher and it goes on with the next execution stage.

While the gate is closed, it is not possible for the scripting language to access the content of the reference. That way, we can guarantee a mutable or immutable reference is only accessed when the dispatcher knows it is allowed. The script can continue doing stuff using threads of course, but it will not be able to access potentially used resources.

The runtime overhead cost of such a mechanism is extremely small, as it's only a matter of setting boolean values. As the scripting language can not copy the reference itself, every time it wants to access the value it needs to go through the wrapped reference. That means that every value access requires an additional if, but if compiled properly this can be 2 x86/ARM instructions, and if memory mapped correctly it would not break the CPU caching.

[torkleyy]

Sorry if this wasn't clear enough in my comment, but the borrowing model is mostly about the ownership of nodes. Those nodes aren't managed by shred (and probably shouldn't be if you look at the consequences of that model for vnodes).

[Moxinilian]

I don't see the issues?

[torkleyy]

Execution is not arbitrary (as such an interface should be), but uses a fork-join model as Specs. That doesn't make that much sense for vnodes as a general-purpose bridge between languages and code units.

[torkleyy]

Also look at the most common operation listed:

• very common: calling a node; this can be a script or an engine function that's exposed via nodes (e.g. /ecs/insert to insert a component)

[Moxinilian]

Are we designing an interface for Amethyst systems written with scripting languages to interact with the ECS, or is there something more I don't get?

[torkleyy]

Err vnodes is more than that, I'm sure we discussed it. You need to expose most of the Amethyst API to scripts somehow, so yeah it definitely is more than an interface for ECS, it's an interface for cross-language communication. And then there will also be the need to not compile all the Rust code into one big binary, but also shared libraries. For that you'll also need some way to logically "share" the core API.

[Moxinilian]

Okay, but what's the issue with having all this API be managed by shred?
Rust doesn't need it because it has borrow checking, but if we use any other language, why not use the borrow checking capabilities of shred to protect vnodes?

[Moxinilian]

We could have vnodes be a special kind of SystemData.

[torkleyy]

As I've said, with shred

[e]xecution is not arbitrary (as such an interface should be), but uses a fork-join model as Specs. That doesn't make that much sense for vnodes as a general-purpose bridge between languages and code units.

You want to call vnodes' nodes from everywhere, not build up a whole dispatcher before that.

[Moxinilian]

I feel like you are trying to solve again the borrow checking problem.
What you are trying to design is safe parallelism without constraints on lifetimes.
Rust was invented because they felt that there is no acceptable solution to that problem.

Also, if vnodes are to be called from everywhere, I don't see why Amethyst would have to use an architecture that bends to this constraint considering we already control when code is executed through shred.

[torkleyy]

As I don't plan to write any more code here, feel free to try it out. I won't reject any PRs or anything like that, I just thought you were asking for my opinion.

[Moxinilian]

Of course I was!
I'm just not sure the original purpose of vnodes is realistic, so that's what I wanted you to address.

[torkleyy]

I think it's necessary to expose the API properly, yes. "Realistic" - it's not very easy, but it's the best I've come up with to solve many problems. But this all just very experimental, so I really recommend you start with some code and see how well it works. I opened this issue after I implemented one model, sort of as a documentation and an ongoing, well, development of this model. You need to start with something to see how it works in practice.

[Moxinilian]

Do you have a specific example of stateful Amethyst API that is not part of the ECS?

[torkleyy]

Dealing with all kind of values, like Transform or other components.

[OvermindDL1]

Also as a note, in my engine a vnode was not 'owned' by the vnode tree at all, especially remember that a single vnode may be in multiple places of the tree at the same time, can be added/removed on the fly, and all vnodes were 'owned' and handled by other systems, whether hardware interfaces, a game level and the entities within it, etc... etc...