🦁

数値計算ライブラリにおいて配列を表現するクラスの実装とはどうあるべきかを悩んだ末のポエム (1次元)

2022/06/13に公開約2,300字5件のコメント

はじめに

この記事の答えは私自身見つかっていません.是非コメント欄にコメントください..

数値計算や機械学習のコードを書いている皆さん,どうもこんにちは.
今日は私が3日悩んでいるポエムのような話をしようと思います.

この記事では前提としてC++で開発することを考えますが,RustとかJuliaでも同じだと思います.

また,ちょっとわかりにくくて申し訳ないのですが,この記事では配列とarrayという言葉を分けて,

  • array(アレイ) : ベクトルとの対比に用いる,掛けたりするとアダマール積になるもの
  • 配列 : メモリに連続に格納された領域のことを指す.ベクトルなのかテンソルなのかアレイなのかは問わない

と定義することにします.

プロトタイプ実装もせず,頭の中でしか考えてないです.

なぜarrayクラスを再実装しないといけないのか

理由

さっそくですが,言語はともかくとして数値計算ライブラリにおいて,

x = {1, 2, 3};

と書いてあったとき,この x とはなんでしょうか?

一次元の配列であることは間違いないですが,実際には,

  • 配列 (array)
  • ベクトル (vector)
  • テンソル (tensor)

という可能性があります.

人によってどれを望んでいるかは異なるし,人類はこの問題に対する答えを残念ながら定義できていません.これらの違いによって,たとえば * という演算が内積なのかアダマール積(要素ごとの積)なのかが異なります.

どのように定義するかはさておき,こういう問題がある以上,数値計算ライブラリの開発者は自分で何らかのクラスを実装する必要が出てきます.

この記事で扱う適当な配列クラス

本記事では,このようなクラスをC++実装するときにどのような実装にすべきなのかを考えたいと思います.

C++であれば,std::vector, std::array, std::valarray などがありますが,それらをそのまま使えばいい例を出しても面白くないので,
ここでは一例として疎な配列のクラスを定義したいと思います.

疎な配列とは,例えば以下のような値がほとんどゼロの配列のことです.

{0, 0, 1, 0, 2, 0, 0, 3}

こういった配列の場合,ゼロの要素を保持しておく意味がないので,以下のようにゼロ以外のみで構成された配列とインデックスの配列だけ持てばよいです.

value = {1, 2, 3}
index = {2, 4, 7}

このようなクラスを自分で定義するときの実装について考えます.

実装として考えられるもの

当然ですが,こういう関数を1から実装するのは大変です.
先に述べたようにC++にも std::vector, std::array, std::valarray などがあり,これらをそのまま使えれば標準ライブラリの沢山の機能が使えます.

一方でそのまま使えないから自分で作っているわけで,なんとか拡張しないといけません.
5つほど考えたので,以下に書いていきますが,1.と4.のどちらかな気がしています.

どちらが正解なのか,どういうメリット・デメリットがあるのか,深く考えたことがある人,コメントください...

1. 我が道を行き,自分で全部書く

ポインタなりスマートポインタをメンバ変数として持って,全部自分で書きます.
力こそパワーです.何の問題もありません.自分で書くのだから書いた通りの性能が出ます.

xtensorとかEigenとかはこれで実装している気がします (全部見きれてない).

開発が滞ると陳腐化していきます.工数を無視してこれを管理し続けられるなら苦労しません

2. 自分で全部書くが,std::*へのキャストオペレータなりconvert関数を定義する

上手くディープコピーが発生しないようにカスタムアロケータを定義して中身だけぐるぐる使いまわします.

やめろ

3. publicなメンバ変数としてstd::*のクラスをもつ

中身はstd::vector等だから抜き出すなり機能を使うなり勝手にしてねってことです.

今回の例だと,valueだけresizeされたりすると死にます.

やめろ

4. privateなメンバ変数としてstd::*のクラスをもつ

ユーザに見せたい関数だけラッパー関数を定義して見せます.それなりに工数はかかりますが,1.ほどじゃないはずです.
ただ,普通に実装するとCポインタからstd::vectorへのディープコピーが発生するのでシャローコピーをするカスタムアロケータが必須でしょうか?

3.もそうですが,gccやclangの実装の違いに苦しんだりしないかなあ.

これが1.とくらべてどういう問題が起きそうなのか想像力が追いついていません.

あとstd::*頼みな部分が強くなるので,FFIが大変だったりする?
結局クラスにした時点でCに戻さないといけないんだから手間は一緒か?

5. std::*のクラスを継承する

デストラクタとアップ/ダウンキャスト問題と戦うことになります (protected継承すればいい気はする).
一見便利に見えますが,結局意味の違う関数は直さないといけないので4.とくらべて実装量が変わらない上,C++のバージョンアップに付き合う必要があります.

多分良くない気がするんですけど,そんなことない?

GitHubで編集を提案

Discussion

1 か 4 だとは思います。

ただ,普通に実装するとCポインタからstd::vectorへのディープコピーが発生するのでシャローコピーをするカスタムアロケータが必須でしょうか?

内部にデータをコピーしてしまった方が安全だとは思いますが、サイズが大きくてないし速度特化するためにそのコピーコストすら受け入れられないのであれば、内部にデータを持たない view の併用が良いのではないでしょうか。

もし、STLの利用の有無を現時点ですぐに決められないのであれば、数学的なメソッドを実装するクラス(ベクトル・行列 etc) に直接STLをもたせるのではなく、その内部にデータを保持するクラスを作ってそこにSTLを持たせてはどうでしょうか?

ちょっと用途が異なるので参考になるかはわかりませんが、私は同様にデータ保持クラスを作っていたのですが、 view に対応する時に結局 std::vector からポインタに改修しました。


https://gitlab.com/ymd_h/cpprb/-/blob/0e37e8deef95156c5b0ad8e5bce1577f612e90fa/cpprb/ReplayBuffer.hh#L30-L72

改修

https://gitlab.com/ymd_h/cpprb/-/commit/5b7b47baed7610818ea1a95d627c8078bf6075f2

ありがとうございます

サイズが大きくてないし速度特化するためにそのコピーコストすら受け入れられない

これはYESです.
メモリが足りないから計算機を複数繋ごうと言ってスパコンみたいなものがある業界なので..

んー...やっぱりviewとかやろうとするとポインタに改修したくなりますよね...
内部にデータを保持するクラスを作るのはいい考えな気がします.ちょっとそれで始めてみようかな...

RustとかJuliaでも同じだと思います.

記事をざっと斜め読みした限り、Julia は全然事情が違うと感じましたので、その点だけ少しだけ紹介します。

Julia は既に「1. 我が道を行き,自分で全部書く」の方針で実装された Array 型(AbstractArray の subtype で concrete type)が存在します。Julia で「配列」と言えばこれで、1次元配列ならば Vector 扱い(リスト構造ではありませんが要素の追加削除挿入等も可能)、2次元ならば Matrix 扱い(*は行列積、.*が要素ごとの積(アダマール積)と区別もされている)、3次元以上の多次元配列(≒テンソル?)も利用できます。
標準ライブラリ SparseArrays も備えていて using SparseArrays すると SparseVectorSparseMatrixCSC を利用できます。SparseVector <: AbstractVector <: AbstractArraySparseMatrixCSC <: AbstractMatrix <: AbstractArray です。

あと A isa AbstractMatrixx isa AbstractVector に対して A * x は行列とベクトル(列ベクトル)の積(結果はベクトル(列ベクトル))とか、ベクトルの内積は dot(v1, v2) もしくは v1 ⋅ v2はU+22C5のUnicode演算子)(dot()は要 using LinearAlgebra)とか色々ありますが、それだけで記事が一つ書けるボリュームになってしまうので、詳しくは公式マニュアルを見てください。

https://docs.julialang.org/en/v1/base/arrays/
https://docs.julialang.org/en/v1/stdlib/SparseArrays/
https://docs.julialang.org/en/v1/stdlib/LinearAlgebra/

補足:「自分で全部書く」と書きましたが、行列演算等は BLASS や LAPACK を裏で使っています。

ありがとうございます.
そしてJuliaの配列について,ありがとうございます.細かくは知らなかったので,助かります.

そしてちょっとわかりにくくてすみません.
私は結構特殊な型を扱う必要があって,どんな言語でも独自型ってどうしてもいるよね.みたいな軽い気持ちで書きました.
一例に実装の少ないSparse vectorを挙げたのですが,例が悪かったです.すみません.

こちらこそ昼休みにふと見かけた記事に「Juliaはこうだよ」ととにかくお伝えしようとだけ考えてあまり記事をきちんと読まずに的外れなコメントをしてしまったかもしれません、スミマセンでした。

ということでさらに補足すると、Juliaでは(標準の)配列と互換性のあるオレオレ配列型を定義でき、他の配列型と同じインターフェースを利用できます(*が行列積として使えるとか標準の配列に対して動作する関数を動作させることができるとか)。その一例が SparseArrays の提供する各型です。
その方法は「既存の関数にオリジナル型のメソッドを生やす」というような感覚になります。Julia は関数を型シグニチャ(引数の組合せ)の違いで多重定義することでアドホックなポリモーフィズムが享受され(なので「メソッド」は「関数」に属するものという考え方になっています)、それを利用して既存の型との演算も可能となります(内部を自分で実装すれば)。これは配列に限った話ではなく Julia の型と関数の普遍的な仕様です。
つまり言いたかったことは「独自の型を作って目的を達成することは Julia では普通にできるし、それが既存のAPI利用を妨げない」、つまり「(Rust については詳しくないのですが少なくとも)C++とは事情が全然違う」ということでした。

ログインするとコメントできます