[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: new module "mpsort" for faster sorting
From: |
Bruno Haible |
Subject: |
Re: new module "mpsort" for faster sorting |
Date: |
Mon, 29 Jan 2007 12:53:16 +0100 |
User-agent: |
KMail/1.9.1 |
Jim Meyering wrote:
> When sorting records larger than a pointer, reduced data movement is
> likely to be the overriding factor: better use of cache.
> I.e., setting up the array of pointers costs just O(N) time and memory,
> but you save O(N log(N)) time in reduced data copying costs, because
> mpsort is swapping only pointers, whereas qsort swaps the entire (larger)
> records.
This is undoubtable.
My question is: Once you have switched from an array representation with
sizeof (element) > sizeof (void *) to an array representation with
sizeof (element) == sizeof (void *), you still have 3 ways to sort:
a) with qsort and a comparison function that does
int cmp (void **p, void **q) { return element_cmp (*p, *q); }
b) with a mergesort implementation that looks like mpsort, but calls
cmp (&ba, &bb)
instead of
cmp (ba, bb)
and instead does the indirection in the comparison function:
int cmp (void **p, void **q) { return element_cmp (*p, *q); }
c) with the mpsort function as it is, and element_cmp as the comparison
function.
Does the major speedup come from the transition a) -> b), or from the
transition b) -> c) ?
Bruno