Counting 1 bits.
Go 標準ライブラリの中に符号なし整数をビット列と見たとき、 1 のビットを数える関数がある。この実装がなかなか膝打ちのアイデアで面白い。なおここで紹介するアイデアは "Hacker's Delight" 第5章に詳しく書かれている。
例
以下の 16 bit の数を考える。
1 の数は 8 個ある。
数え上げのナイーブな実装として、 16 回ループを回し 1 のビットを見つけたらカウンタをインクリメントすることを思いつく。
これだと計算量は O(n)
となる。
しかし、分割統治法を使うことで O(log(n))
にすることができる。すごい。
分割統治法
肝となる考えは「大きな問題を部分的な問題へ分割し、部分問題の結果をもとに大きな問題を解決する」ということだ。 16 個のビットを一度に計算するのではなく、より小さいビット幅で計算することを考える。
再び例にもどる。
はじめに 2 ビット幅ずつ見てみよう。 見やすいよう下図のように 7 個の仕切りを追加する。
仕切りにより 8 個の 2 ビットのペアが出来た。 仕切られた空間をここでは 部屋 と呼ぶことにする。つまり上図では 8 個の 2 ビット幅の部屋がある。
次に各部屋ごとにビットの数を計算しよう。各部屋の計算結果を 2 進数で格納すると下図になる。
同様に 4 ビット幅、8 ビット幅、16 ビット幅と、ビット幅を倍にして 1 の個数を求め続ける。これらの操作により下図のようになる。
最後部屋を見ると求めたかった 1 の個数 0b1000
、つまり 8 が得られた。
実装
例えば 2つの 2 ビット幅の部屋から、4 ビット幅の部屋を求めることを考える。 これは左の部屋を右に 2 ビットシフトし右の部屋の値と足し合わせれば良い。
実装上の注意として、不要な値を無視するために 00110011 ...
のビットマスクを使用する。
以下のコードはGo標準ライブラリにある、64ビットの符号なし整数の 1 の数を数える関数 OnesCount64
である。
(一部簡略化した形で引用した。)
const m0 = 0x5555555555555555 // 01010101 ... const m1 = 0x3333333333333333 // 00110011 ... const m2 = 0x0f0f0f0f0f0f0f0f // 00001111 ... func OnesCount64(x uint64) int { x = x>>1&m0 + x&m0 x = x>>2&m1 + x&m1 x = (x>>4 + x) & m2 x += x >> 8 x += x >> 16 x += x >> 32 return int(x) & (1<<7 - 1) }
ここまでくれば関数の各行から、ビットの幅を倍にして部屋の値を求めている操作が想像できるだろう。
なお標準ライブラリのコードでは 8 ビットシフトからマスクを取らない。
これは uint64
の 1 の数は高々 64 = 26 個 であり、最終行の 1<<7-1
のマスクで 7 ビット目以降は無視できるからである。
参考資料
++i is better than i++ in C++?
タイトルの答えは条件付きの Yes。その条件は「インクリメントする式の値を無視する場合」というもの。
たとえば次のように単にi
をインクリメントしたい場合++i
と書くほうが良い。
int i = 0; while (true) { // use i i++; }
何故「良い」のかはGoogleのC++スタイルガイドに書かれている。
要約するとi++
の場合i
のコピーをつくる必要があり*1、その必要がない++i
と比べ*2メモリがお得だからという理由。
さらにC++の場合オペレータのオーバーロードができる。そのため i
が整数でない場合、より両者の性能差が広がる可能性がある。ガイドの次の文はおそらくこのことを述べている。
If i is an iterator or other non-scalar type, copying i could be expensive.
それでは Proof Of Concept として次の実験をしてみよう。
実験
前置++
と後置++
をオーバーロードしたクラスを用意し、両者の性能差を計測する。
クラス
クラス | 説明 |
---|---|
HugeClass |
実験対象のクラス |
Timer |
実行時間の計測用クラス |
なお今回のTimer
の実装はC++でフリープラットフォームな時間計測を参考にした。
コード
#include <iostream> #include <chrono> using namespace std; class HugeClass { public: // prefix increment HugeClass& operator ++() { for (int &num : this->nums) { ++num; } return *this; } // postfix increment HugeClass operator ++(int) { HugeClass ret = *this; for (int &num : this->nums) { num++; } return ret; } private: int nums[100000]; }; class Timer { private: chrono::system_clock::time_point startTime; chrono::system_clock::time_point endTime; public: void start(){ this->startTime = chrono::system_clock::now();}; void end(){ this->endTime = chrono::system_clock::now();}; chrono::microseconds diff(){ return chrono::duration_cast<chrono::microseconds>( this->endTime - this->startTime ); }; }; int main() { int REPEAT_NUMBER = 10000; // post increment HugeClass hc_post = HugeClass(); Timer t_post = Timer(); t_post.start(); for (int i = 0; i < REPEAT_NUMBER; i++) { hc_post++; } t_post.end(); // pre increment HugeClass hc_pre = HugeClass(); Timer t_pre = Timer(); t_pre.start(); for (int i = 0; i < REPEAT_NUMBER; i++) { ++hc_pre; } t_pre.end(); cout << "post inc: " << t_post.diff().count() << " " << endl; cout << "pre inc: " << t_pre.diff().count() << " ticks" << endl; }
結果
wandbox上で試した結果、期待通り後置インクリメントが遅かった。
post inc: 3606617 ticks pre inc: 3338294 ticks
今回はインクリメントに話題を限定したが、デクリメントも同様の議論がなりたつ。
参考資料
Zen言語で作るRISC-Vエミュレータ、その1
Zen言語とは今注目の言語です。 そしてRISC-Vとは今注目の命令セットです。 (多分に個人的感想ですが)どちらも聞かない日はありません。
そんな両者の接点ともいえるエミュレータを開発します。現時点で実装している命令は5種類のみですが、 第一目標のフィボナッチ数列が計算できるようになりました。
開発環境
公式サイトのダウンロードページよりコンパイラのバイナリをダウンロード出来ます。
バージョンは次のコマンドにより確認できます。
$ zen version 0.8.20191124+552247019
注意
- ここに登場する命令はすべて
RV32I
と呼ばれる基本命令セットです。
リポジトリ
RISC-Vの5とZenをあわせ、「5zen」と名付けました。
現在の完成度
フィボナッチ数列の計算を最初の目標とし、それを達成した時点での記事のため、出来は非常にミニマルです。
RV32I
命令セットの全47命令のなかで以下の5命令にしか実装していません。
- add
- addi
- blt
- jal
- jalr
以下は第10項目のフィボナッチ数を求める、C言語コードとRISC-Vアセンブリ言語です。
実際に5zen
ではユニットテスト
により計算結果を確かめています。
int main() { int lhs = 1; int rhs = 1; int result = 0; // 第1, 2項目は計算済とし、第3項から数え上げる int counter = 3; while (counter <= 10) { result = lhs + rhs; lhs = rhs; rhs = result; counter++; } // result == 55 }
## t0: lhs ## t1: rhs ## t2: result ## t3: counter addi t0, t0, 1 addi t1, t1, 1 addi t3, t3, 3 addi t4, t4, 10 ## if (t3 < t4) { jump to `ret`} blt t4, t3, 24 add t2, t0, t1 add t0, t1, zero add t1, t2, zero addi t3, t3, 1 ## unconditional jump to `blt t4, t3, 24` jal zero, -20 ret
一年前の私へ
タイトルとここまでを一読しても、一年前の私にはほとんどピンと来ず、わからなかったでしょう。 そんな過去の自分に向けた章です。もし役立つ方がいれば幸甚です。
RISC-Vとは命令セットの一種です。
「セット」には集まりという意味があり、命令セットとは(ラフにいうと)命令の集まりです。
そしてこの「命令」とは、コンピュータの根幹部品であるCPUに対し、特定の動作を定めるものです。
例えばRISC-Vにはaddi
命令があります。これは次のように、3つのオペランドと合わせて1つの命令を構成します。
addi rd, rs, imm
具体的にはaddi x5, x6, 1
などと書き、これは「x6
レジスタの値に即値1
を足し、結果をx5
レジスタに格納する」
という命令として実行されます。
命令にはその命令を実行できるCPUが必要です。 例えば、SiFive社が開発したHiFive1はRISC-Vプロセッサが搭載されたボードです。
これは物理的なCPUですが、その動作を模倣するようなソフトウェアをエミュレータと呼びます。
そして今回は
「Zen言語を用いて、RISC-V命令を実行できるCPU
をエミュレータとして実装しました」
ということを紹介するブログポストです。
方針は決まりました。では一歩目は何をすれば良いのでしょう。 その答えは、CPUの具体的な動作を知ることで見えてきます。
CPUの動作
CPUは「フェッチ」、「デコード」、「実行」と呼ばれる3種類の動作を行います。
動作 | 解説 |
---|---|
フェッチ | 実行する命令をメモリからロードする |
デコード | フェッチした命令が命令セットのどの命令にあたるか解釈する |
実行 | デコードした命令を実行する |
それぞれが一度きりの動作ではなく、 フェッチ、デコード、実行、フェッチ、デコード、実行、フェッチ・・・ とループされます。このループをCPUの実行サイクルと呼びます。
3つの動作例として、前章に挙げたaddi x5, x6, 1
のフェッチから実行までを見てみましょう。
フェッチ例
命令はすべてメモリ内に機械語として格納されています。
フェッチでは現在のPC(プログラムカウンタ)が指す命令をメモリからロードします。
デコード例
フェッチにより、実行すべき命令の機械語00000000000100110000001010010011
を取得できました。
デコードではこのビット列が何命令であるか、そのオペランドは何かを解釈します。
このままでは見ずらいため、これを意味のあるビット列に分割すると次のようになります。
000000000001 00110 000 00101 0010011
ここで公式ドキュメントにある次の図を引用します。
ビット列と図を見比べてみてください。フェッチしたビット列がaddi x5, x6, 1
命令であることがわかります。*1
実行例
デコードによりaddi x5, x6, 1
という命令だとわかりました。
あとは「x6
レジスタの値に即値1
を足し、結果をx5
レジスタに格納する」ことを行い、プログラムカウンタの値をインクリメントし次の命令をフェッチできるようにします。
CPUの実装
5zen
ではフェッチ、デコード、実行の三動作をCPU
構造体のメソッドとしてそれぞれ次のように実装しています。
pub const CPU = struct { ... pub fn fetch(self: *Self) PROG_TYPE { ... } pub fn decode(self: *Self, inst_bytes: PROG_TYPE) InstructionSet { ... } pub fn execute(self: *Self, inst: InstructionSet) void { ... } }
エミュレータの実装
5zen
ではEmulator
構造体のrun
メソッドにCPU実行サイクルを実装しました。
RISC-Vにはサイクルを止めるhalt
命令に相当する命令が存在しません。
そのため現在はret
命令を実行後、サイクルループを脱出しています。これはMOIZこちらの記事*2を参考にしました。
pub const Emulator = struct { const Self = @This(); cpu: CPU, ... pub fn run(self: *Self) void { // Stop the CPU cycle loop when pc equals `RET_ADDR`. while (self.cpu.pc != RET_ADDR) { const inst_bytes = self.cpu.fetch(); const inst = self.cpu.decode(inst_bytes); self.cpu.execute(inst); } } };
Zen言語のメリット
今回の開発では、Zenで提供されるタグ付き共用体
というデータ構造の有用性を実感しました。これはHaskellでは代数的データ型、Rustでは列挙型に相当するものです。
タグ付き共用体
はあらかじめ取りうる選択肢がタグにより定められており、そのどれか1つを(紐づくヴァリアントを用いて)実行するような処理を書きたいときに便利です。
そしてこの特徴はエミュレータの実装において、命令セットからどれか1つの命令を実行したいという動機とマッチします。
実際RISC-Vの命令セットをタグ付き共用体
で次のように実装しました。
pub const InstructionSet = union(Opcode) { Add: AddInst, Addi: AddiInst, Blt: BltInst, Jal: JalInst, Jalr: JalrInst, }
ここでOpcode
は列挙型として次のように定義することで、実装する命令にタグを付けます。
pub const Opcode = enum { Add, Addi, Blt, Jal, Jalr, };
そして5zen
のexecute
メソッドでは、switch
文により各命令を分岐して、それぞれの動作を実行します。
pub fn execute(self: *Self, inst: InstructionSet) void { switch(inst) { .Add => |add| { ... }, .Addi => |addi| { ... }, .Blt => |blt| { ... }, .Jal => |jal| { ... }, .Jalr => |jalr| { ... } } }
このとき分岐をもれなくカバーしないとコンパイルエラーとしてくれます。そしてこの機能が開発に役立ちます。
5zen
では実装する命令を1つづつ追加する、インクリメンタルな開発を行います。
そのときこの機能のおかげで、「Opcode
には新命令をタグとして追加したが、execute
内の実装を忘れてしまった」というミスをコンパイル時に発見してくれます。
(実際にAddi
命令がある状態で、Add
命令を実装しようとしたとき、コンパイラが分岐の網羅漏れを発見してくれました。)
今回はインクリメンタルな開発を目指し、1つづつ対応する命令を増やして行きました。 Zen言語ではソースコード内にユニットテストをかける、コンパイラによるタグ付き共用体の網羅性チェックなど、 インクリメンタルな開発と相性が良いようです。 このあたりはZenの思想に通じており公式サイトでは漸と紹介されています。
さいごに
RV32I命令だけ見ても全47命令中5命令しか実装できておらず、割合では完成は程遠く感じます。ただインクリメンタルな開発のおかげで命令を増やす心理的な負荷はあまり感じません。いずれにせよなかなか楽しい趣味になりそうなので、空いた時間に開発を続けようと思います。
参考
サイト
書籍
xv6 initプロセス ことはじめ
あるプロセスには親プロセスという生みの親がいます。その親にも親がいます。
そして、プロセスの系譜をさかのぼり続けると一つのプロセスに行き着きます。
それはinit
プロセス。Unix及びUnix系のOSではこの名前がついています。*1
またタイトルにあるxv6
とは、2006年MITで開発された教育用OSです*2。
ANSI Cで書かれておりソースコードリーディングに適しています。
今回はあらゆるプロセスの祖先といえるinit
プロセスの生成と実行はじめまでを、xv6
のソースコードを読み、観察してみましょう。(同じ内容のスライドがあります。こちらはブログと比べスタックの動的な操作がわかりやすいです。)
あらすじ
xv6
のプロセスinit
プロセスの生成- スケジューラが
init
プロセスを選択 - スケジューラから
init
へのコンテキストスイッチ init
の実行
注意
init
プロセスに話をしぼるため、ブートローダーやカーネルの設定や初期化は完了済とします。- 掲載するソースコードのなかで今回の話に不要と思われる記述は修正や省略をしました。例えば
xv6
はマルチプロセッサに対応しており、排他制御を行うコードも存在します。しかし私の理解不足と紙面の都合上意図的に省略しました。 - 以下に登場するメモリ領域の図は上が high アドレスとなっており、スタックは下に積まれます。
xv6のプロセス
早速init
プロセスの生成を見ていきたいところですが、その前にxv6
ではプロセスをどのように実装しているのでしょう。
それはproc.h
にproc
構造体として定義されています。
struct proc { pde_t* pgdir; char *kstack; enum procstate state; int pid; struct proc *parent; struct trapframe *tf; struct context *context; };
フィールド | 説明 |
---|---|
pgdir |
仮想メモリと物理メモリのマッピングを定める |
kstack |
tf やcontext を格納する領域 |
state |
プロセスの状態を表す。proc.h にenum型として定義される |
pid |
プロセスに割り振られる一意な整数値 |
parent |
親プロセス |
tf |
トラップの発生時に使用される。今回はinit プロセスの実行に必要なレジスタを格納する |
context |
コンテキストスイッチ時にレジスタを格納する、または復元するために使用される |
init
もプロセスであるため、その生成はproc
構造体のインスタンスとして定義されます。
Cの構造体は各メンバが連続したメモリに配置されます。
つまりinitの生成は以下のようなメモリ領域を作成することと同じです。
init
プロセスの生成
この節では上に挙げたメモリ領域をinit
のために作成することが目標です。
すでにカーネルの設定は終わっているためmain
関数の中で今回の話と関係のある関数はuserinit
とmpmain
の2つです。
int main(void) { \\ カーネル、割り込みの設定のため略 userinit(); mpmain(); }
userinit
userinit
は次の4つの仕事を行います。
- initプロセスの生成
- initのカーネル空間のpagingの設定
- initのプログラムをメモリに展開
- トラップフレームの設定
そのうち上3つを以下の関数がuserinit
内で呼ばれることで、それぞれ請け負います。
allocproc
setupkvm
inituvm
次のコードはuserinit
の前半部分です。早速allocproc
が呼ばれていることがわかります。
void userinit(void) { struct proc *p; p = allocproc(); if((p->pgdir = setupkvm()) == 0) panic("userinit: out of memory?"); inituvm(p->pgdir, _binary_initcode_start, (int)_binary_initcode_size); ..... }
allocproc
allocproc
の主な仕事は次の3つです。
UNUSED
なプロセスをテーブルから探す- そのプロセスの設定
- pid, state, trapframe, etc…
- 設定したプロセスを返す
なおallocproc
は1つのプロセスを生成するので、userinit
からだけではなくfork
からも呼び出されます。
まずプロセステーブルの中からUNUSED
なプロセスを探す処理が次のコードです。
static struct proc* allocproc(void) { struct proc *p; for (p = ptable.proc; p < &ptable.proc[NPROC]; p++) if (p->state == UNUSED) goto found; return 0; found: ... }
プロセステーブルptable
はproc.c
にグローバル変数として定義されており、64
個のプロセスエントリを格納します。
コードではプロセステーブルの先頭から最後まで見て、UNUSED
なプロセスを見つけた場合found
ラベルへと飛びます。
found
ラベル以降は次のようなコードです。
found: p->state = EMBRYO; p->pid = nextpid++; // Allocate kernel stack. if ((p->kstack = kalloc()) == 0){ p->state = UNUSED; return 0; } .....
今UNUSED
なプロセスが見つかったためその初期化を行います。まずstate
をEMBRYO
にしています。
EMBRYOは「生まれたて」という意味があります。またpid
の割り当てを行い、グローバル変数であるnextpid
をインクリメントします。これにより次回のallocproc
呼び出しではプラス1された整数値がpid
として割り当てられます。
次にkalloc
を呼び出しp
のカーネルスタックを割り当てます。これにより1ページ(4096バイト)分のメモリ領域がカーネルスタックの領域として確保されました。この領域はトラップフレームやコンテキストを格納するためにあります。ここまでの処理により次のようなメモリ領域の図になります。
カーネルスタックの設定
次に確保したカーネルスタック領域を複数の部分領域へ区切ります。後の処理によりそこにトラップフレームやコンテキストを格納できるようにします。
具体的なコードは次のようなものです。
sp = p->kstack + KSTACKSIZE; // Leave room for trap frame. sp -= sizeof *p->tf; p->tf = (struct trapframe*)sp; .....
まずsp
をカーネルスタックの最上部を指すようにします。そしてsizeof *p->tf;
によりsp
をトラップフレームのメモリ領域分を押し下げ、そのアドレスをp->tf
に代入しています。
sp -= 4; *(uint*)sp = (uint)trapret; sp -= sizeof *p->context; p->context = (struct context*)sp; memset(p->context, 0, sizeof *p->context); p->context->eip = (uint)forkret; return p;
同様にまずsp
を4バイト下げ、関数trapret
の関数ポインタを格納します。
さらにsp
をコンテキスト分下げ、eip
の領域に関数forkret
を格納します。
関数trapret
とforkret
はコンテキストスイッチが起こり、スケジューラからプロセスへ制御が渡された後すぐに実行されます。
最後にp
をリターンして関数を抜けます。ここまでの処理によりinit
は次のようなメモリ領域を構築できました。
userinit
再びuserinit
に処理が戻ってきました。次は以下の3行です。
if((p->pgdir = setupkvm()) == 0) panic("userinit: out of memory?"); inituvm(p->pgdir, _binary_initcode_start, _binary_initcode_size);
まずsetupkvm
によりinit
用のページテーブルを設定します。ページテーブルにより仮想アドレスと物理アドレスのマッピングが設定されます。inituvm
はこのマッピングにもとづいて仮想アドレスの0番地にinit
用のプログラムinitcode
を展開します。
次にinit
のトラップフレームの設定を行います。
p->tf->cs = (SEG_UCODE << 3) | DPL_USER; p->tf->ds = (SEG_UDATA << 3) | DPL_USER; p->tf->es = p->tf->ds; p->tf->ss = p->tf->ds; p->tf->eflags = FL_IF; p->tf->esp = PGSIZE; p->tf->eip = 0; // beginning of initcode.S
コメントにもある通りp->tf->eip = 0;
でinitcode
が格納されている0番地をeip
が来るようにしています。eip
はx86アーキテクチャの32bit版命令ポインタで、実行する次のアドレスを格納します。今p->tf->eip
が0となっているため、コンテキストスイッチ後に0番地から実行できるよう下準備をしました。
userinit
の最後はpの状態をRUNNABLE
にして関数を抜けます。
p->state = RUNNABLE;
これまで作成したinitのメモリは次のようになります。
スケジューラがinit
プロセスを選択
xv6
のスケジューラはシンプルに実装されています。プロセステーブルを先頭から調べstate
がRUNNABLE
なプロセスをみつけたらそのプロセスへとコンテキストスイッチします。
以下がスケジューラのコードの一部です。for文が入れ子になっており、外側のループは無限ループになっています。
void scheduler(void) { struct proc *p; struct cpu *c = mycpu(); c->proc = 0; for(;;) { ... for (p = ptable.proc; p < &ptable.proc[NPROC]; p++) { if (p->state != RUNNABLE) continue; c->proc = p; switchuvm(p); p->state = RUNNING; swtch(&(c->scheduler), p->context); ... } } }
RUNNABLE
なプロセスを見つけると、まずswitchuvm(p);
が呼ばれます。今RUNNABLE
なプロセスはinit
しかいません。
そのためswtchuvm
ではinit
のページング設定をcr3
レジスタにロードし、スケジューラのアドレス空間からinit
プロセスのアドレス空間へ切り替えます。
次にinit
をRUNNNIG
状態にします。そしてようやくswtch
関数によるコンテキストスイッチです。
swtch
の第一引数と第二引数には、それぞれ古いコンテキスト(のアドレス、理由は後述)と新しいコンテキストを指定します。
今swtch(&(c->scheduler), p->context);
であるためスケジューラからinit
プロセスへとコンテキストスイッチすることがわかります。
スケジューラからinit
へのコンテキストスイッチ
swtch
関数swtch
はswtch.S
にアセンブリで書かれています。
.glonl swtch swtch: # load `old` movl 4(%esp), %eax # load `new` movl 8(%esp), %edx # Save old callee-saved registers pushl %ebp pushl %ebx pushl %esi pushl %edi # Switch stacks movl %esp, (%eax) movl %edx, %esp # Load new callee-saved registers popl %edi popl %esi popl %ebx popl %ebp ret
swtch
呼び出し直後はスケジューラのカーネルスタックに、第二引数p-context
, 第一引数&(c->scheduler)
, swtchの戻り先のアドレス
の順に積みます。
まず先頭2行のアセンブリでeax
とedx
に、それぞれスイッチ先のプロセスのコンテキストとスケジューラのアドレスを代入します。
# load `old` movl 4(%esp), %eax # load `new` movl 8(%esp), %edx
次の4つのpushl
命令によりスケジューラのコンテキストを保存します。
# Save old callee-saved registers pushl %ebp pushl %ebx pushl %esi pushl %edi
次に2つのmovl
命令が続きます。
movl %esp, (%eax) movl %edx, %esp
1つ目の命令movl %esp, (%eax)
によりスケジューラのコンテキストを保存します。(実際はスケジューラのコンテキストの先頭を指すスタックポインタesp
の値を保存します。スケジューラのコンテキストの保存先は&(c->scheduler)
で定まる特定のアドレスであり、このためにアンパサンドがついていました。)
2つ目の命令movl %edx, %esp
がコンテキストスイッチの肝です。今までスケジューラのスタックを指していたesp
をプロセスのスタックを指すようにします。つまり
から
へとesp
が移動しました。
残りは下準備したinit
のコンテキストへ切り替えるためpop
命令を繰り返します。
# Load new callee-saved registers popl %edi popl %esi popl %ebx popl %ebp ret
4度のpopl
によりesp
は次の位置まであがります。
ret
命令により、eip
に格納されているforkret
関数ポインタをポップし、そこにジャンプします。
forkret
はC言語の関数として定義されていますが、関数を抜ける際にスタックをポップし、
そこへとジャンプすることは変わりません。よってtrapret
関数の関数ポインタがポップされ、関数の先頭へジャンプします。
残るトラップフレームのポップはtrapret
によって行われます。trapret
は次のようなアセンブリで書かれています。
.globl trapret trapret: popal popl %gs popl %fs popl %es popl %ds addl $0x8, %esp # trapno and errcode iret
トラップフレーム内のレジスタに注目するため、一つ上に載せたカーネルスタックからトラップフレームの部分を拡大します。それは次のような図になります。今esp
はトラップフレームの最下部を指していることに注意してください。
まずpopal
により汎用レジスタを復元します。次の4つのpopl
命令によりセグメントレジスタを復元します。そして次のaddl
命令によりesp
を8バイト押し上げ、trapno
とerrcode
を無視します。最後のiret
により残るレジスタの復元を行います。具体的にはeip
, cs
, eflags
, esp
, ss
が復元されます。特にeip
とesp
の復元により、initcode
(init
プロセスの実行プログラム)のために格納した4096バイトの最下部と最上部を、それぞれeip
とesp
が指すようになり、無事initcode
の実行が始まります。
参考文献
- xv6
- book-rev11.pdf
- xv6実装の詳解(マルチタスク処理 switching編)
*1:https://ja.wikipedia.org/wiki/Init
*2:https://pdos.csail.mit.edu/6.828/2019/xv6.html
*3:本テーマと不要なメンバは省略しています
浮動小数点数の悲劇
"Roundoff Error and the Patriot Missile" を読んだ。以下要約。
結果: イラクのスカッドミサイルがアメリカ陸軍兵舎に向け放たれた。 アメリカのパトリオットミサイルは迎撃に失敗、28人の兵士が死亡。
原因: パトリオットミサイルのシステムは、内部クロックとして0.1秒ごとにインクリメントするカウンタ を採用していた。0.1を2進数の浮動小数点数で表すと循環小数になり、どこかで数を丸める必要がある(実際は仮数部を23bitで保持していた)。 システム起動から100時間後には、丸めから生じる誤差は、実時間と比べおよそ0.34秒になった。 迎撃システムの性質上、長時間連続して可動させた上でも、正確な計算が求められるのだろう。0.34秒という誤差は致命的だった。 実際の直接的な原因は、システム内のタイマーを正確なものに置き換えたとき、 一部、誤差が存在するタイマーがそのまま残ってしまったことだったようだ。
欅坂46 ブログの自動生成 (開発日記)
以下は先日ポストした欅坂ブログ自動生成アプリ「zelkova」
の開発日記です。
当初はアンドロイドアプリとして動かそうと思っていましたが、PCのターミナル上で自動生成できたところで、日記として掲載します。
-----------------------------------------------------------------------------------------------------
20180905
urllib3ライブラリを使い、<script>タグの中にあるブログ更新日時文字列の取得に成功した。
その文字列からメンバーIDを鍵、更新日時を値とした辞書"member_update_time"を作成した
20180906
webスクレイピングにより、blogのタイトルと文面を取得できた。
CSSセレクターを使うことでより直接値を取得できた。(昨日のやり方では、存在する<script>タグのループを回し、該当箇所を見つけていた)
LSTM(long short term memory)の概要を学んだ。
RNN(Recurrent neural network)の拡張であり、どちらも時系列データ(sequential data)を扱う。
時系列順にならんだデータに対し、入力と出力のデータの位置が時系列として近い場合、RNNは過去のデータをもとに学習できる。
だが、その位置が遠い場合(長期依存性の問題という)、RNNでは学習が進まなかった。
LSTMではそれを克服し、長期的な依存関係を学習できるようになった。
これを日本語文の自動生成に当てはめると、今までの単語の列を時系列データとして、次に予想される単語を生成することができるようになる(らしい)
参考文献
2. https://qiita.com/KojiOhki/items/89cd7b69a8a6239d67ca
今の所、理論よりもすぐに日本語を自動生成した意欲が勝っている。
なにか本を買うべきなのか?
明日は、今開いているLSTM文章生成ページのどれかを参考にし、文章を生成したい
20180907
pipインストールがうまく動かない。python3にmecab(日本語形態素解析ツール)を入れようとしたが通らず。
この記事を参考にアナコンダをアンインストールした。
https://qiita.com/pickles/items/12c8c73d3d4bbd61f738
python3, pip3も再インストールした。
mecabインストールできた。
ex.
'5', '月', 'も', 'もうすぐ', 'で', '終わり', '、', '、', 'あ', '、', 'そう', 'いえ', 'ば', '、', 'これ', 'といった', '五月', '病', 'に', 'かかっ', 'て', 'ない', 'かも', 'しれ', 'ん', '!', 'こ', '~', 'れ', 'は', '今年', 'の', '小林', '、', '一味', 'ちがう', 'ぞ', 'っ', '!', '小林', '由依', 'です'
アンドロイドアプリはうまくいくのかな?
ストップウォッチアプリを作ろうと思い
https://employment.en-japan.com/engineerhub/entry/2017/06/23/110000
を試した。初kotlin。たくさんエラーが出て放置。
20180908(土)
できていないこと
・分割した各形態素を学習し、文章をLSTMにて自動生成すること
・androidアプリをつくり、実機でテストすること。
python3へのtensorflowのインストールに手間取った。
pyenvでpython 3.6.0へダウングレードしてから、
pip3 install tensorflow
で通った
いまのところLSTMを用いた文章生成のサンプルソースコードを見てもよくわからない。
なので、本「ゼロから作るDeep Learning ❷ ―自然言語処理編」を注文した。
届くまでの間、kotlin入門をやろうと思う。
http://www.atmarkit.co.jp/ait/series/8323/
20180913(木)
ブログの最終更新日時取得のコードはpythonで書いた。
android studioでkotlinを用い、androidアプリでそれを利用したい場合、
pythonコードをサーバー上において、androidアプリからはそのresponseを受け取る形にしてはどうか?(竹宮)
20180920(木)
本「ゼロから作るDeep Learning ❷ ―自然言語処理編」の7章1節「言語モデルを使った文章生成」まで読んだ。
学習済みの重み行列を用いてはいないが(CPUで計算する場合、学習に2日かかると記述があり、怖気づいた)、文章生成は行えた。
うまくいきそう。アンドロイドアプリとなるかはおいといて。
githubにレポジトリを作成。最近、覚えたて。嬉しくてよくpushしてる。
pythonによるwebscrapingも久しぶりに行った。
主な変更点は、
現在(18/09/20)までの過去の全ブログ(小林由依の)の、文章、タイトル、更新日をカラムとするcsvファイルを生成できた。
できていないこと、改良点は、
・メンバーごとの変数(ブログでの管理番号)は別ファイルに定数として保存
・各メンバーブログの最初のポストがあるurlまで、for文をまわすこと
例:
メンバーのブログは、ポストが新しい順にならんでいる。いかのurlにおいて
http://www.keyakizaka46.com/s/k46o/diary/member/list?ima=0000&cd=member&ct=07&page=XXXX
XXXXが大きいほど、古いブログポスト。XXXX=nが最初のポストがあるページだとすると、
http://www.keyakizaka46.com/s/k46o/diary/member/list?ima=0000&cd=member&ct=07&page=n+1
まではforループが回ってほしくない
・csvファイルを読み取りcorpusを作ること(mecabを使う)
20180921(金)
改良点は主に2点。
1, word2vecのCBOWモデルを用い, 指定した単語と類似度の高いものを列挙できるようになった。
なお、この場合の類似度は、メンバーが書いたブログをもとに、生成するもの。
[query] 織田
鈴本: 0.86669921875
今泉: 0.828125
菅井: 0.8173828125
娘: 0.787109375
米谷: 0.78662109375
[query] see
おやすみなさい: 0.92431640625
you: 0.92236328125
again: 0.82763671875
うら: 0.8037109375
では: 0.78173828125
2, 関数と定数をそれぞれディレクトリ"functions", "datasets"の中に入れ、共通パーツ化した。
なお、関数のコード自体は数日前に書いたものもある。
関数は
getUpdateTime(): ブログの最新更新日時を取得する
getBlogPutCSV(): webサイトへスクレイピングに行き、全投稿ブログの、投稿日時、タイトル、本文を取得し、csvファイルとして出力する
generatePkl(): NNで学習や推論時、使用するcorpus, word_to_id, id_to_word, wordsを格納した辞書型ファイルをpickleファイルとして生成する
次に目指すことは、時系列データを生成し(改良点の1ではtargetとなる単語のの両脇の単語を、同等のものとして学習した、これは時系列データの学習ではない)、ブログの文面を自動生成することを目指す。
20180922(土)
備忘のため。
1. SGDのS(stochastic: 確率的)のイミ。
2. Adamとは
1. そもそもNNの学習手順は
mini-batch処理、勾配の算出、パラメータの更新を繰り返す。
このときのmini-batch処理とは、訓練データの中からランダムに一部のデータを選び出す。
その選出がstochasticの由来
2. AdamはAdaGradとMomentumという、2つのパラメータの更新方法を融合したもの。
AdaGradは、大きく学習すると学習率を小さくし、小さく学習すると学習率を大きくするように調整する、パラメータの更新法。
Momentumは重みWの更新に、速度ベクトルvを導入したもの。
本「ゼロから作るDeep Learning ❷ ―自然言語処理編」の「6.3節RNNLMのさらなる改善」では
RNNLM(recurrent neural network language model)の改善モデルBetter RNNLMモデルを導入した。
そのモデルの学習用コードではcorpus, corpus_val, corpus_testとptbのデータセットから得られるcorpusを3つ作成していた。
その意図がわからない。
ptb.train.txtとptb.valid.txtとptb.test.txtとあるが、ある全体の文章を8:1:1に分割してそれぞれ作成してみてはどうか?
→した。うまくいきそう。明日の朝結果を確かめる
今の所ブログをスクレイピングしてきたデータは時系列順になっている。
corpusを8:1:1に分割してDLするなら、1ブログ単位でシャッフルしたほうが良いと思う。
→やろう
python3でサーバーをたて、ブログの最新更新日時や、自動生成したブログを返すようなコードをサーバー上で実行し、
アンドロイドアプリとして受け取るのはどうか?python3のサーバーは簡単に建てられたと思う。
20180923(日)
ch06/zelkova_train_better_rnnlm.pyを行った。8時間ぐらいかかった。
学習ではppl(パープレキシティ)が良い方向に更新されたときに、パラメータのsaveを行うのだが、
学習開始1時間半後が最終更新となっていた。そのため、あとの6時間半はpplを更新できていなかったのかも。
とにかく昨晩作成したパラメータ(zelkova_trained_weight_better_rnnlm_kobayashi.pkl)を用いて、
ch07/zelkova_generate_better_text.pyでブログの文章生成を行おうと思う。
→エラー
toasa:ch07 $ python3 zelkova_generate_better_text.py
Traceback (most recent call last):
File "zelkova_generate_better_text.py", line 25, in <module>
model.load_params('../ch06/zelkova_trained_weight_better_rnnlm_kobayashi.pkl')
File "../common/base_model.py", line 49, in load_params
param[...] = params[i]
ValueError: could not broadcast input array from shape (7647,650) into shape (10000,650)
20180924(月)
toasa:ch07 $ python3 /Users/tohyama/sample/python/zelkova/dl-master/ch07/zelkova_generate_better_text.py
私 の マスカラ に 踊っ て しまい まし た 。 ホワイト もらい まし た それ と 2017 みん が 信じ ない 方 は もう 出来る ん です よ よ ね ~ なんて 幸せ な ん です ファン 番組 の 大好き な 気分 は あっ たら 大丈夫 な そう だ な ~ と 思っ て い ます 。 ららぽーと 使い ない 力 。 という こと で どっち の こと で こういう 期生 の 人間 観 ましょ う (°´ ˘ `°)/ さあ どんどん 撮り は ます 。 明日 から 、 握手 会 汚れ 握 で 大阪 でし た ! ZIP の CM
できた。はじめての文章生成、小林由依のブログ。
こちらで最初の一文字目"私"を選択。残りの99文字は自動生成されている。
20180925(火)
ブログを取得し、csvファイルとして出力し、corpusまで作成するファイルをprepare/prep_all.pyとして実装した。コマンドライン引数にメンバーの
名前を書くことで実行できる
ex.
$ python3 prep_all.py kobayashi