Replace custom single threaded merge sort with std::stable_sort
Needs ReviewPublic

Authored by fabiank on Aug 27 2019, 7:47 PM.

Details

Reviewers
elvisangelaccio
Group Reviewers
Dolphin

Diff Detail

Repository
R318 Dolphin
Branch
newsort
Lint
No Linters Available
Unit
No Unit Test Coverage
Build Status
Buildable 15711
Build 15729: arc lint + arc unit
fabiank created this revision.Aug 27 2019, 7:47 PM
Restricted Application added a project: Dolphin. · View Herald TranscriptAug 27 2019, 7:47 PM
Restricted Application added a subscriber: kfm-devel. · View Herald Transcript
fabiank requested review of this revision.Aug 27 2019, 7:47 PM

Using the new benchmark, we can see some improvement, mostly in the single threaded case:

Custom mergeSort:
RESULT : DolphinSortingBenchmark::sortInt():

0.25 msecs per iteration (total: 64, iterations: 256)

PASS : DolphinSortingBenchmark::sortString(usr_bin)
RESULT : DolphinSortingBenchmark::sortString():"usr_bin":

2.4 msecs per iteration (total: 79, iterations: 32)

PASS : DolphinSortingBenchmark::sortString(citynames)
RESULT : DolphinSortingBenchmark::sortString():"citynames":

0.14 msecs per iteration (total: 72, iterations: 512)

PASS : DolphinSortingBenchmark::sortStringParallel(usr_bin)
RESULT : DolphinSortingBenchmark::sortStringParallel():"usr_bin":

0.63 msecs per iteration (total: 81, iterations: 128)

PASS : DolphinSortingBenchmark::sortStringParallel(citynames)
RESULT : DolphinSortingBenchmark::sortStringParallel():"citynames":

0.056 msecs per iteration (total: 58, iterations: 1024)

PASS : DolphinSortingBenchmark::cleanupTestCase()
Totals: 7 passed, 0 failed, 0 skipped, 0 blacklisted, 1610ms

std::stable_sort:
RESULT : DolphinSortingBenchmark::sortInt():

0.10 msecs per iteration (total: 54, iterations: 512)

PASS : DolphinSortingBenchmark::sortString(usr_bin)
RESULT : DolphinSortingBenchmark::sortString():"usr_bin":

2.3 msecs per iteration (total: 76, iterations: 32)

PASS : DolphinSortingBenchmark::sortString(citynames)
RESULT : DolphinSortingBenchmark::sortString():"citynames":

0.11 msecs per iteration (total: 57, iterations: 512)

PASS : DolphinSortingBenchmark::sortStringParallel(usr_bin)
RESULT : DolphinSortingBenchmark::sortStringParallel():"usr_bin":

0.61 msecs per iteration (total: 79, iterations: 128)

PASS : DolphinSortingBenchmark::sortStringParallel(citynames)
RESULT : DolphinSortingBenchmark::sortStringParallel():"citynames":

0.047 msecs per iteration (total: 97, iterations: 2048)

I expected that std::inplace_merge would be faster than the custom merge function, but that was not the case in the benchmark; it was actually quite a bit slower.

meven added a subscriber: meven.Wed, Nov 13, 12:43 PM

Seems sane to me and nice since it removes some code.

src/kitemviews/private/kfileitemmodelsortalgorithm.h
84

Could you keep this function line at line 30 instead of moving, so that the diff actually shows what changed.