On Thu, Feb 20, 2014 at 7:27 PM, Jeremy Harris <jgh@wizmail.org> wrote:
> 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.
Can you explain this further? This seems like an important clue that
could be useful when trying to optimize this code, but I'm a little
unclear which part of the operation has more cache misses with your
changes and why.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company