On Thu, Feb 20, 2014 at 7:27 PM, Jeremy Harris <j...@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 -- Sent via pgsql-hackers mailing list (firstname.lastname@example.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers