Skip to content

Allocate and store B-trees in a shared arena

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT
Notifications You must be signed in to change notification settings

Jakobeha/btree-plus-store

 
 

Repository files navigation

btree-plus-store: B-trees backed by a slab/arena to reduce allocations and increase locality + copyable, immutable B-trees which must be manually dropped

CI Crate information License Documentation

Forked from btree-slab.

Why would you want this?

You have many b-trees, some of which are very tiny, and want to reduce allocations and increase localization by storing them all in the same memory region.

Or you want immutable b-trees which can be Copyd and share the same memory, with the trade-off that you must drop and deallocate their memory via a manually-invoked tracing gc.

What is it?

BTreeMap and BTreeSet with an interface almost identical to standard library (with some additional features), but constructed via new_in(&'a BTreeStore).

BTreeStore is internally an arena allocator, in that it allocates nodes in large fixed-sized regions; but it's also a slab allocator, in that it maintains a linked list of allocated and discarded nodes. This means we get the locality benefits of arena allocation but can also reuse storage by dropped b-trees in new b-trees, although the memory won't get reclaimed (usable outside of b-trees) until the arena is destroyed.

Under the copyable feature: copyable::BTreeMap and copyable::BTreeSet are Copy-able, immutable b-trees created from their mutable counterparts. Once created, the memory associated with the mutable b-trees will no longer be automatically reclaimed (since these can be freely copied, we never know if we are deallocating the last one). Instead, there is an unsafe method tracing_gc, which lets you manually specify the b-trees which are still live, and any other nodes will be deallocated.

use btree_plus_store::{BTreeSet, BTreeStore};
#[cfg(feature = "copyable")]
use btree_plus_store::copyable;

fn main() {
  let store = BTreeStore::new();
  let mut foo_bars: BTreeSet<'_, &'static str> = BTreeSet::new_in(&store);
  let mut alphabeticals: BTreeSet<'_, &'static str> = BTreeSet::new_in(&store);
  
  foo_bars.insert("foo");
  alphabeticals.insert("abc");
  foo_bars.insert("bar");
  alphabeticals.insert("def");
  foo_bars.insert("baz");
  foo_bars.insert("qux");
  alphabeticals.insert("xyz");
  foo_bars.remove(&"baz");
  alphabeticals.remove(&"def");
  for elem in &foo_bars {
      println!("Iterate {}", elem);
  }
  // TODO: retain, drain_filter, intersect, union, difference, and symmetric_difference
  // for elem in alphabeticals.drain_filter(|a| a.starts_with('a')) {
  //     println!("Drain {}", elem);
  // }
  for elem in alphabeticals {
      println!("Consume {}", elem)
  }
    
  #[cfg(feature = "copyable")]
  {
      let foo_bars = copyable::BTreeSet::from(foo_bars);
      let foo_bars2 = foo_bars;
      let foo_bars3 = foo_bars2;
      for elem in &foo_bars {
          assert!(foo_bars2.contains(elem) && foo_bars3.contains(elem));
      }
  }
}

Safety

This library makes heavy use of unsafe, although the non-copyable tests do pass with MIRI. There are tests for most operations and edge cases, but it's still in the early phase. And since with std::collections::BTreeMap and std::collections::BTreeSet are available and better in most cases, it shouldn't be used in production.

Benchmarks

Benchmarks are run for a sequence of operations including insertion, retrieval, iteration, and removal. We vary the # and size of maps and sets.

This library performs slightly faster than std on very small maps and sets, but slower otherwise.

Full Report

1_map_3000_operations 10_maps_300_operations 100_maps_30_operations 1000_maps_3_operations 1_set_3000_operations 10_sets_300_operations 100_sets_30_operations 1000_sets_3_operations

copyable maps and sets are not shown, but their benchmarks should be nearly the same as the non-copyable variants, because they're wrappers.

License

Licensed under either of

at your option.

Forked from btree-slab, which is also dual licensed under Apache 2.0 "or" MIT.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

About

Allocate and store B-trees in a shared arena

Topics

Resources

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • HTML 55.7%
  • Rust 43.9%
  • Shell 0.4%