Javaの関数型言語への挑戦

Java Day Tokyo 2015

Transcript

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