Speedup sort
ClosedPublic

Authored by jtamate on Jun 30 2018, 3:41 PM.

Details

Summary

Uses a reference to the collator instead of copying and reinitializing it again and again. This is the reason for the speedup.

Changing the implementation from a Functor class to a Lambda removes some boilerplate code, but is not relevant for performance.

This requires a workaround for https://bugreports.qt.io/browse/QTBUG-69361
Just a single comparison to force the clean state of QCollator.

Test Plan

Sorting in a directory with 82874 images:
[TIME] Sorting: 19883 (before)
[TIME] Sorting: 4198 (after)

kfileitemmodelbenchmark before: .............. Passed 29.36 sec
kfileitemmodelbenchmark after: .............. Passed 20.39 sec

Diff Detail

Repository
R318 Dolphin
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
jtamate created this revision.Jun 30 2018, 3:41 PM
Restricted Application added a project: Dolphin. · View Herald TranscriptJun 30 2018, 3:41 PM
Restricted Application added a subscriber: kfm-devel. · View Herald Transcript
markg added a subscriber: markg.Jul 1 2018, 12:41 PM

+1

Great! :) Back to the good old fast performance it once had!
Please do get rid of the underscore before the name. Nothing (afaict) does that in Dolphin, lets not introduce it. Just lessThan is fine.

Also, note that this was done for a reason. I think it was the one in the comment: "non-reentrant comparison functions" which is why the roles other then NameRole are using single-threaded sort.
I don't know if that's still an issue or if your patch re-introduces whatever the problem was (race conditions?). You could look back in the commit log when that was added to figure out more about it.

markg added a comment.Jul 1 2018, 12:48 PM

I don't know if that's still an issue or if your patch re-introduces whatever the problem was (race conditions?). You could look back in the commit log when that was added to figure out more about it.

To answer that myself, it was done in this commit: https://cgit.kde.org/dolphin.git/commit/src/kitemviews/kfileitemmodel.cpp?id=d9680ead8099df9a2b06bfed61a62923778996f2
And doesn't explain anything :)

bruns added a subscriber: bruns.Jul 1 2018, 2:47 PM

I don't know if that's still an issue or if your patch re-introduces whatever the problem was (race conditions?). You could look back in the commit log when that was added to figure out more about it.

To answer that myself, it was done in this commit: https://cgit.kde.org/dolphin.git/commit/src/kitemviews/kfileitemmodel.cpp?id=d9680ead8099df9a2b06bfed61a62923778996f2
And doesn't explain anything :)

If you follow the link in the comment, i.e. https://bugs.kde.org/show_bug.cgi?id=312679, it mentions date sorting and KDateTime being non-reentrant.

I don't know if that's still an issue or if your patch re-introduces whatever the problem was (race conditions?). You could look back in the commit log when that was added to figure out more about it.

To answer that myself, it was done in this commit: https://cgit.kde.org/dolphin.git/commit/src/kitemviews/kfileitemmodel.cpp?id=d9680ead8099df9a2b06bfed61a62923778996f2
And doesn't explain anything :)

If you follow the link in the comment, i.e. https://bugs.kde.org/show_bug.cgi?id=312679, it mentions date sorting and KDateTime being non-reentrant.

Yes, that is why parallelMergeSort is only used to sort by name. All methods of QCollator are reentrant (http://doc.qt.io/qt-5/qcollator.html)

jtamate updated this revision to Diff 37010.Jul 1 2018, 2:53 PM

Remove the _ prefix.

bruns added a comment.Jul 1 2018, 2:54 PM

I assume you are sorting by name with "natural sorting". There may be another possibility for speedup here:
QCollator::sortkey(), http://doc.qt.io/qt-5/qcollator.html#sortKey

It might be possible to generate the sortkey in e.g. https://phabricator.kde.org/source/dolphin/browse/master/src/kitemviews/kfileitemmodel.cpp$1334

I assume you are sorting by name with "natural sorting". There may be another possibility for speedup here:
QCollator::sortkey(), http://doc.qt.io/qt-5/qcollator.html#sortKey

It might be possible to generate the sortkey in e.g. https://phabricator.kde.org/source/dolphin/browse/master/src/kitemviews/kfileitemmodel.cpp$1334

Unfortunately is not a trivial change, because it uses a <QByteArray, QVariant> and QCollatorSortKey can not be transformed into a QVariant, therefore it will not be in in this patch.

jtamate updated this revision to Diff 37019.Jul 1 2018, 4:53 PM

Can not use the name lessThan because of: error: use of ‘lessThan’ before deduction of ‘auto’

markg added a comment.EditedJul 1 2018, 7:38 PM

I don't know if that's still an issue or if your patch re-introduces whatever the problem was (race conditions?). You could look back in the commit log when that was added to figure out more about it.

To answer that myself, it was done in this commit: https://cgit.kde.org/dolphin.git/commit/src/kitemviews/kfileitemmodel.cpp?id=d9680ead8099df9a2b06bfed61a62923778996f2
And doesn't explain anything :)

If you follow the link in the comment, i.e. https://bugs.kde.org/show_bug.cgi?id=312679, it mentions date sorting and KDateTime being non-reentrant.

That would be really interesting as KDateTime isn't used anywhere in Dolphin anymore (according to my grep on the source). It's all QDateTime now and that is all reentrant according to the Qt docs!
In other words, the fix for that can probably be removed now.

Just an assumption though. I haven't tried anything.

Edit:
Neither does KIO (for KFileItem) where the issue original originated from.
An old fix that can probably be removed which will also simplify the code :)

apol added a subscriber: apol.Jul 1 2018, 11:55 PM

+1 otherwise.

src/kitemviews/kfileitemmodel.cpp
1715

it's "lambda".

jtamate updated this revision to Diff 37053.Jul 2 2018, 10:37 AM
jtamate marked an inline comment as done.

In other words, the fix for that can probably be removed now.

I prefer not to do it (even I've tried without any crash), because QVariant is not even reentrant.

Changed to lambdaLessThan.

bruns added a comment.Jul 2 2018, 10:44 AM

In other words, the fix for that can probably be removed now.

I prefer not to do it (even I've tried without any crash), because QVariant is not even reentrant.

Reentrancy is only relevant when the class has some global state.

Anyway, it is indepedent and should go in a separate review.

bruns added a comment.Jul 2 2018, 10:52 AM

I assume you are sorting by name with "natural sorting". There may be another possibility for speedup here:
QCollator::sortkey(), http://doc.qt.io/qt-5/qcollator.html#sortKey

It might be possible to generate the sortkey in e.g. https://phabricator.kde.org/source/dolphin/browse/master/src/kitemviews/kfileitemmodel.cpp$1334

Unfortunately is not a trivial change, because it uses a <QByteArray, QVariant> and QCollatorSortKey can not be transformed into a QVariant, therefore it will not be in in this patch.

You can store any type in QVariant, see http://doc.qt.io/qt-5/qmetatype.html#Q_DECLARE_METATYPE

But the comment was meant as a hint where to look for performance improvements, not specifically for this review.

jtamate updated this revision to Diff 37056.Jul 2 2018, 11:20 AM

Undo the right number of steps from a quick experiment. :-)

markg accepted this revision.Jul 2 2018, 1:07 PM

2x +1 = +2
Ship it :)

This revision is now accepted and ready to land.Jul 2 2018, 1:07 PM
elvisangelaccio requested changes to this revision.Jul 2 2018, 8:17 PM
elvisangelaccio added a subscriber: elvisangelaccio.

Impressive, I went from 18 seconds to 4 :O

But please remove

friend class KFileItemModelLessThan;

from kfileitemmodel.h

This revision now requires changes to proceed.Jul 2 2018, 8:17 PM
jtamate updated this revision to Diff 37182.Jul 5 2018, 11:30 AM

Remove the friend non-exist class.

elvisangelaccio accepted this revision.Jul 5 2018, 6:54 PM
This revision is now accepted and ready to land.Jul 5 2018, 6:54 PM
This revision was automatically updated to reflect the committed changes.

I really, really hate these things.
I've been testing this patch more than one month without any problem.
And now, after pushing it, I got crashes everytime I start dolphin without parameters (user home).
But not if I start it in / and keep changing directories, including user home.

Please, test dolphin with latest sources.

#6 0x00007fc0ba4e5904 in icu_61_1::RuleBasedCollator::getAttribute(UColAttribute, UErrorCode&) const () from /usr/lib64/libicui18n.so.61.1
#7 0x00007fc0ba4e6dc6 in icu_61_1::RuleBasedCollator::setAttribute(UColAttribute, UColAttributeValue, UErrorCode&) () from /usr/lib64/libicui18n.so.61.1
#8 0x00007fc0c0dfec25 in QCollatorPrivate::init() () at tools/qcollator_icu.cpp:82
#9 0x00007fc0c0dfedab in QCollator::compare (this=0x1928070, s1=0x1bd6b98, len1=19, s2=0x1d70af8, len2=17) at tools/qcollator_icu.cpp:109
#10 0x00007fc0c880ac30 in KFileItemModel::sortRoleCompare (this=this@entry=0x1928040, a=a@entry=0x1c0e1f0, b=b@entry=0x1cfbdf0, collator=...) at /g/5kde/kde/applications/dolphin/src/kitemviews/kfileitemmodel.cpp:1836
#11 0x00007fc0c880b2a2 in KFileItemModel::lessThan (this=this@entry=0x1928040, a=0x1c0e1f0, b=0x1cfbdf0, collator=...) at /g/5kde/kde/applications/dolphin/src/kitemviews/kfileitemmodel.cpp:1707
#12 0x00007fc0c8811715 in KFileItemModel::<lambda(const KFileItemModel::ItemData*, const KFileItemModel::ItemData*)>::operator() (__closure=0x7ffe8d4307a8, b=<optimized out>, a=<optimized out>) at /g/5kde/kde/applications/dolphin/src/kitemviews/kfileitemmodel.cpp:1717

markg added a comment.Jul 7 2018, 1:27 PM

I really, really hate these things.
I've been testing this patch more than one month without any problem.
And now, after pushing it, I got crashes everytime I start dolphin without parameters (user home).
But not if I start it in / and keep changing directories, including user home.

Please, test dolphin with latest sources.

#6 0x00007fc0ba4e5904 in icu_61_1::RuleBasedCollator::getAttribute(UColAttribute, UErrorCode&) const () from /usr/lib64/libicui18n.so.61.1
#7 0x00007fc0ba4e6dc6 in icu_61_1::RuleBasedCollator::setAttribute(UColAttribute, UColAttributeValue, UErrorCode&) () from /usr/lib64/libicui18n.so.61.1
#8 0x00007fc0c0dfec25 in QCollatorPrivate::init() () at tools/qcollator_icu.cpp:82
#9 0x00007fc0c0dfedab in QCollator::compare (this=0x1928070, s1=0x1bd6b98, len1=19, s2=0x1d70af8, len2=17) at tools/qcollator_icu.cpp:109
#10 0x00007fc0c880ac30 in KFileItemModel::sortRoleCompare (this=this@entry=0x1928040, a=a@entry=0x1c0e1f0, b=b@entry=0x1cfbdf0, collator=...) at /g/5kde/kde/applications/dolphin/src/kitemviews/kfileitemmodel.cpp:1836
#11 0x00007fc0c880b2a2 in KFileItemModel::lessThan (this=this@entry=0x1928040, a=0x1c0e1f0, b=0x1cfbdf0, collator=...) at /g/5kde/kde/applications/dolphin/src/kitemviews/kfileitemmodel.cpp:1707
#12 0x00007fc0c8811715 in KFileItemModel::<lambda(const KFileItemModel::ItemData*, const KFileItemModel::ItemData*)>::operator() (__closure=0x7ffe8d4307a8, b=<optimized out>, a=<optimized out>) at /g/5kde/kde/applications/dolphin/src/kitemviews/kfileitemmodel.cpp:1717

I just cloned dolphin with your changes.
It compiled just fine.
Starting it with and without arguments also worked just fine.

Perhaps it's a local issue on your side? Have you tried cleaning your dolphin build (and perhaps KIO as well) and re-run it to see if it still happens?

I just cloned dolphin with your changes.
It compiled just fine.
Starting it with and without arguments also worked just fine.

Perhaps it's a local issue on your side? Have you tried cleaning your dolphin build (and perhaps KIO as well) and re-run it to see if it still happens?

I've done a kdesrc-build from empty sources directory and empty build directory, but not empty install directory and it still happens. I will try later after I get enough free space with an empty install directory.

I've reverted the change until I know why this is happening. We can't have an always crashing dolphin.

Perhaps it's a local issue on your side? Have you tried cleaning your dolphin build (and perhaps KIO as well) and re-run it to see if it still happens?

I've done a kdesrc-build from empty sources directory and empty build directory, but not empty install directory and it still happens. I will try later after I get enough free space with an empty install directory.

I've done it again with an empty install directory, empty sources directory and empty build directory: I get a crash. :-(
I'll try to find why it fails only at the beginning of the execution and not after.

I've reverted the change until I know why this is happening. We can't have an always crashing dolphin.

jtamate updated this revision to Diff 37305.Jul 8 2018, 8:39 AM

My crashes are gone just doing a single comparison using the collator at the constructor.

markg added a comment.Jul 8 2018, 9:59 AM

Somehow i'm inclined to think that m_collator is wrong.
But inspecting the code shows no issue as far as i can tell. It's a normal class member that lives as long as the KFileItemModel instance lives.

Now here's a tricky part. KFileItemModel is new'ed for each view (and the folders panel) and as the sorting is (for strings) done with multiple threads.
Perhaps there is a remote possibility of closing a view while sorting which will cause the lessThan lambda to have a dangling reference to m_collator and crash.

That's just in theory though, i haven't been able to reproduce that.
But if that is true then you do have ways to create that dangling reference and thus crash while sorting.

src/kitemviews/kfileitemmodel.cpp
112

I don't know what @elvisangelaccio thinks about this, but i'm against it. This feels like a hacky workaround to me that should not be needed.

@jtamate Can you show a complete gdb backtrace + valgrind log of this crash?

@jtamate Can you show a complete gdb backtrace + valgrind log of this crash?

Here you are

Reading the source of QCollator*, I guess the hack works because I get a collator where d->dirty is true,
and in compare there is this code

if (d->dirty)
  d->init();

Once initialized, I don't see any other modification of QCollator members.
Probably because I have a strange LANGUAGE=es:en_US
LANG=es_ES.UTF-8

Hmm, so the crash is in ucol_close() (aka in ICU) and we are working around it by forcing the cleanup in the KFileItemModel ctor (= single thread).

Sounds reasonable, but we should (1) document this hack in the comment and/or in the commit message and (2) report this crash to bugreports.qt.io because ICU is supposed to be thread-safe.

elvisangelaccio reopened this revision.Jul 8 2018, 5:16 PM
This revision is now accepted and ready to land.Jul 8 2018, 5:16 PM
elvisangelaccio requested changes to this revision.Jul 8 2018, 5:17 PM
elvisangelaccio added inline comments.
src/kitemviews/kfileitemmodel.cpp
111

Please explain why we need this workaround here (see my previous comment)

This revision now requires changes to proceed.Jul 8 2018, 5:17 PM
jtamate updated this revision to Diff 37422.Jul 9 2018, 7:18 AM
jtamate edited the summary of this revision. (Show Details)

Created the bug report referenced in the summary and code.
Changed the strings to compare, they can be anything.

Perhaps there is a remote possibility of closing a view while sorting which will cause the lessThan lambda to have a dangling reference to m_collator and crash.

Right now this possibility is non-existent, sort does not allows any event management, and in fact I thing is this bug report: https://bugs.kde.org/show_bug.cgi?id=395374

elvisangelaccio accepted this revision.Jul 10 2018, 8:25 PM

Thanks for filing the upstream bug. Looks good to me now.

This revision is now accepted and ready to land.Jul 10 2018, 8:25 PM
bruns added inline comments.Jul 10 2018, 11:38 PM
src/kitemviews/kfileitemmodel.cpp
58

this causes the dirty state - maybe also do the forced (re)initialization here?

112

Maybe better:

// Force initialization from the main thread. The collator is captured by reference and passed to the threads,
// and if it is not in a clean state all threads will try to initialize it in parallel.
113

m_collator.compare(QString(), QString()); is sufficient

jtamate updated this revision to Diff 37543.Jul 11 2018, 7:48 AM

I've applied some of @bruns suggestions.
Just use QString(), less filesize and memory.
Move the comparison after loadSortingSettings();
Change the comment from Force the cleanup of to Force the clean state of. @bruns comment is already in the bug.

As soon as I can do a test where the bug is reproducible, I'll commit it.

bruns requested changes to this revision.Jul 11 2018, 12:46 PM
bruns added inline comments.
src/kitemviews/kfileitemmodel.cpp
60

loadSortingSettings(), which sets dirty, is also called from slotSortingChoiceChanged(), so the forced initialization has to be done there too.

This revision now requires changes to proceed.Jul 11 2018, 12:46 PM
jtamate updated this revision to Diff 37559.Jul 11 2018, 12:58 PM
jtamate edited the summary of this revision. (Show Details)

Apply the workaround in loadSortingSettings.
It is applied in the constructor and when the type of sorting is changed by the user.

bruns added a comment.Jul 11 2018, 3:06 PM

The code looks fine now, but the summary is incorrect.

The savings is not from using a lambda, but caused by initializing it once. If the old code had used m_collator(other.m_collator) in the copy constructor, construction would have been just a ref count increment and each of the following m_collator.setFoo(...) would have been noops (QCollator checks if the new value is different to its current value).

Of course this would have triggered the QCollator bug as well.

markg added a comment.Jul 11 2018, 4:19 PM

The code looks fine now, but the summary is incorrect.

The savings is not from using a lambda, but caused by initializing it once. If the old code had used m_collator(other.m_collator) in the copy constructor, construction would have been just a ref count increment and each of the following m_collator.setFoo(...) would have been noops (QCollator checks if the new value is different to its current value).

Of course this would have triggered the QCollator bug as well.

Is there even a need to have n QCollator objects?
I'm talking about a QCollator _within_ a given view. Each view could obviously have it's own collator due to different view settings.

jtamate edited the summary of this revision. (Show Details)Jul 11 2018, 6:53 PM

Is there even a need to have n QCollator objects?
I'm talking about a QCollator _within_ a given view. Each view could obviously have it's own collator due to different view settings.

Strictly speaking you need one collator per thread (it is reentrant (save the bug), but not thread-safe). As long as the collator objects are not modified, each one is just the d-pointer, as QCollator is CoW.

Copying a clean QCollator is cheap. Default-constructing one and modifying it is expensive - each one has to be initialize the underlying ICU (actually, this happens twice for each one, once on construction, once after the m_collator.setFoo(...) calls).

Using a const reference, as done here, is even slightly cheaper. But doing so is also undefined behaviour - QCollator is reentrant, but not thread-safe. We get away with it by using the forced initialization, which avoids the UB (UB only happens when the QCollator is dirty).

When the fix in https://codereview.qt-project.org/#/c/234359/3//ALL,unified is applied, it is no longer necessary to force the init() under the premise each thread uses its own private collator object (which is implicitly shared).

This revision was not accepted when it landed; it landed in state Needs Review.Jul 13 2018, 4:55 PM
Closed by commit R318:765cc968c9df: Speedup sort (authored by jtamate). · Explain Why
This revision was automatically updated to reflect the committed changes.
bruns added a comment.Jul 13 2018, 8:09 PM

Any reason why you have pushed this with an obviously wrong commit message?

Any reason why you have pushed this with an obviously wrong commit message?

Because I though the commit message was right.

What should it be?

bruns added a comment.Jul 14 2018, 1:09 PM

Any reason why you have pushed this with an obviously wrong commit message?

Because I though the commit message was right.

What should it be?

The new code uses a reference to the collator instead of copying and reinitializing it again and again. This is the reason for the speedup.

Changing the implementation from a Functor class to a Lambda removes some boilerplate code, but is not relevant for performance.

jtamate edited the summary of this revision. (Show Details)Jul 14 2018, 2:17 PM

Also amended the commit message.

bruns added a comment.Jul 14 2018, 2:28 PM

Also amended the commit message.

thanks, but unfortunately this won't change the git commit message :-(