Disaster with BetterList performance

[AGB]

It doesnt seems, that BetterList really is Better, eats more than 50% of CPU in my project, when i moved from Z to Depth.
There are two possible solutions:
1. use LinkedList instead of List if it is required to add items frequently
2. Use constructor, which accepts initial capacity of an array http://msdn.microsoft.com/en-us/library/dw8e0z9z(v=vs.110).aspx

Why dont use something like:

1.  public class Comparer : IComparer
2.  {
3.   Comparison<T> comparer;
4.  
5.   public Comparer(Comparison<T> comparer)
6.   {
7.    this.comparer = comparer;
8.   }
9.  
10.   public int Compare(object x, object y)
11.   {
12.    return comparer((T)x, (T)y);
13.   }
14.  }
15.  
16.  public void Sort(Comparison<T> comparer)
17.  {
18.   Comparer cmp = new Comparer(comparer);
19.   Array.Sort(buffer, 0, size, cmp);
20.  }

[ArenMook]

List and Linked List are two very different things. Linked list does not exist in a continuous block of memory. Initializing a list with a capacity is a better approach, but BetterList, but in many use cases BetterList doesn't know what its max size is (for example -- filling in the widget buffers). BetterList was designed to reduce garbage collection. Using a regular list results in way too much of it.

[LionbI4]

In case, where it is required to allocate items frequently it is recommended to modify Capacity of a List. http://msdn.microsoft.com/en-us/library/y52x03h2(v=vs.110).aspx

[kindex]

I have around 250 gui objects on game screen. On NGUI 2.x NGUI LateUpdate CPU usage was 10-15%.

On NGUI 3.0.x I have terrible performance - fps is 5-10 times slower. BetterList.Sort is awful. It uses O(N^2) algorithm. In general, why BetterList is better than default well-optimized List?


Array.Sort (O(N*logN)) algorithm from AGB comment helps a bit, but appears next problem with UIPanel.Fill. Total CPU usage on NGU now is around 80%.


I waste one week to port my project from 2.x to 3.x, but now project is broken because of performance. If performance will not be fixed soon, I will ought to search another GUI framework.

[ArenMook]

I see CompareFunc takes majority of the time, suggesting that it's re-sorting the widget list based on depth, which happens when you either alter the depth of some widget(s) or enable/disable them.

And in regards to BetterList, as I mentioned it was created to reduce memory allocation / garbage collection (back in Unity 3.3 days). If the performance differs now, and better results can be achieved by using a regular list, then I don't mind changing it. If you want to try it yourself, just global replace BetterList with List.

[blechowski]

Same problem here:
http://www.tasharen.com/forum/index.php?topic=6287

The problem here seems to be with:
[1] void BetterList< T >.Sort   (   System.Comparison< T >    comparer   )
That Aren implements on his own and which is slow.

The name of parameter is not consistent with regular List<T>, which is:
public void Sort(   Comparison<T> comparison)

This is critical because List and Array implement another sort method:
public void Sort(   IComparer<T> comparer) [3]

And the sort method that would work perfectly with BetterList is:
public void Sort(   int index,   int count,   IComparer<T> comparer) [4]

Use this method for sorting as it is quick.

[1] http://www.tasharen.com/ngui/docs/class_better_list_3_01_t_01_4.html#a61855a957a241aaf9017671ec99e72d2
[2] http://msdn.microsoft.com/en-us/library/w56d4y5z(v=vs.110).aspx
[3] http://msdn.microsoft.com/en-us/library/234b841s(v=vs.110).aspx
[4] List http://msdn.microsoft.com/en-us/library/8ce6t5ad(v=vs.110).aspx
Array http://msdn.microsoft.com/en-us/library/k3e17y47(v=vs.110).aspx
Array http://msdn.microsoft.com/en-us/library/8kszeddc(v=vs.110).aspx

[ArenMook]

This is what the Sort() function looks like in the Professional repository right now:

1.         class Comparer : System.Collections.IComparer
2.         {
3.                 System.Comparison<T> mCompare;
4.                 public Comparer (System.Comparison<T> comparer) { mCompare = comparer; }
5.                 public int Compare (object x, object y) { return mCompare((T)x, (T)y); }
6.         }
7.  
8.         /// <summary>
9.         /// List.Sort equivalent.
10.         /// </summary>
11.  
12.         public void Sort (System.Comparison<T> comparer) { System.Array.Sort(buffer, 0, size, new Comparer(comparer)); }