Speed up plan access

[k88hudson-cfa]

Profiling large simulation sizes (1,000,000+) shows a decent amount of time spent in accessing plans:

Given plans have sequential ids, perhaps we could speed things up by using a better data structure than a HashMap?

ixa/src/plan.rs

Lines 127 to 146 in d98a7f5

	pub fn get_next_plan(&mut self) -> Option<Plan<T>> {
	trace!("getting next plan");
	loop {
	// Pop from queue until we find a plan with data or queue is empty
	match self.queue.pop() {
	Some(entry) => {
	// Skip plans that have been cancelled and thus have no data
	if let Some(data) = self.data_map.remove(&entry.plan_id) {
	return Some(Plan {
	time: entry.time,
	data,
	});
	}
	}
	None => {
	return None;
	}
	}
	}
	}

[RobertJacobsonCDC]

Definitely worth investigating.

Plans are stored in two distinct structures internally:

1. The plan queue, Queue::queue, which is a priority queue implemented using a std::collections::BinaryHeap.
2. The plan data map, Queue:data_map, which stores the handler that is called at plan execution, implemented using a HashMap.

The data map is the mechanism by which we cancel plans: to cancel a plan, remove it from the data map. Some alternatives worth benchmarking:

• Store the handler inline, and use a marker field for plan cancellation. This requires that we search the queue whenever we want to cancel a plan, which is fast but not O(1).
• Disallow plan cancelation. Might not be as crazy as it sounds if we move to a wrapper closure that performs alive checks for people. Is this our only use case for plan cancelation?
• Use a more clever data structure for storing data map data. It's not clear what this would be.

As for the queue itself, we do need something that is philosophically a priority queue, but a BinaryHeap is certainly not the only way to implement one. This is probably the easiest thing to experiment with—just swap out the data structure and measure.

It's not obvious to me that we can just stick things in a vector, because we are removing the plans for execution according to the lixicographic ordering of the tuple (scheduled_time, execution_phase, plan_id). BUT sometimes the thing that seems like the most inefficient is actually the fastest in practice. If we knew we only have ~10 plans scheduled at once, I would actually expect linearly scanning a vector to find the next plan to execute to be the fastest! But what if we have 100 plans? 1000 plans? When do more sophisticated data structures start to win? You always have to measure.