D23507: Replace custom single threaded merge sort with std::stable_sort

[Fabian Kosmale]

fabiank added reviewers: Dolphin, elvisangelaccio.
fabiank added a comment.


  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.

REPOSITORY
  R318 Dolphin

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

To: fabiank, #dolphin, elvisangelaccio
Cc: kfm-devel, aprcela, vmarinescu, fprice, MrPepe, fbampaloukas, alexde, Codezela, feverfew, meven, spoorun, navarromorales, firef, andrebarros, emmanuelp, mikesomov
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.kde.org/mailman/private/kfm-devel/attachments/20190827/62104ca3/attachment.htm>