Reduce redundant code of prevector and speed it up #11988

pull AkioNak wants to merge 1 commits into bitcoin:master from AkioNak:prevector changing 1 files +42 −49
  1. AkioNak commented at 11:25 am on December 22, 2017: contributor

    In prevector.h, the code which like item_ptr(size()) apears in the loop. Both item_ptr() and size() judge whether values are held directly or indirectly, but in most cases it is sufficient to make that judgement once outside the loop.

    This PR adds 2 private function fill() which has the loop to initialize by specified value (or iterator of the other prevector’s element), but don’t call item_ptr() in their loop. Other functions(assign(), constructor, operator=(), insert()) that has similar loop, call fill() instead of original loop.

    Also, resize() was changed like fill(), but it calls the default constructor for that element each time.

  2. laanwj added the label Refactoring on Dec 22, 2017
  3. laanwj commented at 12:34 pm on December 22, 2017: member
    Can you please quantify the speedup, for example with benchmark results?
  4. AkioNak commented at 3:24 pm on December 22, 2017: contributor

    @laanwj thank you for your comment.

    When measuring with the bench_bitcoin command on my iMac(macOS 10.13.2, i5 2.9GHz, mem 8G, HDD), the following result was reported.

    CCheckQueueSpeedPrevectorJob => 9% faster PrevectorClear => 38% faster PrevectorDestructor => 47% faster

    [command line that actually using] (for i in `seq 1 4`; do ./src/bench/bench_bitcoin; done) | grep -i prevector | sort

    [result/before PR] CCheckQueueSpeedPrevectorJob,416,2476254,2514895,2492253,7164553,7276354,7210843 CCheckQueueSpeedPrevectorJob,416,2483647,2512180,2502839,7185942,7268498,7241472 CCheckQueueSpeedPrevectorJob,416,2497689,2519979,2507328,7226569,7291065,7254458 CCheckQueueSpeedPrevectorJob,416,2515822,2534179,2522573,7279033,7332149,7298568 PrevectorClear,5120,212797,216803,214775,615687,627278,621411 PrevectorClear,5120,213950,217197,215902,619023,628418,624671 PrevectorClear,5120,214470,217563,216133,620527,629475,625339 PrevectorClear,5120,214977,219112,216335,621995,633958,625923 PrevectorDestructor,5120,205272,214398,209738,593915,620318,606836 PrevectorDestructor,5120,206815,215047,210133,598380,622198,607979 PrevectorDestructor,5120,207571,213791,209739,600567,618564,606839 PrevectorDestructor,5120,207918,211055,209359,601571,610649,605740

    [result/after PR] CCheckQueueSpeedPrevectorJob,448,2247962,2302933,2278089,6504033,6663083,6591203 CCheckQueueSpeedPrevectorJob,448,2251507,2314172,2285333,6514292,6695605,6612160 CCheckQueueSpeedPrevectorJob,448,2259503,2321880,2298217,6537434,6717903,6649438 CCheckQueueSpeedPrevectorJob,448,2292934,2339778,2315147,6634153,6769688,6698422 PrevectorClear,6656,151838,155543,154061,439314,450034,445746 PrevectorClear,6656,152427,157205,154585,441018,454842,447261 PrevectorClear,6656,152926,155595,154268,442462,450186,446345 PrevectorClear,6656,153213,155464,154469,443293,449806,446927 PrevectorDestructor,7168,140658,144660,142405,406966,418546,412022 PrevectorDestructor,7168,140769,146722,142579,407289,424512,412526 PrevectorDestructor,7168,140925,149154,142697,407738,431550,412867 PrevectorDestructor,7168,141167,146494,142699,408441,423853,412871

  5. laanwj commented at 5:03 pm on December 22, 2017: member
    Thanks for the results, that looks promising and quite significant!
  6. practicalswift commented at 4:55 pm on December 23, 2017: contributor

    Very nice work! Thanks!

    Concept ACK

  7. in src/prevector.h:198 in 37bf6f93f0 outdated
    193@@ -194,16 +194,29 @@ class prevector {
    194     T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
    195     const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
    196 
    197+    void fill(T* dst, size_type count, const T& value) {
    198+        for (size_type i = 0; i < count; i++) {
    


    promag commented at 4:34 pm on January 2, 2018:
    ++i

    AkioNak commented at 4:03 pm on January 4, 2018:
    @promag Thank you. I fixed it.
  8. promag commented at 4:37 pm on January 2, 2018: member
    utACK 37bf6f9.
  9. promag commented at 3:00 pm on January 10, 2018: member
    re-utACK 885d061.
  10. Reduce redundant code of prevector and speed it up
    In prevector.h, the code which like item_ptr(size()) apears in the loop.
    Both item_ptr() and size() judge whether values are held directly or
    indirectly, but in most cases it is sufficient to make that judgement
    once outside the loop.
    
    This PR adds 2 private function fill() which has the loop to initialize
    by specified value (or iterator of the other prevector's element),
    but don't call item_ptr() in their loop.
    Other functions(assign(), constructor, operator=(), insert())
    that has similar loop, call fill() instead of original loop.
    
    Also, resize() was changed like fill(), but it calls the default
    constructor for that element each time.
    b4a23a91ef
  11. AkioNak force-pushed on Jan 17, 2018
  12. AkioNak commented at 2:17 am on January 17, 2018: contributor
    Squashed. More reviews are welcome.
  13. dcousens approved
  14. AkioNak commented at 0:56 am on January 19, 2018: contributor

    Travis-job has failed on address_types.py. It’s very similar to #12171 and #12205 . I think #12206 fixes them and has merged after this travis-job.

    travis log: https://travis-ci.org/bitcoin/bitcoin/jobs/329717560

    0 test  2018-01-17 14:21:53.497000 TestFramework (DEBUG): Check unconfirmed balances: [Decimal('1072.10999190'), Decimal('1429.47998920'), Decimal('0E-8'), Decimal('0E-8')] 
    1 test  2018-01-17 14:21:53.498000 TestFramework (ERROR): Assertion failed
    2Traceback (most recent call last):
    3  File "/home/travis/build/bitcoin/bitcoin/build/bitcoin-i686-pc-linux-gnu/test/functional/test_framework/test_framework.py", line 123, in main
    4    self.run_test()
    5  File "/home/travis/build/bitcoin/bitcoin/build/bitcoin-i686-pc-linux-gnu/test/functional/address_types.py", line 183, in run_test
    6    assert_equal(unconf_balances[to_node], to_send * 10 * (2 + n))
    7  File "/home/travis/build/bitcoin/bitcoin/build/bitcoin-i686-pc-linux-gnu/test/functional/test_framework/util.py", line 38, in assert_equal
    8    raise AssertionError("not(%s)" % " == ".join(str(arg) for arg in (thing1, thing2) + args))
    9AssertionError: not(0E-8 == 714.73999460) 
    
  15. in src/prevector.h:198 in b4a23a91ef
    193@@ -194,16 +194,29 @@ class prevector {
    194     T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
    195     const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
    196 
    197+    void fill(T* dst, size_type count, const T& value) {
    198+        for (size_type i = 0; i < count; ++i) {
    


    NicolasDorier commented at 5:45 am on February 27, 2018:
    nit: i++ instead of ++i

    sipa commented at 5:52 am on February 27, 2018:
    The style guide prefers ++i (it doesn’t matter for simple types, but for more complex types the prefix version is sometimes more efficient).

    NicolasDorier commented at 5:57 am on February 27, 2018:
    TIL
  16. eklitzke commented at 6:50 am on February 27, 2018: contributor
    I have another PR out, #12549 which cherry-picks this commit and then adds further optimizations.
  17. in src/prevector.h:229 in b4a23a91ef
    225@@ -213,11 +226,8 @@ class prevector {
    226         if (capacity() < n) {
    227             change_capacity(n);
    228         }
    229-        while (first != last) {
    230-            _size++;
    231-            new(static_cast<void*>(item_ptr(size() - 1))) T(*first);
    232-            ++first;
    233-        }
    234+        _size += n;
    


    Empact commented at 8:10 am on February 27, 2018:
    Seems n here should be difference_type as well.

    AkioNak commented at 2:49 pm on February 27, 2018:
    @Empact Thank you for your review. However, I think I will close this PR after a while because of having cherry-pickked by #12549 .
  18. AkioNak commented at 11:57 pm on February 27, 2018: contributor
    meld into #12549
  19. AkioNak closed this on Feb 27, 2018

  20. laanwj referenced this in commit 32987d5aeb on Mar 1, 2018
  21. AkioNak deleted the branch on Mar 2, 2018
  22. codablock referenced this in commit f599b4759f on Oct 1, 2019
  23. codablock referenced this in commit e5852a2bcd on Oct 1, 2019
  24. codablock referenced this in commit 595826ad63 on Oct 2, 2019
  25. barrystyle referenced this in commit 2ceaa3eabb on Jan 22, 2020
  26. DrahtBot locked this on Sep 8, 2021

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: 2024-11-17 15:12 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me