Concurrent Clean : String2 : 効率改善
簡単な速度調査とかやってみて分かったのは、文字列としての文字配列の性能というのはバカにならないくらいよいということだ。それは、Cleanのような非破壊的な文字配列であってもそうなのだ。
これは、まあ、結果を見てみればそうだろうと思ったのだけれど、結果を見るまではあまり想定していなかった。やはり、実験はしてみるものだ。
とはいえ、文字配列を文字列として使うのは、使い方によっては非効率が生まれるのは実験結果にも表れているわけで、文字配列のよい所とFinger treesのよい所を組み合わせて使うというのを試してみようと思う。
というようなことを考えて、今のString2に次の修正をいれてみる。
- 文字列を結合するときは、結合する部分の文字断片が、一定のサイズ以下だった場合には、文字断片の結合を行う
- measureの計算はeagerに行う
２つ目の話は上の話とは関係なくて、[id:lethevert:20070811:p4]で下した判断はどうも間違っていて、thunkがたまってメモリを消費してしまっているらしいので。
-
-
- -
-
上の２つだけでは十分に高速化しきれなかった。１つ目のブロック化は、数十％の効果はあったが、なお十分なものではなかった。
そこで、コードが複雑化してしまうが、String2の実装を文字配列とFinger treeの組み合わせで持つことにした。つまり、短い文字列は文字配列で持ち、長い文字列はFinger treeを使う。そしてFinger treeはさらにブロック化する。
:: String2 = ST !{#Char}
| FT !(FingerTree Int String2Elem)という構成を取ることにした。結果として、コードは複雑になったものの、ほぼ満足いくパフォーマンスを達成した。つまり、短い文字列操作は文字配列と同等の効率で、長い文字列はFinger treeの性能を示した。
-
-
- -
-
[id:lethevert:20070813:p6]で行ったテストプログラムの結果は、次のように改善された。
| N=10000 | N=50000 | N=100000 | |
|---|---|---|---|
| 文字配列 | 0.12 | 0.64 | 1.26 |
| String2 | 0.17 | 0.87 | 1.54 |
| String2(前回) | 0.66 | - | - |
