search

Kerollmops / sdset

Set theory applied on sorted and deduplicated slices.
https://docs.rs/sdset
MIT License
46 stars 3 forks source link

[Performance] reduce calls to exponential_offset_ge #16

Closed tzcnt closed 2 years ago

tzcnt commented 2 years ago

For difference / difference_by_key: If the data is sorted and deduplicated, then the next element that will be greater than the current element is simply the next element.

For intersection: Don't need to call exponential_offset_ge on the slice pointer(s) that are known to already be at the max value.

All tests pass, and I ran the benchmark several times and observed consistent performance improvements in the affected operations. Bench Old New
duo::difference::bench::two_slices_big 324 ns/iter (+/- 1) 179 ns/iter (+/- 1)
duo::difference::bench::two_slices_big2 189 ns/iter (+/- 2) 117 ns/iter (+/- 5)
duo::difference::bench::two_slices_big3 63 ns/iter (+/- 2) 57 ns/iter (+/- 1)
duo::difference_by_key::bench::two_slices_big 324 ns/iter (+/- 16) 174 ns/iter (+/- 1)
duo::difference_by_key::bench::two_slices_big2 204 ns/iter (+/- 10) 130 ns/iter (+/- 1)
duo::difference_by_key::bench::two_slices_big3 88 ns/iter (+/- 0) 88 ns/iter (+/- 0)
duo::intersection::bench::two_slices_big 67 ns/iter (+/- 0) 57 ns/iter (+/- 2)
duo::intersection::bench::two_slices_big2 44 ns/iter (+/- 1) 36 ns/iter (+/- 4)
duo::intersection::bench::two_slices_big3 10 ns/iter (+/- 0) 9 ns/iter (+/- 0)
duo::symmetric_difference::bench::two_slices_big 66 ns/iter (+/- 0) 66 ns/iter (+/- 0)
duo::symmetric_difference::bench::two_slices_big2 93 ns/iter (+/- 2) 89 ns/iter (+/- 2)
duo::symmetric_difference::bench::two_slices_big3 96 ns/iter (+/- 1) 96 ns/iter (+/- 2)
duo::union::bench::two_slices_big 98 ns/iter (+/- 1) 99 ns/iter (+/- 1)
duo::union::bench::two_slices_big2 83 ns/iter (+/- 1) 86 ns/iter (+/- 2)
duo::union::bench::two_slices_big3 76 ns/iter (+/- 1) 77 ns/iter (+/- 2)
multi::difference::bench::three_slices_big 628 ns/iter (+/- 2) 482 ns/iter (+/- 3)
multi::difference::bench::three_slices_big2 470 ns/iter (+/- 3) 373 ns/iter (+/- 13)
multi::difference::bench::three_slices_big3 68 ns/iter (+/- 1) 67 ns/iter (+/- 2)
multi::difference::bench::two_slices_big 423 ns/iter (+/- 1) 273 ns/iter (+/- 6)
multi::difference::bench::two_slices_big2 242 ns/iter (+/- 2) 167 ns/iter (+/- 3)
multi::difference::bench::two_slices_big3 64 ns/iter (+/- 1) 64 ns/iter (+/- 1)
multi::difference_by_key::bench::three_slices_big 646 ns/iter (+/- 1) 459 ns/iter (+/- 22)
multi::difference_by_key::bench::three_slices_big2 490 ns/iter (+/- 3) 382 ns/iter (+/- 9)
multi::difference_by_key::bench::three_slices_big3 105 ns/iter (+/- 2) 105 ns/iter (+/- 2)
multi::difference_by_key::bench::two_slices_big 444 ns/iter (+/- 5) 293 ns/iter (+/- 1)
multi::difference_by_key::bench::two_slices_big2 272 ns/iter (+/- 1) 197 ns/iter (+/- 2)
multi::difference_by_key::bench::two_slices_big3 103 ns/iter (+/- 2) 103 ns/iter (+/- 2)
multi::intersection::bench::three_slices_big 587 ns/iter (+/- 10) 572 ns/iter (+/- 4)
multi::intersection::bench::three_slices_big2 278 ns/iter (+/- 5) 273 ns/iter (+/- 2)
multi::intersection::bench::three_slices_big3 26 ns/iter (+/- 0) 26 ns/iter (+/- 0)
multi::intersection::bench::two_slices_big 491 ns/iter (+/- 7) 455 ns/iter (+/- 4)
multi::intersection::bench::two_slices_big2 300 ns/iter (+/- 6) 282 ns/iter (+/- 4)
multi::intersection::bench::two_slices_big3 23 ns/iter (+/- 0) 23 ns/iter (+/- 1)
multi::symmetric_difference::bench::three_slices_big 935 ns/iter (+/- 24) 854 ns/iter (+/- 34)
multi::symmetric_difference::bench::three_slices_big2 772 ns/iter (+/- 19) 725 ns/iter (+/- 27)
multi::symmetric_difference::bench::three_slices_big3 148 ns/iter (+/- 3) 147 ns/iter (+/- 5)
multi::symmetric_difference::bench::two_slices_big 501 ns/iter (+/- 3) 475 ns/iter (+/- 13)
multi::symmetric_difference::bench::two_slices_big2 313 ns/iter (+/- 13) 304 ns/iter (+/- 24)
multi::symmetric_difference::bench::two_slices_big3 95 ns/iter (+/- 2) 95 ns/iter (+/- 2)
multi::union::bench::three_slices_big 822 ns/iter (+/- 58) 820 ns/iter (+/- 34)
multi::union::bench::three_slices_big2 796 ns/iter (+/- 30) 775 ns/iter (+/- 32)
multi::union::bench::three_slices_big3 156 ns/iter (+/- 5) 154 ns/iter (+/- 6)
multi::union::bench::two_slices_big 650 ns/iter (+/- 23) 589 ns/iter (+/- 22)
multi::union::bench::two_slices_big2 368 ns/iter (+/- 12) 338 ns/iter (+/- 11)
multi::union::bench::two_slices_big3 94 ns/iter (+/- 1) 96 ns/iter (+/- 6)
Kerollmops commented 2 years ago

I am awaiting your next PR that introduces new convenience functions, now 😃