11 Apr 2015, 06:52

C 言語/C++ における イベントハンドラの定石 (switch/ 関数ポインタ配列/lambda)

はじめに

C/C++ における イベントハンドラの書き方について,定石を整理してみた.

[toc]

前提

<div class="outline-text-3" id="text-unnumbered-2">
  <p>
    以下のようなコードがあるとする.
  </p>

  <p>
    [sourcecode language=&#8221;cpp&#8221; title=&#8221;&#8221; ]<br /> #include <iostream><br /> typedef enum {START, STOP} COMMAND;
  </p>

  <p>
    void check (COMMAND command) {<br /> std::cout << (int) command << " is called" << std::endl; } int main (int argc, char *argv[]) { check (START); check (STOP); return 0; } [/sourcecode] 

    <p>
      出力結果は以下のようになる.
    </p>

    <p>
      [sourcecode language=&#8221;text&#8221; title=&#8221;&#8221; ]<br /> 0 is called<br /> 1 is called<br /> [/sourcecode]
    </p>

    <p>
      この出力結果は以下のようにしたい.
    </p>

    <p>
      [sourcecode language=&#8221;text&#8221; title=&#8221;&#8221; ]<br /> start is called<br /> stop is called<br /> [/sourcecode]
    </p></div> </div> </div> 

    <div id="outline-container-unnumbered-3" class="outline-2">
      <h2 id="unnumbered-3">
        方法
      </h2>

      <div class="outline-text-2" id="text-unnumbered-3">
      </div>

      <div id="outline-container-unnumbered-4" class="outline-3">
        <h3 id="unnumbered-4">
          switch を使う
        </h3>

        <div class="outline-text-3" id="text-unnumbered-4">
          <p>
            一番単純な方法は, switch をつかって, 表示を分岐する
          </p>

          <p>
            [sourcecode language=&#8221;cpp&#8221; title=&#8221;&#8221; ]<br /> void onStart () { std::cout << "start is called" << std::endl; } void onStop () { std::cout << "stop is called" << std::endl; } void check (COMMAND command) { switch (command) { case START: onStart (); break; case STOP: onStop (); break; } } }; [/sourcecode] </div> </div> 

            <div id="outline-container-unnumbered-5" class="outline-3">
              <h3 id="unnumbered-5">
                関数ポインタ配列を使う
              </h3>

              <div class="outline-text-3" id="text-unnumbered-5">
                <p>
                  別の定石は, 関数ポインタ配列をつかう.
                </p>

                <p>
                  [sourcecode language=&#8221;cpp&#8221; title=&#8221;&#8221; ]<br /> #include <iostream>
                </p>

                <p>
                  typedef enum {START, STOP} COMMAND;
                </p>

                <p>
                  void onStart () { std::cout << "start is called" << std::endl; } void onStop () { std::cout << "stop is called" << std::endl; } typedef void (*HANDLER) (); static HANDLER handle_tbl[2] = {&onStart, &onStop}; void check (COMMAND command) { handle_tbl[command] (); } [/sourcecode] </div> </div> 

                  <div id="outline-container-unnumbered-6" class="outline-3">
                    <h3 id="unnumbered-6">
                      lambda をつかう
                    </h3>

                    <div class="outline-text-3" id="text-unnumbered-6">
                      <p>
                        関数テーブルに関数を登録するために, 関数を作成する必要があるけれども, 一行なので, 関数を作成するのは面倒.
                      </p>

                      <p>
                        そんなときは,c++11 からつかえるようになったラムダ式を利用する.
                      </p>

                      <p>
                        [sourcecode language=&#8221;cpp&#8221; title=&#8221;&#8221; ]<br /> #include <iostream><br /> #include <functional>
                      </p>

                      <p>
                        typedef enum {START, STOP} COMMAND;
                      </p>

                      <p>
                        static std::function<void ()> handle_tbl[2] = {<br /> [] (){ std::cout << "start is called" << std::endl;}, [] (){ std::cout << "stop is called" << std::endl;} }; void check (COMMAND command) { handle_tbl[command] (); } int main (int argc, char *argv[]) { check (START); check (STOP); return 0; } [/sourcecode] 

                        <p>
                          やっぱり, これからは関数型の時代だよね!
                        </p></div> </div> </div> 

                        <div id="outline-container-unnumbered-7" class="outline-2">
                          <h2 id="unnumbered-7">
                            Special Thanks
                          </h2>

                          <div class="outline-text-2" id="text-unnumbered-7">
                            <p>
                              この記事によると, switch 型と関数テーブル型では, スピードは変わらないとか.
                            </p>

                            <ul class="org-ul">
                              <li>
                                <a href="http://dixq.net/forum/viewtopic.php?f=3&t=13875">関数ポインタテーブルと switch 文 • C 言語交流フォーラム ~ mixC++ ~</a>
                              </li>
                            </ul>

                            <p>
                              委譲をつかう方法もある (Strategy Pattern)
                            </p>

                            <ul class="org-ul">
                              <li>
                                <a href="http://www7b.biglobe.ne.jp/~robe/pf/pf016.html">プログラマの友 第十六報:イベントハンドリングとデリゲート</a>
                              </li>
                            </ul>

                            <p>
                              C++11 の方法.
                            </p>

                            <ul class="org-ul">
                              <li>
                                <a href="http://qiita.com/shiro_naga/items/5967f6cd1710e7b78677">C++ &#8211; メンバー関数ポインタと配列を使って, メンバー関数を番号で指定して呼び出す方法 &#8211; Qiita</a>
                              </li>
                              <li>
                                <a href="http://kaworu.jpn.org/cpp/std::function">std::function &#8211; C++ 入門</a>
                              </li>
                            </ul>
                          </div>
                        </div>

28 Mar 2015, 23:47

Emacs で C/C++ の開発環境をめちゃガチャパワーアップしたまとめ

はじめに

次の業務が C/C++ をつかいそうなので, Emacs で C/C++ 開発環境を構築してみました.

題名は, なぜかけっこうアクセス数のあった Ruby 編にあやかった.

[toc]

IDE が備えるべき機能

優れた IDE が備えるべき機能と Emacs での代表的な実現方法は以下.

  • シンタックスハイライト/ インデント
    • major-mode
  • 検索・置換
    • たくさんあるよ.
  • タグジャンプ
    • gtags
    • ggtags
  • コード補間
    • auto-complete
    • company
  • エラーチェック
    • flymake
    • flycheck
  • リファクタリング
    • emacs-refactor
  • インタープリタ・デバッカ
    • emacs-dbgr
  • プロジェクト管理
    • projectile
  • ドキュメント参照
    • eldoc

最近, 以下の記事を見つけたので, 刺激をうけてまとめた.

Eclipse よりも Emacs が好き

かつて, Eclipse に洗脳されていた若き日の自分は, Eclipse における C/C++ の開発環境を徹底的に調べた.

Emacs と Eclipse どちらが優れているか?

機能的には, 優劣つけがたい. あとは好き嫌いだと思う.

  • ゴテゴテの Eclipse の UI が嫌い
  • Emacs のテキスト操作における圧倒的優位性

を考慮すると, 今は Emacs のほうが好きだ.

ただ, Emacs は 以下に書くように 設定が大変 なので,

  • 導入が面倒なひと
  • 初心者
  • サラリーマン

は Eclipse CDT でよいのでは??

実際の設定

github の dotfiles のリンクをはっておきます.

major-mode

C 言語・ C++ のためのモード.

cc-mode

C, C++, Objc, Java などなどをいっぺんに設定するモード

マニュアル.

c-mode-common-hook は java にも適用されてしまうようだ.

(require 'cc-mode)

;; c-mode-common-hook は C/C++ の設定
(add-hook 'c-mode-common-hook
          (lambda ()
            (setq c-default-style "k&r") ;; カーニハン・リッチースタイル
            (setq indent-tabs-mode nil)  ;; タブは利用しない
            (setq c-basic-offset 2)      ;; indent は 2 スペース
            ))

c++-mode

C++ 言語固有設定.

以下の記述でヘッダファイルが c++ として認識される.

(add-to-list 'auto-mode-alist '("\\.h\\'" . c++-mode))

Error Check

今は, flymake よりも, flycheck でしょう.

flycheck

gcc, clnag, cppcheck が default のチェッカーとして用意されている.

参考: 今は自分で定義しなくても build-in されているよう.


(add-hook 'c-mode-common-hook 'flycheck-mode)
  • checker の変更は M-x flycheck-select-checker
  • helm-flycheck で helm i/f から エラーを選択.

gcc

gcc だとなにも検出してくれない.なんでだろう. -> 結果が日本語表示だったから

(defmacro flycheck-define-clike-checker (name command modes)
  `(flycheck-define-checker ,(intern (format "%s" name))
     ,(format "A %s checker using %s" name (car command))
     :command (,@command source-inplace)
     :error-patterns
     ((warning line-start (file-name) ":" line ":" column ": 警告:" (message) line-end)
      (error line-start (file-name) ":" line ":" column ": エラー:" (message) line-end))
     :modes ',modes))
(flycheck-define-clike-checker c-gcc-ja
                   ("gcc" "-fsyntax-only" "-Wall" "-Wextra")
                   c-mode)
(add-to-list 'flycheck-checkers 'c-gcc-ja)
(flycheck-define-clike-checker c++-g++-ja
                   ("g++" "-fsyntax-only" "-Wall" "-Wextra" "-std=c++11")
                   c++-mode)
(add-to-list 'flycheck-checkers 'c++-g++-ja)

Refactoring

semantic-refactoring

Semantic Refactor is a refactoring tool for C/C++.

ついに見つけた, extract method. menu で番号を選択するとバグっているので, Enter で選択.(そのうちなおるかと)

(require 'srefactor)
(define-key c-mode-map (kbd "M-RET") 'srefactor-refactor-at-point)
(define-key c++-mode-map (kbd "M-RET") 'srefactor-refactor-at-point)

Completion

auto-complete-c-headers

ヘッダの情報源

(require 'auto-complete-c-headers)
(add-hook 'c++-mode-hook '(setq ac-sources (append ac-sources '(ac-source-c-headers))))
(add-hook 'c-mode-hook '(setq ac-sources (append ac-sources '(ac-source-c-headers))))

clang-complete-async

clang を利用した 補完. 構造体とかもばっちり!

(require 'auto-complete-clang-async)

(defun ac-cc-mode-setup ()
  (setq ac-clang-complete-executable "~/.emacs.d/el-get/repo/clang-complete-async/clang-complete")
  (setq ac-sources (append ac-sources '(ac-source-clang-async)))
  (ac-clang-launch-completion-process))

(defun my-ac-config ()
  (add-hook 'c-mode-common-hook 'ac-cc-mode-setup)
  (add-hook 'auto-complete-mode-hook 'ac-common-setup)
  (global-auto-complete-mode t))
  (my-ac-config)

function-args

C/C++ 用の 補完. CEDET のモダンな置き換え.

moo-complete で構造体やクラス変数が置換できるのがうれしい.

  • M-o moo-complete semantic な補完
  • M-i fa-show 関数ヒントをポップアップ
  • M-j fa-jump-maybe ポップアップ状態でオスとジャンプ
  • moo-propose-overide オーバーライドを suggest
  • moo-propose-variable 変数を suggest
(require 'function-args)
(fa-config-default)

(define-key function-args-mode-map (kbd "M-o") nil)
(define-key c-mode-map (kbd "C-M-:") 'moo-complete)
(define-key c++-mode-map (kbd "C-M-:") 'moo-complete)

(custom-set-faces
 '(fa-face-hint ((t (:background "#3f3f3f" :foreground "#ffffff"))))
 '(fa-face-hint-bold ((t (:background "#3f3f3f" :weight bold))))
 '(fa-face-semi ((t (:background "#3f3f3f" :foreground "#ffffff" :weight bold))))
 '(fa-face-type ((t (:inherit (quote font-lock-type-face) :background "#3f3f3f"))))
 '(fa-face-type-bold ((t (:inherit (quote font-lock-type-face) :background "#999999" :bold t)))))

rtags

clang をつかった便利機能詰め合わせ.

設定が大変そうだな.. これは今回は挫折.

fixit って, 自動エラー修正? スゴそう.

Document

ggtags

ggtags も c 言語ように eldoc 機能を提供している. ggtags は後述.

c-eldoc

C 言語用 eldoc 機能.

(require 'c-eldoc)
(add-hook 'c-mode-hook 'c-turn-on-eldoc-mode)
(add-hook 'c++-mode-hook 'c-turn-on-eldoc-mode)
(setq c-eldoc-buffer-regenerate-time 60)

Debugger

gdb

M-x gdb 標準搭載.

emacs-dbgr

デバッグ用 統一 I/F M-x realgud:gdb

gdb との違いはよくわからない.

(require 'realgud)

その他

タグジャンプ

ggtags

タグジャンプ用のツール. GNU Global を利用.

(require 'ggtags)
(add-hook 'c-mode-common-hook
          (lambda ()
            (when (derived-mode-p 'c-mode 'c++-mode 'java-mode 'asm-mode)
              (ggtags-mode 1))))

;; use helm
(setq ggtags-completing-read-function nil)

;; use eldoc
(setq-local eldoc-documentation-function #'ggtags-eldoc-function)

;; imenu
(setq-local imenu-create-index-function #'ggtags-build-imenu-index)

(define-key ggtags-mode-map (kbd "C-c g s") 'ggtags-find-other-symbol)
(define-key ggtags-mode-map (kbd "C-c g h") 'ggtags-view-tag-history)
(define-key ggtags-mode-map (kbd "C-c g r") 'ggtags-find-reference)
(define-key ggtags-mode-map (kbd "C-c g f") 'ggtags-find-file)
(define-key ggtags-mode-map (kbd "C-c g c") 'ggtags-create-tags)
(define-key ggtags-mode-map (kbd "C-c g u") 'ggtags-update-tags)

(define-key ggtags-mode-map (kbd "M-,") 'pop-tag-mark)

helm-gtags

helm I/F を利用した gtags 操作. 自分は ggtags をつかってる.

projectile

プロジェクト管理用の デファクトスタンダード.

自動でプロジェクトのルートディレクトリを探して, それ以下のファイルを見つけたり色々できる.

.projectile ファイルをマニュアルで作成することで, そのフォルダを Route Folder と認識出来る.(要 Emacs 再起動)

(require  'projectile)
(projectile-global-mode)

;; windows indexing 高速化のおまじない.
(setq projectile-indexing-method 'alien)

  ;; 大きいプロジェクトだと劇的に速度が改善するらしい.
(setq projectile-enable-caching t)

GNU Global と組み合わせるには, ggtags が必要.(gtags ではないので注意)

以下で GTAGS を作成.

  • projectile-regenerate-tags
(when (executable-find "gtags")
   (setq projectile-tags-file-name "GTAGS")
   (setq projectile-tags-command "gtags")))

helm-make

C 言語といったら make でしょう. make 用 helm I/F.

(require 'helm-make)

(eval-after-load 'makefile-mode
  '(define-key makefile-mode-map (kbd "M-\"") 'helm-make-projectile))
(define-key c-mode-map (kbd "M-\"") 'helm-make-projectile)
(define-key c++-mode-map (kbd "M-\"") 'helm-make-projectile)

Special Thanks

07 Mar 2015, 11:56

システム制御は奥が深い! 井戸の中の蛙な自分.coursera で Cloud Computing Cocepts をうけた

はじめに

coursera で クラウドコンピューティングを学ぶ講座をとりました.

分量が多いので, Cloud Computing Concepts は Part1,2 に分かれている. 今回は, Part1 についての記事.

これは, クラウドコンピューティング 3 シリーズのなかのはじめに位置する講座です.

  • Distribute Systems
  • Cloud Application
  • Cloud Networking.

内容

内容は分散コンピューティングについての古典的な理論から, 最新の研究の話題まで, 幅広い.

Part1 では, 以下を学んだ.

  • Introduction

Clouds, Mapreduce, Key-value stores

  • Classical Precursors

Peer-to-ppeer systems, Grids

  • algorithms

Gossip, Membership, Paxos

  • Classical algorithms

Time and Ordering, Snapshots, Multicast

NoSQL や P2P の最前線の話題についても触れる.

動画がとても早口 (通常速度で x1.3-5 くらい?) あまり英語を聞き取れず. もっぱら以下の本の該当個所を読みながら進めた.

プロクラミングの課題もある. C++ で実装する.

感想

以前の仕事について

この記事とかぶる部分もあるが, もう一度.

今働いている会社の部署は, サーバやストレージ製品の制御ファームをつくっている. クラウドコンピューティングに関わる製品の設計開発だ.

そして自分はというと, 今でこそ名実ともに窓際族であるので 部署の仕事とまったく関係ない遊び人をしているが, かつてはストレージ製品の開発に関わってた.

自分の担当していた機能は, 異常検出.

2,4,8 ノードのそれぞれ独立した RAID コントローラが, それぞれを互いに監視しあう. あるコントローラで異常が発生したときは, 別のコントローラが異常をすばやく検出して, エラーリカバリを実施する.

なので, 以今回学んだことは前の仕事にかなり関わってた.

あまりに無知だった

8 ノードでの異常検出について自分の頭でいろいろ考えた.

自分の知らないところでは, そのような知識は体系化されて, 理論的な裏付けがされていて, 改良されていることなど, 想像だにしなかったことだった.これには, とても驚いた.

以下, 具体例をあげる.

Failure Detector/HeartBeating

異常検出については, 以前の記事でまとめた.

Membership List

自分の関わってきた製品は, 最大 8 ノードまでだったが, 今後はノードが動的に追加できる, スケールアウト型ストレージの需要がでてくるかもしれない.

今までは, 固定の構成で仕様を考えていたが, 動的に変更されるような構成で仕様を考えることになるかもしれない.

スケールアウト型の制御方法で王道的な制御方法として MembershipList による制御があることをしった.

Consensus

Master-Slave アーキテクチャで制御しているとき, Master であるノードで異常が発生したさいに, 次の Master ノードを決定する必要がある.

また, 複数ノード同時に異常を検出した場合, 被疑個所がノードにあるの か通信経路にあるのかを決定して, たのノードと合意をとる必要がある.

このような, 複数のノード間で単一の結果について合意を得るプロセス は Consensus 問題と呼ばれていて, それに対して効果的なアルゴリズム の研究がされている.

システム制御は奥が深い! そして自分は井戸の中の蛙だった

自分の所属している部署は, 自称システム制御を得意としているが, それは井戸の中の蛙のような気がしてきた. いったい, なにと比較して得意だといっているのだろうか? 年月だけ重ねても, 世の中についていけなければ意味がない.

他のクラウド製品が, フォルトトラレント性を確保するために どのようなことをしているのか, まったく無知である. それらは企業秘密ということもあり, 特許で防衛しているところもある.

しかし, 世の中では, 分散コンピューティングの理論やアルゴリズムが 日進月歩で開発されていて, Yahoo, Google, Facebook などの先端企業は そのような技術を取り入れている.

新しい技術に対して無知であることは, 世の中からとりのこされるばかりか, 自分たちの仕事すらなくなってしまうおそれのある, 非常に危険なことだ.

継続して技術動向を追いかけていくような態度が必要だ. それは, 自分にも必要だが, 組織にも必要だ.

15 Feb 2015, 10:22

Flycheck で g++ の日本語表記のコンパイルエラーがパースできていなかった (C/C++)

はじめに

Emacs の エラーチェッカーで flycheck がある.静的文法チェック. flymake の後継.

C++ でつかってみると, どうも動かないので調べてみたメモ.

Build-in

マニュアルによると, gcc, clnag, cppcheck が default のチェッカーとして用意されている.

パーサーを見てみると..

ソースを除いてみると, たとえば gcc のパーサーは以下.

(flycheck-define-checker c/c++-gcc
  "A C/C++ syntax checker using GCC.

Requires GCC 4.8 or newer.  See URL `https://gcc.gnu.org/'."
  :command ("gcc"

    "長いので途中省略"

  :error-patterns
  ((error line-start
          (message "In file included from") " " (file-name) ":" line ":"
          column ":"
          line-end)
   (info line-start (file-name) ":" line ":" column
         ": note: " (message) line-end)
   (warning line-start (file-name) ":" line ":" column
            ": warning: " (message) line-end)
   (error line-start (file-name) ":" line ":" column
          ": " (or "fatal error" "error") ": " (message) line-end))
  :error-filter
  (lambda (errors)
    (flycheck-fold-include-levels (flycheck-sanitize-errors errors)
                                  "In file included from"))
  :modes (c-mode c++-mode)
  :next-checkers ((warning . c/c++-cppcheck)))

おかしいなぁと悩むこと 1 時間近く… パーサーの文字が英語だと気づいた…

自分の環境では, g++ を走らせると,

  • error -> エラー
  • Warining -> 警告

と表示される.

日本語表記で checker を定義

しかたがないので, 自分で定義をする.

(require 'flycheck)
(add-hook 'c-mode-common-hook 'flycheck-mode)

(defmacro flycheck-define-clike-checker (name command modes)
  `(flycheck-define-checker ,(intern (format "%s" name))
     ,(format "A %s checker using %s" name (car command))
     :command (,@command source-inplace)
     :error-patterns
     ((warning line-start (file-name) ":" line ":" column ": 警告:" (message) line-end)
      (error line-start (file-name) ":" line ":" column ": エラー:" (message) line-end))
     :modes ',modes))
(flycheck-define-clike-checker c-gcc-ja
                   ("gcc" "-fsyntax-only" "-Wall" "-Wextra")
                   c-mode)
(add-to-list 'flycheck-checkers 'c-gcc-ja)
(flycheck-define-clike-checker c++-g++-ja
                   ("g++" "-fsyntax-only" "-Wall" "-Wextra" "-std=c++11")
                   c++-mode)
(add-to-list 'flycheck-checkers 'c++-g++-ja)

基本的なところにかなりハマってた…

29 Aug 2014, 13:24

他人のコードに INCEPTION する!coursera で The Hardware/Software Interface を受けた

coursera で The Hardware/Software Interface を受けた感想です.

目的

組込みソフトの知識を身につけるため

私はいちおう組込みエンジニアなのだが, 組込みソフトの知識がない.

すごく, そのことに危機感を感じている. 組込みソフトの知識は, 実際に業務で取り組まないと身につける機会が少ない.

しかし, 仕事ではいつまで待っていても新しいプロジェクトには移動できな い.仕事を通して知識を身につけようなんて思っていたら, 10 年経っても身 につかない気がする.

メモリ管理・プロセス管理・アセンブラ言語などなど, このあたりの知識がほしい.

アセンブラ言語の知識を身につけるため

この講座では, アセンブラ言語についても学ぶことができる.

職場でも, アセンブラ言語を利用しているという話はたまにきくので, 学んでいれば, 新しい業務にもつながることを期待.

感想

C 言語のことをなにもボクは知らなかった

一番感じたことは, 自分は C 言語のことについて理解したつもりになってい たが, それはまだまだ不十分だったということだ.

たとえば, この講義では, malloc, free の原理について解説される. そして, malloc, free を自分で実装するような課題が出される.

ヒープ領域, スタック領域がどういう役割していて, それぞれどういうようにプログラムでは利用されているか, 自分は理解していなかった. それなのに, C 言語なんて全部わかったよ! なんて思っていた自分が恥ずかしい.

まるでそれはインセプション!

課題がどれも難しく, 毎週 10 時間以上かかった. しかし, 今まで受けてきた MOOC の課題の中ではもっともおもしろかった.

そのなかでもとくにおもしろかったのは, バッファオーバーフローについての課題.

与えられたプログラムのセキュリティホールに対して バッファオーバーフローアタックを仕掛けて, まったく関係ない関数を実行したり, さらにはセキュリティホールから自分で書いたアセンブラコードを注入し て実行させたりする.

それはまるで, 映画”インセプション” のような興奮だ!

映画では, ディカプリオが他人の夢の中に侵入して,思い通りの記憶を埋め込む. そして私は, 他人のプログラムのなかに侵入して, 思い通りのコードを埋め込む.

ハッカーはこの快感をもとめて悪さをするのだろう.

内容

シラバスからそのまま引用.

Topics:
    Number representation
    Assembly language
    Basics of C
    Memory management
    Operating-system process model
    High-level machine architecture
    Memory hierarchy
    Implementation of high-level languages

Number representation

ビット演算について学ぶ.

まず, 驚いたことは, if や while のような制御文は ビット演算でかけてしまうということだ.

C 言語なんて楽勝でしょと思っていたら, しょっぱなから出鼻を折られるという..

また, コンピュータは 0 と 1 の世界で, プログラミング言語はそれを置き換 えたものに過ぎないという, 基本的なことを気づかされる.

Assembly language

x86-64 アセンブリ言語の文法を学ぶ. 意外にネットや書籍での情報が多く, 参考になった.

昔のテレビゲームは, アセンブラ言語でかかれていたときく. こんな世界でガリガリコーディングをするなんて, すごいな.

Memory management

メモリがどのように利用されているかのお話.

プログラムがどうやって動いているのかをアセンブラレベルで理解して, 今までなにもわかっていなかったんだと自覚. とともに, 仕組みが分かって感動.

2^n-1
|---------------------|
| Stacks              | ローカル変数, プロシージャの内容
|                     |
| Dynamic Data (Heap) | new や malloc で獲得できる領域
| Static Data         | グローバル変数など.
| Literals            | 文字列
| Instructions        | プログラム. 関数
|---------------------|
0

Memory hierarchy

キャッシュアーキテクチャとその制御アルゴリズム, 仮想メモリについて. C 言語通じて, コンピュータアーキテクチャも学べる.

| registers          |             |
| L1 Cache           | SRAM        |
| L2 Cache           | SRAM        |
| Memory             | DRAM        |
| local 2nd storage  | local disks |
| remote 2nd storage | Web Servers |

私は, ストレージ屋だ. (そしてもうやめたい) キャッシュ技術を学ぶと, ストレージを支える技術というものは, かなりの部分がキャッシュが関わっているのだと思った.

  • Disk の性能をあげるためには?
  • ホスト I/O の性能をあげるためには?

とりあえず, 特許でこまったらキャッシュを思い出す. 講義でも, CS の世界での問題解決の常套手段が関節参照だ! と力説してた.

これから

今までセキュアコーディングなんてまったく意識したことがなかった. 無知のまま脆弱性をプログラムに仕込んでしまうことは恐ろしいと思った. もうすこし, セキュアコーディングについて学んでおこうと思った.

アセンブリ言語はこれ以上は深堀りしなくていいかな… なんとなくだけれども, プログラムの仕組みが理解できたし, あまりおもしろいものではないので.

18 Feb 2014, 13:28

スレッドとタスクの違いについてしらべてみた(C++/Linux)

今日、タスクとスレッドの違いについて質問された。

うまく説明できなかった。

人間失格。

ということで、ここで反省しようと思う。

タスクとスレッドの定義について

Wikipediaから引用する。

スレッド

<div class="outline-text-4" id="text-1-0-1">
  <blockquote>
    <p>
      スレッド(thread)とは、CPU利用の単位。<br /> プロセスに比べて、プログラムを実行するときのコンテキスト情報が最小で済むので切り替えが早くなる。<br /> スレッドは、thread of execution(実行の脈絡)という言葉を省略したものである。
    </p>
  </blockquote>

  <blockquote>
    <p>
      ある処理を単一のスレッドのみを用いて動作させる環境もしくは手法をシングルスレッドという。<br /> 対して、複数のスレッドが同時に動作することをマルチスレッドという。<br /> プログラム(概ねプロセス)の開始時にはメインとなるスレッドが動作する。<br /> 必要に応じてその他の処理をするスレッドを作り、実行させる事も出来る。
    </p>
  </blockquote>

  <ul class="org-ul">
    <li>
      <a href="http://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%AC%E3%83%83%E3%83%89_(%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF)">スレッド (コンピュータ) &#8211; Wikipedia</a>
    </li>
  </ul>
</div></p>

タスク

<div class="outline-text-4" id="text-1-0-2">
  <blockquote>
    <p>
      1つのタスクは、1つ以上のプロセスから構成され、1つのプロセスは、1つ以上のスレッドから構成される。
    </p>

    <p>
      プロセスと同義。スレッド (コンピュータ)と同義。タスク並列性などの用語では両者を区別しない場合もある。
    </p>
  </blockquote>

  <ul class="org-ul">
    <li>
      <a href="http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%AB%E3%83%81%E3%82%BF%E3%82%B9%E3%82%AF">マルチタスク &#8211; Wikipedia</a>
    </li>
  </ul>

  <blockquote>
    <p>
      OSから見た処理の実行単位。<br /> 通常はスレッドが実行単位となるが、OSによってはプロセス(複数のスレッドを含むプログラム全体)を1つの実行単位としてみる場合もある。<br /> 一つのアプリケーションソフトが行っている作業全体を一つのタスクと扱う場合が多く、この場合は「プロセス」に近い意味合いになる。
    </p>
  </blockquote>

  <ul class="org-ul">
    <li>
      <a href="http://e-words.jp/w/E382BFE382B9E382AF.html">タスクとは 【 task 】 &#8211; 意味/解説/説明/定義 : IT用語辞典</a>
    </li>
  </ul>
</div></p>

調査結果

<div class="outline-text-3" id="text-1-1">
  <p>
    わからん。
  </p></p>
</div></p>

C++からアプローチ

C++11では、threadライブラリがあるので、使ってみる。

 g++ thread.cpp  -pthread -std=c++11 -Wl,--no-as-needed

実装結果

<div class="outline-text-3" id="text-2-1">
  <p>
    わからん。
  </p></p>
</div></p>

タイマをつかって比べてみる

タイマをつかってみた。

スレッドライブラリをつかったマルチスレッドプログラムは5秒かかる。

スレッドライブラリをつかってないシングルスレッドプログラムは15秒かかる。

実装結果

<div class="outline-text-3" id="text-3-1">
  <p>
    ちょっとわかった。
  </p></p>
</div></p>

まとめ

C++/Linux環境だと、コンパイルした a.outを実行したものがタスク(プロセス?)

% ./a.out &
% ps
  PID TTY          TIME CMD
11484 pts/5    00:00:00 a.out

ひとつのプログラムのなかに複数のスレッドが動ける。

これはシングルスレッドかつシングルタスク。


int main()
{
  std::cout << "hello thread" << std::endl;
  return 0;
}

これはマルチスレッドかつシングルタスク。


int main()
{
  thread th(  std::cout << "hello thread" << std::endl; );
  thread th2(  std::cout << "hello thread" << std::endl; );
  th.join();
  th2.join();
  return 0;
}

これはマルチタスク。


 % ./a.out &
 % ./a.out &
 % ps
  PID TTY          TIME CMD
 8668 pts/5    00:00:00 a.out
 8874 pts/5    00:00:00 a.out

結論

<div class="outline-text-3" id="text-4-1">
  <p>
    結局、わからん。
  </p></p>
</div></p>

07 Dec 2013, 07:45

[Coursera]C++ For C Programmersを受講しました

Cプログラマなので、C++を勉強するために『C++ For C Programmers』を受講しました。

概要

C++の初級的な話題が紹介される。この講義でC++の基礎がマスターできる内容。Cプログラマを対象にしているため、Cとの比較やC++のここがスゴイのだという説明も出てきて、Cしかしらない自分にはこのCについての伏線が嬉しい。

また、なにかにつけてC++11の話題がガッツリ紹介されるので、C++11 For C++98 Programmersというタイトルのほうが実は適切な気がする。

オープニングにJAZZが流れて、ダンディさあふれるのIra Pohl教授が現れる。

[//www.youtube.com/embed/tph2O4qPNMg?rel=0]

話し方がカメみたいにものすごくゆっくりなので、English的な壁は大丈夫だった。スライドにカラーペンで書き込みながら説明されるので、臨場感がある。(しかし字がけっこうきたない)

参考書

参考書は、ネット上にある無料のものと、有料のものがある。

  • C++ by Dissection
  • C++ For C Programmers


が、自分は利用しなかった。どちらかというと、副読本としては、かつて挫折した独習C++を読んでた。

各回の概要

Week1 C++ as a Better C

A言語からC言語までに至る歴史の説明。そして、C++がC言語に比べてなぜ優れているかを解説する。課題は、C言語でかかれたコードをC++に書きなおす。ここでC++独特の表記をならう。

week2 C++: Basics of Generics and Classes Template

templateが出てくる。より汎用的で、再利用可能な書き方について学ぶ。課題はダイクストラ法の実装。どのへんがC Programmerのためなのだ? モンテカルロ法やPriorityQueueを使いこなす必要があり、難しい。

week3 C++: Class Constructors and Destructors

コンストラクタ、デコンストラクタの説明。または、List構造の説明。Assignmentの実装方法に関するフォローの講義も入る。

week4: C++: Minimum Spanning Tree & Standard Template Library

auto,継承、friend関数などなど。ここで、STLの解説とイテレータという概念が出てくる。だんだんC++ぽくなってくる。Assignmentは最小スパニングツリーをプリム法かクラスカル法で実装。

week5: C++ 11 Standard; Containers, Iterators and Algorithms

主にここではSTLの説明。コンテナ、イテレータ、アルゴリズムの三本柱が詳しく解説される。lambdaの使い方も紹介されるが、理解できなかった。

week6: Hex, the game and C++ Inheritance

後半の大きな話題である、Hex gameの説明が入る。また、重要な概念である、もここで解説。

Module 7: Min-Max and C++11 Classes; Alpha-beta and Polish

Copy Constactor や Move Costractorなど。またHex Gameを実装するための方法が解説される。ミニマックス法やアルファ・ベータ法など。ここで、このCourseのサムネイル画像がチェスの理由を理解した。この先生はチェスがとても好きらしい。チェスにおけるAIの実装方法なども出てくる。

後半の課題である、Hex Gameを 3weekにわたって実装する。この課題で、C++のfeatureを全部注ぎ込みなさいと言われて、けっこう頑張った。

Module 8: Monte Carlo Evaluation; the C++11 Standard

例外処理、スレッド処理などなど、今までで解説していないC++のfeatureももれなく紹介。また、C++中級への道として、簡単なデザインパターンが紹介される。

おわりに

For C Programmerな部分は実はweek1だけだった気がした。グラフ理論やゲーム理論が出てきて、『いったいどのへんがFor C Programmerナンダヨ!』と全生徒が唸ったに違いない。

Cしかできない自分にとっては、まさにうってつけの授業だった。

Hex Game

[//www.youtube.com/embed/kNOFq7aEYUE?rel=0]

20 Nov 2013, 14:47

C++でのSTLアルゴリズムの使い方まとめ(sort)

C++ STLの algorithmで便利そうなものをメモしてきます.

並べ替え・ソート(sort)

  • 並べ替えを実施します。
  • vectorなどのランダムアクセス可能なコンテナで利用可能。
  • ロジックはクイックソートを利用している。

使い方

sortの引数として、並べ替えたい初めと終わりのイテレータを渡す。たいていは begin(),end().

sort(a.begin(), a.end());

デフォルトでは小さい順(less())に並べ替えられる。大きい順に並べ替える時は、以下のようにgreater<>()を引数として渡す。

sort(a.begin(), a.end(), greater<int>());

#include <algorithm>
#include<vector>
#include<iostream>

using namespace std;

int main()
{
  vector<int> a;
  a.push_back(3);
  a.push_back(1);
  a.push_back(2);

  sort(a.begin(), a.end());
  for( auto x : a ) cout << x;
  cout << endl;

  sort(a.begin(), a.end(), greater<int>());
  for( auto x : a ) cout << x;
  cout << endl;
}

実行結果

$ g++ -std=c++11 sort.cpp
$ ./a
123
321

10 Nov 2013, 00:34

UnionFindアルゴリズムを実装してみた

UnionFindをC++で実装した。

UnionFindとは、2つの異なる集合がつながっているかを調べるアルゴリズム。詳しくは以下。

Implement

以下のJavaでかかれた実装をC++版に書き直してみた。木構造にデータを保持する場合と、そう強いない場合の2つを実装。

04 Nov 2013, 14:46

C++ での優先順位付きキューの使い方まとめ (PriorityQueue)

はじめに

優先順位付きキューのを PriorityQueue という.

キューの中で最大 (最小) のものを抜き出す場合などに利用する.

使い方

宣言

<div class="outline-text-3" id="text-unnumbered-3">
  <p>
    デフォルトでは大きい順で pop されるので, 最小のものを pop で取り出すには, greater を宣言時に追記する.
  </p>

  <p>
    [sourcecode language=&#8221;cpp&#8221; title=&#8221;&#8221;]<br /> #include <queue><br /> using namespace std;
  </p>

  <p>
    priority_queue <int> maxpq; // default 大きい順<br /> priority_queue<int, vector<int>, greater<int> > minpq; // 小さい順<br /> [/sourcecode]
  </p>
</div>

関数

<div class="outline-text-3" id="text-unnumbered-4">
</div>

<div id="outline-container-unnumbered-5" class="outline-4">
  <h4 id="unnumbered-5">
    要素を追加する (push)
  </h4>

  <div class="outline-text-4" id="text-unnumbered-5">
    [sourcecode language=&#8221;cpp&#8221; title=&#8221;&#8221;]<br /> pq.push (1);<br /> [/sourcecode]
  </div>
</div>

<div id="outline-container-unnumbered-6" class="outline-4">
  <h4 id="unnumbered-6">
    先頭の要素を取り出す
  </h4>

  <div class="outline-text-4" id="text-unnumbered-6">
    <p>
      最大 (または最小) の先頭を取り出します.
    </p>

    <p>
      [sourcecode language=&#8221;cpp&#8221; title=&#8221;&#8221;]<br /> pq.pop ();<br /> [/sourcecode]
    </p>
  </div>
</div>

<div id="outline-container-unnumbered-7" class="outline-4">
  <h4 id="unnumbered-7">
    要素を調べる
  </h4>

  <div class="outline-text-4" id="text-unnumbered-7">
    [sourcecode language=&#8221;cpp&#8221; title=&#8221;&#8221;]<br /> // キューがからかどうかを調べる<br /> pq.empty ()</p> 

    <p>
      // 要素数をしらべる<br /> pq.size ();
    </p>

    <p>
      // 次に取り出される要素を調べる<br /> pq.top ();<br /> [/sourcecode]
    </p>
  </div>
</div>

Sample

昇順に取り出す

<div class="outline-text-3" id="text-unnumbered-9">
  [sourcecode language=&#8221;cpp&#8221; title=&#8221;&#8221;]<br /> #include <queue><br /> #include <iostream><br /> using namespace std;</p> 

  <p>
    int main ()<br /> {<br /> priority_queue<int> pq;
  </p>

  <p>
    pq.push ( 2 );<br /> pq.push ( 1 );<br /> pq.push ( 3 );
  </p>

  <p>
    cout << pq.top () << endl;<br /> pq.pop ();<br /> cout << pq.top () << endl;<br /> pq.pop ();<br /> cout << pq.top () << endl;<br /> pq.pop ();
  </p>

  <p>
    return 0;<br /> }<br /> [/sourcecode]
  </p>
</div>

<div id="outline-container-unnumbered-10" class="outline-4">
  <h4 id="unnumbered-10">
    実行結果
  </h4>

  <div class="outline-text-4" id="text-unnumbered-10">
    [sourcecode language=&#8221;language&#8221; title=&#8221;&#8221;]<br /> 3<br /> 2<br /> 1<br /> [/sourcecode]
  </div>
</div>

降順に取り出す

<div class="outline-text-3" id="text-unnumbered-11">
  [sourcecode language=&#8221;cpp&#8221; title=&#8221;&#8221;]<br /> #include <queue><br /> #include <iostream><br /> using namespace std;</p> 

  <p>
    int main ()<br /> {<br /> priority_queue<int, vector<int>, greater<int> > pq;
  </p>

  <p>
    pq.push ( 2 );<br /> pq.push ( 1 );<br /> pq.push ( 3 );
  </p>

  <p>
    cout << pq.top () << endl;<br /> pq.pop ();<br /> cout << pq.top () << endl;<br /> pq.pop ();<br /> cout << pq.top () << endl;<br /> pq.pop ();
  </p>

  <p>
    return 0;<br /> }<br /> [/sourcecode]
  </p>
</div>

<div id="outline-container-unnumbered-12" class="outline-4">
  <h4 id="unnumbered-12">
    実行結果
  </h4>

  <div class="outline-text-4" id="text-unnumbered-12">
    [sourcecode language=&#8221;language&#8221; title=&#8221;&#8221;]<br /> 1<br /> 2<br /> 3<br /> [/sourcecode]
  </div>
</div>

おまけ

ダイクストラ法の実装をする際に, C++ の STL があるとは知らずに, 自前で最小優先キューを実装しました. STL を利用すればよかった.

この Java Sourse を参考に C++ に書きなおした.

MinPQ: