CSY/reowolf Changeset - 939a6de6ca76 · Centrum Wiskunde & Informatica (CWI)

Changeset - 939a6de6ca76

Parent rev.

Child rev.

[Not reviewed]

0 1 0

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

matrices seem very promising

1 file changed with 40 insertions and 26 deletions:

src/runtime/ecs.rs

0 comments (0 inline, 0 general)

src/runtime/ecs.rs

➞

Show inline comments

 use crate::common::*;
 use crate::runtime::endpoint::EndpointExt;
 use crate::runtime::ProtocolS;
 use std::collections::HashMap;
 /// invariant: last element is not zero.
 /// => all values out of bounds are implicitly absent.
 /// i.e., &[0,1] means {1<<32, 0} while &[0,1] is identical to &[1] and means {1}.
 #[derive(Debug, Default)]
 struct BitSet(Vec<u32>);
 impl BitSet {
     fn as_slice(&self) -> &[u32] {
         self.0.as_slice()
+    }
     fn iter(&self) -> impl Iterator<Item = u32> + '_ {
         self.0.iter().copied()
+    }
     fn is_empty(&self) -> bool {
         // relies on the invariant: no trailing zero u32's
         self.0.is_empty()
+    }
     fn clear(&mut self) {
         self.0.clear();
+    }
     fn set_ones_until(&mut self, mut end: usize) {
         self.0.clear();
         loop {
             if end >= 32 {
                 // full 32 bits of 1
                 self.0.push(!0u32);
             } else {
                 if end > 0 {
                     // #end ones, with a (32-end) prefix of zeroes
                     self.0.push(!0u32 >> (32 - end));
+                }
                 return;
+            }
+        }
+    }
     #[inline(always)]
     fn index_decomposed(index: usize) -> [usize; 2] {
         // [chunk_index, chunk_bit]
         [index / 32, index % 32]
+    }
     fn test(&self, at: usize) -> bool {
         let [chunk_index, chunk_bit] = Self::index_decomposed(at);
         match self.0.get(chunk_index) {
             None => false,
             Some(&chunk) => (chunk & (1 << chunk_bit)) != 0,
+        }
+    }
     fn set(&mut self, at: usize) {
         let [chunk_index, chunk_bit] = Self::index_decomposed(at);
         if chunk_index >= self.0.len() {
             self.0.resize(chunk_index + 1, 0u32);
+        }
         let chunk = unsafe {
             // SAFE! previous line ensures sufficient size
             self.0.get_unchecked_mut(chunk_index)
         };
         *chunk |= 1 << chunk_bit;
+    }
     fn unset(&mut self, at: usize) {
         let [chunk_index, chunk_bit] = Self::index_decomposed(at);
         if chunk_index < self.0.len() {
             let chunk = unsafe {
                 // SAFE! previous line ensures sufficient size
                 self.0.get_unchecked_mut(chunk_index)
             };
             *chunk &= !(1 << chunk_bit);
             while let Some(0u32) = self.0.iter().copied().last() {
                 self.0.pop();
+            }
+        }
+    }
+}
 /// 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,
-    cached: Option<u32>, // None <=> iterator is done
     cached: u32,
+}
 impl<I: Iterator<Item = u32>> BitChunkIter<I> {
     fn new(mut chunk_iter: I) -> Self {
         let cached = chunk_iter.next();
         Self { chunk_iter, next_bit_index: 0, cached }
     fn new(chunk_iter: I) -> Self {
         // first chunk is always a dummy zero, as if chunk_iter yielded Some(0).
         // Consequences:
         // 1. our next_bit_index is always off by 32 (we correct for it in Self::next) (no additional overhead)
         // 2. we don't need to ever cache an Option. We can encounter them in Self::next.
         Self { chunk_iter, next_bit_index: 0, cached: 0 }
+    }
+}
 impl<I: Iterator<Item = u32>> Iterator for BitChunkIter<I> {
     type Item = usize;
     fn next(&mut self) -> Option<Self::Item> {
         loop {
             println!("LOOP");
             // get cached chunk. If none exists, iterator is done.
             let mut chunk = self.cached?;
             if chunk == 0 {
                 // self.next_bit_index jumps to next multiple of 32
         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 is still empty! get the next one...
             chunk = self.chunk_iter.next()?;
             // ... and jump self.next_bit_index to the next multiple of 32.
             self.next_bit_index = (self.next_bit_index + 32) & !(32 - 1);
                 self.cached = self.chunk_iter.next();
                 continue;
+        }
             // this chunk encodes 1+ Items to yield
             // shift the contents of chunk until the least significant bit is 1
         // 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 shifty(chunk: &mut u32, shift_by: usize, next_bit_index: &mut usize) {
+        fn shift_and_inc(chunk: &mut u32, shift_by: usize, next_bit_index: &mut usize) {
             if *chunk & ((1 << shift_by) - 1) == 0 {
                 *next_bit_index += shift_by;
                 *chunk >>= shift_by;
+            }
-                println!("{:#032b}", *chunk);
+            // println!("{:#032b}", *chunk);
+        }
             shifty(&mut chunk, 16, &mut self.next_bit_index);
             shifty(&mut chunk, 08, &mut self.next_bit_index);
             shifty(&mut chunk, 04, &mut self.next_bit_index);
             shifty(&mut chunk, 02, &mut self.next_bit_index);
             shifty(&mut chunk, 01, &mut self.next_bit_index);
         shift_and_inc(&mut chunk, 16, &mut self.next_bit_index);
         shift_and_inc(&mut chunk, 08, &mut self.next_bit_index);
         shift_and_inc(&mut chunk, 04, &mut self.next_bit_index);
         shift_and_inc(&mut chunk, 02, &mut self.next_bit_index);
         shift_and_inc(&mut chunk, 01, &mut self.next_bit_index);
         // least significant bit of chunk is 1.
         // assert(chunk & 1 == 1)
         // prepare our state for the next time Self::next is called.
         // Overwrite self.cached such that its shifted state is retained,
         // and jump over the bit whose index we are about to return.
         self.next_bit_index += 1;
             self.cached = Some(chunk >> 1);
             if chunk > 0 {
                 return Some(self.next_bit_index - 1);
+            }
+        }
         self.cached = chunk >> 1;
         // returned index is 32 smaller than self.next_bit_index because we use an
         // off-by-32 encoding to avoid having to cache an Option<u32>.
         Some(self.next_bit_index - 1 - 32)
+    }
+}
 /// Returns an iterator over chunks of bits where ALL of the given
 /// bitsets have 1.
 struct AndChunkIter<'a> {
     // this value is not overwritten during iteration
     // invariant: !sets.is_empty()
     sets: &'a [&'a [u32]],
     next_chunk_index: usize,
+}
 impl<'a> AndChunkIter<'a> {
     fn new(sets: &'a [&'a [u32]]) -> Self {
         let sets = if sets.is_empty() { &[&[] as &[_]] } else { sets };
         Self { sets, next_chunk_index: 0 }
+    }
+}
 impl Iterator for AndChunkIter<'_> {
     type Item = u32;
     fn next(&mut self) -> Option<u32> {
         let old_chunk_index = self.next_chunk_index;
         self.next_chunk_index += 1;
         self.sets.iter().fold(Some(!0u32), move |a, b| {
             let a = a?;
             let b = *b.get(old_chunk_index)?;
             Some(a & b)
         })
+    }
+}
 #[test]
 fn test_bit_iter() {
     static SETS: &[&[u32]] = &[
         //
         &[0b101001, 0b101001],
         &[0b100001, 0b101001],
     ];
     let iter = BitChunkIter::new(AndChunkIter::new(SETS));
     let indices = iter.collect::<Vec<_>>();
     println!("indices {:?}", indices);
+}
 enum Entity {
     Payload(Payload),
     Machine { state: ProtocolS, component_index: usize },
+}
 struct PortKey(usize);
 struct EntiKey(usize);
 struct CompKey(usize);
 struct ComponentInfo {
     port_keyset: HashSet<PortKey>,
     protocol: Arc<Protocol>,
+}
 #[derive(Default)]
 struct Connection {
     ecs: Ecs,
     round_solution: Vec<(ChannelId, bool)>, // encodes an ASSIGNMENT
     ekey_channel_ids: Vec<ChannelId>,       // all channel Ids for local keys
     component_info: Vec<ComponentInfo>,
     endpoint_exts: Vec<EndpointExt>,
+}
 /// Invariant: every component is either:
 ///        in to_run = (to_run_r U to_run_w)
 ///     or in ONE of the ekeys (which means it is blocked by a get on that ekey)
 ///     or in sync_ended (because they reached the end of their sync block)
 ///     or in inconsistent (because they are inconsistent)
 #[derive(Default)]
 struct Ecs {
     entities: Vec<Entity>, // machines + payloads
     assignments: HashMap<(ChannelId, bool), BitSet>,
     payloads: BitSet,
     ekeys: HashMap<usize, BitSet>,
     inconsistent: BitSet,
     sync_ended: BitSet,
     to_run_r: BitSet, // read from and drained while...
     to_run_w: BitSet, // .. written to and populated. }
+}
 impl Debug for Ecs {
     fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
         let elen = self.entities.len();
         write!(f, "{:<30}", "payloads")?;
         print_flag_bits(f, &self.payloads, elen)?;
         write!(f, "{:<30}", "inconsistent")?;
         print_flag_bits(f, &self.inconsistent, elen)?;
         write!(f, "{:<30}", "sync_ended")?;
         print_flag_bits(f, &self.sync_ended, elen)?;
         write!(f, "{:<30}", "to_run_r")?;
         print_flag_bits(f, &self.to_run_r, elen)?;
         write!(f, "{:<30}", "to_run_w")?;
         print_flag_bits(f, &self.to_run_w, elen)?;

0 comments (0 inline, 0 general)