shithub: riscv

Download patch

ref: b5086c1863fe10faf48ab675f503e562ec8dfcf0
parent: 51b22d8548e61d3807b8b94e09d84f116ca0eb1c
author: Ori Bernstein <[email protected]>
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 {