[PATCH] Binheap performance improvements

[Aliaksandr Valialkin]

cc'ing varnish-dev

On Thu, Oct 13, 2011 at 3:51 PM, Aliaksandr Valialkin <valyala at gmail.com> wrote:
> On Thu, Oct 13, 2011 at 3:10 AM, Artur Bergman <sky at crucially.net> wrote:
>> Just so I follow, it helps when pages that are part of the binheap are swapped out?
>
> Almost correct, except that the current implementation touches
> external pages via cmp(key1, key2) and update(index) callbacks while
> traversing and updating the binheap. So the total number of pages,
> which can be potentially touched by binheap (;et's call this set of
> pages 'working set') can become quite big under certain conditions
> such as large-size structures, which embed key and index and high
> fragmentation of these structures in memory. For the reference,
> current size of objcore, which embeds key and index, is 120 bytes. See
> my remarks for test results in the comment to the second patch for
> more details.
>
> The patch significantly reduces working set for binheap and makes the
> size of the working set more predictable. This provides two benefits:
> - Speedup when pages from binheap working set are swapped out.
> - Speedup due to reduced probability of swapping out other pages when
> swapping in binheap pages. Imagine that these 'other' pages contain
> cache data.
>
>> Artur
>>
>> On Oct 12, 2011, at 4:56 PM, Aliaksandr Valialkin wrote:
>>
>>> Hi there.
>>>
>>> Could you look into this pull request:
>>> https://github.com/varnish/Varnish-Cache/pull/1 ?
>>>
>>> I attached patches from the pull request. The first two are essential,
>>> while the last two are just small cleanups. I could merge them with
>>> the second patch, but didn't do this, since the corresponding commits
>>> were already published on github and history rewrites are considered
>>> bad :)
>>> These patches should improve Varnish performance when its cache don't fit RAM.
>>>
>>> --
>>> Best Regards,
>>>
>>> Aliaksandr
>>> <0001-Binheap-test-improvements.patch><0002-Major-binheap-refactoring.patch><0003-added-missing-parentheses.patch><0004-verify-idx-value-for-pointers-from-malloc_list.patch>_______________________________________________
>>> varnish-dev mailing list
>>> varnish-dev at varnish-cache.org
>>> https://www.varnish-cache.org/lists/mailman/listinfo/varnish-dev
>>
>>
>
>
>
> --
> Best Regards,
>
> Aliaksandr
>



-- 
Best Regards,

Aliaksandr