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

Thu May 7 21:22:20 BST 2015

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

(Updated May 7, 2015, 8:22 p.m.)

Status
------

This change has been marked as submitted.

Review request for Dolphin.

Changes
-------

Submitted with commit e69d3489751ea15c0477fe1d41fcc252c775d377 by Frank Reininghaus to branch master.

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/20150507/63094dab/attachment.htm>