Help us understand the problem. What is going on with this article?

allocatable配列のsizeとcapacityについて(内容訂正中)

お詫び (2019/12/06 追記)

Fortranアドベントカレンダー2019/12/03として本記事を投稿させていただきましたが、検証結果に誤りがあることがわかりました。

真っ先に記事自体を削除することを考えましたが、
間違った内容の記事であっても一定の数の方々の目にすでに触れてしまったわけなので、
誤りと認めずにこっそり黙って削除するのではなく、どこまで正しくどこまで正しいのかしっかり検証した上で、事実のみを述べた記事へと更新する予定です。

大変申し訳ありませんでした。

気になったこと

可変長配列の実装といえば、C++のstd::vectorが第一に挙げられるでしょう。Fortranのallocatableも、概ねstd::vectorのような仕様になっているのだろう勝手に想像して今まで使ってきたけれど、実際のメモリ確保のタイミングはどうなっているのか?気になったので調べてみました。

以下、実行環境について、特に明示しない場合
gnu(gfortran 7.4.0 , g++ 7.4.0) の結果とします。

前提知識 std::vectorについて

C++ 日本語リファレンスより引用
https://cpprefjp.github.io/reference/vector/vector.html

vectorはシーケンスコンテナの一種で、各要素は線形に、順序を保ったまま格納される。

vectorコンテナは可変長配列として実装される。通常の(new []で確保した)配列と同じように、vectorの各要素は連続して配置されるため、イテレータだけでなく添字による要素のランダムアクセスも高速である。

配列と違い、ストレージはvector自体が管理するため、自動的に領域の拡張が行われる。

vectorは次の点で優れている。

  • 各要素への添字アクセス(定数時間)
  • 全要素の両方向の走査(線形時間)
  • 末尾への要素の追加・削除(償却定数時間)

通常の配列の特徴に、自動で領域拡張する機能がついたものですから、Fortran2003以降のallocatableの仕様と同じです。

今回のテーマとなるのが、末尾への要素の追加・削除(償却定数時間) という記述です。
std::vectorにはsizecapacityという2つの大きさがあります。sizeとはプログラムから見た要素数、capacityとは、メモリ上に予約された容量です。
capacityは常にsize以上となるよう、大目にとってあります。
sizeを増やしていった場合、capacityを超えなければ予約しておいたアドレスに書き込むだけなので定数時間で動作します。capacityを越えようとした場合、新しく別のアドレスにメモリを予約したのち、すべてのデータを新しいアドレスへとコピーするので線形時間で動作します。capacityの更新するタイミングが適切に調整されて、平均的には定数時間で動作する状態を指して、償却定数時間と呼びます。

以下のコードは、sizeを0からひとつずつ増やしていき、capacityが変化したときのみ出力することで、
sizeに対するcapacityの変化を確認するコードです。
一般的なC++の実装では、capacityが2^nで増加していくことが確認できます。

#include <cstdint>
#include <vector>
#include <iostream>

typedef std::vector<int32_t> Vector;

int main(int argc, char** argv) {

  Vector          vec(0);                                     // 空のvectorの
  auto capacity = vec.capacity();

  for(auto i = Vector::size_type(1); i <= 10000; i++) {
    vec.push_back(0);                                         // 末尾に追加
    if (capacity != vec.capacity()) {                         // capacityが変化したら
      std::cout << (capacity = vec.capacity()) << std::endl;  // 出力する
    }
  }
}
$ ./cpp.out
1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384

Fortranでcapacityを知るために...

allocatableで現在のcapacityを知る標準化された方法はないので、capacityが更新されたら、配列の先頭のアドレスが変化するという仮定をおいて、以下のコードで擬似的にcapacityの変化を追跡することとします。

program main

    use iso_fortran_env
    use iso_c_binding

    implicit none

    integer(int32),target,allocatable :: vec(:)
    integer(int32),pointer            :: cursor => NULL(), temp_cursor
    integer :: i

    allocate(vec(0))

    do i = 1,10000
        vec = [vec(:), 0]
        temp_cursor => vec(1)
        if (.not. associated(temp_cursor, cursor)) then
            cursor => temp_cursor
            print *, i
        end if
    end do
end program main
$ ./fortran.out
           1
           7
          11
          15
          19
          23
          27
          31
          35
          39
          43
          47
          51
          55
          59
          63
          67
          71
          75
          79
          83
          87
          91
          95
          99
         103
         107
         111
         115
         119
         123
         127
         131
         135
         139
         143
         147
         151
         155
         159
         163
         167
         171
         175
         179
         183
         187
         191
         195
         199
         203
         207
         211
         215
         219
         223
         227
         231
         235
         239
         243
         247
         251
         255
         259
         263
         527
        1059
        2119
        4243
        8487

謎の数列が得られました!!!

概ね以下のような振る舞いをしていることがわかります。

  • 1KiB程度(要素数だと256個ほど)までは線形に
  • 1KiBを超えたところから2^nで増加

Fortranの結果はbytesize(配列全体のバイト数)を参照しているように思えてならないので、色々な数値型を試して、パターンを分類してみました。

パターン
1byte int8
2byte int16
4byte int32 real32
8byte int64 real64
16byte int128 real128

予想通り、要素数に対する容量の変化パターンが、要素のバイト数に応じて変わっていることがわかりました。
このことに注目して、要素数ではなく、配列全体のバイト数と容量の関係をプロットしてみます。

bsize_vs_capacity.png

1024byteから片対数でプロットした恣意的なグラフですが、1024byteを境に、指数的な変化へと切り替わっていることがわかると思います。

注意点

上に述べたbytesizecapacityの関係は、かなり環境に依存することもわかりました。

  • gfortranのバージョンが同じでも、CPUが違う環境で動かすと異なる結果となります。(アーキテクチャ依存)
  • 同じCPUでもintel fortranを用いた場合とgfortranの場合の結果は異なります。(コンパイラ依存)

一方で、同一CPUでgfortranのバージョン間の結果を比較をすると同じ結果であることもわかりました。

まとめ

  • allocatable配列にも、std::vectorにおけるcapacityの概念が存在する。
  • allocatable配列のcapacityを直接知る方法は存在しないが、先頭アドレスの変化を追跡することで擬似的に確認可能。
  • allocatable配列のcapacityは、sizeではなく、bytesizeを基準に定まっているらしい。
  • bytesizecapacityの関係は、単純な2^nとはなっていないことが多い。

実行時に延長をしているallocatableについて、最小と最大の間にcapacity変更が行われるタイミングがどれほどあるか確認しておくと、賢くallocatableを利用できるかもしれません。

ローカルと本番環境でアーキテクチャ/コンパイラが違う場合、capacity変更タイミングが違うことにも注意が必要です。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away