Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Array.Sort performance issue


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
18 replies to this topic

#1 Headkaze   Members   -  Reputation: 583

Like
0Likes
Like

Posted 27 October 2013 - 03:51 PM

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)
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);
}

 
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.

Sponsor:

#2 N.I.B.   Members   -  Reputation: 1195

Like
0Likes
Like

Posted 27 October 2013 - 04:09 PM

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.



#3 Postie   Members   -  Reputation: 1083

Like
0Likes
Like

Posted 27 October 2013 - 04:41 PM

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?


Currently working on an open world survival RPG - For info check out my Development blog: ByteWrangler

#4 Headkaze   Members   -  Reputation: 583

Like
0Likes
Like

Posted 27 October 2013 - 04:46 PM

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.

#5 wintertime   Members   -  Reputation: 1801

Like
1Likes
Like

Posted 27 October 2013 - 04:52 PM

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, 27 October 2013 - 04:55 PM.


#6 Headkaze   Members   -  Reputation: 583

Like
0Likes
Like

Posted 27 October 2013 - 04:53 PM

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

#7 phil_t   Crossbones+   -  Reputation: 3949

Like
3Likes
Like

Posted 27 October 2013 - 06:13 PM

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.



#8 N.I.B.   Members   -  Reputation: 1195

Like
0Likes
Like

Posted 28 October 2013 - 12:31 AM

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.



#9 iMalc   Crossbones+   -  Reputation: 2313

Like
0Likes
Like

Posted 28 October 2013 - 02:15 AM

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.


"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

#10 apatriarca   Crossbones+   -  Reputation: 1747

Like
0Likes
Like

Posted 28 October 2013 - 02:51 AM

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.

#11 N.I.B.   Members   -  Reputation: 1195

Like
-1Likes
Like

Posted 28 October 2013 - 03:13 AM

 

 

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.

 

Disabling vsync will only worsen the issue. If this sort code runs at 55FPS, than vsync will not magically increase the performance - it will still run at 55FPS.

It will only affect the original code, which will probably run faster then 60FPS, which only increases the performance drop.



#12 apatriarca   Crossbones+   -  Reputation: 1747

Like
2Likes
Like

Posted 28 October 2013 - 04:30 AM

I never said disabling vsync solves the performance problem. I said that evaluating performance differences in frame per second with vsync is pointless. If you are really interested in evaluating the effect of some algorithm on performance you should disable vsync and start using better profiling methods and tools.

#13 N.I.B.   Members   -  Reputation: 1195

Like
0Likes
Like

Posted 28 October 2013 - 05:00 AM

If you are really interested in evaluating the effect of some algorithm on performance you should disable vsync and start using better profiling methods and tools.

I totally agree.

#14 Eck   Crossbones+   -  Reputation: 3096

Like
1Likes
Like

Posted 28 October 2013 - 10:07 AM

When trying to fix performance issues, step 1 is profiling. Humans are bad at guessing where the problem is, so put some profiling in. If you don't have access to a profile library, you can write a little StopWatch class to time each line or function that you're interested in. That being said, I may have noticed some things.

 

Your first couple of comparisons: Layer and Translation.Z. Is Layer a class or a struct? If Layer is a class, they will only be == if they are pointing to the same instance.

Layer layer1 = new Layer(Layer.Bottom);
Layer layer2 = new Layer(Layer.Bottom);
 
if(layer1 == layer2)
 Console.WriteLine("This line will not be hit if Layer is a class. They are NOT equal");

Same goes for Translation.Z. Sometimes you might think they're the same, but it turns out they aren't.

 

For your TextureArray's. What that code is saying is this. If they both have a texture[0], see if they are different, otherwise they are equivalent. I suspect this is wrong (but might not be in your case). If one side is null, and the other is not null, that is probably a difference you care about. 

// If we don't have a texture array
if (this.TextureArray[0] == null)
{
    // but the other guy does
    if (other.TextureArray[0] != null)
        return -1; // we're smaller
 
    // Otherwise, we both have a null texture and we're the same. move along.
}
// If we do have a texture array, and the other guy doesn't
else if (other.TextureArray[0] == null)
{
    return 1; // we're bigger
}
// else we both have a texture, so we have to check
else if (this.TextureArray[0].Id != other.TextureArray[0].Id)
{
    return this.TextureArray[0].Id.CompareTo(other.TextureArray[0].Id);
}

 

Depending on the way you want to sort in this case a null texture might be bigger or smaller. Change the return values if this isn't the case.

 

And lastly, your BlendMode and ScissorRect seems wrong as well. What this says is: If our blend modes are different, then I'm bigger than the next guy.  Things that are sorting on this will swap back and forth each time you Sort your list even if nothing changes.  So, let's say  you have two blend modes, Opaque and Transparent. The first pass you compare Opaque and Transparent, Opaque will be bigger than Transparent. But call Sort again and Transparent will be bigger than Opaque. Not only that, if you have multiple guys that are sorting on this criteria, Opaque and Transparent will be scattered about randomly.

 

That last one might be the cause of your performance depending on the sort algorithm in use as the list will never stay sorted.

 

And like I said before, keep in mind whether or not things are Reference Types (class) or Value Types (structs) as that makes a difference in what you're telling the code to do. For Reference Types you're saying am I referencing the same instance. For Value types you're saying: are the values of these objects equivalent.

http://www.gamedev.net/topic/649248-list-remove/#entry5103729

 

I hope this helps. But PROFILE IT! :)

- Eck

 

 

 

 



#15 Headkaze   Members   -  Reputation: 583

Like
0Likes
Like

Posted 28 October 2013 - 04:29 PM

I understand about StopWatch and how to profile performance. I did state in my original post that having only one evaluation in CompareTo would not effect performance. The frame rate drop is not a perfect measurement but it's enough to see there is a substantial performance hit. So I don't need to profile to know where the issue lies. At this stage it's important that my engine maintains a solid 60 FPS.

I think the best thing to do is break the render object list up into separate lists for each layer as suggested.

Another thing I could try would be to use a different sorting algorithm. Array.Sort uses a QuickSort and does not maintain the original list order (unstable). Any suggestions there would be appreciated.

phil_t and Eck make some good points about some of issues with comparisons I've made. Layer and Translation.Z are just floats so there is no reference comparison there. But you're right about the Texture's and null values and I did make a mistake with the BlendMode comparison returning 0 instead of -1. For the ScissorRect I've changed it to compare using Rect.GetHashCode().

Thanks to everyone for all the suggestions.

Edited by Headkaze, 28 October 2013 - 04:36 PM.


#16 phil_t   Crossbones+   -  Reputation: 3949

Like
2Likes
Like

Posted 28 October 2013 - 04:44 PM


I did state in my original post that having only one evaluation in CompareTo would not effect performance.

 

To clarify, you said having only one evaluation resulted in "no performance problem" (and so apparently has a large effect on performance compared to the logic you need in there).

 

To re-iterate what myself and others have said already (which you haven't addressed): (EDIT: ok, you edited your last post since I wrote this :-))

- when making perf measurements, turn v-sync off. Give performance numbers in seconds or ms per frame, not FPS.

- as pointed out by both me and Eck, your compare function is flawed (since it may claim both that "B comes before A" and "A comes before B"). In addition to not sorting properly, this could very likely be causing a lot more calls to CompareTo than are necessary. Before proceeding any further, you should address this. It may very well be the cause of your performance issues (in addition to being incorrect).

 

If after that, you still are having perf issues with the sorting, then investigate other avenues (separate lists for each layer, or a sorting algorithm that is efficient on already nearly sorted lists).


Edited by phil_t, 28 October 2013 - 04:45 PM.


#17 Headkaze   Members   -  Reputation: 583

Like
0Likes
Like

Posted 28 October 2013 - 05:20 PM

Here is the new CompareTo method

 

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

    for (int i = 0; i < TEXTURE_ARRAY_COUNT; i++)
    {
        if (this.TextureArray[i] == null)
        {
            if (other.TextureArray[i] != null)
                return -1;
        }
        else if (other.TextureArray[i] == null)
            return 1;
        else if (this.TextureArray[i].Id != other.TextureArray[i].Id)
            return this.TextureArray[i].Id.CompareTo(other.TextureArray[i].Id);
    }

    if (this.BlendMode != other.BlendMode)
        return this.BlendMode.CompareTo(other.BlendMode);

    if (this.ScissorRect != other.ScissorRect)
        return (this.ScissorRect.GetHashCode() - other.ScissorRect.GetHashCode());

    return this.Index.CompareTo(other.Index);
}

 

Unfortunately the performance has not improved.



#18 Eck   Crossbones+   -  Reputation: 3096

Like
1Likes
Like

Posted 28 October 2013 - 06:17 PM

I'm pretty sure there can't be a meaningful sort on ScissorRect.GetHashCode(), and I wasn't sure how you'd "sort" on ScissorRect to determine which order you should be drawing stuff in. I also have suspicions about sorting on Texture.Id. If those aren't meaningful sorts, then you can get rid of them. Just delete all those comparisons ScissorRect, TextureArray.

 

Another thing you might try is switching from List to SortedList. I have no idea if the gains there will help or hurt you.

 

And finally (or firstly rather), you could give profiling a whirl. :)

 

- Eck



#19 frob   Moderators   -  Reputation: 22289

Like
3Likes
Like

Posted 28 October 2013 - 08:03 PM

I see a few suspects. A simple sort of 1000 items is extremely quick, but you have a complex comparison function.

A sort by itself is extremely quick. Did you accidentally put the sort inside a loop, or otherwise call it more frequently than necessary?

Sort requires "strict weak" ordering, but I'm not convinced you are following that. This ruins the sort algorithm so be absolutely certain you follow it.

Your comparison function includes a nested loop, how big is TEXTURE_ARRAY_COUNT?

Your comparison function uses many accessors to read values from other objects, are those complex functions?

Your comparison function calls other comparison functions, are those comparison functions complex functions?

As others mentioned, these are things that should be obvious once run through a profiler.

Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I write about assorted stuff.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS