2013-03-29

Java の BlockingQueue 実装の性能を比較してみた

Posted on 2013-03-29, 2:22 in

巷では「ArrayBlockingQueue よりも LinkedBlockingQueue の方がスループット性能がいいよ」なんてまことしやかに言われているけど、どうにも気になったので検証してみたら、実は ArrayBlockingQueue の方が性能いいんじゃない? という結論に至った話です。

Producer-Consumer デザインパターンと BlockingQueue

Java で Producer-Consumer デザインパターン を実現するときによくお世話になる BlockingQueue インタフェース。このインタフェースには ArrayBlockingQueue クラスLinkedBlockingQueue クラス の二つの実装が標準 API として提供されています。

高い処理性能を要求されるプログラムを Java で書こうとしたときに、CPU のすべてのコアをフル稼動させることを狙って Producer-Consumer パターンによって処理フローをパイプライン的に構成することがあります。そのときにいつも気になっていたのが、「ArrayBlockingQueue と LinkedBlockingQueue、果たしてどちらを利用した方がスループットが高くなるのだろうか?」ということ。

この疑問に対して、海外でも 議論 されていたり、検証 されていたりされているようで、それらの 結論 としては概ね「LinkedBlockingQueue の方が ArrayBlockingQueue よりも高スループットだよ」というものになっています。

しかし、ArrayBlockingQueue と LinkedBlockingQueue の双方の実装やデータ構造の特性を考えると「LinkedBlockingQueue の方が高スループット」という結論がにわかに信じ難かったので、実際に検証をしてみることにしました。

双方のデータ構造と実装の特性

検証を始める前にまず、それぞれのデータ構造および実装の特性を確認してみることにします。参考にした実装は Oracle の JDK 1.7 (update 17) です。

ArrayBlockingQueue クラス

  • 配列をベースとしたキュー実装で、配列をリングバッファとして扱います。
    • エンキュー (add() / offer() / put()) 操作、デキュー (remove() / poll() / take()) 操作をする配列上のインデックスを、それぞれ別々に保持しています (putIndex フィールドと takeIndex フィールド)。
  • キューの大きさは固定長で、その大きさを超える要素数を保持することはできません。
  • エンキュー操作において、余計なオブジェクトが生成されることはありません。
  • エンキュー/デキュー操作では、一つのロックオブジェクト (lock フィールドの ReentrantLock オブジェクト) を共用して排他制御をします。
    • エンキューとデキュー操作のメソッド呼び出しが重なると、一方の処理にてロック解除待ちが生じてしまいます。

LinkedBlockingQueue クラス

  • 片方向の連結リストをベースとしたキュー実装です。
    • 要素の数に応じて、リストが伸長・縮退します。
  • 連結リストの先頭 (head フィールド) より要素をデキューし、末尾 (last フィールド) に要素をエンキューします。
  • 保持できる要素数は最大で Integer.MAX_VALUE になります。
    • コンストラクタで capacity を指定することで、保持する要素数を制限することもできます。
  • 要素のエンキュー操作ごとに、連結リストの Node オブジェクトの生成操作が発生します。
    • 1 つの要素につき 16 バイトほどのヒープを余計に消費します。
  • エンキュー/デキュー操作の排他制御はそれぞれ別々のロックオブジェクト (putLock フィールド、takeLock フィールド) を利用します。
    • エンキューとデキュー操作のメソッド呼び出しが重なったとしても、ロック解除待ちは発生せず並列に処理することができます。

これら上記の双方の特性を比較すると、

  • ArrayBlockingQueue は処理が単純な分、エンキュー/デキュー操作の処理コストが小さく、一方で LinkedBlockingQueue はオブジェクト生成が必要となるために特にエンキュー操作の処理コストが高い。
  • ArrayBlockingQueue は、エンキュー/デキュー操作においてロックオブジェクトを共有するために Producer / Consumer の並列性が低くなるが、LinkedBlockingQueue は別々のロックオブジェクトが用意されているため、Producer / Consumer の並列性が高まる。

と言うことができそうです。 LinkedBlockingQueue の方がスループットが高い、というのは後者の並列性が根拠になっていると思われますね。

性能検証する

続いて、実際に両者の BlockingQueue 実装を利用したプログラムを作成し、各種性能を測定してみました。

測定方法

検証用プログラム を用いて、エンキュー操作、デキュー操作を独立して 1,600 万回ほど行ったときの処理時間、およびエンキュー/デキュー操作を複数の別スレッド (Producer / Consumer) で同時並列に 1,600 万回実施したときのスループットを ArrayBlockingQueue, LinkedBlockingQueue それぞれの実装ごとに測定してみました。

また測定を進めていく上で、Java VM の 32 bit と 64 bit の違いや、Java コンパイラ (JDK / Eclipse)、ハードウェア・OS (Windows / Mac) の違いが性能に影響を与えることが明らかになったため、これらの構成の組み合わせも合わせて検証してみることにしました。

検証環境

  • ハードウェア・OS
    • Windows PC
      • Windows 7 (64 bit)
      • Core i5-3450 (3.10GHz)
      • 8GB Memory
    • Mac
      • Mac OS X 10.8.2
      • 1.7GHz Core i5-3317U
      • 4GB Memory
  • Java
    • Java VM (オプション : Xms1200m)
      • Java 7 Update 17 (32 bit & 64 bit)
    • Java コンパイラ
      • JDK 1.7 Update 17
      • Eclipse Compiler for Java 3.8.2

測定項目

  • エンキュー/デキュー操作を行う各種メソッドの呼び出しにかかる時間 [ミリ秒]
    • エンキュー
      • add()
      • offer()
      • put()
    • デキュー
      • remove()
      • poll()
      • take()
  • スループット [メッセージ/秒]
    • Producer x 1 スレッド, Consumer x 1 スレッド
    • Producer x 1 スレッド, Consumer x 2 スレッド
    • Producer x 2 スレッド, Consumer x 1 スレッド
    • Producer x 2 スレッド, Consumer x 2 スレッド

測定結果と考察

上記の内容で測定した結果を Google ドキュメントで公開 しています。数値に対するカラースケールは行(横一列)のグループに対して設定されており、緑色が良い性能であることを、黄色がほどほどの性能を、赤色が性能が悪いことを示します。

Java VM (64 bit / 32 bit) の違い

さてこの結果を見てすぐに分かることは、ArrayBlockingQueue と LinkedBlockingQueue のどちらについても、32 bit Java VM よりも 64 bit の方が性能がよい、ということになりますね。メソッド単体の呼び出し性能もスループットも、どちらも下は 1.5x から上は 4x ぐらいまでの性能が 64 bit VM では出ています。

メソッドの呼び出し性能に着目すると、32 bit VM ではメソッド間で性能差が大きく開きバラつきがあり、ArrayBlockingQueue も LinkedBlockingQueue もそれぞれの性能特徴がよく分かる結果となっています。一方で 64 bit VM では、メソッド間の性能差は 32 bit ほどの開きは見られず、安定した性能が出せていることがうかがえます。

スループットについては、64 bit VM を使うことで ArrayBlockingQueue の性能が 32 bit VM のときより大幅に性能向上することが見て取れます。LinkedBlockingQueue も 64 bit VM による性能劣化はなく、ArrayBlockingQueue ほどではないものの多少の性能向上がうかがえます。

Java VM の違いにおいて ArrayBlockingQueue と LinkedBlockingQueue の結果を比較すると、

  • 32 bit VM では LinkedBlockingQueue の方が性能がよい。
  • 64 bit VM では ArrayBlockingQueue の方が性能がよい。

と言えるでしょう。

Java コンパイラ (JDK / Eclipse) の違い

コンパイラの違いについては、今回の測定結果では優劣が明確になるほどの性能差は出ませんでした。

ハードウェア・OS の違い

Mac の場合、ArrayBlockingQueue と比べて LinkedBlockingQueue の性能が全体的に悪いことがわかります。メソッドの呼び出しについては、特にエンキュー操作の性能が極端に悪いですね。

スループットも、エンキュー操作メソッドの性能に引きづられてか、LinkedBlockingQueue の性能は芳しくありません。エンキュー操作が競合しやすい Producer x 2 の構成での落ち込みが大きいですね。

Mac では、 ArrayBlockingQueue 択一 と言ってしまっていいと思います。

まとめ

ArrayBlockingQueue を使うべきか、それとも LinkedBlockingQueue を使うべきかの判断は Java VM 次第、すなわち

  • (Mac を含む) 64 bit の Java VM を利用するなら ArrayBlockingQueue がよい。
  • 32 bit の Java VM なら LinkedBlockingQueue がよい。

と言ってしまっていいでしょう。ただ今後のことを考えれば 64 bit VM の利用が多くなっていくと考えられるため、開発時点では 32 bit の VM 利用を想定していても、ArrayBlockingQueue を採用しておくのが無難じゃないかと思います。はい。

だいじなこと

今回は Windows と Mac とで性能検証をしてきたのですが、実際に Java アプリが利用される環境は Linux など Unix 系の OS が多いかと思います。今回の検証でなんとなく傾向はつかめた (64 bit なら ArrayBlockingQueue) のですが、これがそのまま Linux でも通じるかどうかはまた別の話、つまりは要検証、ということです。

31 件のコメント

  1. 32bit版の性能について、HotSpot ClientVMが使われているということはないでしょうか?
    64bit版は、HotSpot ServerVMだけなので、32bit版でClientVMが使われていると最適化レベルが違うため、性能に差がでることはあります。

    返信削除
  2. なるほど、ServerVM と ClientVM の違いでしたか。
    それは全然考慮できていませんでした。

    確認・追試をしてみたいと思います。
    ありがとうございます!

    返信削除
  3. Awesome..You have clearly explained …Its very useful for me to know about new things..Keep on blogging..
    Oracle -apps-technical-course.html Online Training

    Oracle-bpm Online Training

    返信削除
  4. Blog is very informative. Thanks for sharing!
    http://www.kitsonlinetrainings.com/oracle-adf-online-training.html
    http://www.kitsonlinetrainings.com/oracle-apps-functional-online-training.html

    返信削除
  5. you are able to take the help of experts making a call at QuickBooks Payroll Support Phone Number
    Well! If you’re not in a position to customize employee payroll in.

    返信削除
  6. Our Professionals have designed services in a competent means so that they will offer the required solutions to the shoppers. we've got a tendency to at QuickBooks client Service are accessible 24*7 you merely have to call our QuickBook Customer Support Number that you can get available on the market on our website.

    返信削除
  7. Can be executed every user task with QuickBooks Payroll Tech Support Number Accounting software. Therefore you merely desire to install QuickBooks Payroll software and fetch the details, rest all the essential calculation will soon be done automatically as a result of the software.

    返信削除
  8. The most common errors faced by the QuickBooks users is unknown errors thrown by QuickBooks software at the time of software update. To help you to correct the problem, you need to look at your internet and firewall setting, internet browser setting and system time and date setting you can simply contact us at QuickBooks Customer Support Number for instant assistance in QB issues.

    返信削除
  9. Intuit has pops up many accounting software like Quicken , Intuit Tax Online Accountant, QuickBooks GoPayment, Mint,TaxCaster by TurboTax,MyTaxRefund by TurboTax,TurboTax SnapTax,Online Payroll, QuickBooks Online however the users of Quickbooks are far more than other products . Even though you make a search in the Google Quickbooks Support Number you will likely confused when a so many number comes up into the search results ,because Intuit is dealing with so many products that why each product and each region they getting the different Tech Support official .

    返信削除
  10. You don’t have to strain yourself about the safety and privacy of your data as this issue can be resolved with the help of QuickBooks Support Phone Number at toll-free number in minimum time. There are a number of possible reasons of this issue. A number of the reasons include-

    返信削除
  11. We've got experienced individuals to provde the figure. We will also provide you with the figure within your budget which you are able to get in the near future from now. This will be only possible with QuickBooks Tech Support Phone Number.

    返信削除
  12. Get prominent options for QuickBooks near you right away! Without any doubts, QuickBooks has revolutionized the process of doing accounting this is the core strength for small in addition to large-sized businesses. QuickBooks Support Phone Number is assisted by our customer support specialists who answr fully your call instantly and resolve all of your issues at that moment.

    返信削除
  13. No matter if you're getting performance errors or perhaps you are facing any kind of trouble to upgrade your software to its latest version, you can easily quickly get help with Quickbooks Support Number. Every time you dial QuickBooks 2018 technical support phone number, your queries get instantly solved. Moreover, you will get in touch with our professional technicians via our email and chat support options for prompt resolution of all of the related issues.

    返信削除
  14. The reason us different is quality of one's services inside the given time interval. The locus of your services may be based upon delivering services in shortest span of that time period, without compromising aided by the quality of your services. Our support team is engaged in pre-research to create themselves prepared in advance for the possible errors of QuickBooks. This practice helps them produce you the specified wind up in the given time window. QuickBooks Tech Support Number are there to assist you 24*7 as we try not to disassociate ourselves together with your troubles even through the wee hours.

    返信削除
  15. If any method or technology you can not understand, if that's the case your better option is which will make call us at our QuickBooks Support Phone Number platform.

    返信削除
  16. Intuit QuickBooks Tech Support Number will likely not accept direct deposit fees, however, $2.00 monthly fees are imposed when you have one client. Clients may have own logins to process own payment after they intend to customize Intuit online payroll.

    返信削除
  17. Enhanced QuickBooks Tech Support Number and Full-service payroll are encompassed in Online Payroll whereas Basic, Enhanced and Assisted Payroll come under Payroll for Desktop.

    返信削除
  18. When you have recently come across a peculiar QuickBooks error, specifically, QuickBooks Error 3371 “QuickBooks could not load license data. This might be brought on by a missing or damaged file.” with a status code of 11118, you are not alone. This dilemma is prevalent amidst lots of users who use QuickBooks for accounting purposes.

    返信削除
  19. “Just dial our QuickBooks Payroll Support Phone Number to inquire of about for Quickbooks Payroll customer service to get rid of payroll issues. We make use of startups to small-scale, medium-sized to multinational companies.”

    返信削除
  20. QuickBooks Enterprise Support Phone Number has almost eliminated the typical accounting process. Along with a wide range of tools and automations, it provides a wide range of industry verticals with specialized reporting formats and tools

    返信削除
  21. The QuickBooks Payroll Support Phone Number software has tight security. Thus, all of your data are safe. You are able to put the password over there. This might protect the contents.

    返信削除
  22. Our support also also contains handling those errors that always occur once your type of QuickBook Enterprise Technical Support Number happens to be infected by a malicious program like a virus or a spyware, which may have deleted system files, or damaged registry entries.

    返信削除
  23. QuickBooks has now reached the pinnacle of popularity due to its time saving accounting features. No, doubt this software handles almost every areas of business accounting with an excellent ease along with secured network to its users to receive and send files. QuickBooks Support Phone Number is designed to give you the instant resolution of every QuickBooks issues along with round the clock tech assistance into the software. Through this web site, I will be discussing the annoying update errors that arise while updating the software. This error generally arises as a result of misconfigured system file which causes registry errors in operating system.

    返信削除
  24. We suggest anyone to join our services just giving ring at toll-free QuickBooks Enterprise Help Number to enable you to fix registration, installation, import expert and plenty of other related issues to the enterprise version. Also, you can fix accessibility, report mailing & stock related issues in quickbooks enterprise software. 24×7 available techies are well-experienced, certified and competent to correct all specialized issues in an experienced manner.

    返信削除
  25. Don’t worry we have been always here to aid you. As you are able to dial our Quickbooks Support Number. Our QB online payroll support team provide proper guidance to fix all issue connected with it. I will be glad that will help you.

    返信削除
  26. QuickBooks software program is developed in such a manner that it will supply you with the best account management reference to this era. However, you could face the issue with your QuickBooks Support Phone Number + 1888-567-1159 software and begin trying to find the clear answer. You should not worries,

    返信削除
  27. Reach us at QuickBooks Tech Phone Number at and experience our efficient tech support team of many your software related issues. If you're aa QuickBooks enterprise user, it is possible to reach us out immediately at our QuickBooks Support contact number .

    返信削除
  28. QuickBooks Enterprise Tech Support Number offers an extensive financial solution, where it keeps all your valuable business accounting requirements in a single place. From estimates to bank transfers, invoicing to tracking your expenses and staying in addition to bookkeeping when it comes to tax time, it really is prepared for all of it at one go.

    返信削除
  29. QuickBooks Payroll Tech Support Number requires below described information to help you to customize desktop or online account fully for payment processing in quite a reliable manner. Within the next step, you can find information through the last service provider.

    返信削除
  30. QuickBooks Error Code 6000-301 occurs when accessing the company file in Quickbooks accounting software. This error could be brought on by various defect and damages to QuickBooks desktop. QuickBooks Error -6000, -301 encounters while wanting to use a desktop company file.

    返信削除