第16回 StringBeginners での発表資料
Binary search with modern processors
第16回 StringBeginners での発表資料
コンパイラ中間言語およびその最適化の設計と実装
こんにちは､びしょ〜じょです｡ 年明けに買った対洗濯物用乾燥機のおかげで窓を開けたりカーテンレールにハンガーを吊るす日々が終わりました｡ ところで2月分の電気代はすでに1月分を越えようとしています｡ 1. はじめに 今年は4年次なので卒業研究! ということでjoin pointを追加したコンパイラ中間言語の設計と､その上での最適化を定義してやっていきました｡ 実装はこちら 卒研発表をスライドを作るためにも､何をしたかを噛み砕いて文に起こしてみたいと思います｡ 2. 関連研究 PLDI 2017で『Compiling without Continuations』1という発表がありました｡ 継続の緑の本をもじったタイトルですが､CPSと直接戦っている感じではないです｡ join pointと呼ばれるものを明示的に扱うことでコードサイズの爆発を抑えたり高速に動作するターゲット言語に変換しようとい
プログラムを高速化する話
9. 9 最適化について 「細かい効率のことは忘れて、時間の 97% について考え よう。時期尚早な最適化は諸悪の根源だ。それでも残り 3% についても機会を逃すべきではない」 - Donald E. Knuth 「プログラム最適化の第一法則 : 最適化するな。 プログラム最適化の第二法則 ( 上級者限定 ): まだするな。 」 - Michael A. Jackson 11. 11 最適化の対象 主に Intel の Haswell マイクロアーキテクチャ以降を対象 多くのテクニックは他のプロセッサにも応用できます ベース マイクロアーキテクチャ プロセスルール 登場年 Nehalem Nehalem 45nm 2008 〃 Westmere 32nm 2010 Sandy Bridge Sandy Bridge 32nm 2011 〃 Ivy Bridge 22nm 2012 Hasw
Optimizing Closures in O(0) time | Lambda the Ultimate
Optimizing Closures in O(0) time, by Andrew W. Keep, Alex Hearn, R. Kent Dybvig: The flat-closure model for the representation of first-class procedures is simple, safe-for-space, and efficient, allowing the values or locations of free variables to be accessed with a single memory indirect. It is a straightforward model for programmers to understand, allowing programmers to predict the worst-case
メモリモデル？なにそれ？おいしいの？ - yohhoyの日記（別館）
この記事はC++ Advent Calendar 2014の21日目にエントリしています。 内容はC++メモリモデルと逐次一貫性についての概説記事となっています。 flickr / nomadic_lass もくじ 忙しい人のための「C++メモリモデル」 C++メモリモデル一問一答 ソフトウェアからみた「C++メモリモデル」 “メモリ”という共有リソース C++ソースコードが実行されるまで メモリの一貫性と整合性 逐次一貫性モデル is Easy ハードウェアからみた「C++メモリモデル」 ハードウェア・メモリ一貫性モデル C++コンパイラの責任と自由 強いメモリモデル vs. 弱いメモリモデル 逐次一貫性モデル is Hard （本文のみ約9600字） まえがき When your hammer is C++, everything begins to look like a thumb
シェーダの最適化についての GDC 2013 講演 "Low-level Thinking in High-level Shading Languages" を翻訳しました - Siv3D 開発ブログ
Avalanche Studios Emil Persson 氏の GDC 2013 講演 "Low-level Thinking in High-level Shading Languages" を翻訳しました。 HLSL の低水準での最適化について書かれている画期的な資料で、講演者が長い開発経験で得たテクニックの数々が紹介されています。 シェーダを書くのに非常に役立つと思い、勉強も兼ねて翻訳しました。多少訳が不自然なところは目をつむってください。 講演のスピーチ文も含めた日本語訳 PDF はこちらからダウンロードできます。 【日本語訳】Persson_LowLevelThinking.pdf オリジナルの講演資料はこちらです。 Low-Level Thinking in High-Level Shading Languages - Humus - Articles 【日本語訳】"Low
「末尾最適化」を正しく理解する - ブートストラッピングでコンパイラを作る日記
以下の記事でPythonやRubyの末尾再帰関数をループに変換する手法が「末尾再帰最適化」や「末尾呼び出し最適化」として紹介されているのですが、これらの用語を使うのは間違いです。 紹介されている手法(動的束縛を利用して制御フローを変形する手法)自体は大変面白いですね。 Pythonで末尾再帰最適化をする。 Rubyで末尾再帰最適化をする。 参考文献として以下を挙げておきます。 William D. Clinger "Proper Tail Recursion and Space Efficiency" ちゃんと読み直していないので、以下の説明に間違いがあるかも知れません。その場合はご指摘お願いします。 まず「末尾呼び出し(Tail Call)」は関数の一番最後の式(末尾式)であって、関数呼び出しであるものを指します。 void foo() { bar(); baz(); /* 末尾呼び出し
プログラミング言語の最適化のしやすさについて - ブートストラッピングでコンパイラを作る日記
プログラミング言語の高級化はえてしてプログラムを複雑化し最適化を阻害してしまいます。 rowlの開発ではこのトレードオフについて神経質になろうと思っています。 最適化の基本 最適化には命令数削減・並列化・パイプライン最適化・レジスタ割り当て・スケジューリング・キャッシュ最適化・・・とさまざまな対象・手法が存在しますが、いずれにも共通する事は 元のプログラムをより良いものに変形する という事で、その際に重要なのは プログラムの意味を変えてはならない という最適化の基本原則です。プログラムの意味を変えない為にはプログラムの解析が必要で、その為の手法は大きく分けると フロー解析 型解析 です。最適化がしやすい言語とはこれらを精度よく行う事が出来る言語と言う事ができます。 また、Haskellの様な参照透過性が完璧に保たれている言語ではこれらの解析をすることなくプログラムの変形が可能です。 型解析
Firefox、第3のJITエンジン「IonMonkey」開発中 - 目標はChrome凌駕 | エンタープライズ | マイコミジャーナル
Firefox web browser - Faster, more secure & customizable Firefoxには「SpiderMonkey」「TraceMonkey」「JaegerMonkey」という3つのJavaScriptエンジンが搭載されている。「SpiderMonkey」がベースとなるJavaScriptインタプリタで、ここに「TraceMonkey」と「JaegerMonkey」という2つのJITエンジンを追加して高速化を実施している。2種類の異なるターボ機構を搭載しているようなものだ。 SpiderMonkey - FirefoxのコアJavaScriptインタプリタエンジン。ここにTraceMonkeyおよびJaegerMonkeyという2つのJIT技術を併用して高速化を実現する。 TraceMonkey - トレースタイプのJavaScript JITエ
誤差を許容することで劇的な省電力を目指すコンピューティング | スラド デベロッパー
大規模化するデータセンタや、より小型で高性能になるモバイル機など、コンピュータの省電力化は近年ますます重要になっている。こうしたデジタル計算機の動作にあたっては、常に正確な動作を得られるように十分なマージンを設けた電力を使っている。DRAM の内容が揮発しないような短いリフレッシュ間隔や、回路でタイミングエラーを発生させないための高い駆動電圧といったものだ。しかし、アプリケーションによってはそこまで正確な結果を要求しないものもある。 ワシントン大学の研究チームは、ある程度の誤差を許容することで劇的な省電力を目指すハードウェアと、それをソフトウェア面でサポートするための言語を提案している。本件は、米サンノゼで開催されている PLDI 2011 で発表される (Session 3a.“EnerJ: Approximate Data Types for Safe and General Low-
単相比較による高速化テクニック、そして、そのあまり知られていない落とし穴 - camlspotter’s blog
今日は一転、真面目な話です ある程度 OCaml プログラミング経験がある皆様は、 int, string 等の基本型の比較には多相比較ではなく、単相比較を使うべし。最適化された比較関数が使われ、早くなる という教をご存知かと思います。正しいです。でも、そこに実は落とし穴が: 実は、型だけ単相にしてもダメで、引数を全適用した形で使用しないと、最適化されない!! (OCaml 3.11.2 現在。将来は知りませんよ!!) もしこれをご存知でしたら、もう読んでいただく必要はありません。 第一のポイントは結構知られているようなのですが、実は第二のポイントはあまり知られていない様なのです。ざっと私が普段使っているOCaml のオープンソースライブラリを検索してみましたが、最適化された比較関数を使おうとしているが、第二のポイントを知らなかったため、実はされていなかった、というコードを結構見つけてしま
Haskellコードの高速化
Haskellで速いコードを書くためのヒントを無秩序に集積したもの。環境としてはGHCを想定する。私は高速化について詳しい訳ではないが、思い付いたことはなんでもかんでも書くように心がけたので、運が良ければ何か役に立つ情報があるかもしれない。 並列処理のパフォーマンスについてはこの文章では触れない。まったく経験がないので。同じ理由で、浮動小数点数を多用した数値計算コードの効率化と、書き換え規則を多用する高水準の最適化も扱わない。 お願い: 文中に間違いや分かりにくい部分があれば指摘いただけると有難いです。また、他に載せた方が良さそうな最適化テクニックや、その他の改善提案があれば教えてください。掲示板またはメールまたはTwitter(@mkotha)までお願いします。 目次 基本的なこと 遅延評価の計算量見積もりの方法と、GHCの内部に依存しないテクニック集。入門書を読んだけれども、Haske
アセンブラコードで見るC++ Composer XEの強力な最適化機能 | OSDN Magazine
インテル C++ Composer XEには、強力な最適化機能を備えるコンパイラが含まれている。インテルCPUが備えるSSEやAVXといった機能を効率的に利用するコードや、マルチコアによる並列処理を行うコードを自動的に生成できるのが特徴だ。本記事ではインテル C++ Composer XEが持つさまざまな最適化機能を紹介するとともに、コンパイラが出力するアセンブラコードをチェックしてその効果を探っていく。 無視できないコンパイラの最適化機能、アプリケーションによっては数十パーセントものパフォーマンス向上も 近年のCPUの進化に伴い、コンパイラの最適化機能が注目されるようになってきた。パイプライン化やキャッシュの大容量化、分岐予測や投機的な実行といった機能の採用など、CPUの内部アーキテクチャは進化を続けている。そのため、コンパイラにはCPUのリソースを効率良く利用できるバイナリコードを生成
講座 最適化技法の物理学的解釈 ー古典力学から最大値原理へー
以下は、同じタイトルで、社団法人建築研究振興協会「建築の研究」誌に2005年12月号から2007年10月号にとびとびで連載されたものである。建築振興協会の承認のもとで、転載したものである。 「建築の研究」誌は2ヶ月に1回の割りで発行しており、また、紙面の都合で、連載記事も次号送りとなることがあり、一部の読者から、まとめて読みたいという要望が連載中から筆者に届くこともあった。そうした理由でホームページ掲載とした。 ホームページの画面の都合で、レイアウトを多少変更したが、明らかな誤記を除いて、内容はそのままである。 皆様の研究に役立てば幸いである。 青木 義次 2008年1月 第1回 ニュートンの運動方程式と変数変換 ０. はじめに（ガイダンス） １．ニュートンの運動方程式 ２．ニュートンの運動方程式における変数変換 第２回 オイラー・ラグランジュ方程式 ３．エネルギーとラグラ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
最適化超入門
Happy Optimization
http://blog.ezyang.com/2011/05/space-leak-zoo/
x86/x64最適化勉強会1