SICP 1.2
1.2 手続きとその生成するプロセス
1.2.1
再帰的プロセス(recursive process)と反復的プロセス(iterative process)
手続きの定義の中で自分自身を再帰的に呼び出していく。
SICPで勉強を始めた時(=ソフトウェアの仕事を始めたばかりの頃)、最も関心したのがこの部分。
インタプリタが保持すべき情報量のオーダーがO(1)なのかO(n)なのか。
反復プロセスの場合、常に一定の記憶量でループを処理する事が可能。
C,Pascal等では反復的プロセスを行いたくとも、再帰呼び出しの際に
スタックを次々消費していくよう設計されている。
反復プロセスにはfor,while等の特殊なループ構造が必要。
また、Schemeの実装は末尾再帰的(固定記憶領域で再帰呼び出しが可能な性質)である事が
IEEE企画で定められている。
1.2.3
計算量(O(n))の話
1.2.5 / 1.2.6
若干数学寄りの話なので略
SICP 1.1
SICPの復習も兼ねて、学んだ内容を自分なりに噛み砕くため、
大枠と必要なら詳細をブログに書いてみる事にした。
不定期に。
1.1 プログラムの要素
1.1.1
schemeの演算規則など、基本的な文法説明。
1.1.2
defineと環境(大域環境の説明)
1.1.4
合成手続きの説明と実例。
defineについて再度説明。
defineによる手続きの定義は、すなわちその環境における手続きに対する名称の対応付けである。
1.1.5
置き換えモデルの説明。
3章で説明が出てくるが、set!等の破壊的代入が導入されるとこのモデルは破綻する。
作用的順序(applicative-order evaluation)と正規順序(normal-order evaluation)の違い。
実際にインタプリタが採用しているのは作用的順序(単純な展開ではなく、引数の評価と作用を行う)
schemeの式を眺めたとき、全ての部分式を展開するといった解釈方法は誤り。
1.1.6
condと特殊形式if
ifは何故特殊形式なのか?
- > (if predicate consequent alternative)
のcons.とalt.は共に単一の式で無ければならない。
q1.5
- > 正規順序によるインタプリタでは、処理が無限ループに入る。
1.1.7
小数・分数の扱い方の違い
まとめ
1.1はschemeの言語としての部品と処理系に関する基本的な話。
以上、終わり。
concurrency & parallel
SICPを読んでいたら並列性(concurrently)が出てきたので、
coucurrencyとparallelの違いについて調べてみた。
日本語訳ではconcurrencyが並行でparallelが並列らしい。
SICPでの訳と逆だけど、まぁこれは日本語の問題なので略。
http://stackoverflow.com/questions/1050222/concurrency-vs-parallelism-what-is-the-difference
ここでの議論から引用。
coucurrency:2つ以上のプロセスが同一期間に実行可能状態(開始、実行、終了)にある事。
プロセスは必ずしも同じ瞬間(同時刻)に実行されていなくても良い。
→シングルコア、マルチタスク(TSSによる時分割実行でも可)
parallel:2つ以上のプロセスが真に同時刻に実行される事。
→マルチコア、マルチタスク
というニュアンスらしい。
概念的にはconcurrencyがparallelを内包している、という関係。
以上。
openFrameworks + ofxBox2dでハマったのでメモ
OFことopenFrameworksに興味が出たので、田所淳氏のサイトhttp://yoppa.org/で
公開している"Beyond Interaction"を参考に色々触っていたら、addon(ofxBox2d)の導入でビルドエラーが出てつまづいた。
ググってみるとofxBox2dのサンプルビルドで躓いている人が多数なようなので、
簡易メモとして残す事に。
環境は64bit Ubuntu 12.04LTS & OF 0.7.4 (-> 0.8.1に入れ替え)
結論としては、openFrameworksとofxBox2dのバージョンが
合っていなかった事が原因。
* ofxBox2dの入手
git clone git://github.com/vanderlin/ofxBox2d.git
* README.md
Compatibilityの項より、使ってるOFのバージョンに合わせてcheckoutせよ、
と書いてあるものの、branchもtagも切っていない模様?
何故???
とりあえずこれをgit cloneし、OF 0.7.4で使用していたため、
Beyond Interactionに掲載のソースをビルドした際にコンパイル時にエラーが多発。
OF0.8.1に入れ替え、コードを数ヶ所書き換えたら動作しました。
* testApp.h (OF 0.8.1ではofApp.hにrename)
#ifndef _TEST_APP #define _TEST_APP #pragma once #include "ofMain.h" /* #include "ofxVectorMath.h" */ #include "ofxBox2d.h" class testApp : public ofBaseApp{ public: void setup(); void update(); void draw(); void keyPressed (int key); void keyReleased(int key); void mouseMoved(int x, int y ); void mouseDragged(int x, int y, int button); void mousePressed(int x, int y, int button); void mouseReleased(int x, int y, int button); void windowResized(int w, int h); void dragEvent(ofDragInfo dragInfo); void gotMessage(ofMessage msg); ofxBox2d box2d; /* vector <ofxBox2dCircle> circles; */ vector <ofPtr<ofxBox2dCircle> > circles; }; #endif
* testApp.cpp (OF 0.8.1ではofApp.cppにrename)
#include "ofApp.h" //-------------------------------------------------------------- void ofApp::setup(){ ofSetVerticalSync(true); ofBackground(0, 0, 0); box2d.init(); box2d.setGravity(0, 5); box2d.createBounds(0, 0, ofGetWidth(), ofGetHeight()); box2d.setFPS(30); } //-------------------------------------------------------------- void ofApp::update(){ box2d.update(); } //-------------------------------------------------------------- void ofApp::draw(){ for (int i = 0; i < circles.size(); i++){ circles[i].get()->draw(); // circles[i].draw(); } box2d.draw(); } //-------------------------------------------------------------- void ofApp::keyPressed(int key){ } //-------------------------------------------------------------- void ofApp::keyReleased(int key){ } //-------------------------------------------------------------- void ofApp::mouseMoved(int x, int y ){ } //-------------------------------------------------------------- void ofApp::mouseDragged(int x, int y, int button){ } //-------------------------------------------------------------- void ofApp::mousePressed(int x, int y, int button){ float r = ofRandom(10, 40); // ofxBox2dCircle circle; // circles.setPhysics(1.0, 0.8, 0.5); // circles.setup(box2d.getWorld(), mouseX, mouseY, r); ofPtr<ofxBox2dCircle> circle = ofPtr<ofxBox2dCircle>(new ofxBox2dCircle); circle.get()->setPhysics(1.0, 0.8, 0.5); circle.get()->setup(box2d.getWorld(), mouseX, mouseY, r); circles.push_back(circle); } //-------------------------------------------------------------- void ofApp::mouseReleased(int x, int y, int button){ } //-------------------------------------------------------------- void ofApp::windowResized(int w, int h){ } //-------------------------------------------------------------- void ofApp::gotMessage(ofMessage msg){ } //-------------------------------------------------------------- void ofApp::dragEvent(ofDragInfo dragInfo){ }
上記のようにソースコードを変更後、makeを実行する事でビルドが成功。
以上、メモ書きまで。
cache bounce
キャッシュバウンスなる物を始めて知ったのでメモ。
情報系の学生さんなら講義で学ぶのだろうか。
cache line bouncing
http://arighi.blogspot.jp/2008/12/cacheline-bouncing.html
・マルチプロセッサ環境(各プロセッサ毎にキャッシュ有)でマルチスレッドなプログラムを想定
・変数A、変数BはそれぞれスレッドA,Bでのみ使用される
・スレッドAはプロセッサAで動作、スレッドBはプロセッサBで動作
という上記の条件において変数A,Bが同一のキャッシュライン内に格納されてしまった場合、プロセッサA,B間のキャッシュコヒーレンスを保つためのプロトコル動作が大きなオーバーヘッドになり、結果としてパフォーマンスが低下する。
・・・という事らしい。
対策としてはキャッシュラインのサイズを考慮に入れて、適当なpadding用データを挿入する事で同一のキャッシュラインに格納される事を防いでいる模様。
こういった問題を体系的に学んでいない身としてはこういう問題は非常に面白い。
もっと技術情報収集のアンテナをもっと高くしたいなぁ。
sshとVNCでマウスとキーボード削減
Raspberry Pi用に別途マウスとキーボードを接続するのが
面倒になったので、ホストPC(Debian Squeezeにて稼動中)からの
sshは初めから導入済みなので、まずはRaspberry Piにsshで接続。
$ssh pi@xxx.xxx.xxx.xxx(ラズベリーパイのIP)
VNCサーバーをインストール。
pi@raspberrypi ~ $sudo apt-get install tightvncserver
インストール後、初回時の起動でパスワード設定。
pi@raspberrypi ~ $ tightvncserver
とりあえずssh接続を終了。
pi@raspberrypi ~ $ logout
ホスト側にVNCクライアントをインストール。
$sudo apt-get install xvnc4viewer
$xvnc4viewer xxx.xxx.xxx.xxx(ラズベリーパイのIP):1
以上で接続完了。
とりあえずベンチマーク
Raspberry Pi関連でオーバークロックに関する記事を発見したので
何はともあれ追実験のベンチマークをしてみる。
http://www.raspberrypi.org/archives/2008
使用するツールはnbenchを使用。
http://www.tux.org/~mayer/linux/bmark.html
ソースコードを持ってきてRaspberry Pi上でネイティブコンパイル。
デフォルトの700MHzから始まり100MHzずつ動作周波数を上げていき、
nbenchによる計測を行った。
(オーバークロックの設定はsudo raspi-configから行える)
********overclock:none********
BYTEmark* Native Mode Benchmark ver. 2 (10/95)
Index-split by Andrew D. Balsa (11/97)
Linux/Unix* port by Uwe F. Mayer (12/96,11/97)
TEST : Iterations/sec. : Old Index : New Index
: : Pentium 90* : AMD K6/233*
--------------------:------------------:-------------:------------
NUMERIC SORT : 206.72 : 5.30 : 1.74
STRING SORT : 30.272 : 13.53 : 2.09
BITFIELD : 7.8843e+07 : 13.52 : 2.82
FP EMULATION : 41.029 : 19.69 : 4.54
FOURIER : 2192.8 : 2.49 : 1.40
ASSIGNMENT : 2.4705 : 9.40 : 2.44
IDEA : 688.16 : 10.53 : 3.13
HUFFMAN : 423.08 : 11.73 : 3.75
NEURAL NET : 3.0546 : 4.91 : 2.06
LU DECOMPOSITION : 76.329 : 3.95 : 2.86
==========================ORIGINAL BYTEMARK RESULTS==========================
INTEGER INDEX : 11.204
FLOATING-POINT INDEX: 3.644
Baseline (MSDOS*) : Pentium* 90, 256 KB L2-cache, Watcom* compiler 10.0
==============================LINUX DATA BELOW===============================
CPU :
L2 Cache :
OS : Linux 3.2.27+
C compiler : gcc version 4.6.3 (Debian 4.6.3-12+rpi1)
libc : libc-2.13.so
MEMORY INDEX : 2.434
INTEGER INDEX : 3.102
FLOATING-POINT INDEX: 2.021
Baseline (LINUX) : AMD K6/233*, 512 KB L2-cache, gcc 2.7.2.3, libc-5.4.38
* Trademarks are property of their respective holder.
********overclock:modest********
BYTEmark* Native Mode Benchmark ver. 2 (10/95)
Index-split by Andrew D. Balsa (11/97)
Linux/Unix* port by Uwe F. Mayer (12/96,11/97)
TEST : Iterations/sec. : Old Index : New Index
: : Pentium 90* : AMD K6/233*
--------------------:------------------:-------------:------------
NUMERIC SORT : 235.4 : 6.04 : 1.98
STRING SORT : 34.732 : 15.52 : 2.40
BITFIELD : 9.0119e+07 : 15.46 : 3.23
FP EMULATION : 46.984 : 22.54 : 5.20
FOURIER : 2487.5 : 2.83 : 1.59
ASSIGNMENT : 2.7195 : 10.35 : 2.68
IDEA : 789.58 : 12.08 : 3.59
HUFFMAN : 485.06 : 13.45 : 4.30
NEURAL NET : 3.5198 : 5.65 : 2.38
LU DECOMPOSITION : 84.286 : 4.37 : 3.15
==========================ORIGINAL BYTEMARK RESULTS==========================
INTEGER INDEX : 12.754
FLOATING-POINT INDEX: 4.118
Baseline (MSDOS*) : Pentium* 90, 256 KB L2-cache, Watcom* compiler 10.0
==============================LINUX DATA BELOW===============================
CPU :
L2 Cache :
OS : Linux 3.2.27+
C compiler : gcc version 4.6.3 (Debian 4.6.3-12+rpi1)
libc : libc-2.13.so
MEMORY INDEX : 2.751
INTEGER INDEX : 3.550
FLOATING-POINT INDEX: 2.284
Baseline (LINUX) : AMD K6/233*, 512 KB L2-cache, gcc 2.7.2.3, libc-5.4.38
* Trademarks are property of their respective holder.
********overclock:medium********
BYTEmark* Native Mode Benchmark ver. 2 (10/95)
Index-split by Andrew D. Balsa (11/97)
Linux/Unix* port by Uwe F. Mayer (12/96,11/97)
TEST : Iterations/sec. : Old Index : New Index
: : Pentium 90* : AMD K6/233*
--------------------:------------------:-------------:------------
NUMERIC SORT : 262.56 : 6.73 : 2.21
STRING SORT : 39.169 : 17.50 : 2.71
BITFIELD : 1.0126e+08 : 17.37 : 3.63
FP EMULATION : 52.676 : 25.28 : 5.83
FOURIER : 2779.3 : 3.16 : 1.78
ASSIGNMENT : 2.9656 : 11.28 : 2.93
IDEA : 888.28 : 13.59 : 4.03
HUFFMAN : 546.66 : 15.16 : 4.84
NEURAL NET : 3.937 : 6.32 : 2.66
LU DECOMPOSITION : 89.52 : 4.64 : 3.35
==========================ORIGINAL BYTEMARK RESULTS==========================
INTEGER INDEX : 14.266
FLOATING-POINT INDEX: 4.526
Baseline (MSDOS*) : Pentium* 90, 256 KB L2-cache, Watcom* compiler 10.0
==============================LINUX DATA BELOW===============================
CPU :
L2 Cache :
OS : Linux 3.2.27+
C compiler : gcc version 4.6.3 (Debian 4.6.3-12+rpi1)
libc : libc-2.13.so
MEMORY INDEX : 3.064
INTEGER INDEX : 3.984
FLOATING-POINT INDEX: 2.510
Baseline (LINUX) : AMD K6/233*, 512 KB L2-cache, gcc 2.7.2.3, libc-5.4.38
* Trademarks are property of their respective holder.
********overclock:turbo********
BYTEmark* Native Mode Benchmark ver. 2 (10/95)
Index-split by Andrew D. Balsa (11/97)
Linux/Unix* port by Uwe F. Mayer (12/96,11/97)
TEST : Iterations/sec. : Old Index : New Index
: : Pentium 90* : AMD K6/233*
--------------------:------------------:-------------:------------
NUMERIC SORT : 308.88 : 7.92 : 2.60
STRING SORT : 43.81 : 19.58 : 3.03
BITFIELD : 1.1398e+08 : 19.55 : 4.08
FP EMULATION : 59.592 : 28.60 : 6.60
FOURIER : 3283.7 : 3.73 : 2.10
ASSIGNMENT : 3.9185 : 14.91 : 3.87
IDEA : 996.02 : 15.23 : 4.52
HUFFMAN : 615.08 : 17.06 : 5.45
NEURAL NET : 4.6261 : 7.43 : 3.13
LU DECOMPOSITION : 122.22 : 6.33 : 4.57
==========================ORIGINAL BYTEMARK RESULTS==========================
INTEGER INDEX : 16.521
FLOATING-POINT INDEX: 5.601
Baseline (MSDOS*) : Pentium* 90, 256 KB L2-cache, Watcom* compiler 10.0
==============================LINUX DATA BELOW===============================
CPU :
L2 Cache :
OS : Linux 3.2.27+
C compiler : gcc version 4.6.3 (Debian 4.6.3-12+rpi1)
libc : libc-2.13.so
MEMORY INDEX : 3.631
INTEGER INDEX : 4.535
FLOATING-POINT INDEX: 3.106
Baseline (LINUX) : AMD K6/233*, 512 KB L2-cache, gcc 2.7.2.3, libc-5.4.38
* Trademarks are property of their respective holder.