addrman, refactor: improve stochastic test in `AddSingle` #27319

1. 
   brunoerg commented at 8:25 PM on March 23, 2023: contributor

   This PR changes this algorithm to be O(1) instead of O(n). Also, in the current implementation, if pinfo->nRefCount is 0, we created an unnecessary variable (nFactor), this changes it. the change is relatively simple and does not cause conflicts.

2. 
   DrahtBot commented at 8:25 PM on March 23, 2023: contributor

   <!--e57a25ab6845829454e8d69fc972939a-->

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

   <!--006a51241073e994b41acfe9ec718e94-->

   Code Coverage

   For detailed information about the code coverage, see the test coverage report.

   <!--021abf342d371248e50ceaed478a90ca-->

   Reviews

   See the guideline for information on the review process.

   Type	Reviewers
   ACK	amitiuttarwar, stratospher, achow101

   If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

3. 
   dergoegge commented at 12:44 PM on March 31, 2023: member

   This doesn't seem like a big win. Have you benchmarked this to see if it actually makes a difference?

   (fwiw I think the bigger optimization you are making here is using << over the loop, as opposed to what you mention in the description)

4. 
   brunoerg commented at 12:55 PM on March 31, 2023: contributor

   (fwiw I think the bigger optimization you are making here is using << over the loop, as opposed to what you mention in the description)

   Just updated the description, thanks.

   This doesn't seem like a big win. Have you benchmarked this to see if it actually makes a difference?

   In a general view perhaps we won't see a HUGE difference, didn't benchmark to ensure. However, it changes this algorithm from O(n) - where n is the value of pinfo->nRefCount - to O(1). Since this is a simple change, easy to review and test, I supposed it would be interested for us.

5. 
   Ayush170-Future commented at 11:15 PM on April 1, 2023: contributor

   Yeah, the left shift should be faster than the iterative approach. Yet I'm not sure how much of an improvement it will make in terms of efficiency (because I'm not sure how big pinfo -> nRefCount could be).

   But, there are other instances in the same file where the Left shift is already being used for the same purpose. As a result, I see no point in continuing to use the current iterative method for calculating the power of two. It's better to change it for the sake of consistency and better practice.

6. Ayush170-Future approved
7. 
   DrahtBot commented at 9:13 AM on August 8, 2023: contributor

   <!--8ac04cdde196e94527acabf64b896448-->

   There hasn't been much activity lately. What is the status here?

   Finding reviewers may take time. However, if the patch is no longer relevant, please close this pull request. If the author lost interest or time to work on this, please close it and mark it 'Up for grabs' with the label, so that it can be picked up in the future.

8. achow101 requested review from sipa on Sep 20, 2023
9. achow101 requested review from amitiuttarwar on Sep 20, 2023
10. achow101 requested review from mzumsande on Sep 20, 2023
11. in src/addrman.cpp:598 in a7ba3a248d outdated

     598 | -        if (nFactor > 1 && (insecure_rand.randrange(nFactor) != 0))
     599 | -            return false;
     600 | +        if (pinfo->nRefCount > 0) {
     601 | +            const int nFactor{1 << pinfo->nRefCount};
     602 | +            if (insecure_rand.randrange(nFactor) != 0)
     603 | +                return false;
    

    ---

    ---

    

    amitiuttarwar commented at 5:10 PM on September 27, 2023:

    since you're touching, can you update to make this fit the developer style notes? 🔗

    If an if only has a single-statement then-clause, it can appear on the same line as the if, without braces. In every other case, braces are required, and the then and else clauses must appear correctly indented on a new line.

    ---

    

    brunoerg commented at 5:31 PM on September 27, 2023:

    sure

12. 
    amitiuttarwar commented at 5:28 PM on September 27, 2023: contributor

    I don't think this is a significant improvement, but the slight improvement seems fine since it's small, easy to check that there's no delta in behavior, and doesn't conflict with other PRs.

13. addrman, refactor: improve stochastic test in `AddSingle`

    This commit changes this algo to be O(1) instead of O(n) by using `<<`.

    e064487ca2
14. brunoerg force-pushed on Sep 27, 2023
15. 
    brunoerg commented at 5:36 PM on September 27, 2023: contributor

    Force-pushed addressing #27319 (review).

    Also updated the description.

16. 
    amitiuttarwar commented at 7:34 PM on December 11, 2023: contributor

    ACK e064487ca28c12ba774c2f43a3c7acbdb1a278c9

17. 
    stratospher commented at 5:14 AM on January 5, 2024: contributor

    ACK e064487ca28c12ba774c2f43a3c7acbdb1a278c9. simple use of << instead of a loop, didn't observe any behaviour difference before and after.

    if pinfo->nRefCount is 0, we created an unnecessary variable (nFactor)

    i don't think pinfo->nRefCount can be 0 here though. pinfo->nRefCount can take on values [1, 7] here. the very first time when we add an address, it would go to the else block instead of the current if block.

18. DrahtBot added the label CI failed on Jan 13, 2024
19. 
    achow101 commented at 6:40 PM on February 8, 2024: member

    ACK e064487ca28c12ba774c2f43a3c7acbdb1a278c9

20. achow101 merged this on Feb 8, 2024
21. achow101 closed this on Feb 8, 2024

    ---

22. PastaPastaPasta referenced this in commit 1c6eb819ef on Oct 24, 2024
23. PastaPastaPasta referenced this in commit 03e0bd3347 on Oct 24, 2024
24. PastaPastaPasta referenced this in commit aaccc9ea51 on Oct 24, 2024
25. bitcoin locked this on Feb 7, 2025

Contributors

brunoergDrahtBotdergoeggeAyush170-Futureamitiuttarwarstratospherachow101

Review Requested
sipamzumsande