This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: quicksort


Hi,

Carlos O'Donell suggested talking about the code first before stating
with the paperwork.  I think this is a sane suggestion.

A few related remarks:

 * A badly chosen pivot lowers the number of swaps needed, a really
   badly chosen pivot leads to something with a performance comparable
   to selection sort.

 * The correctness of the median of three selection with detection of
   equal elements is not that obvious at first sight, thus I verified
   a simpler version, e.g., without a comparison function, using
   Frama-C's plugin jessie (not in a very beautiful way, though).

 * An earlier version did check if LONG_MAX equals to INT_MAX and set up
   the SWAP macro accordingly to also check if int-wise swaps are
   possible if they aren't equal.

 * The insertion sort at the end (which is btw. with todays cache sizes
   hardly a performance gain in comparison to running insertion sort on
   small arrays) does not use the tuned SWAP macro and it always adds
   about N comparisons.

 * The documentation update in my latest commit might contain relevant
   additional information.

 * The size of the compiled object could be reduced by moving the
   pseudo-median of nine selection to a non-inlined function.  In my
   tests I could save about 500 byte (after stripping) when compiled
   with -Os or -O2.


* Ryan S. Arnold [2011-11-29 09:49 -0600]:
> Patents: This restricts implementation. ?In order for the FSF to
> accept code that utilizes patents I believe the FSF needs to have
> patent cross-licensing (or some other use permit) on file.

Just for completeness, the earlier multi-pivot patent [1] contains the
following claim:

| A method for improving the software algorithm in claim 1 involving
| comparing the current pivot about to be partitioned with the last
| pivot, and if these two pivots are equal, pivoting equal records
| remaining in the unpartitioned list between the previous pivot and the
| current pivot. This improvement handles duplicate records during
| runtime and adds very little overhead.

My code also compares pivots to handle equal elements, but both
approaches are completely different (I could be more verbose about this
if required).

 [1] http://www.google.com/patents/about?id=RwCkAAAAEBAJ


> Copyright: This denotes ownership of THIS specific block of code/text.
> This indicates who will defend the license in the event of an
> infringement. ?You may release different versions of the code onto the
> net with different copyrights as long as you hold exclusive license to
> the original.

My original version contains the following code (due a lack of
creativity I used the variable names from Bentley and McIlroy):

| if ((r1 = CMP(pa, pd)) > 0) SWAP(pa, pd);
| if ((r2 = CMP(pa, pv)) > 0) SWAP(pa, pv);

The code on github contains this code:

| if ((r1 = ((*cmp) ((void *) hi, (void *) lo, arg))) < 0)
|    SWAP (hi, lo);
| if ((r2 = ((*cmp) ((void *) hi, (void *) mid, arg))) < 0)
|    SWAP (hi, mid);

There are code blocks that are even more similar and some that are
completely different.  I did not assume that these versions really could
count as different work (work might not be the correct term in this
case, but my intention should be clear).  If what you wrote above
applies in this case, then we just need to talk about the code and do
the paperwork afterwards.


Notes related to the copyright:

 * Although the way I handle multisets is heavily based on Justin Peel's
   idea of alternating the side to place the equal elements, I did not
   use any of his code or even a similar algorithm.

 * The partitioning code is nearly identical to the one used in a paper
   "R. Geoff Dromey", but has been written before I read this paper
   (there aren't that many ways to implement partitioning).


Carsten


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]