resortAllItems findings

[Mark]

On Tue, Jul 30, 2013 at 10:12 PM, Mark <markg85 at gmail.com> wrote:
> On Tue, Jul 30, 2013 at 5:11 PM, Frank Reininghaus
> <frank78ac at googlemail.com> wrote:
>> Hi,
>>
>> 2013/7/30 Mark:
>>> On Tue, Jul 30, 2013 at 10:45 AM, Frank Reininghaus
>>> <frank78ac at googlemail.com> wrote:
>>>>
>>>> Hi Mark,
>>>>
>>>> 2013/7/29 Mark:
>>>> > The first things that i noticed are:
>>>> > - oldUrls is being created, is that needed?
>>>>
>>>> Yes, is needed for the itemsMoved signal.
>>>>
>>>> > - m_groups is cleared but never filled again, why?
>>>>
>>>> It is filled again lazily when the view requests information about the
groups.
>>>>
>>>> > - m_items is cleared and refilled, but is that actually needed?
>>>>
>>>> In principle, it is not necessary to clear m_items. We could just
>>>> update the entries without removing them first. However, that could
>>>> lead to subtle bugs if not done correctly.
>>>>
>>>>
>>>> Assume that there is one file 'a' in the directory. m_items will then
>>>> have one entry with the key 'a' and the value 0 (the index of the
>>>> item).
>>>>
>>>> If 'a' is renamed to 'b', and we do not remove the entry 'a', then
>>>> m_items would have two entries 'a' and 'b' which both point to the
>>>> same index 0. This could cause trouble later on. The unit tests would
>>>> even crash because they verify the consistency of the model with an
>>>> assert.
>>>
>>> my assumption with looking at that code was that it's being called
>>> when you press one of the header columns. It's should be just
>>> resorting - like the name implies, right?
>>>
>>> To check if my assumption is right i debugged this. A rename is
>>> causing KFileItemModel::slotRefreshItems to be called which is
>>> executed before resortAllItems and is already updating m_items when
>>> needed. I didn't do more testing like deletion or moving files, but
>>> i'm fairly sure that those all trigger some other function prior to
>>> resortAllItems that update m_items as well which leads me to think
>>> that resortAllItems should have no need to rebuild m_items as it's
>>> just not needed and causes overhead for the resorting operation.
>>
>> When inline renaming is used, DolphinView calls
>> KFileItemModel::setData(), which does not update m_items AFAICS. It
>> might still be that we receive a refreshItems signal later on, which
>> then updates m_items. But I'm not sure, and I don't want to risk
>> regressions at this point of the release cycle. Moreover, how much
>> time does it save, actually? Did you do some benchmarking and see that
>> not clearing m_items does improve the performance significantly? If
>> yes, how does it compare to the improvement you get if you keep
>> m_items.clear(), but then reserve the (already known) amount of space
>> that is needed for all items?
>>
>> Regards,
>> Frank
>
> I had it benchmarked but didn't save the actual numbers. I will re-run
> that and report back in here with some numbers.

Hi Frank,

Here are some benchmarks. They are from git KDE/4.11 bransh with hash:
f6bbc7d224eb2cb3d0b3665fd9af19e1164eaa97

Apparently the first time i press the header for resorting, the operation
is a lot more expensive

== Stock benchmark, no code changes by me ==
dolphin(2362) KFileItemModel::resortAllItems:
===========================================================
dolphin(2362) KFileItemModel::resortAllItems: Resorting 500000 items
dolphin(2362) KFileItemModel::resortAllItems: [TIME] Resorting of 500000
items: 1890
dolphin(2362) KFileItemModel::resortAllItems:
===========================================================
dolphin(2362) KFileItemModel::resortAllItems: Resorting 500000 items
dolphin(2362) KFileItemModel::resortAllItems: [TIME] Resorting of 500000
items: 1112
dolphin(2362) KFileItemModel::resortAllItems:
===========================================================
dolphin(2362) KFileItemModel::resortAllItems: Resorting 500000 items
dolphin(2362) KFileItemModel::resortAllItems: [TIME] Resorting of 500000
items: 1110
dolphin(2362) KFileItemModel::resortAllItems:
===========================================================
dolphin(2362) KFileItemModel::resortAllItems: Resorting 500000 items
dolphin(2362) KFileItemModel::resortAllItems: [TIME] Resorting of 500000
items: 1125

== Removing the rebuilding of m_items completely ==
Diff: http://paste.kde.org/p649ae3ea/
dolphin(2958) KFileItemModel::resortAllItems:
===========================================================
dolphin(2958) KFileItemModel::resortAllItems: Resorting 500000 items
dolphin(2958) KFileItemModel::resortAllItems: [TIME] Resorting of 500000
items: 1457
dolphin(2958) KFileItemModel::resortAllItems:
===========================================================
dolphin(2958) KFileItemModel::resortAllItems: Resorting 500000 items
dolphin(2958) KFileItemModel::resortAllItems: [TIME] Resorting of 500000
items: 713
dolphin(2958) KFileItemModel::resortAllItems:
===========================================================
dolphin(2958) KFileItemModel::resortAllItems: Resorting 500000 items
dolphin(2958) KFileItemModel::resortAllItems: [TIME] Resorting of 500000
items: 684
dolphin(2958) KFileItemModel::resortAllItems:
===========================================================
dolphin(2958) KFileItemModel::resortAllItems: Resorting 500000 items
dolphin(2958) KFileItemModel::resortAllItems: [TIME] Resorting of 500000
items: 701

== Your request: keep clear + reserve ==
Diff: http://paste.kde.org/p2b5ee46d/
dolphin(3491) KFileItemModel::resortAllItems:
===========================================================
dolphin(3491) KFileItemModel::resortAllItems: Resorting 500000 items
dolphin(3491) KFileItemModel::resortAllItems: [TIME] Resorting of 500000
items: 1876
dolphin(3491) KFileItemModel::resortAllItems:
===========================================================
dolphin(3491) KFileItemModel::resortAllItems: Resorting 500000 items
dolphin(3491) KFileItemModel::resortAllItems: [TIME] Resorting of 500000
items: 1100
dolphin(3491) KFileItemModel::resortAllItems:
===========================================================
dolphin(3491) KFileItemModel::resortAllItems: Resorting 500000 items
dolphin(3491) KFileItemModel::resortAllItems: [TIME] Resorting of 500000
items: 1134
dolphin(3491) KFileItemModel::resortAllItems:
===========================================================
dolphin(3491) KFileItemModel::resortAllItems: Resorting 500000 items
dolphin(3491) KFileItemModel::resortAllItems: [TIME] Resorting of 500000
items: 1109

Also, i explicitly tested inline renaming and m_items is updated before
resortAllItems is being called.

I also tried further optimizations without removing functionality but that
didn't add (or actually remove) more miliseconds so the above results have
to do for now.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.kde.org/mailman/private/kfm-devel/attachments/20130731/96736438/attachment.htm>