Advent Calender 2016 Javaの記事として1つ書かせていただきます。
ちょっと昔(Java7の頃)の失敗談です。
今とは状況が異なるかもしれないので、そこはお察しください。
背景
それは私が学生の頃の話です。
当時の研究テーマは大量のデータを扱うというもので、とにかく検索が高速かつ省メモリな処理を行うためにどうすればいいかを考えていました。
検索の高速化のためにはHashSetやHashMapが必要不可欠でしたが、ArrayListなどと比べるとメモリ効率が悪いのがネックです。
HashSetの実装はHashMapを使っていた！
なんとか改善できないものかと、HashSetのコードを覗いていると以下のような形になってました。
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
}
ここで重要なのはprivate transient HashMap<E,Object> map;の部分です。
すなわち、HashSetは実装上は内部にHashMapを持っており、ValueとしてPRESENTという定数(中身はオブジェクト型の共通インスタンス)を入れることでHashSetとしての役割を実現しているということです。
なるほど確かに、HashSetというのはキー部分だけのHashMapと考えることができるので、このような実装になっているということは納得できます。
HashMapの実装は？
では、大元のHashMapの方の実装はというとこんな感じ。
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
transient Entry[] table;
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
}
putメソッドを実行すると、挿入先のインデックスを決定してからaddEntryメソッドが呼ばれます。
addEntryメソッドでは、Entryクラスのインスタンスを生成してtableに入れます。
このEntryクラスもHashMap内で定義されています。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
さて、Entryクラスはデータを追加するたびにインスタンスが生成されます。
HashMapのフィールドはtable以外はデータサイズが変化しないものばかりなので、データ数が大きい場合、HashMapのサイズはほとんどN×(Entryのインスタンスサイズ)と考えることができます。
これは、EntryのインスタンスサイズがHashMapのデータサイズに大きな影響を与えるということを意味しています。
たとえば、Entryのインスタンスサイズが1byte減るとHashMapのデータサイズはNbyte減少します。
Nは大きな値なので、例えば100万とした場合、100万byte = 1MBのデータサイズの削減につながります。
Entryクラスの改造
以上を踏まえたうえで、Entryクラスの定義を見てみると、key、value、next、hashの4つのフィールドがあります。
ここで、HashSetはHashMapを使って実装されていたことを思い出すと、HashSetのほうでは共通のオブジェクトをValueに入れていることから、Entryクラスのvalueのフィールドは不要であることがわかります。
そこで、HashSetの場合専用の(valueのない)Entryクラスを作ることでEntryインスタンスのデータサイズを削減できるのではないかと考えました。
そこで、HashSetをHashMapを使わない方法で実装しなおし、その中にvalueがないEntryを実装しなおします。
実装しなおしたSimpleHashSet.javaのコードは以下のような感じです。
public class SimpleHashSet<E> extends AbstractSet<E>{
protected Entry entries[];
static protected class Entry<E>{
final E key;
Entry<E> next;
int hash;
Entry(E key){
this.key = key;
hash = hash(key.hashCode());
}
}
}
メモリ消費量は改善されたか？
比較結果自体は残ってなかったですが、結論としては、通常のHashSetとSimpleHashSetのメモリ消費量を比較してみても変化はたいしてなかったです。
これに関して調べてみると、JVMのメモリ管理の単位についての情報が得られました。
JVMでは、オブジェクトのメモリが8byte単位で切り上げられるとのこと。
また、何もフィールドが存在しないオブジェクトでも8byteはメモリを消費します。
これを踏まえて改造前と改造後のEntityインスタンスのサイズを計算してみると
改造前: 8 + 4(key) + 4(value) + 4(next) + 4(hash) = 24 byte
改造後: 8 + 4(data) + 4(next) + 4(hash) = 20 byte
純粋にbyte数計算を行った場合だと、改造後の方が4byteデータサイズが削減されています。
しかし、8byte単位で切り上げるとどちらもも24byteになってしまいます。
結論
メモリ改善するならJVMの仕様をちゃんと把握してからじゃないとダメですね。
思いつきだけで実装しても上手くいかないという教訓になりました。
ただ、久々に昔のコードを見ていて気付いたんですがハッシュ値を格納しているhashフィールドを削除すれば16byteになりそうですね(未検証)。
その場合、ハッシュ値のフィールドがない分、比較の際に毎回計算が実行されます。
HashSetの場合、検索時に結構な回数ハッシュ値の比較が行われるのでそのあたりを効率かしないと検索効率が落ちそうですが。