In our lab, I see this for performance improvements, which is pretty good. I test with a relatively dense dragon model with an animated bend modifier applied.

In D11993#309496, @Sergey Sharybin (sergey) wrote:

Suggest to put this patch on hold, or - we could use this method when there are at least a certain number of loops per thread, since it does give measurable speedup.

@Campbell Barton (campbellbarton), you mention that vertex accumulation now runs in parallel. Is is something what can be done in the current code top improve performance?

Not trivially, since we have an array of data to accumulate in destination indices.

Some options I've considered:

• Having access to a vertex -> loop map (what D11906 does).
  
  Note that BMesh is already doing this since no data generation is needed.
  
  This is only worthwhile if the map can be reused many times as generating it would likely be single threaded (multi-threading runs into a similar problem we've running into here).
• Accumulating into TLS arrays would work, but the memory for each thread and cost merging the data back with many threads makes it impractical.
• It's also possible to accumulate vector additions into a granular data structure in TLS, bucketing to ensure thread safety when they're written back.
  
  Mentioning for completeness as the overhead makes it impractical AFAICS.
• Locking the vector addition (what this patch does).

In D11993#309224, @Bastien Montagne (mont29) wrote:

But we could also try an alternative solution: each task loops over the full set of faces, with a predefined, 'private' range of vertex indices, and only contribute to normal computing for loops that match 'their' vertices.

This would require always computing poly normals first in their own parallelized loop, and then in a second one we'd accumulate normals in vnors and normalize them in a single step.

I would expect looping over faces/loops that need no processing (since out of our own vertex indices range) to be extremely fast (it's essentially a few integers increments and comparisons), compared to actual weighted normals computing. And that way we avoid any need for locking/atomics/TLS? That solution should also be fully scalable both regarding mesh size, and threads count. Added benefit could be that those tasks being much bigger (each would loop over all polys, then all of their own 'private' vnors for final normalization and conversion to short), the threading overhead would be much less noticeable.

@Campbell Barton (campbellbarton) what do you think of that idea? Only thing am unsure about it (without trying it in real) is the overhead of looping over all faces/loops, even if each task does nothing for most of them?

Another idea could be to generate virtual islands of the mesh (groups of faces/vertices fully isolated, with no possible concurrent access), and then process all the boundary data in a single task. But that would be fairly complex I recon, and preparing those islands would likely add a significant overhead too.

@Bastien Montagne (mont29) it could be worth testing.

Some issues could be:

• It gets less efficient as more threads are added (if you have many loops at once over all polygons, each loop has overhead even if it's reasonably small it could add up).
• Some duplicate work calculating normals of multiple polygons (unless polygon normals are stored for reuse).
• Some duplicate work calculating adjacent normalized edge vectors that currently get reused while walking around the polygon.
• Efficiently calculating next/previous normalized edge vectors in cases were loops might not be used could get messy.
• Some threads may take longer than others, where idle threads are left waiting for others to finish. This might be one of the biggest down-sides, as the size of meshes increases the chance that one thread takes longer than others increases too. Are there ways to avoid this problem?

@Bastien Montagne (mont29) @Campbell Barton (campbellbarton) do you have a pointer to a model and workflow where I can profile the "low" point here? Maybe I can help sussing out why 128K faces is a local maximum.

Last week I tried some alternative optimizations, these have been listed in the main task for completeness since for the most-part the results aren't promising.

One change tested resulted in a very minor speedup over the current method by storing the loop weights instead of scaled polygon-normal's (listed in the main task as Store Loop Weights Instead of Vectors).

Since the difference is so small, I'd rather not make this change for now.

Before jumping to conclusions about the current timing, I'd like to check how other systems perform.

Am still fairly hesitant regarding adding back atomics here... But yes, performances as reported here seem fine, maybe CPU architectures have become much better at dealing with extra cost of atomics? What was exactly the CPU used for those tests btw?

In any case, I'd like to see one more testcase checked about this patch: what happens with a lot of relatively small meshes (say, 1k objects made of 1k vertices) ? As far as I understand you only tried with 16 objects, and it essentially made both old and new code overall almost as fast?

• These tests ran on a AMD Ryzen Threadripper 3970X 32-Core Processor (using 64 threads).
• Testing many 1k objects is these will only get one thread as min_iter_per_thread is set to 1024. I think it's reasonable to use production files that include many small objects as a test case, since a large number of exactly 1k poly objects is an artificial test case that could give unrealistically skewed results.

If the aim is to generate a mesh with the greatest lock contention, that'd be a single mesh with (number-of-system-threads * min_iter_per_thread vertices), if you have many of these objects, the lock contention will reduce since the threads will be working on different object.

In the generated graphs that'd be a single 64k mesh having the most locking, if that were the case a 400k mesh should have ~1/6th the locking contention (roughly).

Further, swapping out the locking and non-locking versions of these functions hardly made a difference, although if you're concerned about this it might be worth generating a graph that doesn't use locking, to see if there is a situation that happens to be running in to lock contention.

Another useful test would be to benchmark a complex production file, compare the frame-rate with/without locking.

Edit: tested some files from sprite-fight with/without locking and I couldn't notice any difference from the FPS.

Here is a quick test on two sprites production scenes, every time just Load + 10 frames update, for BKE_mesh_normals_loop_split performances.

Ran on an AMD Ryzen 7 3800X 8-Core, 16 threads.

This is of course fairly limited test, but this patch seems to be either neutral, or beneficial (although normals evaluation as a whole represents less than 0.1% of a frame evaluation time in those scenes anyway).

To be clear, I am not worried about potential locking (concurrency issues between threads) here. I am worried about the extra cost induced by an atomic operation, regardless of whether there are actually collisions or not.

Atomics used to induce a fairly high overhead (due to cache coherency constraints), that was strongly reducing the benefits of threading on light tasks as those normals computing, especially with very high number of threads. That's why they were removed in rBd130c66db436 four years ago.

From all that testing, it would appear that this might be much less of an issue with modern processors? Would be interesting to check on a recent Intel architecture though.

In D11993#315758, @Bastien Montagne (mont29) wrote:

To be clear, I am not worried about potential locking (concurrency issues between threads) here. I am worried about the extra cost induced by an atomic operation, regardless of whether there are actually collisions or not.

Atomics used to induce a fairly high overhead (due to cache coherency constraints), that was strongly reducing the benefits of threading on light tasks as those normals computing, especially with very high number of threads. That's why they were removed in rBd130c66db436 four years ago.

From all that testing, it would appear that this might be much less of an issue with modern processors? Would be interesting to check on a recent Intel architecture though.

I tested this change with the dragon scene on the Xeon in our lab and saw an improvement of 8.7% in playback performance.