row / cells selecting slow down when sorting by column with many same values

[Argos]

Hi,

I encounter the problem like in subject. You can simply reproduce it by:
1) create simple project with RadGridView
2) Set model as ObjectDataSource
3) fill it like this:

•  public Form1()
          {
              InitializeComponent();
  
              List<Model> model = GenerateModel();
              this.radGridView1.DataSource = model;
          }
• private List<Model> GenerateModel()
          {
              List<Model> model = new List<Model>();
  
              // 1)    EVERYTHING WORKS FINE
              //for (int i = 0; i < 100000; i++)
              //{
              //    Model m = new Model() { Text = i.ToString(), Number = i, Text2 = i.ToString() };
              //    model.Add(m);
              //}
  
              // 2)    SLOW DOWN
              for (int i = 0; i < 100000; i++)
              {
                  Model m = new Model() { Text = i.ToString(), Number = i, Text2 = "1" };
                  model.Add(m);
              }
  
              return model;
          }
• public class Model
      {
          public string Text { get; set; }
          public int Number { get; set; }
          public string Text2 { get; set; }
      }
  

When you uncoment version one ( and of course comment version 2 ) everything works fine = selecting rows / cells works perfect.
But when you comment version 1 and uncoment second ( like in above example ) after set sorting on third column ( Text2 ) selecting rows / cells slows down. When you clear sorting on third column behavior back to normal. Sorting by another columns ( first or second ) doesn't couse such behavior.
So in my opinion it is happend when many cells in sorted columns contain the same value.
I think that because when fill only half of rows with the same value and rest with different it spead up.

Does someone has any solution for this
Thanks in advance

[George]

Hi Argos,

Thank you for contacting us.

Although I could not reproduce the described behavior on my end there is one thing that you can try. You can set the threshold which defines what sorting algorithm will be used. You can use the following code:

RadDataView<GridViewRowInfo> dataView = this.grid.GridViewElement.Template.ListSource.CollectionView as RadDataView<GridViewRowInfo>;
FieldInfo indexerField = typeof(RadDataView<GridViewRowInfo>).GetField("indexer", BindingFlags.NonPublic | BindingFlags.Instance);
HybridIndex<GridViewRowInfo> indexer = indexerField.GetValue(dataView) as HybridIndex<GridViewRowInfo>;
indexer.Threshold = 500;

When the items count is greater than the threshold BinaryTree will be used to perform the sorting operations.

I have implemented this in the sample project which you can find attached below. Feel free to modify the project and send it back to me if you require any further assistance.

Looking forward to your response.

Regards,
George
Telerik

[Argos]

Hi,
Thank you for you reply.
To see slow down, just select first row and keeping presed arrow down key move down selection. Then you noticed that when sorting is by first or second column ( different values ) you move three time faster (on my computer ) then when sorting by third column ( the same "1" values ). I measured it with stopwatch in 10 second period - results: 97 rows compared to 263 row = almost 3 time slower.
Of course - such slow doesn't "kill application performance" but when you add handler to grid event such as SelectionChanging, SelectionChanged, FilterChanging, FilterChanged, and the most time consuming ViewCellFormatting (I need it to hide cell in filtering row for some columns I want to filter programaticly - out of grid, and not with filtering row functionality ) then this slow down make impossible to use application.
Once again - in my opinion operation ( e.g selecting rows ) should take same time on grid sorted by columns with different values and same values.
I tried your solution with indexer but it not change the speed.
Could you give me another solution to resolve this issue?
Thanks in advance!

[George]

Hi Argos,

Thank you for your reply.

This behavior is due to the algorithm we use to find the rows in the grid. We are using a RedBlackOrderedTree which in cases like this when all nodes are with the same value has some performance losses. Unfortunately we cannot provide you with a workaround for this scenario.

Let me know if you have any further questions.

Regards,
George
Telerik

[Andrea]

The workaround I use, that works if the data you show have any unique property, is to provide the grid an IComparer<GridViewRowInfo>

theGrid.MasterTemplate.SortComparer = <your comparer here>

when you generate such comparer, you will keep a reference to the associated grid, and when the grid calls the compare functions, you should return based on the filterdescriptor collection and when you find two records are equals value for the given sort descriptor also look at the primary key value (if exists).

an example:

public class RecordComparer: IComparer<GridViewRowInfo>

   {

        

       public RadGridView Associated { get;set;  }

        

 

       public int Compare(GridViewRowInfo x, GridViewRowInfo y)

       {

           MyClass a = x.DataBoundItem as MyClass;

           MyClass b = y.DataBoundItem as MyClass;

 

           if (Associated == null)

               return 0;

 

           if (a == null || b == null)

               return Telerik.WinControls.UI.GridViewRowInfoComparer.CompareRows(x, y, Associated.SortDescriptors);

            

           foreach (var d in Associated.SortDescriptors)

           {

               int multiplier = d.Direction == ListSortDirection.Ascending ? 1 : -1;

               IComparable oa;

               object ob;

               //may use reflection but slow down

               if (d.PropertyName == "myProp1")

               {

                   oa = a.MyProp1;

                   ob = b.MyProp1;

               }

               else if (d.PropertyName == "myProp2")

               {

                   //etcetera

               }

 

               if (oa == null && ob == null)

                   continue;

               if (oa == null)

                   return -multiplier;

               if (ob == null)

                   return multiplier;

 

               int compare = oa.CompareTo(ob);

 

               if (compare != 0)

                   return multiplier * compare;

 

           }

           return a.PrimaryKey.Compare(b.PrimaryKey); //if no other order found sort by primary key otherwise the sorting slow down


       }

 

   }

By the way there is something wrong in this source code and I think this slow down sorting of medium number of record, like 10K records:

// in Telerik.Collections.Generic.HybridIndex<T>
                        if (binary)
                        {
                            List<T> collection = (List<T>)items;
                            int index = collection.BinarySearch(item, this.CollectionView.Comparer);
                            if (index < 0)
                            {
                                collection.Insert((index * -1) - 1, item);
                            }
                            else
                            {
                                while (++index < collection.Count
                                     && this.CollectionView.Comparer.Compare(item, collection[index]) == 0) ;
                                collection.Insert(index, item);
                            }
                        }

it find the first item greather or equal than then we do a linear loop to find the first element greather than: when there are many equal values this tend to O(n^2) defeating the purpose of a binary search,

Instead if we are searching the first element great than we should pass a modified comparer to BinarySearch, that return -1 even if the elements are equals, so binary search will always return the first element greather than the searched item, thus the linear loop could be removed, in my opinion.


Best regards

[Ivan Todorov]

Hello Andrea,

Thank you sharing your solution with the community. Indeed, using the primary key in the comparer function is a pretty neat solution. Unfortunately, we won't be able to incorporate such solution in our code because it is specific to each certain case. The slowdown in cases where there are many equal values comes from the fact that operations like Find, IndexOf, RemoveAt would require doing a linear search among the rows which are equal according to the comparer but are actually different objects. We are aware of this limitation and we will think of possible solutions in the near future.

As to your second suggestion, we are also aware of that. Note that even if the linear index search was resolved, we still use Collection.Insert which will perform linear shift of all elements in the collection when the insert index is small. This, as you mentioned, defeats the performance of the binary search and is a bottleneck to the whole method. Again, we are aware of that and we plan to improve it in the upcoming releases. For the time being, you can easily switch the binary search to the red-black tree implementation by reducing the Threshold property (mentioned by my colleague George in one of the previous posts).

Thank you very much for your feedback. Your Telerik Points have been updated for this.

Should you have any other questions or suggestions do not hesitate to contact us.

 

Regards,
Ivan Todorov
Telerik

 

 

[Andrea]

Thank you for answer, but please note that the hypotesis were that many values are equals, in the extreme case, where all values are equals, collection.insert will be a "best case" where the cost will be O(1) unless collection is implemented as a tree so have O( log N) .

By the way I suggest everybody to use custom sorting or implement a comparer such the one above, for the simple fact that not using reflection have visible benefits if number of record is large for sorting.

Best Regards.

[Andrea]

Thank you for the answer, but please note that the hypotesis were to have many same values to sort, if we consider the extreme situation "all valuse are the same" collection.insert should be at its "best case" of O(1) insert, unless it is implemented as a tree so will have O(log N)

By the way I suggest other users to use custom sorting or implement a comparer like the one above, the simple fact of not using reflection have visible benefits over large number of records for sorting.

Best Regards.

[Ivan Todorov]

Hello Andrea,

Thanks for the clarification. Indeed, with the modifications you've mentioned and considering that all values are equal, the complexity of the insertion will be a constant. We'll keep this in mind when refactoring this part.

As to the custom sorting, you are right that reflection can turn out to be the performance bottleneck when used very extensively. Using the properties of an object directly will surely improve the overall performance.

Thanks for sharing your insights!

Regards,
Ivan Todorov
Telerik