netail.net

_ 新歓 ▲

oucc の新歓コンパ．それなりにビールだけ飲む．50人もいると，さすがに食べ物はほとんどない．

毎年，敬語を使わない（使えない）１年生がいるのは仕方ないが，酒をつがれるときにグラスをどんと立てておくだけの（お礼も言わない）人間は初めて見た．放っておくと手酌で飲むし，ほとんど喋らないし（後半見てなかったけど），何なのだろう．

まあ，全体としては，人数も多くて，わりとノリのいい人間も多いので，それなりに好印象の学年ではある．問題は，何人残るか，だが……．

_ AspectJ ▲

AspectJ 情報で，若干，誤植等を訂正．

_ 論文 ▲

David Binkley and Mark Harman. Results From a Large-Scale Study of PerformanceOptimization Techniques for Source Code Analyses Based on Graph Reachability Algorithms. 3rd IEEE International Workshop on Source Code Analysis and Manipulation (SCAM 2003). 27th September 2003, Amsterdam, Netherlands. pages 203-212.

大規模 C プログラムに対するスライス計算をするときに，グラフを事前にどういじったらどのくらい高速化したか，という最適化の実験の話．

Strongly Connected Components の接続の１頂点化，SCC に対するデータ構造的なサポート導入，頂点のトポロジカルソート導入，推移的な辺の除去，というようにだんだん最適化している．

実験の適用対象はけっこう大規模で（というか他の論文と同じだが）100万行分くらい．とはいえ，全部で100万行なので，この書き方は誤解を招きそう．平均的には，３倍くらいの高速化をしている．

例によって，評価している時間はスライス計算の時間のみでグラフ構築時間を見ていない．実はグラフ構築に激しく時間かかってたりしないよなぁ，とちょっと邪推したくなるのだが．CodeSurfer を使ってる人たちで，SDG (System Dependence Graph) 構築時間について言及している人を，あまり見たことがない．昔はとても遅かったらしいが，今はどうなんだろう．

_ 論文 ▲

Laura K. Dillon, R.E.Kurt Stirewalt:Lightweight Analysis of Operational SpecificationsUsing Inference Graphs.

Operational Specifications というのはLOTOS などの形式言語のことらしく，色々な言語に対応するために式評価を Inference Graph としてアーキテクチャ構築で使うコンポーネント図みたいな部品を合成したデータフローグラフとして表現すれば，入力値が要らないものから順番に評価していけば結果が取れますね，という感じ．

何が lightweight なのかはよく分からないが，ルールベースで自動生成するところなのだろうか．inference graph の有用性はいまひとつ分からない．

_ 論文 ▲

David Binkley and Mark Harman. An Empirical Study of Predicate Dependence Levels and Trends 25th IEEE/ACM International Conference on Software Engineering (ICSE 2003). 3-10 May, 2003. Portland, Oregon, USA, Pages 330-339.

プログラムの中に登場する predicate から参照できる Formal parameters の数と，predicate で実際に使われるパラメータの数に関する統計を取ってみた，という論文．predicate の定義が曖昧だが，たぶん if など制御文などで使われる変数式全般．

対象のプログラムは20個の C プログラムで，最大で160KLOCくらい．Predicates per KLOC はどのプログラムでも変わらなかったらしい．

で，結果としては，使えるパラメータ数が増えていくに従って，だんだん参照可能なパラメータは増えていくが，実際に使われるパラメータはあまり増えないので，コンテキストへの依存度（使われる率）は下がっていくらしい．ただし，グローバル変数に関してはそういう関係がなく，グローバル変数が増えるほど使われる傾向にあったらしい．

で，依存度が低ければスライスサイズなども小さくなるので人間の労力を大きく削減できるだろう，ということになる．参照可能な Parameter の数さえ数えればだいたいの傾向がわかって，しかもそんなに計算コストは高くないので便利そう？これ単体で，どうこうできるものではないような気もするが．

_ 論文 ▲

David Binkley, Mark Harman:A Large-Scale Empirical Study of Forward and Backward Static Slice Size and Context Sensitivity.19th IEEE International Conference on Software Maintenance (ICSM 2003). Amsterdam, The Netherlands, 22-26 September 2003. Pages 44-53.

プログラムスライスを全部のスライス基点から計算することで統計的に比較をしている論文．実験時のスライス基点については，基点の選び方が効いてくるので，とりあえず全部計算するのがいい，と思っている様子．

対象プログラムは C で書かれた43プログラム，合計100万行ばかり．静的スライスの計算は CodeSurfer で計算されたもの．グラフ中でループになっているようなStrongly Connected Components (SCC) を１頂点として集約して，手続き内頂点はトポロジカルソートしてから，計算している．

グラフ構築は置いておいて，計算そのものは平均 3000KLOC/sec くらいのペースで処理が進んだらしい．(大きいものほど遅くて，100KLOC/sec を切るものもいくつか)

スライスサイズは，プログラム全体の７％~６０％程度．また，context-sensitive （ある手続きに複数の呼び出し文があるときにそれらを区別する）を省略すると，スライスサイズが sensitive なときの50％増しくらい（物によっては数倍）になったらしい．

ちなみに，forward slice と backward slice とを比べるとforward slice のほうがサイズが小さくなるらしい．何となく正しいような気はするけど．

context-sensitivity に関しては色々研究があるらしくて，呼び出し列を call string という文脈自由文法扱いにしてスライスサイズを減らすための情報に使うらしい．引用されているのは次の二つ．

Krinke, J.: Evaluation context-sensitive slicing and chopping. ICSM 2002, pp.22-31.

Agrawal, G. and Guo, L.: Evaluating explicitly context-sensitive program slicing. Workshop on Program Analysis for Software Tools and Engineering, pp.6-12, 2001.

_ [OUCC] PCトラブル ▲

おーさか＠OUCC様のPCが，BIOS画面にすら進まない謎の症状を出した．電源／メモリ／ビデオカードをそれぞれ動くものと交換してもダメだったので，マザーボードの不良ということにしておく．

_ [work] 査読とか ▲

この手の仕事が，先生を経由せずに直接依頼で発生するようになったのは，いちおう知名度が上がったということで，いいことなのか…．

_ ウィークリーマンションに移動 ▲

下宿引き払いに向けて，ウィークリーマンションに移動して，人に手伝ってもらって本棚など引き取ってもらった．

_ [hyCalendar] PCMode ６月号に掲載されてます ▲

「オンラインソフト鑑定団」という，ソフトウェアの価値を勝手に評価するという記事で取り上げられてます．

_ [Java] ファイルの一部だけ読む Reader ▲

既存のファイル処理コードに対して，手持ちファイルの一部だけをさも独立したファイルであるかのように読ませたかったので，あやしい Readerクラスを作成してみました．

このオブジェクトは，引数として与えられた Reader から，引数 pBegin バイト目から pEnd-1 バイト目までを読みます．long 値のオーバーフロー対策以外には特に工夫はありません．「読みすぎた分は単に捨てる」方式なので，元となった Reader が pEnd バイト目から続きを読めることも保証しません．

public class FileRangeReader extends Reader {
  private Reader r;
  private long size;   // どこまで読むか
  private long offset; // どこまで読んだか
  
  public FileRangeReader(Reader reader, long pBegin, long pEnd)
    throws IOException {
    r = reader;
    r.skip(pBegin);
    size = pEnd - pBegin;
    offset = 0;
  }
  @Override
  public void close() throws IOException {
    r.close();
  }
  @Override
  public int read(char[] buf, int off, int len) throws IOException {
    if (size == offset) return -1;
    int bytes = r.read(buf, off, len);
    if (offset > size - bytes) { // == offset + bytes > size.
      bytes = (int)(size - offset);
    }
    offset += bytes;
    return bytes;
  }
}

2個以上のReaderの中身をさも連続したストリームであるかのように読み込むReaderなんかも，上記のコードと同様に簡単に作成できるので，Decorator パターンはやっぱり強力だなと思います．良い設計かどうかはともかく，既存コードの変更量がとにかく少ない，というのがありがたいところです．

(追記: 2008/9/8) Reader は char 配列を読み込むため，ストリームのデータの中身を確認する必要があり，大量のデータを読み飛ばすには問題があるようです．InputStream をベースに同様のコードを作れば，byte単位で処理できるので，かなり高速になります．