Search Unity

  1. Unity 2019.1 is now released.
    Dismiss Notice

As entities are inherently multi-threaded what is the best sorting algorithm?

Discussion in 'Data Oriented Technology Stack' started by Arowx, May 18, 2019.

  1. Arowx


    Nov 12, 2009
    As entities are inherently multi-threaded what is the best sorting algorithm or is entity sorting built into DOTS?
    francois85 likes this.
  2. Soaryn


    Apr 17, 2015
    What kind of answer are you looking for? Even generalized sorting algorithms have there operation time dependent on the scenario of the data.
  3. francois85


    Aug 11, 2015
    I was picturing sorting like Intel TBB: parallel_sort() but that has its own set of problems. I would think this is more on the Jobs side of thing since it appears very similar to TBB . But how it all come together I have no idea, I don’t enough about the systems
    Last edited: May 18, 2019
  4. DreamingImLatios


    Jun 3, 2017
    Are you looking to sort the entities and then lock their chunks? If so, multithreading isn't as big of an issue as much as getting their final positions in place without having to add and remove components or something.

    Because entities can have a lot of components attached to them, it is better to extract a key and index and sort those than perform swaps on the full entity payload.

    Step 1: IJobForEachWithEntity to extract the keys and indices.
    Step 2: Sort the keys with indices as the payload. Unity has a built-in sort which is a generic comparison unstable sort. If your sorting criteria is numeric like mine typically is, you can beat it with a radix sort. If this process is still too expensive in an IJob with Burst, then you will have to do some magic to intelligently partition your data to multi-thread the sort without creating a sync point on the main thread.
    Step 3: Generate an array of chunk indices and indices inside of chunks for 0 to EntityCount.
    Step 4: Generate another array like in Step 3 except map it to the original entity ordering.
    Step 5: Use EntityManager.SwapComponents or ExclusiveEntityTransaction.SwapComponents to swap the entities in order of the sorted index array. You also need to swap the elements in the array from Step 4 to track the positions.

    I'm sure in doing the above you may find some optimizations and shortcuts along the way. Steps 1-4 can all be in Burst jobs, so take advantage of that.
  5. snacktime


    Apr 15, 2013
    Googling map reduce sort will give some good insight into how this problem is often tackled. It's not a new problem and it has been somewhat generalized. Although the normal context is big data where the work is spread over multiple servers as well as cores.
  6. Draveler


    Jul 1, 2018