Closed m4ushold closed 1 month ago
The recent changes enhance the FromTreeNodes
function in api/converter/from_pb.go
, streamlining the management of parent-child relationships among TreeNode
instances. By introducing a depthTable
, the new implementation allows direct access to parent nodes, significantly boosting efficiency and readability, especially for larger datasets. Additionally, new benchmarking tests have been added to assess the performance of tree editing operations across various sizes.
File | Change Summary |
---|---|
api/converter/from_pb.go |
Optimized FromTreeNodes function by replacing nested loops with a depthTable for direct parent node access, improving time complexity and overall performance. |
test/bench/tree_editing_bench_test.go |
Introduced benchmarking tests for tree editing operations with BenchmarkTreeEditing and BenchmarkTreeConverting , assessing performance across various tree sizes. |
In the forest deep, where tree nodes grow,
A rabbit found a way to make them flow.
With a map of depth, oh what a sight,
No more loops to slow down the night!
Hopping through code, so swift and bright,
Efficiency gained, oh what a delight! πβ¨
Thank you for using CodeRabbit. We offer it for free to the OSS community and would appreciate your support in helping us grow. If you find it useful, would you consider giving us a shout-out on your favorite social media?
I've cleaned up the benchmark code a little more. Please refer to the commit below. https://github.com/yorkie-team/yorkie/commit/379ee54f5c72216d429addb1ce1915101c974ba5
Before:
After:
What this PR does / why we need it:
The time complexity of creating crdt.TreeNode is O(N^2), potentially causing performance bottlenecks. It's optimized to O(n).
While this may not be a significant issue currently, there is a risk that as the number of tree nodes in the protobuf increases, operations will scale quadratically, potentially causing performance bottlenecks.
Which issue(s) this PR fixes:
Addresses #930
Special notes for your reviewer:
Does this PR introduce a user-facing change?:
Additional documentation:
Checklist:
Summary by CodeRabbit
Summary by CodeRabbit
Improved Performance
Code Readability