Merge lp:~josharenson/unity-scopes-shell/fix-overview-results-sorting into lp:unity-scopes-shell

[Josh Arenson]

Fix the list sorting of overviewresults

When the results for the model were set, the loop responsible for sorting them
was being executed hundreds of thousands of times. It has been replaced with a
simple insertion sort.

Fix the list sorting of overviewresults

When the results for the model were set, the loop responsible for sorting them
was being executed hundreds of thousands of times. It has been replaced with a
simple insertion sort.

[Paweł Stołowski (stolowski)]

Looks good to me, thanks!

As discussed on IRC, it's not clear what made the previous implementation so slow (although the fact the 'i' wasn't incremented on every iteration could be part of the problem), but what you propose make sense and is an improvement, the tests are passing and I haven't found any regression with this change, so +1.

One remark only, could you please remove the extra line before we land this:
32 + for (int i = 1; i < m_results.size(); i++) {
33 +

review: Approve

[lp:~josharenson/unity-scopes-shell/fix-overview-results-sorting]

356. By Josh Arenson on 2016-12-16

Clean syntax

[Josh Arenson (josharenson)]

> Looks good to me, thanks!
>
> As discussed on IRC, it's not clear what made the previous implementation so
> slow (although the fact the 'i' wasn't incremented on every iteration could be
> part of the problem), but what you propose make sense and is an improvement,
> the tests are passing and I haven't found any regression with this change, so
> +1.
>
> One remark only, could you please remove the extra line before we land this:
> 32 + for (int i = 1; i < m_results.size(); i++) {
> 33 +

Removed the line and also changed "j -= 1" to "j--" as that was bothering me as well :-)

[Andrea Cimitan (cimi)]

Finally managed to test it on my laptop (I wasn't able to run unity8 on my laptop due to deps and such), confirm it solve the slow reordering issue

review: Approve

Unmerged revisions

356. By Josh Arenson on 2016-12-16

Clean syntax

355. By Josh Arenson on 2016-12-12

Fix the list sorting of overviewresults

When the results for the model were set, the loop responsible for sorting them
was being executed hundreds of thousands of times. It has been replaced with a
simple insertion sort.

=== modified file 'src/Unity/overviewresults.cpp'
--- src/Unity/overviewresults.cpp	2015-09-08 12:32:05 +0000
+++ src/Unity/overviewresults.cpp	2016-12-16 15:39:51 +0000
@@ -126,21 +126,26 @@
         ++row;
     }
 
-    // iterate over results, move rows if positions changes
-    for (int i = 0; i<m_results.size(); )
-    {
-        auto scope_meta = m_results.at(i);
-        const QString id = QString::fromStdString(scope_meta->scope_id());
-        if (newResult.contains(id)) {
-            pos = newResult[id];
-            if (pos != i) {
-                beginMoveRows(QModelIndex(), i, i, QModelIndex(), pos + (pos > i ? 1 : 0));
-                m_results.move(i, pos);
-                endMoveRows();
-                continue;
-            }
+
+    // Iterate over results, move rows if positions changes.
+    // Use the ordering of newResults to sort m_results.
+    // Since the list is small and usually already sorted, or has only a
+    // single element out of order, insertion sort suffices.
+    QList<int> sort_keys;
+    for (int i = 0; i < m_results.size(); i++){
+        QString current_string = QString::fromStdString(m_results.at(i)->scope_id());
+        sort_keys.append(newResult[current_string]);
+    }
+
+    for (int i = 1; i < m_results.size(); i++) {
+        int j = i;
+        while (j > 0 && sort_keys.at(j - 1) > sort_keys.at(j)) {
+            sort_keys.swap(j, j - 1);
+            beginMoveRows(QModelIndex(), j, j, QModelIndex(), j - 1);
+            m_results.move(j - 1, j);
+            endMoveRows();
+            j--;
         }
-        i++;
     }
 
     Q_EMIT countChanged();