インライン関数ってどれだけ早いの？？
インライン関数ってどれだけ早いの？
インライン関数がどれだけ早いのか気になったので、調べた。
コード
#include<iostream> #include<chrono> #include<vector> using namespace std; template<class T>inline int inline_sz(T &a) { return a.size(); } template<class T>int sz(T &a) { return a.size(); } using ll = long long; inline int fin(int a) { return a; } int f(int a) { return a; } double clock(ll N) { chrono::system_clock::time_point start,end; start = chrono::system_clock::now(); for (int i = 0; i < N; ++i) { f(i); } end = chrono::system_clock::now(); auto elapsed = chrono::duration_cast< chrono::microseconds >(end - start).count(); double y = elapsed; y /= 1000; return y; } double inline_clock(ll N) { chrono::system_clock::time_point start,end; start = chrono::system_clock::now(); for (int i = 0; i < N; ++i) { fin(i); } end = chrono::system_clock::now(); auto elapsed = chrono::duration_cast< chrono::microseconds >(end - start).count(); double y = elapsed; y /= 1000; return y; } int main() { ll N = 1e+9; double cl = 0; int M = 1; for (int i = 0; i < M; ++i) { cl += clock(N); } printf("w/o inline : %.7f[ms]\n", (double)cl/M); double incl = 0; for (int i = 0; i < M; ++i) { incl += inline_clock(N); } printf("w/ inline : %.7f[ms]\n", (double)incl/M); return 0; }
結果
w/o inline : 2331.5940000[ms] w/ inline : 2075.2720000[ms]
109 回 引数を返すだけの簡単な関数を呼び出すと、 inlineの方が早い。
参照渡しにしてみた
inline int fin(int &a) { return a; } int f(int &a) { return a; }
結果
w/o inline : 2083.8500000[ms] w/ inline : 2091.7830000[ms]
参照渡しにすればinlineにしてもほとんど変わらない。（本当に？）
どのくらいの長さの関数だったらinlineにすべきか？
inline int fin(int a) { for (int i = 0; i < 1; ++i) { a += i; } return a; } int f(int a) { for (int i = 0; i < 1; ++i) { a += i; } return a; }
ちょっと関数を長くしてみた（なにこの関数）。
結果
w/o inline : 3191.2370000[ms] w/ inline : 4289.5910000[ms]
ほんのちょっと長くなっただけなのに結構遅くなった。
結論
inline化しても競技プログラミングの実行時間内では差がほとんどない。
Leafletでせんつなぎ！
自力でせんつなぎ！がしたい。ztnに頼りっぱなしは良くないのでは？
これをやる
JavaSprictもHTMLも全然わかんない
Leafletとは
Leafletとは、地図を表示するために使われているJavaScriptライブラリである。
Leafletの使い方
Leafletで地図を書くときはJavaSprictやHTMLで書く。leaflet.jsやら、leaflet.cssやらを引っ張ってくる。このときにcdnjsというWeb上の巨大なライブラリ置き場から引っ張ってきた。
gpxファイルの描画
gpxはgpsの情報が入ったファイル。中身を見るとめっちゃ緯度と経度が書いてある（多分）。これを地図上に描画してくれるようにするプラグインがあるらしい。プラグインが何かも良くわかってないけど。使い方としては、やっぱりcdnjsにライブラリが置いてあるので引っ張ってくる。 https://cdnjs.cloudflare.com/ajax/libs/leaflet-gpx/1.5.0/gpx.min.js これを引っ張ってくる。あとは、gpxファイルをインポートする部分だが、JSなんて書いたことないのでgitのコード丸パクリ。ありがとうございます。インポートしたいgpxファイルはgpx以下に置いておく。
エラーが出た
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>test Map</title>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/leaflet/1.6.0/leaflet.css" />
<script src="https://cdnjs.cloudflare.com/ajax/libs/leaflet/1.6.0/leaflet.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/leaflet-gpx/1.5.0/gpx.min.js"></script>
<script>
function init() {
let map = L.map('mapcontainer');
map.setView([38.3, 138], 5);
L.tileLayer('https://cyberjapandata.gsi.go.jp/xyz/pale/{z}/{x}/{y}.png', {
attribution: "<a href='https://maps.gsi.go.jp/development/ichiran.html' target='_blank'>地理院タイル</a>"
}).addTo(map);
let gpx_lst = ['2020_sustainable_summer_camp_1.gpx',
'2020_sustainable_summer_camp_2.gpx',
'2020_sustainable_summer_camp_3.gpx',
'2020_sustainable_summer_camp_4.gpx',
'2020_sustainable_summer_camp_5.gpx'];
for(let i = 0; i < gpx_lst.length; i++) {
new L.GPX( '/gpx/'+gpx_lst[i], {
async: true,
marker_options: {
startIconUrl: false,
endIconUrl: false,
shadowUrl: false
},
polyline_options: {
color: 'red',
opacity: 0.75,
weight: 3,
lineCap: 'round'
}
}).on('loaded', function(e) {
}).addTo(map);
}
}
</script>
</head>
<body onload="init()">
<div id="mapcontainer" style="width:600px;height:600px"></div>
</body>
</html>
こんな感じのindex.htmlを作成。open index.html をすると、地図は表示されるけど線は出てこない…。ブラウザ上でoption + command + i をすると、エラー内容が見れたが、どうやらローカルファイルを読み込めないらしい。なので、簡易サーバーを立てて解決した。https://qiita.com/terufumi1122/items/39b2a3659bc585c07f64
またエラー
new L.GPX( '/gpx/'+gpx_lst[i] の部分は new L.GPX( 'http://127.0.0.1:8080/gpx/'+gpx_lst[i] に書き換えた。127.0.0.1はlocalhost。すると、アクセス権が無いとかなんとかでエラーが出た。一時的にそれを無効にするChromeの拡張機能を入れて解決。https://developer.yukimonkey.com/article/20200227/
ついに表示
はじめてのせんつなぎ
やったー。
gpxファイルを地図上に（複数個）描画することができるようになった。
2020/09/03
やったこと
- JavaScriptの地図ライブラリ、Leafletを用いてせんつなぎ！を再現（gpxファイルを地図上に描画した）。
- 自作OS20日目をやった。アプリの起動に成功。
- チョムスキーが気になったので、「我々はどのような生き物なのか」を借りた。ちょっとずつ読む。
- 研究はしてない。やりなさい。
明日やること
- 研究。テストベンチの作成。TDCの信号を読め。
- 自作OS21日目。最近あんまり面白くない。
- マスタリングTCP/IPをちょっと読む。
- HTMLとJSの基本について学ぶ。
10日目 重ね合わせ処理
1. メモリ管理の続き
メモリの管理を0x1000バイト単位で管理することにする。
切り上げはどうするかというと、and演算を使う。i = i & 0xfffff000 とすれば、0x1000以下の数字を切り捨てられるので改造して、
i = (i + 0xfff) & 0xfffff000 とすれば切り上げられる。
・切り上げ、切り捨てはAND演算でできる
2. 重ね合わせ処理
レイヤを複数重ね合わせるようにして画面表示することを考える。
一番上のレイヤにマウスカーソルを描いて、一番下のレイヤにデスクトップ壁紙を用意する。マウスカーソルの移動はレイヤごと移動させる。
レイヤの情報を構造体にまとめる。
・レイヤの大きさ
・レイヤの位置
・透明色番号（？）
・レイヤの高さ
・フラグ（？）
このレイヤたちを管理する構造体も作成する。
レイヤのそのものと、レイヤのアドレスを表示順に並べたものを持っておくことにする。
あと用意した関数は、
・メモリを初期化、確保する関数
・レイヤの大きさやバッファをセットする関数
・レイヤの高さを設定する関数
・レイヤを順番通りに表示し直す関数、リフレッシュ
・レイヤを移動させる関数
・使い終わったレイヤを解放する関数
・メモリの確保、解放を逐一するのでプログラムが巨大になる
3. 重ね合わせ処理の高速化 (1)
4. 重ね合わせ処理の高速化 (2)
レイヤのリフレッシュの際に、変化していない画素も含めて全ての画素を変更しているので時間がかかる。
指定した範囲内の画素のみを変化させるように関数を変更する。
いいかんじ。
9日目 メモリ管理
1. ソースの整理
長くなったbootpack.c の一部をkeyboard.c とmouse.c に分割。
2. メモリ容量チェック (1)
まずはメモリの容量をチェック。その前に、キャッシュを停止する必要がある。
2.1 キャッシュとは
キャッシュとは、CPU内部にある小さいメモリ。メインメモリを読んだり書いたりすると、キャッシュメモリにアドレスとその内容を記録するようになっている。これによって、メインメモリの同じアドレスにアクセスする際にキャッシュメモリを参照することで高速にデータを取得できる。
書き込む際も、とりあえずキャッシュメモリに書き込んでおいて、暇な時にそれをメインメモリに書きにいく。
例えば、for(int i = 0; i < 100; ++i) {} の中では、i にはどんどん違う値が書き込まれていくわけだが、キャッシュ制御回路はこの様子を見て、メインメモリにi を書き込むのを一旦やめて置いて、キャッシュの中だけで処理するようにする。そして、i が100 になって落ち着いたらようやくメインメモリにi の情報を書き込む。
2.2 メモリチェック
さて、メモリチェック。メモリチェックはメモリに適当な値を書いてみて、その直後にそこを読んでみて、書いた値と等しい値が入っているかどうかでチェックする。
この時に、キャッシュが挟まると、メインのチェックしたいメモリにはアクセスさせてもらえずに書いた値と読んだ値が等しいという結果になるので、正しいチェックができない。ので、停止。
2.3 386？486？
キャッシュ機能があるのは486以降のCPUなので、まずCPUが386か、486以降かをチェックして、486以降ならキャッシュを停止するようにする。
2.4 実際にメモリチェック
チェックの手順は、あるアドレスにアクセスして値を覚えておく→そのアドレスに適当な値を書き込む→メモリ上でそれを反転させてみて反転したかどうかをチェック
実際に0x00400000〜0xbfffffff をチェックしてみると… 3072MB！これはおかしい。←これにならなかった…
・キャッシュはCPU内の簡易的なメモリ。メモリチェックは実際に書き込んでみる。
3. メモリ容量チェック (2)
3.1 コンパイラの最適化
どうやら2.4 の問題（手元の環境では起きてないのだが）はコンパイラが無駄な部分を最適化してくれていたのが悪かったらしい。
・コンパイラはかしこい
4. メモリ管理に挑戦
4.1 メモリ管理の必要性
メモリはアプリケーションの起動に必要だったり、使い終わって不要になったりする。
どれが今使用中でどれが空いているかを管理する必要がある。
メモリ管理の基本は確保と解放。
4.2 実際にどうやるか
一番簡単な方法は、どのメモリが使用中かの表を作成する。
例えば、128MBのメモリを4KB単位で管理するとする。128 MB / 4KB = 32786 バイトの領域を作成して、そこに0か1を書き込んで、使用中かどうかをメモしておく。
これだと表が大きすぎるのと書き込み読み込みに時間がかかるので、もう少し賢いやり方にする。
xx番地からooバイトだけメモリが空いている、という情報を表にしておく（配列にして持っておく）方法
これだと早いし、表も小さい。ただしプログラムがちょっと複雑。
正しいのか？分かんね〜
・メモリの管理は大切
8日目 マウス制御と32ビットモード切り替え
1. マウスの解読 (1)
マウスから得たデータを解読して、それに合わせてマウスカーソルを動かすぞ。
マウスからのデータは3バイトずつ。あと、最初に0xfaが送られてくる。
0xfaは読み捨てるのと、3バイトずつのデータを1バイトずつ入手して、3バイト溜まるごとに出力。
・マウスからのデータは3バイト
2. ちょっと整理
構造体やら関数を作って整理。
・整理した
3. マウスの解読 (2)
マウスから送られてくるデータは…
・下位3ビットがボタンの状態（右クリックした？左クリックした？）
・真ん中1バイトがx座標、上位1バイトがy座標（y座標は反転してくるので逆にすること）
・下位1バイトのうち、0x10がx座標が移動したかのフラグ、0x20がy座標が移動したかのフラグ
まずは、クリックに応じて表示を変える部分を作成〜。
・マウスからのデータはクリック情報と座標情報
4. 動けマウス
得られた座標データを用いて、マウスの表示を動かす。
境界だけちょっと気をつければ
動いた〜
・動いた
5. 32ビットモードへの道
asmhead.nas の説明をようやくする。
はじめに
割り込み禁止する。
キーボードコントローラのおまけ出力ポートに0xdf というデータを出力。これによってA20GATE信号線というものがONになる。
これは、古いOS（16ビット）との互換性のために、メモリが1 MBまでしか使えないようになっているが、それを解除するもの。
プロテクトモードに移行。
プロテクトモード
本当は「protected virtual address mode」。今までのモードはリアルモードといい、「real address mode」。
これは、メモリアドレスを指定する時に、セグメントレジスタの値で直接アドレスを指定するか、GDTを使ってセグメント番号で仮想的に指定するかの違いである。プロテクトモードに入るとアプリケーションが勝手にセグメントの設定を変えられなくなるので、プロテクト。
メモリをコピー
ブートセクタ（0x7c00からの512バイト）を1MB以降のメモリ（0x100000）にコピー。
0x8200からのディスクの中身を0x100200にコピー。
これで、メモリの0x100000からディスクの中身が揃ったことになる。
bootpackの置いてあるアドレスから512KBを0x280000以降にコピー。
bootpackを実行するために必要なデータをコピー。よくわからん。
メモリマップ
ここで自作OSのメモリマップをまとめる
0x00000000 - 0x000fffff 起動中に色々使うけどそのあとは空き（1MB）
0x00100000 - 0x00267fff フロッピーディスクの内容記憶用（1440KB）
0x00268000 - 0x0026f7ff あき（30KB）
0x0026f800 - 0x0026ffff IDT（2KB）
0x00270000 - 0x0027ffff GDT（64KB）
0x00280000 - 0x002fffff bootpack.hrb（512KB）
0x00300000 - 0x003fffff スタックなど（1MB）
0x00400000 - あき
こういうメモリマップを最初に作ってからOSを作り始めるのが筋
GDT
あとはGDTとかの設定。よくわかってない。
・いろいろしてたけど、メモリのしかるべき場所に作ったものを割り振っているという感じ？
7日目 FIFOとマウス制御
1. キーコードを取得しよう
・キーボードからデータ（キーコード）を取得する
まず、キーボードからデータを受け取った直後にPICに対して、IRQ1が発生したのを確認したよ〜ということを教えてあげる必要がある。
これをしないと、PICは次の入力に対して反応しなくなってしまう。
io_out8(PIC0_OCW2, 0x61); でPIC
に教える。OCW2に「0x60 + IRQ番号」を教えれば良い。
次に、装置番号0x0060 から8ビットのキーコードを取得する。
装置番号はhttp://oswiki.osask.jp/?%28AT%29keyboard を参照。
・装置に入力→外部装置に入力確認→貰ったデータを取得
2. 割り込み処理は手早く
1.では割り込み処理の途中で文字を出力したが、文字の出力には時間がかかり、その間には他の割り込み処理を受け付けられない。
割り込み処理は一瞬で終わらせる必要があるため、「キー入力に対しては一旦変数にキーコードを保存しておいて、あとで出力する」という形をとる。
一時的にデータを保存するバッファを作成し、キー入力→キーコードをバッファに保存→ゆっくりとバッファからキーコードを取得、という流れ
・割り込み処理は一瞬で
3. FIFOバッファを作る
4. FIFOバッファを改良する
FIFOを改良する。3.ではメモリに入っているデータをpopがある度に平行移動していたが、時間がかかるのでデータの位置は変えずに、どのアドレスに読みに行くか？を変更していく。
5. FIFOバッファを整理する
ファイルを小分けにする。
・FIFOを作った
6. さあマウスだ
・今までマウスが使えなかった理由について、
マウスは比較的新しい装置なので、マウスができた時にはほとんどのOSがマウスに対応していなかった。そんな状況でマウスを少し動かすだけで割り込みを発生させていたら、ハングアップしてしまうので、マウスを外さないといけない。
これは面倒なので、マウス用の回路については有効化命令を出さないと割り込み信号を出さないように設計した。
マウスを使うには、マウス制御回路とマウスそのものに有効化命令を出さないといけない。
・キーボード制御回路
マウス制御回路はキーボード制御回路の中にあるので、キーボード制御回路をうまく初期化。
まずは、キーボードコントローラ（KBC）が制御命令を受け付けられるようになるのを待つ。
具体的には、装置番号0x0064から読み取ったデータの下から2ビット目が0になればOK
KBCが受付を始めたら、モードを設定するよ〜というコマンドを送り、マウスを使うモードにするコマンドを送る。
これで、制御回路に有効化命令を出せた。
・マウスそのもの
マウスに有効化命令を送るには、キーボード制御回路に命令を送る。
マウスに命令を送ってくれ〜というコマンドを送り、マウスを有効化するためのコマンドを送る。
マウスは有効化命令を受け取ると、これからマウスの情報を送るよ〜という意味の情報を早速送ってくる（0xfa）
・マウスを使うには、制御回路とマウスそのものを有効化しなければならない
7. マウスからのデータ受信
PICへの割り込み通知は、スレーブのIRQなのでマスタとスレーブの両方に受付完了の通知を送らなければならない。
あとは、キーボードと一緒。
・マウスデータの受け取りは、キーボードデータの受け取りと同じ
