型変換による実行時コスト

.NETで外部ベンダー提供の DLL を使っているのだけれど、その中のあるメソッドの返値が符号付バイトの配列 sbyte で返ってくる。これを BinaryWriter.Writeを使って書き込みたいのだけれど、あいにくこのメソッドには sbyte を受け入れるオーバーロードがない。Write(sbyte)で 1 バイトずつ書き込んでもいいんだけど、毎秒3000回近く呼び出される箇所なのでメソッド呼び出しにかかるコストが気になる。

そこで BinaryWriter.Write(byte) で書き込むことにし、sbyte を符号無バイトの配列 byte[] に変換する方法を探る。しかし System.Convert や System.BitConverter のリファレンスを見ても適当なメソッドが無い。そこで http://www.ujihara.jp/CodeTips/VJSharp/ja/jslanguage.html を見ると、特にメソッドなど使わず、型変換をかませば目的を達成できるようだ。

この処理にかかる時間が配列の長さに比例するかどうかが気になる。リンク先には

JIT後のコードでは、変換の実行時コストはない

とあるので、中間言語のレベルで見てみよう。次のような C# のプログラムを用意した。

// ByteTest.cs

using System;
class ByteTest

{

    public static void Main(string[] argv)

    {

        byte[] bb = { 0, 50, 100, 150, 200, 250};

        sbyte[] ss = (sbyte[])((object)bb);

    }

}

object 型までアップキャストしてから打って返してダウンキャストする。このプログラムを実行可能形式にコンパイル後、中間言語に逆アセンブルしてみる。

>csc ByteTest.cs

>ildasm ByteTest.exe /out=ByteTest.il

できあがった ByteTest.il はテキストエディタで読める。ごちゃごちゃといろいろなおまじないがまとわりついているが、本体はここだろう。

  .method public hidebysig static void  Main(string[] argv) cil managed

  {

    .entrypoint

    // Code size       27 (0x1b)

    .maxstack  3

    .locals init (uint8[] V_0,

             int8[] V_1)

    IL_0000:  nop

    IL_0001:  ldc.i4.6

    IL_0002:  newarr     [mscorlib]System.Byte

    IL_0007:  dup

    IL_0008:  ldtoken    field valuetype '{934617AD-5A3F-4DA5-B4AC-E2247CF20B6B}'/'__StaticArrayInitTypeSize=6' '{934617AD-5A3F-4DA5-B4AC-E2247CF20B6B}'::'$$method0x6000001-1'

    IL_000d:  call       void [mscorlib]System.Runtime.CompilerServices.RuntimeHelpers::InitializeArray(class [mscorlib]System.Array,

                                                                                                        valuetype [mscorlib]System.RuntimeFieldHandle)

    IL_0012:  stloc.0

    IL_0013:  ldloc.0

    IL_0014:  castclass  int8[]

    IL_0019:  stloc.1

    IL_001a:  ret

  } // end of method ByteTest::Main

IL_0014 を見ると、キャストが一発で行なわれていることが分かる。ここまでやって思ったけど、castclass が配列の長さに依存しない定数時間で終わる保証はないので、問題の解決になってない気が・・・。 IL の仕様を調べねば。

DrSchemeでSICP

SICPのサンプルコードで、そのまま書いてもうまく動作しないものを解決する。DrScheme+Moduleという組み合わせを想定する。

trace の使い方
再帰的に定義された関数がどのように自分自身を呼び出しているのかを見るのに、trace という関数が使えるらしい。DrScheme+Module ではそのままでは使えないので、以下の一行をプログラムに追加する。

(require (lib "trace.ss"))

例えば、1.2.5 節の最大公約数の例なら

(require (lib "trace.ss"))
(define (gcd a b)
  (if (= b 0) 
      a
      (gcd b (remainder a b))))
(trace gcd)

とやっておけば、

(gcd 206 40)
|(gcd 206 40)
|(gcd 40 6)
|(gcd 6 4)
|(gcd 4 2)
|(gcd 2 0)
|2
2

となる。

runtime
問題 1.22 で、プログラムの実行時間計測のために runtime という関数が必要となる。これは

(define (runtime) (current-milliseconds))

と定義してやればよい。

nil
問題2.2.1以降で必要な nil は、空リストで定義しておく。

(define nil '())

初めての投稿

プログラミングを勉強する過程において、自分用のまとめとして書いていこうと思う。

ブログの書式に関してはいろいろ試していこうと思っている。プログラムを文中に掲載することが頻出すると思われる。この際、はてなダイアリーの引用形式だと気に入らない点が２つある。

1. 固定ピッチのフォントを使いたいところだがプロポーショナルフォントになってしまう。
2. 行頭のスペースが省略されてしまう。

どうやって解決しようか。
→ はてなダイアリーは HTML タグが使えるようなので、引用 >> << なぞ使わなくても <pre> タグを使えばOK。
<pre> タグの中では HTML のタグは無効になるが、はてな記法が有効のままになってしまう。はてな記法にスーパーpre記法 >||が用意されているのでこれをつかうことにする。