• Michael Müller's avatar
    [core] Optimization for storage2::BinaryHeap (#508) · 958dbc1c
    Michael Müller authored
    
    
    * BinaryHeap::new()
    
    * Failing FromIterator test
    
    * Dumb push impl
    
    * Dumb peek impl
    
    * Naive push implementation
    
    * Copy in some reference impls for inspiration
    
    * WIP: use storage2::Vec and implement pop
    
    * Fix sift_up
    
    * Fix sift_down
    
    * Test with heap from slice
    
    * Add pass through clear impl
    
    * Add storage trait impls
    
    * Add binary_heap bench, start experimentation
    
    # Conflicts:
    #	core/Cargo.toml
    
    * Add tests for push/pull from storage
    
    * Get basic bench working for pushing largest value
    
    * Fmt
    
    * Prevent storage from being cleared in test env
    
    * iter batched
    
    * Make inline setup to test consistency
    
    * Revert to iter_batch tests
    
    * Add populated cache benches
    
    * Fmt
    
    * Factor out bench push
    
    * Refactor benchmark loop on push
    
    * Configure warm-up and measurement times to improve consistency
    
    * Remove redundant test
    
    * Refactor push benches
    
    * Refactor push benches again
    
    * Add Pop benchmark
    
    * Fmt
    
    * Add some comments to the benchmarks
    
    * Remove some todos
    
    * Use iter_batched_ref
    
    * Fix pop benchmark name
    
    * Add test for worst case O(log n) push
    
    * Fmt
    
    * Add push test
    
    * Add peek and pop test
    
    * Fix up sift comments and log tests
    
    * Comments
    
    * Add Reverse wrapper type for min heaps
    
    * Fmt
    
    * Peek mut
    
    * Fmt
    
    * Add empty tests
    
    * Check complexity of pushing smallest value
    
    * Test drop clears cells
    
    * Fix stable build
    
    * Basic property test
    
    * Fix wasm build
    
    * Fmt
    
    * Derive Default, PartialEq, Eq
    
    * Add property test to feature
    
    * Fix doc links
    
    * Fmt
    
    * Remove commented out println
    
    * Avoid potential false positive
    
    * Add punctuation
    
    * Comments
    
    * Fmt
    
    * [core] Fix comment
    
    * [core] Remove unnecessary println
    
    * [core] Store two children in one Cell
    
    * [core] Add group_count() for fuzz tests
    
    * [core] Apply cargo fmt
    
    * [core] Fix imports for std env
    
    * [core] Improve comments describing read/write ops
    
    * [core] Improve feature switch
    
    * [core] Improve code readability
    
    * [core] Apply general comments
    
    * [core] Add group.exists() and make more use of Group API
    
    * [core] Major renaming
    
    * [core] Implement AlwaysPacked for Children
    
    * [core] Improve comments and panic messages
    
    * [core] Improve comments
    
    * [core] Improve comments
    
    * [core] Improve comments
    
    * [core] Improve comments
    
    * [core] Improve comments
    
    * [core] Improve comments
    
    * [core] Migrate children.exists() to children.is_empty()
    
    * [core] Fix children.is_empty()
    
    * [core] Bring back PackedLayout impl
    
    * Move binary_heap to crates
    
    * Make it compile
    
    * Fix up doc test and benches
    
    * Fmt
    
    * Fix license headers
    
    * [core] Improve Children API
    
    * [core] Use super instead of crate import
    
    * [core] Fix comments
    
    * [core] Rename Elements to ChildrenVector
    
    * [core] Fix comments
    
    * [core] Fix footprint
    
    * [core] Improve count()
    
    * [core] Move iterator to correct file
    
    * [core] Restrain visibility
    
    * [core] Fix comments
    
    * [core] Fix imports
    
    * [core] Rename ChildrenVector to ChildrenVec
    
    * [core] Improve imports
    
    * [storage] Use crate import instead of super
    
    * [storage] Remove some pub(super)
    
    * [storage] Add #[inline]
    
    * [storage] Rename push_to to insert
    
    * [storage] Add rational for child_count
    
    * [storage] Apply cargo fmt
    
    * [core] Give me back my blank line
    Co-authored-by: Andrew Jones's avatarAndrew Jones <ascjones@gmail.com>
    958dbc1c