Editor slows down by ForLoop(I guess).

Question

Hey. I'm getting quite bad Performance on a Custom Editor which saves TreeInstances to Groups.

I'm imagine it's connected to this this for loop.. (But I'm out of Ideas how I could make it different..){ lets say saving 500 TreeInstances takes about 1/2 second. 2500 TreeInstances taking about 2 Seconds. but... all above 5000 take Ages. (Working on a MacPro late 2013) it' freezes Unity for a Moment due to the Saving Process of those Instances.

Ok here is my suspected slow down save code:

 void SaveGroup_CHECK(int TI_INDEX){

         for(int i = 0; i<m_GO_Groups.Length;i++){
             for(int ii = 0; ii < m_GO_Groups[i].m_GameObjects.Count;ii++){
                 for(int iii = 0; iii<m_ted.treePrototypes.Length;iii++){
                     if(m_ted.treeInstances[TI_INDEX].prototypeIndex == iii){
                         if(m_ted.treePrototypes[iii].prefab == m_GO_Groups[i].m_GameObjects[ii]){
                             TreeInstance TI = new TreeInstance();
                             TI = m_ted.treeInstances[TI_INDEX];
                             TI.prototypeIndex = ii;
                             m_TI_Groups[i].m_TreeInstances.Add(TI);
                         }
                     }
                 }
             }
         }
     }

and I've got two Main saving Lists:

 [System.Serializable]public struct list_GameObject {
         [SerializeField]public List<GameObject> m_GameObjects; 
     }
 
 [System.Serializable]public struct list_TreeInstances {
         [SerializeField]public List<TreeInstance> m_GameObjects; 
     }
 
 // like this.
 list_GameObject[] m_GO_Groups;
 list_TreeInstances[] m_TI_Groups;

I could Provide the whole Code if needed..

EDIT:

Ok i have a Custom Editor where you can Create Groups as many you want. In to a group i can Add Prefabs (Trees (TreePrototypes for Unity Terrain)). Now you can select the Groups you want and Load them in to Terrain. The Tree Prefabs are now showing up in the Terrain Component. Now if you Paint Trees on to the Terrain, TreeInstances are created by the Terrain. Those Instances hold the Position, Rotation, Height and more inside of it. But the most Important thing is the TreePrototypeIndex, which allows me to read which Prefab was used for each Instances.

If I change/load different Groups, or Clear out the Terrain, I want to save the TreeInstances in to a List, connected to the Groups I've made. I thought the easiest way is to create foreach Group, which I created a new List.

So in the End on to this Point, I have 2 Main Arrays which hold Lists.

The First Array holds a List of TreePrototypes and the Second Array holds a TreeInstance List. (See the Second Code snippet above).

For Loading I want to call first the List with the Prototypes(Prefabs) and Load them to the Terrain. And then I'm loading the Instances in to Terrain, modifying the TreeInstance.prototypeIndex(int value), so it matches to the Correct TreePrototypes. (If I'd do it reverse, an Error shows Up, that the TreeInstances is lacking a Prototype Index.).

First I worked with a List> but this didn't work out because of I think SerializedProperty isn't able to handle List>.(Didn't figure out how to Digg inside the List with FindPropertyName/Relative)

A Brief board of my Idea

Answer 1

Best Answer

Answer by JVene · Sep 17, 2018 at 07:08 PM

While I don't actually know what TreeInstance is, I assume is otherwise a rather common class, so if that assumption is in error I could run astray on some of this:

I think the true performance issue is this block:

                          TreeInstance TI = new TreeInstance();
                          TI = m_ted.treeInstances[TI_INDEX];
                          TI.prototypeIndex = ii;
                          m_TI_Groups[i].m_TreeInstances.Add(TI);

I expect that the new TreeInstance created for TI is never actually used, as the second line of this block should replace that new instance with that from m_ted.treeInstances[TI_INDEX]. That is to say, in the second line TI is taking a reference to the instance held by m_ted.treeInstances[TI_INDEX], and is not copying the content of that instance into an extant instance held by TI (the new one). Instead, I assume the new instance is immediately dropped.

That would 'thrash' memory management in larger volumes (a few thousand like you've said), creating GC 'hiccups'. I think you can eliminate the first line, merely reducing the first line to:

                          TreeInstance TI = m_ted.treeInstances[TI_INDEX];

I'm just eye-balling here, but that seems the highest impact on performance of this code, but there are a couple of other points to think about.

This line:

                  if(m_ted.treeInstances[TI_INDEX].prototypeIndex == iii)

It appears to me this is searching for an iii that matches a prototype index, but that index is based on TI_INDEX, which doesn't change throughout this function. To my thinking, this makes the loop for iii unnecessary. I think where you consume iii, you could just use the prototype index coming from the entry at TI_INDEX, removing the 'iii' loop. Since this is an interior loop, it is quite magnified relative to impact, but these do run fast in volumes below several thousand, so it is minor.

The overall point about the loop iii, this is a 3 level nested loop, recognizable as a potential cube of volume (though I have no view into the sizes you're running here). When an engineer see's that, we fight for any way we can find to remove the interior loop.

There is also impact on dereferences. In C++, my preferred language, we take great pains against this, but then compilers are fair at figuring these things out. Yet, my point is about this kind of thing:

  m_GO_Groups[i].m_GameObjects[ii]

Here, i is coming from an outer loop, while ii is interior. It can be a waste to calculate the i'th position in m_GO_Groups for every access in the interior loop sequencing ii. In C++ we have fast pointers for this, but in C# there's no great way out. If ii is a large volume, it might pay to use a temporary local reference to m_GO_Groups[i], so that the 'i' is not being calculated and dereferenced at every interior loop. Because of the cost of doing this in C#, I have less experience to assess the 'breakpoint' at which there's a positive return on the investment, but it is worth considering where performance issues crop up.

On the larger issue is the algorithm itself, which I can't gauge. Let me explain. I have no idea why you must form a 3 layer loop like this, but there are classic studies where we're giving such a problem to try to optimize it. Students will attend to those things I've mentioned thus far an ignore the larger problem that might exist, where the algorithm itself may be the flaw. Sometimes there is simply no choice to loop through i entries, testing for each ii rows searching for a match against the iii'th entry in that row, and end up with a n^3 performance, such that there's acceptable performance for n at 10 or 20, but some point marks a line after which the exponential explosion of this loop makes seconds become hours, and then days. In contrived examples in college courses, there may be hidden in the problem a way out, by changing the algorithm. In one study I recall, a method which required 10 seconds at volumes under 1000, but zoomed to hours at a volume of 3000, then literally weeks at volumes over 10,000 was transformed to merely minutes for volumes of 10,000 and an hour or so for 1 million entries, all because there was another way to search and match the data.

I really don't know the algorithm here, beyond a nested search, but I can already see the interior most loop (iii) may not even be required, so I have to wonder what this actually does to see if there's a faster method for performing the work. I just point it out for thought. In some cases, the student cases were situated just so there was no better solution, and the idea is for them to reach that conclusion when (and only when) that's true.

Add comment · Show 17 · Share

dan_wipf · Sep 18, 2018 at 03:30 AM 0

Share

@JVene Thank you for your detailed answer!!!

Well for I explain the case a little bit more:

I can create Groups of GameObjects like something:

Group One: m_GO_Groups[0].m_GameObjects {A,B,C}
Group Two: m_GO_Groups[1].m_GameObjects{D,E}
GroupThree: m_GO_Groups[2].m_GameObjects{F}

Now I load in to Terrain Group 2 and 3.

If I Paint now Trees there are TreeInstances Created which are connected to the GameObjects by an Index(PrototypeIndex)(D = 1, E = 2, F = 3). Now if I save the Groups Again the Instances need to be stored like D = 1, E = 2, F = 1. So if I use them Again there are now complications with which Instance is connected to the GameObject.

Thats where the nested loop is taking place

 if(m_ted.treeInstances[TI_INDEX].prototypeIndex == iii)

I tried now for weeks, but that was the only solution YET that worked properly without any Errors. But as you $$anonymous$$entioned, a costly Solution..

for Loading purpose I use this line:

     public void LoadGroup(){
         ClearTerrain();
         m_TP_ToLoad.Clear();
         m_TI_ToLoad.Clear();
         m_DeleteGroup.Clear();
         m_DeleteGroup.AddRange(m_SelectGroup);
 
         for(int i = 0; i<m_GO_Groups.Length;i++){
             if(m_SelectGroup[i]){
                 foreach(GameObject obj in m_GO_Groups[i].m_GameObjects){
                     TreePrototype TP = new TreePrototype();
                     TP.prefab = obj;
                     m_TP_ToLoad.Add(TP);
                 }
             }
         }
         int c = 0;
         for(int i = 0; i<m_TI_Groups.Length;i++){
             
             if(m_SelectGroup[i]){
                 Debug.Log(m_TI_Groups[i].m_TreeInstances.Count);
                 m_EndCheck += m_TI_Groups[i].m_TreeInstances.Count;
                 List<TreeInstance> t = new List<TreeInstance>();
                 t.AddRange(m_TI_Groups[i].m_TreeInstances);
                 LoadGroup_INSTANCES(t,c);
                 c += m_GO_Groups[i].m_GameObjects.Count;
             }
         }
         
         m_ted.treePrototypes = m_TP_ToLoad.ToArray();
         m_ted.treeInstances = m_TI_ToLoad.ToArray();
         m_ted.RefreshPrototypes();
         m_ter.Flush();
     }
 
 
     void LoadGroup_INSTANCES(List<TreeInstance> t,int c){
         for(int i = 0; i<t.Count;i++){
             TreeInstance TI = t[i];
             TI.prototypeIndex += c;
             m_TI_ToLoad.Add(TI);
             
         }
     }

dan_wipf · Sep 18, 2018 at 09:25 AM 0

Share

Well I tested now a new method. but i still got for 100 TreeInstances / 5 GameObjects, 500 counts inside the nested for loop:

 public void SaveNew(){
         int c = 0;
         for(int i = 0; i<m_SelectGroupLoaded.Count; i++){
             if(m_SelectGroupLoaded[i]){
                 int f = 0;
                 for(int ii = 0; ii<m_GO_Groups[i].m_GameObjects.Count; ii++){
                     List<TreeInstance> m_TI = new List<TreeInstance>();
                     AddToGroup(c,f,m_TI);
                     f++;
                     c++;
                     m_TI_Groups[i].m_TreeInstances.AddRange(m_TI);
                 }
             }
         }
     }
     public void AddToGroup(int INDEX, int TE$$anonymous$$P, List<TreeInstance> m_TI){
         for(int i = 0; i<m_ted.treeInstances.Length;i++){
             Counter++;
             if(m_ted.treeInstances[i].prototypeIndex == INDEX){
                 TreeInstance TI = m_ted.treeInstances[i];
                 TI.prototypeIndex = TE$$anonymous$$P;
                 m_TI.Add(TI);
                 m_ted.treeInstances.ArrayRemoveAt(i);
                 m_ted.treeInstances = m_ted.treeInstances.OrderBy(x => x.prototypeIndex).ToArray();
             }
         }
     }

JVene dan_wipf · Sep 18, 2018 at 05:32 PM 1

Share

$$anonymous$$y time is short today, and a more thoughtful reply will have to wait until I return from my appointments. I'm still not 100% clear on what the algorithm is doing. One $$anonymous$$or confusion for me is m_TI, because when I see it I read "m_" as meaning it is a member, but it isn't (that's what m_ usually is intended to mean). I don't have enough time to unravel the meaning of the algorithm, or it's similarity in purpose to the version posted in your original question. What I see here is that creating a new list inside a loop is going to take quite a bit of time, and sorting in the interior (AddToGroup) wasn't noticed in the first version, so I wonder if that is really required. $$anonymous$$aybe it will be clearer when I have more time to read later.

JVene JVene · Sep 18, 2018 at 11:29 PM 1

Share

@dan_wipf, I've read through again, and here's what I need to be of any serious help, beyond nudging from one vague notion or another; I need you to give a narrative outline of exactly what your plan is. Not the algorithm you're attempting to implement, but your overall (yet detailed) objective(s).

Here's the problem. Position yourself as someone out here, on the other side of the world, trying to understand what you're doing by reading through code you are experimenting with, without the benefit of seeing all that is on your $$anonymous$$d or your total code. In order to really help, I need that vision.

What I understand thus far is there may be thousand of trees, and that something requires you to organize newly painted trees within the extant population, but I don't really understand why or what parameters deter$$anonymous$$e how that organization should be performed. I can sense there may well be considerable optimization possible, but I also sense that is algorithmic, while all I (or anyone) can really do is suggest microscopic observations (nothing on the larger scale).

For example, in the recent post I observe you're sorting and organizing lists inside the interior of what is basically reorganization, but I can't really read the code in a reasonable frame of time to reverse engineer the reasons, purpose and design of that reorganization. It is well known engineering principle that sorting, repeatedly, within the loops show here, is likely a heavy (and very avoidable) series of operations. Typically one attempts to organize materials for one form of organization at the tail end, but until I better understand what really is happening here I can't quite formulate a plan to suggest.

Put another way, in my experience I've frequently written this sort of thing which can handle millions of items in seconds (sometimes even less), but that is often in my preferred language (C++), and often using threads (which may still be a possibility here).

I just need help to be able to help you, to see what really is going on.

For example, this: Group One: m_GO_Groups[0].m_GameObjects {A,B,C} Group Two: m_GO_Groups[1].m_GameObjects{D,E} GroupThree: m_GO_Groups[2].m_GameObjects{F}

I understand that 'F' is group 3 (entry 2), but I don't know why or how your example decides it should become group 1, or what that really means to the organization - does that become A,B,C,F?

Why sort? Is there a lookup purpose, or something else? I ask because sometimes there are containers or methods used for the overall, large scale purpose which could perform much better.

Show more comments

dan_wipf · Oct 03, 2018 at 05:08 PM 0

Share

@JVene if you’re intrested this is my final asset, and it needs some testing :-) thanks again for your help https://forum.unity.com/threads/testing-terrain-prototypes-group-manager.563632/

JVene dan_wipf · Oct 04, 2018 at 02:43 AM 1

Share

Congratulations! I'll check into it, thanks.

dan_wipf JVene · Oct 28, 2018 at 10:08 AM 0

Share

@JVene i’m wondering how i could call Random.Range inside a thread. is it even possible?

Show more comments

Editor slows down by ForLoop(I guess).

1 Reply

Follow this Question

Related Questions