Оптимизационное (Тухлый косит под тру девелопера)
LeechCraft показывает довольно полную статистику о подключенных пирах для каждого торрента. Для этой статистики есть свой QTreeView, QSortFilterProxyModel, дабы юзер мог сортировать статистику, и своя модель class PeersModel : public QAbstractItemModel. Для поддержания модели в актуальном состоянии раз в секунду вызывается функция PeersModel::Update(const QList<PeerInfo>& peers, int torrent), которой передается список текущих пиров и номер торрента.
В начале все выглядело так:
1: void PeersModel::Update (const QList<PeerInfo>& peers, int torrent)
2: {
3: CurrentTorrent_ = torrent;
4: QList<PeerInfo> peers2insert (peers.size ());
5: QMap<QString, int> IP2position;
6:
7: qDebug () << "filling ip2position";
8: for (int i = 0; i < Peers_.size (); ++i)
9: IP2position [Peers_.at (i).IP_] = i;
10:
11: qDebug () << "finding positions";
12: int psize = peers.size (),
13: lPsize = Peers_.size ();
14: for (int i = 0; i < psize; ++i)
15: {
16: PeerInfo pi = peers.at (i);
17:
18: int found = false;
19: for (int j = 0; j < lPsize; ++j)
20: if (Peers_.at (j).IP_ == pi.IP_)
21: {
22: found = true;
23: Peers_ [j] = pi;
24: IP2position.remove (pi.IP_);
25: emit dataChanged (index (j, 1), index (j, 11));
26: break;
27: }
28:
29: if (found)
30: continue;
31:
32: peers2insert << pi;
33: }
34:
35: qDebug () << "removing";
36: QList<int> values = IP2position.values ();
37: qSort (values.begin (), values.end (), qGreater<int> ());
38: for (int i = 0; i < values.size (); ++i)
39: {
40: beginRemoveRows (QModelIndex (), values.at (i), values.at (i));
41: Peers_.removeAt (values.at (i));
42: endRemoveRows ();
43: }
44:
45: qDebug () << "adding";
46: if (peers2insert.size ())
47: {
48: beginInsertRows (QModelIndex (), Peers_.size (), Peers_.size () + peers2insert.size () - 1);
49: Peers_ += peers2insert;
50: endInsertRows ();
51: }
52: qDebug () << "finished";
53: }
При больших количествах пиров (Peers_.size () == peers.size () == 70) код на строках 12-33, ищущий, какие пиры обновились, какие добавились, а какие вообще перестали существовать, выполнялся чуть более 3 секунд (сравнивались временные метки в логах, так как нормального профилера под рукой не оказалось). Не дело, тормоза видны невооруженным глазом. Остальные части функции выполнялись не больше 100 миллисекунд, чем можно пренебречь. Оптимизируем именно тот кусок. При всех оптимизациях мы будем пользоваться тем, что никакие постоянные структуры данных не меняются в ходе работы кода 12-33, все добавление/удаление идет после вычисления вторым проходом.
Оптимизация 1
Замечаем, что мапа IP2position уже содержит всю информацию по соответствию IP <-> позиция в Peers_. Поиск по ней — O(log(n)), судя по Assistant'у, в то время как поиск по QList — O(n). Итак, заменяем тот код таким:
1: int psize = peers.size ();
2: for (int i = 0; i < psize; ++i)
3: {
4: PeerInfo pi = peers.at (i);
5: QMap<QString, int>::iterator pos = IP2position.find (pi.IP_);
6:
7: if (pos != IP2position.end ())
8: {
9: int ind = pos.value ();
10: Peers_ [ind] = pi;
11: IP2position.erase (pos);
12: emit dataChanged (index (ind, 1), index (ind, 11));
13: }
14: else
15: peers2insert << pi;
16: }
Судя по логам, на таком же количестве пиров в установившемся режиме этот кусок выполняется чуть меньше 2 секунд. Прогресс налицо!
Оптимизация 2
Можно заметить, что порядок данных в IP2position неважен, и для QString определен qHash. К чему я это? Правильно, к тому, что можно QMap заменить на QHash. Выигрыш будет, так как O(log(n)) сведется к O(1). Заодно вынесем испускание сигнала dataChanged в отдельный блок, чтобы посмотреть, сколько времени он занимает. Итак, получаем лог вида
[16:42:38.607] [thread ptr 0x641d30] filling ip2position [16:42:38.607] [thread ptr 0x641d30] finding positions [16:42:38.608] [thread ptr 0x641d30] emitting [16:42:40.640] [thread ptr 0x641d30] removing [16:42:40.641] [thread ptr 0x641d30] adding [16:42:40.642] [thread ptr 0x641d30] finished
для кода
1: qDebug () << "finding positions";
2: int psize = peers.size ();
3: QList<PeerInfo> peers2insert;
4: QList<int> changedPos;
5: for (int i = 0; i < psize; ++i)
6: {
7: const PeerInfo& pi = peers.at (i);
8: QHash<QString, int>::iterator pos = IP2position.find (pi.IP_);
9: if (pos != IP2position.end ())
10: {
11: int ind = pos.value ();
12: Peers_ [ind] = pi;
13: IP2position.erase (pos);
14: changedPos << ind;
15: }
16: else
17: peers2insert << pi;
18: }
19:
20: qDebug () << "emitting";
21: int cp = changedPos.size ();
22: for (int i = 0; i < cp; ++i)
23: {
24: emit dataChanged (index (changedPos [i], 1), index (changedPos [i], 11));
25: }
26:
27: qDebug () << "removing";
То есть, мы видим, что оптимизировать поиск измененных пиров было вообще бессмысленно. Ну что ж, все равно, можно будет ощущать внутреннюю гордость, что что-то работает быстрее.
Анализ
Такая длительная задержка в emit в сочетании с тем, что она проявляется лишь при включенной сортировке, наводит на мысль, что при каждом сигнале dataChanged прокси-модель QSortFilterProxyModel пересортировывается. Таким образом, нам нужно либо свести количество испусканий dataChanged к минимуму, либо вообще уведомлять View об изменении данных по-другому.
Так как пока не нужно сохранять выделение между обновлениями (разве что, для красоты, но к черту красоту!), будем просто вызывать reset(). Итак, вот последняя версия функции, которая совершенно не тормозит:
1: void PeersModel::Update (const QList<PeerInfo>& peers, int torrent)
2: {
3: CurrentTorrent_ = torrent;
4:
5: QHash<QString, int> IP2position;
6: for (int i = 0; i < Peers_.size (); ++i)
7: IP2position [Peers_.at (i).IP_] = i;
8:
9: int psize = peers.size ();
10: QList<PeerInfo> peers2insert;
11: for (int i = 0; i < psize; ++i)
12: {
13: const PeerInfo& pi = peers.at (i);
14: QHash<QString, int>::iterator pos = IP2position.find (pi.IP_);
15: if (pos != IP2position.end ())
16: {
17: Peers_ [pos.value ()] = pi;
18: IP2position.erase (pos);
19: }
20: else
21: peers2insert << pi;
22: }
23:
24:
25:
26: QList<int> values = IP2position.values ();
27: qSort (values.begin (), values.end (), qGreater<int> ());
28: for (int i = 0; i < values.size (); ++i)
29: {
30: beginRemoveRows (QModelIndex (), values.at (i), values.at (i));
31: Peers_.removeAt (values.at (i));
32: endRemoveRows ();
33: }
34:
35: reset ();
36:
37: if (peers2insert.size ())
38: {
39: beginInsertRows (QModelIndex (), Peers_.size (), Peers_.size () + peers2insert.size () - 1);
40: Peers_ += peers2insert;
41: endInsertRows ();
42: }
43: }
Здесь мы переставили reset() так, что модель опрашивается при минимальном видимом количестве пиров, чтобы количество запросов тоже было минимальным.
Результат
Среднее время на цикл до всех оптимизаций — 3 секунды, после — 40 миллисекунд. Причем, это время можно еще уменьшить за счет подбора соотношения количество_пиров/количество_измененных_данных, когда выгоднее испускать несколько dataChanged, а когда — сразу бабахать reset()'ом.
Premature optimization is the root of all evil (эпилог)
Да, правда, так. Сначала нужно узнать, что на самом деле вызывает падение производительности, и только потом браться за оптимизацию.