Insert/Delete address perf improvement

rahulghangas commented 4 years ago

Calling Signatory() on an address is an expensive operation and is called various times in the function parameter for sort.Search(). However, since we already store the signatories in the addrsBySignatories map, we can make the lookup for signatories significantly cheaper by making addrsBySignatories a bidirectional hashMap.

Gives ~10x performance gain for both InsertAddr and DeleteAddr

[x] Perf tests (Benchmarking)

Benchmark results of PR (using Bi directional hashmap)

DHT Addresses
  Adding 1000 addresses to distributed hash table

• [MEASUREMENT]
DHT

    Ran 10 samples:
    runtime:
      Fastest Time: 0.207s
      Slowest Time: 0.216s
      Average Time: 0.209s ± 0.002s
------------------------------
• [MEASUREMENT]
DHT Addresses
  Removing 1000 addresses from distributed hash table

• [MEASUREMENT]
DHT

    Ran 10 samples:
    runtime:
      Fastest Time: 0.001s
      Slowest Time: 0.001s
      Average Time: 0.001s ± 0.000s

vs Becnhmark results of master

DHT Addresses
  Adding 1000 addresses to distributed hash table

• [MEASUREMENT]
DHT

    Ran 10 samples:
    runtime:
      Fastest Time: 1.942s
      Slowest Time: 1.985s
      Average Time: 1.951s ± 0.012s
------------------------------
DHT Addresses
  Removing 1000 addresses from distributed hash table

• [MEASUREMENT]
DHT

    Ran 10 samples:
    runtime:
      Fastest Time: 2.217s
      Slowest Time: 2.314s
      Average Time: 2.249s ± 0.033s

loongy commented 4 years ago

@rahulghangas please add the benchmark results to the description, would love to see some concrete numbers.

rahulghangas commented 4 years ago

Added initial benchmark results to description

rahulghangas commented 3 years ago

Closing this, changes have been integrated into the experimental branch

renproject / aw

Insert/Delete address perf improvement #46