[GRASS-dev] r.univar -e

[Glynn Clements]

Hamish wrote:

> > > A few comments/questions before putting it in CVS:
> > 
> > > * qsort() comparison functions are declared as static int. 
> > > a) shouldn't they just be int?
> Brad:
> > static is the best declaration.  Declaring the function static means
> > it is "bound" to that file.  As long as qsort() is called [only] from
> > that file, it will work as designed.
> Glynn:
> > They aren't used from outside the file in which they are defined, so
> > they should be declared "static".
> > 
> > Note that "static" is a storage specifier; it isn't part of the type.
> 
> ok, I was thinking about the "global variable" use of that memory space.
> I guess the multi-file thing precludes qisort.c becoming a fast G_qsort()?

No. In my comments above, "used" refers to the point where the
variable's name appears.

If you have e.g. G_qsort(..., cmp_int), cmp_int is "used" in the file
in which the call occurs, not the file where G_qsort() is defined. So
long as the call occurs in the file where cmp_int is defined, it
doesn't matter if it is declared "static".

The "static" modifier on a global variable causes the symbol to be
omitted from the symbol table of the object file, so the symbol cannot
be referenced from another file. The object (variable, function) to
which the symbol refers can still be referenced via a pointer, just
not by name.

> > > b) could/should these fns be inlined for speed?
> > 
> > Indirect function calls (e.g. qsort() callbacks) cannot be inlined.
> > 
> > > * GRASS 5's s.cellstats uses something called qisort() instead of
> > > qsort(), which claims to be faster. Comments from the crowd?
> > >  http://freegis.org/cgi-bin/viewcvs.cgi/grass/src/sites/s.cellstats/qisort.c?rev=HEAD&content-type=text/vnd.viewcvs-markup
> > 
> > It claims to be faster than some specific qsort() implementations on a
> > specific system for specific test cases.
> > 
> > Unless there is empirical evidence that qisort() beats the system's
> > qsort() on the majority of systems with representative test data, I
> > would recommend sticking with the system's qsort() routine.
> 
> Martin:
> real    0m0.817s
> ..
> real    0m0.532s

That's a sample population of one, which is a rather small sample. 
Also, I don't know how representative the test data is.

> But I suppose the gcc/glibc people have their [good] reasons..........

The libc qsort() needs to work over a wide range of cases, in terms of
element size, number of elements, and whether the data is almost
sorted, unsorted almost reverse-sorted etc.

Some approaches do better for almost-sorted data at the expense of the
general case (or vice-versa), or have better worst-case behaviour at
the expense of the general case (or vice-versa).

In general terms, a sorting algorithm optimised for specific cases
will do better than a general-case one. If we were to add a single
G_qsort() function, we would need to consider all use cases rather
than choosing an algorithm based upon a specific case. OTOH, if we
were to add a selection of sorting functions, each case would need to
determine the correct one to use.

-- 
Glynn Clements <glynn at gclements.plus.com>