an-cabal/an-rope

Refactor Rope::rebalance()

Opened this issue · 3 comments

hawkw commented

From the TODO comment:

  // TODO: this is a huge mess, I based it on the IBM Java implementation
  //       please refactor until it stops being ugly!
  //        - eliza, 12/17/2016
hawkw commented

I'm adding the "performance" label to this issue, since Rope performance with rebalancing enabled is currently much, much slower than with rebalancing disabled. So this is no longer just a style issue.

hawkw commented

Some potential improvements:

  • #36: Rewrite Rope.rebalance() to be iterative
  • #35: Cache node depth as well as node length
  • #37: "Fuzzy" rope balance heuristic
hawkw commented

Performance numbers without rebalance():

test tests::rope_add_1000                     ... bench:     124,555 ns/iter (+/- 34,449)
test tests::rope_insert_1000                  ... bench:     315,314 ns/iter (+/- 126,368)
test tests::rope_insert_at_half_long          ... bench:         216 ns/iter (+/- 30)
test tests::rope_insert_at_half_short         ... bench:         219 ns/iter (+/- 58)
test tests::rope_insert_at_start_long         ... bench:         211 ns/iter (+/- 100)
test tests::rope_insert_at_start_short        ... bench:         221 ns/iter (+/- 80)
test tests::rope_insert_char_at_half_long     ... bench:         277 ns/iter (+/- 92)
test tests::rope_insert_char_at_half_short    ... bench:         264 ns/iter (+/- 98)
test tests::rope_insert_char_at_start_long    ... bench:         265 ns/iter (+/- 54)
test tests::rope_insert_char_at_start_short   ... bench:         260 ns/iter (+/- 61)
test tests::string_add_1000                   ... bench:      52,093 ns/iter (+/- 11,475)
test tests::string_insert_1000                ... bench:   3,751,875 ns/iter (+/- 706,234)
test tests::string_insert_at_half_long        ... bench:       3,532 ns/iter (+/- 754)
test tests::string_insert_at_half_short       ... bench:       2,714 ns/iter (+/- 691)
test tests::string_insert_at_start_long       ... bench:       3,603 ns/iter (+/- 1,330)
test tests::string_insert_at_start_short      ... bench:       4,097 ns/iter (+/- 671)
test tests::string_insert_char_at_half_long   ... bench:       1,905 ns/iter (+/- 251)
test tests::string_insert_char_at_half_short  ... bench:         513 ns/iter (+/- 158)
test tests::string_insert_char_at_start_long  ... bench:       3,750 ns/iter (+/- 867)
test tests::string_insert_char_at_start_short ... bench:         242 ns/iter (+/- 115)

Performance numbers with rebalance():

test tests::rope_add_1000                     ... bench:  45,825,566 ns/iter (+/- 12,068,116)
test tests::rope_insert_1000                  ... bench:  45,818,271 ns/iter (+/- 5,643,682)
test tests::rope_insert_at_half_long          ... bench:       5,770 ns/iter (+/- 3,534)
test tests::rope_insert_at_half_short         ... bench:     153,156 ns/iter (+/- 16,536)
test tests::rope_insert_at_start_long         ... bench:      13,904 ns/iter (+/- 3,904)
test tests::rope_insert_at_start_short        ... bench:     130,540 ns/iter (+/- 13,963)
test tests::rope_insert_char_at_half_long     ... bench:      33,084 ns/iter (+/- 4,527)
test tests::rope_insert_char_at_half_short    ... bench:     196,555 ns/iter (+/- 18,049)
test tests::rope_insert_char_at_start_long    ... bench:      13,627 ns/iter (+/- 2,597)
test tests::rope_insert_char_at_start_short   ... bench:     151,585 ns/iter (+/- 15,159)
test tests::string_add_1000                   ... bench:      63,185 ns/iter (+/- 12,603)
test tests::string_insert_1000                ... bench:   3,688,743 ns/iter (+/- 638,169)
test tests::string_insert_at_half_long        ... bench:       2,964 ns/iter (+/- 599)
test tests::string_insert_at_half_short       ... bench:       2,839 ns/iter (+/- 557)
test tests::string_insert_at_start_long       ... bench:       4,200 ns/iter (+/- 800)
test tests::string_insert_at_start_short      ... bench:       3,802 ns/iter (+/- 408)
test tests::string_insert_char_at_half_long   ... bench:       1,808 ns/iter (+/- 355)
test tests::string_insert_char_at_half_short  ... bench:         361 ns/iter (+/- 74)
test tests::string_insert_char_at_start_long  ... bench:       3,396 ns/iter (+/- 991)
test tests::string_insert_char_at_start_short ... bench:       1,222 ns/iter (+/- 236)