py/objlist: Make a small code size optimization in mp_quicksort.

While clarifying the meaning of the arguments to `mp_quicksort`, I noticed
that by pre-adjusting the `head` argument similar to what was already done
for `tail`, code size could be saved by eliminating repeated calculation of
`h + 1`.

Signed-off-by: Jeff Epler <jepler@unpythonic.net>

1 files changed, 18 insertions, 6 deletions

diff --git a/py/objlist.c b/py/objlist.c
index 71414a849..5a94ba8d9 100644
--- a/py/objlist.c
+++ b/py/objlist.c
@@ -277,10 +277,20 @@ static mp_obj_t list_pop(size_t n_args, const mp_obj_t *args) {
     return ret;
 }
 
+// "head" is actually the *exclusive lower bound* of the range to sort. That is,
+// the first element to be sorted is `head[1]`, not `head[0]`. Similarly `tail`
+// is an *inclusive upper bound* of the range to sort. That is, the final
+// element to sort is `tail[0]`, not `tail[-1]`.
+//
+// The pivot element is always chosen as `tail[0]`.
+//
+// These unusual choices allows structuring the partitioning
+// process as a do/while loop, which generates smaller code than the equivalent
+// code with usual C bounds & a while or for loop.
 static void mp_quicksort(mp_obj_t *head, mp_obj_t *tail, mp_obj_t key_fn, mp_obj_t binop_less_result) {
     mp_cstack_check();
-    while (head < tail) {
-        mp_obj_t *h = head - 1;
+    while (tail - head > 1) { // So long as at least 2 elements remain
+        mp_obj_t *h = head;
         mp_obj_t *t = tail;
         mp_obj_t v = key_fn == MP_OBJ_NULL ? tail[0] : mp_call_function_1(key_fn, tail[0]); // get pivot using key_fn
         for (;;) {
@@ -291,19 +301,21 @@ static void mp_quicksort(mp_obj_t *head, mp_obj_t *tail, mp_obj_t key_fn, mp_obj
             if (h >= t) {
                 break;
             }
+            // A pair of objects must be swapped to the other side of the partition
             mp_obj_t x = h[0];
             h[0] = t[0];
             t[0] = x;
         }
+        // Place the pivot element in the proper position
         mp_obj_t x = h[0];
         h[0] = tail[0];
         tail[0] = x;
         // do the smaller recursive call first, to keep stack within O(log(N))
-        if (t - head < tail - h - 1) {
+        if (t - head < tail - h) {
             mp_quicksort(head, t, key_fn, binop_less_result);
-            head = h + 1;
+            head = h;
         } else {
-            mp_quicksort(h + 1, tail, key_fn, binop_less_result);
+            mp_quicksort(h, tail, key_fn, binop_less_result);
             tail = t;
         }
     }
@@ -327,7 +339,7 @@ mp_obj_t mp_obj_list_sort(size_t n_args, const mp_obj_t *pos_args, mp_map_t *kw_
     mp_obj_list_t *self = MP_OBJ_TO_PTR(pos_args[0]);
 
     if (self->len > 1) {
-        mp_quicksort(self->items, self->items + self->len - 1,
+        mp_quicksort(self->items - 1, self->items + self->len - 1,
             args.key.u_obj == mp_const_none ? MP_OBJ_NULL : args.key.u_obj,
             args.reverse.u_bool ? mp_const_false : mp_const_true);
     }