rustgd / vnodes Goto Github PK

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 ;)

I'd like to create a blog post for the Amethyst website as soon as the rewrite landed. I think I can use some of the things I already explained in amethyst/amethyst#725 .

@Moxinilian Anything specific you want me to include? Feel free to comment some things that helped your understanding of vnodes. I'll probably look into creating some diagrams for the post, too.

While the performance isn't bad, it is "only" about two times faster than FnvHashMap (with strings!).

@OvermindDL1 did you do any benchmarks on your maps? Do you know how they compare to string maps given a size of 32?

In my rewrite I'm using a Stack (similar to the Lua one) to store values of different types in a plain Vec. This allows me to save unnecessary allocations.

Every time you call a dynamic function, you push the arguments to the stack, the function pops them off again and pushes the return value.

In my current experimentations (PR will follow soon), I've used tuples with the intention to always expect a tuple for function args.

This, however has two disadvantages:

• exposing the vnodes_push_* functions for tuples to C seems to be rather complicated
• individually popping off only one element at a time is impossible, we need to pop the whole tuple at once

Why is that a problem? Each segment of a path is basically a u64. So let's say we search for a node /foo/bar/other/meaning/ful/words. The first segment we can pop (that's at the top of the stack) is "foo". So the root node knows it needs to go to the foo node. That's enough, we don't need to know any more. But if we need to pop the whole tuple, we can't pop just a single path segment. We'd need to pop the whole path, provide a rather large buffer for it or even allocate for it. That's not what we want.

Thus, I think we should simply allow to push and pop multiple values to the stack for the function parameters. However, this has a drawback. We can't check if we have all the right types upfront and a node might pop too many elements from the stack. How should we deal with that? Pass an integer indicating the number of arguments?