Question Help with garbage collection / memory allocation

I'm working on a procedural terrain generator.

I'm going to simplify how my code works and hopefully that's enough. I'm lacking an inutituve understanding of garbage collection and memory allocation and need help identifying what I need to target.

First I had this:

Code (CSharp):

1. mesh.vertices = vertices2.ToArray();
2. mesh.triangles = triangles2.ToArray();

where vertices2 is a list of Vector3s, and triangles2 is a list of integers. These list can be very long, tens of thousands to almost two hundred thousand entries long. This of had quite the impact on my performance as I found in the profiler, where ToArray was causing significant hangups.

I then read that arrays are more performant than lists. Conveniently I actually start and end with arrays - both vertices2 and triangles2 are assembled from many little arrays, the problem is the final length of vertices2 and triangles2 is variable so lists are used, then converted back to arrays.

I changed my code two ways to try and never go to lists. First I tried just combining each new little array into a new array with for loops:

Code (CSharp):

1.             triangles2 = new int[triangles2.Length + verticesAndTriangles.Item2.Length]; // triangles2 is a new empty array, with a length of its last length plus the new length
2.  
3.             for (int i = 0; i < triangles2Additive.Length; i++) // fill in the old triangles first. For the first time this will be 0 and will not run.
4.             {
5.                 triangles2[i] = triangles2Additive[i];
6.                 k++;
7.             }
8.  
9.             for (int i = 0; i < verticesAndTriangles.Item2.Length; i++) // now for the new triangles, add them to the bottom of the main list
10.             {
11.                 triangles2[k + i] = verticesAndTriangles.Item2[i];
12.             }
13.  
14.             triangles2Additive = triangles2; // set the array to be used next time
15.             k = 0;

If you're able to help me with this overall problem, you may see that this is remarkably worse. I could barely get this to run because of the number of for loop iterations (I think).

I then replaced the for loops with Array.Copy:

Code (CSharp):

1.             triangles2 = new int[triangles2.Length + verticesAndTriangles.Item2.Length]; // triangles2 is a new empty array, with a length of its last length plus the new length
2.  
3.             Array.Copy(verticesAndTriangles.Item2, 0, triangles2, (triangles2.Length-verticesAndTriangles.Item2.Length), verticesAndTriangles.Item2.Length);
4.             Array.Copy(triangles2Additive, 0, triangles2, 0, triangles2Additive.Length);
5.  
6.             triangles2Additive = triangles2; // set the array to be used next time

This time it's still running worse than it was before. In the profiler, GC.Collect is taking tons of time. When I was using lists, GC.Collect didn't even show up.


My questions:
Any suggestions on how I can do this more efficiently? Do you need more information to determine what I'm doing poorly? And, is there a way I can work with these arrays more efficiently, or is just using the lists still my most efficient option?

 

https://learn.microsoft.com/en-us/dotnet/standard/design-guidelines/guidelines-for-collections

 

In what context? It is important to understand why something is like that or not.

As @AngryProgrammer posted you create new array (object) that must be collected by GC at some point.
Usually to avoid allocation you try to use the same array or list which is basically wrapper for array that manages resize for you.

First of all there are other methods to make it better, for example SetVertices() that takes list as parameter and I guess it copies data directly, so I think you should at least get rid of that allocation.

Second, probably even faster way would be to use NativeArray, but you would need to know the size of elements in advance or you can use NativeList (you need collections package) then cast to native array, but in this case it does not allocate additional managed memory, plus it blits the data, so should be fast.

Third, if you use List, try to create it with some capacity, becuase every time you exceed the capacity it must create new array and copy all elements and if you have 10.000+ elements it happens at least several times. Obviously do not create new list every time, but clear and reuse the previous one.

Fourth, if you really want to maximize performence there are specialized functions to do that.

 

Thank you both for the advice.

This was very helpful, I switched to SetVertices(), SetTriangles(), and SetNormals() using the lists as the inputs and it's running better that way. I'll give your other advice a shot probably later when I'm forced to optimize further.

In my context I do know the capacity before I start filling the lists, but the capacity is changing all the time. Is it worth it to set the exact capacity for the lists after I clear() them, or not worth it? I see in the profiler that List.SetCapacity is using some memory, but I can't identify the resize in the profiler when I don't do that. Everyone that speaks of setting list capacities to save memory says to do so when the list is initialized, but I'm setting it several times every so often.

 

Yes, do it once, not every time you clear it. If you set capacity to 1000 for instance, then when you fill it, there is already array with that size allocated for you, if you don't then after adding two elements it will create new array under the hood with size of 4 and copy elements, then if you exceed 4 elements it will allocate new array of size 8, copy all elements and GC the old one. At some point it does the same thing for 1024, 2048, 4096...

You don't need to change capacity later, even if you don't use all elements you don't care, this is what list is for.

 

One more trick I've used for procedural generation:
Effectively the "ping pong" or "double buffer" method:
Keep two .mesh instances and render one while the other one is being updated.
This is only meaningful with multithreading so the update can actually happen in the background. That likely means you need to use NativeArray/List and the job system (myself am updating the meshes via C# thread as it happens in a cpp dll, so I cannot give exact advice).

 

Thanks all for the help and advice, I'm now good but I'm sure I'll reference this thread again in the future.