File indexing completed on 2024-07-14 15:54:53

0001 /*
0002     SPDX-FileCopyrightText: 2020 Milian Wolff <mail@milianw.de>
0003 
0004     SPDX-License-Identifier: LGPL-2.1-or-later
0005 */
0006 
0007 #include <algorithm>
0008 #include <array>
0009 #include <cstdint>
0010 #include <iostream>
0011 #include <list>
0012 #include <random>
0013 #include <vector>
0014 
0015 #include <QVector>
0016 
0017 #include <boost/container/pmr/monotonic_buffer_resource.hpp>
0018 #include <boost/container/pmr/polymorphic_allocator.hpp>
0019 #include <boost/container/pmr/slist.hpp>
0020 #include <boost/container/slist.hpp>
0021 
0022 #include "../../src/analyze/allocationdata.h"
0023 
0024 constexpr uint64_t MAX_TREE_DEPTH = 64;
0025 constexpr uint64_t NO_BRANCH_DEPTH = 4;
0026 constexpr uint64_t BRANCH_WIDTH = 8;
0027 constexpr uint64_t NUM_TRACES = 1000000;
0028 
0029 using Trace = std::array<uint64_t, MAX_TREE_DEPTH>;
0030 
0031 uint64_t generateIp(uint64_t level)
0032 {
0033     if (level % NO_BRANCH_DEPTH) {
0034         return level;
0035     }
0036     static std::mt19937_64 engine(0);
0037     static std::uniform_int_distribution<uint64_t> dist(0, BRANCH_WIDTH - 1);
0038     return dist(engine);
0039 }
0040 
0041 Trace generateTrace()
0042 {
0043     Trace trace;
0044     for (uint64_t i = 0; i < MAX_TREE_DEPTH; ++i) {
0045         trace[i] = generateIp(i);
0046     }
0047     return trace;
0048 }
0049 
0050 std::vector<Trace> generateTraces()
0051 {
0052     std::vector<Trace> traces(NUM_TRACES);
0053     std::generate(traces.begin(), traces.end(), generateTrace);
0054     return traces;
0055 }
0056 
0057 namespace Tree {
0058 template <template <typename...> class Container>
0059 struct Node
0060 {
0061     AllocationData cost;
0062     uint64_t ip = 0;
0063     const Node* parent = nullptr;
0064     Container<Node> children;
0065 };
0066 
0067 template <template <typename...> class Container>
0068 void setParentsImpl(Container<Node<Container>>& nodes, const Node<Container>* parent)
0069 {
0070     for (auto& node : nodes) {
0071         node.parent = parent;
0072         setParentsImpl(node.children, &node);
0073     }
0074 }
0075 
0076 void setParents(QVector<Node<QVector>>& nodes, const Node<QVector>* parent)
0077 {
0078     setParentsImpl(nodes, parent);
0079 }
0080 
0081 void setParents(std::vector<Node<std::vector>>& nodes, const Node<std::vector>* parent)
0082 {
0083     setParentsImpl(nodes, parent);
0084 }
0085 
0086 void setParents(std::list<Node<std::list>>&, const Node<std::list>*)
0087 {
0088     // nothing to do
0089 }
0090 
0091 void setParents(boost::container::slist<Node<boost::container::slist>>&, const Node<boost::container::slist>*)
0092 {
0093     // nothing to do
0094 }
0095 
0096 void setParents(boost::container::pmr::slist<Node<boost::container::pmr::slist>>&,
0097                 const Node<boost::container::pmr::slist>*)
0098 {
0099     // nothing to do
0100 }
0101 
0102 template <template <typename...> class Container, typename... Allocator>
0103 Container<Node<Container>> buildTree(const std::vector<Trace>& traces, const Allocator&... allocator)
0104 {
0105     auto findNode = [&](Container<Node<Container>>* nodes, uint64_t ip, const Node<Container>* parent) {
0106         auto it =
0107             std::find_if(nodes->begin(), nodes->end(), [ip](const Node<Container>& node) { return node.ip == ip; });
0108         if (it != nodes->end())
0109             return it;
0110         return nodes->insert(it, Node<Container> {{}, ip, parent, Container<Node<Container>> {allocator...}});
0111     };
0112 
0113     Container<Node<Container>> ret(allocator...);
0114     const Node<Container>* parent = nullptr;
0115     for (const auto& trace : traces) {
0116         auto* nodes = &ret;
0117         for (const auto& ip : trace) {
0118             auto it = findNode(nodes, ip, parent);
0119             it->cost.allocations++;
0120             nodes = &it->children;
0121             parent = &(*it);
0122         }
0123     }
0124 
0125     setParents(ret, nullptr);
0126 
0127     return ret;
0128 }
0129 
0130 template <template <typename...> class Container>
0131 uint64_t numNodes(const Node<Container>& node)
0132 {
0133     return std::accumulate(node.children.begin(), node.children.end(), uint64_t(1),
0134                            [](uint64_t count, const Node<Container>& node) { return count + numNodes(node); });
0135 }
0136 
0137 template <template <typename...> class Container>
0138 uint64_t numNodes(const Container<Node<Container>>& tree)
0139 {
0140     return std::accumulate(tree.begin(), tree.end(), uint64_t(0),
0141                            [](uint64_t count, const Node<Container>& node) { return count + numNodes(node); });
0142 }
0143 
0144 template <template <typename...> class Container>
0145 std::pair<uint64_t, uint64_t> run(const std::vector<Trace>& traces)
0146 {
0147     const auto tree = buildTree<Container>(traces);
0148     return {tree.size(), numNodes(tree)};
0149 }
0150 
0151 template <>
0152 std::pair<uint64_t, uint64_t> run<boost::container::pmr::slist>(const std::vector<Trace>& traces)
0153 {
0154     boost::container::pmr::monotonic_buffer_resource mbr;
0155     const auto tree = buildTree<boost::container::pmr::slist>(traces, &mbr);
0156     return {tree.size(), numNodes<boost::container::pmr::slist>(tree)};
0157 }
0158 }
0159 
0160 enum class Tag
0161 {
0162     QVector,
0163     StdVector,
0164     StdList,
0165     BoostSlist,
0166     BoostPmrSlist,
0167 };
0168 
0169 std::pair<uint64_t, uint64_t> run(const std::vector<Trace>& traces, Tag tag)
0170 {
0171     switch (tag) {
0172     case Tag::QVector:
0173         return Tree::run<QVector>(traces);
0174     case Tag::StdVector:
0175         return Tree::run<std::vector>(traces);
0176     case Tag::StdList:
0177         return Tree::run<std::list>(traces);
0178     case Tag::BoostSlist:
0179         return Tree::run<boost::container::slist>(traces);
0180     case Tag::BoostPmrSlist:
0181         return Tree::run<boost::container::pmr::slist>(traces);
0182     }
0183     Q_UNREACHABLE();
0184 }
0185 
0186 int main(int argc, char** argv)
0187 {
0188     if (argc != 2) {
0189         std::cerr << "usage: bench_tree [QVector|std::vector|std::list|boost::slist|boost::pmr::slist]\n";
0190         return 1;
0191     }
0192 
0193     const auto tag = [&]() {
0194         auto t = std::string(argv[1]);
0195         if (t == "QVector")
0196             return Tag::QVector;
0197         if (t == "std::vector")
0198             return Tag::StdVector;
0199         if (t == "std::list")
0200             return Tag::StdList;
0201         if (t == "boost::slist")
0202             return Tag::BoostSlist;
0203         if (t == "boost::pmr::slist")
0204             return Tag::BoostPmrSlist;
0205         std::cerr << "unhandled tag: " << t << "\n";
0206         exit(1);
0207     }();
0208 
0209     const auto traces = generateTraces();
0210     const auto result = run(traces, tag);
0211     std::cout << result.first << ", " << result.second << std::endl;
0212     return 0;
0213 }