Optimize RoomList sorting

Keep the almost sorted list around and sort by the raw timestamp value
instead of doing the expensive toMSecSinceEpoch conversion.

5 files changed, 41 insertions, 35 deletions

diff --git a/src/CacheStructs.h b/src/CacheStructs.h
index 2051afc8..ab7bbc71 100644
--- a/src/CacheStructs.h
+++ b/src/CacheStructs.h
@@ -39,7 +39,8 @@ struct DescInfo
         QString event_id;
         QString userid;
         QString body;
-        QString timestamp;
+        QString descriptiveTime;
+        uint64_t timestamp;
         QDateTime datetime;
 };
 
diff --git a/src/RoomInfoListItem.cpp b/src/RoomInfoListItem.cpp
index 13c7b54d..ee8d532d 100644
--- a/src/RoomInfoListItem.cpp
+++ b/src/RoomInfoListItem.cpp
@@ -187,10 +187,11 @@ RoomInfoListItem::paintEvent(QPaintEvent *event)
                 QFont tsFont;
                 tsFont.setPointSizeF(tsFont.pointSizeF() * 0.9);
 #if QT_VERSION < QT_VERSION_CHECK(5, 11, 0)
-                const int msgStampWidth = QFontMetrics(tsFont).width(lastMsgInfo_.timestamp) + 4;
+                const int msgStampWidth =
+                  QFontMetrics(tsFont).width(lastMsgInfo_.descriptiveTime) + 4;
 #else
                 const int msgStampWidth =
-                  QFontMetrics(tsFont).horizontalAdvance(lastMsgInfo_.timestamp) + 4;
+                  QFontMetrics(tsFont).horizontalAdvance(lastMsgInfo_.descriptiveTime) + 4;
 #endif
                 // We use the full width of the widget if there is no unread msg bubble.
                 const int bottomLineWidthLimit = (unreadMsgCount_ > 0) ? msgStampWidth : 0;
@@ -227,7 +228,7 @@ RoomInfoListItem::paintEvent(QPaintEvent *event)
 
                         p.setFont(tsFont);
                         p.drawText(QPoint(width() - wm.padding - msgStampWidth, top_y),
-                                   lastMsgInfo_.timestamp);
+                                   lastMsgInfo_.descriptiveTime);
                         p.restore();
                 } else {
                         int btnWidth = (width() - wm.iconSize - 6 * wm.padding) / 2;
diff --git a/src/RoomList.cpp b/src/RoomList.cpp
index 764fabb4..617710c4 100644
--- a/src/RoomList.cpp
+++ b/src/RoomList.cpp
@@ -82,7 +82,9 @@ RoomList::addRoom(const QString &room_id, const RoomInfo &info)
                 MainWindow::instance()->openLeaveRoomDialog(room_id);
         });
 
-        rooms_.emplace(room_id, QSharedPointer<RoomInfoListItem>(room_item));
+        QSharedPointer<RoomInfoListItem> roomWidget(room_item);
+        rooms_.emplace(room_id, roomWidget);
+        rooms_sort_cache_.push_back(roomWidget);
 
         if (!info.avatar_url.empty())
                 updateAvatar(room_id, QString::fromStdString(info.avatar_url));
@@ -100,6 +102,14 @@ RoomList::updateAvatar(const QString &room_id, const QString &url)
 void
 RoomList::removeRoom(const QString &room_id, bool reset)
 {
+        auto roomIt = rooms_.find(room_id);
+        for (auto roomSortIt = rooms_sort_cache_.begin(); roomSortIt != rooms_sort_cache_.end();
+             ++roomSortIt) {
+                if (roomIt->second == *roomSortIt) {
+                        rooms_sort_cache_.erase(roomSortIt);
+                        break;
+                }
+        }
         rooms_.erase(room_id);
 
         if (rooms_.empty() || !reset)
@@ -336,7 +346,8 @@ RoomList::updateRoomDescription(const QString &roomid, const DescInfo &info)
 
 struct room_sort
 {
-        bool operator()(const RoomInfoListItem *a, const RoomInfoListItem *b) const
+        bool operator()(const QSharedPointer<RoomInfoListItem> a,
+                        const QSharedPointer<RoomInfoListItem> b) const
         {
                 // Sort by "importance" (i.e. invites before mentions before
                 // notifs before new events before old events), then secondly
@@ -351,12 +362,10 @@ struct room_sort
 
                 // Now sort by recency
                 // Zero if empty, otherwise the time that the event occured
-                const uint64_t a_recency = a->lastMessageInfo().userid.isEmpty()
-                                             ? 0
-                                             : a->lastMessageInfo().datetime.toMSecsSinceEpoch();
-                const uint64_t b_recency = b->lastMessageInfo().userid.isEmpty()
-                                             ? 0
-                                             : b->lastMessageInfo().datetime.toMSecsSinceEpoch();
+                const uint64_t a_recency =
+                  a->lastMessageInfo().userid.isEmpty() ? 0 : a->lastMessageInfo().timestamp;
+                const uint64_t b_recency =
+                  b->lastMessageInfo().userid.isEmpty() ? 0 : b->lastMessageInfo().timestamp;
                 return a_recency > b_recency;
         }
 };
@@ -366,27 +375,17 @@ RoomList::sortRoomsByLastMessage()
 {
         isSortPending_ = false;
 
-        std::multiset<RoomInfoListItem *, room_sort> times;
+        std::sort(begin(rooms_sort_cache_), end(rooms_sort_cache_), room_sort{});
 
-        for (int ii = 0; ii < contentsLayout_->count(); ++ii) {
-                auto room = qobject_cast<RoomInfoListItem *>(contentsLayout_->itemAt(ii)->widget());
+        int newIndex = 0;
+        for (const auto &roomWidget : rooms_sort_cache_) {
+                const auto currentIndex = contentsLayout_->indexOf(roomWidget.get());
 
-                if (!room)
-                        continue;
-                else
-                        times.insert(room);
-        }
-
-        for (auto it = times.cbegin(); it != times.cend(); ++it) {
-                const auto roomWidget   = *it;
-                const auto currentIndex = contentsLayout_->indexOf(roomWidget);
-                const auto newIndex     = std::distance(times.cbegin(), it);
-
-                if (currentIndex == newIndex)
-                        continue;
-
-                contentsLayout_->removeWidget(roomWidget);
-                contentsLayout_->insertWidget(newIndex, roomWidget);
+                if (currentIndex != newIndex) {
+                        contentsLayout_->removeWidget(roomWidget.get());
+                        contentsLayout_->insertWidget(newIndex, roomWidget.get());
+                }
+                newIndex++;
         }
 }
 
@@ -500,7 +499,9 @@ RoomList::addInvitedRoom(const QString &room_id, const RoomInfo &info)
         connect(room_item, &RoomInfoListItem::acceptInvite, this, &RoomList::acceptInvite);
         connect(room_item, &RoomInfoListItem::declineInvite, this, &RoomList::declineInvite);
 
-        rooms_.emplace(room_id, QSharedPointer<RoomInfoListItem>(room_item));
+        QSharedPointer<RoomInfoListItem> roomWidget(room_item);
+        rooms_.emplace(room_id, roomWidget);
+        rooms_sort_cache_.push_back(roomWidget);
 
         updateAvatar(room_id, QString::fromStdString(info.avatar_url));
 
diff --git a/src/RoomList.h b/src/RoomList.h
index a0151f92..d3470666 100644
--- a/src/RoomList.h
+++ b/src/RoomList.h
@@ -100,6 +100,7 @@ private:
         OverlayModal *joinRoomModal_;
 
         std::map<QString, QSharedPointer<RoomInfoListItem>> rooms_;
+        std::vector<QSharedPointer<RoomInfoListItem>> rooms_sort_cache_;
         QString selectedRoom_;
 
         bool isSortPending_ = false;
diff --git a/src/Utils.cpp b/src/Utils.cpp
index f0a8d61b..7f11a8cd 100644
--- a/src/Utils.cpp
+++ b/src/Utils.cpp
@@ -41,6 +41,7 @@ createDescriptionInfo(const Event &event, const QString &localUser, const QStrin
           utils::messageDescription<T>(
             username, QString::fromStdString(msg.content.body).trimmed(), sender == localUser),
           utils::descriptiveTime(ts),
+          msg.origin_server_ts,
           ts};
 }
 
@@ -184,9 +185,10 @@ utils::getMessageDescription(const TimelineEvent &event,
                 info.userid = sender;
                 info.body   = QString(" %1").arg(
                   messageDescription<Encrypted>(username, "", sender == localUser));
-                info.timestamp = utils::descriptiveTime(ts);
-                info.event_id  = QString::fromStdString(msg->event_id);
-                info.datetime  = ts;
+                info.timestamp       = msg->origin_server_ts;
+                info.descriptiveTime = utils::descriptiveTime(ts);
+                info.event_id        = QString::fromStdString(msg->event_id);
+                info.datetime        = ts;
 
                 return info;
         }