D11282: less expensive findByUrl in KCoreDirListerCache

[Jaime Torres Amate]

jtamate abandoned this revision.

REPOSITORY
  R241 KIO

REVISION DETAIL
  https://phabricator.kde.org/D11282

To: jtamate, #frameworks, dfaure
Cc: kde-frameworks-devel, bruns, mwolff, michaelh, ngraham

D11282: less expensive findByUrl in KCoreDirListerCache

[Jaime Torres Amate]

jtamate added a comment.


  About the KCoreDirLister::Private::addNewItems method, benchmarking the 
current and sorted list implementation with 5000 fileItems:
  
  It only takes 1.5 msecs per iteration without filters and 1.9 msecs with a 
nameFilter and a mimeFilter.
  For reference, doing a std::partition of a copy of the list with 
isItemVisible also takes 1.5 msecs per iteration without filters and 1.4 with 
filters.

INLINE COMMENTS

> mwolff wrote in kcoredirlister.cpp:852
> is it OK that you operate on a copy of the item here? the item in the hash 
> won't be modified, is that on purpose?

The item in the hash will be refreshed, but not the item returned.
This is not called when a rename is detected, therefore the key(url) is the 
same.

REPOSITORY
  R241 KIO

REVISION DETAIL
  https://phabricator.kde.org/D11282

To: jtamate, #frameworks, dfaure
Cc: kde-frameworks-devel, bruns, mwolff, michaelh, ngraham

D11282: less expensive findByUrl in KCoreDirListerCache

[Stefan Brüns]

bruns added inline comments.

INLINE COMMENTS

> mwolff wrote in kcoredirlister.cpp:2532
> this can be slow, see above

To make this more efficient, a little bit of reshuffling is needed IMHO:

1. Move the filter implementation from  `KDL::Private::addNewItem(...)` to 
`KDL::Private::addNewItems(...)`, i.e. sort the `items` based on 
`->matchesMimeFilter(item)` into two new QHashes
2. For each partition, use QHash::unite() to merge it into the respective list

3. Make `KDL::Private::addNewItem(...)` a wrapper function for 
`KDL::Private::addNewItems(...)`.

REPOSITORY
  R241 KIO

REVISION DETAIL
  https://phabricator.kde.org/D11282

To: jtamate, #frameworks, dfaure
Cc: kde-frameworks-devel, bruns, mwolff, michaelh, ngraham

D11282: less expensive findByUrl in KCoreDirListerCache

[Stefan Brüns]

bruns added inline comments.

INLINE COMMENTS

> dfaure wrote in kcoredirlister.cpp:852
> That was the case already hmm but not in my version of kio. It looks like 
> this patch is on top of other patches.

D10742  - this makes it even harder to 
review ...

> mwolff wrote in kcoredirlister.cpp:1970
> O(N) iteration over a large hash is extremely slow, is this done elsewhere? 
> if so, then you may need to find an alternative approach - potentially via 
> multiple containers or by using a sorted vector after all like you proposed 
> initially

My proposal:
A few lines earlier, a `KFileItemList` (~`QList)

REPOSITORY
  R241 KIO

REVISION DETAIL
  https://phabricator.kde.org/D11282

To: jtamate, #frameworks, dfaure
Cc: kde-frameworks-devel, bruns, mwolff, michaelh, ngraham

D11282: less expensive findByUrl in KCoreDirListerCache

[Stefan Brüns]

bruns added a comment.
Restricted Application added a subscriber: kde-frameworks-devel.


  @jtamate - can you use `arc --diff` next time you create a revision, instead 
of using the web upload?
  
  Not using arc results in phabricator being unable to show the context 
("Context not available"), which makes reviewing considerably harder.
  
  See https://secure.phabricator.com/T5029 for background info.

REPOSITORY
  R241 KIO

REVISION DETAIL
  https://phabricator.kde.org/D11282

To: jtamate, #frameworks, dfaure
Cc: kde-frameworks-devel, bruns, mwolff, michaelh, ngraham

D11282: less expensive findByUrl in KCoreDirListerCache

[Jaime Torres Amate]

jtamate added a dependency: D12945: kcoredirlister lstItems benchmark.

REPOSITORY
  R241 KIO

REVISION DETAIL
  https://phabricator.kde.org/D11282

To: jtamate, #frameworks, dfaure
Cc: mwolff, michaelh, ngraham, bruns

D11282: less expensive findByUrl in KCoreDirListerCache

[David Faure]

dfaure requested changes to this revision.
dfaure added a comment.
This revision now requires changes to proceed.


  This definitely needs a benchmark. (use Q_BENCHMARK in a qtestlib-based 
unittest)

INLINE COMMENTS

> mwolff wrote in kcoredirlister.cpp:852
> is it OK that you operate on a copy of the item here? the item in the hash 
> won't be modified, is that on purpose?

That was the case already hmm but not in my version of kio. It looks like 
this patch is on top of other patches.

REPOSITORY
  R241 KIO

REVISION DETAIL
  https://phabricator.kde.org/D11282

To: jtamate, #frameworks, dfaure
Cc: mwolff, michaelh, bruns

D11282: less expensive findByUrl in KCoreDirListerCache

[Milian Wolff]

mwolff added a comment.


  I'm not into the code base, just adding some comments to ensure everything is 
taken into account - maybe your initial attempt was better after all...

INLINE COMMENTS

> kcoredirlister.cpp:852
> +if (refresh) {
> +(*it).refresh();
>  }

is it OK that you operate on a copy of the item here? the item in the hash 
won't be modified, is that on purpose?

> kcoredirlister.cpp:1970
>  // Delete all remaining items
> -QMutableListIterator it(lstItems);
> +QMutableHashIterator it(hashItems);
>  while (it.hasNext()) {

O(N) iteration over a large hash is extremely slow, is this done elsewhere? if 
so, then you may need to find an alternative approach - potentially via 
multiple containers or by using a sorted vector after all like you proposed 
initially

> kcoredirlister.cpp:2532
>  // Of course if there is no filter and we can do a range-insertion 
> instead of a loop, that might be good.
> -QList::const_iterator kit = items.begin();
> -const QList::const_iterator kend = items.end();
> +auto kit = items.begin();
> +const auto kend = items.end();

this can be slow, see above

REPOSITORY
  R241 KIO

REVISION DETAIL
  https://phabricator.kde.org/D11282

To: jtamate, #frameworks, dfaure
Cc: mwolff, michaelh, ngraham

D11282: less expensive findByUrl in KCoreDirListerCache

[Jaime Torres Amate]

jtamate updated this revision to Diff 29574.
jtamate edited the summary of this revision.
jtamate edited the test plan for this revision.
jtamate added a comment.


  Depends on https://phabricator.kde.org/D10742, including the diff.

REPOSITORY
  R241 KIO

CHANGES SINCE LAST UPDATE
  https://phabricator.kde.org/D11282?vs=29388=29574

REVISION DETAIL
  https://phabricator.kde.org/D11282

AFFECTED FILES
  src/core/kcoredirlister.cpp
  src/core/kcoredirlister_p.h

To: jtamate, #frameworks, dfaure
Cc: mwolff, michaelh, ngraham

D11282: less expensive findByUrl in KCoreDirListerCache

[Milian Wolff]

mwolff added a comment.


  have you considered using a hash map instead?

REPOSITORY
  R241 KIO

REVISION DETAIL
  https://phabricator.kde.org/D11282

To: jtamate, #frameworks, dfaure
Cc: mwolff, michaelh

D11282: less expensive findByUrl in KCoreDirListerCache

[Jaime Torres Amate]

jtamate created this revision.
jtamate added reviewers: Frameworks, dfaure.
Restricted Application added a project: Frameworks.
jtamate requested review of this revision.

REVISION SUMMARY
  From O(n) in the worst case to at most Log2(n) + O(1) comparisons.
  Unfortunately, fetching the files in a directory is now a little more 
expensive.
  
  CCBUG: 320231

TEST PLAN
  findByUrl was slow, for example, renaming 50.000 small files, it has to go 
through a list of 50.000 items 50.000 times, so renaming that number of files 
takes more than an hour, now it takes less time, but baloo re-scanning and the 
dirlister re-scanning the directory doesn't help to reduce the time.
  
  Moving 50.000 small files from sftp://127.0.0.1/borrar to /borrar1, the first 
step, fetching data from the dirlister took more than 1 minute, now it is 
instantaneous.

REPOSITORY
  R241 KIO

REVISION DETAIL
  https://phabricator.kde.org/D11282

AFFECTED FILES
  src/core/kcoredirlister.cpp

To: jtamate, #frameworks, dfaure
Cc: michaelh