D10857: Change qSort to std::sort

[Jaime Torres Amate]

This revision was not accepted when it landed; it landed in state "Changes 
Planned".
This revision was automatically updated to reflect the committed changes.
Closed by commit R241:7bb346ac2a4d: Change qSort to std::sort (authored by 
jtamate).

CHANGED PRIOR TO COMMIT
  https://phabricator.kde.org/D10857?vs=28274&id=28420#toc

REPOSITORY
  R241 KIO

CHANGES SINCE LAST UPDATE
  https://phabricator.kde.org/D10857?vs=28274&id=28420

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

AFFECTED FILES
  src/core/ksslcertificatemanager.cpp
  src/filewidgets/kurlnavigatorbutton.cpp
  src/ioslaves/http/http_cache_cleaner.cpp
  src/kpac/script.cpp
  src/kpasswdserver/kpasswdserver.cpp
  src/widgets/kdirmodel.cpp
  src/widgets/kfileitemactions.cpp

To: jtamate, #frameworks, dfaure, markg
Cc: markg, apol, michaelh

D10857: Change qSort to std::sort

[Jaime Torres Amate]

jtamate retitled this revision from "Change qSort to std::sort in 
simplifiedUrlList" to "Change qSort to std::sort".
jtamate edited the summary of this revision.
jtamate edited the test plan for this revision.

REPOSITORY
  R241 KIO

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

To: jtamate, #frameworks, dfaure, markg
Cc: markg, apol, michaelh

D10857: Change qSort to std::sort in simplifiedUrlList

[Mark Gaiser]

markg added a comment.


  In D10857#216725 , @dfaure wrote:
  
  > I cannot confirm that stable_sort is faster, on the contrary. 
http://www.davidfaure.fr/2018/qsort_performance.cpp updated, says (repeatedly)
  >  "std::sort took: 5003 ms"
  >  "std::stable_sort took: 7490 ms"
  >
  > Maybe on specific data (the actual filenames you're testing this with), 
stable_sort ends up being faster, but this isn't true in general (with random 
data).
  
  
  "qSort took: 3308 ms"
  "std::sort took: 3383 ms"
  "std::stable_sort took: 5829 ms"
  
  My results. A direct copy-paste from your benchmark, no edits.
  Release mode and linux this time.
  
  @jtamate std::sort it is. Feel free to commit :)

REPOSITORY
  R241 KIO

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

To: jtamate, #frameworks, dfaure, markg
Cc: markg, apol, michaelh

D10857: Change qSort to std::sort in simplifiedUrlList

[Jaime Torres Amate]

jtamate added a comment.


  In D10857#216725 , @dfaure wrote:
  
  > I cannot confirm that stable_sort is faster, on the contrary. 
http://www.davidfaure.fr/2018/qsort_performance.cpp updated, says (repeatedly)
  >  "std::sort took: 5003 ms"
  >  "std::stable_sort took: 7490 ms"
  >
  > Maybe on specific data (the actual filenames you're testing this with), 
stable_sort ends up being faster, but this isn't true in general (with random 
data).
  
  
  http://www.cplusplus.com/reference/algorithm/stable_sort/
  If enough extra memory is available, linearithmic in the distance between 
first and last: Performs up to N*log2(N) element comparisons (where N is this 
distance), and up to that many element moves.
  Otherwise, polyloglinear in that distance: Performs up to N*(log2(N))^2 
element comparisons, and up to that many element swaps.
  
  http://www.cplusplus.com/reference/algorithm/sort/
  On average, linearithmic in the distance between first and last: Performs 
approximately N*log2(N) (where N is this distance) comparisons of elements, and 
up to that many element swaps (or moves).
  
  So, std::sort then?

REPOSITORY
  R241 KIO

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

To: jtamate, #frameworks, dfaure, markg
Cc: markg, apol, michaelh

D10857: Change qSort to std::sort in simplifiedUrlList

[David Faure]

dfaure added a comment.


  I cannot confirm that stable_sort is faster, on the contrary. 
http://www.davidfaure.fr/2018/qsort_performance.cpp updated, says (repeatedly)
  "std::sort took: 5003 ms"
  "std::stable_sort took: 7490 ms"
  
  Maybe on specific data (the actual filenames you're testing this with), 
stable_sort ends up being faster, but this isn't true in general (with random 
data).

REPOSITORY
  R241 KIO

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

To: jtamate, #frameworks, dfaure, markg
Cc: markg, apol, michaelh

D10857: Change qSort to std::sort in simplifiedUrlList

[David Faure]

dfaure added a comment.


  That is amazing, I could have sworn that the whole point of sort vs 
stable_sort was that stable_sort was potentially slower, which was the reason 
for sort to exist (when you don't care about the "stability" of equal items)...

REPOSITORY
  R241 KIO

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

To: jtamate, #frameworks, dfaure, markg
Cc: markg, apol, michaelh

D10857: Change qSort to std::sort in simplifiedUrlList

[Jaime Torres Amate]

jtamate added a comment.


  I've found the problem.  The problem is qSort itself.
  
  Chaning qSort to qStableSort I've got normal times in the test case, select 
50.000 files and pressing Shift+Supr.
  
  Also in the small test, the times, running under callgrind are:
  qSort: between 33148 and 45745
  std::sort between 53231 and 66780
  qStableSort: between 11232 and 15116
  std::stable_sort: between 22581 and 25957
  
  Therefore, before patching, should I change all of them to std::sort or 
std::stable_sort or qStableSort?

REPOSITORY
  R241 KIO

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

To: jtamate, #frameworks, dfaure, markg
Cc: markg, apol, michaelh

D10857: Change qSort to std::sort in simplifiedUrlList

[Jaime Torres Amate]

jtamate planned changes to this revision.
jtamate added a comment.


  I've run David test, it is not a CPU problem:
  
  g++ -fPIC -O2 qsort_performance.cpp -I /usr/include/qt5/QtCore 
-I/usr/include/qt5 -l Qt5Core
  ./a.out
  "qSort took: 3335 ms"
  "std::sort took: 3452 ms"
  "qSort took: 3285 ms"
  "std::sort took: 3464 ms"
  "qSort took: 3582 ms"
  "std::sort took: 3681 ms"
  "qSort took: 3338 ms"
  "std::sort took: 3646 ms"
  "qSort took: 3635 ms"
  "std::sort took: 3826 ms"
  "qSort took: 3747 ms"
  "std::sort took: 3510 ms"
  "qSort took: 3637 ms"
  "std::sort took: 3590 ms"
  "qSort took: 3418 ms"
  "std::sort took: 3559 ms"
  "qSort took: 3493 ms"
  "std::sort took: 3750 ms"
  "qSort took: 3445 ms"
  "std::sort took: 3545 ms"
  
  Even with a modified test simulating the input data in the call in 
simpliedUrlList, the results are normal
  F5734576: qsort_performance_test.cpp 
  g++ -fPIC -O2 qsort_performance_test.cpp -I /usr/include/qt5/QtCore 
-I/usr/include/qt5 -l Qt5Core
  ./a.out
  "qSort took: 786 ms"
  "std::sort took: 930 ms"
  "qSort took: 987 ms"
  "std::sort took: 1143 ms"
  "qSort took: 1006 ms"
  "std::sort took: 1188 ms"
  "qSort took: 1039 ms"
  "std::sort took: 1161 ms"
  "qSort took: 1005 ms"
  "std::sort took: 1167 ms"
  "qSort took: 1012 ms"
  "std::sort took: 1171 ms"
  "qSort took: 1026 ms"
  "std::sort took: 1197 ms"
  "qSort took: 1014 ms"
  "std::sort took: 1158 ms"
  "qSort took: 1010 ms"
  "std::sort took: 1162 ms"
  "qSort took: 1012 ms"
  "std::sort took: 1236 ms"
  
  Therefore I'll try to discover why it is so slow, there must be something 
wrong anywhere, before changing the sort method that hides the problem.

REPOSITORY
  R241 KIO

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

To: jtamate, #frameworks, dfaure, markg
Cc: markg, apol, michaelh

D10857: Change qSort to std::sort in simplifiedUrlList

[David Faure]

dfaure accepted this revision.
dfaure added a comment.
This revision is now accepted and ready to land.


  " it does suck a little that qSort beats std::sort."
  I was curious whether that was true, so I ran Mark's benchmark, with a few 
fixes: one more zero in the number of items for the vectors, because there was 
too much variation in numbers when measuring something that lasts around 500ms, 
and I looped over the two sorting methods, to avoid having to run the benchmark 
multiple times (because I'm lazy, and because the first iteration seems to have 
some cold cache effect, the later ones are faster). 
http://www.davidfaure.fr/2018/qsort_performance.cpp
  
  That gives me pretty stable results.
  In release mode:
  
"qSort took: 4710 ms"
"std::sort took: 4818 ms"
"qSort took: 4600 ms"
"std::sort took: 4737 ms"
"qSort took: 4610 ms"
"std::sort took: 4739 ms"
"qSort took: 4585 ms"
"std::sort took: 4735 ms"
"qSort took: 4592 ms"
"std::sort took: 4748 ms"
"qSort took: 4644 ms"
"std::sort took: 4736 ms"
"qSort took: 4605 ms"
"std::sort took: 4767 ms"
  
  I ran both sorting algos (in RelWithDebInfo mode) in perf+hotspot to find out 
where the difference comes from, but I see nothing conclusive. std::sort goes 
via swap which calls QString::swap(QString&) which calls 
qSwap(pointers) while qSort is able to call qSwap(pointers) directly, but 
that's all inline, shouldn't make a difference, I would expect. So it must be 
the sorting algorithm itself. Oh well, not much we can do, apart from, well, 
comparing libstdc++ and libc++, another day :)
  
  (Curiously, in debug mode, qSort is much slower than std::sort (9s vs 7.6s).)

REPOSITORY
  R241 KIO

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

To: jtamate, #frameworks, dfaure, markg
Cc: markg, apol, michaelh

D10857: Change qSort to std::sort in simplifiedUrlList

[Mark Gaiser]

markg accepted this revision.
markg added a comment.


  +1, but wait till someone else had a look as well.

INLINE COMMENTS

> kdirmodel.cpp:42
>  
> -#include 
> -

Don't you need to keep that one?
Nothing seems to be including  (for std::sort at the very least) so 
i'm not sure why it would work at the moment without that header.

REPOSITORY
  R241 KIO

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

To: jtamate, #frameworks, dfaure, markg
Cc: markg, apol, michaelh

D10857: Change qSort to std::sort in simplifiedUrlList

[Jaime Torres Amate]

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


  Changed all qSort in Qlist to std::sort.
  At least the people with Intel(R) Core(TM) i5-4200U (model 69) will see a big 
improvement in time.
  
  I tried with KDE Neon with a kernel without patches for the cpu, and with the 
dolphin included in Neon and OpenSuse, the results are the same: very slow 
using qSort.

REPOSITORY
  R241 KIO

CHANGES SINCE LAST UPDATE
  https://phabricator.kde.org/D10857?vs=28100&id=28274

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

AFFECTED FILES
  src/core/ksslcertificatemanager.cpp
  src/filewidgets/kurlnavigatorbutton.cpp
  src/ioslaves/http/http_cache_cleaner.cpp
  src/kpac/script.cpp
  src/kpasswdserver/kpasswdserver.cpp
  src/widgets/kdirmodel.cpp
  src/widgets/kfileitemactions.cpp

To: jtamate, #frameworks, dfaure
Cc: markg, apol, michaelh

D10857: Change qSort to std::sort in simplifiedUrlList

[Mark Gaiser]

markg added a comment.


  In D10857#214867 , @jtamate wrote:
  
  > In D10857#214607 , @dfaure wrote:
  >
  > > I'm not opposed to the idea, but measuring CPU usage is a rather 
misleading indicator. What if it takes 10 times longer, because it's 
progressing much more slowly? ;)
  > >
  > > Please at least measure with QElapsedTimer around the sorting (not to be 
committed, just to gather numbers about the actual performance of this from a 
user's point of view).
  > >  I'm interested in the result ;)
  >
  >
  > The results are strange. All the results are measured sorting 50.000 small 
files:
  >
  > Both Qt are the same version from opensuse.
  >
  > In an i5, why the difference is so big? recent cpu bugs?
  >  qSort in i3 
  >  274764, 276060 (with 3 directories), 365878, 424506  (without directories)
  >  std::sort in i3
  >  940, 995 (with 3 directories), 2472, 2539 (without directories)
  >
  > In AMD the results are closer, qSort wins
  >  qSort in AMD
  >  658, 726, 695, 683, 676, 666, 649, 684, 666 (without directories)
  >  std:sort in AMD
  >  843, 839, 878, 896,  925 (without directories)
  
  
  That surprises me a lot!
  I "thought" qSort was just a template or alias to std::sort, but it isn't: 
http://code.qt.io/cgit/qt/qtbase.git/tree/src/corelib/tools/qalgorithms.h#n340
  But it isn't which kinda makes my other expectations moot (qSort == 
std::sort... it isn't)
  
  So i did some tests as well.
  5 filenames sorting them (computer sorting, not the natural one) with 
std::string and QString (yes, it matters)
  Filenames, well, sorta.. Made them up in a loop :)
  
  QString version: https://p.sc2.nl/r1JTFaf_z
  qSort: ~220ms
  std::sort ~276ms
  
  std::string version: https://p.sc2.nl/HJ69Y6G_G
  qSort: ~100ms
  std::sort ~130ms
  
  Note that std::string might not be the fair comparison as it's 8 bit/char. 
QString is 16.
  My compiler (in this rare case) Visual Studio 2017 on an Intel CPU.
  
  I still think it's wise to replace all qSort, if only for it being 
deprecated. But it does suck a little that qSort beats std::sort.

REPOSITORY
  R241 KIO

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

To: jtamate, #frameworks, dfaure
Cc: markg, apol, michaelh

D10857: Change qSort to std::sort in simplifiedUrlList

[Aleix Pol Gonzalez]

apol added a comment.


  I'd say the bottom line is qSort is deprecated in favor of std::sort.
  
  @jtamate make sure you are profiling release builds.

REPOSITORY
  R241 KIO

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

To: jtamate, #frameworks, dfaure
Cc: markg, apol, michaelh

D10857: Change qSort to std::sort in simplifiedUrlList

[Jaime Torres Amate]

jtamate added a comment.


  In D10857#214607 , @dfaure wrote:
  
  > I'm not opposed to the idea, but measuring CPU usage is a rather misleading 
indicator. What if it takes 10 times longer, because it's progressing much more 
slowly? ;)
  >
  > Please at least measure with QElapsedTimer around the sorting (not to be 
committed, just to gather numbers about the actual performance of this from a 
user's point of view).
  >  I'm interested in the result ;)
  
  
  The results are strange. All the results are measured sorting 50.000 small 
files:
  
  Both Qt are the same version from opensuse.
  
  In an i5, why the difference is so big? recent cpu bugs?
  qSort in i3 
  274764, 276060 (with 3 directories), 365878, 424506  (without directories)
  std::sort in i3
  940, 995 (with 3 directories), 2472, 2539 (without directories)
  
  In AMD the results are closer, qSort wins
  qSort in AMD
  658, 726, 695, 683, 676, 666, 649, 684, 666 (without directories)
  std:sort in AMD
  843, 839, 878, 896,  925 (without directories)

REPOSITORY
  R241 KIO

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

To: jtamate, #frameworks, dfaure
Cc: markg, apol, michaelh

D10857: Change qSort to std::sort in simplifiedUrlList

[David Faure]

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


  I'm not opposed to the idea, but measuring CPU usage is a rather misleading 
indicator. What if it takes 10 times longer, because it's progressing much more 
slowly? ;)
  
  Please at least measure with QElapsedTimer around the sorting (not to be 
committed, just to gather numbers about the actual performance of this from a 
user's point of view).
  I'm interested in the result ;)

REPOSITORY
  R241 KIO

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

To: jtamate, #frameworks, dfaure
Cc: markg, apol, michaelh

D10857: Change qSort to std::sort in simplifiedUrlList

[Mark Gaiser]

markg added a comment.


  +1, also for what @apol said.

REPOSITORY
  R241 KIO

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

To: jtamate, #frameworks, dfaure
Cc: markg, apol, michaelh

D10857: Change qSort to std::sort in simplifiedUrlList

[Aleix Pol Gonzalez]

apol added a comment.


  +1
  If there's 11, we better change them all at once?

REPOSITORY
  R241 KIO

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

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

D10857: Change qSort to std::sort in simplifiedUrlList

[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
  qSort is depecreated in Qt5.
  But qSort is also quite slow compared to std::sort.
  
  There are 11 more uses of qSort in kio.

TEST PLAN
  Select 50.000 small files and press Shift-Supr.
  With qSort 11% of cpu
  F5730673: qSortOneTime.png 
  
  Select 50.000 small files and press Shift-Supr, cancel and press Shift-Supr 
again.
  With std::sort 3.3% of cpu
  F5730676: stdSortTwoTimes.png 

REPOSITORY
  R241 KIO

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

AFFECTED FILES
  src/widgets/kdirmodel.cpp

To: jtamate, #frameworks, dfaure
Cc: michaelh