Javaの関数型言語への挑戦／ベターオブジェクト指向言語からの脱皮

Java Day Tokyo 2015
[3-1]
Javaの関数型言語への挑戦／
ベターオブジェクト指向言語からの脱皮
２０１５年４月８日
富士通株式会社
数村憲治
Copyright 2015 FUJITSU LIMITED
アジェンダ
 関数型言語とは
 Javaと関数型言語
 関数型言語の特徴
 参照透過性
 再帰
 ストリーム
 遅延評価
 ストリームで注意すべきこと
 Javaにおける並列プログラミングの実力
1
Copyright 2015 FUJITSU LIMITED
関数型言語(FP)とは
Lisp
Erlang
Haskell
モナド
末尾再帰
Scala
高階関数
無名関数
2
F#
遅延評価
参照透過性
Copyright 2015 FUJITSU LIMITED
なぜ、今、関数型言語か
ハードウェア
メニーコア
大容量メモリ
SSD
環境・プラットフォーム
IoT
ビッグデータ
インメモリデータベース
並列プログラミングの
必然性
手続き型言語では難しい
関数型言語に注目
3
Copyright 2015 FUJITSU LIMITED
メニーコアで性能向上させるには
並列処理は、どんな言語でも頑張ればできる。
プログラマーは、どれだけ頑張ればよいのか？
性能＋品質
熟練プログラマ
手続き型言語
≧
低い
熟練プログラマ
関数型言語
≒
高い
一般プログラマ
関数型言語
4
≫
一般プログラマ
手続き型言語
Copyright 2015 FUJITSU LIMITED
並列と並行
並列(Parallel)とは、
一つの作業を複数に分割し、
それぞれを「本当に」同時に実行することで、
全体処理時間を短くする。
並行(Concurrent)とは、
複数の作業を別々のスレッドで、
(同期を取りながら)実行する。
必ずしも「本当に」同時に実行しなくてもよい。
5
Copyright 2015 FUJITSU LIMITED
並列と並行の例
Parallel GC
GC処理を
複数スレッドで
同時に実行
GC thread #1
GC thread #2
GC thread #3
Concurrent GC
GC thread
GC処理とアプリ処理を
同時に実行
APP thread #1
APP thread #2
6
Copyright 2015 FUJITSU LIMITED
並行・並列プログラミングレベル
レベル１
レベル２
レベル３
スレッド生成・終了アプリ
言語システム
言語システム
排他制御
アプリ
言語システム
言語システム
スレッドプール管理
アプリ
言語システム
言語システム
タスク指向
fork/join・future
なし
アプリ
言語システム
Actorモデル
なし
なし
アプリ
ストリーミング
なし
なし
アプリ
C/C++
Java SE 1.4
Java SE 5-7
FP
Java SE 8
7
Copyright 2015 FUJITSU LIMITED
レベル１からレベル２へ
スレッド指向
・スレッドを作るところから始める
・スレッドから子スレッドを作ると収集つかない
・スレッドプールは自作
タスク指向
・スレッドの生成やプーリングはシステムで
・プログラマは、スレッドで行う仕事にフォーカス
・結果を同期、非同期いずれでも確認可能
8
Copyright 2015 FUJITSU LIMITED
スレッド指向とタスク指向
スレッド指向
class Target
implements Runnable
{
public void run() {
// do something
}
}
Target target = new Target();
Thread t1 =
new Thread(target);
t1.start();
t1.join();
result = target.get();
タスク指向
class Task
extends RecursiveTask <Object>
{
Object compute() {
// do something
}
}
ForkJoinPool pool =
new ForkJoinPool(N);
Future future =
pool.submit(new Task());
if (future.isDone())
result = future.get();
9
Copyright 2015 FUJITSU LIMITED
レベル２からレベル３へ
並列処理
レベル２
ストリームAPI
レベル３
並行処理
アクターモデル
akka等
Javaの標準ライブラリには含まれていない
10
Copyright 2015 FUJITSU LIMITED
アジェンダ
 関数型言語とは
 Javaと関数型言語
 関数型言語の特徴
 参照透過性
 再帰
 ストリーム
 遅延評価
 ストリームで注意すべきこと
 Javaにおける並列プログラミングの実力
11
Copyright 2015 FUJITSU LIMITED
パラダイムシフト
命令型
オブジェクト指向
関数型
?
C
ベターC
モジュール
構造化
・・・
C++
Java
Scala
Haskell
?
?
ベターOOP
継承
カプセル化
・・・
12
参照透過
ラムダ
・・・
Copyright 2015 FUJITSU LIMITED
Javaはどこへ向かうのか
http://mail.openjdk.java.net/pipermail/lambda-dev/2011-August/003877.html
Brian Goetz
It is my belief that the best direction for evolving Java
is to encourage a more functional style of
programming. The role of Lambda is primarily to
support the development and consumption of more
functional-like libraries; I've offered examples such as
filter-map-reduce to illustrate this direction.
Simply put, we believe the best thing we can do for Java
developers is to give them a gentle push towards a more
functional style of programming. We're not going to
turn Java into Haskell, nor even into Scala.
13
Copyright 2015 FUJITSU LIMITED
OOPとFP
OOP
・データはオブジェクト。メッセージはメソッド。
・オブジェクトにメッセージを送り状態を変化。
メッセージ： +2
データ(オブジェクト)
1→3→９
メッセージ： X3
FP
・データは不変。
・データに関数を適用し、新しいデータを作る。
関数： +2
データ:1
関数： X3
データ:3
14
データ:9
Copyright 2015 FUJITSU LIMITED
FP品質 - 制約プログラミング
関数型言語で新たに出来ることよりも、
オブジェクト指向言語で出来たことが、
関数型言語では出来なくなることが重要。
破壊的代入
副作用
ループ
プログラマに制約をかけ、自由度を減らす
プログラム品質の向上
15
Copyright 2015 FUJITSU LIMITED
FP品質 - 数学的プログラミング
数学
証明された定理を積み上げて
新たな定理を証明
プログラム動作保証された小さな関数を合成して
新たな関数を作成
Curry-Howard同型対応
直感主義命題論理と単純型付ラムダ計算の対応
命題＝型証明＝プログラム
コンパイルが通れば動作の証明(型に関して)
16
Copyright 2015 FUJITSU LIMITED
アジェンダ
 関数型言語とは
 Javaと関数型言語
 関数型言語の特徴
 参照透過性
 再帰
 ストリーム
 遅延評価
 ストリームで注意すべきこと
 Javaにおける並列プログラミングの実力
17
Copyright 2015 FUJITSU LIMITED
参照透過性
関数型言語の関数
・関数の引数が同じなら、戻り値は同じ
・関数呼び出しによる副作用(状態変化)なし
・変数の再代入(破壊的代入)ができない
→ 並列化しやすい
Javaのメソッド
・メソッド呼び出しは、メッセージ送信
・メソッドはオブジェクトの状態を変化させる
→ 並列化しにくい
18
Copyright 2015 FUJITSU LIMITED
Javaで参照透過を実現するには
・メソッドは副作用がないように書く。
・変数には、「final」をつける。
・Immutableオブジェクトを作成・使用。
→ できる範囲で
19
Copyright 2015 FUJITSU LIMITED
Immutableオブジェクト
Cプログラム
char* str = ・・・
str[3] = ‘¥0’;
オーバランの危険性
複数スレッドで操作すると
データ破壊の可能性
Javaプログラム
String str = ・・・
str = str.substring(3);
Stringはimmutable
常に新しいString生成
ImmutableなStringがJavaを高品質に
20
Copyright 2015 FUJITSU LIMITED
Mutableなクラス
public class SuperMarket {
private ArrayList<Food> foodList;
public List<Food> get() {
return foodList;
}
public void add(Food food) {
foodList.add(food);
}
public void remove(Food food) {
foodList.remove(food);
}
mutable
複数スレッドから
呼べない
安全にするには？（並行プログラミング）
21
Copyright 2015 FUJITSU LIMITED
mutableなクラスを安全に
public class SuperMarket {
private ArrayList<Food> foodList;
public synchronized List<Food> get() {
return foodList;
}
public synchronized void add(Food food) {
foodList.add(food);
}
public synchronized void remove(Food food) {
foodList.remove(food);
}
getメソッドで返されるListオブジェクトがmutable
22
Copyright 2015 FUJITSU LIMITED
mutableなクラスを安全に
public class SuperMarket {
private ArrayList<Food> foodList;
public synchronized List<Food> get() {
return foodList.clone();
}
public synchronized void add(Food food) {
foodList.add(food);
}
public synchronized void remove(Food food) {
foodList.remove(food);
}
23
Copyright 2015 FUJITSU LIMITED
更新があまりないなら
public class SuperMarket {
private CopyOnWriteArrayList<Food> foodList;
public synchronized List<Food> get() {
return foodList.clone();
}
public synchronized void add(Food food) {
foodList.add(food);
}
public synchronized void remove(Food food) {
foodList.remove(food);
}
java.util.concurrent.CopyOnWriteArrayListの使用で
synchronizedを削減
24
Copyright 2015 FUJITSU LIMITED
Listを更新されたくないなら
public class SuperMarket {
private CopyOnWriteArrayList<Food> foodList;
public List<Food> get() {
return
Collections.unmodifiableList(
foodList.clone());
}
java.util.Collections.unmodifiableListで
read-onlyのListの作成
25
Copyright 2015 FUJITSU LIMITED
アジェンダ
 関数型言語とは
 Javaと関数型言語
 関数型言語の特徴
 参照透過性
 再帰
 ストリーム
 遅延評価
 ストリームで注意すべきこと
 Javaにおける並列プログラミングの実力
26
Copyright 2015 FUJITSU LIMITED
ループから再帰
ループ
再帰
int foo(Bar[] bars) {
int result = 0;
for (int i = 0 ; i < bars.length ; ++i)
result += bars[i].get();
return result;
}
再代入の解消
int foo(final Bar[] bars) {
return foo1(0, 0, bars);
}
int foo1(final int n, final int result, final Bar[] bars) {
if (n == bars.length)
return result;
return foo1(n+1, bars[n].get()+result, bars);
}
27
Copyright 2015 FUJITSU LIMITED
末尾再帰最適化(TCO)
最後の処理が自分自身への呼び出しなら、
関数コール(新しいスタック作成)しない。
ループ処理のように同じスタックで処理する。
int foo1(final int n, final int result, final Bar[] bars) {
if (n == bars.length)
return result;
return foo1(n+1, bars[n].get()+result, bars);
}
Java(JIT)では未対応
28
最後の処理が
自分自身への
呼び出し
Copyright 2015 FUJITSU LIMITED
アジェンダ
 関数型言語とは
 Javaと関数型言語
 関数型言語の特徴
 参照透過性
 再帰
 ストリーム
 遅延評価
 ストリームで注意すべきこと
 Javaにおける並列プログラミングの実力
29
Copyright 2015 FUJITSU LIMITED
ストリーム(パイプライン)とは
FPスタイル
input
func1
func2
func3
output
UNIXのパイプ処理
% cat input | grep keyword | sort | head -5 > output
ストリームプログラミング
read(input).stream()
.filter(keyword)
.sorted()
.limit(5)
.writeTo(output)
30
Copyright 2015 FUJITSU LIMITED
ループからストリーム
int foo(Bar[] bars) {
int result = 0;
for (int i = 0 ; i < bars.length ; ++i)
result += bars[i].get();
int foo(Bar[] bars) {
int result = 0;
for (Bar b : bars)
result += b.get();
Java SE 7の
糖衣構文
int foo(Bar[] bars) {
return Arrays.stream(bars)
.mapToInt( b -> b.get() );
.sum();
Java SE ８の
stream API
31
Copyright 2015 FUJITSU LIMITED
ループv.s.ストリーム(並列化)
ループの並列化
int foo(Bar[] bars) throws InterruptedException {
BarSum[] barSum = new BarSum[N];
for (int i = 0 ; i < N ; ++i)
barSum[i] = new BarSum(bars, bars.length/N*i,
bars.length/N*(i+1));
int result = 0;
for (int i = 0 ; i < N ; ++i) {
barSum[i].join();
result += barSum[i].result;
}
return result;
}
class BarSum extends Thread {
Bar[] bars;
int begin, end;
int result;
BarSum(Bar[] bars, int begin, int end) {
this.bars = bars;
this.begin = begin;
this.end = end;
}
public void run() {
for (int i = begin ; i < end ; ++i)
result += bars[i].get();
}
}
ストリームの並列化
int foo(Bar[] bars) {
return Arrays.stream(bars)
.parallel()
.mapToInt( b -> b.get() );
.sum();
32
Copyright 2015 FUJITSU LIMITED
アジェンダ
 関数型言語とは
 Javaと関数型言語
 関数型言語の特徴
 参照透過性
 再帰
 ストリーム
 遅延評価
 ストリームで注意すべきこと
 Javaにおける並列プログラミングの実力
33
Copyright 2015 FUJITSU LIMITED
遅延評価
必要になるまで評価しない
メリット
・無駄な処理をしなくてよくなる
・重い処理を後回しにできる
・並列処理効率を上げられる
デメリット
・メモリ使用量が増える
・デバッグが難しくなる
34
Copyright 2015 FUJITSU LIMITED
Javaでの評価タイミング
例１
if ( f1() && f2() ) {
f1()がfalseならf2()は評価しない
一般的には遅延評価と言わない
例２
int n = foo();
nの値はここで決定
// nに関係ない処理
ここなら
遅延評価という
System.out.println(n);
Javaでは
普通のメソッド呼び出しは遅延評価しない
35
Copyright 2015 FUJITSU LIMITED
Javaにおける遅延評価
ストリームの中間操作は遅延評価
終端操作実行時に評価
int foo(List<Integer> list) {
return list.stream()
.filter(i -> i > 30)
.mapToInt(i -> i * 2)
.limit(50)
.sum();
}
36
中間操作
中間操作
中間操作
終端操作
Copyright 2015 FUJITSU LIMITED
ストリーム操作の種類
遅延評価
ストリーム操作
中間操作
終端操作
forEach/count
ステートレス操作
ステートフル操作
map/filter
distinct/sorted
並列化しやすい
37
Copyright 2015 FUJITSU LIMITED
多段ループ処理
int foo(List<Integer> list) {
ArrayList<Integer> list2 = new ArrayList<>;
for (int i : list)
if (i > 30)
list2.add(i);
ArrayList<Integer> list3 = new ArrayList<>;
for (int i : list2) list3.add(i * 2)
int result = 0; int count = 0;
for (int i : list3) {
result += i;
count ++;
if (count == 50)
break;
}
return result;
38
待ち合わせ
待ち合わせ
Copyright 2015 FUJITSU LIMITED
メニーコアにおける並列化
理想
現実
・・・
コア１
コア２
タスク
タスク
タスク
タスク
タスク
タスク
タスク
タスク
タスク
コア１
コア２
タスク
タスク
タスク
タスク
タスク
タスク
・・・
コアｎ
同時に終わる
コアｎ
タスク
タスク
タスク
空き
空き
39
CPUに空き
Copyright 2015 FUJITSU LIMITED
ループの並列処理化
int foo(List<Integer> list) {
int result = 0;
int count = 0;
for (int i : list) {
if (i > 30) {
result += i *2;
count ++;
if (count == 50)
break;
}
}
return result;
}
ループは一つになったが
並列化するには、
複数スレッドで
同期を取りながら
５０数える必要がある
40
Copyright 2015 FUJITSU LIMITED
遅延評価と並列化
int foo(List<Integer> list) {
return list.stream()
.parallel()
.filter(i -> i > 30)
.mapToInt(i -> i * 2)
.limit(50)
.sum();
}
遅延評価がないと
待ち合わせ
待ち合わせ
待ち合わせ
並列化の源は遅延評価
41
Copyright 2015 FUJITSU LIMITED
アジェンダ
 関数型言語とは
 Javaと関数型言語
 関数型言語の特徴
 参照透過性
 再帰
 ストリーム
 遅延評価
 ストリームで注意すべきこと
 Javaにおける並列プログラミングの実力
42
Copyright 2015 FUJITSU LIMITED
並列から逐次へ
someStream
.parallel()
.filter(e -> e.shouldHandle())
.sorted()
.limit(100)
.forEach(e -> System.out.println(e));
someStream
.parallel()
.filter(e -> e.shouldHandle())
.sorted()
.sequential()
.limit(100)
.forEach(e -> System.out.println(e));
43
ソートされない
出力
ソート後は逐次に
Copyright 2015 FUJITSU LIMITED
streamは速やかに流す
static Object lock = new Object();
Bar foo(List<Bar> list) {
return list.stream()
.parallel()
.map(b -> {
synchronized (lock) { return b.baz();}
})
.max(comparator);
}
Synchronizedを使わない
44
Copyright 2015 FUJITSU LIMITED
副作用を書かない
void foo(List<Bar> list) {
ArrayList<Bar> result = new ArrayList<>();
list.stream()
.parallel()
.filter(b -> b.baz())
.forEach(b -> result.add(b));
List<Bar> result = list.stream()
.parallel()
.filter(b -> b.baz())
.collect(Collectors.toList());
45
Copyright 2015 FUJITSU LIMITED
Collectors(リダクション)
java.util.stream.Collectors
・リダクション用のstaticメソッド群が定義
・Stream.collect()メソッドに指定する
・toList/groupingBy/summingIntなど
例：
List<Bar> result = list.stream()
.parallel()
.filter(b -> b.baz())
.collect(Collectors.toList());
46
Copyright 2015 FUJITSU LIMITED
CollectorとStreamの属性
Collectorの属性
UNORDERED: 順序が保証されない
CONCURRENT: アキュムレータの同時呼び出し可
IDENTITY_FINISH: フィニッシャー不要
Streamの属性
unordered: 順序不定のストリーム
parallel: 並列ストリーム
47
Copyright 2015 FUJITSU LIMITED
並列リダクションの条件
(A) Streamがparallel
かつ
(B) CollectorがCONCURRENT
かつ
(C) Streamがunordered または
CollectorがUNORDERED
48
Copyright 2015 FUJITSU LIMITED
並列リダクション
Map<Foo, Bar> result = source.stream()
.parallel()
parallel stream
.filter(b -> b.baz())
.collect(toMap(b->b.foo(), b));
非並列
CONCURRENT属性なし
ConcurrentMap<Foo, Bar> result =
source.stream()
CONCURRENT属性
parallel stream
UNORDERED属性
.parallel()
.filter(b -> b.baz())
並列
.collect(toConcurrentMap(b->b.foo(), b));
49
Copyright 2015 FUJITSU LIMITED
アジェンダ
 関数型言語とは
 Javaと関数型言語
 関数型言語の特徴
 参照透過性
 再帰
 ストリーム
 遅延評価
 ストリームで注意すべきこと
 Javaにおける並列プログラミングの実力
50
Copyright 2015 FUJITSU LIMITED
Stream APIによる並列性能
レベル２のプログラム(fork/join使用)と
レベル３のプログラム(stream使用)との比較
指標
生産性(ソース行数)と性能(実行時間)
ベンチマークモデル
100万件の購買伝票を基に、
購入関連の高い商品群を抽出し、
未購入ユーザにレコメンドする。
51
Copyright 2015 FUJITSU LIMITED
生産性(ソース行数)
140
ス
テ
ッ
プ
数
ソース行数（除共通部分）
120
100
80
60
40
20
0
レベル２(fork/join)
レベル３（stream）
レベル２のソース
レベル３のソース
static Map<Account, List<Product>> createProductMap(Account[] accounts) {
Map<Account, List<Product>> map = new ConcurrentHashMap<>();
ArrayList<ForkJoinTask> tlist = new ArrayList<>();
for (Account acc : accounts) {
ForkJoinTask task = pool.submit(new Runnable() {
public void run() {
ArrayList<Product> list = new ArrayList<>();
for (PurchaseRecord pr : acc.records)
for (Order ord : pr.orders)
if (!list.contains(ord.product))
list.add(ord.product);
map.put(acc, list);
}});
tlist.add(task);
}
for (ForkJoinTask task : tlist)
task.join();
return map;
}
static Map<Account, List<Product>> createProductMap(Account[] accounts) {
return Arrays.stream(accounts).parallel()
.collect(Collectors.toMap(Function.identity(),
acc -> acc.records.stream()
.flatMap(rec -> rec.orders.stream())
.map(ord -> ord.product)
.distinct()
.collect(Collectors.toList())));
}
52
Copyright 2015 FUJITSU LIMITED
性能(処理時間)
M10-4S SPARC64-X 4CPU x16core x2thread
40000
時
間
(
m
s
35000
レベル２(fork/join)
30000
25000
レベル３（stream）
20000
15000
10000
)
5000
0
2
4
8
16
32
64 128
スレッド数
・スレッド数が少ないほど、レベル２の方が良い
・スレッド数が大きくなると、差はほとんどなくなる傾向
53
Copyright 2015 FUJITSU LIMITED
まとめ
メニーコアを使い切る並列プログラミング
Javaによる高品質並列処理
ストリームプログラミング
参照透過・遅延評価の活用
関数型言語の仕組みを知る
オブジェクト指向言語
54
Copyright 2015 FUJITSU LIMITED
Q&A
55
Copyright 2015 FUJITSU LIMITED
Copyright 2010 FUJITSU LIMITED

Download Report