{"payload":{"feedbackUrl":"https://github.com/orgs/community/discussions/53140","repo":{"id":359996917,"defaultBranch":"main","name":"rust_bst","ownerLogin":"mlodato517","currentUserCanPush":false,"isFork":false,"isEmpty":false,"createdAt":"2021-04-21T01:25:23.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/18740355?v=4","public":true,"private":false,"isOrgOwned":false},"refInfo":{"name":"","listCacheKey":"v0:1685383244.698807","currentOid":""},"activityList":{"items":[{"before":null,"after":"a78283558d980f3561432a8efa2b1c60353be870","ref":"refs/heads/dependabot/cargo/criterion-0.5","pushedAt":"2023-05-29T18:00:44.698Z","pushType":"branch_creation","commitsCount":0,"pusher":{"login":"dependabot[bot]","name":null,"path":"/apps/dependabot","primaryAvatarUrl":"https://avatars.githubusercontent.com/in/29110?s=80&v=4"},"commit":{"message":"Update criterion requirement from 0.4 to 0.5\n\nUpdates the requirements on [criterion](https://github.com/bheisler/criterion.rs) to permit the latest version.\n- [Changelog](https://github.com/bheisler/criterion.rs/blob/master/CHANGELOG.md)\n- [Commits](https://github.com/bheisler/criterion.rs/compare/0.4.0...0.5.1)\n\n---\nupdated-dependencies:\n- dependency-name: criterion\n  dependency-type: direct:production\n...\n\nSigned-off-by: dependabot[bot] <support@github.com>","shortMessageHtmlLink":"Update criterion requirement from 0.4 to 0.5"}},{"before":"286c94b3bdcc638eea21462beda46cf15b0e2f5f","after":"3447a554be4f6068de57b3d5ab5223252a96f0a5","ref":"refs/heads/avoid-allocation-in-delete-miss","pushedAt":"2023-03-16T16:18:53.000Z","pushType":"force_push","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Avoid unnecessary allocation in delete-miss\n\n## This Commit\n\nUses `bangsafe`'s `DeleteResult` construct to avoid unnecessary\n`Rc::new`ing when trying to delete a node that isn't there.\n\n## Why?\n\nPreviously, `Child::Delete` would call `Rc::new` on the result of\n`n.delete(k)` regardless of what happened. This means that, if\n`n.delete(k)` did nothing, we'd allocate a new `Rc` instead of cloning\nan existing one. See [this comment][0] for more details.\n\n## Benchmarks\n\nIgnoring `find`, `insert`, and `find-miss` since those codepaths weren't\ntouched, we see:\n\n```\ndelete/immutable/6          time:   [58.097 ns 58.167 ns 58.250 ns]\n                            change: [+12.429% +12.732% +13.025%]\n                            Performance has regressed.\ndelete/immutable/126        time:   [161.59 ns 161.74 ns 161.91 ns]\n                            change: [+11.545% +11.783% +12.023%]\n                            Performance has regressed.\ndelete/immutable/2046       time:   [306.21 ns 306.81 ns 307.88 ns]\n                            change: [+1.7977% +2.2199% +2.5886%]\n                            Performance has regressed.\ndelete/immutable/32766      time:   [494.58 ns 495.30 ns 496.57 ns]\n                            change: [+6.8019% +7.0829% +7.3743%]\n                            Performance has regressed.\ndelete-miss/immutable/6     time:   [34.370 ns 34.401 ns 34.438 ns]\n                            change: [-51.402% -51.225% -51.080%]\n                            Performance has improved.\ndelete-miss/immutable/126   time:   [45.142 ns 45.171 ns 45.200 ns]\n                            change: [-73.200% -73.095% -73.020%]\n                            Performance has improved.\ndelete-miss/immutable/2046  time:   [57.241 ns 57.282 ns 57.327 ns]\n                            change: [-82.457% -82.430% -82.402%]\n                            Performance has improved.\ndelete-miss/immutable/32766 time:   [67.454 ns 67.489 ns 67.527 ns]\n                            change: [-86.728% -86.697% -86.672%]\n                            Performance has improved.\n```\n\nwhich is expected. `delete` is now doing more work because it's tracking\nwhether or not the value was found. So when the value _is_ found, we're\ndoing extra work for \"nothing\"*. However, in `delete-miss`, we now avoid\nunnecessary allocations of new `Rc`s so there are huge improvements.\n\n\\* I say this is for \"nothing\" but I don't really mean it. Realistically,\n`Tree::delete` should return the value of the deleted node and\n`DeleteResult` is a reasonable place to store that because the caller\nneeds both the new tree and the `Option<Rc<V>>`. Because of this, I'm\nokay with the hit to `delete` and a future PR should add the deleted\nvalue to the return value of `delete`.\n\n[0]: https://github.com/mlodato517/rust_bst/pull/17#discussion_r1120728564","shortMessageHtmlLink":"Avoid unnecessary allocation in delete-miss"}},{"before":"0ab9adeb32e53ef3bd9a19a4edee54eeb15f3ca4","after":"286c94b3bdcc638eea21462beda46cf15b0e2f5f","ref":"refs/heads/avoid-allocation-in-delete-miss","pushedAt":"2023-03-16T16:18:31.000Z","pushType":"force_push","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Avoid unnecessary allocation in delete-miss\n\n## This Commit\n\nUses `bangsafe`'s `DeleteResult` construct to avoid unnecessary\n`Rc::new`ing when trying to delete a node that isn't there.\n\n## Why?\n\nPreviously, `Child::Delete` would call `Rc::new` on the result of\n`n.delete(k)` regardless of what happened. This means that, if\n`n.delete(k)` did nothing, we'd allocate a new `Rc` instead of cloning\nan existing one. See [this comment][0] for more details.\n\n## Benchmarks\n\nIgnoring `find`, `insert`, and `find-miss` since those codepaths weren't\ntouched, we see:\n\n```\ndelete/immutable/6          time:   [58.097 ns 58.167 ns 58.250 ns]\n                            change: [+12.429% +12.732% +13.025%]\n                            Performance has regressed.\ndelete/immutable/126        time:   [161.59 ns 161.74 ns 161.91 ns]\n                            change: [+11.545% +11.783% +12.023%]\n                            Performance has regressed.\ndelete/immutable/2046       time:   [306.21 ns 306.81 ns 307.88 ns]\n                            change: [+1.7977% +2.2199% +2.5886%]\n                            Performance has regressed.\ndelete/immutable/32766      time:   [494.58 ns 495.30 ns 496.57 ns]\n                            change: [+6.8019% +7.0829% +7.3743%]\n                            Performance has regressed.\ndelete-miss/immutable/6     time:   [34.370 ns 34.401 ns 34.438 ns]\n                            change: [-51.402% -51.225% -51.080%]\n                            Performance has improved.\ndelete-miss/immutable/126   time:   [45.142 ns 45.171 ns 45.200 ns]\n                            change: [-73.200% -73.095% -73.020%]\n                            Performance has improved.\ndelete-miss/immutable/2046  time:   [57.241 ns 57.282 ns 57.327 ns]\n                            change: [-82.457% -82.430% -82.402%]\n                            Performance has improved.\ndelete-miss/immutable/32766 time:   [67.454 ns 67.489 ns 67.527 ns]\n                            change: [-86.728% -86.697% -86.672%]\n                            Performance has improved.\n```\n\nwhich is expected. `delete` is now doing more work because it's tracking\nwhether or not the value was found. So when the value _is_ found, we're\ndoing extra work for \"nothing\"*. However, in `delete-miss`, we now avoid\nunnecessary allocations of new `Rc`s so there are huge improvements.\n\n\\* I say this is for \"nothing\" but I don't really mean it. Realistically,\n`Tree::delete` should return the value of the deleted node and\n`DeleteResult` is a reasonable place to store that because the caller\nneeds both the new tree and the `Option<Rc<V>>`. Because of this, I'm\nokay with the hit to `delete` and a future PR should add the deleted\nvalue to the return value of `delete`.\n\n[0]: https://github.com/mlodato517/rust_bst/pull/17#discussion_r1120728564","shortMessageHtmlLink":"Avoid unnecessary allocation in delete-miss"}},{"before":"5de848c9ca96f329e68162bfc2e80136f2c0d63d","after":"0ab9adeb32e53ef3bd9a19a4edee54eeb15f3ca4","ref":"refs/heads/avoid-allocation-in-delete-miss","pushedAt":"2023-03-16T16:15:09.000Z","pushType":"force_push","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Avoid unnecessary allocation in delete-miss\n\n## This Commit\n\nUses `bangsafe`'s `DeleteResult` construct to avoid unnecessary\n`Rc::new`ing when trying to delete a node that isn't there.\n\n## Why?\n\nPreviously, `Child::Delete` would call `Rc::new` on the result of\n`n.delete(k)` regardless of what happened. This means that, if\n`n.delete(k)` did nothing, we'd allocate a new `Rc` instead of cloning\nan existing one. See [this comment][0] for more details.\n\n## Benchmarks\n\nIgnoring `find`, `insert`, and `find-miss` since those codepaths weren't\ntouched, we see:\n\n```\ndelete/immutable/6          time:   [58.097 ns 58.167 ns 58.250 ns]\n                            change: [+12.429% +12.732% +13.025%]\n                            Performance has regressed.\ndelete/immutable/126        time:   [161.59 ns 161.74 ns 161.91 ns]\n                            change: [+11.545% +11.783% +12.023%]\n                            Performance has regressed.\ndelete/immutable/2046       time:   [306.21 ns 306.81 ns 307.88 ns]\n                            change: [+1.7977% +2.2199% +2.5886%]\n                            Performance has regressed.\ndelete/immutable/32766      time:   [494.58 ns 495.30 ns 496.57 ns]\n                            change: [+6.8019% +7.0829% +7.3743%]\n                            Performance has regressed.\ndelete-miss/immutable/6     time:   [34.370 ns 34.401 ns 34.438 ns]\n                            change: [-51.402% -51.225% -51.080%]\n                            Performance has improved.\ndelete-miss/immutable/126   time:   [45.142 ns 45.171 ns 45.200 ns]\n                            change: [-73.200% -73.095% -73.020%]\n                            Performance has improved.\ndelete-miss/immutable/2046  time:   [57.241 ns 57.282 ns 57.327 ns]\n                            change: [-82.457% -82.430% -82.402%]\n                            Performance has improved.\ndelete-miss/immutable/32766 time:   [67.454 ns 67.489 ns 67.527 ns]\n                            change: [-86.728% -86.697% -86.672%]\n                            Performance has improved.\n```\n\nwhich is expected. `delete` is now doing more work because it's tracking\nwhether or not the value was found. So when the value _is_ found, we're\ndoing extra work for \"nothing\"*. However, in `delete-miss`, we now avoid\nunnecessary allocations of new `Rc`s so there are huge improvements.\n\n\\* I say this is for \"nothing\" but I don't really mean it. Realistically,\n`Tree::delete` should return the value of the deleted node and\n`DeleteResult` is a reasonable place to store that because the caller\nneeds both the new tree and the `Option<Rc<V>>`. Because of this, I'm\nokay with the hit to `delete` and a future PR should add the deleted\nvalue to the return value of `delete`.\n\n[0]: https://github.com/mlodato517/rust_bst/pull/17#discussion_r1120728564","shortMessageHtmlLink":"Avoid unnecessary allocation in delete-miss"}},{"before":"60dacba4118f56c01a3c3f0c651e791f89aa83b9","after":"5de848c9ca96f329e68162bfc2e80136f2c0d63d","ref":"refs/heads/avoid-allocation-in-delete-miss","pushedAt":"2023-03-16T15:58:38.000Z","pushType":"force_push","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Avoid unnecessary allocation in delete-miss\n\n## This Commit\n\nUses `bangsafe`'s `DeleteResult` construct to avoid unnecessary\n`Rc::new`ing when trying to delete a node that isn't there.\n\n## Why?\n\nPreviously, `Child::Delete` would call `Rc::new` on the result of\n`n.delete(k)` regardless of what happened. This means that, if\n`n.delete(k)` did nothing, we'd allocate a new `Rc` instead of cloning\nan existing one. See [this comment][0] for more details.\n\n## Benchmarks\n\n[0]: https://github.com/mlodato517/rust_bst/pull/17#discussion_r1120728564","shortMessageHtmlLink":"Avoid unnecessary allocation in delete-miss"}},{"before":"d4c629090753631bf005e00bdace55aade3b5172","after":null,"ref":"refs/heads/immutable-iterator","pushedAt":"2023-03-16T15:57:34.000Z","pushType":"branch_deletion","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"}},{"before":"2f2733a2e86d362aec121e19947472a1c683a60f","after":"1180690a3f0128ea4551cc09b4d56321414fdca2","ref":"refs/heads/main","pushedAt":"2023-03-16T15:57:31.000Z","pushType":"pr_merge","commitsCount":2,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Merge pull request #27 from mlodato517/immutable-iterator\n\nAdd tree-based iterator to immutable tree","shortMessageHtmlLink":"Merge pull request <a class=\"issue-link js-issue-link\" data-error-text=\"Failed to load title\" data-id=\"1627768491\" data-permission-text=\"Title is private\" data-url=\"https://github.com/mlodato517/rust_bst/issues/27\" data-hovercard-type=\"pull_request\" data-hovercard-url=\"/mlodato517/rust_bst/pull/27/hovercard\" href=\"https://github.com/mlodato517/rust_bst/pull/27\">#27</a> from mlodato517/immutable-iterator"}},{"before":null,"after":"d4c629090753631bf005e00bdace55aade3b5172","ref":"refs/heads/immutable-iterator","pushedAt":"2023-03-16T15:40:28.000Z","pushType":"branch_creation","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Add tree-based iterator to immutable tree\n\n## This Commit\n\nAllows for iterating over references of the key-value pairs in an\nimmutable tree.\n\n## Why?\n\nBecause this is a standard collections interface we should support. Also\nit's a good learning opportunity because it's sneaky-hard.\n\n## Up Next\n\nI do not like what I came up with one bit haha. I know I saw something\nabout this in the Nomicon way back when so I'm going to go look that up\nnow and update with the changes.\n\n### Update\n\nWell, after looking at the Nomicon, it seems like this is more-or-less\nThe Way so :tada:?","shortMessageHtmlLink":"Add tree-based iterator to immutable tree"}},{"before":"a59032ea66db9622f8daedc92a628c4a47b2f94a","after":"6dfa8acb9eab5145173490f46c95571162078cbf","ref":"refs/heads/optimize-unsafe-rotations","pushedAt":"2023-03-16T12:52:45.000Z","pushType":"force_push","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Extract `Link` type for unsafe rotations\n\n## This Commit\n\nExtracts a `Link` type to implement on rotations so root and non-root\nnodes can rotate purely through pointer swapping.\n\n## Why?\n\nThis method of rotation is simpler to understand and maintain compared\nto the previous `mem::swap` approach. Also, for nodes with large\nkeys/values, moving pointers will be faster than `mem::swap`ping node\nfields.\n\n## Benchmarks\n\nWith the change of benchmarks to have nodes with `[i32; 1024]`, it seems\nto make an improvement but it didn't help for nodes with `i32` values.\nWe might want a constant time check to decide between the two based on\nthe types of `K` and `V`.","shortMessageHtmlLink":"Extract <code>Link</code> type for unsafe rotations"}},{"before":"be3b1754199a656666a9070a9e98ea4ee6409f96","after":"a59032ea66db9622f8daedc92a628c4a47b2f94a","ref":"refs/heads/optimize-unsafe-rotations","pushedAt":"2023-03-16T12:52:31.000Z","pushType":"force_push","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Extract `Link` type for unsafe rotations\n\n## This Commit\n\nExtracts a `Link` type to implement on rotations so root and non-root\nnodes can rotate purely through pointer swapping.\n\n## Why?\n\nThis method of rotation is simpler to understand and maintain compared\nto the previous `mem::swap` approach. Also, for nodes with large\nkeys/values, moving pointers will be faster than `mem::swap`ping node\nfields.\n\n## Benchmarks\n\nWith the change of benchmarks to have nodes with `[i32; 1024]`, it seems\nto make an improvement but it didn't help for nodes with `i32` values.\nWe might want a constant time check to decide between the two based on\nthe types of `K` and `V`.","shortMessageHtmlLink":"Extract <code>Link</code> type for unsafe rotations"}},{"before":"38ccff0df59bedbb9c8b0c96a78ae345a67085c9","after":"be3b1754199a656666a9070a9e98ea4ee6409f96","ref":"refs/heads/optimize-unsafe-rotations","pushedAt":"2023-03-15T21:39:53.000Z","pushType":"force_push","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Not done but this is looking WAY better\n\nBenchmarks are confusing though. To make pointer swapping faster than\nmem::swapping I tried making the tree node values `[i32; 1024]`. Here\nare the lackluster results:\n\n```\ndelete-miss/bangsafe/3  time:   [130.26 ns 130.42 ns 130.59 ns]\n                        change: [-59.444% -59.377% -59.311%] (p = 0.00 < 0.05)\n                        Performance has improved.\ndelete-miss/bangsafe/7  time:   [673.77 ns 674.41 ns 675.14 ns]\n                        change: [-45.424% -45.341% -45.258%] (p = 0.00 < 0.05)\n                        Performance has improved.\ndelete-miss/bangsafe/11 time:   [1.9576 µs 1.9644 µs 1.9711 µs]\n                        change: [-38.710% -37.728% -36.242%] (p = 0.00 < 0.05)\n                        Performance has improved.\nFound 4 outliers among 100 measurements (4.00%)\n  2 (2.00%) high mild\n  2 (2.00%) high severe\ndelete-miss/bangsafe/15 time:   [3.3926 µs 3.4347 µs 3.4808 µs]\n                        change: [-34.141% -33.115% -31.946%] (p = 0.00 < 0.05)\n                        Performance has improved.\n```\n\nA _slight_ improvement. So either:\n\n1. I need more specific tests for rotations\n2. The two kinds of rotation should be gated behind a constant time\n   check on the size of `K` and `V`\n3. I've done something wrong\n4. This optimization isn't worth it\n\nSince this isn't a slam dunk I'll probably head over to do iterators\ninstead.","shortMessageHtmlLink":"Not done but this is looking WAY better"}},{"before":null,"after":"38ccff0df59bedbb9c8b0c96a78ae345a67085c9","ref":"refs/heads/optimize-unsafe-rotations","pushedAt":"2023-03-15T20:03:48.000Z","pushType":"branch_creation","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Not done but this is looking WAY better","shortMessageHtmlLink":"Not done but this is looking WAY better"}},{"before":"37461b135961a10a50e4ec2057e7ff9d555c3e6e","after":null,"ref":"refs/heads/share-gh-action-cache-between-branches","pushedAt":"2023-03-15T16:36:33.000Z","pushType":"branch_deletion","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"}},{"before":"b35f97afa51551aba8b9e256f754ddb7a4b2d5b3","after":"2f2733a2e86d362aec121e19947472a1c683a60f","ref":"refs/heads/main","pushedAt":"2023-03-15T16:36:28.000Z","pushType":"pr_merge","commitsCount":2,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Merge pull request #25 from mlodato517/share-gh-action-cache-between-branches\n\nEnable sharing GH Action Cache across branches","shortMessageHtmlLink":"Merge pull request <a class=\"issue-link js-issue-link\" data-error-text=\"Failed to load title\" data-id=\"1625858185\" data-permission-text=\"Title is private\" data-url=\"https://github.com/mlodato517/rust_bst/issues/25\" data-hovercard-type=\"pull_request\" data-hovercard-url=\"/mlodato517/rust_bst/pull/25/hovercard\" href=\"https://github.com/mlodato517/rust_bst/pull/25\">#25</a> from mlodato517/share-gh-action-cache-between-…"}},{"before":null,"after":"37461b135961a10a50e4ec2057e7ff9d555c3e6e","ref":"refs/heads/share-gh-action-cache-between-branches","pushedAt":"2023-03-15T16:26:57.000Z","pushType":"branch_creation","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Enable sharing GH Action Cache across branches\n\n## This Commit\n\nRuns the CI action on pushes to `main`.\n\n## Why?\n\nThis creates a cache that lives on `main` which, because `main` is the\ndefault branch, is then accessible on all branches. By default, [sibling\nbranches cannot share a cache][0]. Because of this, I saw that [new PRs\nweren't sharing caches from old PRs][^1][^2]. This should hopefully fix that.\n\n[0]: https://docs.github.com/en/actions/using-workflows/caching-dependencies-to-speed-up-workflows#restrictions-for-accessing-a-cache\n[^1]: https://github.com/mlodato517/rust_bst/actions/runs/4428287946/jobs/7767145421#step:3:22\n[^2]: https://github.com/mlodato517/rust_bst/actions/runs/4428436760/jobs/7767514408#step:3:14","shortMessageHtmlLink":"Enable sharing GH Action Cache across branches"}},{"before":"f4dac0a21b6e29b29fcae5c6ec26096c8eb71228","after":null,"ref":"refs/heads/tree-clone","pushedAt":"2023-03-15T16:22:00.000Z","pushType":"branch_deletion","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"}},{"before":"2192ae99ee956669f736a0c7297cd1d49245d299","after":"b35f97afa51551aba8b9e256f754ddb7a4b2d5b3","ref":"refs/heads/main","pushedAt":"2023-03-15T16:21:56.000Z","pushType":"pr_merge","commitsCount":2,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Merge pull request #24 from mlodato517/tree-clone\n\nAdd ability to `Clone` trees","shortMessageHtmlLink":"Merge pull request <a class=\"issue-link js-issue-link\" data-error-text=\"Failed to load title\" data-id=\"1625830599\" data-permission-text=\"Title is private\" data-url=\"https://github.com/mlodato517/rust_bst/issues/24\" data-hovercard-type=\"pull_request\" data-hovercard-url=\"/mlodato517/rust_bst/pull/24/hovercard\" href=\"https://github.com/mlodato517/rust_bst/pull/24\">#24</a> from mlodato517/tree-clone"}},{"before":"587f98142df6e76fe176ec0fd1856e6bc3596386","after":"f4dac0a21b6e29b29fcae5c6ec26096c8eb71228","ref":"refs/heads/tree-clone","pushedAt":"2023-03-15T16:10:07.000Z","pushType":"force_push","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Add ability to `Clone` trees\n\n## This Commit\n\nAdds `Clone` implementations for the immutable and unsafe trees.\n\n## Why?\n\nBecause, for the unsafe case at least, it's an interesting thing to\nlearn how to do. It also simplifies the benchmarks a little.","shortMessageHtmlLink":"Add ability to <code>Clone</code> trees"}},{"before":"d0225b2fbdc302a7451819278a32011bf6eb78a0","after":null,"ref":"refs/heads/unsafe-bst","pushedAt":"2023-03-15T16:02:49.000Z","pushType":"branch_deletion","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"}},{"before":"a09bfa88399d53557b3deb5efe76121b2213bb9c","after":"2192ae99ee956669f736a0c7297cd1d49245d299","ref":"refs/heads/main","pushedAt":"2023-03-15T16:02:46.000Z","pushType":"pr_merge","commitsCount":2,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Merge pull request #23 from mlodato517/unsafe-bst\n\nAdd unsafe AVL Tree","shortMessageHtmlLink":"Merge pull request <a class=\"issue-link js-issue-link\" data-error-text=\"Failed to load title\" data-id=\"1623754371\" data-permission-text=\"Title is private\" data-url=\"https://github.com/mlodato517/rust_bst/issues/23\" data-hovercard-type=\"pull_request\" data-hovercard-url=\"/mlodato517/rust_bst/pull/23/hovercard\" href=\"https://github.com/mlodato517/rust_bst/pull/23\">#23</a> from mlodato517/unsafe-bst"}},{"before":"16343c43d043ecb27b6006a5ad1a5fdf439cac50","after":"d0225b2fbdc302a7451819278a32011bf6eb78a0","ref":"refs/heads/unsafe-bst","pushedAt":"2023-03-15T15:56:39.000Z","pushType":"force_push","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Add unsafe AVL Tree\n\n## This Commit\n\nAdds an implementation of an AVL tree using `unsafe` and raw pointers.\n\n## Why?\n\nTo compare performance against the immutable tree and learn how to\nimplement data structures requiring `unsafe` code.\n\n## Benchmarks\n\nSee the full benchmarks below the fold but the high level review is:\n\n1. finding is basically equivalent between the trees (this is expected)\n2. insert/delete is faster for the unsafe tree in general\n    - How much faster? Great question and I don't _really_ know. Maybe\n      ~4x but I think I should make the benchmarks more targeted for\n      various kinds of rotations and things.\n\n<details>\n<summary>Results</summary>\n\n```\nfind/immutable/6            time:   [18.312 ns 18.530 ns 19.003 ns]\nfind/bangsafe/6             time:   [17.497 ns 17.624 ns 17.764 ns]\nfind/immutable/126          time:   [23.565 ns 23.605 ns 23.654 ns]\nfind/bangsafe/126           time:   [22.644 ns 22.731 ns 22.839 ns]\nfind/immutable/2046         time:   [30.506 ns 30.562 ns 30.621 ns]\nfind/bangsafe/2046          time:   [29.023 ns 29.055 ns 29.095 ns]\nfind/immutable/32766        time:   [40.783 ns 41.067 ns 41.370 ns]\nfind/bangsafe/32766         time:   [44.619 ns 44.954 ns 45.305 ns]\n\ndelete/immutable/6          time:   [53.678 ns 53.724 ns 53.775 ns]\ndelete/bangsafe/6           time:   [34.415 ns 34.448 ns 34.487 ns]\ndelete/immutable/126        time:   [146.14 ns 146.69 ns 147.40 ns]\ndelete/bangsafe/126         time:   [52.139 ns 52.220 ns 52.306 ns]\ndelete/immutable/2046       time:   [310.10 ns 310.93 ns 311.89 ns]\ndelete/bangsafe/2046        time:   [73.214 ns 73.388 ns 73.596 ns]\ndelete/immutable/32766      time:   [490.92 ns 498.97 ns 510.66 ns]\ndelete/bangsafe/32766       time:   [130.12 ns 131.33 ns 132.58 ns]\n\ninsert/immutable/6          time:   [228.69 ns 229.27 ns 230.35 ns]\ninsert/bangsafe/6           time:   [122.80 ns 122.85 ns 122.92 ns]\ninsert/immutable/126        time:   [250.56 ns 250.77 ns 251.01 ns]\ninsert/bangsafe/126         time:   [56.900 ns 56.961 ns 57.032 ns]\ninsert/immutable/2046       time:   [430.40 ns 431.41 ns 432.59 ns]\ninsert/bangsafe/2046        time:   [70.494 ns 70.745 ns 71.161 ns]\ninsert/immutable/32766      time:   [652.87 ns 655.95 ns 659.06 ns]\ninsert/bangsafe/32766       time:   [107.08 ns 107.72 ns 108.34 ns]\n\nfind-miss/immutable/6       time:   [17.797 ns 17.826 ns 17.868 ns]\nfind-miss/bangsafe/6        time:   [17.745 ns 17.768 ns 17.793 ns]\nfind-miss/immutable/126     time:   [23.399 ns 23.443 ns 23.495 ns]\nfind-miss/bangsafe/126      time:   [24.865 ns 25.247 ns 26.027 ns]\nfind-miss/immutable/2046    time:   [30.361 ns 30.429 ns 30.504 ns]\nfind-miss/bangsafe/2046     time:   [29.651 ns 29.713 ns 29.786 ns]\nfind-miss/immutable/32766   time:   [40.383 ns 41.047 ns 41.927 ns]\nfind-miss/bangsafe/32766    time:   [41.519 ns 41.622 ns 41.732 ns]\n\ndelete-miss/immutable/6     time:   [73.729 ns 73.890 ns 74.131 ns]\ndelete-miss/bangsafe/6      time:   [22.151 ns 22.183 ns 22.217 ns]\ndelete-miss/immutable/126   time:   [168.89 ns 169.11 ns 169.35 ns]\ndelete-miss/bangsafe/126    time:   [28.771 ns 28.807 ns 28.848 ns]\ndelete-miss/immutable/2046  time:   [337.73 ns 338.81 ns 340.09 ns]\ndelete-miss/bangsafe/2046   time:   [42.772 ns 42.895 ns 43.041 ns]\ndelete-miss/immutable/32766 time:   [514.39 ns 517.86 ns 521.50 ns]\ndelete-miss/bangsafe/32766  time:   [68.273 ns 68.716 ns 69.236 ns]\n```\n\n</details>","shortMessageHtmlLink":"Add unsafe AVL Tree"}},{"before":"7b724d5ea4b811e1ed9daa8ace457e61ebb74648","after":"16343c43d043ecb27b6006a5ad1a5fdf439cac50","ref":"refs/heads/unsafe-bst","pushedAt":"2023-03-15T15:14:00.000Z","pushType":"push","commitsCount":1,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Don't bother caching Miri stuff in CI\n\nLooking at [this uncached run][0] and [this cached run][1] it looks like\ncaching doesn't change how long this step takes.\n\n[0]: https://github.com/mlodato517/rust_bst/actions/runs/4419189738/jobs/7747299651\n[1]: https://github.com/mlodato517/rust_bst/actions/runs/4427209702/jobs/7764481287","shortMessageHtmlLink":"Don't bother caching Miri stuff in CI"}},{"before":"7e719d37f9a607a3164ff675b68a3e8c02b7561a","after":"7b724d5ea4b811e1ed9daa8ace457e61ebb74648","ref":"refs/heads/unsafe-bst","pushedAt":"2023-03-15T14:06:32.000Z","pushType":"push","commitsCount":2,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Change assertion when fixing height\n\nBefore I was checking that the new height was less than `usize::MAX`.\nThis is sort of fine because presumably the children got here this way\ntoo but, for maximal correctness, we actually want to verify that\nneither child height `== usize::MAX`. That ensures that adding 1 won't\nwrap around to 0 and cause an issue when we drop a Node and check for\n`VALUE_REMOVED` (I guess worst case is we'd leak the memory?).\n\nSince these assertions should be incredibly predictable, hopefully this\ndoesn't meaningfully impact performance. We can always move them to\ndebug assertions later because I really don't understand how one could\nget a tree that tall anyway.","shortMessageHtmlLink":"Change assertion when fixing height"}},{"before":"ad2e3bf00e9038e915762c37d41949a237080983","after":"7e719d37f9a607a3164ff675b68a3e8c02b7561a","ref":"refs/heads/unsafe-bst","pushedAt":"2023-03-14T19:33:27.000Z","pushType":"push","commitsCount":1,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Improve some comments","shortMessageHtmlLink":"Improve some comments"}},{"before":"7021c3d5bc6f7ee8e6a68a3583d16a8b7f376e14","after":"ad2e3bf00e9038e915762c37d41949a237080983","ref":"refs/heads/unsafe-bst","pushedAt":"2023-03-14T19:02:43.000Z","pushType":"push","commitsCount":1,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Remove outdated and unhelpful benchmark comments","shortMessageHtmlLink":"Remove outdated and unhelpful benchmark comments"}},{"before":"bed57700d4b41aa8422df65d1f2d33dabd65ebf0","after":"7021c3d5bc6f7ee8e6a68a3583d16a8b7f376e14","ref":"refs/heads/unsafe-bst","pushedAt":"2023-03-14T18:59:52.000Z","pushType":"push","commitsCount":1,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Only one GH Action at a time","shortMessageHtmlLink":"Only one GH Action at a time"}},{"before":"7593717a7f19d99836d8f5e10dc768e98f2c21ff","after":"bed57700d4b41aa8422df65d1f2d33dabd65ebf0","ref":"refs/heads/unsafe-bst","pushedAt":"2023-03-14T18:59:16.000Z","pushType":"push","commitsCount":2,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Revert \"Test caching\"\n\nThis reverts commit 7593717a7f19d99836d8f5e10dc768e98f2c21ff.","shortMessageHtmlLink":"Revert \"Test caching\""}},{"before":"8d466757a4ba19eb3cbe5dbaa85c68817aea277e","after":"7593717a7f19d99836d8f5e10dc768e98f2c21ff","ref":"refs/heads/unsafe-bst","pushedAt":"2023-03-14T18:54:33.000Z","pushType":"push","commitsCount":1,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Test caching","shortMessageHtmlLink":"Test caching"}},{"before":"15688002fcdd7c7405385bafb3498698380a58eb","after":"8d466757a4ba19eb3cbe5dbaa85c68817aea277e","ref":"refs/heads/unsafe-bst","pushedAt":"2023-03-14T18:49:42.000Z","pushType":"push","commitsCount":1,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Better CI cache key","shortMessageHtmlLink":"Better CI cache key"}},{"before":"acf7c623e751f031dad901357dcda1b591e3f796","after":"15688002fcdd7c7405385bafb3498698380a58eb","ref":"refs/heads/unsafe-bst","pushedAt":"2023-03-14T18:47:05.000Z","pushType":"force_push","commitsCount":0,"pusher":{"login":"mlodato517","name":"Mark Lodato","path":"/mlodato517","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/18740355?s=80&v=4"},"commit":{"message":"Attempt to cache stuff + Miri","shortMessageHtmlLink":"Attempt to cache stuff + Miri"}}],"hasNextPage":true,"hasPreviousPage":false,"activityType":"all","actor":null,"timePeriod":"all","sort":"DESC","perPage":30,"cursor":"djE6ks8AAAADNm_jnQA","startCursor":null,"endCursor":null}},"title":"Activity · mlodato517/rust_bst"}