Re: [BK PATCH 1/2] Remove NGROUPS hardlimit (resend w/o qsort)

[Horst von Brand <vonbrand@inf.utfsm.cl>]

Timothy Hockin <th122948@scl2.sfbay.sun.com> said:

[...]

> +/* a simple shell-metzner sort */
> +static void groupsort(gid_t *grouplist, int gidsetsize)
> +{
> +	int right, left, cur, max, stride;
> +
> +	stride = gidsetsize / 2;

This guarantees bad performance for certain gidgetsizes... customary wisdom
(at least, Knuth sayeth so) is to go:

        for(stride = 1; stride < gidgetsize; stride = 3 * stride + 1)
		;
        do {
           stride /= 3;
           ...
        } while (stride > 1) {

> +	while (stride) {
> +		max = gidsetsize - stride;
> +
> +		for (left = 0; left < max; left++) {
> +			cur = left;
> +			while (cur >= 0) {
> +				right = cur + stride;
> +				if (grouplist[right] < grouplist[cur]) {
> +					gid_t tmp = grouplist[cur];
> +					grouplist[cur] = grouplist[right];
> +					grouplist[right] = tmp;
> +					cur -= stride;
> +				} else {
> +					break;
> +				}
> +			}

You should work by stuffing the new element in a temporary variable, and
just shift the greater ones up, then stuff the one in

My version of shellsort (h is stride, n is size) goes:

  /*
   * shellsort.c: Shell sort
   */

  #include "sort.h"

  void
  sort(double a[], int n)

  {
    int i, j, h;
    double tmp;

    for(h = 1; h < n; h = 3 * h + 1)
      ;

    do {
      h /= 3;
      for(i = h; i < n; i++) {
	tmp = a[i];
	for(j = i - h; j >= 0 && tmp < a[j]; j -= h)
	  a[j + h] = a[j];
	a[j + h] = tmp;
      }
    } while(h > 1);
  }

This gets around bad h (stride) values, and does just a bit more than 1
assignment per element moved in the inner loop (you do 3). Plus it is
shorter ;-)
-- 
Dr. Horst H. von Brand                   User #22616 counter.li.org
Departamento de Informatica                     Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria              +56 32 654239
Casilla 110-V, Valparaiso, Chile                Fax:  +56 32 797513