sofastack / sofa-rpc

SOFARPC is a high-performance, high-extensibility, production-level Java RPC framework.
https://www.sofastack.tech/sofa-rpc/docs/Home
Apache License 2.0
3.81k stars 1.17k forks source link

improve efficiency of list difference #1241

Closed nocvalight closed 1 year ago

nocvalight commented 1 year ago

Motivation:

The efficiency is too low while doing list difference, when list size is 10000, it cost almost 4000ms. image

Modification:

Use set difference instead of list difference.

Result:

SetDifference is 100 times more efficient than ListDifference, with a little more temporary memory allocation.

BenchMark result: image

image

codecov[bot] commented 1 year ago

Codecov Report

Merging #1241 (e26141f) into master (169016c) will increase coverage by 0.06%. The diff coverage is 96.66%.

@@             Coverage Diff              @@
##             master    #1241      +/-   ##
============================================
+ Coverage     72.04%   72.11%   +0.06%     
- Complexity      779      780       +1     
============================================
  Files           410      411       +1     
  Lines         17376    17404      +28     
  Branches       2703     2710       +7     
============================================
+ Hits          12519    12551      +32     
+ Misses         3475     3469       -6     
- Partials       1382     1384       +2     
Impacted Files Coverage Δ
.../java/com/alipay/sofa/rpc/common/RpcConstants.java 100.00% <ø> (ø)
.../main/java/com/alipay/sofa/rpc/common/Version.java 100.00% <ø> (ø)
...m/alipay/sofa/rpc/common/struct/SetDifference.java 96.15% <96.15%> (ø)
...ay/sofa/rpc/client/AllConnectConnectionHolder.java 60.76% <100.00%> (+0.25%) :arrow_up:
...ipay/sofa/rpc/codec/bolt/SofaRpcSerialization.java 76.19% <100.00%> (+0.17%) :arrow_up:
.../alipay/sofa/rpc/common/struct/ListDifference.java 93.10% <0.00%> (-3.45%) :arrow_down:
...om/alipay/sofa/rpc/server/triple/TripleServer.java 74.86% <0.00%> (-1.07%) :arrow_down:
...java/com/alipay/sofa/rpc/module/LookoutModule.java 85.71% <0.00%> (+33.33%) :arrow_up:

Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.