I thought to myself that I do this pretty frequently, but then I realized only if I'm going from make -j8 to make -j1. I guess parallelism does throw some indeterminancy into this
The time I was able to make -j 128 and it took 3 minutes to do what used to take an hour, I almost wet myself.
If parallelism adds indeterminacy, then you have a bug (probably in working out the dependency graph.) Not an unusual one - lots of open source in the 1990s had warnings about not building above -j1 because multi-core systems weren't that common and people weren't actually trying it themselves...