# Re: Glib sort routines

• From: Charlie Brej <gtk-devel brej org>
• To: gtk-devel-list gnome org
• Subject: Re: Glib sort routines
• Date: Sun, 04 Jul 2010 01:24:49 +0100

Stim sort is a sorting method targeting for linked lists in glib. It is closely related to Tim sort. It is a stable sort, has NlogN worst case and a N best case.
```
---Algorithm---
The algorithm breaks into three parts: extraction, stacking, and merging.

Extraction:
```
From the original list, we look for sorted sequences. We look for either increasing or decreasing sequences. In the case of an increasing (already sorted) sequence, we tie off the last element next pointer (which pointed to a non-increasing element) to NULL. If the list is decreasing, we remove each element and prepend it to a new list (thus reversing the sequence). Both increasing and decreasing sequences can have sequences of equal elements, but in the decreasing list, there are added in order rather than reversed. This method will always find sequences of two or more (unless it is a list of length 1 or 0).
```
Stacking:
```
The real sorting function takes a "want" parameter which specifies the minimum number of nodes items we wish to remove from the list and have sorted. The top function calls with the list length. If the number is large (over 16) the function then recurses asking for half that number as a start. Otherwise it asks from an extracted strand. These functions reply two sorted sequences. The first is an attempt to forfill the requested number, and the second is any sequences beyond this that may be very large. If the current strand is greater than 1/3 of what we desire, we request for the remainder, otherwise we request an equal size block to double up. If we encounter any large blocks that are greater than the request, we return up the stack. Further up the stack, the system decides which sequences to merge first (the smaller ones).
```
Merge:
```
Merge combines two sorted sequences into one large one. Each list has a type, ascending(1), descending(2) or neither(0). The first elements of a descending list directly followed by an ascending list were already compared during the extraction step. So this can be used to skip the first compare. The product of an ascending list which had the lower is another list, is an ascending list. A merge of any list with a descending list which has the lowest element at the head, is a descending list. All other combinations become neither.
```
```
System walks along the list with the lower element, looking for the point the elements become higher than one at the head of the other list. If 8 steps are made looking for this, the searcher starts galloping. Taking increasingly larger step sizes, it looks for either the end of the list, or a component higher than the other list head. From here it performs a binary chop down to the element. Initial step size of 3 seemed to be marginally faster in tests.
```
```
In doubly linked lists, the prev pointers are ignored during the sort, and are zipped to nodes once the sort is finished.
```
---Benchmarks---

List size: 1000
Test                           ,MergeSort,StimSort ,Percent of comparisons
Sorted ascending               ,     4932,      999,    20.26%
Sorted descending              ,     5044,      999,    19.81%
All equal                      ,     4932,      999,    20.26%
Sorted but 10 unsorted at start,     5798,     1201,    20.71%
Sorted but 10 unsorted at end  ,     4990,     1199,    24.04%
Sorted but with three swaps    ,     5714,     1233,    21.59%
Sorted but with ten random     ,     5097,     1040,    20.40%
Sorted sequences of 16         ,     5452,     2762,    50.66%
Random but many same (4 values),     7991,     5468,    68.43%
Random                         ,     8707,     9035,   103.77%

List size: 10,000,000
Test                           ,MergeSort,StimSort ,Percent of comparisons
Sorted ascending               ,114434624,  9999999,     8.74%
Sorted descending              ,118788160,  9999999,     8.42%
All equal                      ,114434624,  9999999,     8.74%
Sorted but 10 unsorted at start,122942957, 10000472,     8.13%
Sorted but 10 unsorted at end  ,114434811, 10000475,     8.74%
Sorted but with three swaps    ,122892793, 10000633,     8.14%
Sorted but with ten random     ,116036786, 10000100,     8.62%
Sorted sequences of 16         ,120125153, 28238529,    23.51%
Random but many same (4 values),195962270, 55544515,    28.34%
Random                         ,220099126,223401423,   101.50%

Callgrind running on random 10,000 element list.
Merge sort: 61,298,879 Instructions
Stim sort:  58,411,259 Instructions

```
Ultimately, there is a couple percent overhead when working with truly random data. In terms of raw performance assuming a simple comparison function, even with random data, there is a small performance improvement. There is a noticeable increase in code size. It is over 330 lines of code. Same algorithm can be applied to slist and queue. The galloping can be applied to the insert sorted function.
```
Could someone take a look at the patch and see if it looks sensible?
```
```diff --git a/glib/glist.c b/glib/glist.c
index 252330a..885d7e9 100644
--- a/glib/glist.c
+++ b/glib/glist.c
@@ -1018,70 +1018,343 @@ g_list_insert_sorted_with_data (GList            *list,
return g_list_insert_sorted_real (list, data, (GFunc) func, user_data);
}

-static GList *
-g_list_sort_merge (GList     *l1,
-		   GList     *l2,
-		   GFunc     compare_func,
-		   gpointer  user_data)
+static void
+g_list_sort_merge (GList        *node_a,
+                        int           type_a,
+                        GList        *node_b,
+                        int           type_b,
+                        GFunc         compare_func,
+		                gpointer      user_data)
{
-  GList list, *l, *lprev;
-  gint cmp;
+  GList *merged_list;
+  GList *swap_temp_list;
+  GList *old_node_a;
+
+  if (!node_a)
+    {
+      return;
+    }
+  if (!node_b)
+    {
+      return;
+    }
+  if (!(type_a == 2 && type_b == 1) &&
+      ((GCompareDataFunc) compare_func) (node_a->data, node_b->data, user_data) > 0)
+    {
+      swap_temp_list = node_b;
+      node_b = node_a;
+      node_a = swap_temp_list;
+      if (type_b == 2)
+    }
+  else
+    {
+      if (type_a == 1)
+    }
+
+  while (1)
+    {
+      int step_count = 0;
+      do
+        {
+          if (step_count++ >= 8)
+            {
+              int step_size = 3;
+              int step_mul = 1;
+              int steps_done;
+              GList *gallop_node;
+              while (1)
+                {
+                  gallop_node = node_a;
+                  if (!node_a->next)
+                    {
+                      node_a->next = node_b;
+                      return;
+                    }
+                  for(steps_done = 0; steps_done < step_size; steps_done++)
+                    {
+                      if (!gallop_node->next)
+                        break;
+                      gallop_node = gallop_node->next;
+                    }
+                  if (((GCompareDataFunc) compare_func) (gallop_node->data, node_b->data, user_data) <= 0)
+                    {
+                      node_a = gallop_node;
+                      if (step_mul)
+                        step_size *= 2;
+                      else
+                        step_size -= steps_done / 2 ;
+                    }
+                  else
+                    {
+                      step_size = steps_done / 2;
+                      step_mul = 0;
+                    }
+                  if (!step_size)
+                    {
+                      old_node_a = node_a;
+                      node_a = node_a->next;
+                      break;
+                    }
+                }
+              step_count = 0;
+              break;
+            }
+          old_node_a = node_a;
+          node_a = node_a->next;
+          if (!node_a)
+            {
+              old_node_a->next = node_b;
+              return;
+            }
+        }
+      while (((GCompareDataFunc) compare_func) (node_a->data, node_b->data, user_data) <= 0);

-  l = &list;
-  lprev = NULL;
+      old_node_a->next = node_b;
+      swap_temp_list = node_b;
+      node_b = node_a;
+      node_a = swap_temp_list;
+    }
+
+}

-  while (l1 && l2)
+static void
+g_list_sort_extract (GList         *node,
+                     GFunc          compare_func,
+		             gpointer       user_data)
+{
+  int cmp;
+  int count = 0;
+  GList *new_list;
+  if (!node)
{
-      cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
-
-      if (cmp <= 0)
+      return;
+    }
+  if (!node->next)
+    {
+      return;
+    }
+  new_list = node;
+  while (1)
+    {
+      cmp = ((GCompareDataFunc) compare_func) (node->data, node->next->data, user_data);
+      if (cmp)
+        break;
+      node = node->next;
+      count++;
+      if (!node->next)
{
-	  l->next = l1;
-	  l1 = l1->next;
-        }
-      else
-	{
-	  l->next = l2;
-	  l2 = l2->next;
+          return;
}
-      l = l->next;
-      l->prev = lprev;
-      lprev = l;
}
-  l->next = l1 ? l1 : l2;
-  l->next->prev = l;
+  if (cmp < 0)
+    {
+      /* a < b so do ascending list */
+      node = node->next;
+      count += 2;
+      while(1)
+        {
+          if (!node->next)
+            {
+              return;
+            }
+          if (((GCompareDataFunc) compare_func) (node->data, node->next->data, user_data) > 0)
+            {
+              node->next = NULL;
+              return;
+            }
+          count++;
+          node = node->next;
+        }
+    }
+  else
+    {
+      /* a > b so do a descending list */
+      GList *cur_node;
+      GList *eq_node;
+
+      cur_node = node;
+      node = node->next;
+      cur_node->next = NULL;
+      cur_node = node;
+      node = node->next;
+      cur_node->next = new_list;
+      new_list = cur_node;
+      eq_node = new_list;
+      count += 2;
+      while(1)
+        {
+          if (!node)
+            {
+              return;
+            }
+          cmp = ((GCompareDataFunc) compare_func) (new_list->data, node->data, user_data);
+          if (cmp < 0)
+            {
+              return;
+            }
+          count++;
+          cur_node = node;
+          node = node->next;
+          if (cmp == 0)
+            {
+              cur_node->next = eq_node->next;
+              eq_node->next = cur_node;
+            }
+          else
+            {
+              cur_node->next = new_list;
+              new_list = cur_node;
+            }
+          eq_node = cur_node;
+
+        }
+    }
+}

-  return list.next;
+static void
+g_list_sort_body (GList         *node,
+                  GList         *left_list,
+                  int            left_count,
+                  int            left_type,
+                  int            want,
+                  GFunc          compare_func,
+		          gpointer       user_data)
+{
+  GList *right1_list, *right2_list;
+  int right1_count, right2_count;
+  int right1_type, right2_type;
+  GList *rest;
+  if (want < 16)
+    {
+      g_list_sort_extract (node,
+                           &right1_list, &right1_count, &right1_type,
+                           &rest,
+                           compare_func,
+                           user_data);
+    }
+  else
+    {
+      g_list_sort_body (node,
+                        left_list, left_count, left_type,
+                        &left_list, &left_count, &left_type,
+                        &right1_list, &right1_count, &right1_type,
+                        &rest,
+                        want/2,
+                        compare_func,
+                        user_data);
+    }
+
+  while (left_count < want && right1_count && right1_count < want)
+    {
+      int mywant = left_count > want / 3 ? want - left_count : left_count;
+      g_list_sort_body (rest,
+                        right1_list, right1_count, right1_type,
+                        &right1_list, &right1_count, &right1_type,
+                        &right2_list, &right2_count, &right2_type,
+                        &rest,
+                        mywant,
+                        compare_func,
+                        user_data);
+      g_list_sort_merge (left_list, left_type,
+                         right1_list, right1_type,
+                         &left_list, &left_type,
+                         compare_func,
+                         user_data);
+      left_count = left_count + right1_count;
+      right1_list = right2_list;
+      right1_count = right2_count;
+      right1_type = right2_type;
+    }
+  return;
}

-static GList*
-g_list_sort_real (GList    *list,
-		  GFunc     compare_func,
-		  gpointer  user_data)
+static GList*
+g_list_sort_real (GList*       list,
+                  GFunc        compare_func,
+		          gpointer     user_data)
{
-  GList *l1, *l2;
+  GList *node, *rest;
+  int count;
+  int type;
+  int want = g_list_length (list);

-  if (!list)
-    return NULL;
-  if (!list->next)
-    return list;
+  g_list_sort_extract (list, &node, &count, &type, &rest, compare_func, user_data);

-  l1 = list;
-  l2 = list->next;
-
-  while ((l2 = l2->next) != NULL)
+  g_list_sort_body (rest,
+                    node, count, type,
+                    &rest,
+                    want,
+                    compare_func,
+                    user_data);
+
+  GList *prev_node = NULL;
+  while (node)
{
-      if ((l2 = l2->next) == NULL)
-	break;
-      l1 = l1->next;
+      node->prev = prev_node;
+      prev_node = node;
+      node = node->next;
}
-  l2 = l1->next;
-  l1->next = NULL;
-
-  return g_list_sort_merge (g_list_sort_real (list, compare_func, user_data),
-			    g_list_sort_real (l2, compare_func, user_data),
-			    compare_func,
-			    user_data);
}

/**
@@ -1111,7 +1384,7 @@ g_list_sort_real (GList    *list,
**/
GList *
g_list_sort (GList        *list,
-	     GCompareFunc  compare_func)
+             GCompareFunc  compare_func)
{
return g_list_sort_real (list, (GFunc) compare_func, NULL);

@@ -1143,8 +1416,8 @@ g_list_sort (GList        *list,
**/
GList *
g_list_sort_with_data (GList            *list,
-		       GCompareDataFunc  compare_func,
-		       gpointer          user_data)
+                       GCompareDataFunc  compare_func,
+                       gpointer          user_data)
{
return g_list_sort_real (list, (GFunc) compare_func, user_data);
}
diff --git a/tests/Makefile.am b/tests/Makefile.am
index f78e9d5..13d9509 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -96,6 +96,7 @@ test_programs =					\
gio-test				\
iochannel-test				\
list-test				\
+	list-performance-test				\
mainloop-test				\
mapping-test				\
markup-collect				\