On 09/02/14 17:11, Jeremy Harris wrote:
> On 06/02/14 18:21, Jeff Janes wrote:
>> Did you try sorting already-sorted, reverse
>> sorted, or pipe-organ shaped data sets? We will also need to test it on
>> strings. I usually use md5(random()::text) to generate strings for such
>> purposes, at least for a first pass.
>
> Attached is version 2 of the patch, which fixes the performance on
> constant-input.
Having beaten on this some more I'm prepared to abandon it.
The wallclock time, for random input, drifts up at larger N
(compared to the existing code) despite the number of comparisons
being consistently less.
Run under cachegrind, it takes about N/10 last-level cache misses,
all for the new item being introduced to the heap. The existing
code takes none at all.
It might be worthwhile for a seriously expensive comparison function;
say, more than 50 clocks. For integers and md5-strings it isn't.
--
Cheers, Jeremy