getaddressesbylabel API spends much time #15447

1. 
   nekonenene commented at 9:40 am on February 20, 2019: none

   The getaddressesbylabel API spends a lot more time than the getaddressesbyaccount API.

   I generated addresses by the getnewaddress API, then, I measured time that the getaddressesby* API spends. It seems the algorithm of the getaddressesbylabel API takes O(N ^ 2) time! The results of my survey are as follows.

   getaddressesbylabel

   bitcoind v0.17.1 on Ubuntu 16.04 (AWS EC2 t3.large)

   11,001 addresses

   0time sudo /usr/local/bin/bitcoin-cli -conf=/etc/bitcoin/bitcoin.conf getaddressesbylabel ""
   1# (omitted)
   2real    0m1.230s # 1.2s
   3user    0m0.044s
   4sys 0m0.048s
   

   111,001 addresses

   0time sudo /usr/local/bin/bitcoin-cli -conf=/etc/bitcoin/bitcoin.conf getaddressesbylabel ""
   1# (omitted)
   2real    1m37.027s # 97.0s
   3user    0m0.408s
   4sys 0m0.544s
   

   211,001 addresses

   0time sudo /usr/local/bin/bitcoin-cli -conf=/etc/bitcoin/bitcoin.conf getaddressesbylabel ""
   1# (omitted)
   2real    6m3.727s # 363.7s
   3user    0m0.800s
   4sys 0m0.900s
   

   getaddressesbyaccount

   bitcoind v0.16.3 on Ubuntu 16.04 (AWS EC2 t3.large)

   11,001 addresses

   0time sudo /usr/local/bin/bitcoin-cli -conf=/etc/bitcoin/bitcoin.conf getaddressesbyaccount ""
   1# (omitted)
   2real    0m0.500s # 0.5s
   3user    0m0.092s
   4sys 0m0.160s
   

   111,001 addresses

   0time sudo /usr/local/bin/bitcoin-cli -conf=/etc/bitcoin/bitcoin.conf getaddressesbyaccount ""
   1# (omitted)
   2real    0m1.361s # 1.4s
   3user    0m0.168s
   4sys 0m0.348s
   

   211,001 addresses

   0time sudo /usr/local/bin/bitcoin-cli -conf=/etc/bitcoin/bitcoin.conf getaddressesbyaccount ""
   1# (omitted)
   2real    0m2.220s # 2.2s
   3user    0m0.384s
   4sys 0m0.532s
   

2. fanquake added the label RPC/REST/ZMQ on Feb 20, 2019
3. MarcoFalke added the label Wallet on Feb 20, 2019
4. MarcoFalke added this to the milestone 0.18.0 on Feb 20, 2019
5. MarcoFalke added the label Resource usage on Feb 20, 2019
6. 
   ryanofsky commented at 10:06 pm on February 20, 2019: member

   It might be useful to test getaddressesbyaccount in 0.17.1 with -deprecatedrpc=accounts, to see if that is slow as well.

   Just comparing getaddressesbyaccount in 0.16.3 and getaddressesbylabel in 0.17.1, I don’t see what would make the new version O(N^2), although it is returning more data so I would expect it to be somewhat slower.

   If I were going to try to optimize this code, I think I might start by adding a UniValue move constructor, and pushKV overload that can move from std::string and UniValue arguments instead of copying. It looks like all this code is doing is iterating over a map and building a giant UniValue.

7. 
   MarcoFalke commented at 2:24 pm on February 21, 2019: member

   Related #14765?
8. 
   ryanofsky commented at 3:14 pm on February 21, 2019: member

   Related #14765?

   Good find, #14765 completely explains this issue. The switch from push_back to pushKV makes getaddressesbylabel O(N^2). Using __pushKV instead would fix it.

9. laanwj removed this from the milestone 0.18.0 on Mar 4, 2019
10. laanwj added this to the milestone 0.19.0 on Mar 4, 2019
11. 
    laanwj commented at 11:50 am on March 4, 2019: member

    This is annoying but not a blocker for 0.18.0 release imo (it’s not a regression in 0.18 after all), moving the milestone.
12. MarcoFalke closed this on Apr 23, 2019

    ---

13. MarcoFalke referenced this in commit cd14d210c4 on Apr 23, 2019
14. pravblockc referenced this in commit ef518a1303 on Sep 25, 2021
15. pravblockc referenced this in commit 9577ca7b25 on Sep 29, 2021
16. kittywhiskers referenced this in commit 3ee77fcf6e on Oct 12, 2021
17. MarcoFalke locked this on Dec 16, 2021

Contributors
nekonenene ryanofsky MarcoFalke laanwj

Labels
Wallet RPC/REST/ZMQ Resource usage

Milestone
0.19.0