🔒 Locked 🎮 Unity

[.net] Efficiently adding to List

Started by lack o comments May 9, 2009 at 5:20 PM 5 replies 1.3k views

Original Post

May 9, 2009 at 5:20 PM

I am writing a rendering system in C# and have come to a point where the CPU is severely bottle-necking the performance of a test. Honestly, I'll admit that this is just some optimize-before-it's-time-curiosity but I still would like to know what's going on for future reference. Each frame I'm adding collections of simple 6-vertex quads (for sprites) to a List of vertices. When it's time to render I simply lock the VertexBuffer and pop them in then draw. With 12,000 verts per frame I was doing fine at ~10 ms but with 60,000 it started hitting 50-60ms. Within the function that adds new verts to the List I allocate a simple Array and then copy the current image's verts into it, transform them and then add that to the List like so:


DeviceVertex[] TempVerts = (DeviceVertex[])graphic.Verts.ToArray();
			for(int i = 0; i < GlobalRendererSettings.VertsPerSprite; i++)
				{
				TempVerts.x += xPos*2;
				TempVerts.y += yPos*2;
				}
//... later...
list.Verts.AddRange(TempVerts);

I managed to boil the entire performance hit down to that last line. If I took it out, everything else fell right back down to ~10ms. On a hunch I decided to use a List uniformly across the board like so:


List<DeviceVertex> verts = new List<DeviceVertex>(6);
			TempVerts = graphic.Verts;
			TempVerts.ForEach(delegate(DeviceVertex v)
					{
					v.x += (xPos*2);
					v.y += (yPos*2);
					} );

After that, everything was happily hanging around 25ms. Trouble is I can't seem to actually get the transformation within that ForEach block to work. I can't access the data any other way without some kind of complex conversion and tossing of data everywhere. And then it just brings me right back up to the 45-50ms range. For now I can safely go back to the conversion between Lists and Arrays but I'm worried about problems in the future where I can't get away with that. Any advice? For reference I did my timing both with QPC and PIX and tested all scenarios with locking and drawing both on and off. I'm certain that it isn't a GPU stall anywhere.

turnpast

May 9, 2009 at 5:54 PM

I suspect that the reason that your second method using ForEach() on the list is not working because your DeviceVertex is a value type. If so the 'v' is a copy of what actually in the list and assigning to it assigns only to the copy.

I could be wrong here, but I believe that in extremely critical performance code it is best to avoid any type of reference allocation as this can hit your performance both upfront and unexpectedly when the GC kicks in. Consider keeping a big enough array of verts around, reusing it every frame and avoid creating lots of little arrays.

One thing you can do is use a struct with 6 named verts instead of a 6 element array of verts as your quad representation. More of a pain to work with, but could perform better depending on your usage. If you use the StructLayout attribute on a struct that is a collection of verts you can make it binary compatible with a very[] and probably even with a float[]. If your structs are binary compatible you should be able to move things around very efficiently with Buffer.BlockCopy() and Even the methods from Marshal (if you are feelig crazy).

You may also want to avoid calls to thinks like List.Add()/AddRange() as these things can inadvertently cause new memory allocations. You should be able to get similar enough behavior just incrementing an index into your buffer.

Mind you, I am no performance expert, so you may want to do some more research before following anything I suggest.

Hope this helps

lack o comments

May 9, 2009 at 6:25 PM

Quote:

I suspect that the reason that your second method using ForEach() on the list is not working because your DeviceVertex is a value type. If so the 'v' is a copy of what actually in the list and assigning to it assigns only to the copy.

You got me there. My DeviceVertex is setup as just a struct with sequential memory. Its use was specifically for SlimDX. I was worried what you said would be the case but I wasn't sure. Well nuts :/ I was really banking on that ForEach()

Quote:

I could be wrong here, but I believe that in extremely critical performance code it is best to avoid any type of reference allocation as this can hit your performance both upfront and unexpectedly when the GC kicks in. Consider keeping a big enough array of verts around, reusing it every frame and avoid creating lots of little arrays.

Yeah, that's what I figured too which is why I'm using a List with a pre-allocation size equal to the maximum verts needed. This is kept around during the lifetime of the application and it is what is filled and pushed into the vertexbuffer each lock. It seems the actual conversion from List to Devicevertex[] and back is what is killing me. I wanted to simply use List the whole way but the compiler says I cannot change the values of what is stored. I can only read them.

I removed the code that actually transforms the verts from the first example. This had no performance increase. From there I simply used List<> in place of Array and instantly the performance went up. Trouble is, I can't transform the verts while they are kept in the List<>. The compiler keeps telling me they are not variables.

I guess I'll keep at it with some of the other things you said. Thanks.

turnpast

May 9, 2009 at 6:37 PM

You should be able to transform the verts in the list, you just have to reassign them the the correct index after you have transformed them.

for(int i = 0; i < GlobalRendererSettings.VertsPerSprite; i++){	DeviceVertex d = graphic.Verts;	d.x += xPos*2;	d.y += yPos*2;	graphic.Verts = d;}

lack o comments

May 9, 2009 at 7:05 PM

Huzzah! Actually you were close. You see, the graphic.Verts is the master copy of the image's local space that is being transformed for each instanced copy. So the last line had to be

TempVerts = d

Where TempVerts is a List<> that is pre-allocated and exists with the lifetime of the rendering system.

I managed to find my own way with:

for(int i = 0; i < 6; i++)	{	TempVerts = new DeviceVertex(graphic.Verts.x + (xPos*2),graphic.Verts.y + (yPos*2),graphic.Verts.z,graphic.Verts.color,graphic.Verts.u,graphic.Verts.v);	}

But yours runs slightly faster. Mine was getting around 35-45 ms. Yours seems to have a consistant 29-32 ms.

Thanks indeed sir! Rating++

turnpast

May 10, 2009 at 2:39 PM

Glad you got everything working the way you want :)

kbirger

May 20, 2009 at 11:48 AM

I know the issue has been solved but I would just like to mention something. using the ForEach method is generally a bad idea, it was added as something like a hack / by-the-way feature when extension methods were introduced in order to make LINQ function.

You should avoid using it when you can use a standard foreach loop. You're making an anonymous delegate call, which is rather slow compared to real loop operation.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.