Search Unity

How to make List<List<T>> access Burst friendly?

Discussion in 'Data Oriented Technology Stack' started by Tony_Max, Sep 8, 2019.

  1. Tony_Max

    Tony_Max

    Joined:
    Feb 7, 2017
    Posts:
    63
    I have some data in my project that i want to store in List<List<T>>. I use enum to easly access to this data.
    Code (CSharp):
    1. public static class GameInfo {
    2.     static Faction[] factions;
    3. }
    4.  
    5. public class Faction {
    6.     List<List<Memory>> memory;
    7.  
    8.     void AddMemory(MemoryType memType, Memory mem) {
    9.         memory[(int)memType].Add(mem);
    10.     }
    11. }
    12.  
    13. enum MemoryType {
    14.     Wood,
    15.     Stone,
    16.     Building
    17. }
    I want to access GameInfo.faction[int].memory[(int)MemoryType] in a bursted job. So i somehow need to use native collections. I can't simply write NativeList<NativeList<Memory>>. I see only 2 ways how to implement what i want.
    1. Prepare data before scheduling job (tranform c# List to NativeList/NativeArray). The problem is i don't know what MemoryType and even what Faction i need to prepare outside of a job, so i need to prepare all (in my case every frame).
    2. Refuse to use perfect AddMemory(MemoryType, Memory) and rewrite to something like this (also will need to have single NativeList<Memory> for every MemoryType.
      Code (CSharp):
      1. void AddMemory(MemoryType memType, Memory mem)
      2. {
      3.     switch(memType)
      4.     {
      5.         case Wood:
      6.             woodMemory.Add(mem);
      7.             break;
      8.         case Stone:
      9.             stoneMemory.Add(mem);
      10.             break;
      11.         case Building:
      12.             buildingMemory.Add(mem);
      13.             break;
      14.     }
      15. }
    Maybe u can make me an advise how to implement what i want.
     
  2. DreamingImLatios

    DreamingImLatios

    Joined:
    Jun 3, 2017
    Posts:
    424
    This seems like you really want a NativeMultiHashmap or the entity equivalent which is a dynamic buffer of entities with dynamic buffers.
     
    MostHated likes this.
  3. recursive

    recursive

    Joined:
    Jul 12, 2012
    Posts:
    591
    You can also have a 1d array of your data and an array of ints to define the ranges
     
  4. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,393
    If your second dimension size is constant, for each element of first dimension, I would go with NativeArray.
    It is easy to access this way, any desired element of your 1D array with an index offset.
     
  5. Tony_Max

    Tony_Max

    Joined:
    Feb 7, 2017
    Posts:
    63
    Storing so many levels of data inside NativeMultiHashMap is a very slow way, cause every moment that i need to extract data i need to iterate through huge NativeMultiHashMap.
    Using entities with DynamicBuffer<Entities> of entities, which have DynamicBuffer<Memory> (Memory also store an Entity, so there is so much ENTITY:confused:) replicates this idea, but to extract data i will need to prepare it outside of a job, or to use too many CDFE/BFE.
    i thought about this, but i have no idea how to store all this levels of data (faction -> memoryType -> memory) in 1d array, when i need to dynamicly add/remove from lower level.
    No, i have no constant size of this lists
     
    Last edited: Sep 8, 2019
  6. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,393
    If you need iterate through second dimensions (2nd) as well and you have undefined size of thay second dimensions, you could make 1st dimension as entities, and 2nd as buffer arrays.
    Also, in such case, you could use Native Hash map as 1st dimension to access entities.
    Depending what you are doing with 2D array.

    So basically, you create storage entity to hold stone, with buffer.
    Then storage entities with wood, buildings, metal, etc.
    This way you can nicely 'burst' it.
     
    wobes likes this.
  7. DreamingImLatios

    DreamingImLatios

    Joined:
    Jun 3, 2017
    Posts:
    424
    If you don't want to use Entities, your best option is to create your own NativeContainer that uses an UnsafeList of UnsafeLists.
     
  8. Tony_Max

    Tony_Max

    Joined:
    Feb 7, 2017
    Posts:
    63
    NativeContainers is blackboxes for me, but i will try to learn and implement my own. Good idea, thank u)
     
  9. DreamingImLatios

    DreamingImLatios

    Joined:
    Jun 3, 2017
    Posts:
    424
    You can look at the source code of Unity.Collections to see how to do it. Unity.Physics also has a couple of custom containers as additional examples.
     
  10. Enzi

    Enzi

    Joined:
    Jan 28, 2013
    Posts:
    199
    Why are we in the DOTS forum and I read nothing about components, like:
    entity:
    - resourceComponent
    - factionComponent

    I'm sorry, what you currently have is terrible data design even for OOP.
     
  11. DreamingImLatios

    DreamingImLatios

    Joined:
    Jun 3, 2017
    Posts:
    424
    ECS are just one portion of DOTS. Some people have existing projects non-DOTS and want to speed up an expensive aspect only. So they will look towards the other parts of DOTS, Jobs and Burst to get a speedup. And if entities help, entities help. And those people are definitely welcome on the DOTS forum.

    But in this case, I suspect the data is being built from SOs or something and then needs to get brought into the ECS world as read-only data. But I'm just speculating and trying to directly answer the question asked.
     
  12. Tony_Max

    Tony_Max

    Joined:
    Feb 7, 2017
    Posts:
    63
    DOTS is not only components. In this thread we discussed NativeContainers, Entities, DynamicBuffers, CDFE/BFE, Jobs, Burst, still not DOTS?
    Why? Can u give some advises?
    Not certainly in that way. Some logic accumulates data in List<List<T>> and some another logic needs to access data depends on MemoryType. I have no need to update or something this data, only add/remove, so i see no need to use entities and components for this, just singleton as static class and static field.
     
  13. recursive

    recursive

    Joined:
    Jul 12, 2012
    Posts:
    591
    Do the individual elements need to be ordered?
    You could get away with NativeMultiHashMap<MemoryType, T>, If there are multiple T's per MemoryType.

    Another alternative is each memory type has an index offset and a range computed when you setup your Data. Especially if it's static or precomputed once/infrequently.
    Or you have separate stable NativeArrays, and a lookup system that returns a void pointer* to that arrays memory you can then cast to the appropriate T*, if T is only structs you're willing to play with unsafe code.
     
  14. DreamingImLatios

    DreamingImLatios

    Joined:
    Jun 3, 2017
    Posts:
    424
    How exactly do you need to index the List<List<Memory>>? Are you using int2 or are you doing searches?

    Another option, while I would argue isn't as great as the other options proposed but might give you the syntax you like, is to use T4 to generate a struct with a bunch of NativeLists that also has a custom indexer to pick the NativeList.
     
  15. Tony_Max

    Tony_Max

    Joined:
    Feb 7, 2017
    Posts:
    63
    No need in order.
    But i need to somehow store multiple NativeMultiHashMap<MemoryType, T> per faction (which have dynamic count).
    Yeap, but my data isn't static =)
    I just need to access inner list by MemoryType, and i do it like
    Code (CSharp):
    1. List<Memory> GetMemory(MemoryType memType) {
    2.    return memory[(int)memType];
    3. }
    Yeah, thought about something like that. But it's plan B for me =)
     
  16. tim_jones

    tim_jones

    Unity Technologies

    Joined:
    May 2, 2019
    Posts:
    19
    Do you need to access the list of factions itself inside a Burst-compiled job? If not, you could retrieve the faction outside the job, and pass just the NativeMultiHashMap<MemoryType, T> to the job.
     
  17. Tony_Max

    Tony_Max

    Joined:
    Feb 7, 2017
    Posts:
    63
    Yes, i need. Probably i explained my task terribly
     
  18. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,393
    Is there any reason, you can not use Entities as factions, in which faction store buffers, of each type of resources?
     
  19. Enzi

    Enzi

    Joined:
    Jan 28, 2013
    Posts:
    199
    No, because I think no one understands your use-case or what you actually want to achieve with this. I see no reason for such tightly packed data, it can be decoupled, that's pretty much all there is. If you want to get better feedback, you need to lay out your assumptions what brought you to the conclusion to make it like that and what the actual data transformations are.

    What will the bursted job do?
     
  20. Tony_Max

    Tony_Max

    Joined:
    Feb 7, 2017
    Posts:
    63
    Because i don't want to use BufferFromEntity.
    Ok. In game units knows about objects in a world. When units see object i add it to memory and remove it after they not see object anymore. In bursted job i want to get collection of memory within MemoryType. I store memory by MemoryType cause algorithms that use it are different. If data not separated i need to prepare it every time i need it.
     
    Last edited: Sep 9, 2019
  21. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,393
    Why is that? What is wrong with it?
    I use it completely fine, with 10s of thousands of entities cases, on 5 years old PC rig.

    I think you need describe a bit more, what are your concerns?
     
  22. Tony_Max

    Tony_Max

    Joined:
    Feb 7, 2017
    Posts:
    63
    I think that use case of CDFE/BFE is when you have to access entitie data not linear and you have no another way. And i thought that it's very slow. It seems like i'm wrong.
     
  23. DreamingImLatios

    DreamingImLatios

    Joined:
    Jun 3, 2017
    Posts:
    424
    It has a random access penalty which is slower, but you already have that with the outer List picking the inner List. There is still the Entity lookup when using a BufferFromEntity, so at worst case you'll have a 2x performance hit compared to a NativeJaggedList2D implementation.
     
  24. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,393
    If I were you, I would specifically stress test, to see what you can get and what you can expect in terms of performance.
    As once someone mentioned, you most likely will find multiple ways, to get improved optimization.


    @Tony_Max if you could determine expected max size of the arrays, for each resource per faction, that could save you lot of pain, as simply you could have fixed sized linearized 1D array.

    Is this something you can potentially do?
     
  25. Tony_Max

    Tony_Max

    Joined:
    Feb 7, 2017
    Posts:
    63
    That is what i decided to do.
    It must be dynamic and i can't make it fixed size
     
  26. Enzi

    Enzi

    Joined:
    Jan 28, 2013
    Posts:
    199
    I see, the usage makes more sense now but you're running into an unsolvable dilemma with having that type of data in heap memory.
    So, solving this problem with a native block is certainly possible but the data is too intertwined to make it one single block and reasonable if it gets any bigger.

    Here are some suggestions if you really don't want to deal with ECS (although I think you should):
    - MemorySystem: (not a real job/componentsystem)
    Has a (huge) static NativeList of memory. Every memory gets an ID, this is not the array index but a value that just gets incremented.
    static methods to add/remove

    - jobs:
    If you need burst you can write them in such a way that they write to 2 different arrays, one for removal, one for adding.
    Actual adding/removing is then done on the main thread and use the MemorySystem.
    NativeList.AsArray can be used to feed the job.

    About factions, those are a game specific categorizations and therefore not good in code. You're better off giving the memories a reference to the faction or a simple integer value instead of making them dependent on each other.
     
  27. Tony_Max

    Tony_Max

    Joined:
    Feb 7, 2017
    Posts:
    63
    Thank you all very much for the response. Especially @Enzi and @Antypodish. Your answers made me think. I decided go with ECS and use chains of DynamicBuffers. Will test performance when it will be ready.