giantneco’s blog

技術メモ

AtCoder Beginner Contest 121

プログラミングコンテスト

久しぶりにプログラミングコンテストやってみたが、ビギナーで 1000 点中 300 点しかとれなかった。雑魚い。

反省点:

  • C++ の API 調べながらでは当然遅い
  • 難しく考えすぎ
    • 必要のない最適化をやろうとしてしまっている
    • 全体のソートは遅いだろうなと思ってたが、他の参加者のコードを見ると全然間に合うようだった

前者については解答方法はわかっていながら全然手が追いついてない状態なので、 C++ でのプログラミングコンテストに慣れれば少しはマシになるはず。

後者は経験の他、柔軟さが足りてない感じがする。

とりあえず他の参加者のコードを読んで見るところから練習し直しする。

C++ Mix #2

勉強会メモ C++

cppmix.connpass.com

C++ Mix の第2回に参加してきたメモ。

iOS パズル「パズモナ」の秘密, @5mingame2

C++ でゲーム作った話。 フレームワークとして CINDER というものを採用してる。 また方針として new と delete は使わず、 包含やスマートポインタでどうにかしている。 また UI は boost::any を使用して書きやすくしている。 UI 周りは詳しくないが、や利用あるもんなんだろうか？

Qt x Reactive Extensions, @tetsurom

Reactive Extensions と Qt の話。

Rx の説明として「values-distributed-in-time」というのは初めて聞いた。 あとオブザーバパターン、イテレータパターン、関数型プログラミングのいいとこ取りというのも。

C++ でも RxCpp があるのは意外だったが、run loop は自分で仕込む必要があるらしい。 あと Qt と RxCpp をつなぐライブラリを作ったとのこと。うまく Qt の難しい部分を解決できているらしい。

C++のパッケージマネージャ「poac」を開発した話　@matken11235

poac は C++ 向けのパッケージマネージャ。 以前に聞いたときは「開発している」話だったので、結構進歩あったっぽい。 この発表を見てインストールしてみたがなかなか使えそうな感じ。

公式のドキュメント(https://docs.poac.io/ja/)を見ながら実行するとこんな感じになる。 これから対応パッケージが増えることに期待。

% poac new hello

Your "hello" project was created successfully.


Go into your project by running:
    $ cd hello

Start your project with:
    $ poac run

% cd hello
% poac install hello_world
==> Resolving packages...
==> Resolving dependencies...
==> Fetching...

  ●  hello_world 0.1.0 (from: poac)

==> Done.
% vim main.cpp 
% poac run
==> hello
Compiled: Output to `_build/bin/hello`
Running: `_build/bin/hello`
Hello, world!

雑談タイム

なんというかここが本番だった気がする。

基礎勉強会#6 アルゴリズム

勉強会資料

slides.com

社内で行った基礎勉強会の第 6 回。アルゴリズムの話。

アルゴリズムの話といいつつ、メインは競技プログラミングの話をしている。

アルゴリズムを勉強するご利益についても書いてみたが、これはちょっと強引だった気がする。 仕事によっては非常によく考えるし使いもするが、 アルゴリズムをまったく考えないで済むような作業があるのも確かなので、一般的にあてはまるとは言いづらい。

基礎的なアルゴリズムとしてはソートとグラフアルゴリズムから２，３個紹介するにとどめている。 ココらへんはもう実装はたくさんあるはずだし。

アルゴリズムの設計手法も競技プログラミングでよく使われるものを紹介した。 競技プログラミングについては、これのおかげでプログラミングの腕をあげた気がしているので、初心者ほどやってみるといいと思っている。

競技プログラミングサイトとしては TopCoder の他、AtCoder と AOJ を紹介した。日本語対応しているし。 過去問を解いているところを実演しようとしたが、焦ってコンパイルが通らず残念な結果に。 まあ雰囲気はわかってもらったはず。

基礎勉強会としてはとりあえずこれで終わりにするつもり。 資料作るのにかなり時間を使ってしまって、あまり自分の勉強ができていないのは良くない。 最初は他の人にも発表してもらうつもりだったが、人があつまらないんじゃなあ。 とまれ最後まで参加してくれた人には感謝したい。

基礎勉強会#5 データ構造

勉強会資料

slides.com

社内で行った基礎勉強会の第 5 回。データ構造の話。

基礎的なデータ構造としてリスト、ハッシュテーブル、ツリーを取り上げた。 データ構造の比較のために計算量の話が必要になるので、計算量も合わせて取り上げている。

資料作成に当たってはみんなのデータ構造を非常に参考にしている。良い本なので買って読もう。

次回はアルゴリズムの話。ちょっと競技プログラミングの話も合わせてしたいと思っている。

基礎勉強会#4 低レイヤの開発ツール

勉強会資料

slides.com

社内で行った基礎勉強会の第 4 回。低レイヤでの開発ツールの話。

gdb や valgrind などの低レイヤ、というか C/C++ での開発で使いそうなツールの話。半分以上 は gdb。 参加者が現在進行形で C を書いているというのでテーマに取り上げた。

gdb は調べてみると結構知らないことがあって驚いた。 C-x C-a で TUI にできたり、reverse-next できたり、Go や Rust にも対応していたり。 おまけに reverse-next とかの機能はもう 10 年くらい前にはもうあったらしい。gdb のうちではマイナーなコマンドかもしれないが、もうちょっと先に知っておきたかった。

発表としてはほぼツールを実際に使ってみてみせるだけなので、資料としてはかなり薄め。内容がない。 デモのためのコードも書いてみたが、gdb の watch コマンドの実演がいまいちうまくいかなかった。デモの練習が足りてない。

次回はデータ構造の話。ようやく基礎らしい話ができる。

Go Conference 2018 Autumn メモ

golang 参加報告

少し前の話になるが Go Conference 2018 autumn に参加した。 Go Conference 2018 autumn は 2018/11/25 に行われた Go 言語のイベントで、六本木の Google オフィスで行われた。

自分と Go との関わりだが、今現在のプロジェクトでは Go を使っているもののどうも妙な使い方をしている。 なので他のところでの話は機会があれば聞いておきたかった。

自分が聞いた範囲では GAE とマイクロサービスでの話が多かった。 やはりクラウド上でマイクロサービスを使う場合には、Go が有利なんじゃかないかと思う。

その他にも低レイヤよりの話や、パフォーマンスチューニング、導入事例など色々な話が聞けてよかった。

以下メモ。

キーノート by Steven Buss

キーノートは GAE/Go の 歴史的な変遷と最新の GAE の話。

以前は NaCl= Google Native Client で動いており、 ptrace を使ってシステムコールの呼び出しを検知しハンドリングすることで環境を独立させていた。 新しい世代の App Engine では gVisor を使っているのでそれらの必要がなくなった。

gVisor は Go で書かれた ユーザ空間カーネルで、 アプリケーションのシステムコールなどをハンドリングして環境を隔離し、セキュアにできる。

gVisor:

gVisor の構成:

2 つのプロセス間は 9P (Plan 9 Filesystem Protocol) で繋がれている。

将来的には Google のクラウドはすべて Go で作られる。

  • gVisor
  • Second-gen pp Engine runtimes
  • Cloud functions
  • k8s
  • knative
  • etc, etc

Mirroservices 実装ガイド in Go at Mercari by @_yagi5

メルカリでのマイクロサービスの話。

  • サービスの追加手順
  • サービス間通信
  • サービスのテンプレート
    • エコーサーバ
  • ミドルウェア
    • grpc-echosystem/go_grpc_middleware の ServerChain の仕組みを使用
  • ロギング(トレーシング)
    • opencensus と zap(zapgrpc) を利用
  • マイクロサービスでの Go のいいところ
    • ネットワーク/ミドルウェアレイヤとの相性がいい
    • 静的解析ツールで書き方を強制できる

OpenCensus による APM の実現と未来 by @munisystem

APM = Application Performance Management の話。

  • APM
    • APM = 「Service Level を維持するため app のパフォーマンスの継続的な監視をすること」
  • 実現に必要
    • performance の取得
    • data の可視化、活用できる基盤の構築
      • Tracing: サービス・サーバをまたいだイベントの追跡
      • Metrics: なにが原因で悪くなったか調べるのに必要
      • Logging: ログ
      • Error reporting: エラーの調査

Go での APM 実現例として:

  • Tracing: Stackdriver Trace /Datadog APM /Zipkin ?jaeger
  • Metrics: Stackdriver Monitoring / Dtadog /Prometheus
  • Loggin: zap / glog + fluentd
  • Error repoirting: Hobeybadger /Sentry

だが上記のライブラリではクライアントライブラリと基盤が密になってしまっている。 APM 基盤はサービス、組織の規模で変更を楽にしたい。

OpenCensus * OSS 版 Census * APM のデータを収集→外部サービスに提供 * アプローチ *コレクターとエクスポーターの分離 * コレクター データの収集 * エクスポーター 変換と送信 * Cloud provider は expoorter だけ実装する * App はデータを収集するところだけ実装する * 欠点 * バックエンド固有の最適化のためのメタデータの付与が行えない←結合度が下がったため

Profiling Go Application by @orisano

Go アプリケーションの性能を改善した話。

  • 画像変換サーバが OOM killer に殺された
    • 調査 　* pprof, GODEBUG=allocfreetrace=1
      • GC で参照グラフをダンプしてみた
    • 問題点
      • 同時変換数に制限がつけられてなかった
  • disintegration/imaging が 遅い
    • boundary check elimination
      • 添字チェック→安全だと判断できればコンパイラ側が削除してくれる

  • kubelet でCPU負荷が高い

    • 調査
      • kubelet は pprof を imporot しているので pprof を使う
    • 問題点
      • String.Replacer が大量にあった
    • 対策
      • Write がたくさんある部分を１ Write にまとめることができる
      • Readdir 遅い, -> goreaddir に入れ替え

  • まとめ

    • 普段使っているものでもカリカリにチューニングされているわけではない
    • 遅いと思ったら自分で改善してみる
    • 対策するには
      • Benchmark を書く: bnechcmp or chenccomp
    • Go はパフォーマンスチューニングしやすい
      • ツール充実している

Biscuit Code Reading by @shibu_jp

Biscuit Code Reading - Google スライド

@shibu_jp さんは「Goならわかるシステムプログラミング」の著者の方で、 Biscuit をネタに主にブートシーケンスに関する低レイヤの話をしていただけた。

  • Biscuit は 並列・分散の研究ためのOS で Go で書かれている

    • 論文
    • Features
      • multicore
      • journaled FS with concurrent, deferred and group commit
    • 中身
      • ほぼ Go のところがある
      • Biscuit のみの部分は buicuit/ 下に置いてある
    • Kernel Space
      • Bisucut / Go library / Shim
      • shim -> systell call 置き換え
    • Executable File Format は ELF

  • まとめ

    • Go はコンピュータシステムを学ぶのによい教材
    • Go 言語のランタイムは低レイヤから上まで Go で書かれている
    • Goならわかるシステムプログラミングを読もう

基礎勉強会#3 並行・並列処理の基礎

勉強会資料 並行プログラミング

slides.com

社内で行った基礎勉強会の第３回目は並列・並行がテーマ。

なんだがテーマが前回・前々回から飛んだ感じはあるが、リクエストがあったしそのうちやったほうがいいと思ったのでこのテーマで話すことにした。

広く浅くという感じであるが、並列・並行処理に関する基礎知識にはそこそこ触れられたかな？ 個人的にも概念を色々整理できたのはよかった。データ競合と競合状態はちょっとごっちゃに覚えていた気がするのでちゃんと調べてみてよかったと思う。

残念な点として、もうちょっとモダンな並行処理を取り上げたかったのはある。 リアクティブプログラミングとか話をしたかったが、資料が間に合わないのとちょっと自分でも知識が足りてない気がするので残念ながら見送った。 ただ若干反応が薄かったので、聞いていた人のニーズには合ってなかったかもしれない。

参考資料にも書いたが、Java Concurrency in Action は今読んでも結構いい内容になってる。

次回は gdb, valgrind など低レイヤでの各種ツールの話。 基礎なのか？という気はするが、話を聞きに来てくれている人がCを書いている人しかいないので需要は満たしている。