4 ms·
I stand corrected. The contiguous vector is better and more cache-friendly. #include <chrono> #include <iostream> #include <memory> static constexpr
by 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