Jump to content
  • Advertisement
Sign in to follow this  
Headkaze

Array.Sort performance issue

This topic is 1724 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement

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.

Share this post


Link to post
Share on other sites

A few thoughts pop to mind: 

 

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

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

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?

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.wink.png

Edited by wintertime

Share this post


Link to post
Share on other sites

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).

Share this post


Link to post
Share on other sites

This code:

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

seems incorrect for a Compare function: http://msdn.microsoft.com/en-us/library/xh5ks3b3.aspx

 

Sorting implies an order, and you need to return a -ve or +ve number to indicate that one item precedes another or vice versa. With what you have now, If Compare(A, B) says that A comes before B, then Compare(B, A) would say that B comes before A. I'm pretty sure this could impact the performance (and correctness) of your sort.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

First of all I would undo that manual-loop-unrolling / copy-pasting for TextureArray and just put it back into a loop. It's the compiler's job to unroll such an easily unroll-able loop if it makes sense.

 

Then, profile how often each comparison is executed. It may be that it most often returns after the first comparison, or it may be that it often gets right down to the last one.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!