search

an-cabal / an-rope

an rope data structure
https://docs.rs/an-rope
MIT License
11 stars 2 forks source link

perf(Rope metrics): Cache and evaluate Rope metrics lazily #72

Closed hawkw closed 7 years ago

hawkw commented 7 years ago

Changes in this PR:

Lazy metrics

Rewrite Rope metrics to be cached using Cells and lazily evaluated only when needed. See issue #71 and my comment on commit 7750a3966da6c891419b810773983ec8619c1e56 for more details on how we do this and why we might want to.

Closes #71

Factor out metrics

Rather than storing metrics on BranchNodes, this PR refactors the Rope structure to have a Node struct which contains all node metrics and owns a NodeValue enum. The NodeValue enum indicates whether the node is a branch or a leaf, but does not store any metrics information. This way, metrics are cached for both Leaf nodes and Branch nodes – which is possible because we now guarantee that the strings stored on Leaf nodes are immutable (as of #70).

Closes #57

Refactor internals module

Split the very long internals.rs file into multiple files. Moved some unit tests into the internals module so that they could continue to access private fields. Organisation and project structure may require more work, but having many files of over 1000 LoC was starting to become a pain.

hawkw commented 7 years ago

Note that this PR is not ready to merge - commit 81e9de1c601002fddb886f4ea926d586f478cbbe adds a rough working version of this feature but it needs code style cleanup and some tests (the ones for fmt::Debug) are currently failing. I just wanted to open the PR so that I could have someplace to store discussion related to this change.

hawkw commented 7 years ago

Benchmark results:

This branch:

(commit 81e9de1c601002fddb886f4ea926d586f478cbbe with --features unstable)

test bench::insert::rope::at_3quarter::char_long    ... bench:     578,732 ns/iter (+/- 70,888)
test bench::insert::rope::at_3quarter::char_short   ... bench:       1,018 ns/iter (+/- 36)
test bench::insert::rope::at_3quarter::long         ... bench:     575,089 ns/iter (+/- 99,528)
test bench::insert::rope::at_3quarter::rope_long    ... bench:     570,635 ns/iter (+/- 28,577)
test bench::insert::rope::at_3quarter::rope_short   ... bench:         922 ns/iter (+/- 28)
test bench::insert::rope::at_3quarter::short        ... bench:       1,051 ns/iter (+/- 94)
test bench::insert::rope::at_end::char_long         ... bench:         117 ns/iter (+/- 18)
test bench::insert::rope::at_end::char_short        ... bench:         113 ns/iter (+/- 8)
test bench::insert::rope::at_end::long              ... bench:         126 ns/iter (+/- 13)
test bench::insert::rope::at_end::rope_long         ... bench:          27 ns/iter (+/- 4)
test bench::insert::rope::at_end::rope_short        ... bench:          27 ns/iter (+/- 3)
test bench::insert::rope::at_end::short             ... bench:         117 ns/iter (+/- 14)
test bench::insert::rope::at_half::char_long        ... bench:     579,629 ns/iter (+/- 25,122)
test bench::insert::rope::at_half::char_short       ... bench:       1,019 ns/iter (+/- 26)
test bench::insert::rope::at_half::long             ... bench:     574,666 ns/iter (+/- 70,541)
test bench::insert::rope::at_half::rope_long        ... bench:     570,279 ns/iter (+/- 16,671)
test bench::insert::rope::at_half::rope_short       ... bench:         922 ns/iter (+/- 16)
test bench::insert::rope::at_half::short            ... bench:       1,059 ns/iter (+/- 247)
test bench::insert::rope::at_quarter::char_long     ... bench:     586,287 ns/iter (+/- 67,380)
test bench::insert::rope::at_quarter::char_short    ... bench:       1,039 ns/iter (+/- 66)
test bench::insert::rope::at_quarter::long          ... bench:     599,612 ns/iter (+/- 80,054)
test bench::insert::rope::at_quarter::rope_long     ... bench:     573,714 ns/iter (+/- 30,521)
test bench::insert::rope::at_quarter::rope_short    ... bench:         939 ns/iter (+/- 72)
test bench::insert::rope::at_quarter::short         ... bench:       1,038 ns/iter (+/- 83)
test bench::insert::rope::at_start::char_long       ... bench:         113 ns/iter (+/- 34)
test bench::insert::rope::at_start::char_short      ... bench:         117 ns/iter (+/- 49)
test bench::insert::rope::at_start::long            ... bench:         126 ns/iter (+/- 53)
test bench::insert::rope::at_start::rope_long       ... bench:          27 ns/iter (+/- 5)
test bench::insert::rope::at_start::rope_short      ... bench:          27 ns/iter (+/- 12)
test bench::insert::rope::at_start::short           ... bench:         117 ns/iter (+/- 18)
test bench::insert::string::at_3quarter::char_long  ... bench:       1,546 ns/iter (+/- 93)
test bench::insert::string::at_3quarter::char_short ... bench:         172 ns/iter (+/- 15)
test bench::insert::string::at_3quarter::long       ... bench:       1,418 ns/iter (+/- 96)
test bench::insert::string::at_3quarter::short      ... bench:       1,434 ns/iter (+/- 89)
test bench::insert::string::at_end::char_long       ... bench:       1,422 ns/iter (+/- 78)
test bench::insert::string::at_end::char_short      ... bench:       1,460 ns/iter (+/- 74)
test bench::insert::string::at_end::long            ... bench:       2,518 ns/iter (+/- 76)
test bench::insert::string::at_end::short           ... bench:       1,909 ns/iter (+/- 105)
test bench::insert::string::at_half::char_long      ... bench:       1,504 ns/iter (+/- 178)
test bench::insert::string::at_half::char_short     ... bench:         132 ns/iter (+/- 7)
test bench::insert::string::at_half::long           ... bench:       3,205 ns/iter (+/- 762)
test bench::insert::string::at_half::short          ... bench:       2,237 ns/iter (+/- 328)
test bench::insert::string::at_quarter::char_long   ... bench:       2,762 ns/iter (+/- 790)
test bench::insert::string::at_quarter::char_short  ... bench:         602 ns/iter (+/- 7,982)
test bench::insert::string::at_quarter::long        ... bench:       3,026 ns/iter (+/- 460)
test bench::insert::string::at_quarter::short       ... bench:       1,176 ns/iter (+/- 146)
test bench::insert::string::at_start::char_long     ... bench:       3,463 ns/iter (+/- 431)
test bench::insert::string::at_start::char_short    ... bench:         858 ns/iter (+/- 93)
test bench::insert::string::at_start::long          ... bench:       3,714 ns/iter (+/- 737)
test bench::insert::string::at_start::short         ... bench:       1,388 ns/iter (+/- 182)
test bench::rope_add_1000                           ... bench:     259,608 ns/iter (+/- 62,883)
test bench::rope_insert_1000                        ... bench: 600,973,337 ns/iter (+/- 108,406,512)
test bench::split::at_3quarter::long                ... bench:     578,088 ns/iter (+/- 38,552)
test bench::split::at_3quarter::short               ... bench:         891 ns/iter (+/- 74)
test bench::split::at_end::long                     ... bench:     587,606 ns/iter (+/- 155,509)
test bench::split::at_end::short                    ... bench:         867 ns/iter (+/- 66)
test bench::split::at_half::long                    ... bench:     581,468 ns/iter (+/- 37,425)
test bench::split::at_half::short                   ... bench:         898 ns/iter (+/- 80)
test bench::split::at_quarter::long                 ... bench:     581,773 ns/iter (+/- 69,334)
test bench::split::at_quarter::short                ... bench:         883 ns/iter (+/- 47)
test bench::split::at_start::long                   ... bench:     593,865 ns/iter (+/- 59,172)
test bench::split::at_start::short                  ... bench:         872 ns/iter (+/- 62)
test bench::string_add_1000                         ... bench:      63,389 ns/iter (+/- 7,223)
test bench::string_insert_1000                      ... bench:   3,481,236 ns/iter (+/- 299,650)

new-persist branch:

(commit fc4fc673665b51db0a1be5785424c42a41a1de2f with `--features unstable)

test bench::insert::rope::at_3quarter::char_long    ... bench:     646,158 ns/iter (+/- 243,622)
test bench::insert::rope::at_3quarter::char_short   ... bench:       1,204 ns/iter (+/- 170)
test bench::insert::rope::at_3quarter::long         ... bench:     695,117 ns/iter (+/- 103,156)
test bench::insert::rope::at_3quarter::rope_long    ... bench:     703,728 ns/iter (+/- 103,753)
test bench::insert::rope::at_3quarter::rope_short   ... bench:       1,111 ns/iter (+/- 147)
test bench::insert::rope::at_3quarter::short        ... bench:       1,197 ns/iter (+/- 168)
test bench::insert::rope::at_end::char_long         ... bench:         129 ns/iter (+/- 60)
test bench::insert::rope::at_end::char_short        ... bench:         116 ns/iter (+/- 13)
test bench::insert::rope::at_end::long              ... bench:         130 ns/iter (+/- 26)
test bench::insert::rope::at_end::rope_long         ... bench:          34 ns/iter (+/- 14)
test bench::insert::rope::at_end::rope_short        ... bench:          32 ns/iter (+/- 10)
test bench::insert::rope::at_end::short             ... bench:         112 ns/iter (+/- 16)
test bench::insert::rope::at_half::char_long        ... bench:     690,208 ns/iter (+/- 150,302)
test bench::insert::rope::at_half::char_short       ... bench:       1,200 ns/iter (+/- 266)
test bench::insert::rope::at_half::long             ... bench:     705,760 ns/iter (+/- 105,246)
test bench::insert::rope::at_half::rope_long        ... bench:     717,130 ns/iter (+/- 127,532)
test bench::insert::rope::at_half::rope_short       ... bench:       1,022 ns/iter (+/- 182)
test bench::insert::rope::at_half::short            ... bench:       1,283 ns/iter (+/- 227)
test bench::insert::rope::at_quarter::char_long     ... bench:     704,034 ns/iter (+/- 166,557)
test bench::insert::rope::at_quarter::char_short    ... bench:       1,174 ns/iter (+/- 212)
test bench::insert::rope::at_quarter::long          ... bench:     711,607 ns/iter (+/- 113,174)
test bench::insert::rope::at_quarter::rope_long     ... bench:     706,387 ns/iter (+/- 174,588)
test bench::insert::rope::at_quarter::rope_short    ... bench:       1,113 ns/iter (+/- 254)
test bench::insert::rope::at_quarter::short         ... bench:       1,174 ns/iter (+/- 224)
test bench::insert::rope::at_start::char_long       ... bench:         109 ns/iter (+/- 46)
test bench::insert::rope::at_start::char_short      ... bench:         118 ns/iter (+/- 20)
test bench::insert::rope::at_start::long            ... bench:         129 ns/iter (+/- 23)
test bench::insert::rope::at_start::rope_long       ... bench:          31 ns/iter (+/- 5)
test bench::insert::rope::at_start::rope_short      ... bench:          30 ns/iter (+/- 5)
test bench::insert::rope::at_start::short           ... bench:         111 ns/iter (+/- 28)
test bench::insert::string::at_3quarter::char_long  ... bench:       1,611 ns/iter (+/- 222)
test bench::insert::string::at_3quarter::char_short ... bench:         184 ns/iter (+/- 63)
test bench::insert::string::at_3quarter::long       ... bench:       1,010 ns/iter (+/- 97)
test bench::insert::string::at_3quarter::short      ... bench:       1,860 ns/iter (+/- 217)
test bench::insert::string::at_end::char_long       ... bench:       1,222 ns/iter (+/- 191)
test bench::insert::string::at_end::char_short      ... bench:         743 ns/iter (+/- 114)
test bench::insert::string::at_end::long            ... bench:       3,604 ns/iter (+/- 538)
test bench::insert::string::at_end::short           ... bench:       1,779 ns/iter (+/- 240)
test bench::insert::string::at_half::char_long      ... bench:       1,479 ns/iter (+/- 200)
test bench::insert::string::at_half::char_short     ... bench:       1,503 ns/iter (+/- 135)
test bench::insert::string::at_half::long           ... bench:       1,636 ns/iter (+/- 212)
test bench::insert::string::at_half::short          ... bench:       1,529 ns/iter (+/- 218)
test bench::insert::string::at_quarter::char_long   ... bench:       2,661 ns/iter (+/- 486)
test bench::insert::string::at_quarter::char_short  ... bench:       1,273 ns/iter (+/- 186)
test bench::insert::string::at_quarter::long        ... bench:       2,288 ns/iter (+/- 246)
test bench::insert::string::at_quarter::short       ... bench:       1,468 ns/iter (+/- 265)
test bench::insert::string::at_start::char_long     ... bench:       3,310 ns/iter (+/- 398)
test bench::insert::string::at_start::char_short    ... bench:       1,817 ns/iter (+/- 10,009)
test bench::insert::string::at_start::long          ... bench:       4,136 ns/iter (+/- 281)
test bench::insert::string::at_start::short         ... bench:       2,035 ns/iter (+/- 188)
test bench::rope_add_1000                           ... bench:     261,234 ns/iter (+/- 45,983)
test bench::rope_insert_1000                        ... bench: 701,397,075 ns/iter (+/- 74,412,882)
test bench::split::at_3quarter::long                ... bench:     667,640 ns/iter (+/- 61,563)
test bench::split::at_3quarter::short               ... bench:         972 ns/iter (+/- 52)
test bench::split::at_end::long                     ... bench:     665,607 ns/iter (+/- 102,987)
test bench::split::at_end::short                    ... bench:         951 ns/iter (+/- 382)
test bench::split::at_half::long                    ... bench:     663,890 ns/iter (+/- 66,101)
test bench::split::at_half::short                   ... bench:         949 ns/iter (+/- 78)
test bench::split::at_quarter::long                 ... bench:     659,072 ns/iter (+/- 45,453)
test bench::split::at_quarter::short                ... bench:         947 ns/iter (+/- 30)
test bench::split::at_start::long                   ... bench:     662,310 ns/iter (+/- 29,277)
test bench::split::at_start::short                  ... bench:         926 ns/iter (+/- 63)
test bench::string_add_1000                         ... bench:      57,938 ns/iter (+/- 5,525)
test bench::string_insert_1000                      ... bench:   3,475,382 ns/iter (+/- 226,220)
hawkw commented 7 years ago

Commit 036c4ac1371009e72340ab0414d809708647e3ec fixes a really tragic performance regression – a lot of our insert benchmark numbers went down by about 2 digits.

hawkw commented 7 years ago

Current benchmark numbers:

test bench::insert::rope::at_3quarter::char_long    ... bench:       4,452 ns/iter (+/- 1,559)
test bench::insert::rope::at_3quarter::char_short   ... bench:         259 ns/iter (+/- 65)
test bench::insert::rope::at_3quarter::long         ... bench:       4,526 ns/iter (+/- 1,036)
test bench::insert::rope::at_3quarter::rope_long    ... bench:       4,640 ns/iter (+/- 1,101)
test bench::insert::rope::at_3quarter::rope_short   ... bench:         164 ns/iter (+/- 99)
test bench::insert::rope::at_3quarter::short        ... bench:         246 ns/iter (+/- 111)
test bench::insert::rope::at_end::char_long         ... bench:         123 ns/iter (+/- 71)
test bench::insert::rope::at_end::char_short        ... bench:         116 ns/iter (+/- 44)
test bench::insert::rope::at_end::long              ... bench:         146 ns/iter (+/- 103)
test bench::insert::rope::at_end::rope_long         ... bench:          26 ns/iter (+/- 12)
test bench::insert::rope::at_end::rope_short        ... bench:          26 ns/iter (+/- 12)
test bench::insert::rope::at_end::short             ... bench:         113 ns/iter (+/- 14)
test bench::insert::rope::at_half::char_long        ... bench:       4,219 ns/iter (+/- 1,354)
test bench::insert::rope::at_half::char_short       ... bench:         229 ns/iter (+/- 96)
test bench::insert::rope::at_half::long             ... bench:       5,160 ns/iter (+/- 2,124)
test bench::insert::rope::at_half::rope_long        ... bench:       4,527 ns/iter (+/- 964)
test bench::insert::rope::at_half::rope_short       ... bench:         186 ns/iter (+/- 88)
test bench::insert::rope::at_half::short            ... bench:         236 ns/iter (+/- 119)
test bench::insert::rope::at_quarter::char_long     ... bench:       4,359 ns/iter (+/- 917)
test bench::insert::rope::at_quarter::char_short    ... bench:         217 ns/iter (+/- 29)
test bench::insert::rope::at_quarter::long          ... bench:       4,043 ns/iter (+/- 1,832)
test bench::insert::rope::at_quarter::rope_long     ... bench:       3,963 ns/iter (+/- 1,115)
test bench::insert::rope::at_quarter::rope_short    ... bench:         151 ns/iter (+/- 47)
test bench::insert::rope::at_quarter::short         ... bench:         238 ns/iter (+/- 73)
test bench::insert::rope::at_start::char_long       ... bench:         127 ns/iter (+/- 23)
test bench::insert::rope::at_start::char_short      ... bench:         128 ns/iter (+/- 30)
test bench::insert::rope::at_start::long            ... bench:         129 ns/iter (+/- 30)
test bench::insert::rope::at_start::rope_long       ... bench:          27 ns/iter (+/- 5)
test bench::insert::rope::at_start::rope_short      ... bench:          26 ns/iter (+/- 6)
test bench::insert::rope::at_start::short           ... bench:         127 ns/iter (+/- 28)
test bench::insert::string::at_3quarter::char_long  ... bench:       1,448 ns/iter (+/- 231)
test bench::insert::string::at_3quarter::char_short ... bench:       1,395 ns/iter (+/- 180)
test bench::insert::string::at_3quarter::long       ... bench:       2,678 ns/iter (+/- 365)
test bench::insert::string::at_3quarter::short      ... bench:       1,467 ns/iter (+/- 158)
test bench::insert::string::at_end::char_long       ... bench:         833 ns/iter (+/- 205)
test bench::insert::string::at_end::char_short      ... bench:         190 ns/iter (+/- 50)
test bench::insert::string::at_end::long            ... bench:       2,300 ns/iter (+/- 477)
test bench::insert::string::at_end::short           ... bench:       1,835 ns/iter (+/- 249)
test bench::insert::string::at_half::char_long      ... bench:       1,522 ns/iter (+/- 408)
test bench::insert::string::at_half::char_short     ... bench:       1,639 ns/iter (+/- 186)
test bench::insert::string::at_half::long           ... bench:       1,804 ns/iter (+/- 209)
test bench::insert::string::at_half::short          ... bench:         793 ns/iter (+/- 176)
test bench::insert::string::at_quarter::char_long   ... bench:       2,589 ns/iter (+/- 438)
test bench::insert::string::at_quarter::char_short  ... bench:         162 ns/iter (+/- 96)
test bench::insert::string::at_quarter::long        ... bench:       2,348 ns/iter (+/- 1,056)
test bench::insert::string::at_quarter::short       ... bench:       1,198 ns/iter (+/- 145)
test bench::insert::string::at_start::char_long     ... bench:       3,025 ns/iter (+/- 1,094)
test bench::insert::string::at_start::char_short    ... bench:       1,657 ns/iter (+/- 153)
test bench::insert::string::at_start::long          ... bench:       4,125 ns/iter (+/- 584)
test bench::insert::string::at_start::short         ... bench:       1,718 ns/iter (+/- 206)
test bench::rope_add_1000                           ... bench:     229,787 ns/iter (+/- 83,634)
test bench::rope_insert_1000                        ... bench:   4,609,541 ns/iter (+/- 1,106,735)
test bench::split::at_3quarter::long                ... bench:       3,851 ns/iter (+/- 1,195)
test bench::split::at_3quarter::short               ... bench:         127 ns/iter (+/- 54)
test bench::split::at_end::long                     ... bench:       3,990 ns/iter (+/- 1,128)
test bench::split::at_end::short                    ... bench:          89 ns/iter (+/- 21)
test bench::split::at_half::long                    ... bench:       4,643 ns/iter (+/- 1,141)
test bench::split::at_half::short                   ... bench:         107 ns/iter (+/- 31)
test bench::split::at_quarter::long                 ... bench:       4,450 ns/iter (+/- 935)
test bench::split::at_quarter::short                ... bench:         105 ns/iter (+/- 70)
test bench::split::at_start::long                   ... bench:       4,031 ns/iter (+/- 685)
test bench::split::at_start::short                  ... bench:          86 ns/iter (+/- 16)
test bench::string_add_1000                         ... bench:      64,421 ns/iter (+/- 10,044)
test bench::string_insert_1000                      ... bench:   3,814,262 ns/iter (+/- 664,790)
hawkw commented 7 years ago

This should be ready to merge now, provided the Travis build passes.

codecov-io commented 7 years ago

Current coverage is 94.49% (diff: 90.47%)

Merging #72 into master will increase coverage by 0.05%

@@             master        #72   diff @@
==========================================
  Files             7          9     +2   
  Lines          1169       1543   +374   
  Methods           0          0          
  Messages          0          0          
  Branches          0          0          
==========================================
+ Hits           1104       1458   +354   
- Misses           65         85    +20   
  Partials          0          0

Powered by Codecov. Last update 130900e...dc441b0