Qt: what is the most efficient way to vizualize a large 2D array?

I’m porting a project which uses Curses to visualize a large (5000×5000, for example) 2D array of chars. The problem is, it must be a high-performance project where the array is constantly updated, but in its current state, the output to stdout is a bottleneck no matter how I optimize the back-end. The project would benefit from using a faster and object-oriented approach Qt can provide. What I’ve tried:

#include <QtWidgets>

int main(int argc, char *argv[])
{
    QApplication a(argc, argv);
    QGraphicsScene scene;
    QGraphicsView view(&scene);

    double totalY = 0;
    for (size_t i = 0; i < 5000; ++i) {
        double totalX = 0;
        for (size_t j = 0; j < 5000; ++j) {
            // Add an arbitrary char
            QGraphicsSimpleTextItem *simpleText = scene.addSimpleText(QChar('.'));
            simpleText->setPos(totalX, totalY);
            // Add cell's width and height respectively
            totalX += 10;
        }
        totalY += 10;
    }

    view.show();

    return a.exec();
}

But it turned out that creating 5000×5000 graphic items is waaay slower. My next idea is to create some sort of viewport which will eliminate the need to use graphic items. It could be some canvas (QImage), which I will clear and draw on every time the array is updated. But what do you recommend?

Answer

2nd Attempt

After the 1st attempt wasn’t really satisfying, I followed the hint of V.K.:

I mean that drawing a character is very expensive operation. So I suggest that you draw each possible character (I assume there are not many of them) to some small image in memory. And than do bitblt (if you do not understand some word, then google for it), i.e. copy blocks of bytes to the final QImage. It will be much faster than painting texts.

testQLargeCharTable2.cc:

#include <cassert>
#include <algorithm>
#include <random>
#include <vector>

#include <QtWidgets>

template <typename Value>
class MatrixT {
  private:
    size_t _nCols;
    std::vector<Value> _values; 
  public:
    MatrixT(size_t nRows, size_t nCols, Value value = Value()):
      _nCols((assert(nCols > 0), nCols)), _values(nRows * nCols, value)
    { }

    size_t rows() const { return _values.size() / _nCols; }
    size_t cols() const { return _nCols; }
    
    Value* operator[](size_t i)
    {
      assert(i < rows());
      return &_values[i * _nCols];
    }
    const Value* operator[](size_t i) const
    {
      assert(i < rows());
      return &_values[i * _nCols];
    }
};

using CharTable = MatrixT<char>;

class CharTableView: public QAbstractScrollArea {
  private:
    const CharTable* pTbl = nullptr;
    using CharCache = std::map<char, QPixmap>;
    int wCell;
    int hCell;
    CharCache cacheChars;

  public:
    CharTableView(QWidget* pQParent = nullptr);
    virtual ~CharTableView() = default;

    CharTableView(const CharTableView&) = delete;
    CharTableView& operator=(const CharTableView&) = delete;

    void set(CharTable* pTbl)
    {
      this->pTbl = pTbl;
      updateScrollBars();
      update();
    }

  protected:
    virtual void resizeEvent(QResizeEvent* pQEvent) override;
    virtual void paintEvent(QPaintEvent* pQEvent) override;

  private:
    void updateScrollBars();
    const QPixmap& getCharPixmap(char c);
};

void CharTableView::resizeEvent(QResizeEvent* pQEvent)
{
  updateScrollBars();
}

void CharTableView::paintEvent(QPaintEvent* pQEvent)
{
  if (!pTbl) return;
  const int xView = horizontalScrollBar()
    ? horizontalScrollBar()->value() : 0;
  const int yView = verticalScrollBar()
    ? verticalScrollBar()->value() : 0;
  const int wView = viewport()->width();
  const int hView = viewport()->height();
  const int iRow0 = yView / hCell;
  const int iCol0 = xView / wCell;
  const int iRowN = std::min((int)pTbl->rows(), (yView + hView) / hCell + 1);
  const int iColN = std::min((int)pTbl->cols(), (xView + wView) / wCell + 1);
  QPainter qPainter(viewport());
  for (int iRow = iRow0; iRow < iRowN; ++iRow) {
    const char*const row = (*pTbl)[iRow];
    const int yCell = iRow * hCell - yView;
    for (int iCol = iCol0; iCol < iColN; ++iCol) {
      const int xCell = iCol * wCell - xView;
      const QPixmap& qPixmap = getCharPixmap(row[iCol]);
      qPainter.drawPixmap(
        QRect(xCell, yCell, wCell, hCell),
        qPixmap);
    }
  }
}

CharTableView::CharTableView(QWidget* pQWidget):
  QAbstractScrollArea(pQWidget)
{
  QFontMetrics qFontMetrics(viewport()->font());
  wCell = 2 * qFontMetrics.averageCharWidth();
  hCell = qFontMetrics.height();
}

void CharTableView::updateScrollBars()
{
  const int w = (int)(pTbl ? pTbl->cols() : 0) * wCell;
  const int h = (int)(pTbl ? pTbl->rows() : 0) * hCell;
  const QSize sizeView = viewport()->size();
  QScrollBar*const pQScrBarH = horizontalScrollBar();
  pQScrBarH->setRange(0, w > sizeView.width() ? w - sizeView.width() : 0);
  pQScrBarH->setPageStep(sizeView.width());
  QScrollBar*const pQScrBarV = verticalScrollBar();
  pQScrBarV->setRange(0, h > sizeView.height() ? h - sizeView.height() : 0);
  pQScrBarV->setPageStep(sizeView.height());
}

const QPixmap& CharTableView::getCharPixmap(char c)
{
  const CharCache::iterator iter = cacheChars.find(c);
  if (iter != cacheChars.end()) return iter->second;
  QPixmap& qPixmap = cacheChars[c] = QPixmap(wCell, hCell);
  qPixmap.fill(QColor(0, 0, 0, 0));
  { QPainter qPainter(&qPixmap);
    qPainter.drawText(
      QRect(0, 0, wCell, hCell),
      Qt::AlignCenter,
      QString(QChar(c)));
  }
  return qPixmap;
}

int main(int argc, char** argv)
{
  qDebug() << "Qt Version:" << QT_VERSION_STR;
  const size_t n = 10;
  QApplication app(argc, argv);
  // setup data
  const char chars[]
    = "0123456789()[]{}/&%$!'+#?="
      "abcdefghijklmnopqrstuvwxyz"
      "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  CharTable tbl(5000, 5000);
  std::random_device rd;
  std::mt19937 rng(rd()); // seed the generator
  std::uniform_int_distribution<size_t> distr(0, std::size(chars) - 1);
  for (size_t i = 0; i < tbl.rows(); ++i) {
    char*const row = tbl[i];
    for (size_t j = 0; j < tbl.cols(); ++j) {
      row[j] = chars[distr(rng)];
    }
  }
  // setup GUI
  CharTableView qCharTableView;
  qCharTableView.setWindowTitle("Large Character Table View - 2nd Attempt");
  qCharTableView.resize(1024, 768);
  qCharTableView.set(&tbl);
  qCharTableView.show();
  // runtime loop
  return app.exec();
}

Output:

Snapshot of testQLargeCharTable2.exe (GIF Animation)

I did the same test with a full screen window (2560×1280). The performance still was comparable. (The snapped GIF animations were too large to be uploaded here.)

In opposition to the hint of V.K., I used QPixmap. QImage can be modified with a QPainter as well. There is also a QPainter::drawImage() available.

1st Attempt

My first attempt was to print characters in the paintEvent() of a class derived from QAbstractScrollArea. Thereby, I carefully skipped all rows and columns which are outside of the view area. At the first glance, the performance seemed not that bad but with full screen window size, the approach showed weaknesses. While dragging the scrollbars, the output was significantly lacking behind.

testQLargeCharTable1.cc:

#include <cassert>
#include <algorithm>
#include <random>
#include <vector>

#include <QtWidgets>

template <typename Value>
class MatrixT {
  private:
    size_t _nCols;
    std::vector<Value> _values; 
  public:
    MatrixT(size_t nRows, size_t nCols, Value value = Value()):
      _nCols((assert(nCols > 0), nCols)), _values(nRows * nCols, value)
    { }

    size_t rows() const { return _values.size() / _nCols; }
    size_t cols() const { return _nCols; }
    
    Value* operator[](size_t i)
    {
      assert(i < rows());
      return &_values[i * _nCols];
    }
    const Value* operator[](size_t i) const
    {
      assert(i < rows());
      return &_values[i * _nCols];
    }
};

using CharTable = MatrixT<char>;

class CharTableView: public QAbstractScrollArea {
  private:
    const CharTable* pTbl = nullptr;
    int wCell;
    int hCell;

  public:
    CharTableView(QWidget* pQParent = nullptr);
    virtual ~CharTableView() = default;

    CharTableView(const CharTableView&) = delete;
    CharTableView& operator=(const CharTableView&) = delete;

    void set(CharTable* pTbl)
    {
      this->pTbl = pTbl;
      updateScrollBars();
      update();
    }

  protected:
    virtual void resizeEvent(QResizeEvent* pQEvent) override;
    virtual void paintEvent(QPaintEvent* pQEvent) override;

  private:
    void updateScrollBars();
};

void CharTableView::resizeEvent(QResizeEvent* pQEvent)
{
  updateScrollBars();
}

void CharTableView::paintEvent(QPaintEvent* pQEvent)
{
  if (!pTbl) return;
  const int xView = horizontalScrollBar()
    ? horizontalScrollBar()->value() : 0;
  const int yView = verticalScrollBar()
    ? verticalScrollBar()->value() : 0;
  const int wView = viewport()->width();
  const int hView = viewport()->height();
  const int iRow0 = yView / hCell;
  const int iCol0 = xView / wCell;
  const int iRowN = std::min((int)pTbl->rows(), (yView + hView) / hCell + 1);
  const int iColN = std::min((int)pTbl->cols(), (xView + wView) / wCell + 1);
  QPainter qPainter(viewport());
  for (int iRow = iRow0; iRow < iRowN; ++iRow) {
    const char*const row = (*pTbl)[iRow];
    const int yCell = iRow * hCell - yView;
    const int yC = yCell + hCell / 2;
    for (int iCol = iCol0; iCol < iColN; ++iCol) {
      const int xCell = iCol * wCell - xView;
      const int xC = xCell + wCell / 2;
      qPainter.drawText(
        QRect(xCell, yCell, wCell, hCell),
        Qt::AlignCenter,
        QString(QChar(row[iCol])));
    }
  }
}

CharTableView::CharTableView(QWidget* pQWidget):
  QAbstractScrollArea(pQWidget)
{
  QFontMetrics qFontMetrics(viewport()->font());
  wCell = 2 * qFontMetrics.averageCharWidth();
  hCell = qFontMetrics.height();
}

void CharTableView::updateScrollBars()
{
  const int w = (int)pTbl->cols() * wCell;
  const int h = (int)pTbl->rows() * hCell;
  const QSize sizeView = viewport()->size();
  QScrollBar*const pQScrBarH = horizontalScrollBar();
  pQScrBarH->setRange(0, w - sizeView.width());
  pQScrBarH->setPageStep(sizeView.width());
  QScrollBar*const pQScrBarV = verticalScrollBar();
  pQScrBarV->setRange(0, h - sizeView.height());
  pQScrBarV->setPageStep(sizeView.height());
}

int main(int argc, char** argv)
{
  qDebug() << "Qt Version:" << QT_VERSION_STR;
  const size_t n = 10;
  QApplication app(argc, argv);
  // setup data
  const char chars[]
    = "0123456789()[]{}/&%$!'+#?="
      "abcdefghijklmnopqrstuvwxyz"
      "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  CharTable tbl(5000, 5000);
  std::random_device rd;
  std::mt19937 rng(rd()); // seed the generator
  std::uniform_int_distribution<size_t> distr(0, std::size(chars) - 1);
  for (size_t i = 0; i < tbl.rows(); ++i) {
    char*const row = tbl[i];
    for (size_t j = 0; j < tbl.cols(); ++j) {
      row[j] = chars[distr(rng)];
    }
  }
  // setup GUI
  CharTableView qCharTableView;
  qCharTableView.setWindowTitle("Large Character Table View - 1st Attempt");
  qCharTableView.resize(640, 480);
  qCharTableView.set(&tbl);
  qCharTableView.show();
  // runtime loop
  return app.exec();
}

Output:

Snapshot of testQLargeCharTable1.exe (GIF Animation)