git: 9front

Download patch

ref: 0f07ed9bb0712dfab2af7d6ad9457df6c2ab6554
parent: be866d7cc86997ed3ba677308e8cf5cc0342091c
author: Ori Bernstein <ori@eigenstate.org>
date: Sun Nov 1 06:23:39 EST 2020

libc: recurse on smaller half of array

Our qsort has an optimization to recurse on one
half of the array, and do a tail call on the other
half. Unfortunately, the condition deciding which
half of the array to recurse on was wrong, so we
were recursing on the larger half of the array and
iterating on the smaller half.

This meant that if we picked the partition poorly,
we were pessimizing our stack usage instead of
optimizing it.

This change reduces our stack usage from O(n)
to O(log(n)) for poorly chosen pivots.

--- a/sys/src/libc/port/qsort.c

+++ b/sys/src/libc/port/qsort.c

@@ -100,7 +100,7 @@

 		j = (pj - a) / es;

 		n = n-j-1;

-		if(j >= n) {

+		if(j < n) {

 			qsorts(a, j, p);

 			a += (j+1)*es;

 		} else {

-- 

⑨