allwpilib
allwpilib copied to clipboard
wpilibsuite
[🛠️] Change Command Scheduler to fix iterator invalidation bugs and get rid of "hacks" in C++ and Java
scheduledCommands.erase() was being called in for(Command* command : scheduledCommands)
this now gets put into a temporary vector (at the size of the set, I do not think all the commands will end in the same for loop but nevertheless it's the size of the set) and erases them after the for loop is done.
Found together with @PeterJohnson.
Wasn't the iteration being done via an iterator (and then the removal also being done through the iterator)?
Sort of. It used a range for, which has an internal iterator. That iterator is invalidated by SmallSet when the current object is removed, which means the for loop next iteration is incrementing from an invalid iterator (UB). Even manually managing the iterators doesn't work with SmallSet, because it can use a vector implementation, which invalidates all iterators, not just the current one. So the only other possible fix would be to use std::set AND manually manage the iterators instead of using range-for.
Java doesn't have this issue--iterator.remove() updates itself in such a way that hasNext() on it is safe for the next loop iteration.
The way robot.py did it seems like a better way to mitigate this issue, and SmallSet<Command*>(scheduledCommands) should create a copy of the smallSet, and I don't think the smallSet will be big enough that this will have a performance impact.
What do you guys think?
I agree that copying scheduledCommands would be the cleaner solution. Some things to remember for whoever implements that:
- Make the same change to Java (I think iterating over
m_scheduledCommands.toArray(new Command[0])would be the most performant way to copy the set) - Add a check to the start of the run loop to skip commands that are no longer scheduled
- Remove the
inRunLoop,toSchedule,toCancelCommands, andtoCancelInterruptorsmember variables
Whatever behavior is being chosen, if it's going to being a part of the "spec", there should be tests that fail currently and pass afterwards added.
Set.copyOf is memory allocation heavy; this is what the implementation is:
return (Set<E>)Set.of(new HashSet<>(coll).toArray());
So it first creates a HashSet, then creates an array of its elements, then creates a Set from that array.
For how we're using it here, toArray() would be more efficient. As a further optimization we could even avoid allocations most of the time by smartly reusing the array.
Note that toArray(T[]) will automatically try to reuse the passed array, so a simple way to reduce allocations would be to update the array with m_composedCommandsCopy = m_composedCommands.toArray(m_composedCommandsCopy). (There's some options we could explore such as the initial array size and growing the array by more than is initially required, but I don't know if it would necessarily be worth it)
Note that
toArray(T[])will automatically try to reuse the passed array, so a simple way to reduce allocations would be to update the array withm_composedCommandsCopy = m_composedCommands.toArray(m_composedCommandsCopy). (There's some options we could explore such as the initial array size and growing the array by more than is initially required, but I don't know if it would necessarily be worth it)
Note also toArray() will null-fill the end elements, not shrink the array, so you will need to look for the first null and exit the loop early if doing this.
synced with main with rebase.
Will write new tests and better optimize currently working on it
fix formatting with rebase + force-push: (I forget to run wpiformat all the time...)
Update the checking for null and isScheduled as discussed in discord with a amend + force-push:
oops did command.isScheduled() instead of isScheduled(command) what a rookie mistake, fixing with force push now
I have added 3 different tests testing weird cases of using the scheduler inside the commands. all 3 fail on the main branch and pass on this branch
What other tests should I add? @Starlight220?
@KangarooKoala: Should we move some of these tests to SchedulingRecursionTest?
I say we move test cancelNextCommandTest for sure and also scheduleCommandInCommand since they are both similar to #4259 but keep commandKnowsWhenEndedTest since it feels more like a CommandScheduler test more than a scheduling recursion.
Any objections?