tatsumack blog

エンジニアによる雑記です

AtCoder Beginner Contest 102 振り返り

3回連続で400点問題を落として水色チャレンジに失敗していたので、今回は久々の4完でホッとした。

初めて600点問題でACできたので、解説記事でも書こうかと思ったけど、他の方の非常に分かりやすい記事があったのと、他の人の思考過程を知りたいと思うことがよくあるので、今回は自分が解答に至るまでの思考過程を記してみようと思う。

今回のABCの配点は100-200-300-600で、明らかにC速解き勝負だったので、なるべく早く解くことを意識した。

A - Multiple of 2 and N

パッと問題文を読んだときは2*Nを出力すれば良さそうだと思ったけど、サンプルを見て、Nが2で割り切れるときはNを出力すれば良いことに気づく。
Submission #2765392 - AtCoder Beginner Contest 102

B - Maximum Difference

問題文を読んだ時点で、配列要素の最大値と最小値の差を引く、という方針が浮かんだので、そのまま実装する。
Submission #2765973 - AtCoder Beginner Contest 102

C - Linear Approximation

問題文を読んだ時点では、方針が全く浮かんでこなかったので、「C速解き失敗」が脳裏をよぎる。

落ち着いて、問題を簡単に考えることはできないかと、式を眺める。
 A_i - (b+i) は、 B_i = A_i - i とすると  B_i - b として考えることができることに気付く。
よって、配列内の各要素からの距離の総和が最小となるような bを考えれば良くなり、少し単純になる。
まあそれでもまだ分からない。

簡単に考えるために、要素数が2のケースで考えてみる。すると、 bは2要素の間にあれば良いことに気付く。
次に、要素数が3のときを考えてみる。このとき、真ん中の要素と bが一致すれば良いことが分かる。

ということで、 bは配列の要素の中央値を選べば良さそう、という気配が濃厚になったので、実装してみる。
サンプルがすべて通ったので、ちょっと不安はありつつも、提出してみる。

ジャッジサーバーが詰まっていたのか、なかなかジャッジが走らなくてそわそわしたが、無事ACが出たので、一安心。
Submission #2767475 - AtCoder Beginner Contest 102

目標がC速解きだったのと、Dの600点問題は解けるわけないと思っていたので、ちょっと集中力を切らしてtwitterを眺めたりする。

D - Equal Cut

この時点で順位表を見ると、1位だったのでびっくりした。(スクショ取っておけば良かった)
Dも頑張って解いてみるかと思い直し、問題文を読み始める。

部分和を求める必要があるので累積和を使いそうだなーとは思ったが、方針は全く浮かんでこない。

簡単に考えるために、切り口を1つだとして考えてみる。
このときは、配列内のすべての切り口の位置を調べれば、 O(N)で簡単に切り口の位置を求めることができる。

ということで、「切り口1つの位置を考えれば良い」という状況にどうにかして落とし込めれば、この問題は解けそうだと思い始める。

ここで、切り口3つのうち真ん中の切り口を固定すると、左右の切り口の位置は切り口1つの問題に落とし込めることに気付く。「3つあるうち真ん中を固定すると、残りが決まる」というのはよくある形だったこともあり、気付くことができた。

無事にサンプルが通ったので提出するも、TLE。
Submission #2771181 - AtCoder Beginner Contest 102

計算量を落とせる場所がないか考えてみる。
真ん中の切り口の位置を更新するたびに、左右の切り口の位置を全探索して調べるのは無駄なことに気付く。

よくよく考えると、左右の切り口の位置は右にずれていくだけなので、真ん中の切り口を移動する際に、前回の左右の切り口の位置を覚えておいて、そこから計算すれば良さそう。(尺取法的なアプローチ)
Submission #2771925 - AtCoder Beginner Contest 102

サンプルが通ることを確認して、提出して、祈る。。
AC!初めて600点問題を通すことができた。

Dの提出直後は3位だったが、1WAだったこともあり、最終的な順位は4位だった。


振り返り

C問題もD問題も、パッと見よく分からないので、問題を簡単にして考えてみる、というアプローチが上手くいった。直近のコンテストで400点問題が解けないときは難しく考えすぎていたので、その反省が活かせたと思う。

次こそ水色!

はりぼてOSをNASM・GCCで動かす(Mac OSX)

「30日でできる!OS自作入門」を読んだ。

30日でできる! OS自作入門

30日でできる! OS自作入門

この本で開発する「HariboteOS」は作者の独自ツールを使って動かしているが、GNUのツール群で置き換えてビルドできるようにしてみた。

環境

Mac OSX El Capitan(10.11.2)

NASM(Netwide Assembler)に置き換える

作者独自ツールのNASKをNASMに置き換える。
主要なアセンブラとして、NASMの他にGAS(GNU Assembler)が挙げられるが、GASの構文はNASKと大きく異なるので、NASMで置き換えることにした。
参考: Linux のアセンブラー: GAS と NASM を比較する

下記のページに記載のある通り、置き換えをすればアセンブラできるようになる。
http://hrb.osask.jp/wiki/?tools/nask

対応コミット
Replace nask with nasm · tatsumack/HikariOS@877ec9d · GitHub

GCC

C言語で実装されたファイルも作者の独自ツールを使ってコンパイルされていたので、GCCに置き換えてみた。

GCCのビルド

hrb形式のファイルを作成するためには、リンカスクリプトを作成しリンカに渡す必要があるが、
Mac OSXのデフォルトのリンカ(ld)はリンカスクリプトを受け付けるオプションがないので、クロスコンパイラなGCCをビルドする必要がある。
ビルド手順についてはQiitaにまとめた。
qiita.com

その他にやったことの箇条書き

・nasmの出力形式をwin32からelfに変更
・.hrb形式のリンカスクリプト作成
・naskfunc.nasの関数のシンボル名のprefixの_を削除
・色々とライブラリがないので、自作OS本付属のomake/tolsrc/go_0023s/golibcから静的ライブラリを作成し、リンクする
・__builtin_stdarg_startを__builtin_va_startにrename

対応コミット
Replace gocc with gcc · tatsumack/HikariOS@ab4b5d4 · GitHub

「はじめて読む486」を読んだ

はじめて読む486―32ビットコンピュータをやさしく語る

はじめて読む486―32ビットコンピュータをやさしく語る

世間では機械学習・ディープランニングが盛り上がっている中、低レイヤの勉強がマイブームになっている。
この本はIntel486のアーキテクチャについて解説した本で、1994年に書かれた20年以上も前の本ではあるが、名著だと評判なので読んでみた。
(会社の図書スペースにたまたま置いてあったというのもある)

年齢のせいか、1回読んだ本の内容を忘れることが多くなってきたと感じるので、1回読んだ後に再度読み直して、要点をまとめてみた

1. プロローグ

486の3つの動作モード

486は当時広く普及していた8086(x86アーキテクチャの最初のCPU)との互換性を保ちながら、新しい機能と採用するために3つの動作モードがあった。

  • リアルモード
    • 8086との互換性を保つためのモード
    • MS-DOS(マイクロソフトが開発した8086系CPU向けのOS)用アプリケーションを動かす
  • プロテクトモード
    • メモリ管理やタスク管理などの拡張機能を利用できるモード
  • 仮想8086モード
    • プロテクトモードの恩恵を受けながら8086向けのアプリケーションを動かすモード

32bitサポート

486では32bitサポートされ、16bit CPUの8086よりも大きなデータサイズを扱えるようになった。

  • 16bitCPUの64KBの壁
    • 16bitの限界 = 2^16 bit = 64KB
    • 連続して扱える領域は64KBまでに制限される→配列の最大サイズに影響を与える
  • 16bitCPUの640KBの壁
    • 8086ではアドレスを20bitで表すため、利用できるメモリサイズの限界は1MB
    • 360KBをシステムで利用するので、アプリケーションが使えるのは1MB - 360Kb = 640KB
  • 32bit CBUではより大きなデータサイズ、メモリを扱うことができるようになる(物理的な制限は4GB)

2. 486の履歴書

  • 8086から486までのCPUの発展
    • プロテクトモードは286から導入された
    • 32bitサポートは386から
  • 486DX
  • キャッシュメモリ
    • 486の性能向上に最も寄与している
    • CPUの近くに高速なメモリを置いて、一部のデータをキャッシュすることで高速なメモリアクセスを実現した
    • 高速な分、高価なのでデータサイズは小さい(486では8KB)
    • 書き出しのときにキャッシュだけでなく、本来のメモリにも書き込むライトスルー方式を採用している
    • これに対して、キャッシュに書き込むのとは別のタイミングで本来のメモリに書き込むライトバック方式という方法がある
    • ライトバック方式は書き込みの速度を上げることができるが、データの一貫性を保つのが難しい
  • 486SX
    • 486DXの廉価版
    • 実態は486DXと全く一緒で浮動小数点演算機能を無効にしたもの
    • 無効にした分、検査が不要になり、製造コストを下げることができた
  • 486DX2 / ODP
    • 「クロックダブラー」を用いて高速化を実現
    • CPU内部においてクロック速度を2倍にする
    • 低速な外部システムに引きずられることがなくなる

3.オペレーティング・システム

  • プロセス管理
    • Windows 3.1はイベント駆動
      • アプリケーション側でイベント待ちのときに他のタスクに切り替える
      • お行儀の悪いアプリケーションが暴走すると、システム全体が引きずられて停止状態になることがある
    • Windows NTやOS/2プリエンプティブマルチタスク
      • 一定時間ごとのハードウェア割り込みを利用して、割り込み時にタスクの実行権を取り上げ、他のタスクに切り替える
      • 他のタスクに影響されなくなる
  • メモリ管理

4.プロテクトモード

  • CR0(コントロールレジスタ0)のPEビット(Protection Enable)を1にするとプロテクトモードに移行、0にするとリアルモードに移行
  • 移行する際はJMP命令でパイプラインをクリアする必要がある
    • パイプラインとは、命令実行の工程を読み出し・解釈・実行といった複数の段階に分け、ある命令を「実行」している間に次の命令の「解釈」次の次の命令の「実行」を並行して行う処理
    • リアルモードからプロテクトモードに移るとき、リアルモードの命令がパイプラインに残ってしまっているので、パイプラインを無効化する必要がある

5.セグメント

  • セグメントとは、メモリを一定のサイズで区画割りする方式
    • セグメントによって、タスク間のメモリ分離・保護ができる
    • 8086では、メモリ分離・保護機能はなかったものの、16bitレジスタで64KB以上のアドレスにアクセスするためにセグメント機能を採用していた
  • セグメントアドレスとオフセットアドレス
    • CPUが実行するマシン語プログラムでは物理アドレスでメモリを指定することはできず、セグメントアドレスとオフセットアドレスを用いて指定する
    • セグメントアドレスはセグメントに付けた番号、オフセットアドレスはセグメントの先頭から数えた番号
    • セグメントアドレスはセグメントレジスタに格納し、個々の命令ではオフセットアドレスを指定する
  • リアルモードのセグメント
    • セグメントベースは、セグメントアドレスを物理アドレスの上位16bitに当てはめ、下位4bitを0としたものになる
    • アドレスは20bitで表せる範囲=1MBが上限になる
  • プロテクトモードのセグメント
  • 32ビットセグメント
    • リアルモードではオペランドサイズ・アドレスサイズのデフォルト値は16bit
    • プロテクトモードは16bit・32bitのどちらも設定可能
      • CSレジスタが16bitセグメントを指すときはサイズのデフォルトが16bit、32bitセグメントを指すときは32bitになる
      • コードセグメントが16bitか32bitかは、セグメントディスクリプタ中のDビットで決まる

6.保護

  • セグメントリミット
    • すべての命令に先立ち、メモリのオフセットアドレスがリミット値を超えないかチェックする
    • リミット値はセグメントディスクリプタにセットされている
  • セグメント属性
    • セグメント属性によって、使用できるレジスタが制限されている
      • コードセグメントはCSレジスタ、データセグメントはCS以外のセグメントレジスタ(DSなど)
      • リアルモードでは制限されていなかった
  • 特権レベル
    • 実行できる命令の種類とアクセスできるメモリの範囲を規定する
      • 特権レベル0が一番強く、3が一番弱い
      • 0はOS、1~2はデバイスドライバ、3はアプリケーション
    • セグメントごとに特権レベルが定義されており、それをDPLと呼ぶ
    • プログラム実行中の動作レベルをCPLと呼び、実行中のコードセグメントのDPLによって決まる
      • 異なる特権レベルのセグメントに直接ジャンプすることはできない
      • セグメントレジスタセレクタ値をロードする瞬間に、セグメントアクセスのチェックが行われる
      • セグメントの特権レベルが動作レベルよりも高い場合はフォールトを発生させる
    • 上位レベルのコードセグメントを呼ぶときは、コールゲートを介して呼ぶ
      • コールゲートはディスクリプタセグメント中に作成され、セグメントと同様の呼び出し方をする

7.割り込み

  • 割り込み要因
    • ハードウェア割り込み、トラップ、フォールト、アボート
    • 割り込み要因に対応した「割り込み番号」があり、それに対応する割り込み処理ルーチンがある
  • リアルモードでの割り込み処理
    • 割り込み番号と処理ルーチンの対応を「割り込みベクタテーブル」によって設定する
    • 割り込みベクタテーブルは物理アドレス00000Hから固定で1KB確保されている
  • プロテクトモードでの割り込み処理

8.タスク

  • TSS
    • タスク状態の保存・復元に使用するデータ構造
      • タスク1つにつき必ず1つ持つ
      • タスク切り替え時のCPUレジスタの値、OSのファイル・デバイスの管理状況などを持つ
      • TSSを指し示すTSSディスクリプタがある
  • TR
    • 現在のTSSのセレクタ値を保持するレジスタ
    • タスク切り替えでは、jmp命令を用いてTRの指す先を変え、切り替え先のTSSからレジスタ内容を復元し、タスク切り替えを行う

9.ページング

  • ページング方式
    • メモリを固定長に分割して扱う方式
      • セグメント方式はメモリを任意の大きさで区分けする
    • 論理空間におけるページ(論理ページ)を物理メモリのページ(物理ページ)に対応付けてアドレス変換を行う
      • 論理ページと物理ページの対応はタスクごとに独立している
  • 仮想記憶
    • 物理メモリに紐付けられていない論理ページアクセスした際にページフォルトを発生させ、使用されてない論理ページに対応する物理ページをディスクに退避し(ページアウト)、空いた物理ページにディスクから読み込む(ページイン)
    • 実際の物理メモリよりも大きなメモリ空間を扱うことができる
  • 486ではセグメント方式とページング方式を組み合わせてメモリ管理をしている
    • 物理メモリを論理ページに対応付けする(リニアアドレス空間)
    • リニアアドレス空間をセグメント方式によって管理する。つまりページ単位で管理する。
      • セグメント方式のメモリ保護やタスク間のメモリ分離と、ページングの仮想記憶のいいとこ取り
  • ページング機構
    • CR0のPGビットを立てるとページング機構が有効になる
    • リニアアドレスから物理アドレスへの変換では、ページディレクトリテーブル→ページテーブル→ページ→物理メモリと辿っていく
      • 各ページテーブルも仮想記憶の対象とし、最近アクセスのあったページテーブルのみをメモリに置くことで、メモリ効率を高めている
  • PTE
    • ページングに使用されるメモリ上のデータ構造
    • ページ番号
      • PTEの上位20bitに記述され、下位12bitを0で埋めるとページの先頭アドレスになる
    • Pビット
      • PTEに対応するページがメモリに存在するか
    • Aビット
      • 読み書きすると1がセットされる。OSがページアウトの対象を選定するときに用いる。
    • Dビット
      • 書き込み時に1をセットする。ページアウトの際にディスクに書き込むかを判定するのに用いる
  • TLB

10.セキュリティ

  • 要求者特権レベル
    • 本来そのセグメントにアクセスしようとしたプログラムの特権レベル
      • 特権レベルの乗っ取りを防ぐ
  • コンフォーミングセグメント
    • 特権レベルを移行することなく、特権0のプログラムをアプリケーションから呼び出せるしくみ
    • コードセグメントの一種
      • 特権レベル移行時のオーバーヘッドを気にする必要がなくなる
    • コンフォーミングセグメント呼び出し時は動作レベルが変化しない = CPUの動作レベルとセグメントの特権レベルが異なる
  • LDT(ローカルディスクリプタテーブル)
  • I/O許可マップ
    • タスクごとにIOポートのアクセス制限をする
    • TSS内にI/O許可マップを保持する

このあと「11.仮想8086モード」、「12.DOMエクステンダーとDPMI」、「13.486応用プログラミング」と続くが、疲れてきたので割愛。

CPUの挙動の理解が深まる良い本だった。

この本を読み終わった後に、以下の記事などでIntel CPUの歴史を追ってみたりもした。
@IT:PCエンサイクロペディア:第7回 PCのエンジン「プロセッサ」の歴史(1)〜i8088からIntel386までの道のり 1. IBM PCシリーズに採用された86系16bitプロセッサたち
@IT:頭脳放談:第27回 RISCの敗因、CISCの勝因

「君の名は。 Another Side:Earthbound」を読んだ

特に気になっていた三葉の父親の心理描写が描かれており、映画を見てモヤモヤしていた部分がスッキリした。

「君の名は。」を読んだ

年末にようやく「君の名は。」を映画館で見ることができ、その余韻に浸ったままKindleでポチった。
一人称で物語が描かれている点が映画とは異なるが、ストーリーは同じ。なので、異なる描写があることを期待して読むとがっかりするかもしれないが、映画の余韻に浸る分には申し分ない本だった。あとがきで、新海誠監督と川村元気プロデューサーがどういう目線でこの作品を作ったのかを述べているのも興味深い。

「ゲームプログラマになる前に覚えておきたい技術」を読んだ

ゲームプログラマになる前に覚えておきたい技術

ゲームプログラマになる前に覚えておきたい技術

学生時代に3Dゲームを開発する授業があり、その際の参考図書として購入していた本。
去年、サーバーサイドエンジニアからモバイルゲームのクライアントエンジニアに転向するにあたり、もう一度読み直してみた。

いくつかのサンプルゲームの開発を通じて、ゲーム開発に必要なスキルを広範囲に渡って解説しており、ゲーム開発に必要な技術の全体像を掴むのに最適な本だと思う。C++、2D・3Dグラフィクス、シーケンス遷移、衝突処理、サウンド、データ構造・アルゴリズム、マルチスレッド処理と多岐に渡る技術領域を取り上げている。800ページ超の大作だが、説明が丁寧かつ語り口調ベースなので、比較的すらすら読める。ゲーム開発に対する筆者の哲学を所々で語っているのも良かった。

なお、タイトルからは初心者向けの本のように見えるが、C++でのコーディング経験があって、CPUやメモリが何をやっているのかがざっくりイメージできるような方が対象になると思う。

2016年振り返り

🍻を飲みながら雑に振り返っておく。

マネージャー

エンジニア組織のマネージャーになった。模索しながら手探りでやっていたが、振り返ると、メンバーの育成やモチベーションコントロールに意識が取られすぎて、組織がどうあるべきか、組織がどういう方向に進むかを示して引っ張るようなアクションが弱かったように思う。

反省点は多いが、チャレンジングなアサインをしたメンバーがしっかり成果出して成長する姿を見ることができたのは良かった。組織に漂っていた閉塞感を打破しようと、攻めのアサインを行うことを心がけた。組織にとってやはり一定の新陳代謝が必要だと思うので、来年もこれは心がけたい。

バイルネイティブゲームのクライアントエンジニア

主戦場をwebからモバイルネイティブに移した。プログラミング言語的にはPerlJavaScriptから、C++をメインに扱うようになった。メモリ管理面倒だなーと思う一方で、それも含めてCPUの気持ちになってコードを書くのが楽しい。低レイヤをもっと知りたい欲が出てきたし、自作コンパイラ作ってみたいと思うようになった。

筋肉

一念発起して、筋トレを始めた。腹筋も割れてきたし、痩せたし、仕事のパフォーマンスも上がった気がするので、良いこと尽くしだ。

来年やりたいこと

  • OSSへのコントリビュート
  • 英語
  • Rust
  • 自作コンパイラ
  • グラフィックAPI
  • 読んだ本の感想をブログに書く

 

来年は20代最後だし、悔いのない1年にしたい。