perf: remove unnecessary extra child traversal in collectDirtyChildren

[shlusiak]

Please see https://github.com/parse-community/Parse-SDK-Android/issues/1006#issuecomment-682448919 for the analysis of this.

The collectDirtyChildren forgets seen siblings when traversing, which causes extra traversals if those siblings point to the same objects and causes lots of garbage to be created in memory. It also has the potential of adding the same dirty object twice to the dirtyChildren collection, which may or may not be a set.

Removing the copy of the seen set may improve performance significantly.

Should hopefully massively improve the situations described in issues #1006, #1007, possibly #888 and #993 .

[shlusiak]

The function in question actually has a few more issues:

• It uses a HashSet for seen, which means that the object's equals() and hashCode() functions will be used. So if two different ParseObjects implement equals over a set of attributes other than the objectId, this code will wrongly detect a cycle. Note that the ParseTraverser uses a IdentityHashMap.
• Whenever a ParseObject is visited, recursion is used to traverse this object. However, by calling collectDirtyChildren, a new ParseTraverser is instantiated with the current object as the root, which then of course has forgotten all of the previously visited objects and traverse them all again. This is obviously bad, I can't see how this would cause an infinite loop, but it is for sure exploding the algorithm to a point where it may never finish.

[mtrezza]

@shlusiak Thanks for your PR and apologies for the late reply, we are finally looking to close all PRs. Could you merge master into this and resolve any conflicts?

[codecov[bot]]

Codecov Report

Merging #1058 (665b6d0) into master (7cff2ae) will increase coverage by 0.02%. The diff coverage is 0.00%.

@@             Coverage Diff              @@
##             master    #1058      +/-   ##
============================================
+ Coverage     65.29%   65.31%   +0.02%     
- Complexity     2218     2219       +1     
============================================
  Files           122      122              
  Lines          9961     9961              
  Branches       1337     1338       +1     
============================================
+ Hits           6504     6506       +2     
+ Misses         2945     2943       -2     
  Partials        512      512              

Impacted Files	Coverage Δ
parse/src/main/java/com/parse/ParseObject.java	60.44% <0.00%> (+0.13%)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 7cff2ae...665b6d0. Read the comment docs.

[parse-github-assistant[bot]]

Thanks for opening this pull request!

• ❌ Please edit your post and use the provided template when creating a new pull request. This helps everyone to understand your post better and asks for essential information to quicker review the pull request.

[shlusiak]

@mtrezza done.

[mtrezza]

Thanks! Could you also add a test to prevent the issue from occurring in the future?

[shlusiak]

@mtrezza from what I can tell this class does not have any tests at all. Since from the outside the behaviour has not changed at all I couldn't add any blackbox test that verifies that my changes are correct, other than having tests that ensure that behaviour has indeed not changed. This is an optimisation after all. I'm afraid I don't have the time myself to add the required regression tests to ensure I didn't break anything. And I'm unsure whether you'd want to spend time on pouring concret onto the current implementation details to ensure the algorithm isn't altered in the future. A test for this specific issue would require mocking, I suppose.

[mtrezza]

@shlusiak I see, looks like not worth the effort because difficult to test. There is just one new added line that seems to decrease coverage. Maybe we can cover that with a new test (or by modifying an existing test) before merging. Seems to be a simple one.

[parseplatformorg]

🎉 This change has been released in version 2.0.4