C++ ときどき ごはん、わりとてぃーぶれいく☆

USAGI.NETWORKのなかのひとのブログ。主にC++。

Dart の List<T> とメモリー消費量

Dart には言語仕様書で組み込み型として明記される List ジェネリクス型があります。言語仕様書§10.6によれば「いわゆるarrayっぽいそういうの」だそうで。

ちょっと試しに、10M個のintを放り込んでみましょう。

main(){
  final int K = 1024;
  final int M = K * K;
  final int count_max = 10 * M;
  var a = new List<int>(count_max);
  for(int n = 0; n < count_max; ++n)
    a[n] = n;
  num s = 0;
  for(var v in a)
    s += v;
  print(s);
}

こんな単純なコードをtimeってみると、

% time dart test.dart
54975576145920
        Command being timed: "dart test.dart"
        User time (seconds): 4.02
        System time (seconds): 0.04
        Percent of CPU this job got: 98%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 0:04.11
        Average shared text size (kbytes): 0
        Average unshared data size (kbytes): 0
        Average stack size (kbytes): 0
        Average total size (kbytes): 0
        <b>Maximum resident set size (kbytes): 78876</b>
        Average resident set size (kbytes): 0
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 19849
        Voluntary context switches: 1
        Involuntary context switches: 59
        Swaps: 0
        File system inputs: 0
        File system outputs: 0
        Socket messages sent: 0
        Socket messages received: 0
        Signals delivered: 0
        Page size (bytes): 4096
        Exit status: 0

と、云う訳で int 型1つあたり算術平均すると最大でも7.7[byte]くらいしか使ってないという事になりますね。実はDartのint型は任意精度型なので、放り込む値の桁数が多くなるほどメモリを消費します。そこで、放り込む値を double 型、量を100M個にしてみると、

% time dart test.dart
5497558086451200
        User time (seconds): 53.45
        <b>Maximum resident set size (kbytes): 78876</b>

だそうで、 double 型1つあたり最大でも43[bytes]・・・おやおや。 Dart の double は IEEE754 Binary64 と仕様書に明記されていますから、単純なarrayだとしたら1つ辺り8[bytes]のはず。ちなみに量が10M個だと7872[KB]、1つあたり7.7[bytes]・・・はてさて。

nbodyのベンチマークをDartにも移植しようと思い、言語仕様書をそれなりにきっちりと読んだりしているついでtimeって見たのですが、Listの中身、どうなっているんでしょうね…。100M個の時に大量消費しているのは管理情報だとか、或いはC++のstd::vectorが拡張される様な挙動を何故か上記のソース記述でもしてしまっているとかが重なったり、実は単純なarrayじゃないんですとかあり得るだろうけれど、10M個の時に消費量が少なすぎるのは一体…。

とりあえず Dart のソースコードにヒントは無いかと思い覗いてみると、こんなものが:

もしかして Dart の List は Java の ArrayList を内部的に使ってるだけ？（少なくとも Dart VM が .dart をコンパイルする最初の段階では）

Dart はソースまではまだまったく追いかけて居ないし、どういう構成になっているのかも把握していません。上記もちらっと検索したらJavaVMまるっと使ってそうなファイルがあったのでそうなのかなーと思った程度。間違い、勘違いなどあったら教えて下さい☆ミ