Image::rotate90(), Image::rotate270() の性能改善

[Raclamusi]

Image::rotate90() 、Image::rotate270() について、実行速度が従来の実装の約3倍に向上する実装を提案します。 以降、Image::rotate90() のみについて書きますが、Image::rotate270() についても同様の改善が可能です。

提案手法の概要

従来の Image::rotate90() の実装は、幅と高さを入れ替えた新しい画像オブジェクトを作成し、元の画像の画素をメモリ配置の順に新しい画像にコピーしていくというものです。 この実装では、常にコピー先の広い範囲にアクセスしており、コピー先のメモリ領域についてキャッシュをあまり活用することができておらず、実行効率の低下につながっています。 従来実装のメモリアクセスの様子を、横軸をアクセス順、縦軸をメモリアドレスとして、以下に示します。

提案実装は、ブロック化を行い、あるブロックサイズの領域ごとにコピーします。 これにより、近いアドレスの領域を参照する機会が増え、キャッシュを利用できる頻度が上がり、実行効率の向上につながります。

参考：「高速な転置」, Qiita. 参照: 2024年1月7日. [Online]. Available at: https://qiita.com/masayasviel/items/6763d01bf58975d2b444

提案実装のメモリアクセスの様子を、同様に以下に示します。

提案手法の実装と測定用コード

提案手法の実装と測定用コードを以下の gist に示します。 このコード内の my::rotate90() が提案手法を実装したものです。

https://gist.github.com/Raclamusi/9443c1533bfd2f45a73678d9b6b47d46?ts=4

測定結果

従来手法と提案手法それぞれの画像のバイトサイズと実行時間の関係を以下のグラフに示します。

実行時間が従来の1/3程度に向上しました。

計測環境

項目	環境
プロセッサ	Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz 2.11 GHz
RAM	8.00 GB
OS	Windows 11 Home 22H2
IDE	Microsoft Visual Studio Community 2022 (64 ビット) 17.8.3
ビルド	Release x64

[Reputeless]

興味深いです。調査します。

[Reputeless]

効果を確認できたので進めてください。

    for (size_t b = 0; b < m_width; b += BlockSize)
    {
        const size_t blockEnd = Min<size_t>((b + BlockSize), m_width);
        Color* pDstLine = (pDstBase + b * m_height);

        for (size_t y = 0; y < m_height; ++y)
        {
            const Color* pSrc = (pData + y * m_width + b);
            const size_t dstX = (m_height - y - 1);
            Color* pDst = (pDstLine + dstX);
            const size_t w = (blockEnd - b);

            for (size_t x = 0; x < w; ++x)
            {
                *pDst = *pSrc;
                pDst += m_height;
                ++pSrc;
            }
        }
    }

のように operator[] やメンバ関数の呼び出しを回避したり、コードを単純化したりすることで性能を向上できます。とくに MSVC Debug ビルド時の性能を向上できます。

ベンチマークプログラム例

    Image imageSmall{ U"example/windmill.png" };
    Image imageLarge{ U"example/bay.jpg" };
    constexpr int32 N = 32;

    for (int32 k = 0; k < 3; ++k)
    {
        {
            MicrosecClock clock;
            for (int32 i = 0; i < N; ++i)
            {
                test::Rotate90_Old(imageSmall);
            }
            clock.print();
        }

        {
            MicrosecClock clock;
            for (int32 i = 0; i < N; ++i)
            {
                test::Rotate90_New(imageSmall);
            }
            clock.print();
        }

        {
            MicrosecClock clock;
            for (int32 i = 0; i < N; ++i)
            {
                test::Rotate90_New2(imageSmall);
            }
            clock.print();
        }

        {
            MillisecClock clock;
            for (int32 i = 0; i < N; ++i)
            {
                test::Rotate90_Old(imageLarge);
            }
            clock.print();
        }

        {
            MillisecClock clock;
            for (int32 i = 0; i < N; ++i)
            {
                test::Rotate90_New(imageLarge);
            }
            clock.print();
        }

        {
            MillisecClock clock;
            for (int32 i = 0; i < N; ++i)
            {
                test::Rotate90_New2(imageLarge);
            }
            clock.print();
        }

        Print << U"---";
    }

    while (System::Update())
    {

    }

[Reputeless]

width == height のときに in-place で転置する実装も調査したいですね。

[Raclamusi]

メンバ関数呼び出しの回避について、提案コードを修正しました。

https://gist.github.com/Raclamusi/9443c1533bfd2f45a73678d9b6b47d46/revisions#diff-ff9db3cb6025e343dacac7fe1b565394e85d2b614be4ab7b7fedb99d8e8b762d

画像が正方形のときの in-place 転置は調査中です。

[Raclamusi]

正方形画像に対する in-place 実装を少し調べてみましたが、特に高速な実装を紹介しているものが見つからなかったので、自分で考えて実装しました。 4画素を取り出して入れ替えていく実装を、ブロック化によって高速化したものです。 実行時間は元の提案実装の1/2程度に向上しました。

Revisions: https://gist.github.com/Raclamusi/9443c1533bfd2f45a73678d9b6b47d46/revisions?ts=4#diff-ff9db3cb6025e343dacac7fe1b565394e85d2b614be4ab7b7fedb99d8e8b762d

[Raclamusi]

Debug 実行だと in-place 実装の恩恵が劇的になりますね。

[Reputeless]

調査ありがとうございます。良さそうですね！確認します。