CSY/reowolf Changeset - 333f1e2197ac · Centrum Wiskunde & Informatica (CWI)

Changeset - 333f1e2197ac

Parent rev.

Child rev.

[Not reviewed]

0 2 0

Christopher Esterhuyse - 5 years ago 2020-02-20 16:22:32
christopher.esterhuyse@gmail.com

removing btreesets

2 files changed with 97 insertions and 44 deletions:

src/runtime/experimental/bits.rs

src/runtime/experimental/vec_storage.rs

0 comments (0 inline, 0 general)

src/runtime/experimental/bits.rs

➞

Show inline comments

@@ @@ -13,51 +13,52 @@ pub const fn usize_bits() -> usize { @@
     usize_bytes() * 8
+}
 pub const fn usizes_for_bits(bits: usize) -> usize {
     (bits + (usize_bits() - 1)) / usize_bits()
+}
 pub(crate) struct BitChunkIter<I: Iterator<Item = usize>> {
 type Chunk = usize;
 type BitIndex = usize;
 pub(crate) struct BitChunkIter<I: Iterator<Item = Chunk>> {
     cached: usize,
     chunk_iter: I,
-    next_bit_index: u32,
+    next_bit_index: BitIndex,
+}
-impl<I: Iterator<Item = usize>> BitChunkIter<I> {
+impl<I: Iterator<Item = Chunk>> BitChunkIter<I> {
     pub fn new(chunk_iter: I) -> Self {
         // first chunk is always a dummy zero, as if chunk_iter yielded Some(FALSE).
         // Consequences:
         // 1. our next_bit_index is always off by usize_bits() (we correct for it in Self::next) (no additional overhead)
-        // 2. we cache usize and not Option<usize>, because chunk_iter.next() is only called in Self::next.
+        // 2. we cache Chunk and not Option<Chunk>, because chunk_iter.next() is only called in Self::next.
         Self { chunk_iter, next_bit_index: 0, cached: 0 }
+    }
+}
 impl<I: Iterator<Item = usize>> Iterator for BitChunkIter<I> {
     type Item = u32;
 impl<I: Iterator<Item = Chunk>> Iterator for BitChunkIter<I> {
     type Item = BitIndex;
     fn next(&mut self) -> Option<Self::Item> {
         let mut chunk = self.cached;
         // loop until either:
         // 1. there are no more Items to return, or
         // 2. chunk encodes 1+ Items, one of which we will return.
         while chunk == 0 {
             // chunk has no bits set! get the next one...
             chunk = self.chunk_iter.next()?;
             // ... and jump self.next_bit_index to the next multiple of usize_bits().
             self.next_bit_index =
                 (self.next_bit_index + usize_bits() as u32) & !(usize_bits() as u32 - 1);
             self.next_bit_index = (self.next_bit_index + usize_bits()) & !(usize_bits() - 1);
+        }
         // there exists 1+ set bits in chunk
         // assert(chunk > 0);
         // Until the least significant bit of chunk is 1:
         // 1. shift chunk to the right,
         // 2. and increment self.next_bit_index accordingly
         // effectively performs a little binary search, shifting 32, then 16, ...
         // TODO perhaps there is a more efficient SIMD op for this?
-        const N_INIT: u32 = usize_bits() as u32 / 2;
+        const N_INIT: BitIndex = usize_bits() / 2;
         let mut n = N_INIT;
         while n >= 1 {
             // n is [32,16,8,4,2,1] on 64-bit machine
             // this loop is unrolled with release optimizations
             let n_least_significant_mask = (1 << n) - 1;
             if chunk & n_least_significant_mask == 0 {
         // and jump over the bit whose index we are about to return.
         self.next_bit_index += 1;
         self.cached = chunk >> 1;
         // returned index is usize_bits() smaller than self.next_bit_index because we use an
         // off-by-usize_bits() encoding to avoid having to cache an Option<usize>.
-        Some(self.next_bit_index - 1 - usize_bits() as u32)
         Some(self.next_bit_index - 1 - usize_bits())
+    }
+}
 /*  --properties-->
      ___ ___ ___ ___
     |___|___|___|___|
@@ @@ -246,14 +247,13 @@ impl BitMatrix { @@
                 ptr = ptr.add(row_chunks);
+            }
             chunk_mut_fn(slice);
+        }
         if let Some(mask) = Self::last_row_chunk_mask(self.bounds.entity) {
             // TODO TEST
             let mut ptr =
                 unsafe { self.buffer.add((column_chunks - 1) as usize * row_chunks as usize) };
             let mut ptr = unsafe { self.buffer.add((column_chunks - 1) * row_chunks) };
             for _ in 0..row_chunks {
                 unsafe {
                     *ptr &= mask;
                     ptr = ptr.add(1);
+                }
+            }
@@ @@ -265,13 +265,13 @@ impl BitMatrix { @@
     /// 2. a _fold function_ for combining the properties of a given entity
     ///    and returning a new derived property (working )
     fn iter_entities_where<'a, 'b>(
         &'a self,
         buf: &'b mut Vec<usize>,
         mut fold_fn: impl FnMut(&'b [BitChunk]) -> BitChunk,
-    ) -> BitChunkIter<std::vec::Drain<'b, usize>> {
+    ) -> impl Iterator<Item = u32> + 'b {
         let buf_start = buf.len();
         let row_chunks = Self::row_chunks(self.bounds.property as usize);
         let column_chunks = Self::column_chunks(self.bounds.entity as usize);
         let mut ptr = self.buffer;
         for _row in 0..column_chunks {
             let slice;
@@ @@ -283,13 +283,13 @@ impl BitMatrix { @@
             let chunk = fold_fn(slice);
             buf.push(chunk.0);
+        }
         if let Some(mask) = Self::last_row_chunk_mask(self.bounds.entity) {
             *buf.iter_mut().last().unwrap() &= mask;
+        }
         BitChunkIter::new(buf.drain(buf_start..))
+        BitChunkIter::new(buf.drain(buf_start..)).map(|x| x as u32)
+    }
+}
 use derive_more::*;
 #[derive(
     Debug, Copy, Clone, BitAnd, Not, BitOr, BitXor, BitAndAssign, BitOrAssign, BitXorAssign,

src/runtime/experimental/vec_storage.rs

➞

Show inline comments

 use super::bits::{usize_bits, BitChunkIter};
 use crate::common::*;
 use core::mem::MaybeUninit;
 use std::collections::BTreeSet;
 #[derive(Default)]
 struct Bitvec(Vec<usize>);
 impl Bitvec {
     #[inline(always)]
     fn offsets_of(i: usize) -> [usize; 2] {
         [i / usize_bits(), i % usize_bits()]
+    }
     // assumes read will not go out of bounds
     unsafe fn insert(&mut self, i: usize) {
         let [o_of, o_in] = Self::offsets_of(i);
         let chunk = self.0.get_unchecked_mut(o_of);
         *chunk |= 1 << o_in;
+    }
     // assumes read will not go out of bounds
     unsafe fn remove(&mut self, i: usize) -> bool {
         let [o_of, o_in] = Self::offsets_of(i);
         let chunk = self.0.get_unchecked_mut(o_of);
         let singleton_mask = 1 << o_in;
         let was = (*chunk & singleton_mask) != 0;
         *chunk &= !singleton_mask;
         was
+    }
     // assumes read will not go out of bounds
     unsafe fn contains(&self, i: usize) -> bool {
         let [o_of, o_in] = Self::offsets_of(i);
         (*self.0.get_unchecked(o_of) & (1 << o_in)) != 0
+    }
     fn pop_first(&mut self) -> Option<usize> {
         let i = self.first()?;
         unsafe { self.remove(i) };
         Some(i)
+    }
     fn iter(&self) -> impl Iterator<Item = usize> + '_ {
         BitChunkIter::new(self.0.iter().copied()).map(|x| x as usize)
+    }
     fn first(&self) -> Option<usize> {
         self.iter().next()
+    }
+}
 // A T-type arena which:
 // 1. does not check for the ABA problem
 // 2. imposes the object keys on the user
 // 3. allows the reservation of a space (getting the key) to precede the value being provided.
 //
@@ @@ -12,16 +52,17 @@ use std::collections::BTreeSet; @@
 // 2. vacant: uninitialized. may be reused implicitly. won't be dropped.
 // 2. reserved: uninitialized. may be occupied implicitly. won't be dropped.
 // invariant A: elements at indices (0..data.len()) / vacant / reserved are occupied
 // invariant B: reserved & vacant = {}
 // invariant C: (vacant U reserved) subset of (0..data.len)
 // invariant D: last element of data is not in VACANT state
 // invariant E: number of allocated bits in vacant and reserved >= data.len()
 pub struct VecStorage<T> {
     data: Vec<MaybeUninit<T>>,
     vacant: BTreeSet<usize>,
     reserved: BTreeSet<usize>,
     vacant: Bitvec,
     reserved: Bitvec,
+}
 impl<T> Default for VecStorage<T> {
     fn default() -> Self {
         Self { data: Default::default(), vacant: Default::default(), reserved: Default::default() }
+    }
+}
@@ @@ -39,15 +80,15 @@ impl<T: Debug> Debug for VecStorage<T> { @@
                     FmtT::Reserved => write!(f, "Reserved"),
                     FmtT::Occupied(t) => write!(f, "Occupied({:?})", t),
+                }
+            }
+        }
         let iter = (0..self.data.len()).map(|i| {
-            if self.vacant.contains(&i) {
+            if unsafe { self.vacant.contains(i) } {
                 FmtT::Vacant
-            } else if self.reserved.contains(&i) {
+            } else if unsafe { self.reserved.contains(i) } {
                 FmtT::Reserved
             } else {
                 // 2. Invariant A => reading valid ata
                 unsafe {
                     // 1. index is within bounds
                     // 2. i is occupied => initialized data is being dropped
@@ @@ -63,49 +104,56 @@ impl<T> Drop for VecStorage<T> { @@
         self.clear();
+    }
+}
 impl<T> VecStorage<T> {
     // ASSUMES that i in 0..self.data.len()
     unsafe fn get_occupied_unchecked(&self, i: usize) -> Option<&T> {
-        if self.vacant.contains(&i) || self.reserved.contains(&i) {
         if self.vacant.contains(i) || self.reserved.contains(i) {
             None
         } else {
             // 2. Invariant A => reading valid ata
             Some(&*self.data.get_unchecked(i).as_ptr())
+        }
+    }
     // breaks invariant A: returned index is in NO state
     fn pop_vacant(&mut self) -> usize {
-        if let Some(i) = pop_set_arb(&mut self.vacant) {
+        if let Some(i) = self.vacant.pop_first() {
+            i
         } else {
             let bitsets_need_another_chunk = self.data.len() % usize_bits() == 0;
             if bitsets_need_another_chunk {
                 self.vacant.0.push(0usize);
                 self.reserved.0.push(0usize);
+            }
             self.data.push(MaybeUninit::uninit());
             self.data.len() - 1
+        }
+    }
     //////////////
     pub fn clear(&mut self) {
         for i in 0..self.data.len() {
             if !self.vacant.contains(&i) && !self.reserved.contains(&i) {
             // SAFE: bitvec bounds ensured by invariant E
             if unsafe { !self.vacant.contains(i) && !self.reserved.contains(i) } {
                 // invariant A: this element is OCCUPIED
                 unsafe {
                     // 1. by construction, i is in bounds
                     // 2. i is occupied => initialized data is being dropped
                     drop(self.data.get_unchecked_mut(i).as_ptr().read());
+                }
+            }
+        }
         self.vacant.clear();
         self.reserved.clear();
         self.vacant.0.clear();
         self.reserved.0.clear();
+    }
     pub fn iter(&self) -> impl Iterator<Item = &T> {
         (0..self.data.len()).filter_map(move |i| unsafe { self.get_occupied_unchecked(i) })
+    }
     pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
         (0..self.data.len()).filter_map(move |i| unsafe {
             if self.vacant.contains(&i) || self.reserved.contains(&i) {
             // SAFE: bitvec bounds ensured by invariant E
             if self.vacant.contains(i) || self.reserved.contains(i) {
                 None
             } else {
                 // 2. Invariant A => reading valid ata
                 Some(&mut *self.data.get_unchecked_mut(i).as_mut_ptr())
+            }
         })
@@ @@ -117,30 +165,33 @@ impl<T> VecStorage<T> { @@
             unsafe {
                 // index is within bounds
                 self.get_occupied_unchecked(i)
+            }
+        }
+    }
     pub fn get_mut_occupied(&mut self, i: usize) -> Option<&mut T> {
         if i >= self.data.len() || self.vacant.contains(&i) || self.reserved.contains(&i) {
     pub fn get_occupied_mut(&mut self, i: usize) -> Option<&mut T> {
         // SAFE: bitvec bounds ensured by invariant E
         if i >= self.data.len() || unsafe { self.vacant.contains(i) || self.reserved.contains(i) } {
             None
         } else {
             unsafe {
                 // 1. index is within bounds
                 // 2. Invariant A => reading valid ata
                 Some(&mut *self.data.get_unchecked_mut(i).as_mut_ptr())
+            }
+        }
+    }
     pub fn new_reserved(&mut self) -> usize {
         let i = self.pop_vacant(); // breaks invariant A: i is in NO state
         self.reserved.insert(i); // restores invariant A
                                    // SAFE: bitvec bounds ensured by invariant E
         unsafe { self.reserved.insert(i) }; // restores invariant A
+        i
+    }
     pub fn occupy_reserved(&mut self, i: usize, t: T) {
         assert!(self.reserved.remove(&i)); // breaks invariant A
         // SAFE: bitvec bounds ensured by invariant E
         assert!(unsafe { self.reserved.remove(i) }); // breaks invariant A
         unsafe {
             // 1. invariant C => write is within bounds
             // 2. i WAS reserved => no initialized data is being overwritten
             self.data.get_unchecked_mut(i).as_mut_ptr().write(t)
             // restores invariant A
         };
@@ @@ -153,18 +204,20 @@ impl<T> VecStorage<T> { @@
             self.data.get_unchecked_mut(i).as_mut_ptr().write(t)
             // restores invariant A
         };
+        i
+    }
     pub fn vacate(&mut self, i: usize) -> Option<T> {
         if i >= self.data.len() || self.vacant.contains(&i) {
         // SAFE: bitvec bounds ensured by invariant E
         if i >= self.data.len() || unsafe { self.vacant.contains(i) } {
             // already vacant. nothing to do here
             return None;
+        }
         // i is certainly within bounds of self.data
         let value = if self.reserved.remove(&i) {
         // SAFE: bitvec bounds ensured by invariant E
         let value = if unsafe { self.reserved.remove(i) } {
             // no data to drop
             None
         } else {
             // invariant A => this element is OCCUPIED!
             unsafe {
                 // 1. index is within bounds
@@ @@ -179,53 +232,53 @@ impl<T> VecStorage<T> { @@
             // pops at least once:
             while let Some(_) = self.data.pop() {
                 let pop_next = self
                     .data
                     .len()
                     .checked_sub(1)
                     .map(|index| self.vacant.remove(&index))
                     .map(|index| unsafe {
                         // SAFE: bitvec bounds ensured by invariant E
                         self.vacant.remove(index)
                     })
                     .unwrap_or(false);
                 if !pop_next {
                     break;
+                }
+            }
         } else {
             // ... by populating self.vacant.
             self.vacant.insert(i);
             // SAFE: bitvec bounds ensured by invariant E
             unsafe { self.vacant.insert(i) };
+        }
         value
+    }
     pub fn iter_reserved(&self) -> impl Iterator<Item = usize> + '_ {
         self.reserved.iter().copied()
+    }
+}
 fn pop_set_arb(s: &mut BTreeSet<usize>) -> Option<usize> {
     if let Some(&x) = s.iter().next() {
         s.remove(&x);
         Some(x)
     } else {
         None
         self.reserved.iter()
+    }
+}
 #[test]
 fn vec_storage() {
     #[derive(Debug)]
     struct Foo;
     impl Drop for Foo {
         fn drop(&mut self) {
             println!("DROPPING FOO!");
+        }
+    }
     let mut v = VecStorage::default();
     let i0 = v.new_occupied(Foo);
     println!("{:?}", &v);
     let i1 = v.new_reserved();
     println!("{:?}", &v);
     let q = v.vacate(i0);
     println!("q {:?}", q);
     println!("{:?}", &v);
     v.occupy_reserved(i1, Foo);
     println!("{:?}", &v);
     *v.get_occupied_mut(i1).unwrap() = Foo;
     println!("{:?}", &v);
+}

0 comments (0 inline, 0 general)