Differential D12945

kcoredirlister lstItems benchmark
ClosedPublic
Actions

Authored by jtamate on May 17 2018, 2:38 PM.

Details

Reviewers
dfaure
Group Reviewers
Frameworks
Commits
R241:908bfca9fe72: kcoredirlister lstItems benchmark
Summary

Decide which data structure is best for kcoredirlister lstItems.

The results in one machine (in ms):

10 itemsQListQListBinaryQMapQHash
add0.0500.0480.0510.050
findByName0.00000570.00000600.00000600.0000056
findByUrl0.00000560.00000600.00000590.0000059
findByUrlAll0.0180.0200.0170.016
100 itemsQListQListBinaryQMapQHash
add0.460.550.540.52
findByName0.00260.00130.00140.0031
findByUrl0.00280.00260.00240.0021
findByUrlAll0.570.220.1990.17
1000 itemsQListQListBinaryQMapQHash
add4.86.16.05.3
findByName0.0370.00230.00220.16
findByUrl0.0300.00540.00460.0038
findByUrlAll402.52.31.8
10000 itemsQListQListBinaryQMapQHash
add47696853.0
findByName1.80.00340.00331.0
findByUrl1.10.00840.00790.0062
findByUrlAll4372332821

Diff Detail

Repository
R241 KIO
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.May 17 2018, 2:38 PM
Restricted Application added a project: Frameworks. · View Herald TranscriptMay 17 2018, 2:38 PM
Restricted Application added a subscriber: kde-frameworks-devel. · View Herald Transcript
jtamate requested review of this revision.May 17 2018, 2:38 PM
jtamate added a dependent revision: D11282: less expensive findByUrl in KCoreDirListerCache.
dfaure requested changes to this revision.May 25 2018, 11:06 PM
dfaure added inline comments.
autotests/kcoredirlister_benchmark.cpp
245

As discussed in https://phabricator.kde.org/D10742, this doesn't handle the case of hash collisions (this code assumes each URL gets a unique hash). So this commit needs to be updated as well, possibly by just removing this class if making it right is too much effort, for too slow code in the end?

330

number is always 50 so you could remove it as a parameter in all these methods and just use a static const int for instance.

It's more dangerous to have it as a method parameter: if one caller passes a different number, the benchmarks won't be comparable anymore...

377

QBENCHMARK takes care of repeating as many times as necessary, so this for loop isn't needed, is it?

385

copy/paste errors? This is looking up the same URL three times.

This revision now requires changes to proceed.May 25 2018, 11:06 PM
jtamate updated this revision to Diff 35585.Jun 5 2018, 7:12 AM
jtamate edited the summary of this revision. (Show Details)

Changed the structure QListBinaryHash to QMap
Changed from KFileItems pointers to Values (it caused memory problems).

Imported the parts that handle the filters to do the benchmarks of addNewItems.
Assume KFileItems has < operands.

dfaure added a comment.Jul 6 2018, 8:51 AM

It's also interesting to look at numbers for small directories (which is still the most common case, too).

This code could use a run of uncrustify to match the coding style of the rest of kio, but otherwise it looks good.

autotests/kcoredirlister_benchmark.cpp
373

In the long run, people will really wonder what's that about, since your other commit will remove the NonMovableList class/hack ;)

680

fromLocalFile("") doesn't look valid to me

jtamate updated this revision to Diff 38134.Jul 20 2018, 12:47 PM
jtamate marked 6 inline comments as done.
jtamate edited the summary of this revision. (Show Details)

Hopefully done all the requested changes.
Passed uncristify-kf5.
Removed the classes for simulating the filtering.
Added benchmarks for 10, 100, 1000 and 10000 items.
The items are inserted in the same random order for all the implementations.

dfaure accepted this revision.Jul 26 2018, 10:00 PM
This revision is now accepted and ready to land.Jul 26 2018, 10:00 PM
jtamate edited the summary of this revision. (Show Details)Jul 27 2018, 7:12 AM
Closed by commit R241:908bfca9fe72: kcoredirlister lstItems benchmark (authored by jtamate). · Explain WhyJul 27 2018, 2:46 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 38612

View Options

autotests/CMakeLists.txt

Loading...
View Options

autotests/kcoredirlister_benchmark.cpp

Loading...