While working on D9141: Volumes: new Volume to Mesh modifier, I noticed that BKE_mesh_calc_edges is significantly slower than openvdb::tools::volumeToMesh. Openvdb only takes ~115ms in my test setup, while computing the edges used to take ~960ms. With the optimization implemented by this patch, computing the edges only takes ~210ms on my hardware.

Parallelizing BKE_mesh_calc_edges is not entirely trivial, because it has to perform deduplication and some other things that have to happen in a certain order. Still, I managed to parallelize all the individual steps, even though the performance does not scale linearly with the number of cores. The speedup is mainly achieved by having multiple hash tables that are filled in parallel. The distribution of edges to hash tables is based on a hash.

This is the mesh I generate in my test file:

I moved the function to C++, because that made it easier for me to optimize it. Furthermore, I added BLI_task.hh which contains some light tbb wrappers.