fees: optimize decay #11194

1. 
   theuni commented at 7:15 pm on August 29, 2017: member

   As discussed briefly last week with @morcos and @sdaftuar. Rather than jumping around, visit elements in-order. This produces a noticeable speedup.

   I added the assertions because it’s not entirely clear from the existing code if the bucket size is allowed to differ from the individual sizes. I can’t imagine that that could be the case, so I’ll remove them if preferred.

   Additionally, I assume we could skip UpdateMovingAverages() altogether if no entries have ever been added, but it’s not obvious to me how to do that without breaking something.

2. fees: optimize decay

   Rather than jumping around, visit elements in-order. This produces a noticeable
   speedup.

   eb5911fa3d
3. 
   gmaxwell commented at 7:42 pm on August 29, 2017: contributor

   Additionally, I assume we could skip UpdateMovingAverages() altogether if no entries have ever been added, but it’s not obvious to me how to do that without breaking something.

   An optimization like this would be important for IBD.

4. 
   theuni commented at 7:51 pm on August 29, 2017: member

   @gmaxwell Indeed. When profiling IBD for the first few hundred thousand blocks, some of my results showed this function alone accounting for ~5-10% of all cpu time spent on the message handling thread.

   This change reduces those percentages to roughly half iirc, but obviously avoiding it entirely when possible would be best.

5. fanquake added the label Refactoring on Aug 30, 2017
6. 
   promag commented at 10:56 pm on August 30, 2017: member

   Additionally, I assume we could skip UpdateMovingAverages() altogether if no entries have ever been added, but it’s not obvious to me how to do that without breaking something.

   How about not Record() it if current tip is too old? In other words, just Record() and UpdateMovingAverages() when approaching live tip?

   Edit: when in IBD.

7. 
   gmaxwell commented at 0:56 am on August 31, 2017: contributor

   FWIW, I benchmarked a sync completely bypassing CBlockPolicyEstimator::processBlock and it was effectively the same speed (0.5% faster, but that could well be noise).
8. 
   promag commented at 1:06 am on August 31, 2017: member

   You mean speed in IBD, not CPU usage right?
9. 
   gmaxwell commented at 1:07 am on August 31, 2017: contributor

   Yes, though on this host (and in this benchmark) IBD is more or less cpu limited. I didn’t intend to suggest that we shouldn’t optimize here, but it’s apparently not a huge it in IBD as cfields was initially concerned about it being.
10. in src/policy/fees.cpp:252 in eb5911fa3d

    254+    for (auto& bucket : avg) {
    255+        bucket *= decay;
    256+    }
    257+    assert(txCtAvg.size() == buckets.size());
    258+    for (auto& bucket : txCtAvg) {
    259+        bucket *= decay;
    

    ---

    ---

    

    Dllieu commented at 4:31 pm on September 4, 2017:

    Would it might be more clear to write the following

     0auto applyDecay = [&decay, &buckets](std::vector<double>& transactions)
     1{
     2    assert(transactions.size() == buckets.size());
     3    for (double& bucket : transactions)
     4    {
     5        bucket *= decay;
     6    }
     7};
     8
     9for (auto& elem : confAvg)
    10{
    11    applyDecay(elem);
    12}
    13
    14for (auto& elem : failAvg)
    15{
    16    applyDecay(elem);
    17}
    18
    19applyDecay(avg);
    20applyDecay(txCtAvg);
    

11. laanwj added the label TX fees and policy on Sep 6, 2017
12. 
    TheBlueMatt commented at 4:21 pm on November 14, 2017: member

    Please lets not add more asserts in non-consensus/net code. Without the asserts happy with this or @Dllieu’s suggestion.
13. DrahtBot closed this on Jul 20, 2018

    ---

14. 
    DrahtBot commented at 7:21 pm on July 20, 2018: member
15. DrahtBot reopened this on Jul 20, 2018

    ---

16. laanwj added the label Up for grabs on Jan 9, 2019
17. 
    laanwj commented at 4:31 pm on January 9, 2019: member

    Last activity on this was in 2017, going to close this and add “up for grabs”. Let me know if you want me to reopen it.
18. laanwj closed this on Jan 9, 2019

    ---

19. MarcoFalke locked this on Dec 16, 2021

Contributors
theuni gmaxwell promag Dllieu TheBlueMatt DrahtBot laanwj

Labels
Refactoring TX fees and policy Up for grabs