S-JIS[2011-03-21/2011-09-18] 変更履歴

Scala 並列コレクション（正式導入前）

このページは、Scala2.9が正式リリースされる前に並列コレクション（parallel collections）を試したときのメモ。[/2011-09-18]
→正式導入された並列コレクション（メソッド名などはかなり変わっている）

概要 [/2011-03-23]
foreach [/2011-03-23]
sum [/2011-03-23]

kiyoshihosodaさんのScala Parallels Collections

概要

Scala2.9で並列コレクション、つまり並列実行できるコレクションが追加されるというので
sumメソッドを試してみたら速くならなかったので
foreachのサンプルを流してみたら全然並列実行されてなかったという＾＾；

Scala2.9.0.r24435-b20110312020123・JDK1.6.0_22・WindowsXPで実験。
並列処理できるCPU数は以下の通り、2つあるはず。

scala> scala.collection.parallel.availableProcessors
res0: Int = 2

[2011-03-23]
どうやらsumで速くならなかったのは試したクラスやデータ数が悪かった事による勘違いで、
foreachで速くならなかったのはpforeachでないと並列実行されないよう変更された為のようだ(苦笑)

foreachはpが付くメソッドがあるのでsumもpsumとか使わないとダメなのかと思ったら、sumはそのままで並列実行されるようになっている。
foldLeft・reduceLeftは、fold・reduceというメソッドを使うのだそうだ。
→ParIterableLike.scala

foreachの例

kiyoshihosodaさんのScala Parallels Collectionsに書かれているforeachを実行してみた。

scala> benchmark(10){ for(i<- 1 to 100){ Thread.sleep(10) } }.report
List(1078, 1079, 1078, 1078, 1078, 1078, 1079, 1078, 1078, 1078)
1078.125

scala> benchmark(10){ for(i<- (1 to 100).par){ Thread.sleep(10) } }.report
List(1078, 1078, 1063, 1078, 1078, 1078, 1079, 1062, 1078, 1062)
1074.125

全然速くなってない(苦笑)
~~むー、WindowsXPだからいけないのか？~~

たけうちひでゆきさんによると、最近のScala2.9.0ではforeach（for式）では並列実行はされず、pforeachというメソッドを使うのだそうだ。[2011-03-23]

scala> benchmark(10){ (1 to 100).par.pforeach{ _=> Thread.sleep(10) } }.report
List(547, 546, 531, 547, 531, 547, 532, 547, 532, 547)
541.125

sumの例

合算の処理速度を試す過程で並列コレクションを実行してみた。

val range = Range(1, 10000+1)
benchmark(10, 100){ range.par.sum }.report

方法	Int Range	Int Range.par	Long Range	Long Range.par	Int Array	Int Array.par	Long Array	Long Array.par	備考
sum	107	151	313	654	86	172	299	248 332	Array.parのLong版は、上段が`array.par.map(_.toLong).sum` 下段が`array.map(_.toLong).par.sum`
whileループ	115	62	156	67	64	125	76	131
forループ	18	45	17	41	72	109	74	113
foreach	20	51	18	41	74	106	72	111
reduceLeft	84	98	246	684	102	160	280	276	※Longではmap(_.toLong)を使用
foldLeft	94	96	116	109	90	131	96	133
再帰関数	863		887						Range.parは遅すぎて測定を断念

~~並列動作していないので~~全般的に速度が上がっていないのだが、
Rangeのparがwhileループで速くなってるのはなんでだろう？

上記の速度が遅いのは、1万件程度では並列実行の準備（オーバーヘッド）の方が大きいということのようだ。[2011-03-23]

val range = 1 to N
val prange = range.par

	N=1*10000 benchmark(10,100)	N=10*10000 benchmark(10,10)	N=100*10000 benchmark(10,1)	N=1000*10000 benchmark(10,1)
`range.sum`	94	96	107	935
`prange.sum`	106	90	90	896
`range.par.sum`	107	92	92	898

Rangeの場合、並列コレクションParRangeを作る（parの呼び出し）自体は無視できる程度の時間しかかかっていないようだ。

しかし、件数が多くなってくると確かに並列コレクションの方が速いが、CPUが2コアあったら半分くらいの実行時間になると期待していたので、それほどではないなぁ。
でもタスクマネージャでCPU使用率を見てみると、確かに「range.sum」は50％ちょっとで、prange・range.parは100％近くになっている。

でも他の人のはもっと速くなってるのになぁ。

xuweiさんのscala2.9のparallel collection の benchmark をしてみた
k4200さんのParallel Collectionのベンチマークやってみた
kxbmapさんのParallel Collectionのベンチマークやってみました

ん？もしかして自分のマシンが貧弱なだけか？メモリー1GBだし、-Xmsも-Xmxも指定してないし(苦笑)
という訳で試しに指定してみたが、変わったような、変わってないような…。

> set JAVA_OPTS=-Xms768M -Xmx768M

	N=1*10000 benchmark(10,100)	N=10*10000 benchmark(10,10)	N=100*10000 benchmark(10,1)	N=1000*10000 benchmark(10,1)
`range.sum`	86	94	121	1139
`prange.sum`	112	92	90	867
`range.par.sum`	109	90	90	861

つーか、皆さんのは「(1L to N).toList」でListを作り、その「.toParSeq」でParArrayを作っている。
（ちなみに、「1L to 10」でNumericRange[Long]が作れるとは知らなかった…。今回、自分は全部Intで試していて、10万件の合算でもIntに収まりきらないけど、今試したいのは実行速度であって正確な計算結果ではないから、とりあえず良しとしよう＾＾；）
ということは、Range・ParRangeで試しているからいけないのか？
では配列（Array・ParArray）と、ついでにVector・ParVectorでやってみよう。

val array   = Array.range(1, N+1)
val parray  = array.par
val vector  = Vector.range(1, N+1)
val pvector = vector.par

		N=1*10000 benchmark(10,100)	N=10*10000 benchmark(10,10)	N=100*10000 benchmark(10,1)	N=1000*10000 benchmark(10,1)
`array.sum`	`Array`	70	82	72	725
`parray.sum`	`ParArray`	59	43	31	334
`array.par.sum`	`ParArray`	123	102	102	2969
`vector.sum`	`Vector`	186	188	197	1978
`pvector.sum`	`ParVector`	98	74	72	715
`vector.par.sum`	`ParVector`	98	74	72	719

お、すごい！ちゃんと実行時間が半分くらいになった！

配列の場合、parメソッドで並列用配列（ParArray）を作るは結構コストがかかるようだ。きっとデータをコピーしているのだろう。
VectorでParVectorを作るのはほとんどコストがかからない。Vectorは内部が木構造になっていることを考えれば、こういう分割は得意なのかもしれない。
（ただし、sumの実行時間自体はVectorより配列の方が速いけど＾＾；）
（ん？配列も先頭インデックスと末尾インデックスだけ保持する（つまりビューを作る）ようにすれば、別にコピーを作る必要は無いよな。
と思ったが、Vectorは不変だけどArrayは可変だから、ArrayとParArrayは別物なのでコピーしておかないといけないんだな…）

なお、Listにはparメソッド（およびParListクラス）は無い。
Scalaの不変Listは単純な単方向リストなので、どこかで分割しようと思ったら、その位置まで辿る必要がある。
リストサイズすら全データを辿らないと分からないので、どこで区切るかを事前に決めることも出来ない。
分割する為に全データを辿るくらいなら、最初から全データを順番に（分割・並列せずに）処理した方が早い、ということなのかな？＾＾；

並列コレクションへ戻る / コレクションへ戻る / Scala目次へ戻る / 技術メモへ戻る

メールの送信先：ひしだま