Hatena::ブログ(Diary)

はてなかよっ!

2011-05-06

プログラミング初心者にオススメのD言語本

プログラミング初心者がD言語を学ぶのに適した本を,俺が実際に読んだことのあるものの中から選んでみました.

1冊目

1冊目はなんでもいいと思うのでとりあえず定番としてTDPLを挙げておきます.

The D Programming Language

The D Programming Language

これで基本的なD言語の文法が学べるはずです.この手の入門書は「課題」がつきものですが,これには全くありません.まぁ載ってるコードを書いて試せばいいでしょう.

1冊目読了の時点では,以下のプログラムのCTFEバージョンを実装できるようになっていればいいと思います.余裕があれば実際に実装してみてください.

2冊目

ある程度コードが書けるようになったら次はTDPLがいいでしょう.

The D Programming Language

The D Programming Language

この本はD言語を紹介している本ですが,それ以外にも以下のような特徴があります.

  • Concurrencyに関して,今までどんな風にパラダイムが推移してきたかの説明
  • 今後の仕様となるサンプルコードが豊富

特に並行処理に関しては今後どんなプログラミング言語でもほぼかならず必須となる要素なので,D言語での扱いは早めにマスターしておいたほうがいいでしょう.

しかしながら,すべて読むと時間がかかってしまいます.そこで,最初は以下の章だけ読むことお勧めします.

  • 1章「“D”iving In」
  • 5章「Data and Functions. Functional Style」
  • 13章「Concurrency」

Rangeについてはソースコードも参考になります.特にstd.range/std.algorithm/std.variantあたりは重要性も高いので読んでみてもいいと思います.

上記のトピックを読んだ時点では,作れるプログラムは特に増えないかもしれません.しかし,同じことでも効率よく,あるいは楽に,あるいはデバッグしやすく書けるようになっているはずです.

3冊目

3冊目は『TDPL』か『The D Programming Language』のどちらかを勧めます。

The D Programming Language

The D Programming Language

or

The D Programming Language

The D Programming Language

TDPLはD言語という言語を網羅的に説明してありますが,具体例にやや乏しいのが欠点です.The D Programming Languageは仕様例を大量に集めたものですが,Phobosなどの実コードの解説はあまりありません.この2冊(というか1冊)をKindleで買うとあまりの手軽さにドン引きすること間違いないため,最初は紙で読むことをお勧めします.どちらがいいか迷ったときは両方買えばいいと思います.

TDPLを読破した時点で,D言語の学習は終了したと考えていいでしょう.

その後の展開

その後はプログラミング作法やアルゴリズム,あるいはNoSQLやDMDScriptなどの関連した他の言語について学ぶことになるでしょう.その際,D言語と外の世界との間を埋めるものとしてはTDPLは適していないと思います.

The D Programming Language

The D Programming Language

この本を「間を埋めないもの」として紹介したのは,ここまで来るとソースを読んだ方が手っ取り早いからです.

Phobosは標準ライブラリであるため,Rangeやtemplateを使ったコードがふんだんに使われています.D言語で他のプログラマコミュニケーションをするには,D言語を使うのが一番効率が良いです.従って,Andrei先生のコードは非常に読みにくいと評判ですが,他の俺やSeanやDavidなどが書いたコードは読みやすいため,Phobos / druntime / その他公開されているD言語向けのライブラリを読んでおくのは重要です.

データベースはこれひとつで何冊も本が出るほどの大きなトピックです.しかし,D言語からデータベースにアクセスする方法については今現在ほとんどないため,GSoC 2011の成果次第です.俺が突っ込みを入れたのですがSQL専用になりそうなので,他のデータベース群にはそれなりのモジュールを設計しないと駄目になりそうです.

テストについての解説は重要です.テストの大きな目的の一つは,開発中に一度潰したバグを再現してしまうといったような「後戻り」を防ぐことです.特にD言語はtrunkの更新が活発なので,その日に書いたコードを無駄にしないためも,テスト手法については早めにマスターしておくべきでしょう.TDPLでD言語における単体テストの書き方を学んだら,Phobosで実際どのように皆が書いてるのか知るのも非常に勉強になります.

さていくつか書籍を紹介しましたが,もちろん書籍以外からも学ぶことは大いにあります.また,学べば学ぶほど世界が広くなってくるので,「これで十分」という段階にはなかなか達しません.しかし「良いtrunkの破壊的変更に喜んで追従するエンジニア」ならば手の届くところにあります.私もまだまだ道半ばですが,共に「良いtrunkの破壊的変更に喜んで追従するエンジニア」を目指しましょう.


参考

オリジナルの記事はこちら プログラミング初心者にオススメのPerl本

2011-04-12

D言語会議 01

http://partake.in/events/feac18f7-0b78-4129-92c5-ad0cce8feafb

やりました!他の人もブログを書かれているので,探せば見つかると思います(時間があったら上のサイトにコメントとしてまとめておきます.

もともと勉強会ではないと明言していたので,まぁ最初に今のD言語の現状をアジェンダ的に話した以外は,その場のノリに任せました.このイベントを企画した当初はGSoCの話はまだ全然だったんだけど,その後決まったGSoCのプランがなんだかんだで今のD言語の弱点に関するものが多かったので,それをベースに話しました.

とりあえず適当なまとめ

  • gdbが上手く動かないのは,DWARFとDでの定義が被っているかららしい(shinhさん調べ).とりあえずてきとうにずらせば解決する様子
  • Leandroが書いてたcdgcがfork()を使っていて,なんでなんかなぁと前疑問に思って放置していた.今回他にソースを読んだ人も「fork()である必要ない」と言っていたので,まぁなんか色々怪しい.
    • Davidのは別に世代別にしているわけじゃなくて,単にデカいのを舐めないようにしているだけ
  • std.concurrencyにreply機能が欲しいという意見が
    • Erlangと同等を目指すのであれば必要そうだけど,Seanはどこまでやる気があるんだろうなぁという
  • etc.c.curlがあるので,ネットワークアクセスそのものは改善される予定
    • サーバとか非同期IOとかは,GSoCの課題
  • Weak Symbolを使ってないらしく,DLLとexeでシンボルが分かれてしまう現象が起きてるらしい
    • リンカの話し書いてるのにおかしいだろ,と誰か突っ込んでた
  • kinabaさんのtoHash / getHash問題は今でもtwitterで盛り上がっている
  • 後なんか例外のthrowのパースエラーに関してもkinabaさんとりりかるろじかるさんとku6さんが追ってた気がする
  • SHOOは「シュー」ではなく「ショー」
  • CTFEチームも出来てて,結局3 - 4グループに分かれていた気がする
  • haraさんのScopedについての比較でC++0xのコード見てたけど,各コンストラクタとか多過ぎてあばば
  • D言語の仕様としてはrelocatableなのと相まってCopy GCでおかしくなるようなことはない仕様になっている
    • 実装は別なので,誰かとりあえず実装してみると改善がすすむやも?という感じか
  • イベントとかデリゲートとかにスタックトレース的なもの(誰が作ったか)が欲しいという話
    • こういうのってTLSとか上手く使ってなんとかならないだろうのか
  • そういえばユーザ定義アノテーションどうなったの? -> 誰も分からない
  • RangeってBlocking前提なのに非同期とかどうすんべ?Andrei先生の妄想爆発疑惑
  • UUIDをPhobos向けに書こうとしたけど,よくよく考えると俺が使う予定ないし,randomまで書いてオワタ

後なんか思い出したら追記する.まぁこんなてきとうな会で良ければまた開いてみたい.2次会, 3次会まであったものの全員とは話せなかったので,次回はもうちょい手広くやりたい.

正直こんなに人が集まるとは思ってなかったですよ!

2011-03-21

DMD as a Library

ddmdって正直いらないんじゃないかと思ってたけど,インタラクティブ環境をD言語で提供したいと思ったらこれしかないんじゃないかと思えてきた.D言語にevalを入れるのはかなり厳しいし,GSoCでパーサ&レキサの案が出てるけどライブラリとしてどこまで提供するのか分からん.

dmdC++なのでこれからAPIを提供されても困るけど,ddmdならコンテキストを持たせればなんとかなるかもしれない気がしている.勿論色々足りない機能とかあるんだけど,CTFEな部分をもう少し抽象化して強化出来ればAPI経由で操作出来る可能性が!

ということで,当分先になるけど色々考えて置く.

2011-01-10

Scalable memory allocation using jemallocの備忘録的和訳

Scalable memory allocation using jemalloc

jemallocは今使ったりしてるし,今後ソース読む可能性もあるので,適当に(精度とかは期待しないように!).気になる人は元記事を読みましょう.

Scalable memory allocation using jemalloc

Facebookは,8コア+CPUと8GiB RAMな専用マシンの上で走っている,様々な種類のサーバアプリケーションの集合で構成されています.これらのアプリケーションは,CPUとRAMと最大限使う事によって最高のスループットを目標に,並行処理のため大体POSIXスレッドを使っています.この環境は,メモリアロケーションのための重大なチャレンジをもたらします.具体的に言えば,

  • 確保と解放は速くなければいけません.理想的に,メモリアロケーションアプリケーションの定常状態においてはほとんど必要になりませんが,これは動的な入力を基本とするデータ構造においては現実からはほど遠くなります.まぁまぁなアロケータの改善でさえ,スループットに多大な影響を及ぼすことが出来ます.
  • 実際のメモリとRAMの使用量の関係は一貫していなければなりません.言い換えれば,アロケータによって引き起こされたフラグメンテーションによる実質的な限界はクリティカルなものとなります.もしフラグメンテーションが一日毎に1GiBのRAM使用量の増加を引き起こすのであれば,少しだけ余地を残すように設計されたアプリケーションは,数日の内に失敗するでしょう.
  • メモリヒーププロファイリングクリティカルな操作の補助となります.もし全てがプラン通りに行くのであれば,リークの検出と削除は開発のタスクとなります.しかしその場合でも動的な入力は,生産負荷の下での動作の解析によって特徴付けることが可能な,思いがけないメモリ使用のスパイクを引き起こすことが出来ます.

2009年,存在しているメモリアロケータはこれら3つの要件のうちたいてい2つは満たしていました,なので私たちはjemallocにヒーププロファイリングと多くの最適化を加えました,その結果jemallocは今3つ全てを満たしています.このポストの残りは,多数のFacebookのための改善を扱う前のjemallocのコアアルゴリズムとデータ構造のサーベイで,続いてWebサーバの負荷の下で6つのメモリアロケータを比較した実世界でのベンチマークがあります.

NOTE:Tech Talkの宣伝なので省く

コアアルゴリズムとデータ構造

CとC++は,malloc(),posix_memalign(),calloc(),realloc(),そしてfree()の5つの関数をメインに構成されるとても基本的な型付けのないアロケータAPIに依存しています.多くのmalloc実装もまた,malloc_usable_size()のような基本的な機能を提供しています.APIがシンプルな一方,高い並行でのスループットフラグメンテーションの回避は無視出来ない内部の複雑さを要求します.jemallocはいくつかのオリジナルなアイディアと他のアロケータで最も有効なアイディアを組み合わせます.以下のアイディアとアロケーションの指針が絡見合い結合することで,jemallocとなっています.

OSカーネルはページ(大抵一ページ4KiB)を単位として仮想メモリを管理します,なので全てのデータを可能であればいくつかのページへと集めることは重要なことです.phkmallocは,アプリケーションが定期的にHDへとアクティブなページをスワップアウトする問題に取り組む時に,このテネットを有効にしました(全体でスワップするのを回避するという問題が現在でも重要なものとして残っていますが).

  • ロック競合を最小にします

jemallocの独立したアリーナはlkmallocにインスパイアされていますが,時間が経つと,tcmallocは完全な同期を避けることがよりよいことだととてもクリアーにしました,なのでjemallocはまたスレッド特有のキャッシングを実装しています.

  • もし汎用な目的でないなら,十分ではない

jemallocが最初FreeBSDへと併合したとき,それはいくつかのアプリケーションでの深刻なフラグメンテーションを持っていました.そして提案はOS内に複数のアロケータを含ませるために出されました.この考えは,開発者がアプリケーションの特性に基づいた知識のある選択をする公的な権限を与えるというものでした.正しいソリューションはパフォーマンスと予測を改善するため,劇的にシンプルなjemallocのレイアウトアルゴリズムでした.この1年で,この哲学はjemallocにおいて多数の大きなパフォーマンスの改善のモチベーションになりました,そしてこれは欠点が発見され続ける限り開発のガイドとなるでしょう.

jemallocは以下のような3つの大きなサイズクラスカテゴリを持っています(64bitシステムを想定しています).

  • Small: [8], [16, 32, 48, ..., 128], [192, 256, 320, ..., 512], [768, 1024, 1280, ..., 3840]
  • Large: [4 KiB, 8 KiB, 12 KiB, ..., 4072 KiB]
  • Huge: [4 MiB, 8 MiB, 12 MiB, ...]

仮想メモリは論理的に2^k(デフォルトで4MiB)サイズのチャンクへとパーティショニングされています.その結果,ポインタ操作経由で定数時間でsmall / largeオブジェクト(内部ポインタ)のためのアロケータのメタデータを見つけることが可能です,そしてグローバルな赤黒木を経由して対数時間でhugeオブジェクト(チャンクでアラインメントされた)のためのメタデータを探索します.

アプリケーションスレッドは最初にsmall / largeオブジェクトをアロケートした上にラウンドロビンなやり方でアリーナへと割り当てられます.アリーナは完全にそれぞれに独立しています.これらは自身のチャンクを管理し,small / largeオブジェクトのためにページを切り分けます.どのスレッドが解放を実行するかに関わらず,フリーなメモリはいつも自分が確保されたアリーナへと返されます.

http://sphotos.ak.fbcdn.net/hphotos-ak-snc6/hs057.snc6/168744_490348332199_9445547199_5849906_5569868_n.jpg

各アリーナのチャンクはメタデータ(主にページマップ)を含んでいます,続いて一つ以上のページがあります.smallオブジェクトは,各ページの先頭に追加されたメタデータと共に一緒にグルーピングされ,largeオブジェクトは互いに独立していて,これらのメタデータは全てアリーナのチャンクヘッダに存在しています.各アリーナは赤黒木(各サイズクラス毎に一つ)を経由することでsmallオブジェクトのページを追跡します,そしていつもそのサイズクラスのためのlowestなアドレスとページを用いてアロケーション要求に対して情報を提供します.各アリーナは二つの赤黒木を使って利用可能なページを追跡します(一つは綺麗で未使用なページ,もう一つは既に使われたことのあるダーティなページ).ページは優先的に,ダーティツリーからlowestでベストフィットするところからアロケートされます.

http://sphotos.ak.fbcdn.net/hphotos-ak-snc6/hs062.snc6/167209_490348547199_9445547199_5849910_7377432_n.jpg

スレッドはsmallオブジェクトキャッシュを管理するのと同様に,largeオブジェクトを制限サイズ(デフォルトで32KiB)までキャッシュを管理します.それゆえに,アロケーション要求の大部分はアリーナにアクセスする前に,キャッシュされた利用可能なオブジェクトがあるかをまずチェックします.スレッドキャッシュ経由のアロケーションはアリーナの貯蔵庫(smallサイズクラスのための一つ)をロックする必要があります,そして/またはアリーナ全体として.

スレッドキャッシュのメインの目的は同期イベントの削減です.しかしながら,各サイズクラスのためにキャッシュされたオブジェクトの最大数は,実際には同期の減少を考慮すると10-100xレベルとなっています.高めのキャッシュ制限はいくつかのアプリケーションではアロケーションのスピードアップをもたらしますが,大抵のケースで受け入れ難いフラグメンテーションコストもあります.更なるフラグメンテーションの制限のため,スレッドキャッシュは,アロケーションリクエストを単位として時間を計測する,インクリメンタルGCを行います.一つ以上のGCが過ぎた未使用なキャッシュオブジェクトは指数的に低下するアプローチを用いて,各自のアリーナへと徐々にフラッシュされます.

Facebookベースのイノベーション

2009年,Facebookエンジニアが"jemallocの一貫性と信頼性は素晴らしいがまだ速く出来るし,加えてそれが実際に行っていることをモニターするよりよい方法が必要だ"とjemallocの有効性を要約しました.

スピード

私たちは多くの改善点を作ることでスピードアップに取り組みました.以下はそのハイライトです.

改善された速度のほとんどは一定要因となるオーバーヘッドの削減から来ていますが(これらはクリティカルなパスで大切です),私たちもまたキャッシュサイズの厳しい制御が,キャッシュを埋める/フラッシュするコスト増加を和らげる傾向にある,データの局所性をしばしば改善することに気付きました.しかしながら,私たちはサイズ制御(各サイズクラスのための制限と,他のスレッドから完全に独立したインクリメンタルGC)とデータ構造(各サイズクラスのためにシングルリンクLIFO)を単位とするとてもシンプルなデザインを選択しました.

jemallocは以前はとてもシンプルなロック戦略を取っていましたが(エリア毎に一つのmutex),私たちは特にLinux Kernel 2.6.27以前のために,劇的な直列化の効力を持つmmap(),munmap(),madvise()のシステムコールの間はアリーナmutexを持つ事に決めました.しかしながら,私たちはアリーナのチャンクとページにまつわる全ての操作を保護するためアリーナのmutex群を降格させました,そして各アリーナのため,小さなallocation / deallocationで通常アクセスされるデータ構造を保護するため,smallサイズクラス毎に一つのmutexを追加しました.これは不十分な対処ですが,私たちはmadvise()を呼ぶ前に全てのmutex群をdropするためのダーティページのパージング機能を再設計しました.この変更は,Linux 2.6.27以降のmutexの直列化問題を完全に解決しています.

  • ダーティページパージングの書き換え

ダーティページの最大数は,定数よりはむしろトータルのメモリ使用量に比例しています,私たちはまた,一体化したものではなく,クリーンなものとダーティで未使用なページを分離させました.優先的にダーティページを再利用するために,トータルのダーティページのパージングを行うボリュームが減少します.この変更は少々仮想メモリ使用量を増加させますが,これはスループットにおいて肯定的な影響と思うことが出来ます.

  • 新しい赤黒木実装の開発

これは同じlowメモリオーバーヘッド(一つのノードに二つのポインタ)ですが,挿入/削除においておおよそ30%速くなっています.この改善は私たちのアプリケーションの一つにとってとても大切なものでした.以前の実装は2-3-4木ベースのLL(Left-Leaning)赤黒木で,全ての操作は降下パスだけで行うことが出来ました.この反復アプローチは再起や親ポインタの必要性を回避しますが,木の一貫性が連続する上昇パスの間ゆっくりと保存されるならば回避できる,外部の木の操作を必要とします.実験は,最適な赤黒木実装はゆっくりとfix-up(木のバランスを整える)すべきだと示しました.さらに,fix-upはしばしば上昇パスが完成する前に終了し,そして再起の巻き戻しはこのようなケースでは受け入れ難いコストです.私たちは,下降パスの間は親ポインタ配列初期化する非再帰な2-3木ベースのLL赤黒木実装に定め,可能であれば早期に終了させるため,上昇パスでは遅延fix-upのため配列を使います.

振り返り(Introspection)

jemallocはいつもアプリケーション終了時に,human-readableな形式で詳細な内部統計を表示することが可能ですが,これは長期間走るサーバアプリケーションでは制限された使用になります.なので,私たちはアプリケーションによって何度も呼ばれることが可能なmalloc_stats_print()を晒しました.不幸にもこれはまだコンシューマにパージングする負担を課しますが,私たちは個々の統計へのアクセスを提供するBSDのsysctl()システムコールのような,mallctl*()APIを追加しました.私たちは完全なカバレッジを確実にするために,malloc*()を単位としてmalloc_stats_print()を再実装して,そしてゆっくり時間をかけてまた,たくさんの制御(スレッドキャッシュのフラッシュやダーティページパージングの強制など)を提供するためこの機能を拡張しました.

メモリリークの診断は,プロダクションがまだ動いている状態でリークを暴く必要がある時は特に,大きなチャレンジを引き起こします.Googleのtcmallocはプロダクションユースに合った素晴らしいヒーププロファイリング機能を提供しており,私たちはそれがとても有益なものだと気付きました.しかしながら,jemallocだけが適切にメモリ使用量を制御でき,tcmallocだけが適切にメモリ使用量を解析するツールを提供していたので,いくつかのアプリケーションではますますジレンマに直面していました.そのため,私たちはjemallocに互換性のあるヒーププロファイリング機能を追加しました.これによってtcmallocを搭載している後処理ツールを活用できるようになりました.

Experimental

必要であれば.

Successes at Facebook

図を見れば分かる.前提がFacebookなので,使うなら自分の環境で確認すべし.

http://sphotos.ak.fbcdn.net/hphotos-ak-snc4/hs1387.snc4/163987_490348622199_9445547199_5849911_7181837_n.jpg

Future work

jemallocは現在とても成熟していますが,アリーナがどうスレッドに割り当てられるかなどの既知の欠点が残っています.大きな静的なデータ構造を置くためスレッドプールを立ち上げるアプリケーションを考慮するとき,残りを実行するためシングルスレッドな操作へと戻ります.アプリケーションがアリーナの割り当て(もしくは単純にアリーナの数を制限する)の制御に特別なアクションを取らない場合には,初期化フェーズは具合の悪いよく利用されるアリーナの荒れた領域(高いフラグメンテーションなどがある)を置き去りにしがちです.workaroundsは存在していますが,これらが予期しないアプリケーションの動作で起こる時のため,私たちはこれと他の問題に取り組むつもりです.

Acknowledgments

Andrei先生がいて驚き!

2011-01-01

2010年を振り返る

乗るしかない,このビッグウェーブに!

人生的なもの

博士課程まで行ったわけですが前年を持って退学し,今年から働きます.朝生でも色々話にあがりましたが,動けばチャンスはやってくる.夢の東京生活!

D言語

ここから今年が始まった気がします.

  • std.base64 (リプレース)
  • std.utf (エンハンスメント)
  • std.socket (リプレース中)
  • std.event (誰も書かないなら俺がやるしかない?)
  • std.msgpack (RPCとか途中)

その他パッチとかちょくちょく

勉強会関係

他なんか出てたかな?発表増やしたい…

レビュアとして参加してました.俺のコメントが載ってたりします!

広告出させてもらいました.次は記事を(ゲフンゲフン

その他

  • MacBook Air, Kindleのおかげでかなり移動が楽になった
  • Dvorack, Homebrewなどちょっと環境を見直したりした

多分今までで一番充実した1年だった気がする.ただD言語以外へのコミットが減ってるので,この辺もう少し手広くしたい.

Connection: close