要点: Energy Profiles of Java Collections Classes

Last Update: 2016/10/03, Written by Hiroyuki Matsuo

この記事は，論文『Energy Profiles of Java Collections Classes^[1]』の要点を日本語でまとめたものです．

[1] S. Hasan, Z. King, M. Hafiz, M. Sayagh, B. Adams, and A. Hindle. Energy Profiles of Java Collections Classes. In ICSE ‘16 Proceedings of the 38th International Conference on Software Engineering, pages 225-236. ICSE, 2016.

Abstract

Java の List, Map, Set 上の主要な操作が消費する電力の詳細な分析結果を作成した．
これにより，これらのデータ構造は電力消費の観点から著しく異なることが分かった．

例：ArrayList は LinkedList よりも……

電力消費が少ない
- データを真ん中もしくは末尾に挿入する場合
電力消費が大きい
- データを先頭に挿入する場合

この結果を説明するため，操作中のメモリ消費量，およびバイトコードを調べた．
バイトコード中の重い計算タスクと消費電力の間には因果関係が認められたが，メモリ消費量と電力消費の間には認められなかった．

本研究の分析結果を評価するため，6 つのアプリケーション・ライブラリ中に用いられている Collections 型をこれらの型と置き換えた．
分析結果が示す適切でない Collections 型を選んだ場合，最も効率のよいものと比べ，300% 以上の電力を消費することが判明した．

1. INTRODUCTION

対象とする Collections 型は Java Collections Framework, Apache Commons Collections, Trove から選択．
電力消費データは GreenMiner フレームワークを用いて収集．

分析結果では，入力サイズおよびデータ型によって，どれだけ電力消費量が異なるかを示す．

2. COLLECTIONS CLASSES IN OUR STUDY

Java Collections Framework (JCF)
- Java にデフォルトで実装されている，よく使われるデータ構造・アルゴリズム
Apache Commons Collections (ACC)
- サードパーティによる実装．すでに JCF に存在するものに代わるもののみを対象とした
Trove
- サードパーティによる実装．プリミティブなデータ型のみを保持できる Collections．
  JCF の 1/3 のヒープ領域しか使わない

分析した Collections クラスの一覧は，Table 1 の通り．

Table 1: Profiled Collections Classes

Library	List	Map	Set
Java Collections Framework (JCF)	`ArrayList` `LinkedList`	`HashMap` `TreeMap`	`HashSet` `TreeSet` `LinkedHashSet`
Apache Commons Collections (ACC)	`TreeList`	`HashedMap` `LinkedMap`	`ListOrderedSet` `MapBackedSet`
Trove	`TIntArrayList` `TIntLinkedList`	`TIntIntHashMap`	`TIntHashSet`

さらなる結果は，https://sites.google.com/site/collectionsenergy/ から確認できる．

3. ENERGY MEASUREMENT INFRASTRUCTURE SETUP

GreenMiner のハードウェア・インフラストラクチャを用いて，実際の電力消費をジュール (J) で計測した．

3.1 The GreenMiner Infrastructure

GreenMiner
- ハードウェア/ソフトウェアを継続的に試験するためのソフトウェアパッケージ
- 色々なデバイスを取り付け，それらのデバイス上でテストを実行し，その電力消費を計測できる
Raspberry Pi
- GreenMiner のクライアント
- テストベッド（たたき台）として使用
- テスト用 Android デバイスを制御する

Raspberry Pi が Android デバイス上でテストを実行し，デバイスの電力消費を監視している Arduino からデータを収集する．
電力計測チップ INA219 を使用．毎秒 500,000 回計測し，抽出・合計する．
テストベッドが INA219 の総計測データを記録し，GreenMiner のウェブサービスにアップロードする．

3.2 Measurement Process

以下のような，実験用の Android アプリを作成．

ディスプレイには何も表示しないため，ディスプレイの電力消費は一定
実験用の jUnit テストのたたき台
- 各ユニットテストでは，Collections クラスのインスタンスに対して，insertion, iteration といった操作を行う

特定のユースケース用のユニットテストを，GreenMiner 上で随時行う．
例えば，ユースケース “Insertions at the Beginning of Lists” では，Table 1 に示す 5 つのリスト用の jUnit テストを書いた．

現時点で懸念される問題点を 3 つ挙げ，次のように対応する．

Ensuring Fixed Overhead

テストの種類にかかわらず，setUp() メソッドの中ですべての Collections クラスをインスタンシエーションする．
つまり，LinkedList に対して計測をする場合でも，setUp() メソッドの中で，5 つの List クラスがすべてインスタンシエーションされる．

Producing Observable Changes

テスト用メソッドの中では，API を複数回呼び出すことで観測する．
例えば，50 アイテムを挿入する場合，(1) setUp(); (2) 挿入; (3) tearDown(); のセットを 20 回行う．

Ensuring Device Consistency

すべてのテストを一つのデバイス上で行う．

4. ENERGY PROFILE RESULTS

論文の通り．省略．

5. WHY THESE ENERGY DIFFERENCES?

電力消費に違いが生じた原因を説明するため，次の 2 つの要因を調べた：

API 操作中のメモリ消費量
API 操作中の実行に時間がかかる（重い）バイトコード命令

論文に書かれているのは挿入操作についてのみ．
その他の操作についての考察は Web ページを参照．

5.1 Memory Usage

insertion（add()）メソッドの実行前後でメモリ消費量を記録した．

記録によると，リストの先頭，真ん中，末尾への挿入でメモリ消費量はほぼ同じであった．
一方，すでに見たように電力消費量は大きく変わるため，メモリ消費量との間には因果関係がないことが分かった．

5.2 Executed Dalvik Bytecodes

add() 操作をトレースする Dalvik バイトコードを生成し，比較した．

Dalvik VM
- Android プラットフォームで採用されていた，レジスタベースの仮想マシン
- 現在では Android Runtime (ART) に置き換えられ，使用されていない

参考：Dalvik仮想マシン

dexdump（Dalvik VM の実行ファイルを操作できるツール）を用いて，アプリケーションのバイトコードを展開
AndBug（Java Debug Wire Protocol (JDWP) を実装したデバッグツール）を用いて，バイトコードの各行を紐付け
テストの実行中，ツールが実行したバイトコードと対応するソースコードを出力する

リストの真ん中への挿入については，バイトコードの iget-object および invoke-static がパフォーマンスに影響していそうなことが分かった．

リストの先頭・末尾への挿入については，電力消費に違いが生じた原因を説明するだけの十分な分析はできなかった．

6. EVALUATION

これまでの考察で，リストの真ん中への挿入については，ArrayList の方が LinkedList より電力消費が少ないことが分かった．

6 節では，既存のライブラリの List クラスを ArrayList (“good”) / LinkedList (“bad”) にそれぞれ置き換えることで，実際のアプリケーションでも電力消費に差が出るのかどうかを調べた．

あとは論文の通り．省略．

6.7 Discussion

We also noticed that for each of the applications, the degradation factor for energy consumption was the same as the slowdown factor of the bad version of the program.

例えば，Google Gson ライブラリで “bad” な変更を施したものは，実行時間および電力消費の両方が，オリジナルと比べて約 4 倍になった．

ただ，「アプリケーションが遅いと，より多くの電力を消費する」という傾向を結論づけるには，さらなる調査が必要．

関連する研究の解説付き一覧．
電力消費に関する他の観点や，電力消費そのものの色々な計測方法が書いてあり参考になる．