getrawmempool true RPC call is O(n^2) #14765

1. 
   jhoenicke commented at 9:20 pm on November 19, 2018: none

   When the mempool fills the verbose getrawmempool RPC call gets really slow. It can take minutes for >100k transactions in the mempool.

   The culprit is the univalue library. Objects are implemented as a big list, but the library checks for duplicate keys. So inserting n key-value pairs into an object takes O(n^2).

   Possible fixes:

   • Improve univalue library by using linked hash maps.
   • change the RPC output format of getrawmempool to use a list of objects, instead of an object of objects. But this breaks existing code.
   • hack the library to be able to skip the duplicate check.
2. 
   jhoenicke commented at 9:27 pm on November 19, 2018: none

   A quick work-around is to use __pushKV instead of pushKV in rpc/blockchain.cpp, mempoolToJSON
3. MarcoFalke added the label Resource usage on Nov 19, 2018
4. MarcoFalke added the label RPC/REST/ZMQ on Nov 19, 2018
5. MarcoFalke added the label Utils/log/libs on Nov 19, 2018
6. 
   LucianaMarques commented at 11:25 am on November 20, 2018: contributor

   Hi

   I would like to work on this. Is it already assigned?

   Thank you

7. 
   achow101 commented at 4:54 pm on November 20, 2018: member

   Have you opened an issue with the upstream repo about this? This seems like something best fixed upstream rather than here.
8. 
   promag commented at 10:49 pm on November 21, 2018: member

   @achow101 I don’t see why we need the duplicate key check. I’d be surprised if there were duplicate keys. At least we are sure most pushKV calls don’t need to incur in that check.
9. 
   jnewbery commented at 11:39 pm on November 21, 2018: member

   Have you opened an issue with the upstream repo about this? This seems like something best fixed upstream rather than here.

   Bitcoin Core uses https://github.com/bitcoin-core/univalue. Could update it there and then offer a PR upstream to jgarzik/univalue.

10. MarcoFalke referenced this in commit 3515612e06 on Mar 6, 2019
11. MarcoFalke referenced this in commit 2d16fb7a2b on May 15, 2019
12. MarcoFalke closed this on May 15, 2019

    ---

13. sidhujag referenced this in commit 43e363151b on May 15, 2019
14. Munkybooty referenced this in commit 1bd0c5b5a0 on Sep 16, 2021
15. dzutto referenced this in commit 0763dad6e7 on Oct 12, 2021
16. dzutto referenced this in commit 9ffc857c0f on Oct 12, 2021
17. dzutto referenced this in commit fec569b9ef on Oct 12, 2021
18. pravblockc referenced this in commit d714af8e31 on Nov 18, 2021
19. DrahtBot locked this on Dec 16, 2021
20. gades referenced this in commit 2857768e3a on May 24, 2022

Contributors
jhoenicke LucianaMarques achow101 promag jnewbery

Labels
RPC/REST/ZMQ Utils/log/libs Resource usage