Open GeLee-Q opened 2 years ago
# ubuntu20.04 # linux 内核: 5.13.0-48-generic # gcc 11.0
/sparse_data_struct/00.cpp: In instantiation of ‘static void RootGrid<T, Layout>::_write(Node&, int, int, T) [with Node = const HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > >; T = char; Layout = HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > >]’: /sparse_data_struct/00.cpp:158:22: required from ‘void RootGrid<T, Layout>::write(int, int, T) const [with T = char; Layout = HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > >]’ /sparse_data_struct/00.cpp:197:17: required from here /sparse_data_struct/00.cpp:152:37: 错误: passing ‘const HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > >’ as ‘this’ argument discards qualifiers [-fpermissive] 152 | auto *child = node.touch(x >> node.bitShift, y >> node.bitShift); | ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /sparse_data_struct/00.cpp:87:11: 附注: 在调用‘Node* HashBlock<Node>::touch(int, int) [with Node = PointerBlock<11, DenseBlock<8, PlaceData<char> > >]’时 87 | Node *touch(int x, int y) { | ^~~~~ /sparse_data_struct/00.cpp: In instantiation of ‘void DenseBlock<Bshift, Node>::foreach(const Func&) [with Func = RootGrid<char, HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > > >::_foreach<DenseBlock<8, PlaceData<char> >, main()::<lambda(int, int, char&)> >(DenseBlock<8, PlaceData<char> >&, int, int, const main()::<lambda(int, int, char&)>&)::<lambda(int, int, auto:1*)>; int Bshift = 8; Node = PlaceData<char>]’: /sparse_data_struct/00.cpp:170:32: required from ‘static void RootGrid<T, Layout>::_foreach(Node&, int, int, const Func&) [with Node = DenseBlock<8, PlaceData<char> >; Func = main()::<lambda(int, int, char&)>; T = char; Layout = HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > >]’ /sparse_data_struct/00.cpp:171:25: required from ‘RootGrid<char, HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > > >::_foreach<PointerBlock<11, DenseBlock<8, PlaceData<char> > >, main()::<lambda(int, int, char&)> >(PointerBlock<11, DenseBlock<8, PlaceData<char> > >&, int, int, const main()::<lambda(int, int, char&)>&)::<lambda(int, int, auto:1*)> [with auto:1 = DenseBlock<8, PlaceData<char> >]’ /sparse_data_struct/00.cpp:60:25: required from ‘void PointerBlock<Bshift, Node>::foreach(const Func&) [with Func = RootGrid<char, HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > > >::_foreach<PointerBlock<11, DenseBlock<8, PlaceData<char> > >, main()::<lambda(int, int, char&)> >(PointerBlock<11, DenseBlock<8, PlaceData<char> > >&, int, int, const main()::<lambda(int, int, char&)>&)::<lambda(int, int, auto:1*)>; int Bshift = 11; Node = DenseBlock<8, PlaceData<char> >]’ /sparse_data_struct/00.cpp:170:32: required from ‘static void RootGrid<T, Layout>::_foreach(Node&, int, int, const Func&) [with Node = PointerBlock<11, DenseBlock<8, PlaceData<char> > >; Func = main()::<lambda(int, int, char&)>; T = char; Layout = HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > >]’ /sparse_data_struct/00.cpp:171:25: required from ‘RootGrid<char, HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > > >::_foreach<HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > >, main()::<lambda(int, int, char&)> >(HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > >&, int, int, const main()::<lambda(int, int, char&)>&)::<lambda(int, int, auto:1*)> [with auto:1 = PointerBlock<11, DenseBlock<8, PlaceData<char> > >]’ /sparse_data_struct/00.cpp:102:17: required from ‘void HashBlock<Node>::foreach(const Func&) [with Func = RootGrid<char, HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > > >::_foreach<HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > >, main()::<lambda(int, int, char&)> >(HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > >&, int, int, const main()::<lambda(int, int, char&)>&)::<lambda(int, int, auto:1*)>; Node = PointerBlock<11, DenseBlock<8, PlaceData<char> > >]’ /sparse_data_struct/00.cpp:170:32: required from ‘static void RootGrid<T, Layout>::_foreach(Node&, int, int, const Func&) [with Node = HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > >; Func = main()::<lambda(int, int, char&)>; T = char; Layout = HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > >]’ /sparse_data_struct/00.cpp:178:17: required from ‘void RootGrid<T, Layout>::foreach(const Func&) [with Func = main()::<lambda(int, int, char&)>; T = char; Layout = HashBlock<PointerBlock<11, DenseBlock<8, PlaceData<char> > > >]’ /sparse_data_struct/00.cpp:201:15: required from here /sparse_data_struct/00.cpp:27:28: 错误: no match for ‘operator*’ (operand type is ‘PlaceData<char>’) 27 | func(x, y, *m_data[x][y]); |
修改后 DenseBlock & HashBlock后可以编译跑通:
template <int Bshift, class Node> struct DenseBlock { static constexpr bool isPlace = false; static constexpr bool bitShift = Bshift; static constexpr int B = 1 << Bshift; static constexpr int Bmask = B - 1; Node m_data[B][B]; Node *fetch(int x, int y) const { return &m_data[x & Bmask][y & Bmask]; } Node *touch(int x, int y) { return &m_data[x & Bmask][y & Bmask]; } // change_00 : * -> & template <class Func> void foreach(Func const &func) { for (int x = 0; x < B; x++) { for (int y = 0; y < B; y++) { func(x, y, &m_data[x][y]); } } } };
template <class Node> struct HashBlock { static constexpr bool isPlace = false; static constexpr bool bitShift = 0; struct MyHash { std::size_t operator()(std::tuple<int, int> const &key) const { auto const &[x, y] = key; return (x * 2718281828) ^ (y * 3141592653); } }; //change_01 <Node> -> std::unique_ptr<Node> std::unordered_map<std::tuple<int, int>, std::unique_ptr<Node>, MyHash> m_data; // change_02 : it->second.get(); Node *fetch(int x, int y) const { auto it = m_data.find(std::make_tuple(x, y)); if (it == m_data.end()) return nullptr; return it->second.get(); } Node *touch(int x, int y) { auto it = m_data.find(std::make_tuple(x, y)); if (it == m_data.end()) { std::unique_ptr<Node> ptr = std::make_unique<Node>(); auto rawptr = ptr.get(); m_data.emplace(std::make_tuple(x, y), std::move(ptr)); return rawptr; } return it->second.get(); } //change_03 &block -> unique_node.get() (unique_Node = block) template <class Func> void foreach(Func const &func) { for (auto &[key, unique_Node]: m_data) { auto &[x, y] = key; func(x, y, unique_Node.get()); } } };
在运行时遇到内存不断增加的状况。 当N 为(2 * 2) 时,使用valgrind 和 massif-visualizer 查看内存,构造的空间足足有96M, 可能是代码改错了,还请小彭老师看看。
为了方便在我自己平台的跑起来,将main中的foreach改成了和之前的代码一样。
int count = 0; a->foreach([&] (int x, int y, char &value) { if (value != 0) { count++; } }); printf("count: %d\n", count);
结果:运行内存64g全部跑满,最后core dump。
这个可视化的图是在代码运行占到内存一半的时候,ctrl + c 后得到的信息图。
count: 109 main: 14.5131s
内存可视化信息如下:
最后想问一下小彭老师,这个代码没有给错吗,为什么会不停的申请内存导致最后完全不够用呢。
实验环境:
Q1 :10/03/01.cpp 编译出错
修改后 DenseBlock & HashBlock后可以编译跑通:
在运行时遇到内存不断增加的状况。 当N 为(2 * 2) 时,使用valgrind 和 massif-visualizer 查看内存,构造的空间足足有96M, 可能是代码改错了,还请小彭老师看看。
Q2 10/04/06.cpp 运行时内存爆炸
为了方便在我自己平台的跑起来,将main中的foreach改成了和之前的代码一样。
情况 1 : N(512 * 512)
结果:运行内存64g全部跑满,最后core dump。
这个可视化的图是在代码运行占到内存一半的时候,ctrl + c 后得到的信息图。![R}}X)1RI0EU$H{K5OJRDAOX](https://user-images.githubusercontent.com/22428217/173063166-d8bf2745-bbe3-4ef1-8ef1-6fe4b70ebbab.png)
情况 2 : N(32 * 32 )
内存可视化信息如下:![2U3TY{BVCZZ8W@V1_V)_KAY](https://user-images.githubusercontent.com/22428217/173063202-9f3f9318-d810-4377-bd7d-e04902a8c0bc.png)
最后想问一下小彭老师,这个代码没有给错吗,为什么会不停的申请内存导致最后完全不够用呢。