关于第十课---多层嵌套稀疏数据结构代码---BUG

Start by reproducing the compilation failures in 10/03/01.cpp with the stated Ubuntu, GCC, and kernel environment, then run 10/04/06.cpp for the reported matrix sizes. Inspect the DenseBlock and HashBlock changes and use Valgrind or massif-visualizer to identify the source of memory growth. Done means the examples compile, complete without exhausting memory, and their counts and memory usage are explained or corrected.

实验环境：

# ubuntu20.04
# linux 内核: 5.13.0-48-generic
# gcc 11.0

Q1 ：10/03/01.cpp 编译出错

/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， 可能是代码改错了，还请小彭老师看看。

Q2 10/04/06.cpp 运行时内存爆炸

为了方便在我自己平台的跑起来，将main中的foreach改成了和之前的代码一样。

	int count = 0;
    a->foreach([&] (int x, int y, char &value) {
        if (value != 0) {
            count++;
        }
    });
    printf("count: %d\n", count);

情况 1 ： N（512 * 512）

结果：运行内存64g全部跑满，最后core dump。

这个可视化的图是在代码运行占到内存一半的时候，ctrl + c 后得到的信息图。

情况 2 ： N（32 * 32 )

count: 109
main: 14.5131s

内存可视化信息如下:

最后想问一下小彭老师，这个代码没有给错吗，为什么会不停的申请内存导致最后完全不够用呢。