Mar 27, 2011

64bit整数を使わないという、js-ctypesの最適化ノウハウ

先に結論だけ書くと、

  • js-ctypesでCのライブラリから帰ってきた64ビット整数を32ビット整数2つで代用できる場面では、32ビット整数にしておいた方が何倍も速くなることがある
  • ctypes.uint32_tとctypes.unsigned_longが同じ意味になる場合(Win32/Win64など)はctypes.uint32_tを使った方がいい

という話です。以下、実際にどういうケースでこれが役立つかの説明です。

素直に書くと凄く遅くなる場合

先日、システムモニターのFirefox 4対応版をリリースしました。で、リンク先に書いてあるとおり、0.6.0からFirefox 4ではjs-ctypesを使うようになってます。

これを機に初めてjs-ctypesを使ったのですが、前のエントリでちょっと触れている通り、今までCで書いてた物をそのままJavaScriptで書き直しただけだととんでもなくパフォーマンスが落ちる事があります。自分は64ビット整数が絡む場面でそういう問題に遭遇しました。

背景を説明しますと、Windows環境ではGetProcessMemoryInfo()という関数を使うとプロセス毎のメモリ使用量の情報を取得できるのですが、この方法で取れる値はWindows Vista以降のタスクマネージャでの「メモリ(プライベート ワーキング セット)」ではなく「メモリ(コミット サイズ)」の方の値になってしまいます。メモリ使用量が多めに表示されてしまうため、これは精神衛生上良くないです。タスクマネージャの表示と同じ値を出したい場合はMSDNの記事のコメント欄に書かれているプライベートワーキングセットの計算方法を使わないといけません。

この方法の実装例はWebを検索するといくつか見つかりますが、基本的には以下の流れとなります。

  1. まず、1回QueryWorkingSet()を呼んで、確保しないといけないメモリのサイズを求める。
  2. 調べたサイズでメモリを確保する。
  3. 再度QueryWorkingSet()を呼び、ワーキングセットの詳細な情報の配列を受け取る。
  4. 配列の各要素について「共有されている領域かどうか」を判定し、共有されていない領域の個数を調べる。
  5. 4で求めた個数×ページサイズ=「プライベートワーキングセット」として表示される使用メモリ量(単位:バイト)となる。

Cで書くとこんな感じになります。Firefox 3.6用のバイナリもこういう感じのコードに基づいています。

#include <windows.h>
#include <psapi.h>
#include <prmem.h>

typedef struct CL_Memory CL_Memory;
struct CL_Memory {
    PRUint64 total;
    PRUint64 free;
    PRUint64 used;
    PRUint64 virtualUsed;
    PRUint64 self;
};

CL_Memory
CL_GetMemory()
{
    // 全体の消費メモリと空きメモリの情報を得る。
    MEMORYSTATUSEX memory;
    memory.dwLength=sizeof(memory);
    GlobalMemoryStatusEx(&memory);

    // ページサイズを得る。
    SYSTEM_INFO systemInfo;
    GetSystemInfo(&systemInfo);

    // 1回目のトライでページ数を得る。
    ULONG_PTR self[1];
    QueryWorkingSet(GetCurrentProcess(),
                    (PVOID*) &self,
                    sizeof(self));

    ULONG_PTR selfUsage = 0;
    // 1回目のトライで得たページ数+1(最初の1個目はページ数が入る)の
    // 配列のためのメモリを確保する。
    DWORD pagesCount = self[0] + 1;
    ULONG_PTR *actualSelf = (ULONG_PTR *) PR_Malloc(pagesCount, sizeof(ULONG_PTR));
    // 2回目のトライでワーキングセットの詳細な情報を得る。
    if (QueryWorkingSet(GetCurrentProcess(),
                        (PVOID*) actualSelf,
                        pagesCount * sizeof(ULONG_PTR)) != 0) {
      for (ULONG_PTR i = 1; i < pagesCount; i++) {
        // 下から9番目のビットが立っていなければプライベートワーキングセット
        if (!(actualSelf[i] & 0x100)) {
          selfUsage++;
        }
      }
      selfUsage = selfUsage * systemInfo.dwPageSize;
    }

    PR_Free(actualSelf);

    CL_Memory info = {
        memory.ullTotalPhys,                             // total
        memory.ullAvailPhys,                             // free
        memory.ullTotalPhys - memory.ullAvailPhys,       // used,
        selfUsage                                        // self
    };
    return info;
}

これをjs-ctypesを使ってそのまま同じロジックでJavaScriptに移植すると、以下のようになります。

Components.utils.import('resource://gre/modules/ctypes.jsm');

const is64bit = Cc['@mozilla.org/xre/app-info;1']
                    .getService(Ci.nsIXULAppInfo)
                    .QueryInterface(Ci.nsIXULRuntime)
                    .XPCOMABI.indexOf('_64') > -1;

// 型をWindowsプログラミング風の名前で用意しておく。
const NTSTATUS  = ctypes.uint32_t;
const WORD      = ctypes.unsigned_short;
const DWORD     = ctypes.uint32_t;
const DWORDLONG = ctypes.uint64_t;
const BOOL      = ctypes.int;
const HANDLE    = ctypes.intptr_t;
const ULONG_PTR = is64bit ? ctypes.uint64_t : ctypes.unsigned_long ;
const PVOID     = ctypes.voidptr_t;
const LPVOID    = ctypes.voidptr_t;
const DWORD_PTR = ULONG_PTR;

// 使用する構造体の定義をひたすら書く。
// 先に型名をすべて定義しておいたので、
// MSDN等からコピペしやすくなってる。
const MEMORYSTATUSEX = new ctypes.StructType('MEMORYSTATUSEX', [
        { dwLength                : DWORD },
        { dwMemoryLoad            : DWORD },
        { ullTotalPhys            : DWORDLONG },
        { ullAvailPhys            : DWORDLONG },
        { ullTotalPageFile        : DWORDLONG },
        { ullAvailPageFile        : DWORDLONG },
        { ullTotalVirtual         : DWORDLONG },
        { ullAvailVirtual         : DWORDLONG },
        { ullAvailExtendedVirtual : DWORDLONG }
    ]);

const SYSTEM_INFO = new ctypes.StructType('SYSTEM_INFO', [
        { dwOemID    : DWORD },
        { dwPageSize : DWORD },
        { lpMinimumApplicationAddress : LPVOID },
        { lpMaximumApplicationAddress : LPVOID },
        { dwActiveProcessorMask   : DWORD_PTR },
        { dwNumberOfProcessors    : DWORD },
        { dwProcessorType         : DWORD },
        { dwAllocationGranularity : DWORD },
        { wProcessorLevel         : WORD },
        { wProcessorRevision      : WORD }
    ]);

const PSAPI_WORKING_SET_INFORMATION_FIRST = new ctypes.StructType(
    'PSAPI_WORKING_SET_INFORMATION_FIRST', [
        { NumberOfEntries : ULONG_PTR },
        { WorkingSetInfo  : ctypes.ArrayType(ULONG_PTR, 1) }
    ]);

// DLLをオープンする。
// js-ctypesではシステムコールを呼ぶのにも
// 必ず何らかのDLLを介さないといけない。
const gKernel32 = ctypes.open('kernel32.dll');
const gPsapi = ctypes.open('psapi.dll');

// 使う関数を定義する。
// ここも、型名はWindowsプログラミング風のスタイルで書くと
// MSDNの資料と見比べやすくなると思う。
const GlobalMemoryStatusEx = gKernel32.declare(
        'GlobalMemoryStatusEx',
        ctypes.default_abi,
        NTSTATUS,
        MEMORYSTATUSEX.ptr
    );
const GetCurrentProcess = gKernel32.declare(
        'GetCurrentProcess',
        ctypes.default_abi,
        HANDLE
    );
const GetSystemInfo = gKernel32.declare(
        'GetSystemInfo',
        ctypes.default_abi,
        ctypes.void_t,
        SYSTEM_INFO.ptr
    );
const QueryWorkingSet = gPsapi.declare(
        'QueryWorkingSet',
        ctypes.default_abi,
        BOOL,
        HANDLE,
        PVOID,
        DWORD
    );

// 問題の処理
function getMemory() {
    // 全体の消費メモリと空きメモリの情報を得る。
    var info = new MEMORYSTATUSEX(MEMORYSTATUSEX.size, 0, 0, 0, 0, 0, 0, 0, 0);
    GlobalMemoryStatusEx(info.address());

    // ページサイズを得る。
    var systemInfo = new SYSTEM_INFO();
    GetSystemInfo(systemInfo.address());

    // 1回目のトライでページ数を得る。
    var self = new PSAPI_WORKING_SET_INFORMATION_FIRST();
    QueryWorkingSet(GetCurrentProcess(),
                    self.address(),
                    PSAPI_WORKING_SET_INFORMATION_FIRST.size);

    var selfUsage = 0;
    // 1回目のトライで得たページ数に基づく構造体を定義する。
    // メモリはjs-ctypesが自動的に確保してくれる。
    var pagesCount = self.NumberOfEntries;
    var PSAPI_WORKING_SET_INFORMATION = new ctypes.StructType
        ('PSAPI_WORKING_SET_INFORMATION', [
            { NumberOfEntries : ULONG_PTR },
            { WorkingSetInfo  : ctypes.ArrayType(ULONG_PTR, pagesCount) }
        ]);
    var actualSelf = new PSAPI_WORKING_SET_INFORMATION();
    // 2回目のトライでワーキングセットの詳細な情報を得る。
    if (QueryWorkingSet(GetCurrentProcess(),
                        actualSelf.address(),
                        PSAPI_WORKING_SET_INFORMATION.size) != 0) {
      let pages = actualSelf.WorkingSetInfo;
      for (let i = 0; i < pagesCount; i++) {
        // 下から9番目のビットが立っていなければプライベートワーキングセット
        if (!(pages[i] & 0x100)) {
          selfUsage++;
        }
      }
      selfUsage = selfUsage * systemInfo.dwPageSize;
    }

    // 確保したメモリの解放はjs-ctypesでは基本的にガーベジコレクト任せ。
    actualSelf = undefined;
    PSAPI_WORKING_SET_INFORMATION = undefined;

    return {
        total       : info.ullTotalPhys,
        free        : info.ullAvailPhys,
        used        : info.ullTotalPhys - info.ullAvailPhys,
        virtualUsed : info.ullTotalVirtual - info.ullAvailVirtual,
        self        : selfUsage
    };
}

構造体とか関数とかの定義がズラズラ並んでるのが見苦しいし冗長だとは思うのですが、js-ctypesだとCのヘッダファイルをインクルードできないので、こうするしかないのです。なお、構造体を使っているためこのコードはFirefox 3.6では動作しません(構造体のサポートはFirefox 4から)。

で、実際これを動かしてみると、Cで書いた物に比べて物凄く遅くなってしまいました。いくらJITが効いているとはいっても限界はあるよね……というのもあるにはあるのですが、それにしても遅い。Cなら1ミリ秒とかかってなかったものが、JavaScriptだとテスト環境では120ミリ秒くらいかかる。システムモニターでは既定の設定だと1秒(1000ミリ秒)ごとに1回グラフを更新するので、このテスト環境の場合、CPU使用率は常に10%以上の値に貼り付いてしまう事になり、さすが実用的とは言いがたいです。

なんでこんなに遅いのか調べてみたら、遅いのは案の定ループの所でした。前述のロジックだと、例えば消費メモリが共有部分も含めて300MBでページサイズが4KBなら、76800回ループが回るわけです。上記の手法でしか正確なメモリ使用量を計測できないとなると、(配列の全部の要素に対して特定のビットが立っているかどうかを判定しないといけないという都合上、ループの数を減らすわけにはいかないので)これ以上の高速化はどう見ても不可能に思えます。

32ビット整数で高速化

という事でしばらく悩みながらコードをああでもないこうでもないといじっていたら、不意に、ループの部分は一切変更してないのにテスト環境上で処理が20ミリ秒前後で終わるようになってしまいました。

一体何故!? と思ってよく見たら、

var PSAPI_WORKING_SET_INFORMATION = new ctypes.StructType
    ('PSAPI_WORKING_SET_INFORMATION', [
        { NumberOfEntries : ULONG_PTR },
        { WorkingSetInfo  : ctypes.ArrayType(ULONG_PTR, pagesCount) }
    ]);

ここの所を何の間違いか

var PSAPI_WORKING_SET_INFORMATION = new ctypes.StructType
    ('PSAPI_WORKING_SET_INFORMATION', [
        { NumberOfEntries : ULONG_PTR },
        { WorkingSetInfo  : ctypes.ArrayType(ctypes.uint32_t, pagesCount) }
    ]);

と書いていたのが原因でした。

型の違いでどうしてこんなにも速度差が出てしまうのか。これは、JavaScriptのプリミティブな数値がIEEE 754の倍精度浮動小数点数、64ビット浮動小数点数だからというのが理由のようです。

JavaScriptの仕様上、正の整数は最大で53ビットの範囲までしか正確に表現できません。ところがその一方で、Cのライブラリは64ビットの整数を扱うことも多い。そこで、js-ctypesではInt64とUInt64というクラスを専用に用意して、64ビットの整数はこのクラスのインスタンスとして入出力するようになってます。

JavaScriptの仕様では、数値をビット演算しようとすると必ず32ビット整数に内部的に変換される事になっています。なので、UInt64(...).valueOf()してNumber()してそのうち下位32ビットだけを取り出して……という変換処理が何万回と走るループの中で毎回行われて、それが原因で処理に時間がかかっているのではないかと考えられます。

一方、32ビット整数の範囲であればJavaScriptのプリミティブな数値で十分に表現可能なため、js-ctypes経由で32ビット整数型で値を取り出した場合はその時点で既にプリミティブ値になっており、ループの中で上記の変換処理が必要なくなります。

これを踏まえて、配列の内容を64ビット整数ではなく32ビット整数で扱うようにすると、js-ctypesでの実装は以下のようになります。

var selfUsage = 0;
// 1回目のトライで得たページ数に基づく構造体を定義する。
// メモリはjs-ctypesが自動的に確保してくれる。
var pagesCount = self.NumberOfEntries;
// 64ビット環境の場合は、64ビット整数の配列を32ビット整数の配列で代用するので、
// 配列の長さを2倍しておく。
if (is64bit) pagesCount = pagesCount * 2;
var PSAPI_WORKING_SET_INFORMATION = new ctypes.StructType
    ('PSAPI_WORKING_SET_INFORMATION', [
        { NumberOfEntries : ULONG_PTR },
        // 常に32ビット整数型で配列を定義する。
        { WorkingSetInfo  : ctypes.ArrayType(ctypes.uint32_t, pagesCount) }
    ]);
var actualSelf = new PSAPI_WORKING_SET_INFORMATION();
// 2回目のトライでワーキングセットの詳細な情報を得る。
if (QueryWorkingSet(GetCurrentProcess(),
                    actualSelf.address(),
                    PSAPI_WORKING_SET_INFORMATION.size) != 0) {
  let pages = actualSelf.WorkingSetInfo;
  // 下位32ビットの情報を含む要素だけを対象にループを回す。
  let step = is64bit ? 2 : 1 ;
  for (let i = is64bit ? 1 : 0; i < pagesCount; i += step) {
    // 下から9番目のビットが立っていなければプライベートワーキングセット
    if (!(pages[i] & 0x100)) {
      selfUsage++;
    }
  }
  selfUsage = selfUsage * systemInfo.dwPageSize;
}

僕のテスト環境だと、これは元のバージョンに比べて5~6倍高速に動作しました。それでもCPU使用率に若干影響は与えます(例えば20ミリ秒かかればCPU使用率でいうと2%くらいは食ってる事になる)が、元に比べればずっとマシなので今の所は良しとしましょう。

疑問1:ctypes.unsigned_long型じゃ駄目なの?

QueryWorkingSet()で取得できるワーキングセットの情報の配列の要素の型はULONG_PTRですが、これは64ビット環境(Win64)だとctypes.uint64_t、そうでなければctypes.unsigned_longになります。Win32ではunsigned longは32ビット整数なので、ということは、32ビット環境なら上記のような高速化のために敢えてctypes.uint32_tを使わなくてもいいんじゃないのか? という疑問は当然浮かぶでしょう。

実際そう思って、配列の要素の型をctypes.unsigned_longにして実験してみたのですが、これは全然速くなりませんでした。alert(new ctypes.unsigned_long(0))としてみるとctypes.unsigned_long(ctypes.UInt64("0"))と表示されることから分かるように、ctypes.unsigned_long型の値は内部では64ビットで処理されてしまうようです。

調べてみた所、C言語の64ビットへの対応方法には色々あるらしく、Mac OS X ServerやLinuxの64ビット版のようにLP64というデータモデルを採用している環境では、unsigned longという型は64ビット整数になるそうです。なので、混乱を避けるためかjs-ctypesではunsigned long型の変数にJavaScriptから触る時は必ず64ビット整数に変換されるように統一しているという事だそうです。

ちなみに、alert(new ctypes.uint32_t(0))とした場合はctypes.uint32_t(0)と表示されて、JavaScriptのプリミティブ値になっていることが分かります。

疑問2:UInt64.lo()じゃ駄目なの?

Int64UInt64のクラスメソッドを使うと、64ビット整数の上位32ビットや下位32ビットをJavaScriptのプリミティブな数値として取得することができます。という事は、これを使えば配列の長さを32ビット環境と64ビット環境で変えたりといった面倒な事はしなくてもいいんじゃないのか? という疑問も浮かびました。

という事で、試しに以下のようにしてみました。

var selfUsage = 0;
var pagesCount = self.NumberOfEntries;
var PSAPI_WORKING_SET_INFORMATION = new ctypes.StructType
    ('PSAPI_WORKING_SET_INFORMATION', [
        { NumberOfEntries : ULONG_PTR },
        { WorkingSetInfo  : ctypes.ArrayType(ULONG_PTR, pagesCount) }
    ]);
var actualSelf = new PSAPI_WORKING_SET_INFORMATION();
if (QueryWorkingSet(GetCurrentProcess(),
                    actualSelf.address(),
                    PSAPI_WORKING_SET_INFORMATION.size) != 0) {
  let pages = actualSelf.WorkingSetInfo;
  for (let i = 0; i < pagesCount; i++) {
    if (!(ctypes.UInt64.lo(pages[i]) & 0x100)) {
      selfUsage++;
    }
  }
  selfUsage = selfUsage * systemInfo.dwPageSize;
}

これは最初のバージョンに比べると2倍ほど高速でした(テスト環境での所要時間は50ミリ秒ほど)が、32ビット整数の配列として取得するようにした場合に比べると2倍ほど遅いとも言えます。今回の例のように32ビット整数を直接取り出せるような場合(64ビット整数の配列を32ビット整数の配列で代用するなど)では、最初からそうしておいた方がずっと速いということですね。

疑問3:64ビットの整数でちゃんと計算しないといけない時は?

上記の実装だと、おそらく64ビット環境で使用メモリのページ数が53ビットの範囲を超えたあたりから正確な値を取れなくなってくると思われます。今回はシステムモニターというわりとどうでもいい機能の実装ですし、しかも、ページサイズが4KBならこの問題が起こるのは消費メモリの量が32エクサバイト(4KB×1024×1024×1024×1024×1024)の頃になるので、当面は無視して構わない問題でしょう。

とはいえ、ちゃんと64ビットの整数を計算しないといけない場面というのもあるとは思います。

残念ながら、js-ctypesではこの辺に対するフォローがほとんどありません。64ビットの整数同士を足したい時は自分でこういう関数を書いてねなんてオフィシャルのドキュメントに書いてあるくらいです。幸い、64ビットの整数を扱うためのライブラリは既にいくつかありますので、ライセンスや使い勝手や速度などの点で適当な物を選んで組み合わせて使うといいでしょう。

結論

64ビット整数まじわけわかんね!

あと、上記のJavaScriptのコードはそのまま使うとメモリリークになりますので注意が必要です

エントリを編集します。

wikieditish message: Ready to edit this entry.











拡張機能