[gtk/wip/otte/sortlistmodel: 146/154] timsort: Add gtk_tim_sort_set_max_merge_size()

[Benjamin Otte <otte src gnome org>]

commit 927c3c0baba66f389d4c38e67292f13e4a2c77fd
Author: Benjamin Otte <otte redhat com>
Date:   Sun Jul 12 03:36:26 2020 +0200

    timsort: Add gtk_tim_sort_set_max_merge_size()
    
    Makes responsiveness vs performance configurable. This way the
    Tim1SortModel can be fast again while the Tim2SortModel can be
    repsonsive.

 gtk/gtktim2sortmodel.c  |  1 +
 gtk/gtktimsort-impl.c   | 22 +++++++++++-----------
 gtk/gtktimsort.c        | 45 +++++++++++++++++++++++++++++++++++----------
 gtk/gtktimsortprivate.h |  8 ++++++++
 4 files changed, 55 insertions(+), 21 deletions(-)
---
diff --git a/gtk/gtktim2sortmodel.c b/gtk/gtktim2sortmodel.c
index 17ceabf8bd..7203843e63 100644
--- a/gtk/gtktim2sortmodel.c
+++ b/gtk/gtktim2sortmodel.c
@@ -234,6 +234,7 @@ gtk_tim2_sort_model_resort (GtkTim2SortModel *self,
                      sizeof (SortItem),
                      sort_func,
                      self->sorter);
+  gtk_tim_sort_set_max_merge_size (&self->sort, 1024);
   gtk_tim_sort_set_already_sorted (&self->sort, already_sorted);
 
   gtk_tim2_sort_model_start_sorting (self);
diff --git a/gtk/gtktimsort-impl.c b/gtk/gtktimsort-impl.c
index 3e048324e2..8878db6a41 100644
--- a/gtk/gtktimsort-impl.c
+++ b/gtk/gtktimsort-impl.c
@@ -828,13 +828,13 @@ gtk_tim_sort(merge_at) (GtkTimSort *self,
   /* Merge remaining runs, using tmp array with min(len1, len2) elements */
   if (len1 <= len2)
     {
-      if (len1 > MAX_MERGE_PER_RUN)
+      if (len1 > self->max_merge_size)
         {
-          base1 = ELEM (self->run[i].base, self->run[i].len - MAX_MERGE_PER_RUN);
-          gtk_tim_sort(merge_lo) (self, base1, MAX_MERGE_PER_RUN, base2, len2);
-          self->run[i].len -= MAX_MERGE_PER_RUN;
-          self->run[i + 1].base = ELEM (self->run[i + 1].base, - MAX_MERGE_PER_RUN);
-          self->run[i + 1].len += MAX_MERGE_PER_RUN;
+          base1 = ELEM (self->run[i].base, self->run[i].len - self->max_merge_size);
+          gtk_tim_sort(merge_lo) (self, base1, self->max_merge_size, base2, len2);
+          self->run[i].len -= self->max_merge_size;
+          self->run[i + 1].base = ELEM (self->run[i + 1].base, - self->max_merge_size);
+          self->run[i + 1].len += self->max_merge_size;
           g_assert (ELEM (self->run[i].base, self->run[i].len) == self->run[i + 1].base);
           return;
         }
@@ -845,12 +845,12 @@ gtk_tim_sort(merge_at) (GtkTimSort *self,
     }
   else
     {
-      if (len2 > MAX_MERGE_PER_RUN)
+      if (len2 > self->max_merge_size)
         {
-          gtk_tim_sort(merge_hi) (self, base1, len1, base2, MAX_MERGE_PER_RUN);
-          self->run[i].len += MAX_MERGE_PER_RUN;
-          self->run[i + 1].base = ELEM (self->run[i + 1].base, MAX_MERGE_PER_RUN);
-          self->run[i + 1].len -= MAX_MERGE_PER_RUN;
+          gtk_tim_sort(merge_hi) (self, base1, len1, base2, self->max_merge_size);
+          self->run[i].len += self->max_merge_size;
+          self->run[i + 1].base = ELEM (self->run[i + 1].base, self->max_merge_size);
+          self->run[i + 1].len -= self->max_merge_size;
           g_assert (ELEM (self->run[i].base, self->run[i].len) == self->run[i + 1].base);
           return;
         }
diff --git a/gtk/gtktimsort.c b/gtk/gtktimsort.c
index 6f8c8755e3..6ed9b2e1f3 100644
--- a/gtk/gtktimsort.c
+++ b/gtk/gtktimsort.c
@@ -25,16 +25,6 @@
  */
 #define MIN_MERGE 32
 
-/*
- * Limit the amount of work done when merging. This ensures that the step
- * function does not take too much time. Of coure, there's overhead associated
- * with splitting a merge into miultliple merges.
- *
- * So lowering this number will make the average runtime of the step function
- * faster but increase the total runtime.
- */
-#define MAX_MERGE_PER_RUN 1024
-
 /*
  * When we get into galloping mode, we stay there until both runs win less
  * often than MIN_GALLOP consecutive times.
@@ -84,6 +74,7 @@ gtk_tim_sort_init (GtkTimSort       *self,
   self->data = data;
 
   self->min_gallop = MIN_GALLOP;
+  self->max_merge_size = G_MAXSIZE;
   self->min_run = compute_min_run (size);
 
   self->tmp = NULL;
@@ -192,6 +183,40 @@ gtk_tim_sort_set_already_sorted (GtkTimSort *self,
     gtk_tim_sort_push_run (self, self->base, already_sorted);
 }
 
+/*
+ * gtk_tim_sort_set_max_merge_size:
+ * @self: a #GtkTimSort
+ * @max_merge_size: Maximum size of a merge step, 0 for unlimited
+ *
+ * Sets the maximum size of a merge step. Every time
+ * gtk_tim_sort_step() is called and a merge operation has to be
+ * done, the @max_merge_size will be used to limit the size of
+ * the merge.
+ *
+ * The benefit is that merges happen faster, and if you're using
+ * an incremental sorting algorithm in the main thread, this will
+ * limit the runtime.
+ *
+ * The disadvantage is that setting up merges is expensive and that
+ * various optimizations benefit from larger merges, so the total
+ * runtime of the sorting will increase with the number of merges.
+ *
+ * A good estimate is to set a @max_merge_size to 1024 for around
+ * 1ms runtimes, if your compare function is fast.
+ *
+ * By default, max_merge_size is set to unlimited.
+ **/
+void
+gtk_tim_sort_set_max_merge_size (GtkTimSort *self,
+                                 gsize       max_merge_size)
+{
+  g_return_if_fail (self != NULL);
+
+  if (max_merge_size == 0)
+    max_merge_size = G_MAXSIZE;
+  self->max_merge_size = max_merge_size;
+}
+
 #if 1
 #define WIDTH 4
 #include "gtktimsort-impl.c"
diff --git a/gtk/gtktimsortprivate.h b/gtk/gtktimsortprivate.h
index f3875c2cb5..6b0a419680 100644
--- a/gtk/gtktimsortprivate.h
+++ b/gtk/gtktimsortprivate.h
@@ -55,6 +55,12 @@ struct _GtkTimSort
   gpointer base;
   gsize size;
 
+  /*
+   * The maximum size of a merge. It's guaranteed >0 and user-provided.
+   * See the comments for gtk_tim_sort_set_max_merge_size() for details.
+   */
+  gsize max_merge_size;
+
   /*
    * This controls when we get *into* galloping mode.  It is initialized
    * to MIN_GALLOP.  The mergeLo and mergeHi methods nudge it higher for
@@ -97,6 +103,8 @@ void            gtk_tim_sort_finish                             (GtkTimSort
 
 void            gtk_tim_sort_set_already_sorted                 (GtkTimSort             *self,
                                                                  gsize                   already_sorted);
+void            gtk_tim_sort_set_max_merge_size                 (GtkTimSort             *self,
+                                                                 gsize                   max_merge_size);
 gboolean        gtk_tim_sort_step                               (GtkTimSort             *self);
 
 void            gtk_tim_sort                                    (gpointer                base,