パフォーマンスの飛躍的な改善には、2通りの方法があるようです。簡単なものと難しいものの2通りです。ありきたりのことを言っているわけではありません。両方の境界は、驚くほどはっきりとしています。

改善 (簡単なほう) があったと聞くと、拍手して「すごい」とか「それはそうだ」とか「すばらしい」と言います。それを最初に実現するのには、かなり非凡な才能が必要だったかもしれませんが、それを理解するのは簡単です。

もう一方の改善の場合、注意深い測定と、特殊な知識と、かなりの量の調整が必要とされます。これらの作業や知識は、多くの場合、具体的なハードウェアなどの「ローカルな条件」に良くも悪くも左右されます。

優秀なプログラマーは、「困難な」モードか「簡単な」モードのいずれかで作業を進めることができます。Linuxプログラマーにとってパフォーマンスは重要なテーマですので、実際の (プログラミングの) 世界からの難しい例と簡単な例を取り合わせて4つ紹介したいと思います。

いつでも最初は要件から

死と税金は、逃れられないものと相場が決まっています。プログラマーにとってそれと同じぐらい重要なのが、要件についての慎重な配慮です。それは、どんな 種類のプログラミングでも問題となることです。

パフォーマンスはもちろん重要なのですが、この要件に対処するための最善の方法は、必ずしもはっきりしているわけではありません。私は、ほぼ次のようなパターンに当てはまるソフトウェアの課題を何度も経験しています。プログラムが実際に使用されているというパターンです。機能的には何も問題がない。にもかかわらず、ユーザーは「これは遅すぎる」、高速化する必要があると言ってきます。そこで、チームの誰かがすぐに「モニター」を組み込んでやります。パフォーマンスを少し低下させることになりますが、長い処理のときにあとどれぐらい時間がかかるのかをユーザーに常に提示するのです。これでユーザーを満足させることができます。

私が最初にこの現象を観察したのは1960年代遅くで、以来どの時代にも、こうした現象を見受けます。多分ある意味では、コンピューターが利用され始めて以来、ずっとそうなのではないかと思います。重要なことは、エンド・ユーザーがだまされやすいとか、きらきらした装飾に目を奪われやすいといったことではありません。エンド・ユーザーには、われわれ専門家の狭い「パフォーマンス」という考え方よりも大きな目標があります。多くの場合、エンド・ユーザーが計算をもっと高速化する必要があるというときの本当の意味は、計算にどれぐらい時間がかかるのかを、もっと速く、信頼できる形で知りたいということなのです。そういう事実に関する正確な情報がわかれば、コンピューターに時間がかかる間、他の仕事に時間を割り当てることで満足できるわけです。

このように、パフォーマンスに関るすべての人にとって「準備運動」が必要となります。まず、要件管理に関する参考文献で好きなものを読んだり、読み返したりしてください。稿末の参考文献には、出発点として使えるものをいくつか掲げておきました。

次に、ユーザーへの情報提示が少なすぎると思ったときに簡単にアプリケーションに組み込むことのできる、小さな「プログレス・モニター」や「プログレス・バー」や「ストップウォッチ」をいくつかツールキットに用意しておいてください。以下の2つの例が示すように、これらのツールは、全然高価なものである必要はありません。

上に戻る

カウントダウンの2つの例

長い計算を行う際に同時にその進捗状況をユーザーに知らせるというのは、アプリケーション設計の際の興味深い問題の見本となっています。並行性 あるいは「マルチタスク処理」の例だからです。多くの開発者は、並行性を正しく実装するには、精巧なメカニズム、とくに難解なスレッド処理のコードが必要だと考えています。

それは正しくありません。稿末の参考文献には、以前に私が並行性に関係するテクノロジーとしてどんなものがあるのかを概観したdeveloperWorks の記事も示してあります。それに、少なくともkshがその「コプロセス」を標準化した1988年以降は、基本的にすべてのUNIXホストで簡単な並行プログラミングを行えるようになっています。以下のリスト1のkshのソースをex1.kshとして保存して実行すると、「10、9、8 ...」という「カウントダウン」が表示された後、kshのサブプロセスから「All done」という結果が表示されるはずです。実際に、時間のかかる化学の計算やデータベースの読み出しに、このようなものを利用できるかもしれません。処理はサブプロセスとして起動しておき、処理の内容や完了までにあとどれぐらい時間がかかるかを、つねにユーザーに示すわけです。表示の更新は、ソース・コードにして数行で足ります。

                (echo "This models a long-lasting process"; sleep 10;
                                        echo "All done") |&
        for ((i = 10; i > 0; i--))
        do
            printf "%2d seconds before completion ...\r" $i
            sleep 1
        done
        read -p line;      # Discard the title line.
        read -p line
        echo ""
        echo "Output from the sub-process is '$line'."

そこそこの量のコーディングで「リアルタイムな」情報をユーザーに表示することもできます。文字ベースのアプリケーションにおいても可能です。グラフィカル・ユーザ・インターフェース (GUI) のほうがよい場合でも、簡単なことです。多くのツールキットが「ビジー」とか「待機中」とか「進捗状況」の表示機能を内蔵しています。そういうものが手許にない場合でも、Tkなどの最近のGUIツールキットで何行か記述すれば、ちょっとした「アナログ式の」カウントダウン・クロックの文字盤やプログレス・バーを作り出すことができます。以下は「一から」作った場合の例で、数ページに納まる程度のものです。

                proc countdown {seconds} {
          init
          countdown_kernel $seconds
      }
      
      proc countdown_kernel seconds {
          hands $seconds
          if !$seconds return
          after 1000 [list countdown_kernel [incr seconds -1]]
      }
      
      proc draw_hand {angle decorations} {
          eval .c create line $::size $::size [get_xy $angle] $decorations
      }
      
      proc end_coordinate difference {
          set hand_length [expr $::size * .9]
          return [expr $::size + $hand_length * $difference]
      }
      
      proc get_xy angle {
          return [list [end_coordinate [expr sin($angle)]]\
                       [end_coordinate [expr -cos($angle)]]]
      }
      
      proc hands seconds {
          catch {.c delete withtag hands}
      set twopi 6.283185
          set seconds_angle [expr $seconds * $twopi / 60.]
          draw_hand $seconds_angle "-width 1 -tags hands"
          set minutes_angle [expr $seconds_angle / 60.]
          draw_hand $minutes_angle\
                       "-width 3 -capstyle projecting -tags hands"
      }
      proc init {} {
          catch {destroy .c}
          set ::size 30
          set full_diameter [expr 2 * $::size]
          pack [canvas .c -width $full_diameter -height $full_diameter]
          set border 2
          set diameter [expr 2 * $::size - $border]
          .c create oval $border $border\
                         $diameter $diameter\
                         -fill white -outline black
      }
      
      countdown 10

図1にあるように、このカウントダウンには分針と秒針が示されます。情報自体は、先のプログラムと同じです。

教訓: 情報を機能の代わりとすることができる。エンド・ユーザーは、アプリケーションの内部状態について多くのことが知らされるようになれば、要求することが少なくなります。プログラムが何を行っているのかを表示するようにするだけで、数多くのパフォーマンスに関する見かけ上の問題を解決することができます。

上に戻る

並べ換えは難しい

上は「簡単な」教えでした。とくにプログラミングに関する背景知識のない「一般読者」の方でも、その内容は理解できます。でも、並べ換えは「難しい」ほうに分類される問題です。それもそのはずです。Donald Knuth氏がコンピューター利用に関するその古典的叢書のまるまる1冊を並べ換えと検索に割いているのですから (参考文献には、Knuth氏のThe Art of Computer Programming の書評へのリンクを示してあります)。

並べ換えは、ある深い理由から、パフォーマンスに関する数多くの課題の中心になっています。つまり、パフォーマンスは、大規模な計算にだけ関係してくる問題だということです。人は一度に数個のものしか理解できませんので、われわれが長い時間を要するような大きな問題を把握するためには、それらのものを何らかのやり方で組織化したり構造化する必要があります。並べ換えは、その中の最も一般的な方法です。並べ換えられてあるリストは、線型的に検索するのではなく、バイナリー検索を行うことができます。そうすれば、たとえばニューヨーク市の電話帳を手作業で検索するような場合、100万の規模の問題を100万のlogの規模 (約14) の問題に簡単化することができます。

これは、並べ換え作業の典型的な例です。優れたアルゴリズムが、劣ったアルゴリズムの千倍とかそれ以上のパフォーマンスを示すこともよくあることです。賢く並べ換えを行えば、割にあうということです。

といっても、最も賢い方法は、並べ換えを行わないようにする、あるいは少なくとも気付かれることがないようなときにだけ行うことです。これは、データベース管理システムではよく行われることで、その恩恵として「挿入時」インデックス を作成できるということがあります。必要な場合には、並べ換えの結果をインデックスから直接得ることができます。要素の作成や挿入のぶんだけ少し処理時間が長くなるというコストが発生しますが、アプリケーションのワークフローが一般的なものなら、ユーザーがそれに気付くことはありません。

Knuthの文献には、他にもBoyer-MooreとかRabin-Karpなど、個々の特殊な状況での並べ換えを高速化するための技法がたくさん説明されています。これらいろいろな種類の技法に共通な1つの原理は、特殊な問題より一般的な問題のほうが簡単に解決できるということです。数学者は、このことをよく知っています。複素数の計算のほうが実数の計算より面倒だけれども、代数学の一般的な問題は、実数で考えるより複素数で考えたほうが扱いやすいということがあります。

そこで思い出されるのが「装飾・並べ換え・装飾除去 (decorate-sort-undecorate: DSU)」です。以下のようなデータ集合があるとします。

    "Jane Jones" -> 15,000
    "Dan Smith"  ->  6,000
    "Kim Black"  -> 40,000

このとき、名前を、対応する収入で並べ換えたいとします。素朴な方法で行うとすると、並べ換え用のライブラリーのエントリー・ポイントに、Kim Blackの40,000はDan Smithの6,000よりも大きいので、Kim Blackのほうが先にくるというような結果を出す比較関数を指定することになるでしょう。簡明な方法であり、小規模な問題ならこれで用が足ります。

しかし、これよりもはるかに 効率的なのが、とくに、生物科学や金融などの分野でよく行われているように、一度に100万件の並べ換えを行うような場合、わざわざ特別な「リバース・テーブル」を作成するという方法です。この処理に時間はかかりますが、並べ換えは非常に高速になります。Pythonのリスト操作機能を使えば、これを極めて簡潔に表現することができます。しかし、同じ原理は、皆さんがお持ちのどんな言語にでも当てはまることです。

                
      decorated = [ (revenues[name], name) for name in name_list ]
      decorated.sort()
      for (revenue, name) in decorated:
          print "%14s: %8d" % (name, revenue)

得られたデータ集合を並べ換えると、全体的な処理を簡単に1桁あるいはそれ以上に高速化することができます。コンピューターで複雑な計算を行うことは、学生にとって難しい部類の問題のようですが、こうした高速化をもたらす場合には、そのような計算に価値があることは明らかです。

上に戻る

500倍速く

自営のコンサルタントAlex Martelli氏は、昨年、もっと劇的な改善を行っています。彼がPython Business Forumのメーリング・リストで語っているところによると、彼が実装したXMLプロセッサーは、処理を完了するのに8時間かかっていたそうです。それは容認できないことでした。エンド・ユーザーは、そんな長い時間待っていることができませんでした。そこで、いろいろと修正を行ったところ、処理時間を1分にすることができたというのです。なんと一番最初の500倍です。

まず、Python内蔵のXMLライブラリーを専用のpyRXPパーサーに切り換えました。これは、以前にdeveloperWorks に掲載されたXMLの処理性能に関する記事で紹介されたものと同じpyRXPです。記事へのリンクは、参考文献を参照してください。pyRXPは、処理サイクルの使用を節約するだけでなく、Python用の他のXMLエンジンに比べ、メモリーの占有量も劇的に減らしています。メモリーの占有量は、とてつもなく重要なことで、パフォーマンスに関する数多くの障害の典型です。アプリケーションは、メモリー不足で苦しんでいるのです。形式的には適切なアルゴリズムであっても、スワッッピングを必要とするほどに大量のメモリーを使用する場合、破滅的なまでに処理速度を低下させることがあります。それがMartelli氏の最大の問題でした。

したがって、代わりとなる別の製品やアルゴリズムを評価する場合、その外見上のスループットをテストするだけでなく、メモリーへの影響もテストする必要があります。多くの場合、この後者によって、実動アプリケーションの実際上の拡張性が決まってきます。また、よく行われることですが、パフォーマンスに関する問題をハードウェアによって解決することにした場合、まずはメモリーを増設することを検討してください。メイン・メモリーの増設は、劇的な結果を生み出すことの多い安価な実験だと言えます。

これは、第2の簡単な教訓です。メモリーを増やし、現在あるメモリーを有効に活用せよ。メモリーが重要であることは、マネージャーを含め、多くの人が理解しているようです。

上に戻る

ディスク・ドライブは疑ってみる価値がある

パフォーマンス向上を切望している人への最後のヒントは、ディスク・ドライブに疑いをもつということです。大容量記憶装置は、この数10年の間、記憶密度や信頼性に関して驚くべき進歩を遂げてきましたが、私が最近目にしているところでは、少なくとも何社かのメーカーは装置の動作品質を薄っぺらなものにしすぎているような気がします。その結果、すぐに故障するユニットがあったり、さらにそれよりずっと多いのがパフォーマンスの変動するユニットです。

注意深く測定してみないと、ディスク・サブシステムの本当の平均アクセス時間やスループットはわかりません。とくに大容量記憶装置がRAID、SAN、その他の最近のテクノロジーを利用したものである場合に、これが問題となることがあります。頻繁に読み書きに失敗しているのは、ある特定のユニットなのかもしれませんが、アプリケーション・レベルでは、全体的なパフォーマンスが妙に変動することしかわかりません。たとえば、RAIDユニットのスピンドル1個がまるまる駄目になっているために、あるプログラムの経過時間のほとんどがRAIDユニット内でのエラー訂正に費やされているといったことが簡単に起こったりします。

これには、どんな対処が可能なのでしょうか。いろいろな対処方法があるのですが、マニュアルにはきちんとした説明がありません。私が知ってい方法は、たいてい、システム管理者が内輪で伝えている話です。それを、いくつかまとめておきます。

• 信頼できる装置を購入すること。大容量記憶装置は、最低価格で買うのではなく、信頼できるものに金を費やしてもよい類の製品です。
• 多くを望んではならない。SAN、最新世代のSCSI、gigaetherストレージ、その他の製品の善し悪しについては、他のところから聞くとよいでしょう。
• 購入する製品の測定値を調べる。ディスク・ドライブ自体でパフォーマンスや温度などの使用環境をモニターするものを見つけ出してくるとよいでしょう。また、装置がどの程度のパフォーマンスを示すのかを把握しておくために記録をとっておくとよいでしょう。かなり大きなプロジェクトになると、きっと 不可解な動きをするディスクも現れてくることでしょう。不具合が発生しだしてから原因の究明を図るよりも、基礎データを記録しておいたほうが、はるかに賢明です。

パフォーマンスの改善は、編み出したり、実装するのに数分しかかからないものもあれば、実際に使いものになるまでに何日も研究しないといけないものもあります。アプリケーションの速度の本当の限界を見いだすためには、パフォーマンスに関する難しい問題と簡単な問題の両方に取り組む用意が必要です。

参考文献

• 要件確認についての文献のこのページは、Usenetのニュースグループcomp.software-engの情報を基にしたものです。
  
  
• 大人のための並行性は、スレッド処理以外にもいろいろなマルチタスキングの手法があることを解説しています。
  
  
• Cameronのkshに関する個人的なページ には、いろいろなことが可能なこの面白い言語についてのさまざまな参考文献を紹介しています。必ずksh93をインストールしてください。Linuxのディストリビューションには、デフォルトでksh88をインストールするものがたくさんあります。
  
  
• Donald Knuth著のThe Art of Computer Programming についてのDanny Yeeの書評では、Knuth氏が並べ換えと検索 を格調高く扱っていることの背景が少し紹介されています。
  
  
• Brian Goetz氏は、Java言語を使ったプロジェクトで彼が観察してきたパフォーマンスに関するごく一般的な間違いについて、いくつか解説しています。
  
  
• 古くからのServer/Workstation Expert には、ストレージの概念や使い方に関する優れたコラムが掲載されています。今でも読む価値があります。大容量記憶装置を管理するときの難しい問題に対する最新の手ほどきで、これに匹敵するものを見たことがありません。
  
  
• IBMのストレージ製品の詳細については、IBMのTotalStorage のページを参照してください。
  
  
• ドライブ、バックアップ装置、SANなどの管理に関するTivoliの業務内容については、Tivoli Storage Managementのページが良い出発点となります。
  
  
• developerWorks のLinuxゾーンには、他にもLinux開発者向けの参考文献が多数掲載されています。
  
  

著者について

Cameronは、Phaseit, Inc. の常勤のコンサルタントです。オープン・ソースなどの技術的なトピックについて、数々の執筆や発言を行っています。Cameronのメール・アドレスはclaird@phaseit.net です。

この記事を評価する

コメント

上に戻る

目次

• いつでも最初は要件から
• カウントダウンの2つの例
• 並べ換えは難しい
• 500倍速く
• ディスク・ドライブは疑ってみる価値がある
• 参考文献
• 著者について
• コメント