rpc: avoid quadratic JSON construction when keys are unique #36096

Problem: getprioritisedtransactions lets node operators inspect fee adjustments. While building the response, the RPC checks each transaction ID against all previous IDs, even though duplicates are impossible. The same unnecessary search appears in a few other RPC responses built directly from std::map or std::set keys.

Fix: Each changed response key comes from an std::map or std::set, where keys are unique, so insertion can skip the linear findKey() call.

Reproducer: On a Rpi 4 the test below took almost a minute before the fix and about half that time after. The other changed map and set loops perform the same per-key search, so their response construction has the same quadratic-to-linear scaling as the number of entries grows.

<details> <summary>Reproducer commands</summary>

diff --git a/test/functional/mining_prioritisetransaction.py b/test/functional/mining_prioritisetransaction.py
--- a/test/functional/mining_prioritisetransaction.py
+++ b/test/functional/mining_prioritisetransaction.py
@@ -11,6 +11,7 @@ from test_framework.blocktools import NORMAL_GBT_REQUEST_PARAMS
 from test_framework.messages import (
     COIN,
     MAX_BLOCK_WEIGHT,
+    ser_uint256,
 )
 from test_framework.test_framework import BitcoinTestFramework
 from test_framework.util import (
@@ -215,6 +216,12 @@ class PrioritiseTransactionTest(BitcoinTestFramework):
         assert_raises_rpc_error(-1, "getprioritisedtransactions",
                 self.nodes[0].getprioritisedtransactions, True)
 
+        self.log.info("Test getprioritisedtransactions order")
+        txids = [ser_uint256(i).hex() for i in range(20_000, 0, -1)]
+        self.nodes[0].batch([self.nodes[0].prioritisetransaction.get_request(txid, 0, 1) for txid in txids])
+        assert_equal(list(self.nodes[0].getprioritisedtransactions()), txids[::-1])
+        self.clear_prioritisation(self.nodes[0])
+
         # Test `prioritisetransaction` invalid `txid`

</details>

<!--e57a25ab6845829454e8d69fc972939a-->

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

<!--006a51241073e994b41acfe9ec718e94-->

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/36096.

<!--021abf342d371248e50ceaed478a90ca-->

Reviews

See the guideline and AI policy for information on the review process.

If your review is incorrectly listed, please copy-paste <code>&lt;!--meta-tag:bot-skip--&gt;</code> into the comment that the bot should ignore.

<!--5faf32d7da4f0f540f40219e4f7537a3-->

Do we generally rely on the replacing functionality at all? I feel like this could be swapped in almost at every site?

Do we generally rely on the replacing functionality at all?

Valid question, based on the comments we have at least one such case: https://github.com/bitcoin/bitcoin/blob/a24110cef7fa36138620f1876cd0722944618d07/src/rpc/client.cpp#L513-L516

There may be a few other sites where we cannot have duplicated and could use pushKVEnd(), but here that guarantee comes directly from mapDeltas, it's trivial to prove why the lookup isn't needed. Quick LLM search for other candidates if reviewers prefer we include them here:

Strong pushKVEnd() candidates:

• src/rpc/rawtransaction.cpp:1165: eight loops over PSBT maps, including unknown fields and hash preimages. This is the strongest performance follow-up because these objects can be large.
• src/rpc/mempool.cpp:786 and src/rpc/mempool.cpp:851: both iterate CTxMemPool::setEntries, whose comparator makes txids unique. getrawmempool already uses pushKVEnd() for the same reason.
• src/rpc/net.cpp:295: two loops over std::map<std::string, uint64_t> message counters.
• src/rpc/blockchain.cpp:2210: iterates a std::set<std::string>.
• src/rpc/node.cpp:263: category names come from a std::map.
• estimaterawfee: iterates the three distinct fee-estimation horizons.

The last four are tiny objects, so there is little performance value. The worthwhile separate audits are decodepsbt, followed by the two verbose mempool RPCs. I found no open upstream PR covering them.

Edit: ended up pushing the trivial ones in a second commit, thanks for the comment.

crACK 882cf7741583cf8cd00d221e01fd9987dee57952

Verified that all pushKVEnd() calls are for unique keys.

Went down a similar rabbit hole in a5f6d47c444c5ecc777152b8cc9a1faf54eb5925 in May which I dropped on the floor. Maybe worth picking up in some form, probably as another PR.

Seems fine, left some nits

Rebased, used structured bindings for the map iterations and added braces to the affected code

ACK 74ddf1c0a0ef8447686f59044b2fc2ee8d78c0e4

re-ACK 74ddf1c0a0ef8447686f59044b2fc2ee8d78c0e4

Would prefer the last commit was merged into the middle one, but like this is fine too.