CV_8UC3 to rawをチューニングしたら、実行命令数が1/22になった(前編)

TL;DR
=====
- Wayland用のCV_8UC3 to rawにチューニングの余地があった
- 基本的なC++レベルでのチューニングだけでも、実行命令数を半減
 
| Code                    | Ir        |
| -----------------------:|:----------|
| OpenCV 4.9.0            | 5,911,406 |
| SIMD無チューニング       | 2,453,868 |

はじめに
========
LinuxのGUIといえば **「X Window Systm!!」** だったのは相当過去の話である。

例えば、Ubuntu　21.04でも、Debian 10(2019/7)でも、Fedoraでも、皆 **[Wayland](https://wayland.freedesktop.org/)** をデフォルトセッションとしている。

さて、そんな素敵なWaylandだが、OpenCVのhighgui backendとしても実装されている。

https://twitter.com/dandelion1124/status/1537052545008701442

しかし、パフォーマンスチューニング中毒としては、MatからRAWに変換する箇所へ手を入れたくなった。ということで、その作業メモである。

パフォーマンス計測用のテストコード
===============================
今回のテストコードは以下。なお、使用しているopencv-logo.pngは、opencv/doc以下に格納されている。

```cpp
// g++ main.cpp -o a.out -I /usr/local/include/opencv4 -lopencv_core -lopencv_highgui -lopencv_imgcodecs
#include <opencv2/core.hpp>
#include <opencv2/highgui.hpp>
#include <opencv2/imgcodecs.hpp>
#include <iostream>
#include <string>

int main(int argc, char *argv[])
{
  std::cout << "cv::currentUIFramework() returns " << cv::currentUIFramework() << std::endl;

  cv::Mat src;
  src = cv::imread("opencv-logo.png");

  cv::namedWindow("src");
  cv::imshow("src", src);
  (void)cv::waitKey(1000);

  return 0;
}
```

```plaintext
$ pnginfo opencv-logo.png
opencv-logo.png...
  Image Width: 599 Image Length: 556
  Bitdepth (Bits/Sample): 8
  Channels (Samples/Pixel): 4
  Pixel depth (Pixel Depth): 32
  Colour Type (Photometric Interpretation): RGB with alpha channel
  Image filter: Single row per byte filter
  Interlacing: No interlacing
  Compression Scheme: Deflate method 8, 32k window
  Resolution: 11339, 11339 (pixels per meter)
  FillOrder: msb-to-lsb
  Byte Order: Network (Big Endian)
  Number of text strings: 0
```

パフォーマンス測定用の設定
========================
さて、OpenCVのパフォーマンス測定するときには、cmakeオプションで以下を指定すると、「どの行」がボトルネックなのかを確認できる。なお、測定するときはちゃんとCMAKE_BUILD_TYPEがReleaseであることもちゃんと確認しましょう

```plaintext
 CMAKE_BUILD_TYPE                 Release
 BUILD_WITH_DEBUG_INFO            ON
```

オリジナルコード
===============
最初に、現状のOpenCV 4.9.0相当の実装を確認していこう。

https://github.com/opencv/opencv/blob/dad8af6b17f8e60d7b95a1203a1b4d22f56574cf/modules/highgui/src/window_wayland.cpp#L88-L102

```cpp
static void draw_xrgb8888(void *d, uint8_t a, uint8_t r, uint8_t g, uint8_t b) {
    *((uint32_t *) d) = ((a << 24) | (r << 16) | (g << 8) | b);
}


static void write_mat_to_xrgb8888(cv::Mat const &img, void *data) {
    CV_Assert(data != nullptr);
    CV_Assert(img.isContinuous());


    for (int y = 0; y < img.rows; y++) {
        for (int x = 0; x < img.cols; x++) {
            auto p = img.at<cv::Vec3b>(y, x);
            draw_xrgb8888((char *) data + (y * img.cols + x) * 4, 0x00, p[2], p[1], p[0]);
        }
    }
}
```

この状況で、パフォーマンスを測定してみると・・・

```
valgrind --tool=callgrind ./a.out
==19526== Callgrind, a call-graph generating cache profiler
==19526== Copyright (C) 2002-2017, and GNU GPL'd, by Josef Weidendorfer et al.
==19526== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==19526== Command: ./a.out
==19526==
==19526== For interactive control, run 'callgrind_control -h'.
cv::currentUIFramework() returns WAYLAND
==19526==
==19526== Events    : Ir
==19526== Collected : 127867107
==19526==
==19526== I   refs:      127,867,107

$ callgrind_annotate callgrind.out.19526 | grep 8888 | head -1
 5,911,406 ( 4.62%)  /home/kmtr/work/opencv4/modules/highgui/src/window_wayland.cpp:write_mat_to_xrgb8888(cv::Mat const&, void*) [/usr/local/lib/libopencv_highgui.so.4.9.0]
 
```

kcachegrindで、どの行がヤバいのかを見ると・・・
ここで、左側の数字（Ir）とは、`The I refs number is short for "Instruction cache references", which is equivalent to "instructions executed". ` とのことなので、ざっくり言うと実行命令数(≠ 実行サイクル数)になる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/89434/a505623d-9b9c-9a17-07dd-3fb078cd05b7.png)

SIMDを使わないレベルでのチューニング
==================================
さて、この結果を見るといくつかチューニングポイントがある。

まずは、SIMD実装なして、チューニングをしていく。

(1) draw_xrgb8888() 内のshift演算も、Or演算も、aも、全部不要
----------------------------------------------------------
まずは、実際にデータをかき込んでいるこの draw_xrgb8888 を検証していく。

```cpp
static void draw_xrgb8888(void *d, uint8_t a, uint8_t r, uint8_t g, uint8_t b) {
    *((uint32_t *) d) = ((a << 24) | (r << 16) | (g << 8) | b);
}
```

WaylandのXRGB8888というのは、Little Endianでデータを格納する仕様になっている。 ( https://wayland.freedesktop.org/docs/html/apa.html#protocol-spec-wl_display )

> argb8888
>   0 - 32-bit ARGB format, [31:0] A:R:G:B 8:8:8:8 little endian
> xrgb8888
>   1 - 32-bit RGB format, [31:0] x:R:G:B 8:8:8:8 little endian

つまり、 [B:8][G:8][R:8][X:8] で格納する必要がある。ただそのためだけに、shift演算やOR演算を駆使しなければならない理由はない。

さらに言うと、現状のコードだと、PowerPCのようなbig endianな環境だと、
[X:8][R:8][G:8][B:8] 、つまり想定と逆順にデータが格納される（はず）。

また、xrgbであれば、xは何でもいい（なので、RGB formatである)ので、aに関する処理自体ムダである。これを踏まえると、下記で十分という事になる。

```cpp
static void draw_xrgb8888(const uint8_t* d, uint8_t r, uint8_t g, uint8_t b) {
    d[0] = b;
    d[1] = g;
    d[2] = r;
//  d[3] = any
}
```

(2) srcアドレスの計算は無駄
---------------------------

次はデータコピーするSRC側（BGR配列）を見ていこう。これもなかなか…

```cpp
    CV_Assert(img.isContinuous());

    for (int y = 0; y < img.rows; y++) {
        for (int x = 0; x < img.cols; x++) {
            auto p = img.at<cv::Vec3b>(y, x);
```
 
ここで出てきた、`isContinuous()`というのは、Mat型のimgにおける、データ配列の並びが「連続」なのかどうかを判定するものである。例えば、ROI(Rect of interesting)を使って、画像データの一部を切り出した別Matを作っている場合などは、この連続性が保証できない場合もある。

それにもかかわらず、だ。なぜ、pを画素単位で毎回計算する必要がある(# ﾟДﾟ)ﾑｯｷｰ
ということで、`img.ptr(y)`で行ごとに行先頭のアドレスを算出し、次の画素になるときに加算した方が早い。

```cpp
    for (int y = 0; y < img.rows; y++) {
        const uint8_t* p = (const uint8_t*) img.ptr(y);
        for (int x = 0; x < img.cols; x++, p += 3) {
```

おおっと、これで終わりではないのですよ。

さて、先ほど、`isContinuous()`がtrueである場合には、全部のデータが連続している、と言いました。という事は、この「行先頭のアドレス計算」自体も省けるってことでヤンス。

```cpp
    int img_rows = img.rows;
    int img_cols = img.cols;

    if(img.isContinuous()){
        img_cols = img_rows * img_cols;
        img_rows = 1;
    }

    for (int y = 0; y < img_rows; y++) {
        const uint8_t* p = (const uint8_t*) img.ptr(y);
        for (int x = 0; x < img_cols; x++, p += 3) {
```

(3) 出力アドレス計算も無駄
-------------------------

さて、出力側のアドレス計算も見ていこう。ここもざっくり削れる。

```cpp
static void write_mat_to_xrgb8888(cv::Mat const &img, void *data) {
    CV_Assert(data != nullptr);

    for (int y = 0; y < img.rows; y++) {
        for (int x = 0; x < img.cols; x++) {

            draw_xrgb8888((char *) data + (y * img.cols + x) * 4, 0x00, p[2], p[1], p[0]);
        }
    }
}
```

えーっと、このdataというのが先頭アドレスなわけですが・・・

ぶっちゃけ、このoffset計算要りませんね。data内の画素は連続しているのだから、わざわざ掛け算とかして計算しなおす必要は全くないでございます。

```cpp
static void write_mat_to_xrgb8888(cv::Mat const &img, void *data) {
    CV_Assert(data != nullptr);
    uint8_t *dst = (uint8_t*) data;

    for (int y = 0; y < img.rows; y++) {
        for (int x = 0; x < img.cols; x++, dst+=4) {

            draw_xrgb8888(dst, 0x00, p[2], p[1], p[0]);
        }
    }
}
```

ここまでのチューニング結果
-------------------------

ここまでの結果をまとめると、コードは以下のように修正される。

```cpp
static void write_mat_to_xrgb8888(cv::Mat const &img, void *data) {
    CV_CheckTrue(data != nullptr, "data must not be nullptr.");
    CV_CheckType(img.type(), img.type() == CV_8UC3, "Only 8UC3 images are supported.");

    int img_rows = img.rows;
    int img_cols = img.cols;
    uint8_t *dst = (uint8_t*) data;

    // to reduce calling img.ptr()
    if(img.isContinuous())
    {
        img_cols *= img_rows;
        img_rows  = 1;
    }

    // Convert from [b8:g8:r8] to [b8:g8:r8:x8]
    for (int y = 0; y < img_rows; y++)
    {
        const uint8_t* src = (uint8_t*)img.ptr(y);
        for (int x = 0; x < img_cols; x++, src+=3, dst+=4)
        {
            dst[0] = src[0];
            dst[1] = src[1];
            dst[2] = src[2];
        }
    }
}
```

結果は、2,453,868 Irとなったので、おおよそ実行命令数は半減している。

```bash
valgrind --tool=callgrind ./a.out
==24657== Callgrind, a call-graph generating cache profiler
==24657== Copyright (C) 2002-2017, and GNU GPL`d, by Josef Weidendorfer et al.
==24657== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==24657== Command: ./a.out
==24657==
==24657== For interactive control, run 'callgrind_control -h'.
cv::currentUIFramework() returns WAYLAND
==24657==
==24657== Events    : Ir
==24657== Collected : 124629099
==24657==
==24657== I   refs:      124,629,099
kmtr@kmtr-VMware-Virtual-Platform:~/work/build4-main/temp$  callgrind_annotate callgrind.out.24657 | grep 8888 | head -1
 2,453,868 ( 1.97%)  /home/kmtr/work/opencv4/modules/highgui/src/window_wayland.cpp:write_mat_to_xrgb8888(cv::Mat const&, void*) [/usr/local/lib/libopencv_highgui.so.4.9.0]
```

行単位のコストを見ると「なんでやねん！」と突っ込みたいところだが、そこをぐーっと抑えて。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/89434/05c33afc-faaf-a81f-6e0b-dfbafc8efdd7.png)

前半のまとめ
============

| Code                    | Ir        |
| -----------------------:|:----------|
| OpenCV 4.9.0            | 5,911,406 |
| SIMD無チューニング       | 2,453,868 |

いやいや、まだだ。まだこんなもんじゃない！！ということで、後半はSIMD対応で更にガリガリ実行命令数を減らしていくぅ！！！

後半　⇒　https://qiita.com/hon_no_mushi/items/72bb812e3a7901739cb9