CSY/reowolf Changeset - 331ce29f6db7 · Centrum Wiskunde & Informatica (CWI)

Changeset - 331ce29f6db7

Parent rev.

Child rev.

[Not reviewed]

1 1 1

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

bit wizardry

3 files changed with 188 insertions and 286 deletions:

src/runtime/ecs.rs

187

src/runtime/mod.rs

src/runtime/polyp.rs

285

0 comments (0 inline, 0 general)

src/runtime/ecs.rs

➞

Show inline comments

@@ new file 100644 @@
 use crate::common::*;
 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 {
     #[inline(always)]
     fn index_decomposed(index: usize) -> [usize; 2] {
         // [chunk_index, chunk_bit]
         [index / 32, index % 32]
+    }
     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();
+            }
+        }
+    }
+}
 #[derive(Debug, Default)]
 struct BitMasks(HashMap<(ChannelId, bool), BitSet>);
 struct BitChunkIter<I: Iterator<Item = u32>> {
     chunk_iter: I,
     next_bit_index: usize,
     cached: Option<u32>, // None <=> iterator is done
+}
 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 }
+    }
+}
 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
                 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
             #[inline(always)]
             fn shifty(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);
+            }
             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);
             // assert(chunk & 1 == 1)
             self.next_bit_index += 1;
             self.cached = Some(chunk >> 1);
             if chunk > 0 {
                 return Some(self.next_bit_index - 1);
+            }
+        }
+    }
+}
 /// 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)
         })
+    }
+}
 /// Returns an iterator over chunks for bits in range 0..bits_to_go but skipping
 /// indices for which ANY of the given bitsets has a 1
 struct NoneChunkIter<'a> {
     // this value is not overwritten during iteration
     // invariant: !sets.is_empty()
     sets: &'a [&'a [u32]],
     next_chunk_index: usize,
     bits_to_go: usize,
+}
 impl<'a> NoneChunkIter<'a> {
     /// a set of bitsets. the u32s of each are in ascending order of significant digits
     /// i.e., &[0,1] means {1<<32, 0} while &[0,1] is identical to &[1] and means {1}.
     fn new(sets: &'a [&'a [u32]], max_bit: usize) -> Self {
         let sets = if sets.is_empty() { &[&[] as &[_]] } else { sets };
         Self { sets, next_chunk_index: 0, bits_to_go: max_bit }
+    }
+}
 impl Iterator for NoneChunkIter<'_> {
     type Item = u32;
     fn next(&mut self) -> Option<u32> {
         let neutral = match self.bits_to_go {
 => None,
             x @ 1..=31 => Some(!0u32 >> (32 - x)),
             _ => Some(!0u32),
         };
         self.bits_to_go = self.bits_to_go.saturating_sub(32);
         let old_chunk_index = self.next_chunk_index;
         self.next_chunk_index += 1;
         self.sets.iter().fold(neutral, 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 _ = BitChunkIter::new(AndChunkIter::new(SETS));
     let iter = BitChunkIter::new(NoneChunkIter::new(SETS, 9));
     let indices = iter.collect::<Vec<_>>();
     println!("indices {:?}", indices);
+}
 enum Entity {
     Payload(Payload),
     State(ProtocolS),
+}
 fn ecs() {
     let entities: Vec<Entity> = Default::default();
     let assignments: HashMap<(ChannelId, bool), BitSet> = Default::default();
     let to_run: BitSet = Default::default();
+}

src/runtime/mod.rs

➞

Show inline comments

 #[cfg(feature = "ffi")]
 pub mod ffi;
 mod actors;
 pub(crate) mod communication;
 pub(crate) mod connector;
 pub(crate) mod endpoint;
 pub mod errors;
 // mod predicate; // TODO later
-mod polyp;
+mod ecs;
 mod serde;
 pub(crate) mod setup;
 pub(crate) type ProtocolD = crate::protocol::ProtocolDescriptionImpl;
 pub(crate) type ProtocolS = crate::protocol::ComponentStateImpl;
 use crate::common::*;
 use actors::*;
 use endpoint::*;
 use errors::*;
 #[derive(Debug, PartialEq)]
 pub(crate) enum CommonSatResult {
     FormerNotLatter,
     LatterNotFormer,
     Equivalent,
     New(Predicate),
     Nonexistant,
+}
 #[derive(Clone, Eq, PartialEq, Hash)]
 pub(crate) struct Predicate {
     pub assigned: BTreeMap<ChannelId, bool>,
+}
 #[derive(Debug, Default)]
 struct SyncBatch {
     puts: HashMap<Key, Payload>,
     gets: HashSet<Key>,
+}
 #[derive(Debug)]
 pub enum Connector {
     Unconfigured(Unconfigured),
     Configured(Configured),
     Connected(Connected), // TODO consider boxing. currently takes up a lot of stack real estate
+}
 #[derive(Debug)]
 pub struct Unconfigured {
     pub controller_id: ControllerId,
+}
 #[derive(Debug)]
 pub struct Configured {
     controller_id: ControllerId,
     polarities: Vec<Polarity>,
     bindings: HashMap<usize, PortBinding>,
     protocol_description: Arc<ProtocolD>,
     main_component: Vec<u8>,
+}
 #[derive(Debug)]
 pub struct Connected {
     native_interface: Vec<(Key, Polarity)>,
     sync_batches: Vec<SyncBatch>,
     controller: Controller,
+}
 #[derive(Debug, Copy, Clone)]
 pub enum PortBinding {
     Native,
     Active(SocketAddr),
     Passive(SocketAddr),
+}
 #[derive(Debug)]
 struct Arena<T> {
     storage: Vec<T>,
+}
 #[derive(Debug)]
 struct ReceivedMsg {
     recipient: Key,
     msg: Msg,
+}
 #[derive(Debug)]
 struct MessengerState {
     poll: Poll,
     events: Events,
     delayed: Vec<ReceivedMsg>,
     undelayed: Vec<ReceivedMsg>,
     polled_undrained: IndexSet<Key>,
+}
 #[derive(Debug)]
 struct ChannelIdStream {
     controller_id: ControllerId,
     next_channel_index: ChannelIndex,
+}
 #[derive(Debug)]
 struct Controller {
     protocol_description: Arc<ProtocolD>,
     inner: ControllerInner,
     ephemeral: ControllerEphemeral,
+}
 #[derive(Debug)]
 struct ControllerInner {
     round_index: usize,
     channel_id_stream: ChannelIdStream,
     endpoint_exts: Arena<EndpointExt>,
     messenger_state: MessengerState,
     mono_n: Option<MonoN>,
     mono_ps: Vec<MonoP>,
     family: ControllerFamily,
     logger: String,
+}
 /// This structure has its state entirely reset between synchronous rounds
 #[derive(Debug, Default)]
 struct ControllerEphemeral {
     solution_storage: SolutionStorage,
     poly_n: Option<PolyN>,
     poly_ps: Vec<PolyP>,
     ekey_to_holder: HashMap<Key, PolyId>,
+}
 #[derive(Debug)]
 struct ControllerFamily {
     parent_ekey: Option<Key>,
     children_ekeys: Vec<Key>,
+}
 #[derive(Debug)]
 pub(crate) enum SyncRunResult {
     BlockingForRecv,
     AllBranchesComplete,
     NoBranches,
+}
 // Used to identify poly actors
 #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
 enum PolyId {
     N,
     P { index: usize },
+}
 #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
 pub(crate) enum SubtreeId {
     PolyN,
     PolyP { index: usize },
     ChildController { ekey: Key },
+}
 pub(crate) struct MonoPContext<'a> {
     inner: &'a mut ControllerInner,
     ekeys: &'a mut HashSet<Key>,
+}
 pub(crate) struct PolyPContext<'a> {
     my_subtree_id: SubtreeId,
     inner: &'a mut ControllerInner,
     solution_storage: &'a mut SolutionStorage,
+}
 impl PolyPContext<'_> {
     #[inline(always)]
     fn reborrow<'a>(&'a mut self) -> PolyPContext<'a> {
         let Self { solution_storage, my_subtree_id, inner } = self;
         PolyPContext { solution_storage, my_subtree_id: *my_subtree_id, inner }
+    }
+}
 struct BranchPContext<'m, 'r> {
     m_ctx: PolyPContext<'m>,
     ekeys: &'r HashSet<Key>,
     predicate: &'r Predicate,
     inbox: &'r HashMap<Key, Payload>,
+}
 #[derive(Default)]
 pub(crate) struct SolutionStorage {
     old_local: HashSet<Predicate>,
     new_local: HashSet<Predicate>,
     // this pair acts as SubtreeId -> HashSet<Predicate> which is friendlier to iteration
     subtree_solutions: Vec<HashSet<Predicate>>,
     subtree_id_to_index: HashMap<SubtreeId, usize>,
+}
 trait Messengerlike {
     fn get_state_mut(&mut self) -> &mut MessengerState;
     fn get_endpoint_mut(&mut self, eekey: Key) -> &mut Endpoint;
     fn delay(&mut self, received: ReceivedMsg) {
         self.get_state_mut().delayed.push(received);
+    }
     fn undelay_all(&mut self) {
         let MessengerState { delayed, undelayed, .. } = self.get_state_mut();
         undelayed.extend(delayed.drain(..))
+    }
     fn send(&mut self, to: Key, msg: Msg) -> Result<(), EndpointErr> {
         self.get_endpoint_mut(to).send(msg)
+    }
     // attempt to receive a message from one of the endpoints before the deadline
     fn recv(&mut self, deadline: Instant) -> Result<Option<ReceivedMsg>, MessengerRecvErr> {

src/runtime/polyp.rs

➞

Show inline comments

deleted file

0 comments (0 inline, 0 general)