Recommendations for 2-phase cyclic graph structure app

help
1

I'm attempting to write my first real Rust app, based on one I wrote in C. I'm looking for recommendations on the questions/ideas below. Any help is greatly appreciated!

The app has 2 phases. The first phase is single threaded, and builds a large cyclic graph data structure. No parts of the graph are deleted during the process. Nodes contain both individual links and dynamically sized collections of links to other nodes, along with strings and POD fields.

The second phase is multi-threaded, and traverses through various parts of the graph many times, but never does any modifications of the graph. A lot of the performance of the second phase depends on the speed of those traversals. Once in the second phase, the process will remain there (it's a long-lived server).

If I use interior mutability (using Cell throughout), that makes the first phase pretty easy. But, that seems like it would remove the possibility of compiler optimizations during the second phase that take advantage of the total lack of modifications. Also, Cell is !Sync - so how would the graph become sharable by all threads in the second phase?

A wild idea is to have a pair of memory-identical representations for all node types in the graph - one that wraps Cell on all fields and the other that doesn't. Then, do one unsafe cast of the entire graph (by casting its root) after the first phase from the Cell version to the non-Cell version. The second phase threads would share the non-Cell version, which would be Sync and get all the nice optimization benefits from the lack of further modifications. Does that sound crazy? I suspect that this paired-type setup could be keyed by a boolean generic parameter.

Or, is there a better way?

Also, what should I use to own the graph nodes (all of which are 'static)? Some kind of arena?

2

How are the links represented, what is their type?

3

I haven't yet used it myself, but fused_lock::FusedRwLock sounds perfect for this application. It behaves as a sort of combination of Mutex and OnceCell: it is interior mutable until it is “locked for reading”, at which point it is permanently no longer mutable and gives out & references to its contents.

You can also use a graph representation that doesn't involve any interior mutability; usually, that is only necessary if you're storing Arc/Weak pointers to the nodes in the graph itself. If you avoid that, and store indices instead, then there is no trouble with mutating any single node. (Mutating multiple nodes at once might still be troublesome.)

2 Likes
4

How are the links represented, what is their type?

Right now, it's in C - so they're typed raw pointers. The question is how best to convert this to Rust...

5

fused_lock::FusedRwLock sounds perfect for this application

I will look into that - thanks!

If you avoid that, and store indices instead, then there is no trouble with mutating any single node

If I use indices, then each deref during phase 2 involves a bounds check and address arithmetic - slowing down things considerably vs. what C can get.

6

fused_lock::FusedRwLock sounds perfect for this application

I will look into that - thanks!

I don't think FusedRwLock is going to help. It's not something that makes sense to use in place of using Cell around every field of the nodes, and it doesn't help share the overall graph (which has to be !Sync because all of the nodes' fields are wrapped in Cell).

7

Are you sure? The optimizer may do better than you think with that. You can't use pointers/references in safe Rust for this.

1 Like
8

Note that address arithmetic is essentially free -- *p and *a.get_unchecked(i) are each just a single mov on x64, for example (assuming a small power-of-two-sized element).

Depending how many indices you need to look at, you can sometimes have the change pay for itself by using smaller indices than pointers -- using u32 indices instead of 8-byte pointers can sometimes save enough on RAM bandwidth to more than pay for the extra usage of address computation units.

As for bounds checks, never underestimate the branch predictor, since the failure side of bounds checks in Rust is marked cold in LLVM: How much Rust's bounds actually cost | Readyset

2 Likes
9

I will take some time to try to wrap my brain around the idea of using indices pervasively.

It feels a bit like:
Rust: "C/C++ developers, come join us and achieve safe and efficient memory usage!"
C/C++ developers: "Sounds great! How should we convert our C/C++ apps to Rust?"
Rust: "Simple! Imagine you're in the 1960's using FORTRAN and code all links as vector indices!"
C/C++ developers: "SRSLY?"

10

Man, do I wish!

1 Like
11

You might be interested in this classic post: Modeling graphs in Rust using vector indices · baby steps

Depends which C/C++ developers you talk to.

If you find the ones deep down the data-oriented design rabbit hole that store all their stuff in Struct-of-Arrays form and process stuff by walking an index down the slices for the fields they care about, they'll say "well of course!" :upside_down_face:

6 Likes
12

If nothing else, it might help to sketch out your design with the standard Rust graph library: petgraph - Rust

That uses integer indices and creates Send+Sync graphs, so you should be able to get something like what you describe working quite easily, and you will probably find the performance better than you might expect.

2 Likes
14

It seems to me that using vector indices for links in Rust is, for all practical purposes, not benefiting from using Rust.

In my app's case, lifetimes are not an issue because all nodes in the graph last for the whole process. But, if one has a cyclic graph structure with the need to deallocate nodes, then using vector indices means that the problems with dangling references are back with no protections from the borrow/drop checkers.

For instance, if deallocate is simulated using free lists, then there is the possibility of holding an index to a node that got free-listed (and possibly reused) and indexing with it. It's not formally UB, but it can provide all of the problems of UB (except segfaults - which is the best outcome of UB). UB or not UB? That is the wrong question.

Also, there can be multiple vectors with the same element type. An index into one of them would compile when used on any of them. The runtime bounds check will only detect cases where the index is too high. If the index passes the bounds check, the result is very much the same as derefing through a dangling pointer. Even if there is no deallocation. UB or not UB? It's still the wrong question.

To get rid of the above problems and regain full Rust benefits (compile-time guarantee of no UB or the above non-UB equivalents): Don't ever deallocate nodes (free-list or otherwise), and use a singleton vector per node type.

Or, invert the type-checking by moving it to the index: wrap indices in a struct parameterized by target node type, and use a single singleton untyped vector. That's more convenient than having to pass around refs to many vectors each with a different node type.

Call that singleton untyped vector a heap :wink:. Have some heap::new function be the only way that the type-safe wrapped indexes can be created. Don't use realloc internally, just add new storage discontiguously if needed (keeping individual nodes contiguous, but possibly wasting some memory). This means that we also don't need to do any bounds checking or address arithmetic - the wrapped index structs can instead wrap raw pointers directly to their target node.

To retain the small amount of useful borrow checking that Rust did provide in the vector indices case, use a token to represent the singleton heap, pass around a &mut reference to it, and have indexing functions on it borrow from the &mut or & self reference. You can get multiple distinct node &muts by implementing the equivalent of HashMap::get_many_mut on the singleton heap token (runtime checking is needed for distinctness, but it always is). If you prefer using chains of dot-style method calls to nested indexing operators ([i[j[k]]]), add get and get_mut to the wrapped index generic struct, and pass in the appropriate heap token ref.

The heap token would have indexing functions that use an unsafe block, but it is easy to keep them safe because they borrow from the singleton heap ref (in the same way that implementing indexing on Vec borrows from the self ref to keep the element ref it returns safe). These functions don't do anything except cast the raw pointer to the required ref in an unsafe block - they could be always inlined, and the heap token wouldn't appear in the optimized object code at all.

There. Fixed it :wink:

15

Try it! That may be the best way to learn the limitations you're unaware of, or, come up with something new that works.

16

This is incorrect. The index-based solution won't ever make some unrelated part of the program fail in mysterious ways, for instance. It will also behave deterministically wrt. the sequence of actions performed, and not change behavior when doing things like turning on/off debug logging when you try to figure out what's going wrong.

2 Likes
17

Agreed. I exaggerated. But it is still bad, as in you'd like the compiler to prevent it. And it is a type of badness that wouldn't be there in Rust that used normal references throughout.

18

Also, regarding the rest of your suggestions, the common term for that sort of solution in the Rust world is an “arena.” If you search for that term on crates.io, you’ll find lots of crates that implement something similar with a whole range of different capabilities and tradeoffs.

19

However, areas do not allow you to create self-referential data structures. They almost do, until you try to package up the arena and the objects that use it, together in a struct, which is then a self-referencing struct.

20

Back to that "but it's not as bad as UB" issue. Part of my point with the above "fix" (which may be a type of arena) is that it's much like a normal heap in that derefs can be normal pointer following, but because there is no deallocation and no address-arithmetic, there is no way to deref outside of low-level allocated storage. If all you want from "not UB" is guarantee that the app will deref into storage it allocated (and which is still allocated for it), then you don't need Rust. You just need the lack of deallocation and address arithmetic, added to any language. I could do this just as easily in C++. No borrow or drop checks required.

But, if you want more than "not UB", and you want that to include "when I deref, the object I expect to be there is there", then you can't use a non-singleton vector solution. And, if you use a ref to a token for that singleton, then Rust will give you all the anti-aliasing you expect from normal references.

I will check out the arena crates. If any of them provide a singleton solution like this, then that's what I'll use.

21

I can't tell whether you're trying to say the struct I described won't be self-referential, or something else. What I'm talking about is the following.

Whatever unsafe code is used to implement an arena, and whatever technique it uses for allocation, and whether or not it ever deallocates, I assume it will have a safe API that allocates memory and returns a normal Rust reference (not a raw pointer). If you try to place the arena and something allocated from that arena in a struct together, you then have a self-referential struct in Rust, which is unusable (this is well documented). Here's a playground showing the sort of compiler errors that occur.

There are various crates that work around this problem such as safe_cell and others listed under Related projects at that link. But in general self-referential structs are difficult to use at best, and these crates often have their own safety issues. This is one reason for using indexes rather than references or pointers when creating a self-referencing data structure.

I'm not arguing for or against the idea of having typed identifiers for accessing arenas, slabs, etc, to guard against using the wrong index for the wrong thing. I'm only talking about a problem related to use of memory addresses to create self-referencing data structures, that is specific to Rust.

Storing such token references in the same struct as the arena has this problem I mention, because the token references will have the same lifetime as the arena. So they are no different than ordinary references to memory allocated by the arena, in that regard.