3 ms·

It’s a real issue. Consider (as you say) the Rust compiler. It has an IR phase called MIR, which is a tree, and elements in the tree need to know how to find th

It’s a real issue. Consider (as you say) the Rust compiler. It has an IR phase called MIR, which is a tree, and elements in the tree need to know how to find themselves in the parent. For example, a function has a set of basic blocks, and each BB needs to know about its function. This is a very typical IR; LLVM is the same. Backreferences are hard in Rust, so a BB instead maintains its index into a Vec<BB>, owned by the function. But this index is just a number: ownership is not modeled, it is not statically checked, and it may fall out of sync. It is effectively a slow, weird (though sandboxed) raw pointer. You can write this stuff in Rust, but it is awkward and Rust cannot bring its strengths to bear. Rust assumes a tree-like ownership model and if you fall off that path, it can’t help much. Graphs aren’t trees so Rust is less helpful here.

Sean1708 7y ago
> It is effectively a slow ... raw pointer. In my experience (unless I've misunderstood what you're trying to say) this is the fastest way to write graphs because of how much more cache-friendly it is than having to chase a load of pointers.
- zelly 7y ago
  True, but you can do the same thing more efficiently with pointers. Suppose the parent maintains an array of children Node* Then each child has a Node** member which points to itself in that array. That's one dereference to get up to the parent context. In the Rust example, to do the same would take an extra few steps and probably miss the cache. I think speculative execution would favor the pointer method.
  - vlovich123 7y ago
    Do you have benchmarks? An array offset isn’t speculative and I suspect you’ll have a very hard time showing that vec[i] is slower than *ptr. One challenge is if vec[i] involves a bounds check which it might in native rust.
    - zelly 7y ago
      I stand corrected. The contiguous vector is better and more cache-friendly. #include <chrono> #include <iostream> #include <memory> static constexpr size_t MAX_NODES = 1 << 27; struct Node { size_t index_self; Node** ptr_self = nullptr; }; struct TopLevel { Node** ptr_children; size_t n = 0; explicit TopLevel() : ptr_children(new Node*[MAX_NODES]) {} ~TopLevel() { delete[] ptr_children; } void add(const std::shared_ptr<Node>& descendant) { if (n < MAX_NODES) { ptr_children[n] = descendant.get(); descendant->index_self = n; descendant->ptr_self = &ptr_children[n]; n += 1; } } }; int main(void) { TopLevel top_level{}; for (int i = 0; i < MAX_NODES; ++i) { auto node = std::make_shared<Node>(); top_level.add(node); } // access by pointer { auto t_0 = std::chrono::high_resolution_clock::now(); Node** it = &top_level.ptr_children[0]; for (int i = 0; i < MAX_NODES; ++i) { Node* via = *(*it)->ptr_self; it += 1; } auto t_1 = std::chrono::high_resolution_clock::now(); std::cout << "Via pointer: " << std::chrono::duration_cast<std::chrono::nanoseconds>( t_1 - t_0) .count() << " ns\n"; } // access by index { auto t_0 = std::chrono::high_resolution_clock::now(); Node* it = top_level.ptr_children[0]; auto idx = it->index_self; for (int i = 0; i < MAX_NODES; ++i) { Node* via = top_level.ptr_children[idx]; idx += 1; } auto t_1 = std::chrono::high_resolution_clock::now(); std::cout << "Via index: " << std::chrono::duration_cast<std::chrono::nanoseconds>( t_1 - t_0) .count() << " ns\n"; } return 0; } Results: % clang++ -O3 bench.cc && ./a.out Via pointer: 90 ns Via index: 41 ns

Sean1708 7y ago

> It is effectively a slow ... raw pointer. In my experience (unless I've misunderstood what you're trying to say) this is the fastest way to write graphs because of how much more cache-friendly it is than having to chase a load of pointers.

zelly 7y ago
True, but you can do the same thing more efficiently with pointers. Suppose the parent maintains an array of children Node* Then each child has a Node** member which points to itself in that array. That's one dereference to get up to the parent context. In the Rust example, to do the same would take an extra few steps and probably miss the cache. I think speculative execution would favor the pointer method.
- vlovich123 7y ago
  Do you have benchmarks? An array offset isn’t speculative and I suspect you’ll have a very hard time showing that vec[i] is slower than *ptr. One challenge is if vec[i] involves a bounds check which it might in native rust.
  - zelly 7y ago
    I stand corrected. The contiguous vector is better and more cache-friendly. #include <chrono> #include <iostream> #include <memory> static constexpr size_t MAX_NODES = 1 << 27; struct Node { size_t index_self; Node** ptr_self = nullptr; }; struct TopLevel { Node** ptr_children; size_t n = 0; explicit TopLevel() : ptr_children(new Node*[MAX_NODES]) {} ~TopLevel() { delete[] ptr_children; } void add(const std::shared_ptr<Node>& descendant) { if (n < MAX_NODES) { ptr_children[n] = descendant.get(); descendant->index_self = n; descendant->ptr_self = &ptr_children[n]; n += 1; } } }; int main(void) { TopLevel top_level{}; for (int i = 0; i < MAX_NODES; ++i) { auto node = std::make_shared<Node>(); top_level.add(node); } // access by pointer { auto t_0 = std::chrono::high_resolution_clock::now(); Node** it = &top_level.ptr_children[0]; for (int i = 0; i < MAX_NODES; ++i) { Node* via = *(*it)->ptr_self; it += 1; } auto t_1 = std::chrono::high_resolution_clock::now(); std::cout << "Via pointer: " << std::chrono::duration_cast<std::chrono::nanoseconds>( t_1 - t_0) .count() << " ns\n"; } // access by index { auto t_0 = std::chrono::high_resolution_clock::now(); Node* it = top_level.ptr_children[0]; auto idx = it->index_self; for (int i = 0; i < MAX_NODES; ++i) { Node* via = top_level.ptr_children[idx]; idx += 1; } auto t_1 = std::chrono::high_resolution_clock::now(); std::cout << "Via index: " << std::chrono::duration_cast<std::chrono::nanoseconds>( t_1 - t_0) .count() << " ns\n"; } return 0; } Results: % clang++ -O3 bench.cc && ./a.out Via pointer: 90 ns Via index: 41 ns