Java の配列の長さ

プログラミング

問

Java の配列は 231-1 より長いものを作れないというのは、知られていないが案外深刻な問題である。こんなに要素が多いものは作らないと思うかもしれないが、内部で配列を使っているものは少なくない。

  • String のような文字列、
  • ArrayList あるいは HashMap のようなコレクション

など、これらには要素数に限界があるということであり、例えば、以下のような影響が考えられる。

  1. 最近 BigData が流行りだが、たいていのデータはメモリに載るサイズである。例えば、Wikipedia 英語版ですら 40GB あまりの文字列であり、最近の少々多めのメモリを搭載したマシンなら十分載せられる。しかし、 Java を使う限り、そのような長い文字列を直接扱うことはできない。
  2. 以前よりマシンリソースをフル活用した探索 (例えばゲーム木) というものが行われているが、これを十分効率良く行うには十分なメモリ空間が必要である。ここで、単純な Set を用いて記録する場合、ヒープを使い切る前に 31 bit の添字空間を使いきってしまい、宝の持ち腐れとなってしまう。

解決案

  1. 手作業で頑張って切る: 面倒だし、再利用可能性が...。第一、既存のライブラリの入力として使えない。
  2. LongArray 的なクラスを作って隠蔽: 再利用可能性は確保された。しかし、結局ライブラリを作りなおさないといけないことには変わりない。それに用途が用途だけにアクセスのオーバーヘッドもバカにならない。
  3. JNI で: オーバーヘッドは解決されたが、移植性は? そもそも Java でなくなってしまった...。
  4. JVM に配列用の wide っぽい命令を追加: JVM には次に来る命令のジャンプ先アドレスを 8bit から 16 bit に拡張するという命令があるので、それに倣って配列アクセスを int から long にするものを追加する。上の問題は解決されるけれど、これって実現可能なのだろうか？

感想

そもそも、アドレッシングが固定長になっていて変更できないのが問題の発端のわけで、そのせいで他にもファイルアクセス系APIで long 引数 / long 返り値のメソッドが別に追加されるとかおかしなことになっているのだけれど、だからといって多倍長にしてしまうのはそれはそれで重い以外にもいろいろな問題が出るし、新しいVMを作るとしたらどういうアーキテクチャをとるのが良いのだろうか。