From 4976f1816f47e5054ae409d24468b159f3e4420c 2020-02-14 11:41:15 From: Christopher Esterhuyse Date: 2020-02-14 11:41:15 Subject: [PATCH] trying out a matrix representation for components --- diff --git a/src/common.rs b/src/common.rs index 0775b8a025f6c237bd804aa78aa222baf3ffebfe..e7a6037b9085fbbe67ec46ab9eafe6bbf6140448 100644 --- a/src/common.rs +++ b/src/common.rs @@ -2,7 +2,7 @@ pub use core::{ cmp::Ordering, - fmt::Debug, + fmt::{Debug, Formatter}, hash::{Hash, Hasher}, ops::{Range, RangeFrom}, time::Duration, diff --git a/src/runtime/ecs.rs b/src/runtime/ecs.rs index ded78a14e863eb53f3e7df73b7a4052956986ae6..184e8eadaeb5e0ba67bd8628ac3568fe4bb311bf 100644 --- a/src/runtime/ecs.rs +++ b/src/runtime/ecs.rs @@ -1,12 +1,11 @@ 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); impl BitSet { @@ -215,6 +214,23 @@ enum Entity { Machine { state: ProtocolS, component_index: usize }, } +struct PortKey(usize); +struct EntiKey(usize); +struct CompKey(usize); + +struct ComponentInfo { + port_keyset: HashSet, + protocol: Arc, +} +#[derive(Default)] +struct Connection { + ecs: Ecs, + round_solution: Vec<(ChannelId, bool)>, // encodes an ASSIGNMENT + ekey_channel_ids: Vec, // all channel Ids for local keys + component_info: Vec, + endpoint_exts: Vec, +} + /// 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) @@ -222,56 +238,44 @@ enum Entity { /// or in inconsistent (because they are inconsistent) #[derive(Default)] struct Ecs { - component_info: Vec<(Arc, HashSet)>, - entities: Vec, - round_solution: Vec<(ChannelId, bool)>, // encodes an ASSIGNMENT - ekey_channel_ids: Vec, // all channel Ids for local keys - flags: EntityFlags, - ekey_to_channel_id: HashMap, -} -#[derive(Default)] -struct EntityFlags { + entities: Vec, // machines + payloads assignments: HashMap<(ChannelId, bool), BitSet>, payloads: BitSet, - ekeys: HashMap, + ekeys: HashMap, 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 std::fmt::Formatter) -> std::fmt::Result { + fn fmt(&self, f: &mut Formatter) -> std::fmt::Result { let elen = self.entities.len(); write!(f, "{:<30}", "payloads")?; - print_flag_bits(f, &self.flags.payloads, elen)?; + print_flag_bits(f, &self.payloads, elen)?; write!(f, "{:<30}", "inconsistent")?; - print_flag_bits(f, &self.flags.inconsistent, elen)?; + print_flag_bits(f, &self.inconsistent, elen)?; write!(f, "{:<30}", "sync_ended")?; - print_flag_bits(f, &self.flags.sync_ended, elen)?; + print_flag_bits(f, &self.sync_ended, elen)?; write!(f, "{:<30}", "to_run_r")?; - print_flag_bits(f, &self.flags.to_run_r, elen)?; + print_flag_bits(f, &self.to_run_r, elen)?; write!(f, "{:<30}", "to_run_w")?; - print_flag_bits(f, &self.flags.to_run_w, elen)?; + print_flag_bits(f, &self.to_run_w, elen)?; - for (assignment, bitset) in self.flags.assignments.iter() { + for (assignment, bitset) in self.assignments.iter() { write!(f, "{:<30?}", assignment)?; print_flag_bits(f, bitset, elen)?; } - for (ekey, bitset) in self.flags.ekeys.iter() { + for (ekey, bitset) in self.ekeys.iter() { write!(f, "Ekey {:<30?}", ekey)?; print_flag_bits(f, bitset, elen)?; } Ok(()) } } -fn print_flag_bits( - f: &mut std::fmt::Formatter, - bitset: &BitSet, - ecs_keys_end: usize, -) -> std::fmt::Result { - for i in 0..ecs_keys_end { +fn print_flag_bits(f: &mut Formatter, bitset: &BitSet, elen: usize) -> std::fmt::Result { + for i in 0..elen { f.pad(match bitset.test(i) { true => "1", false => "0", @@ -290,30 +294,29 @@ struct Msg { payload: Payload, } -#[test] -fn ecs_test() { - let mut ecs = Ecs::default(); - println!("{:?}", &ecs); -} -impl Ecs { +impl Connection { + fn new_channel(&mut self) -> [PortKey; 2] { + todo!() + } fn round(&mut self) { // 1. at the start of the round we throw away all assignments. // we are going to shift entities around, so all bitsets need to be cleared anyway. - self.flags.assignments.clear(); - self.flags.payloads.clear(); - self.flags.ekeys.clear(); - self.flags.inconsistent.clear(); - self.flags.to_run_r.clear(); - self.flags.to_run_w.clear(); - self.flags.sync_ended.clear(); + self.ecs.assignments.clear(); + self.ecs.payloads.clear(); + self.ecs.ekeys.clear(); + self.ecs.inconsistent.clear(); + self.ecs.to_run_r.clear(); + self.ecs.to_run_w.clear(); + self.ecs.sync_ended.clear(); // 2. We discard all payloads; they are all stale now. // All machines are contiguous in the vector - self.entities + self.ecs + .entities .retain(move |entity| if let Entity::Machine { .. } = entity { true } else { false }); // 3. initially, all the components need a chance to run in MONO mode - self.flags.to_run_r.set_ones_until(self.entities.len()); + self.ecs.to_run_r.set_ones_until(self.ecs.entities.len()); // 4. INVARIANT established: // for all State variants in self.entities, @@ -321,30 +324,30 @@ impl Ecs { // 5. Run all machines in (csb.to_run_r U csb.to_run_w). // Single, logical set is broken into readable / writable parts to allow concurrent reads / writes safely. - while !self.flags.to_run_r.is_empty() { - for _eid in self.flags.to_run_r.iter() { + while !self.ecs.to_run_r.is_empty() { + for _eid in self.ecs.to_run_r.iter() { // TODO run and possbibly manipulate self.to_run_w } - self.flags.to_run_r.clear(); - std::mem::swap(&mut self.flags.to_run_r, &mut self.flags.to_run_w); + self.ecs.to_run_r.clear(); + std::mem::swap(&mut self.ecs.to_run_r, &mut self.ecs.to_run_w); } - assert!(self.flags.to_run_w.is_empty()); + assert!(self.ecs.to_run_w.is_empty()); #[allow(unreachable_code)] // DEBUG 'recv_loop: loop { - let ekey: Key = todo!(); + let ekey: usize = todo!(); let msg: Msg = todo!(); // 1. check if this message is redundant, i.e., there is already an equivalent payload with predicate >= this one. // ie. starting from all payloads // 2. try and find a payload whose predicate is the same or more general than this one // if it exists, drop the message; it is uninteresting. - let ekey_bitset = self.flags.ekeys.get(&ekey); + let ekey_bitset = self.ecs.ekeys.get(&ekey); if let Some(_eid) = ekey_bitset.map(move |ekey_bitset| { let mut slice_builder = vec![]; // collect CONFLICTING assignments into slice_builder for &(channel_id, boolean) in msg.assignments.iter() { - if let Some(bitset) = self.flags.assignments.get(&(channel_id, !boolean)) { + if let Some(bitset) = self.ecs.assignments.get(&(channel_id, !boolean)) { slice_builder.push(bitset.as_slice()); } } @@ -362,7 +365,7 @@ impl Ecs { let mut slice_builder = vec![]; slice_builder.push(ekey_bitset.as_slice()); for assignment in msg.assignments.iter() { - if let Some(bitset) = self.flags.assignments.get(assignment) { + if let Some(bitset) = self.ecs.assignments.get(assignment) { slice_builder.push(bitset.as_slice()); } } @@ -373,51 +376,52 @@ impl Ecs { eid } else { // nothing to overwrite. add a new payload entity. - let eid = self.entities.len(); - self.entities.push(Entity::Payload(msg.payload)); + let eid = self.ecs.entities.len(); + self.ecs.entities.push(Entity::Payload(msg.payload)); for &assignment in msg.assignments.iter() { - let mut bitset = self.flags.assignments.entry(assignment).or_default(); + let mut bitset = self.ecs.assignments.entry(assignment).or_default(); bitset.set(eid); } - self.flags.payloads.set(eid); + self.ecs.payloads.set(eid); eid }; self.feed_msg(payload_eid, ekey); - // TODO run all in self.flags.to_run_w + // TODO run all in self.ecs.to_run_w } } fn run_poly_p(&mut self, machine_eid: usize) { - match self.entities.get_mut(machine_eid) { + match self.ecs.entities.get_mut(machine_eid) { Some(Entity::Machine { component_index, state }) => { // TODO run the machine use PolyBlocker as Pb; let blocker: Pb = todo!(); match blocker { - Pb::Inconsistent => self.flags.inconsistent.set(machine_eid), + Pb::Inconsistent => self.ecs.inconsistent.set(machine_eid), Pb::CouldntCheckFiring(key) => { // 1. clone the machine let state_true = state.clone(); - let machine_eid_true = self.entities.len(); - self.entities.push(Entity::Machine { + let machine_eid_true = self.ecs.entities.len(); + self.ecs.entities.push(Entity::Machine { state: state_true, component_index: *component_index, }); // 2. copy the assignments of the existing machine to the new one - for bitset in self.flags.assignments.values() { + for bitset in self.ecs.assignments.values() { if bitset.test(machine_eid) { bitset.set(machine_eid_true); } } // 3. give the old machine FALSE and the new machine TRUE - let &channel_id = self.ekey_to_channel_id.get(&key).unwrap(); - self.flags + let channel_id = + self.endpoint_exts.get(key.to_raw() as usize).unwrap().info.channel_id; + self.ecs .assignments .entry((channel_id, false)) .or_default() .set(machine_eid); - self.flags + self.ecs .assignments .entry((channel_id, true)) .or_default() @@ -430,9 +434,10 @@ impl Ecs { // 1. make the assignment of this machine concrete WRT its ports let component_info = self.component_info.get(*component_index).unwrap(); - for &channel_id in component_info.1.iter() { + for &ekey in component_info.port_keyset.iter() { + let channel_id = self.endpoint_exts.get(ekey.0).unwrap().info.channel_id; let test = self - .flags + .ecs .assignments .get(&(channel_id, true)) .map(move |bitset| bitset.test(machine_eid)) @@ -440,7 +445,7 @@ impl Ecs { if !test { // TRUE assignment wasn't set // so set FALSE assignment (no effect if already set) - self.flags + self.ecs .assignments .entry((channel_id, false)) .or_default() @@ -448,7 +453,7 @@ impl Ecs { } } // 2. this machine becomes solved - self.flags.sync_ended.set(machine_eid); + self.ecs.sync_ended.set(machine_eid); self.generate_new_solutions(machine_eid); // TODO run this machine to a poly blocker // potentially mark as inconsistent, blocked on some key, or solved @@ -477,6 +482,7 @@ impl Ecs { // this machine already gives an assignment solution_prefix.push(assignment); self.generate_new_solutions_rec(eid, solution_prefix); + solution_prefix.pop(); } else { // this machine does not give an assignment. try both branches! solution_prefix.push(false); @@ -484,8 +490,8 @@ impl Ecs { solution_prefix.pop(); solution_prefix.push(true); self.generate_new_solutions_rec(eid, solution_prefix); + solution_prefix.pop(); } - solution_prefix.pop(); } else { println!("SOLUTION:"); for (channel_id, assignment) in self.ekey_channel_ids.iter().zip(solution_prefix.iter()) @@ -499,35 +505,35 @@ impl Ecs { fn machine_assignment_for(&self, machine_eid: usize, channel_id: ChannelId) -> Option { let test = move |bitset: &BitSet| bitset.test(machine_eid); - self.flags + self.ecs .assignments .get(&(channel_id, true)) .map(test) - .or_else(move || self.flags.assignments.get(&(channel_id, false)).map(test)) + .or_else(move || self.ecs.assignments.get(&(channel_id, false)).map(test)) } - fn feed_msg(&mut self, payload_eid: usize, ekey: Key) { + fn feed_msg(&mut self, payload_eid: usize, ekey: usize) { // 1. identify the component who: // * is blocked on this ekey, // * and has a predicate at least as strict as that of this payload let mut slice_builder = vec![]; let ekey_bitset = - self.flags.ekeys.get_mut(&ekey).expect("Payload sets this => cannot be empty"); + self.ecs.ekeys.get_mut(&ekey).expect("Payload sets this => cannot be empty"); slice_builder.push(ekey_bitset.as_slice()); - for bitset in self.flags.assignments.values() { + for bitset in self.ecs.assignments.values() { // it doesn't matter which assignment! just that this payload sets it too if bitset.test(payload_eid) { slice_builder.push(bitset.as_slice()); } } let chunk_iter = - InAllExceptIter::new(slice_builder.as_slice(), self.flags.payloads.as_slice()); + InAllExceptIter::new(slice_builder.as_slice(), self.ecs.payloads.as_slice()); let mut iter = BitChunkIter::new(chunk_iter); if let Some(machine_eid) = iter.next() { // TODO is it possible for there to be 2+ iterations? I'm thinking No // RUN THIS MACHINE ekey_bitset.unset(machine_eid); - self.flags.to_run_w.set(machine_eid); + self.ecs.to_run_w.set(machine_eid); } } } @@ -608,7 +614,188 @@ ELSE insert this payload with P and K as a new payload, and feed it to any compa ==================== EXTREME approach: 1. entities: {states} U {payloads} -2. flags: {} +2. ecs: {} ================== */ + +struct FlagMatrix { + bytes: *mut u32, + u32s_per_row: usize, + rows: usize, + columns: usize, // conceptually: a column of BITS + // invariant: bytes.len() == rows * columns +} +impl Debug for FlagMatrix { + fn fmt(&self, f: &mut Formatter) -> std::fmt::Result { + for r in 0..self.rows { + write!(f, "|")?; + for c in 0..self.columns { + write!( + f, + "{}", + match self.test(r, c) { + false => '0', + true => '1', + } + )?; + } + write!(f, "|\n")?; + } + Ok(()) + } +} + +#[inline(always)] +fn ceiling_to_mul_32(value: usize) -> usize { + (value + 31) & !31 +} +impl Drop for FlagMatrix { + fn drop(&mut self) { + let layout = Self::layout_for(self.rows, self.u32s_per_row); + unsafe { + //? + std::alloc::dealloc(self.bytes as *mut u8, layout); + } + } +} +impl FlagMatrix { + fn layout_for(rows: usize, u32s_per_row: usize) -> std::alloc::Layout { + let u32s = u32s_per_row * rows; + unsafe { + // this layout is ALWAYS valid: + // 1. size is always nonzero + // 2. size is always a multiple of 4 and 4-aligned + std::alloc::Layout::from_size_align_unchecked(4 * u32s.max(1), 4) + } + } + fn new(rows: usize, columns: usize) -> Self { + let u32s_per_row = ceiling_to_mul_32(columns) / 32; + let layout = Self::layout_for(rows, u32s_per_row); + let bytes = unsafe { + // ? + std::alloc::alloc(layout) + } as *mut u32; + Self { bytes, u32s_per_row, rows, columns } + } + fn assert_within_bounds(&self, row: usize, column: usize) { + assert!(column < self.columns); + assert!(row < self.rows); + } + fn chunk_for(&self, row: usize, column: usize) -> usize { + row * self.u32s_per_row + column / 32 + } + #[inline] + //given: [row, column], return [bytes_index, u32_bit] + fn vec_addr(&self, row: usize, column: usize) -> [usize; 2] { + let bytes_index = self.chunk_for(row, column); + let u32_bit = column % 32; + [bytes_index, u32_bit] + } + fn set(&mut self, row: usize, column: usize) { + self.assert_within_bounds(row, column); + let [bytes_index, u32_bit] = self.vec_addr(row, column); + unsafe { *self.bytes.offset(bytes_index as isize) |= 1 << u32_bit }; + } + fn unset(&mut self, row: usize, column: usize) { + self.assert_within_bounds(row, column); + let [bytes_index, u32_bit] = self.vec_addr(row, column); + unsafe { *self.bytes.offset(bytes_index as isize) &= !(1 << u32_bit) }; + } + fn test(&self, row: usize, column: usize) -> bool { + self.assert_within_bounds(row, column); + let [bytes_index, u32_bit] = self.vec_addr(row, column); + unsafe { *self.bytes.offset(bytes_index as isize) & (1 << u32_bit) != 0 } + } + fn clear(&mut self) { + self.rows = 0; + self.columns = 0; + } + unsafe fn copy_chunk_unchecked(&self, row: usize, nth_col_chunk: usize) -> u32 { + let i = (self.u32s_per_row * row) + nth_col_chunk; + *self.bytes.offset(i as isize) + } +} + +#[derive(Debug, Copy, Clone)] +enum ColumnCombinator<'a> { + Row(usize), + True, + False, + And(&'a ColumnCombinator<'a>, &'a ColumnCombinator<'a>), + Or(&'a ColumnCombinator<'a>, &'a ColumnCombinator<'a>), + Not(&'a ColumnCombinator<'a>), +} +struct FlaggedColumnIter<'a> { + flag_matrix: &'a FlagMatrix, + next_column_chunk: usize, + combinator: &'a ColumnCombinator<'a>, +} +impl<'a> FlaggedColumnIter<'a> { + fn new(flag_matrix: &'a FlagMatrix, combinator: &'a ColumnCombinator<'a>) -> Self { + Self { flag_matrix, combinator, next_column_chunk: 0 } + } + /// #Safety: bounds on self.next_column_chunk have been checked with self.flag_matrix + /// retrieves the column chunk at self.next_column_chunk + unsafe fn combine(&self, c: &ColumnCombinator) -> u32 { + use ColumnCombinator as Cc; + match c { + Cc::Row(row) => self.flag_matrix.copy_chunk_unchecked(*row, self.next_column_chunk), + Cc::False => 0u32, + Cc::True => !0u32, + Cc::And(a, b) => self.combine(a) & self.combine(b), + Cc::Or(a, b) => self.combine(a) | self.combine(b), + Cc::Not(a) => !self.combine(a), + } + } +} +impl<'a> Iterator for FlaggedColumnIter<'a> { + type Item = u32; + fn next(&mut self) -> Option { + struct CombineCtx<'a> { + flag_matrix: &'a FlagMatrix, + nth_col_chunk: usize, + } + if self.next_column_chunk >= self.flag_matrix.u32s_per_row { + None + } else { + let x = unsafe { self.combine(self.combinator) }; + self.next_column_chunk += 1; + Some(x) + } + } +} + +struct ColumnIter<'a> { + bit_chunk_iter: BitChunkIter>, +} +impl<'a> ColumnIter<'a> { + fn new(m: &'a FlagMatrix, combinator: &'a ColumnCombinator) -> Self { + let iter = FlaggedColumnIter::new(m, combinator); + let bit_chunk_iter = BitChunkIter::new(iter); + Self { bit_chunk_iter } + } +} +impl<'a> Iterator for ColumnIter<'a> { + type Item = usize; + fn next(&mut self) -> Option { + let v: Option = self.bit_chunk_iter.next(); + v.filter(|&x| x < self.bit_chunk_iter.chunk_iter.flag_matrix.columns) + } +} + +#[test] +fn matrix() { + let mut m = FlagMatrix::new(2, 10); + m.set(0, 1); + m.set(0, 2); + m.set(1, 2); + m.set(1, 2); + use ColumnCombinator as Cc; + let combinator = Cc::Or(&Cc::Row(0), &Cc::True); + let iter = ColumnIter::new(&m, &combinator); + for c in iter { + println!("{:?}", c); + } + println!("{:?}", &m); +} diff --git a/src/runtime/mod.rs b/src/runtime/mod.rs index e92c928f9546a889a5c5892e135cb11cf1d759d4..1948a0c9e337dba41d0d653ff175ca81a88eb8c3 100644 --- a/src/runtime/mod.rs +++ b/src/runtime/mod.rs @@ -231,7 +231,7 @@ trait Messengerlike { ///////////////////////////////// impl Debug for SolutionStorage { - fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { + fn fmt(&self, f: &mut Formatter) -> std::fmt::Result { f.pad("Solutions: [")?; for (subtree_id, &index) in self.subtree_id_to_index.iter() { let sols = &self.subtree_solutions[index]; @@ -454,7 +454,7 @@ impl Predicate { } } impl Debug for Predicate { - fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { + fn fmt(&self, f: &mut Formatter) -> std::fmt::Result { f.pad("{")?; for (ChannelId { controller_id, channel_index }, &v) in self.assigned.iter() { f.write_fmt(format_args!(