Very Expensive Indirection in Node Lookups

[michaeljfazio]

The following accessors are extremely expensive due to the indirection from keys back to values. Each time they are called, we effectively perform a hash of all items contained in the reference vector and then execute the corresponding hash table search before collecting results. Additionally, these accessors are called very frequently by the default Layers.

• poldercast/src/nodes.rs

  Lines 62 to 67 in f882186

  	pub fn all_available_nodes(&self) -> Vec<&Node> {
  	self.available_nodes()
  	.iter()
  	.filter_map(|id| self.all.get(id))
  	.collect()
  	}

• poldercast/src/nodes.rs

  Lines 74 to 79 in f882186

  	pub fn all_quarantined_nodes(&self) -> Vec<&Node> {
  	self.quarantined_nodes()
  	.iter()
  	.filter_map(|id| self.all.get(id))
  	.collect()
  	}

• poldercast/src/nodes.rs

  Lines 86 to 91 in f882186

  	pub fn all_unreachable_nodes(&self) -> Vec<&Node> {
  	self.unreachable_nodes()
  	.iter()
  	.filter_map(|id| self.all.get(id))
  	.collect()
  	}

If we re-work the data structures to prevent this access pattern we can significantly improve performance of topology processing whilst not impacting the interface of the library too much. For example, this commit shows the early stages of a refactor to the available nodes accessor and underlying data structures.

I'm still fleshing out the details. I'm not too sure about the implications of cloning Node instances into each corresponding lookup. I'm certain a Boxed reference, const *mut, or &'a Node type would be much better performance-wise, and would also be easier to reason about when the collective Node instances are operated on by multiple threads, however the resulting code is far far more complicated due to lifetime details.

Implementation aside, the concept is there.