The Rust question to ask here is: Do you really need pointers, specifically? Or would some other reference mechanism work? You could put all of your graph nodes into a linear data structure like an array, and have them point to each other by holding a list of indices instead of a list of pointers. Or you could give all of your nodes unique keys and keep them in a table, and have them hold references to each other by key. The compiler will not try to prove the correctness of your graph algorithm, and in the event of programmer error that leads to dangling references your program will have to handle the scenario of following an index or a key and not finding a value, so bugs will not introduce memory unsafety.
There's also ongoing work on memory arenas in the nightly compiler, and I believe some libraries. Putting a graph into an arena is a good way to appease the compiler, because the entire arena will be freed at the same time, ensuring that hanging pointers will never exist between graph nodes.
Rust practitioners keep proposing this solution. It is like you have never heard of caches or do not understand that modern CPUs have multiple special prefetchers for pointer chasing and no prefetchers for "rust fanatics"
This solution will be SIGNIFICANTLY slower on any modern CPU. By a wide margin! Since you'll keep having to wait for main memory as the cache prefetchers have no idea about this insane scheme and will not prefetch the data for you. They will for actual pointers.
But isn’t that part of the point of putting nodes into an array? So the nodes are guaranteed to sit next to each other in memory, and so are quite likely to be in cache?
> do not understand that modern CPUs have multiple special prefetchers for pointer chasing and no prefetchers for "rust fanatics"
Doesn’t array indexing reduce down to pointer chasing anyways? Or are you saying that the prefetchers can’t see through “nested” array accesses (e.g. nodes[nodes[i].out[0]].data vs node.out[0].data)?
I'm not an expert and would know more. Can you point out on any benchmark demonstrating those claim? Would love to see the actual number.
Certainly this is more awkward to write than pointer linking, but approximately the same performance should be achievable for sparse or treelike graphs. If you need to work with dense graphs larger than the size of the cache performance will suffer a lot, but this meets the criteria to justify using unsafe, at which point the implementation would look a lot like a C implementation.
You can get around it with Interior Mutability, it's just slightly more verbose.
Also, it isn't really that they made an easy thing hard. Properly maintaining the invariants with cyclical references is hard and unsafe. Rust exposes that difficulty in a very literal way
Half of subj code uses sort of atomics (mem-replace), but they are too small to not leak complexity to “userland”. If they just replaced that with
transaction {
...shuffle values...
}
>Properly maintaining the invariants with cyclical references is hard and unsafe. Rust exposes that difficulty in a very literal way
But a solution to this problem is articulated easily: adjust corresponding nodes if this one goes away. It could help with that instead of just exposing, like tagging such types as heavily linked and demand/derive an [unoptimal] algorithm that would ensure correctness or define “corresponding” and “adjust” at least.
ps. I’m not familiar with rust, nor with discussions on it, maybe that was already discussed and refused or proven unreasonable at early design stages.
> But a solution to this problem is articulated easily: adjust corresponding nodes if this one goes away. It could help with that instead of just exposing,
Articulating things easily doesn't mean they are easy. Now every value needs a backreference to every value that holds it and, during its destructor (which isn't guaranteed to run), it has to make those held references invalid?
I know just enough to know how difficult the problem is, in the general case. The folks thinking about these problems for their day jobs have looked into a lot of simple solutions and they fall apart in cases that are too common or too valuable to no support.
>Now every value needs a backreference to every value that holds it
If it didn’t, wouldn’t that be out of scope of graph/dl-list discussion?
It is interesting that solutions fall apart, because it seems like a warehouse-level problem to me. Any code path is just +1 -1 countable references with some matching-branching in the end. Are these design discussions archived somewhere, like a mailing list / technical rationale talks?
ps. I did not mean anything like “rust magically freeing graphs”. Only that “transaction {shuffle} check” thing. Like in physics, N spin in, N spin out, what’s where is not important, since nothing lost.
So, the usual answer is "use unsafe code." What could possibly go wrong?