3 ms·
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 i
by 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 agoI 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