Cleanup fee estimation code #19630

pull darosior wants to merge 5 commits into bitcoin:master from darosior:20/07/refactor_feeest_code changing 3 files +56 −61
  1. darosior commented at 7:32 PM on July 30, 2020: member

    This (does not change behaviour and) cleans up a bit of unused code in CBlockPolicyEstimator and friends, and slightly improves readability of the rest (comment correction etc.). The last commit is a small reformatting one which I could not resist but am happy to remove at will.

  2. DrahtBot added the label TX fees and policy on Jul 30, 2020
  3. darosior commented at 6:42 PM on July 31, 2020: member

    Added a trivial commit which de-duplicates some duplicated for-loops.

  4. darosior renamed this:
    Refactor fee estimation code
    Cleanup fee estimation code
    on Aug 1, 2020
  5. in src/policy/fees.h:141 in 7f61299da7 outdated 
     137 | @@ -138,9 +138,9 @@ class CBlockPolicyEstimator
 138 |  
 139 |      /** Decay of .962 is a half-life of 18 blocks or about 3 hours */
 140 |      static constexpr double SHORT_DECAY = .962;
 141 | -    /** Decay of .998 is a half-life of 144 blocks or about 1 day */
 142 | +    /** Decay of .9952 is a half-life of 144 blocks or about 1 day */
    laanwj commented at 4:52 PM on August 6, 2020:

    Any idea why these numbers changed but not the associated time period?

    darosior commented at 4:58 PM on August 6, 2020:

    Yeah, the comment was wrong and I think morcos fixed the value but forgot about the comment. The comment change happened in this commit https://github.com/bitcoin/bitcoin/commit/b649e0395464a659f4b3485ec71d28dc95ba48bd , and the variable it refers to no longer exists.

    laanwj commented at 5:06 PM on August 6, 2020:

    Oh I see, the bucket size was changed, thanks.

    jnewbery commented at 3:30 PM on September 11, 2020:

    Remove the number entirely from the comment. No need for a comment that says "x is x"

        /** This decay gives a half-life of 144 blocks or about 1 day */

    Same for other comments here.

    darosior commented at 1:55 PM on September 14, 2020:

    I don't think it's a trivial "x is x" comment: it's not trivial to me that a decay of say .99931 is equivalent to a half-life of 1008 blocks.

    jnewbery commented at 1:58 PM on September 14, 2020:

    I agree! That's why I'm saying remove the literal value that's in the code and leave the rest.

    darosior commented at 7:39 PM on September 14, 2020:

    Ah, ok: will remove if i have to retouch

  6. in src/policy/fees.cpp:221 in 7f61299da7 outdated 
     242 | -    unsigned int curNearBucket = startbucket;
 243 | -    unsigned int bestNearBucket = startbucket;
 244 | -    unsigned int curFarBucket = startbucket;
 245 | -    unsigned int bestFarBucket = startbucket;
 246 | +    unsigned int curNearBucket, bestNearBucket, curFarBucket, bestFarBucket;
 247 | +    curNearBucket = bestNearBucket = curFarBucket = bestFarBucket = maxbucketindex;
    laanwj commented at 4:54 PM on August 6, 2020:

    I personally prefer the old formulation here, with multiple lines instead of the multiple-ary =

    darosior commented at 5:03 PM on August 6, 2020:

    Changed

  7. in src/policy/fees.cpp:204 in 7f61299da7 outdated 
     212 |  
 213 |  // returns -1 on error conditions
 214 |  double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
 215 | -                                         double successBreakPoint, bool requireGreater,
 216 | -                                         unsigned int nBlockHeight, EstimationResult *result) const
 217 | +                                         double successBreakPoint, unsigned int nBlockHeight,
    laanwj commented at 4:57 PM on August 6, 2020:

    Nice catch that the requireGreater argument is unused

  8. in src/policy/fees.cpp:231 in 7f61299da7 outdated 
     226 | @@ -242,8 +227,8 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
 227 |      EstimatorBucket passBucket;
 228 |      EstimatorBucket failBucket;
 229 |  
 230 | -    // Start counting from highest(default) or lowest feerate transactions
 231 | -    for (int bucket = startbucket; bucket >= 0 && bucket <= maxbucketindex; bucket += step) {
 232 | +    // Start counting from highest feerate transactions
 233 | +    for (int bucket = maxbucketindex; bucket >= 0; bucket--) {
    laanwj commented at 4:58 PM on August 6, 2020:

    Maybe use --bucket, pre-in/decrement iis the standard in this project.

    darosior commented at 4:59 PM on August 6, 2020:

    Ok

  9. laanwj commented at 5:07 PM on August 6, 2020: member

    Code review ACK besides some minor nits

  10. darosior force-pushed on Aug 6, 2020
  11. darosior commented at 5:15 PM on August 6, 2020: member

    Amended after review (the unnecessary variables declaration move and the pre-decrement).

  12. laanwj commented at 5:20 PM on August 6, 2020: member

    FYI it looks the last usage of requireGreater=false went away in b2322e0fc6def0baf8581bbd2f4135e61c47d142

  13. darosior force-pushed on Aug 6, 2020
  14. in src/policy/fees.cpp:332 in ec5c7ae9de outdated 
     328 | @@ -339,7 +329,7 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
 329 |      }
 330 |  
 331 |      LogPrint(BCLog::ESTIMATEFEE, "FeeEst: %d %s%.0f%% decay %.5f: feerate: %g from (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out)\n",
 332 | -             confTarget, requireGreater ? ">" : "<", 100.0 * successBreakPoint, decay,
 333 | +             confTarget, ">", 100.0 * successBreakPoint, decay,
    theStack commented at 10:38 AM on August 7, 2020:

    nit: could simply put the ">" directly into the format string instead of the "%s" and have one argument less

    darosior commented at 10:43 AM on August 7, 2020:

    Yeah right

  15. theStack commented at 10:40 AM on August 7, 2020: member

    LGTM, very nice unused code finding and cleanup! I think the last two commits could be squashed, but no strong objective.

  16. darosior force-pushed on Aug 7, 2020
  17. darosior commented at 10:57 AM on August 7, 2020: member

    @theStack i think the for loops unification are not "small readability improvements", and that the readability improvements are not "unify some duplicated for loops". Also, fixed the string format, thanks!

  18. in src/policy/fees.cpp:338 in eda3f910d0 outdated 
     327 | @@ -338,8 +328,8 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
 328 |          failBucket.leftMempool = failNum;
 329 |      }
 330 |  
 331 | -    LogPrint(BCLog::ESTIMATEFEE, "FeeEst: %d %s%.0f%% decay %.5f: feerate: %g from (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out)\n",
 332 | -             confTarget, requireGreater ? ">" : "<", 100.0 * successBreakPoint, decay,
 333 | +    LogPrint(BCLog::ESTIMATEFEE, "FeeEst: %d > %.0f%% decay %.5f: feerate: %g from (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out)\n",
 334 | +             confTarget, 100.0 * successBreakPoint, decay,
    theStack commented at 11:56 AM on August 7, 2020:

    Note that this adds an additional space after the ">" that hasn't been there before. Could be problematic if e.g. some tests rely on a strict format

    darosior commented at 12:00 PM on August 7, 2020:

    Yeah, it's on purpose...

  19. darosior force-pushed on Aug 7, 2020
  20. darosior force-pushed on Aug 8, 2020
  21. darosior commented at 2:47 PM on August 8, 2020: member

    Tests pass but the s390X Travis build is always stuck and eventually results in a failure after one day (i've tried to force-push above but it won't trigger it).

    edit: reopened to kick it back..

  22. darosior closed this on Aug 10, 2020
  23. darosior reopened this on Aug 10, 2020
  24. in src/policy/fees.cpp:331 in dd7f81d528 outdated 
     324 | @@ -338,8 +325,8 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
 325 |          failBucket.leftMempool = failNum;
 326 |      }
 327 |  
 328 | -    LogPrint(BCLog::ESTIMATEFEE, "FeeEst: %d %s%.0f%% decay %.5f: feerate: %g from (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out)\n",
 329 | -             confTarget, requireGreater ? ">" : "<", 100.0 * successBreakPoint, decay,
 330 | +    LogPrint(BCLog::ESTIMATEFEE, "FeeEst: %d > %.0f%% decay %.5f: feerate: %g from (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out)\n",
 331 | +             confTarget, 100.0 * successBreakPoint, decay,
 332 |               median, passBucket.start, passBucket.end,
 333 |               100 * passBucket.withinTarget / (passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool),
    practicalswift commented at 4:05 PM on August 14, 2020:

    While not introduced in this PR we have an existing floating-point division by zero here that would be really nice to get rid of while you're touching these lines :)

    In the case of passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool == 0 that is.

    Depending on Clang version you may see it by running …

    $ CC=clang CXX=clang++ ./configure --with-sanitizers=undefined
$ make
$ src/test/test_bitcoin

    ... and look for policy/fees.cpp:…:…: runtime error: division by zero in the output.

    When this has been addressed the following UBSan suppression can be removed:

    https://github.com/bitcoin/bitcoin/blob/30dd562fd2c58536fa026fff9853b8d825216b01/test/sanitizer_suppressions/ubsan#L3

    darosior commented at 11:23 PM on August 14, 2020:

    Nice catch ! Will push a new commit, thanks :)

    darosior commented at 12:56 AM on August 15, 2020:

    Added in 24bcbbfb7b21641b6f2d00ae18d69c59a7c1f56e

  25. practicalswift changes_requested
  26. practicalswift commented at 4:05 PM on August 14, 2020: contributor

    Concept ACK

  27. in src/policy/fees.cpp:213 in 24bcbbfb7b outdated 
     223 |      int extraNum = 0;  // Number of tx's still in mempool for confTarget or longer
 224 |      double failNum = 0; // Number of tx's that were never confirmed but removed from the mempool after confTarget
 225 | -    int periodTarget = (confTarget + scale - 1)/scale;
 226 | -
 227 | +    int periodTarget = (confTarget + scale - 1) / scale;
 228 |      int maxbucketindex = buckets.size() - 1;
    jnewbery commented at 3:35 PM on September 11, 2020:

    Consider making this const? (Same for periodTarget above)

    darosior commented at 1:55 PM on September 14, 2020:

    Done

  28. in src/policy/fees.cpp:151 in 24bcbbfb7b outdated 
     153 |          failAvg[i].resize(buckets.size());
 154 |      }
 155 |  
 156 |      txCtAvg.resize(buckets.size());
 157 | -    avg.resize(buckets.size());
 158 | +    feerate_avg.resize(buckets.size());
    jnewbery commented at 3:37 PM on September 11, 2020:

    current style guide is to name prefix member variable names with m_, so this would become m_feerate_avg. No need to update the other member variable names - just this one because you're already touching it.

    darosior commented at 1:55 PM on September 14, 2020:

    Done

  29. in src/policy/fees.cpp:331 in 24bcbbfb7b outdated 
     329 | -             confTarget, requireGreater ? ">" : "<", 100.0 * successBreakPoint, decay,
 330 | +    LogPrint(BCLog::ESTIMATEFEE, "FeeEst: %d > %.0f%% decay %.5f: feerate: %g from (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out)\n",
 331 | +             confTarget, 100.0 * successBreakPoint, decay,
 332 |               median, passBucket.start, passBucket.end,
 333 | -             100 * passBucket.withinTarget / (passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool),
 334 | +             100 * passBucket.withinTarget / (passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool + std::numeric_limits<double>::min()),
    jnewbery commented at 3:51 PM on September 11, 2020:

    I'm not sure if this is the correct fix. It's very difficult to parse what this log line is doing, and adding std::numeric_limits<double>::min() makes it harder still. How about taking these calculations out of the log line, putting them in temporary variables, and explicitly setting them to zero if passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool is equal to zero?

    darosior commented at 2:22 PM on September 14, 2020:

    I'm not sure if this is the correct fix

    It's correct in the sense that it's not a division by 0 anymore :). Cleaned up by using temporary variables.

  30. jnewbery commented at 3:51 PM on September 11, 2020: member

    Concept ACK

  31. policy/fees: correct decay explanation comments
    This was confusing: which one is the good one ? After testing the value
is right but not the comment, so fix it.

Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
    dba8196b44
  32. policy/fee: remove requireGreater parameter in EstimateMedianVal()
    It was always passed as true, and complicates the (already complex)
logic of the function.

Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
    5b8cb35621
  33. policy/fees: small readability improvements
    Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
    569d92a4d2
  34. policy/fees: unify some duplicated for loops
    Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
    c36869bbf6
  35. policy/fees: remove a floating-point division by zero
    Reported-by: practicalswift <practicalswift@users.noreply.github.com>
Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
    a3abeec33a
  36. darosior force-pushed on Sep 14, 2020
  37. darosior force-pushed on Sep 14, 2020
  38. darosior commented at 2:25 PM on September 14, 2020: member

    Thanks for the review. Cleaned up the logprint, used the m_ prefix, and made some variables const.

  39. jnewbery commented at 3:20 PM on September 14, 2020: member

    utACK a3abeec33a6ae903e514c7a7b6f587b7c17288a0

  40. in src/policy/fees.cpp:140 in a3abeec33a 
     136 | @@ -139,22 +137,18 @@ class TxConfirmStats
 137 |  TxConfirmStats::TxConfirmStats(const std::vector<double>& defaultBuckets,
 138 |                                  const std::map<double, unsigned int>& defaultBucketMap,
 139 |                                 unsigned int maxPeriods, double _decay, unsigned int _scale)
 140 | -    : buckets(defaultBuckets), bucketMap(defaultBucketMap)
 141 | +    : buckets(defaultBuckets), bucketMap(defaultBucketMap), decay(_decay), scale(_scale)
    ariard commented at 4:32 PM on September 25, 2020:

    If you feel it you can comment scale parameter usage at function declaration.

  41. in src/policy/fees.cpp:212 in a3abeec33a 
     230 | -    // values pass, so we start at maxbucketindex (highest feerate) and look at successively
 231 | -    // smaller buckets until we reach failure.  Otherwise, we are looking for the highest
 232 | -    // feerate such that all lower values fail, and we go in the opposite direction.
 233 | -    unsigned int startbucket = requireGreater ? maxbucketindex : 0;
 234 | -    int step = requireGreater ? -1 : 1;
 235 | +    const int periodTarget = (confTarget + scale - 1) / scale;
    ariard commented at 4:36 PM on September 25, 2020:

    Maybe you can keep comment first halve and precise what the highers values reference is about. I believe it means higher buckets of transactions.

  42. ariard commented at 4:37 PM on September 25, 2020: member

    Code Review ACK a3abeec.

  43. in src/policy/fees.cpp:222 in a3abeec33a 
     225 | -    int periodTarget = (confTarget + scale - 1)/scale;
 226 | -
 227 | -    int maxbucketindex = buckets.size() - 1;
 228 | -
 229 | -    // requireGreater means we are looking for the lowest feerate such that all higher
 230 | -    // values pass, so we start at maxbucketindex (highest feerate) and look at successively
    MarcoFalke commented at 9:38 AM on September 28, 2020:

    nit in commit 5b8cb35621891b681f9b49a9de5f6d8da4ccdecc:

    I think this line in the comment can be kept

  44. MarcoFalke commented at 9:45 AM on September 28, 2020: member

    ACK a3abeec33a6ae903e514c7a7b6f587b7c17288a0 💹

    <details><summary>Show signature and timestamp</summary>

    Signature:

    -----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

ACK a3abeec33a6ae903e514c7a7b6f587b7c17288a0 💹
-----BEGIN PGP SIGNATURE-----

iQGzBAEBCgAdFiEE+rVPoUahrI9sLGYTzit1aX5ppUgFAlwqrYAACgkQzit1aX5p
pUiPSQv9GVM34Ovhf/IZuz4KOiBBJw2Awl49W5aP6XSMN25yuTR2sFX57bUaIMeD
jYCcLC/+Px1xXIre0l8/afNtlHxw4gz/H+iRjWj6I4wA/MF58JiskX2X6TnS5RCi
67pKDN8IiYnWdPVWacahqY9qjLPYC88RiqV65Qce6DTiTJCBh3Kh/mErp0RWjioN
Hrd7UmHgV6bzD4hhqd+qrOTY6RrDkesSC9IAZDVNNHSMl9cOiQI2zQu8lYngIFnW
uwZlDz6s79fWvJWQwnCGOJ+BkniWjii2/20ol+rZM8oOQrEkmu+vZq/aFzs8fdHo
hjk8omKNBWvhPYovGHy4PY3CWRFC7OyyQB2kcCeFkXo9iloGpmVGE0JkCm7NDOfO
gJFohrWE0al6Dl6KVAWUDZ/F8FK64oGiOE4PEI1TLK00JMMU6HL/J+MfvlhKuDD/
M334hu1c0TS0K6NSKHDCH6X5cnNrNo3IimaFAl/JdzRXyOKc7cXCt6VLsnrqZk+Q
2UZJvsAT
=0se/
-----END PGP SIGNATURE-----

    Timestamp of file with hash d9cd36b4e6a9b525b00d5cee9eb8107f4bc33c22ac73950c8b6164e5c2d50eda -

    </details>

  45. fanquake merged this on Sep 29, 2020
  46. fanquake closed this on Sep 29, 2020
  47. sidhujag referenced this in commit 65c18d24bb on Sep 29, 2020
  48. darosior deleted the branch on Jan 12, 2021
  49. deadalnix referenced this in commit 6294e47f79 on Dec 23, 2021
  50. DrahtBot locked this on Aug 16, 2022
Contributors
darosiorlaanwjjnewberytheStackpracticalswiftariardMarcoFalke
Labels
TX fees and policy
github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-04-17 09:14 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me