M Cargo.toml +2 -1
@@ 1,6 1,6 @@
[package]
name = "genmap"
-version = "1.0.2"
+version = "1.0.3"
authors = ["Simon Heath <icefox@dreamquest.io>"]
edition = "2018"
description = "A simple generational map data structure with no dependencies."
@@ 21,6 21,7 @@ maintenance = { status = "experimental"
criterion = "0.3"
slotmap = "0.4"
handy = "0.1"
+generational-arena = "0.2"
[[bench]]
name = "bench_basic"
M benches/bench_basic.rs +75 -0
@@ 14,6 14,7 @@ use criterion::Criterion;
use genmap;
use handy;
use slotmap;
+use generational_arena as ga;
fn insert_elems(c: &mut Criterion) {
static KB: usize = 1024;
@@ 55,6 56,14 @@ fn insert_elems(c: &mut Criterion) {
}
});
});
+ group.bench_with_input(BenchmarkId::new("generational_arena", size), size, |b, &size| {
+ b.iter(|| {
+ let map = &mut ga::Arena::new();
+ for i in 0..size {
+ map.insert(i);
+ }
+ });
+ });
}
group.finish();
}
@@ 116,6 125,18 @@ fn insert_and_remove_elems(c: &mut Crite
}
});
});
+ group.bench_with_input(BenchmarkId::new("generational_arena", size), size, |b, &size| {
+ let map = &mut ga::Arena::new();
+ b.iter(|| {
+ let keys = &mut vec![];
+ for i in 0..size {
+ keys.push(map.insert(i));
+ }
+ for i in keys {
+ map.remove(*i);
+ }
+ });
+ });
}
group.finish();
}
@@ 177,6 198,19 @@ fn remove_elems(c: &mut Criterion) {
}
});
});
+
+ group.bench_with_input(BenchmarkId::new("generational_arena", size), size, |b, &size| {
+ let map = &mut ga::Arena::new();
+ let keys = &mut vec![];
+ for i in 0..size {
+ keys.push(map.insert(i));
+ }
+ b.iter(|| {
+ for i in keys.iter() {
+ map.remove(*i);
+ }
+ });
+ });
}
group.finish();
}
@@ 249,6 283,22 @@ fn insert_lookup_and_remove_elems(c: &mu
}
});
});
+
+ group.bench_with_input(BenchmarkId::new("generational_arena", size), size, |b, &size| {
+ let map = &mut ga::Arena::new();
+ b.iter(|| {
+ let keys = &mut vec![];
+ for i in 0..size {
+ keys.push(map.insert(i));
+ }
+ for i in keys.iter() {
+ let _ = black_box(map.get(*i));
+ }
+ for i in keys {
+ map.remove(*i);
+ }
+ });
+ });
}
group.finish();
}
@@ 309,6 359,19 @@ fn lookup_elems(c: &mut Criterion) {
}
});
});
+
+ group.bench_with_input(BenchmarkId::new("generational_arena", size), size, |b, &size| {
+ let map = &mut ga::Arena::new();
+ let keys = &mut vec![];
+ for i in 0..size {
+ keys.push(map.insert(i));
+ }
+ b.iter(|| {
+ for i in keys.iter() {
+ let _ = black_box(map.get(*i));
+ }
+ });
+ });
}
group.finish();
}
@@ 370,6 433,18 @@ fn iterate_full_list(c: &mut Criterion)
}
});
});
+
+ group.bench_with_input(BenchmarkId::new("generational_arena", size), size, |b, &size| {
+ let map = &mut ga::Arena::new();
+ for i in 0..size {
+ map.insert(i);
+ }
+ b.iter(|| {
+ for (i, _) in map.iter() {
+ let _ = black_box(map.get(i));
+ }
+ });
+ });
}
group.finish();
}
M src/lib.rs +32 -33
@@ 1,36 1,35 @@
-/// A Rust crate for a generational map, handle map, whatever you want to
-/// call it. Whatever it is, this is a random-access data structure that
-/// stores an unordered bag of items and gives you a handle for each
-/// specific item you insert. Looking things up by handle is `O(1)` --
-/// the backing storage is just a `Vec` -- and items can be removed as
-/// well, which is also `O(1)`. Handles are small (two `usize`'s) and
-/// easy to copy, similar to a slice. The trick is that there is a
-/// generation number stored with each item, so that a "dangling"
-/// handle that refers to an item that has been removed is invalid.
-/// Unlike array indices, if you remove an item from the array and a new
-/// one gets put in its place, the old stale handle does not refer to the
-/// new one and trying to use it will fail at runtime.
-///
-/// This is useful for various things: managing lots of uniform things
-/// with shared ownership (such as video game resources), interning
-/// strings, that sort of thing. Essentially by using handles to items
-/// you have runtime-checked memory safety: you can get an item from the
-/// map using the handle, since it's basically just an array index.
-///
-/// In practice this is not unrelated to `Rc`, it's just that `Rc` does
-/// the accounting of memory on cloning the `Rc`, and this does it on
-/// "dereferencing" by looking up an object's handle. Referencing
-/// counting, threading garbage collection and this sort of map are all
-/// different methods of achieving the same thing (checking for memory
-/// safety at runtime) with different tradeoffs. With a reference count
-/// you don't have to explicitly free items and can't have stale handles,
-/// but loops require special handling and you pay for the accounting cost
-/// on cloning a handle. With this you have to free items explicitly, but
-/// stale handles can be safely detected and the accounting happens when
-/// you look the item up. You can also use it as a slab allocator type
-/// thing, where you pre-allocate a large amount of storage and free it
-/// all at once.
-
+//! A Rust crate for a generational map, handle map, whatever you want to
+//! call it. Whatever it is, this is a random-access data structure that
+//! stores an unordered bag of items and gives you a handle for each
+//! specific item you insert. Looking things up by handle is `O(1)` --
+//! the backing storage is just a `Vec` -- and items can be removed as
+//! well, which is also `O(1)`. Handles are small (two `usize`'s) and
+//! easy to copy, similar to a slice. The trick is that there is a
+//! generation number stored with each item, so that a "dangling"
+//! handle that refers to an item that has been removed is invalid.
+//! Unlike array indices, if you remove an item from the array and a new
+//! one gets put in its place, the old stale handle does not refer to the
+//! new one and trying to use it will fail at runtime.
+//!
+//! This is useful for various things: managing lots of uniform things
+//! with shared ownership (such as video game resources), interning
+//! strings, that sort of thing. Essentially by using handles to items
+//! you have runtime-checked memory safety: you can get an item from the
+//! map using the handle, since it's basically just an array index.
+//!
+//! In practice this is not unrelated to `Rc`, it's just that `Rc` does
+//! the accounting of memory on cloning the `Rc`, and this does it on
+//! "dereferencing" by looking up an object's handle. Referencing
+//! counting, threading garbage collection and this sort of map are all
+//! different methods of achieving the same thing (checking for memory
+//! safety at runtime) with different tradeoffs. With a reference count
+//! you don't have to explicitly free items and can't have stale handles,
+//! but loops require special handling and you pay for the accounting cost
+//! on cloning a handle. With this you have to free items explicitly, but
+//! stale handles can be safely detected and the accounting happens when
+//! you look the item up. You can also use it as a slab allocator type
+//! thing, where you pre-allocate a large amount of storage and free it
+//! all at once.
/// A small, easy-to-copy handle referring to a location in
/// a particular `GenMap`.