Eliminate heap allocations in event dispatching

[edrumwri]

With some care, heap allocations can generally be avoided (excepting a "warm up" phase) as a Systems' State is updated over time- i.e., through integration, discrete updates, and unrestricted updates- at least with regard to the Systems framework code.

Given the following code:

Simulator sim(my_system);
sim.Initialize()

in which any necessary heap allocations can be performed in Initialize(.), and assuming that my_system performs no heap allocations outside of that warm up period, calls to sim.AdvanceTo(t_final) would ideally allocate no heap.

Heap allocations are presently found in the following places (not comprehensive) encountered by AdvanceTo():

drake/systems/analysis/simulator.cc

Line 211 in f20d676

auto merged_events = system_.AllocateCompositeEventCollection();

drake/systems/framework/diagram.cc

Line 857 in f20d676

std::vector<T> times(num_subsystems());

drake/systems/framework/event.h

Line 770 in f20d676

auto event = std::unique_ptr<UnrestrictedUpdateEvent<T>>(this->DoClone());

drake/systems/framework/event_collection.h

Line 380 in f20d676

this->add_event(static_pointer_cast<EventType>(other_event->Clone()));

I'm willing to help eliminate these. Fixing the last two would seem to require a redesign.

[sherm1]

Thanks, @edrumwri !

[rpoyner-tri]

While fiddling with writing a test for simulator/event heap usage, I discovered a fun (but in retrospect obvious) additional problem: std::vectors will reallocate when they overflow. See #14950 (review) for some discussion from the test case PR.

It might be possible to count or estimate the event population at init time, and do the necessary pre-allocations. At worst (yuck), it might be possible to add API for some event collection size hint that a user could supply. Something along these lines would be necessary to completely eliminate the possibility of heap transactions during AdvanceTo().

[sherm1]

I don't think the goal has to be "no heap allocations in AdvanceTo()". We could make it "no heap allocations in AdvanceTo() for typical uses" (which would include Evan's). For that we could reserve (say) 128 entries in the vectors that hold simultaneous events. I believe it would be a rare simulation that would need more, but all that would happen is a single heap allocation and some copying upon the 129th event, after which nothing would happen until there were 257 simultaneous events!

[rpoyner-tri]

Agreed that we could do a fixed pre-allocation that would cover most cases. I'm content to have that as a fallback, and explore the possibility of system-aware estimates when I get to that step.

[rpoyner-tri]

Looks like all of the heap fixes I had are now merged. Closing.