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

    Arowx

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

    Soaryn

    Joined:
    Apr 17, 2015
    Posts:
    173
    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

    francois85

    Joined:
    Aug 11, 2015
    Posts:
    469
    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

    DreamingImLatios

    Joined:
    Jun 3, 2017
    Posts:
    204
    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

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    2,160
    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

    Draveler

    Joined:
    Jul 1, 2018
    Posts:
    45