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> {
         // try get something buffered
         if let Some(x) = self.get_state_mut().undelayed.pop() {
             return Ok(Some(x));
+        }
         loop {
             // polled_undrained may not be empty
             while let Some(eekey) = self.get_state_mut().polled_undrained.pop() {
                 if let Some(msg) = self.get_endpoint_mut(eekey).recv()? {
                     // this endpoint MAY still have messages! check again in future
                     self.get_state_mut().polled_undrained.insert(eekey);
                     return Ok(Some(ReceivedMsg { recipient: eekey, msg }));
+                }
+            }
             let state = self.get_state_mut();
             match state.poll_events(deadline) {
                 Ok(()) => {
                     for e in state.events.iter() {
                         state.polled_undrained.insert(Key::from_token(e.token()));
+                    }
+                }
                 Err(PollDeadlineErr::PollingFailed) => return Err(MessengerRecvErr::PollingFailed),
                 Err(PollDeadlineErr::Timeout) => return Ok(None),
+            }
+        }
+    }
+}
 /////////////////////////////////
 impl Debug for SolutionStorage {
     fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
         f.pad("Solutions: [")?;
         for (subtree_id, &index) in self.subtree_id_to_index.iter() {
             let sols = &self.subtree_solutions[index];
             f.write_fmt(format_args!("{:?}: {:?}, ", subtree_id, sols))?;
+        }
         f.pad("]")
+    }
+}
 impl From<EvalErr> for SyncErr {
     fn from(e: EvalErr) -> SyncErr {
         SyncErr::EvalErr(e)
+    }
+}
 impl From<MessengerRecvErr> for SyncErr {
     fn from(e: MessengerRecvErr) -> SyncErr {
         SyncErr::MessengerRecvErr(e)
+    }
+}
 impl From<MessengerRecvErr> for ConnectErr {
     fn from(e: MessengerRecvErr) -> ConnectErr {
         ConnectErr::MessengerRecvErr(e)
+    }
+}
 impl From<EndpointErr> for MessengerRecvErr {
     fn from(e: EndpointErr) -> MessengerRecvErr {
         MessengerRecvErr::EndpointErr(e)
+    }
+}
 impl<T> Default for Arena<T> {
     fn default() -> Self {
         Self { storage: vec![] }
+    }
+}
 impl<T> Arena<T> {
     pub fn alloc(&mut self, t: T) -> Key {
         self.storage.push(t);
         Key::from_raw(self.storage.len() as u64 - 1)
+    }
     pub fn get(&self, key: Key) -> Option<&T> {
         self.storage.get(key.to_raw() as usize)
+    }
     pub fn get_mut(&mut self, key: Key) -> Option<&mut T> {
         self.storage.get_mut(key.to_raw() as usize)
+    }
     pub fn type_convert<X>(self, f: impl FnMut((Key, T)) -> X) -> Arena<X> {
         Arena { storage: self.keyspace().zip(self.storage.into_iter()).map(f).collect() }
+    }
     pub fn iter(&self) -> impl Iterator<Item = (Key, &T)> {
         self.keyspace().zip(self.storage.iter())
+    }
     pub fn len(&self) -> usize {
         self.storage.len()
+    }
     pub fn keyspace(&self) -> impl Iterator<Item = Key> {
         (0..(self.storage.len() as u64)).map(Key::from_raw)
+    }
+}
 impl ChannelIdStream {
     fn new(controller_id: ControllerId) -> Self {
         Self { controller_id, next_channel_index: 0 }
+    }
     fn next(&mut self) -> ChannelId {
         self.next_channel_index += 1;
         ChannelId { controller_id: self.controller_id, channel_index: self.next_channel_index - 1 }
+    }
+}
 impl MessengerState {
     // does NOT guarantee that events is non-empty
     fn poll_events(&mut self, deadline: Instant) -> Result<(), PollDeadlineErr> {
         use PollDeadlineErr::*;
         self.events.clear();
         let poll_timeout = deadline.checked_duration_since(Instant::now()).ok_or(Timeout)?;
         self.poll.poll(&mut self.events, Some(poll_timeout)).map_err(|_| PollingFailed)?;
         Ok(())
+    }
+}
 impl From<PollDeadlineErr> for ConnectErr {
     fn from(e: PollDeadlineErr) -> ConnectErr {
         match e {
             PollDeadlineErr::Timeout => ConnectErr::Timeout,
             PollDeadlineErr::PollingFailed => ConnectErr::PollingFailed,
+        }
+    }
+}
 impl std::ops::Not for Polarity {
     type Output = Self;
     fn not(self) -> Self::Output {
         use Polarity::*;
         match self {
             Putter => Getter,
             Getter => Putter,
+        }
+    }
+}
 impl Predicate {
     // returns true IFF self.unify would return Equivalent OR FormerNotLatter
     pub fn satisfies(&self, other: &Self) -> bool {
         let mut s_it = self.assigned.iter();
         let mut s = if let Some(s) = s_it.next() {
+            s
         } else {
             return other.assigned.is_empty();
         };
         for (oid, ob) in other.assigned.iter() {
             while s.0 < oid {
                 s = if let Some(s) = s_it.next() {
+                    s
                 } else {
                     return false;
                 };
+            }
             if s.0 > oid || s.1 != ob {
                 return false;
+            }
+        }
         true
+    }
     /// Given self and other, two predicates, return the most general Predicate possible, N
     /// such that n.satisfies(self) && n.satisfies(other).
     /// If none exists Nonexistant is returned.
     /// If the resulting predicate is equivlanet to self, other, or both,
     /// FormerNotLatter, LatterNotFormer and Equivalent are returned respectively.
     /// otherwise New(N) is returned.
     pub fn common_satisfier(&self, other: &Self) -> CommonSatResult {
         use CommonSatResult::*;
         // iterators over assignments of both predicates. Rely on SORTED ordering of BTreeMap's keys.
         let [mut s_it, mut o_it] = [self.assigned.iter(), other.assigned.iter()];
         let [mut s, mut o] = [s_it.next(), o_it.next()];
         // lists of assignments in self but not other and vice versa.
         let [mut s_not_o, mut o_not_s] = [vec![], vec![]];
         loop {
             match [s, o] {
                 [None, None] => break,
                 [None, Some(x)] => {
                     o_not_s.push(x);
                     o_not_s.extend(o_it);
                     break;
+                }
                 [Some(x), None] => {
                     s_not_o.push(x);
                     s_not_o.extend(s_it);
                     break;
+                }
                 [Some((sid, sb)), Some((oid, ob))] => {
                     if sid < oid {
                         // o is missing this element
                         s_not_o.push((sid, sb));
                         s = s_it.next();
                     } else if sid > oid {
                         // s is missing this element
                         o_not_s.push((oid, ob));
                         o = o_it.next();
                     } else if sb != ob {
                         assert_eq!(sid, oid);
                         // both predicates assign the variable but differ on the value

src/runtime/polyp.rs

➞

Show inline comments

deleted file

0 comments (0 inline, 0 general)