Review Request 108824: New sorting algorithm for Dolphin

[Emmanuel Pescosta]

> On Feb. 17, 2013, 10:11 a.m., Frank Reininghaus wrote:
> > > Thank you Frank, I will have a look into that and I will add some time measurement stuff to create a proper sorting performance benchmark ;)
> > 
> > Great, as soon as we have a test+benchmark, we can work on ironing out the last details and make sure that this can go into master.
> > 
> > Two small remarks:
> > 
> > 1. I see the function expandedParentsCountCompare() in your diff. This function does not exist any more in master - you might want to rebase your diff on current master.
> > 
> > 2. Concerning the "Avoid some unnecessary lessThan calls" idea: this actually makes your timsort function *much* harder to use. In version 1 of your patch, the function could easily be used as a drop-in replacement for std::sort, std::stable_sort, qSort, etc. by everyone who wants to use TimSort. This is no longer the case in version 2. Does this change improve the performance considerably? If that is not the case, I think that we should not make the function harder to use just to save a few microseconds.

> 2.

2.480.099 compare calls instead of 2.565.333 in my "test" case ;) (without binary sort less-than calls)

With this patch, the less-equal and greater-than comparisons needs only 1 compare call instead of 2 compare calls -> So the real world improvement is sometimes big and sometimes small

But we will see it better, when I have finished the sorting benchmark ;)


- Emmanuel


-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
http://git.reviewboard.kde.org/r/108824/#review27566
-----------------------------------------------------------


On Feb. 16, 2013, 6:19 p.m., Emmanuel Pescosta wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> http://git.reviewboard.kde.org/r/108824/
> -----------------------------------------------------------
> 
> (Updated Feb. 16, 2013, 6:19 p.m.)
> 
> 
> Review request for Dolphin and Frank Reininghaus.
> 
> 
> Description
> -------
> 
> Implemented a new sorting algorithm called Tim Sort which is a modified Merge Sort algorithm (http://svn.python.org/projects/python/trunk/Objects/listsort.txt) - Default sorting algorithm in Python and Java
> 
> Tim Sort is really fast for already sorted lists (Great for inserting new items, sort role changes - see benchmark 2, ...)
> 
> Some benchmarks (200k folders and files):
> # Sort Type: Name => TimSort: 1755 ms - Parallel MergeSort: 1547 ms
> # Sort Type: Name (Reorder descending) => TimSort: 163 ms - Parallel MergeSort: 434 ms
> # Sort Type: Size => TimSort: 259 ms - Parallel MergeSort: 516 ms
> # Sort Type: Type => TimSort: 269 ms - Parallel MergeSort: 594 ms
> 
> Btw.: Tim Sort uses only 1 core!
> 
> ToDo: Write a benchmark for sorting algorithms
> 
> 
> Diffs
> -----
> 
>   dolphin/src/kitemviews/kfileitemmodel.h 903291a 
>   dolphin/src/kitemviews/kfileitemmodel.cpp a763b3f 
>   dolphin/src/kitemviews/private/kfileitemmodelsortalgorithm.h 1d56894 
> 
> Diff: http://git.reviewboard.kde.org/r/108824/diff/
> 
> 
> Testing
> -------
> 
> Sorting works fine for me
> 
> 
> Thanks,
> 
> Emmanuel Pescosta
> 
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.kde.org/mailman/private/kfm-devel/attachments/20130218/102154eb/attachment.htm>