メモリ配置が密な動的可変長配列の作成方法について

今回は前回の高速化の記事に関係した、
密な動的可変長配列の作成方法について紹介する.


前回のリニアな配列を作成して面倒なアクセスを行わずとも、
通常の多次元配列のようにアクセス出来る方法を紹介する。

固定長配列のコンパイル時による最適化について

C/C++では固定長の多次元配列はコンパイルの時点で最適化され、
メモリ上に密に配置されるので、特殊な事をしなくてもCPUキャッシュが存分に活用される。


おそらく以下のような固定長の多次元配列は誰でも作成した事があるはず。

const int WIDTH = 512; // 画像幅
const int HEIGHT = 256; // 画像高
// 512*256の8bitグレイスケール画像の読込配列用
unsigned char imgData[HEIGHT][WIDTH];

このようにソースコード中で固定な配列と分かる場合は、
コンパイラが最適化して配置してくれるため、以下のようにメモリにデータが密に配置される。


@ 先頭ポインタ
■（WIDTH(512)サイズ分のメモリ領域）
□（確保されていないメモリ領域）
□□□@■■...■■■□□□ HEIGHT(256)個分の■が密に確保されている


それでは、動的に配列を作成する場合はどうなのだろうか？

単純な動的可変長配列の作成によるメモリ配置について

まず一般的なc++での動的な多次元配列の作り方を以下に示す。(constで動的確保とか意味ねぇよ、というツッコミはやめてね)

const int WIDTH = 512; // 画像幅
const int HEIGHT = 256; // 画像高
// 512*256の8bitグレイスケール画像の読込配列用
unsigned char** imgData;
imgData = new unsigned char*[HEIGHT];
for(int y = 0; y < HEIGHT; ++y)
{
    imgData[y] = new unsigned char[WIDTH];
}

前回の記事でも触れたが、このメモリの確保の仕方では密なデータの配置がされない。


高速化の必要がない場合は上記のような方法で問題ないが、
膨大なデータを解析する必要がある場合は極力リニアな確保を心がけるべきだろう。

密な動的可変長配列の作成方法

以下の様なメモリ確保を行えば、c++ではメモリ上にデータを密に配置することが可能。

const int WIDTH = 512; // 画像幅
const int HEIGHT = 256; // 画像高
// 512*256の8bitグレイスケール画像の読込配列用
unsigned char** imgData;
// 一次元目のメモリを確保（ジャンプ用のポインタ）
imgData = new unsigned char*[HEIGHT];
// 必要な全サイズのメモリを確保する
imgData[0] = new unsigned char[HEIGHT * WIDTH];
// 二次元目の先頭ポインタを対応するメモリアドレスに設定する
for(int y = 1; y < HEIGHT; ++y)
{
    imgData[y] = imgData[0] + (y * WIDTH);
}

画像処理では画素値のデータ配列は密に作成して高速化するのが一般的で、
OpenCVなどのライブラリでも同様のメモリ確保が行われている。


高速化を意識するなら知っておいても良い知識のひとつかも？