[gtk/wip/otte/sortlistmodel: 104/134] timsort: Add gtk_tim_sort_set_max_merge_size()

[Benjamin Otte <otte src gnome org>]

commit 9588aec9960b1aba52f4e468a9aaacd47fffd44a
Author: Benjamin Otte <otte redhat com>
Date:   Sat Jul 18 04:45:46 2020 +0200

    timsort: Add gtk_tim_sort_set_max_merge_size()
    
    Makes the SOrtListModel responsive when incrementally sorting.
    
    By making it configurable we can avoid losting performance in the
    non-incremental case.

 gtk/gtksortlistmodel.c  | 16 ++++++++++++++++
 gtk/gtktimsort-impl.c   | 22 +++++++++++-----------
 gtk/gtktimsort.c        | 45 +++++++++++++++++++++++++++++++++++----------
 gtk/gtktimsortprivate.h |  8 ++++++++
 4 files changed, 70 insertions(+), 21 deletions(-)
---
diff --git a/gtk/gtksortlistmodel.c b/gtk/gtksortlistmodel.c
index 798ae24e56..5dfc6fb4cd 100644
--- a/gtk/gtksortlistmodel.c
+++ b/gtk/gtksortlistmodel.c
@@ -25,6 +25,21 @@
 #include "gtkprivate.h"
 #include "gtktimsortprivate.h"
 
+/* The maximum amount of items to merge for a single merge step
+ *
+ * Making this smaller will result in more steps, which has more overhead and slows
+ * down total sort time.
+ * Making it larger will result in fewer steps, which increases the time taken for
+ * a single step.
+ *
+ * As merges are the most expensive steps, this is essentially a tunable for the
+ * longest time spent in gtk_tim_sort_step().
+ *
+ * Note that this should be reset to 0 when not doing incremental sorting to get
+ * rid of all the overhead.
+ */
+#define GTK_SORT_MAX_MERGE_SIZE (1024)
+
 typedef struct _SortItem SortItem;
 struct _SortItem
 {
@@ -234,6 +249,7 @@ gtk_sort_list_model_resort (GtkSortListModel *self,
                      sizeof (SortItem),
                      sort_func,
                      self->sorter);
+  gtk_tim_sort_set_max_merge_size (&self->sort, GTK_SORT_MAX_MERGE_SIZE);
   gtk_tim_sort_set_runs (&self->sort, (gsize[2]) { already_sorted, 0 });
 
   gtk_sort_list_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 38a46880e8..e76c915da0 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;
@@ -229,6 +220,40 @@ gtk_tim_sort_set_runs (GtkTimSort *self,
     gtk_tim_sort_push_run (self, self->base, runs[i]);
 }
 
+/*
+ * 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 f6ebd348e9..7472453556 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
@@ -99,6 +105,8 @@ void            gtk_tim_sort_get_runs                           (GtkTimSort
                                                                  gsize                   
runs[GTK_TIM_SORT_MAX_PENDING + 1]);
 void            gtk_tim_sort_set_runs                           (GtkTimSort             *self,
                                                                  gsize                  *runs);
+void            gtk_tim_sort_set_max_merge_size                 (GtkTimSort             *self,
+                                                                 gsize                   max_merge_size);
 
 gboolean        gtk_tim_sort_step                               (GtkTimSort             *self);