I have been having issues trying to get a particular use case to schedule efficiently. I would love some insight into how I could potentially get it working better.
I am trying to jobify the A* algorithm. I have been successful, with zero garbage been generated, however the performance is not good due to the difficulty of scheduling the work.
If you look at the pseudocode on the Wikipedia page (A* search algorithm - Wikipedia), I have implemented the “for each neighbor of current” as a parallel for with a job that runs before it to do the setup for a “step” of the algorithm and another job that runs afterwards to update the data structures given the results of the parallel for. I was originally trying to update the data structures as part of the parallel for, but given the issues I have described on another thread ( NativeHashMap.Concurrent Replace ), I was unable to do this. In any case, this solution should be fine.
So with those 2+num_neighbours jobs, a single step of the algorithm runs well, in parallel, and is fast. The issue is scheduling work for further steps of the algorithm.
My first thought was to create and schedule dynamically from within the final job in the “step”. That would be ideal as it is at that point that we know whether we need to run the algorithm again. However, as documented (https://github.com/Unity-Technologies/EntityComponentSystemSamples/blob/master/Documentation/content/scheduling_a_job_from_a_job.md) this is not allowed.
My next approach was to double buffer jobs so that once I scheduled the chain of jobs for a single “step”, I would build the jobs for the next step and pre-emptively schedule it, with a dependency to the last one. With simple changes to the jobs to effectively no-op if by the time they were run they were not needed, this worked, but gave no speed up as the jobs ran way faster than the set-up time on the main thread for the next set of jobs.
So I decided to expand this idea and schedule batches of “steps” with the required dependencies, again using the double buffering approach so the next batch could be created while the jobs are running. This works, and if I manage to guess the correct number of steps to batch together, the job completes very fast. However, if we do need to schedule another batch of work, we again end up waiting for the main thread to build the jobs to be scheduled. In fact, this approach scales worse than the previous approach with the amount of time we wait for the main thread getting worse and worse as the batch size is increased.
At this point I looked into what exactly was taking the time on the main thread. Virtually all that time was in calls to JobHandle.Schedule. Each batch has batch_size*3 calls to that function, with each taking a single job handle to depend on.
At this point I am fairly stuck. I did try reusing jobs where after first time I create and schedule a batch, I simply schedule the head item of the previously created batch providing a new dependency, however when I do this, only the job that I schedule is run, not the dependants that had previously been set up. I guess that once a job has been scheduled, the dependency information is thrown away by the underlying system and so it can’t be re-used? To be honest, I wasn’t really expecting this one to work, but it would be nice if you did not always have to re-schedule every job in a chain over and over again.
The final thing I am going to try now is collapsing the 3 jobs in each “step” into a single job so that I have less work to schedule in the hope that the main thread can then keep up with scheduling work to keep the job system singing.
I’m really hoping that I have missed something obvious that someone can point me towards to improve this use case?
Thanks,
Kieran