Re: Minor performance improvement in transition to external sort

On Tue, Feb 25, 2014 at 2:55 PM, Jeremy Harris <jgh(at)wizmail(dot)org> wrote:
> On 24/02/14 17:38, Robert Haas wrote:
>>
>> On Thu, Feb 20, 2014 at 7:27 PM, Jeremy Harris <jgh(at)wizmail(dot)org> wrote:
>>>
>>> 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.
>
>
> In the patched version, for the heapify operation the outer loop
> starts at the last heap-parent tuple and works backward to the
> start of the tuples array. A copy is taken of the SortTuple being
> operated on for the inner loop to use. This copy suffers cache misses.
>
> (The inner loop operates on elements between the copy source and the
> end of the array).
>
>
> In the original, the outer loop runs the array in increasing index
> order. Again a copy is taken of the SortTuple for the inner loop
> to use. This copy does not appear to take significant cache misses.
>
> (The inner loop operates on elements between the copy source and
> the start of the array).

Do you have any theory as to why this happens in one case but not the other?

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company