Memory usage

[wtholliday]

Starting a thread here about my memory usage explorations. Currently my app gets killed often by iOS for using too much memory during a boolean. Here's what a graph looks like for a successful boolean:

So high-water-mark memory usage is ~3x steady state during the boolean.

Biggest single allocation (1.18 gb):

[wtholliday]

So SparseIndices is a (sorted) array of pairs of indices: {p1: q1, p2: q2, ...}

Are the p's unique? I'm guessing not, since it uses stable_sort. If this were my own code (i.e. free of library-user constraints) I'd blast that sucker with a GPU radix sort 🔫 haha

With unique keys, some sort of trie would be great at storing a sparse index mapping, provided there is some clustering.

[wtholliday]

What are shadow functions?

I looked inside SparseIndices returned by Collider::Collisions and the ps are not unique. So I don't see how one can make the memory usage for SparseIndices asymptotically better, and what you're saying about getting rid of SparseIndices altogether makes sense, even if I don't really understand the details.

[pca006132]

Those shadow functions are collision checks, but in 2D projections. The problem we got here is that our collider is not giving precise collision pairs, instead what we got is just bounding box intersections. Many of those collision pairs are not real collisions and can be removed.

I'm thinking if we need all 3 halfedges in p1q1 though, because we know that if the first halfedge is included, the other two will follow. If we can change it to include only 1 halfedge, we may reduce the memory usage of boolean3 a bit without too much changes?

[wtholliday]

Those shadow functions are collision checks, but in 2D projections.

Do you mean it's projecting bounding boxes into some plane and then returning all the collisions?

[elalish]

Yeah, but I think I'm probably the only one in a position to attack that particular refactor. I'd like to get to it once we get v3.0 out. If you'd like to have a look at GLM in the meanwhile, that would probably be a great place to help.

[wtholliday]

Yeah I wasn't going to attempt that refactor. Was just hoping I could figure out some decent improvement to SparseIndices.

What if you had an array indexed by the ps of head indices of singly linked lists? Put a bunch of the q's in each list node. Similar to a hash table.

I'll take a look at the GLM stuff :)

[wtholliday]

FWIW SparseIndices::Copy doesn't seem like something that would benefit from parallelization within the for_each (too little calculation per job and it's just going to be memory bandwidth limited)

manifold/src/utilities/include/manifold/sparse.h

Line 72 in 31d6da0

for_each(autoPolicy(out.size()), countAt(0_uz), countAt(out.size()),

[pca006132]

Yes, it probably doesn't benefit much from parallelization here. In general, I think copy operations will not benefit much from parallelization... but probably need more profiling for this on different machines.

[pca006132]

Btw, you can try to run https://github.com/elalish/manifold/blob/master/extras/stl_test.cpp to see what algorithms are not having improvement with parallelization on your target device. Even copy can have some improvement when run in multiple threads, just that it may not be significant to warrant the additional CPU usage...