I am working on a C#/SlimDX rendering engine. I noticed a performance issue after having around 1000 rendered objects in a List<T> and sorting them every frame. I need to sort these objects so they render in the appropriate order. I'm actually getting a significant frame rate drop of about 5 FPS.

The problem is not so much the sorting per se but that I need to perform multiple levels of sorting based on members in the objects such as the layer, texture and so on. Finally the objects need to sort based on the original order they were added to the List so I have an index member for that.

Here is the sorting code (no idea why the indentation isn't working here)
[source]public int CompareTo(RenderObject other)
{
if (this.Layer != other.Layer)
return this.Layer.CompareTo(other.Layer);

if (this.Translation.Z != other.Translation.Z)
return this.Translation.Z.CompareTo(other.Translation.Z);

if (this.TextureArray[0] != null && other.TextureArray[0] != null)
if (this.TextureArray[0].Id != other.TextureArray[0].Id)
return this.TextureArray[0].Id.CompareTo(other.TextureArray[0].Id);

if (this.TextureArray[1] != null && other.TextureArray[1] != null)
if (this.TextureArray[1].Id != other.TextureArray[1].Id)
return this.TextureArray[1].Id.CompareTo(other.TextureArray[1].Id);

if (this.TextureArray[2] != null && other.TextureArray[2] != null)
if (this.TextureArray[2].Id != other.TextureArray[2].Id)
return this.TextureArray[2].Id.CompareTo(other.TextureArray[2].Id);

if (this.TextureArray[3] != null && other.TextureArray[3] != null)
if (this.TextureArray[3].Id != other.TextureArray[3].Id)
return this.TextureArray[3].Id.CompareTo(other.TextureArray[3].Id);

if (this.BlendMode != other.BlendMode)
return (this.BlendMode != other.BlendMode ? 1 : 0);

if (this.ScissorRect != other.ScissorRect)
return (this.ScissorRect != other.ScissorRect ? 1 : 0);

return this.Index.CompareTo(other.Index);
}[/source]

As you can see I've implemented IComparable<T> and call Array.Sort every frame. Unfortunately it's causing this performance issue. Now if I change it to only sort based on index, for example, then there is no problem. So it's the fact I need multiple parameters to sort the object list that is slowing things down.

On a final note I have to be able to sort every frame because some render objects (like text) are dynamic and are added/removed every frame. I actually had a massive 15 FPS drop when I used a loop to remove the objects but have since improve by using List.AddRange to add text character objects and List.RemoveAll to remove them. So now I only have 5 FPS drop that is due to the sorting.

I do not have Linq available to me (using .NET 2.0) so I'd like to hear some ideas on how I can improve the performance of this necessary sorting.

First of all - wow! All those branches are perfomance's worst nightmare.

Not sure why you have to sort. Based on your comparison function, you are trying to minimize state changes, which is a nice idea, but there are more practical ways to do it.

...some render objects (like text) are dynamic and are added/removed every frame...

But surely not all the 1000 objects are dynamic... And even for dynamic objects, such as text, I don't see a reason to sort.

Not sure why you have to sort. Based on your comparison function, you are trying to minimize state changes, which is a nice idea, but there are more practical ways to do it.

It's about minimizing state changes but also rendering order. For example you can place an object on a particular layer. The layer order takes precedence over its z order, and the z order takes precedence over the texture, etc.

If you can shed some light on a more practical way of doing it, I'd like to hear it. But maintaing the order of the objects is important.

BTW I never had any performance issues using this technique in my C++ engine.

The method you use is like throwing everything into a deep barrel and then trying to sort through it to fish out everything again.

What you should do is have many tiny boxes for every combination of static/dynamic, layer, transparency and possibly more, directly put things into the right box and then only sort the few things in the tiny boxes by depth (or maybe even skip that for nontransparent stuff), which would go much faster. Then go through those boxes in your prefered order.

1) What is the time difference in milliseconds? a delta of 5fps when its running at 200fps is not too much to worry about.

It's running at vsync 60 FPS so it is a significant performance hit.

2) Can you use a linked list and manage the order of objects when they are added/removed?

I have never tried using a LinkedList<T>. If it would be a significant benefit in this case I could give it a try.

3) Could you split your list into two smaller lists, one which is for static objects which don't change per frame, and thus don't need the sort, and dynamic ones which do?

Not really.. the 1000 objects I refer to is all text (dynamic).

1. Minimizing state changes is an optimization. In this case, it clearly doesn't optimize anything, so at bear minimum stop comparing the states.

2. You say your objects are dynamic, so someone has to manage them (create/destroy/move). That same entity can also place each object in the correct bucket once it is updated, basically sorting on the fly.

1) What is the time difference in milliseconds? a delta of 5fps when its running at 200fps is not too much to worry about.

It's running at vsync 60 FPS so it is a significant performance hit.

Frames per second with vsync active means very little. When evaluating performance, disable vsync and use milliseconds as already suggested.