Editor slows down by ForLoop(I guess).

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*.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*.m_GameObjects[ii]){
_
TreeInstance TI = new TreeInstance();_
TI = m_ted.treeInstances[TI_INDEX];
_
TI.prototypeIndex = ii;_
m_TI_Groups.m_TreeInstances.Add(TI);
_ }
}
}
}
}
}
and I’ve got two Main saving Lists:_

[System.Serializable]public struct list_GameObject {
[SerializeField]public List m_GameObjects;
_}*_

[System.Serializable]public struct list_TreeInstances {
[SerializeField]public List 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)
[124834-tpgm-board.png|124834]

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*.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*.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, 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._