Repository navigation
Trajectories should be deque, not lists (while generating) #1099
Description
When looking over #1066 I noticed that when the engine is running backwards we are adding to the trajectory via:
trajectory.insert(0, snapshot.reversed)
This is slow, and becomes slower when the list is longer. As we are only ever appending to the trajectory on the ends, the appropriate data structure should be deque instead.
Access by index becomes slower (especially in the middle) so that might need to be handled. Ideally a trajectory would be a deque while running/generating and converting them to a list when finalizing.
Activity
sroet commentedon Jan 17, 2022
Here are some runs for the 1000-10_000 range (more typical for trajectories)
1000
10_000
dwhswenson commentedon Jan 17, 2022
True, but is there any reason to believe that this is a performance bottleneck in real-world use? I think that we have enough overhead in other places that we'd get better performance improvements elsewhere.
An update for this would be welcome, but I don't think it's urgently required (so I probably won't implement it, personally).
One note: some aspects around the
DynamicsEngine.generateandDynamicsEngine.iter_generateare likely to be significantly changed in 2.0. First part of that change in #1042, but I'm also don't particularly like the wayDynamicsEngine.generatedoes thisfor trajectory in it: passthing -- it seems wasteful to create an entire new trajetory object that we just throw away over and over again (overhead of UUIDs, etc). I'm open to significant changes in that for OPS 2.0, such as returning an iterator of snapshots instead of trajectories and only wrapping it in a trajectory in thegeneratemethod.sroet commentedon Jan 18, 2022
I would guess so as well (outside of strange toy-engines that are both fast and generate long trajectories). This was just a thing I noticed when looking over that PR and I made this issue to get it off my (mental) list. I agree that this should not have any priority.