読者です 読者をやめる 読者になる 読者になる

たまにゃんのメモ帳

情報系関連のメモ書きを主に載せていきます。あわよくば他の人の参考になれば...

Node.js でサーバーサイド Javascript を始める

サーバーサイドJavaScriptをずっと使いたいと思いつつ、機会がなかったが。ちょうどいい機会があったので勉強。

Node で Webアプリケーションを簡単に作成するためのツール

いくつか便利なパッケージを見つけたのでいくつか紹介する。
npm(Node.jsのパッケージマネージャー)ですべて簡単にインストールすることができる。
自分はCoffeeScriptが好きなのでCoffeeScriptで開発する予定

  1. Socket.IO
    • WebSocketのNode.js実装
  2. Mongoose
    • node.js 向けに開発された MongoDB アクセスライブラリ
  3. Express
  4. EJS
    • テンプレートエンジン
  5. twitter-bootstrap-node
    • Express で Twitter Bootstrap を簡単に扱うことができる
  6. node-dev
    • Node.jsのプログラムをファイルを書き換えた時に自動で再起動してくれる
  7. js2coffee
    • javaScriptを逆コンパイルしてCoffeeScriptになおしてくれる

簡単なテンプレートの作成例として

$ twitter-bootstrap -t ejs project # EJSを使う
$ cd project && npm install
$ js2coffee app.js > app.coffee
$ js2coffee routes/index.js > routes/index.coffee
$ node-dev app.js # 開発用

なおtwitter-bootstrap-nodeを使う上でバグがあったので、/usr/local/bin/twitter-bootstrapを少し修正

396 - json += '    , "less": ">= 0.0.1"' + eol;
396 + json += '    , "less": "1.3.3"' + eol;

もしくは毎回Packcage.jsonを書き換える必要がある。
バグ修正はgithubのtwitter-bootstrap-nodeに同じ内容のバグが上がっていたのでそれを参考にした。

Expressを少し使ってみた感想として、割りと直感的に扱えるフレームワークだと思った。
ただMVCのMの方は何も用意されてなくない??
Mongooseを使えばいいのかな??

>> 追記
githubのtwitter-bootstrap-nodeにPull Requestを送ったらマージされたのでバグ修正されたと思う。

参考URL

Boosting Multi-Core Reachability Performance with Shared Hash Tables (2010)

URL : http://fmcad10.iaik.tugraz.at/Papers/papers/12Session11/033Laarman.pdf

  1. Abstract
    • この論文はモデル検査アルゴリズムとその他検証手法において重要なキーコンポーネントであるマルチコアReachabiliyのためのデータ構造について焦点を当てる。
    • 我々が提案する共有ストレージはロックレスなハッシュテーブルで実装がベースになっておりスケーラビリティもある。
    • モダンCPUのキャッシュアーキテクチャの考慮して実装された。
  2. Introduction
    • この論文ではSPINやDiVinEのようなマルチコアモデル検査器が共有の状態のストレージとしてコンカレントハッシュテーブルを扱うことで性能を改善させる。
    • Contribution
      • 効率的なコンカレント状態ストレージのデータ構造の提案をする。
      • これによって多くの探索アルゴリズムに対しReachabiliyを持ったスケール可能な並列アルゴリズムの実装を可能にする。
    • Overview
      • Section 2 : Reachability, Load Balancing, Hashing, Parallel Algorithms, Multi-Core Systems のバックグラウンドについて述べる
      • Section 3 : 共有の状態ストレージとして設計されたロックレスなハッシュテーブルについて述べる。しかし、高速な並列アルゴリズムがその上で動くという前提条件の元で評価を行う。
      • Section 4 : DiVinE や SPIN において評価を行う。例題はBEEM databaseを用いる。
  3. Preliminaries
  4. A Lockless Hash Table
    • ハッシュテーブルの要件
      • find-or-put
        • 削除とかは考えなくてよく状態を見つけるか挿入するかの2つだけを考えれば良い
        • ただマルチスレッド環境において同時のアクセスに対して保証しなくてはならない
        • find-or-putという特徴を利用することでアルゴリズムを単純化して、メモリへの負担を下げてそれぞれのコアのキャッシュライン共有を避ける
      • 基本的にはそれぞれの状態にポインタを使うことを避ける
        • 64bitマシンにおいては無視できない量になる
      • find-or-putの時間的効率性は並列実行のプロセス数によってスケールしなくてはならない
    • Hash Table Design
      • Open addressing
      • Walking-the-line
        • Double Hashingによってキャッシュライン上に Linear Probingを提供する。
      • Separated data
        • 索引づけされたデータの配列
      • Hash memoization
      • Lockless
      • Compare-and-swap
    • Hash Table Operations
    • -
  5. Experiments

The ComBack Method – Extending Hash Compaction with Backtracking (2007)

URL : http://link.springer.com/content/pdf/10.1007%2F978-3-540-73094-1_26.pdf

大雑把にいえば状態を持たずにハッシュ値と状態の一意のID(整数)と状態へのバックエッジ(遷移関数、前の状態の一意のID)を持ち、ハッシュ値がぶつかった場合バックエッジで最初の状態root(かもしくはキャッシュされた状態)へたどり再度状態を復元する手法。
状態遷移が軽く、状態のメモリ消費量が多いモデル検査においては非常に効果を発揮しそう。

  1. Abstract
    • ComBack Method は Hash Compaction を拡張し、状態空間のすべてのカバレッジが保証するような手法。
    • それぞれの状態を一意で表現する整数と展開前の状態へのバックエッジを保持する。
    • これで、バックトラックを使うことですべての状態識別子を構築しなおし、Hash Compaction のハッシュ衝突の問題を on-the-fly に解決する
  2. Background
    • Hash Compaction Method
      • Hash Compaction の基本的なアイデアは状態Sから固定サイズのbit-stringの集合にマップする関数Hを使うこと
      • それぞれ訪問した状態sに対して、状態管理表にを完全な状態識別子を登録するのではなく、ハッシュ値のみを保存する
  3. The ComBack Method
    • 完全な状態識別子を持つことなく、オンデマンドにバックトラックキングを使うことで状態管理表に完全な状態識別子を再構築し、ハッシュの衝突を解決する。
    • 完全な状態識別子を再構築するには以下のやり方を用いる
      1. すべての訪問した状態にstate number N(s)を割り当てる
      2. state tableはそれぞれの圧縮状態識別子のcollision listを保存する。collision listとはこの圧縮状態識別子へマップされた訪問先の状態へのstate numberのリストである。
      3. backedge table は訪問された状態へのバックエッジを保存する。状態 s への backedge は transition t と state number nで構成されている。前の状態を s' とすると s' (t)→ s
  4. The ComBack Algorithm
m ← 1
StateTable.Init() StateTable.Insert(H(sI),1)) 
WaitingSet.Init() WaitingSet.Insert(sI,1) 
BackEdgeTable.Init() BackEdgeTable.Insert(1, ⊥)
while ¬ WaitingSet.Empty() do
    (s, n′ ) ← WaitingSet.Select()
    for all t,s′ such that (s,t,s′) ∈ ⊿ do
        if ¬ Contains(s′) then
            m←m+1 StateTable.Insert(H(s′), m) 
            WaitingSet.Insert(s′, m) 
            BackEdgeTable.Insert(m, (n′ , t))

proc Contains(s′) is
    for all n ∈ StateTable.Lookup(H(s′)) do
        if Matches(n, s′) then 
            return tt
        return ff

proc Matches(n, s′) is
    return s′ = Reconstruct(n)
                    
proc Reconstruct(n) is 
    if n = 1 then
        return sI 
    else
        (n′ , t) ← BackEdgeTable.Lookup(n) 
        s ← Reconstruct(n′)
        return Execute(s,t)

Concurrency without Locking in Parallel Hash Structures used for Data Processing(2012)

URL : http://www.waset.org/journals/waset/v61/v61-5.pdf

  1. Abstract
    • ロックとかセマフォとかバリアーとか従来の方法ではなく、現代のマルチスレッドアーキテクチャにおいてより有効な別の方法とマルチスレッドでのConcurrent Hash Tableについて考える。
    • 特にメモリシステムとメモリアクセスの特性にフォーカスを当てた環境ので並列ハッシュテーブルの効果についての理解を目的とする。
  2. Introduction
    • 高速化のためにはアルゴリズムの計算量、データ移動のコスト、メモリのレイアウト、データ構造の使用パターンなどが重要である。
    • この論文の目的は、主なパフォーマンス要因を特定し、その要因を計測することで、マルチコアCPUを有効活用するための様々な方法を提供する。
    • この研究のモチベーションは大規模WebのLogデータの処理である
    • データ処理にはハッシュテーブル必要だよね
    • 構成
      1. 現在の環境において並列アルゴリズムのパフォーマンスの要因を特定し、ロックを使ったハッシュテーブルの近年の研究を述べる
      2. 従来のロックを使う方法を説明する
      3. ロックとかセマフォとか伝統的な同期手法を使わないでそれぞれのスレッドが協力するようなロックフリーなハッシュテーブルの詳細な実装方法について述べる
      4. 計測結果を従来の方法と改善した方法で評価し分析する
      5. まとめ
  3. 関連研究
    • 逐次処理におけるパフォーマンスの要因 
      • パフォーマンスでも最も重要なのは計算量
      • データ、メモリ集約型のアプリケーションにおいて、パフォーマンスで次に重要なのはメモリアクセスの特性
    • 並列実行と排他処理
      • ハッシュテーブルの並列処理のいくつかの実装方法はロックを利用した同期方法を利用している。一つのハッシュテーブルレベルでのロックは簡単にボトルネックになりうる。それゆえ、改善するために発展させなければならない。
      • 2ロックレベル(グローバルのロックとそれぞれのバケットのロック)
      • リーダーとライターのロック
  4. Concurrent Hash Table の実装
    1. Rule-Based Cooperation
      • 従来のロックベースのシナリオと比べて一種の逆の作業割り当てをする
      • nスレッドでn個の領域に分解し、それぞれのスレッドがその領域を担当する
  5. 計測と結果
    • 3種類のタイプの実装を比較
      1. high-level section lock(2種類のロック?)
      2. CAS
      3. rule-based co-operation
    • 計測マシン
    • 50%の挿入と50%の参照と10%の挿入と90の参照の2つを計測

Windows デバイスドライバ 概念図

  • ただ暇つぶしにIRPの流れを書いた。後悔はしていない。

型理論

アップキャスト
あるクラスBaseと、Baseから派生したクラスDerivedがあるとする。アップキャストとは、派生クラスから基底クラスへの型変換、すなわちDerivedのインスタンスをBaseに変換する操作である。

ダウンキャスト
基底クラスから派生クラスへの型変換、すなわちBaseのインスタンスをDerivedに変換する操作である。

ファイル内の文字列検索

$ find . -name "*.py" | xargs grep sys