Manifold::cleanup() is very slow

[cakarsubasi]

I wrote a short benchmark function to test out the changes in build_manifold as follows:

HMesh::Manifold create_huge_manifold()
{
    std::vector<size_t> faces;
    std::vector<CGLA::Vec3d> vertices;
    constexpr auto x_size = 1'000UL;
    constexpr auto y_size = 1'000UL;
    faces.reserve((x_size - 1) * (y_size -1) * 4);
    vertices.reserve(x_size * y_size);

    for (size_t i = 0; i < y_size; ++i) {
        for (size_t j = 0; j < x_size; ++j) {
            auto x = 10.0 * static_cast<double>(j) / static_cast<double>(x_size);
            auto y = 10.0 * static_cast<double>(i) / static_cast<double>(y_size);
            vertices.emplace_back(x, y, 0.0);
        }
    }
    for (size_t i = 0; i < y_size - 1; ++i) {
        for (size_t j = 0; j < x_size - 1; ++j) {
            auto top_left = i * y_size + j;
            auto top_right = top_left + 1;
            auto bottom_left = top_left + x_size;
            auto bottom_right = bottom_left + 1;
            faces.emplace_back(top_left);
            faces.emplace_back(top_right);
            faces.emplace_back(bottom_right);
            faces.emplace_back(bottom_left);
        }
    }

    HMesh::Manifold m;
    HMesh::build_manifold(m, vertices, faces, 4);

    return m;
}

The flamegraph for this is as follows:

Over 90% of the runtime is spent on cleanup, mostly to sort the maps in the IDRemap struct. Switching the internals to unordered_map sped up the function by quite a bit, but I can still fill up my 20GB memory+swap space with only about 4 million vertices which triggers the OOM killer.

Now, obviously build_manifold most likely won't be called with such detailed meshes since every operation ends up taking ages, but if cleanup is meant to compact memory usage, it is currently not doing that.

[janba]

Wow. Worse than expected.

I guess even the unordered_map could be replaced by an array, but I cannot think of a way to avoid the spike in memory usage.

Hmmm. I guess if you find all references to a given vertex and replace them all at once instead of creating a map. Definitely worth looking into.

The price to pay is that there is then no map for remapping the attribute vectors. Still there could be a faster path with little mem overhead when attribute vectors don't matter.

[janba]

I thought more about this. For now just switching to an unordered map is best since the right solution is both more involved and could easily lead to breaking changes.

I was about to implement that, but it sounds like you already did and tested the result. If so, a PR would be appreciated.

[cakarsubasi]

Yes, I will handle this tomorrow.