VIVOTEK Digest

1. 每個 column 個都要多一個 column 來儲存 uncompress 的 string (除了不用搜尋的 snapshot & timestamp column), 但這會增加整個 database 的 size
2. or 要增加 compress, uncompress function 在 Create Table 時加入 https://www.sqlite.org/fts3.html#the_compress_and_uncompress_options , 但這要直接使用 SQLite 的 API function, 對我們使用 Qt 包一層的 API 不好實作

針對常用的match role, 可利用QHash (or QMap) 多存一份, 來加快 search 效率

我們在設計model通常都會定義一個存unique string value的IdRole當作model item的索引, 且會很頻繁對這個role作match, 從"flags對QAbstractItemModel::match的效能影響"中的實驗中可知,
針對string value去作match在效率上是很糟的, 所以只要model數量大到一個程度, 就會很容易使UI thread hang住. 針對這部分的參考解法大致如下,

1. maintain一個QHash把每個model item的IdRole value跟相對應的model index存起來
2. 複寫match, 如果是是要查IdRole, 就直接從QHash找以提升效率
3. 由於QStandardItemModel::clear本身不會觸發rowsAboutToBeRemoved, 所以即使呼叫clear, 還是要主動去清掉hash

#include <QHash>
#include <QModelIndex>
#include <QPersistentModelIndex>
#include <QStandardItemModel>
#include <QVariant>

class MyListModel : public QStandardItemModel
{
  Q_OBJECT

public:
  enum Roles
  {
    IdRole = Qt::UserRole + 1,
    DataRole
  };
  MyListModel(QObject *parent = nullptr)
  {
    // 把每個model item的IdRole value存到QHash裡, key是id, value就是model index (必須用QPersistentModelIndex)
    // 如果是tree model記得要recursive把childrn也加進來,
    // 主要是如果使用者是先把model item的children都append好, 再append本身進來的話, 只會觸發一次rowsInserted.
    QObject::connect(this, &QAbstractItemModel::rowsInserted, [=](const QModelIndex &parent, int start, int end) {
      for (int row = start; row <= end; row++)
      {
        auto mdIndex = index(row, 0, parent);
        auto id = data(mdIndex, MyListModel::IdRole);
        m_idModelIndexHash.insert(id, QPersistentModelIndex(mdIndex));
      }
    });
    QObject::connect(this, &QAbstractItemModel::rowsAboutToBeRemoved, this, [=](const QModelIndex &parent, int start, int end) {
      for (int row = start; row <= end; row++)
      {
        auto mdIndex = index(row, 0, parent);
        auto id = data(mdIndex, MyListModel::IdRole);
        m_idModelIndexHash.remove(id);
      }
    });
  }
  virtual ~MyListModel() = default;

  // 覆寫match function, 如果針對IdRole就去QHash以提升效率
  virtual QModelIndexList match(const QModelIndex &start, int role, const QVariant &value, int hits = 1, Qt::MatchFlags flags = Qt::MatchFlags(Qt::MatchStartsWith | Qt::MatchWrap)) const override
  {
    if (role != MyListModel::IdRole)
    {
      return QStandardItemModel::match(start, role, value, hits, flags);
    }

    // todo, !m_idModelIndexHash.contains just return empty can enhance performance, but m_idModelIndexHash must be 100% correct
    if (!m_idModelIndexHash.contains(value))
    {
      return QModelIndexList();
    }

    return QModelIndexList() << m_idModelIndexHash.value(value);
  }

  // 由於QStandardItemModel::clear本身不會觸發rowsAboutToBeRemoved, 所以clear記得要主動清掉hash
  void clearIdHash()
  {
    m_idModelIndexMap.clear();
  }

  QHash<int, QByteArray> roleNames() const override
  {
    QHash<int, QByteArray> hash;
    hash[MyListModel::DataRole] = "dataRole";
    hash[MyListModel::IdRole] = "idRole";
    return hash;
  }

protected:
  QHash<QVariant, QPersistentModelIndex> m_idModelIndexHash;
};

延續"flags對QAbstractItemModel::match的效能影響"中的實驗方法,
如果利用QHash得到的結果如下,

match from	elapsed (ms)
QStandardItemModel::match	55194
QHash	63

由此可見效率是大大大大提升的, 缺點就是你要好好管理m_idModelIndexHash, 一有差錯都會導致model行為不正確.

秘訣: flags 只要用 Qt::MatchExactly 即可, 如果是 tree model 則再加上Qt::MatchRecursive

QModelIndexList QAbstractItemModel::match(const QModelIndex &start, int role, const QVariant &value, int hits = 1, Qt::MatchFlags flags = Qt::MatchFlags(Qt::MatchStartsWith|Qt::MatchWrap)) const


QAbstractItemModel::match中 flags 參數其實是蠻巨大的.
一般我們在輸入這個 flags 通常都是 copy / paste 舊有的 code , 所以最常看到的組合就是"Qt::MatchFixedString | Qt::MatchCaseSensitive | Qt::MatchRecursive"如以下所示,


model.match(model.index(0,0), IDRole, value, 1, Qt::MatchFixedString | Qt::MatchCaseSensitive | Qt::MatchRecursive);


這是很沒有效率的, 例如對100000筆資料的list model中針對int value作match得到以下的結果,

match for int value flags	elapsed (ms)
Qt::MatchFixedString | Qt::MatchCaseSensitive | Qt::MatchRecursive	125593
Qt::MatchFixedString | Qt::MatchCaseSensitive	120216
Qt::MatchExactly	22162

由此可見型別搞錯會造成的影響有多嚴重,
還有一點就是如果是list model的話, 就不必要下Qt::MatchRecursive, 這樣又可增進一點效能.
另外對string value作match得到的結果如下,

match for string value flags	elapsed (ms)
Qt::MatchFixedString | Qt::MatchCaseSensitive	56188
Qt::MatchExactly	55194

於此可見, 如果match要compare的value是要完全一致的, 其實只要使用Qt::MatchExactly就萬無一失了.

前言

最近在tune ext4 的格式化速度，發現ext4 有 flex_bg 這個 feature 可以用，就開起來測看看。關於 flex_bg 的詳細內容可以參考 ref

概略來說就是將幾個block groups 組成一個 flex_bg
它會將每個 flex_bg 的 group 0 之後的 groups 的 DB bitmap, inode bitmap, inode table
存放到 group 0 統一管理(放不下的時候會放到下一個group)
存放的時候每個 DB bitmap, inode bitmap 都會佔 1 個 block, inode table 會佔 8 個 block
所以DB bitmap, inode bitmap, inode table 之間在開始存放的時候都隔 $GRUUP_SIZE 個blocks (-G $GRUUP_SIZE帶入)

測試

flex_bg 預設的 group size 是 16，使用2的冪次遞增group size來測試的時候一開始一切看
起來都很美好，format 時間隨著group size 增加而下降。一直到 group size 指定為
8192的時候忽然發現 format time 暴增...



這真的蠻奇怪的...網路上也找不到相關的討論。於是只好自己去看 e2fsprogs 裡面關於mke2fs這一段的實作在幹嘛。

結論

首先 在 block size 4KB 下 ext4 管理用的 bitmap 最多 可以 mapping 32K個 block (bitmap佔1個block 32k bits)
所以 blocks per group 最多就是 32768 (可以調小 調小有可能會造成mke2fs 在 -G4096 的時候變慢 後面說明)
以 8K 的 group size 配置的時候，這些metadata(DB bitmap, inode bitmap, inode table)的初始擺放位置
分別是第 1025, 9217, 17409 個 block (中間都間隔 8192 個 block)

這在放置到第 1919 個 group 的 metadata 的時候會發生一個現象





可以看到在配置第 1918 個 group 的 inode table 時即將超出 group 0 的邊界了(32768 blocks per group)

所以在配置地 1919 個 group 的 inode table 時 mke2fs 的實作方法會回頭找 free block 來
存放。這時候找到的是第 2945 個 block(當然如果 group 0 中都沒有 free block 放
metadata 的時候 會開始往 group 1 放不過 mke2fs 的策略看來是 group 0 還有空間就先用
group 0 ... 就算最後一定不夠用如果它是接著往 group 2 放 inode table 的話 就不會有現在的問題了...)
這就造成原本理想上算好間隔分散存放的 metadata 開始交錯配置了。在找free block的時候
原本都是馬上返回下一個free block 的 function call (flexbg_offset)在開始交錯配置以後
都要再做一些 search 才能找到下一個可以用的blockprofile
整個 mke2fs 過程花最多時間也是在 flexbg_offset 這個 function call
(對 1TB 硬碟format 整個 format 過程 總共花 126 秒 其中有121 秒花在 flexbg_offset 的處理)
所以在 GROUP_SIZE 是 8192 的時候會因為這些 metadata 在 group 0 裡面配置的時候容易發生交錯放置的情況
以至於 mke2fs 在搜尋下一個可以放metadata 的 block 的時候 比起其他的 GROUP_SIZE 花比較多的 overhead。

另外 

如果在 -G 8192 的時候加上 -b 8192 的 option (指定 block size 成 8K)->
則 -G 8192 就會變得跟 -G 4096 速度差不多。這是因為 block size 變 8K -> blocks per group 變 64K
(其實有少一些零頭 實際上是 65528個，bitmap 可以 mapping 的 block 數 變 64K )
則 inode table 配置的時候 不會很快遇到 group block 邊界的問題 就比較不會發生和 DB bitmap 或 inode bitmap 交錯配置的情況