Review Request 123620: Fix sorting performance regression by avoiding unnecessary copying of the QCollator

Mon May 4 23:27:39 BST 2015

-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://git.reviewboard.kde.org/r/123620/#review79875
-----------------------------------------------------------

Ship it!

Wow, awesome performance win :)
Thanks!

> I think it might sense to move some or all of the lessThan-related code out of the KFileItemModel class to make it more maintainable.

Yes I absolutely agree with you and I think we can go even further and move the roles updating and group value computation out of it as well.

Maybe we can make plugins out of it.

Possible base classes/interfaces:
* RolesProviderPlugin (creates AbstractRolesProvider, SortRole and GroupRole instances)
* AbstractRolesProvider
* SortRole (implements basic string comparism as fallback)
* GroupRole (returns default group value)

E.g. a KFileItem roles provider:
* KFileItemRolesProviderPlugin implements RolesProviderPlugin
* KFileItemRolesProvider implements AbstractRolesProvider
* DateSortRole extends SortRole
* DateGroupRole extends GroupRole
* TextGroupRole extends GroupRole
* PermissionGroupRole extends GroupRole
* ...

E.g. a Baloo roles provider:
* BalooRolesProviderPlugin implements RolesProviderPlugin
* BalooRolesProvider implements AbstractRolesProvider
* RatingSortRole extends SortRole
* RatingGroupRole extends GroupRole
* ...

And depending on the current sort role, the roles provider plugins create the appropriate sort/group role instances, which can then be used in lessThan.

- Emmanuel Pescosta

On May 3, 2015, 11:14 p.m., Frank Reininghaus wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://git.reviewboard.kde.org/r/123620/
> -----------------------------------------------------------
> 
> (Updated May 3, 2015, 11:14 p.m.)
> 
> 
> Review request for Dolphin.
> 
> 
> Repository: dolphin
> 
> 
> Description
> -------
> 
> I have found that the sorting performance when loading large folders is much worse than in the kdelibs 4.x-based Dolphin versions. The reason is the switch from KStringHandler::naturalCompare(...) to QCollator, which made creating copies of the QCollator object necessary (see https://git.reviewboard.kde.org/r/121817/) in order to fix crashes because QCollator's functions are, unlike KStringHandler::naturalCompare(...), not thread-safe.
> 
> This patch does the following:
> 
> 1. Simplify the benchmarks in kfileitemmodelbenchmark. Currently, the benchmarks are run for many different folder sizes, which was motivated by the O(N^2) complexity which earlier Dolphin versions had if many files with some specific patterns were added. Since these issues have been fixed a long time ago, I think that it makes sense to run the benchmarks for a single folder size only. This makes it much easier to understand the benchmark results at first sight and identify any performance regressions.
> 
> 2. Prevent that unnecessary expensive copies of the QCollator object are made. A copy is only needed if a new thread is forked. In all other cases, the "lessThan" object, which contains the QCollator, can be passed by const reference. I achieved that with rather small code changes, but they are a bit ugly - the only way to force the std::lower_bound and std::upper_bound functions to take a const reference was to specify the template arguments explicitly.
> 
> My next plans would be to add a benchmark which actually benchmarks natural sorting (the current benchmark disables it because its intention was to test the code that inserts items into the model). This could help to investigate if making use of QCollator::sortKey() might speed up sorting. Moreover, I think it might sense to move some or all of the lessThan-related code out of the KFileItemModel class to make it more maintainable.
> 
> 
> Diffs
> -----
> 
>   src/kitemviews/private/kfileitemmodelsortalgorithm.h 50db990 
>   src/tests/kfileitemmodelbenchmark.cpp 3ff0405 
> 
> Diff: https://git.reviewboard.kde.org/r/123620/diff/
> 
> 
> Testing
> -------
> 
> Unit tests still pass. I have verified (with some debug output in KFileItemModelLessThan::operator()) that different threads use different collator objects.
> 
> Benchmark results before/after this patch (with Qt, KF5 and Dolphin built in release mode) show that the performance is improved considerably:
> 
> Before:
> 
> ********* Start testing of KFileItemModelBenchmark *********
> Config: Using QtTest library 5.4.1, Qt 5.4.1 (x86_64-little_endian-lp64 shared (dynamic) release build; by GCC 4.8.3 20140627 [gcc-4_8-branch revision 212064])
> PASS   : KFileItemModelBenchmark::initTestCase()
> PASS   : KFileItemModelBenchmark::insertAndRemoveManyItems(all--n=100000)
> RESULT : KFileItemModelBenchmark::insertAndRemoveManyItems():"all--n=100000":
>      2,575 msecs per iteration (total: 2,575, iterations: 1)
> PASS   : KFileItemModelBenchmark::insertAndRemoveManyItems(1st half + 2nd half--n=100000)
> RESULT : KFileItemModelBenchmark::insertAndRemoveManyItems():"1st half + 2nd half--n=100000":
>      2,596 msecs per iteration (total: 2,596, iterations: 1)
> PASS   : KFileItemModelBenchmark::insertAndRemoveManyItems(2nd half + 1st half--n=100000)
> RESULT : KFileItemModelBenchmark::insertAndRemoveManyItems():"2nd half + 1st half--n=100000":
>      2,594 msecs per iteration (total: 2,594, iterations: 1)
> PASS   : KFileItemModelBenchmark::insertAndRemoveManyItems(even + odd--n=100000)
> RESULT : KFileItemModelBenchmark::insertAndRemoveManyItems():"even + odd--n=100000":
>      2,609 msecs per iteration (total: 2,609, iterations: 1)
> PASS   : KFileItemModelBenchmark::insertAndRemoveManyItems(all - 2nd half--n=100000)
> RESULT : KFileItemModelBenchmark::insertAndRemoveManyItems():"all - 2nd half--n=100000":
>      2,626 msecs per iteration (total: 2,626, iterations: 1)
> PASS   : KFileItemModelBenchmark::insertAndRemoveManyItems(all - 1st half--n=100000)
> RESULT : KFileItemModelBenchmark::insertAndRemoveManyItems():"all - 1st half--n=100000":
>      2,610 msecs per iteration (total: 2,610, iterations: 1)
> PASS   : KFileItemModelBenchmark::insertAndRemoveManyItems(all - odd--n=100000)
> RESULT : KFileItemModelBenchmark::insertAndRemoveManyItems():"all - odd--n=100000":
>      2,636 msecs per iteration (total: 2,636, iterations: 1)
> PASS   : KFileItemModelBenchmark::cleanupTestCase()
> Totals: 9 passed, 0 failed, 0 skipped, 0 blacklisted
> ********* Finished testing of KFileItemModelBenchmark *********
> 
> 
> After:
> 
> ********* Start testing of KFileItemModelBenchmark *********
> Config: Using QtTest library 5.4.1, Qt 5.4.1 (x86_64-little_endian-lp64 shared (dynamic) release build; by GCC 4.8.3 20140627 [gcc-4_8-branch revision 212064])
> PASS   : KFileItemModelBenchmark::initTestCase()
> PASS   : KFileItemModelBenchmark::insertAndRemoveManyItems(all--n=100000)
> RESULT : KFileItemModelBenchmark::insertAndRemoveManyItems():"all--n=100000":
>      21 msecs per iteration (total: 87, iterations: 4)
> PASS   : KFileItemModelBenchmark::insertAndRemoveManyItems(1st half + 2nd half--n=100000)
> RESULT : KFileItemModelBenchmark::insertAndRemoveManyItems():"1st half + 2nd half--n=100000":
>      46 msecs per iteration (total: 92, iterations: 2)
> PASS   : KFileItemModelBenchmark::insertAndRemoveManyItems(2nd half + 1st half--n=100000)
> RESULT : KFileItemModelBenchmark::insertAndRemoveManyItems():"2nd half + 1st half--n=100000":
>      41 msecs per iteration (total: 83, iterations: 2)
> PASS   : KFileItemModelBenchmark::insertAndRemoveManyItems(even + odd--n=100000)
> RESULT : KFileItemModelBenchmark::insertAndRemoveManyItems():"even + odd--n=100000":
>      56.5 msecs per iteration (total: 113, iterations: 2)
> PASS   : KFileItemModelBenchmark::insertAndRemoveManyItems(all - 2nd half--n=100000)
> RESULT : KFileItemModelBenchmark::insertAndRemoveManyItems():"all - 2nd half--n=100000":
>      64 msecs per iteration (total: 64, iterations: 1)
> PASS   : KFileItemModelBenchmark::insertAndRemoveManyItems(all - 1st half--n=100000)
> RESULT : KFileItemModelBenchmark::insertAndRemoveManyItems():"all - 1st half--n=100000":
>      50.0 msecs per iteration (total: 100, iterations: 2)
> PASS   : KFileItemModelBenchmark::insertAndRemoveManyItems(all - odd--n=100000)
> RESULT : KFileItemModelBenchmark::insertAndRemoveManyItems():"all - odd--n=100000":
>      68 msecs per iteration (total: 68, iterations: 1)
> PASS   : KFileItemModelBenchmark::cleanupTestCase()
> Totals: 9 passed, 0 failed, 0 skipped, 0 blacklisted
> ********* Finished testing of KFileItemModelBenchmark *********
> 
> 
> Thanks,
> 
> Frank Reininghaus
> 
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.kde.org/mailman/private/kfm-devel/attachments/20150504/a333b468/attachment.htm>