4 ms·

> 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 beca

> 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

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