3 files changed, 109 insertions(+), 34 deletions(-)

M Cargo.toml
M benches/bench_basic.rs
M src/lib.rs
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`.