CSY/reowolf Changeset - 685eb9d4ae13 · Centrum Wiskunde & Informatica (CWI)

Changeset - 685eb9d4ae13

Parent rev.

Child rev.

[Not reviewed]

0 1 0

Christopher Esterhuyse - 5 years ago 2020-02-15 14:51:16
christopher.esterhuyse@gmail.com

properties as rows works much better

1 file changed with 43 insertions and 7 deletions:

src/runtime/bits.rs

0 comments (0 inline, 0 general)

src/runtime/bits.rs

➞

Show inline comments

@@ @@ -3,13 +3,13 @@ use crate::common::*; @@
 /// Converts an iterator over contiguous u32 chunks into an iterator over usize
 /// e.g. input [0b111000, 0b11] gives output [3, 4, 5, 32, 33]
 /// observe that the bits per chunk are ordered from least to most significant bits, yielding smaller to larger usizes.
 /// works by draining the inner u32 chunk iterator one u32 at a time, then draining that chunk until its 0.
 struct BitChunkIter<I: Iterator<Item = u32>> {
     chunk_iter: I,
-    next_bit_index: usize,
+    next_bit_index: u32,
     cached: u32,
+}
 impl<I: Iterator<Item = u32>> BitChunkIter<I> {
     fn new(chunk_iter: I) -> Self {
         // first chunk is always a dummy zero, as if chunk_iter yielded Some(0).
@@ @@ -17,13 +17,13 @@ impl<I: Iterator<Item = u32>> BitChunkIter<I> { @@
         // 1. our next_bit_index is always off by 32 (we correct for it in Self::next) (no additional overhead)
         // 2. we cache u32 and not Option<u32>, because chunk_iter.next() is only called in Self::next.
         Self { chunk_iter, next_bit_index: 0, cached: 0 }
+    }
+}
 impl<I: Iterator<Item = u32>> Iterator for BitChunkIter<I> {
-    type Item = usize;
+    type Item = u32;
     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.
+        }
         // assert(chunk > 0);
         // Shift the contents of chunk until the least significant bit is 1.
         // ... being sure to increment next_bit_index accordingly.
         #[inline(always)]
-        fn skip_n_zeroes(chunk: &mut u32, n: usize, next_bit_index: &mut usize) {
+        fn skip_n_zeroes(chunk: &mut u32, n: u32, next_bit_index: &mut u32) {
             if *chunk & ((1 << n) - 1) == 0 {
                 // n least significant bits are zero. skip n bits.
                 *next_bit_index += n;
                 *chunk >>= n;
+            }
+        }
   | |___|___|___|___|
   | |___|___|___|___|
+  |
+  V
  entity chunks (groups of 32)
 */
 // TODO newtypes Entity and Property
 #[derive(Debug, Copy, Clone, Eq, PartialEq)]
 struct Pair {
     entity: u32,
     property: u32,
+}
 impl From<[u32; 2]> for Pair {
@@ @@ -158,13 +161,13 @@ impl BitMatrix { @@
     // the bits NOT in 0..entity_bound
     fn last_row_chunk_mask(entity_bound: u32) -> Option<u32> {
         let zero_prefix_len = entity_bound % 32;
         if zero_prefix_len == 0 {
             None
         } else {
             Some(!0u32 >> zero_prefix_len)
+            Some(!0u32 >> (32 - zero_prefix_len))
+        }
+    }
     fn assert_within_bounds(&self, at: Pair) {
         assert!(at.entity < self.bounds.entity);
         assert!(at.property < self.bounds.property);
+    }
@@ @@ -198,17 +201,42 @@ impl BitMatrix { @@
     fn test(&self, at: Pair) -> bool {
         self.assert_within_bounds(at);
         let [o_of, o_in] = self.offsets_unchecked(at);
         unsafe { (*self.buffer.add(o_of) & 1 << o_in) != 0 }
+    }
     fn iter<'a, 'b>(
     fn batch_mut<'a, 'b>(&mut self, mut chunk_mut_fn: impl FnMut(&'b mut [u32])) {
         let row_chunks = Self::row_chunks(self.bounds.property) as usize;
         let column_chunks = Self::column_chunks(self.bounds.entity);
         let mut ptr = self.buffer;
         for _row in 0..column_chunks {
             let slice;
             unsafe {
                 slice = std::slice::from_raw_parts_mut(ptr, row_chunks);
                 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) };
             for _ in 0..row_chunks {
                 unsafe {
                     *ptr &= mask;
                     ptr = ptr.add(1);
+                }
+            }
+        }
+    }
     fn iter_entities_where<'a, 'b>(
         &'a self,
         buf: &'b mut Vec<u32>,
         mut fold_fn: impl FnMut(&'b [u32]) -> u32,
-    ) -> impl Iterator<Item = usize> + 'b {
+    ) -> 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);
         let mut ptr = self.buffer;
         for _row in 0..column_chunks {
             let slice;
@@ @@ -240,11 +268,19 @@ fn matrix_test() { @@
     m.set([2, 0].into());
     m.set([40, 1].into());
     m.set([40, 2].into());
     m.set([40, 0].into());
     println!("{:?}", &m);
     m.batch_mut(|p| p[0] = !0);
     println!("{:?}", &m);
     let mut buf = vec![];
     for index in m.iter(&mut buf, move |slice| slice[0] ^ slice[1] ^ slice[2]) {
     for index in m.iter_entities_where(&mut buf, move |p| p[0] ^ p[1] ^ p[2]) {
         println!("index {}", index);
+    }
     for index in m.iter_entities_where(&mut buf, move |p| (p[0] | p[1]) & p[2]) {
         println!("index {}", index);
+    }
+}
 // TODO something still a bit screwy with 1s where theere should be zeroes

0 comments (0 inline, 0 general)