Diffing_Engine: profiling

[alelom]

Create profiling tests and record results.

I will edit this post with added tests.

ProfilingTest_01 - bars only

Test file: https://github.com/BHoM/BHoM_Engine/blob/Diffing_Engine-initialImplementation/Engine_Test/Diffing_Engine/Profiling01.cs

Execution time

Here I'm testing BH.oM.Structure.Bars only.

Collection-level diffing only:

• From 10 to 20000 elements the algorithm seems to have an efficiency of O(n log n).
• Numbers larger than 20000 the efficiency drops: haven't let it run yet but I fear much more than that.

Collection AND Property-level diffing :

• Efficiency much lower, close to n² for relatively small numbers (5000).

Cpu profile

• A big, probably unnecessary performance hit is caused by how we are forced to retrieve a specific fragment:
  
  This might be food for thought on how we implemented the Fragments.

• However, the largest percentage is lost in the following section, which I can definitely improve
  

Conclusions

• There is definitely room for improvement. I can rewrite code to make it more efficient, for now I only wanted to finish the prototype.
• What if I used CustomData instead of Fragment to save the hashes? Just getting the right fragment has a certain cost.

Other profiling tests

Other tests are needed to account for different cases:

• types of elements: elements with a deep/complex/heavy class structure (Panels? Meshes?)
• variety of elements: mixed types
• others to be defined

[alelom]

Update

(branch Diffing_Engine-toBeMergedForAlpha)

After removing the call to GetHashFragment() and having improved the lookup by using dictionaries with the hash and the objects instead, the performance has improved.

The inefficient section above is now replaced by a more efficient search in the dictionaries by hash.

Execution time

Execution time for Collection-level diffing only is now practically zero.

Execution time for Property-level diffing is same as before, the bottleneck being the Kellerman Library in BH.Engine.Testing.DifferentProperties which should be efficient anyway.

Cpu profile

The processor bottleneck now is (as it should) the "property level diffing", that is implemented through the Kellerman Library in BH.Engine.Testing.DifferentProperties:

The picture shows the result for 1000 elements compared by property.

For 100 elements, DifferentProperties() was closer to 80%, with the other 20% occupied by the "collection-level diffing".

This demonstrates that the more elements, the more the computation is taken by the "property-level diffing", as expected.

[alelom]

After #1248

[alelom]

New profiling results after df3d1c9

I am now logging also the time it takes to compute the hashes.

The latest change introduces the main difference that the hash computing takes significantly longer and becomes the main resource hog for smaller collections. This is due to the correction that had to be done for #1639.

Regarding the diffing only:

• Only collection-level: no difference
• Property-level:
  • up to 1000 objects: comparable results.
  • above 1000 objects result differ significantly, quite slower. However, the bigger the model, the less probability there is that a large quantity of objects is modified. So next profiling should take this into account and reduce the percentage of objects modified as the total number grows.

The last 5000 objects profiling did not complete (I stopped it). The one just before took about 2,5h to complete.

[alelom]

With #1952, performance is about x100 better, especially on large collections.

[alelom]

Measuring performance after changes in #2105. Only slightly slower, same order of magnitude.

[alelom]

Testing on main at 42bccae, I noticed a significant difference (~2x slower). No changes were made to the Hash() function since previous profiling, or to anything that relates to diffing. Could it be the switch to .NETStandard?

[alelom]

Profiling at 6b7f790 (under WIP #2647) shows results that are in line with the previous diffing. Slightly faster on smaller numbers, slightly slower on larger numbers.