こんにちわ、初めてトピックを作成させていただきます。
J2SDK5.0になってからStringBufferの非同期対応版のStringBuilderが登場しました。
実際に一定回数appendメソッドを呼び出して、終わりにtoStringさせるコードを1セットとしてループさせて平均実行速度を計測したのですが、Sunが保証するだけあり、StringBuilderのが方が一回り高速でした。
(すみません具体的な数値は手元に資料がありません。)
テスト自体はシングルスレッドで行いましたが、(スレッドセーフかどうかは別として)マルチスレッドでappendメソッドを呼び出しした場合は、StringBufferのオーバーヘッドが大きくなり、性能差は如実に出そうだな・・・て感じています。
そこでこのStringBuilder互換の機能をJDK1.4上で実現できないかと、StringBuilderのappendメソッドのみを実現するStringAppenderというクラスを自前で実装しました。
http://
appendメソッドでArrayListにオブジェクトを追加しておいて、toStringでいっせいにchar[]を作成してString化する・・・というコードを書いたのですが、性能の方はStringBufferよりもふた周りほど遅いコードになってしまいました。
実装がよくなかったのか、そもそもJDKのランタイム上で動作するStringBufferのByteコードは(ネイティヴに肉薄するように内部で)最適化されているのかどちらなのでしょうか？
どなたかJDKの標準ライブラリの実装について詳しい方がいらっしゃたらご意見くださると幸いです。
J2SDK5.0になってからStringBufferの非同期対応版のStringBuilderが登場しました。
実際に一定回数appendメソッドを呼び出して、終わりにtoStringさせるコードを1セットとしてループさせて平均実行速度を計測したのですが、Sunが保証するだけあり、StringBuilderのが方が一回り高速でした。
(すみません具体的な数値は手元に資料がありません。)
テスト自体はシングルスレッドで行いましたが、(スレッドセーフかどうかは別として)マルチスレッドでappendメソッドを呼び出しした場合は、StringBufferのオーバーヘッドが大きくなり、性能差は如実に出そうだな・・・て感じています。
そこでこのStringBuilder互換の機能をJDK1.4上で実現できないかと、StringBuilderのappendメソッドのみを実現するStringAppenderというクラスを自前で実装しました。
http://
appendメソッドでArrayListにオブジェクトを追加しておいて、toStringでいっせいにchar[]を作成してString化する・・・というコードを書いたのですが、性能の方はStringBufferよりもふた周りほど遅いコードになってしまいました。
実装がよくなかったのか、そもそもJDKのランタイム上で動作するStringBufferのByteコードは(ネイティヴに肉薄するように内部で)最適化されているのかどちらなのでしょうか？
どなたかJDKの標準ライブラリの実装について詳しい方がいらっしゃたらご意見くださると幸いです。
|
|
|
|
コメント(8)
まだJDK 1.5のソースを読んではいないので，前のバージョンの実装からの想像で書いてますが。
ユーザーコードで標準APIと同等のパフォーマンスをもつクラスを作ることは無理だと思います。
StringはImmutableなクラスなので，実際に文字列を保持しているchar配列は，外部からアクセスができないようにしておく必要があります。ですので，ユーザーのコードが提供したchar配列をもとにStringのインスタンスを構築するときは，その配列を直接使うのではなくコピーした配列を値として保持するようにしています。
ですが，StringBufferはStringと同じパッケージであるという特権を生かして，使用していたchar配列を直接Stringにつかわせるという「ズル」をしています。で，StringBufferのほうで「もうStringにつかわれたから変更できない」ということを覚えておいて，StringBufferへのdeleteやreplaceが実行されたら，そのときはじめて自分でchar配列のコピーを作成して値を変更するという実装になってます。
ユーザー作成のStringBuffer互換コードでは，この手の「ズル」できないので，どうしてもchar配列のコピーが発生してしまい，パフォーマンスが悪くなってしまいます。
ユーザーコードで標準APIと同等のパフォーマンスをもつクラスを作ることは無理だと思います。
StringはImmutableなクラスなので，実際に文字列を保持しているchar配列は，外部からアクセスができないようにしておく必要があります。ですので，ユーザーのコードが提供したchar配列をもとにStringのインスタンスを構築するときは，その配列を直接使うのではなくコピーした配列を値として保持するようにしています。
ですが，StringBufferはStringと同じパッケージであるという特権を生かして，使用していたchar配列を直接Stringにつかわせるという「ズル」をしています。で，StringBufferのほうで「もうStringにつかわれたから変更できない」ということを覚えておいて，StringBufferへのdeleteやreplaceが実行されたら，そのときはじめて自分でchar配列のコピーを作成して値を変更するという実装になってます。
ユーザー作成のStringBuffer互換コードでは，この手の「ズル」できないので，どうしてもchar配列のコピーが発生してしまい，パフォーマンスが悪くなってしまいます。
> SKMT。さん
JDK 5.0 のクラスライブラリでは、StringBuilder も StringBuffer も AbstractStringBuilder を継承しています。実装もほぼ一緒で StringBuffer から synchronized を除いたものが StringBuffer だと考えてもよいと思います。
速度差は synchronzied がない StringBuilder の方が JIT コンパイラ最適化が効きやすというのが大きいと思います。
JDK 1.4.2 への移植ですが StringBuffer.java のソースコードから synchronized メソッドを外すバージョンを作るのが第一歩だと思います。これを java.lang.StringAppender クラスと java.lang パッケージにして、-Xbootclasspath/a: オプションで JVM に認識させてやれば、JDK 5.0 と同条件での性能比較はできると思います。Takakiyo さんがおっしゃる内部配列の共有機能は、package 属性の String(int offset, int count, char value[]) というメソッドを使えば可能です。
JDK 5.0 のクラスライブラリでは、StringBuilder も StringBuffer も AbstractStringBuilder を継承しています。実装もほぼ一緒で StringBuffer から synchronized を除いたものが StringBuffer だと考えてもよいと思います。
速度差は synchronzied がない StringBuilder の方が JIT コンパイラ最適化が効きやすというのが大きいと思います。
JDK 1.4.2 への移植ですが StringBuffer.java のソースコードから synchronized メソッドを外すバージョンを作るのが第一歩だと思います。これを java.lang.StringAppender クラスと java.lang パッケージにして、-Xbootclasspath/a: オプションで JVM に認識させてやれば、JDK 5.0 と同条件での性能比較はできると思います。Takakiyo さんがおっしゃる内部配列の共有機能は、package 属性の String(int offset, int count, char value[]) というメソッドを使えば可能です。
SKMT。さんのコードを拝見しましたが、appendするオブジェクトのtoString()を呼び出すと、それだけでStringBuilderのappend以上の処理を行いますから、StringBuilderには勝てないでしょう。
また、SKMT。さんのコードでは、toString()の中でlength()を呼び出しており、length()中でもArrayListの全要素のtoString()を行っていますから、少なくとも2倍のコストがかかると思います。
nminoruさん(ごぶさたしてます)が書かれたとおり、十分に最適化されたコードを書けば、負けないくらい速くなると思いますが、あとは「finalクラスとする」というのも効くのではないかと思います。
また、SKMT。さんのコードでは、toString()の中でlength()を呼び出しており、length()中でもArrayListの全要素のtoString()を行っていますから、少なくとも2倍のコストがかかると思います。
nminoruさん(ごぶさたしてます)が書かれたとおり、十分に最適化されたコードを書けば、負けないくらい速くなると思いますが、あとは「finalクラスとする」というのも効くのではないかと思います。
> 3: Takakiyo さん
StringBuffer と String が char 配列を共有する実装は 5.0 からなくなりました。
個人的には以下のような理由だと推測しています。
1. StringBuffer の内部 char 配列は文字列のサイズよりも多めに確保されているが、
String が StringBuffer を共有するとダブついた char 配列を貰うことになる。
immutable な String がムダ領域を持ったままなのはムダが大きい。
2. StringBuffer の char 配列の初期値は 16 文字だが、String 化する前には何回も
expandCapacity しているのが現状。
3. 2. の状況あるから StringBuffer は escape analysis してスタックに割り付けたい。
しかし StringBuffer の char 配列を String に渡してしまうと、char 配列が脱出
してしまうのでスタックに割り付けられなくなる。
4. StringBuffer の各メソッドに shared 処理が入るので、インライン展開後の最適化
がやり辛くなる。
> 5: まえG さん
激しくご無沙汰しております。
今は XML 全盛のご時世で、現場では文字列処理の高速化が求められているようですが、プリミティブな文字列 API のレベルで最適化を行うのはもうかなり厳しいかも。もっと上位の最適化ができるといいんですが…
＃ プログラム中から頻出する検索パターン(String.indexOf("<xml")とか)を発見して
＃ specialized した検索ルーチンをインライン展開したコードに RedefineClass するとか。
StringBuffer と String が char 配列を共有する実装は 5.0 からなくなりました。
個人的には以下のような理由だと推測しています。
1. StringBuffer の内部 char 配列は文字列のサイズよりも多めに確保されているが、
String が StringBuffer を共有するとダブついた char 配列を貰うことになる。
immutable な String がムダ領域を持ったままなのはムダが大きい。
2. StringBuffer の char 配列の初期値は 16 文字だが、String 化する前には何回も
expandCapacity しているのが現状。
3. 2. の状況あるから StringBuffer は escape analysis してスタックに割り付けたい。
しかし StringBuffer の char 配列を String に渡してしまうと、char 配列が脱出
してしまうのでスタックに割り付けられなくなる。
4. StringBuffer の各メソッドに shared 処理が入るので、インライン展開後の最適化
がやり辛くなる。
> 5: まえG さん
激しくご無沙汰しております。
今は XML 全盛のご時世で、現場では文字列処理の高速化が求められているようですが、プリミティブな文字列 API のレベルで最適化を行うのはもうかなり厳しいかも。もっと上位の最適化ができるといいんですが…
＃ プログラム中から頻出する検索パターン(String.indexOf("<xml")とか)を発見して
＃ specialized した検索ルーチンをインライン展開したコードに RedefineClass するとか。
皆様色々とレスポンスどうもありがとうございます。
>あの 様
実は自分でもどうなっているのかと興味をいだき5.0のsrc.zipを解凍してコードを一瞥しました。
─ですが、実はご指摘のようにAbstractStringBuilder継承してるなぁ〜ってところで留まってます。
もうちょっと読んでみる必要がありそうです。
>たぁぼ 様
>要素を追加すると、新しい配列を作って配列ごとコピーする処理があります。
Listという名前ゆえに勝手に双方向リストなんだと思い込んでおりました。
最初Javaを学びはじめの頃は、パフォーマンスのことを全然考慮せずにVectorクラスを使っていて
その後自信満々にArrayListクラスを使っていましたが、まだパフォーマンス改善の余地はあったわけですね。
Java言語の奥深さを今更再認識します。
>Takakiyo 様
>ですが，StringBufferはStringと同じパッケージであるという特権を生かして，
>使用していたchar配列を直接Stringにつかわせるという「ズル」をしています。
パフォーマンス改善のために非常にアクロバティックなことしているんですね。
だた、ということはネイティヴコードっぽい改善ではなくアルゴリズム上での改善ってことですね。
>nminoru 様
(Takakiyo様へのレスとかぶってしまいますが)
String(int offset, int count, char value[]) メソッドはさっそく試してみたいと思います。
>まえG 様
>length()中でもArrayListの全要素のtoString()を行っていますから
確かにそうですね、ご指摘受けて気がつきました。
とはいうものの実際に自前でchar[]サイズ計算とStringオブジェクトの取得を同時に行うというのは非常に難しい問題だと認識しました。
></かつのり> 様
final予約語ってC言語でいうconstと同義だと思っていましたので、パフォーマンスに影響するかどうかは考えたこともありませんでした。
(総じて)
思っていた以上にStringBufferって沢山機能が実装されているんだなと感じました。
Javaを習得しはじめた当初はStringクラスが変更不可であることも知らずに+演算子で動的に変更可能だと勘違いしていましたので。
若干論点がずれるのですが、JakartaプロジェクトのCommons Lang(Premitiveでしたか??:すみません未確認です)にも興味があり、何かの記事かWebでJDK標準パッケージよりも「軽い」と書かれていたような気がしたのですが、パフォーマンス的な観点ではなかったのでしょうかね。
とりあえずさっそく色々とご教授いただいたアドバイスを参考に、リファクタしてみたいと思います。
ありがとうございました。
#
予想以上にレスポンスが多かったので現時点での全レスさせていただきましたが
タイムラグの都合上レスに入れられなかった方は申し訳ありません。
>あの 様
実は自分でもどうなっているのかと興味をいだき5.0のsrc.zipを解凍してコードを一瞥しました。
─ですが、実はご指摘のようにAbstractStringBuilder継承してるなぁ〜ってところで留まってます。
もうちょっと読んでみる必要がありそうです。
>たぁぼ 様
>要素を追加すると、新しい配列を作って配列ごとコピーする処理があります。
Listという名前ゆえに勝手に双方向リストなんだと思い込んでおりました。
最初Javaを学びはじめの頃は、パフォーマンスのことを全然考慮せずにVectorクラスを使っていて
その後自信満々にArrayListクラスを使っていましたが、まだパフォーマンス改善の余地はあったわけですね。
Java言語の奥深さを今更再認識します。
>Takakiyo 様
>ですが，StringBufferはStringと同じパッケージであるという特権を生かして，
>使用していたchar配列を直接Stringにつかわせるという「ズル」をしています。
パフォーマンス改善のために非常にアクロバティックなことしているんですね。
だた、ということはネイティヴコードっぽい改善ではなくアルゴリズム上での改善ってことですね。
>nminoru 様
(Takakiyo様へのレスとかぶってしまいますが)
String(int offset, int count, char value[]) メソッドはさっそく試してみたいと思います。
>まえG 様
>length()中でもArrayListの全要素のtoString()を行っていますから
確かにそうですね、ご指摘受けて気がつきました。
とはいうものの実際に自前でchar[]サイズ計算とStringオブジェクトの取得を同時に行うというのは非常に難しい問題だと認識しました。
></かつのり> 様
final予約語ってC言語でいうconstと同義だと思っていましたので、パフォーマンスに影響するかどうかは考えたこともありませんでした。
(総じて)
思っていた以上にStringBufferって沢山機能が実装されているんだなと感じました。
Javaを習得しはじめた当初はStringクラスが変更不可であることも知らずに+演算子で動的に変更可能だと勘違いしていましたので。
若干論点がずれるのですが、JakartaプロジェクトのCommons Lang(Premitiveでしたか??:すみません未確認です)にも興味があり、何かの記事かWebでJDK標準パッケージよりも「軽い」と書かれていたような気がしたのですが、パフォーマンス的な観点ではなかったのでしょうかね。
とりあえずさっそく色々とご教授いただいたアドバイスを参考に、リファクタしてみたいと思います。
ありがとうございました。
#
予想以上にレスポンスが多かったので現時点での全レスさせていただきましたが
タイムラグの都合上レスに入れられなかった方は申し訳ありません。
- mixiユーザー
- ログインしてコメントしよう！
|
|
|
|
Java 更新情報
-
最新のアンケート
-
まだ何もありません
-
