I, Jonathan Toomim, hereby offer a $1,000 bounty for ABC code which improves getblocktemplate time by at least 4x on tx chain lengths of 1000 as long as it does not worsen performance on chain lengths of 1 for GBT or for ATMP, or a $2,000 bounty for code that makes GBT approximately O(1) versus chain length (assuming total tx count is not varied), again as long as performance is not significantly worsened in any common or adversarial usage patterns. The bounty will be 50% payable upon submission of reasonable-looking code to reviews.bitcoinabc.org, and the remaining 50% upon the code being merged by amaury. This bounty can be claimed by anyone, including people who already get paid to work on ABC code. If there are multiple submissions, I will split the bounty between them how I see fit. Smaller milestone payments may be available for intermediate tasks, like posting detailed benchmark results and profiling info.
https://imgur.com/a/1H6BsBr (source: @ealmansi on Telegram)
It's expected that the source of the apparently O(n^2) behavior in getblocktemplate is the transaction package handling code and/or the associated child-pays-for-parent (CPFP) code. One approach to winning this bounty is to simply remove the CPFP code entirely. Whether that is a valid approach or not depends on Amaury, not me -- if he doesn't like it, you will be unable to get it merged and won't be able to claim the second 50%. Another approach would be to somehow make the CPFP code not suck.
To get an idea for how the GBT algorithm works, I suggest starting to read the code here:
https://github.com/Bitcoin-ABC/bitcoin-abc/blob/master/src/miner.cpp#L440