徐々に高度になるリングバッファの話 - Software Transactional Memo
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
2で割ることと3で割ること - Qiita
この記事でお題にするのはCPUレジスタ上の整数除算です。以下、単に除算とも書きます。 除算は非常に高コストな演算なため、コンパイラは最適化によって、できるだけ整数除算を別の計算に置き換えようとします。 最適化ができる場合の一つとして、割る数が定数である場合があります。頭のいいコンパイラは、除算を乗算とビットシフト等を駆使した演算に置き換えます。この記事では、そういった最適化の背景にある理屈を部分的に解説します。 計算機環境としてはモダンなx86 CPUを仮定します。したがってレジスタは32/64ビットであり、負数は2の補数表現になっています。ある程度は他の命令セットでも通用する話になっているかもしれません。 そもそも整数の除算とは プログラミングにおける整数の除算の定義について確認します。整数$n$を整数$d$で割るとき $$ n = q \times d + r $$ が成り立つように除
高校生がアルゴリズムとスパコンの力で、京都の碁盤目状道路を13.9%効率化した話 - Qiita
2. 本研究で解く問題 「いざ研究しよう！」と思っても、条件や設定を決めないと何も始まりません。 まずは研究を分かりやすくするために、「一つの問題」に落とし込むことにしました。 問題設定 縦 $N$ 行・横 $N$ 列の大きさの碁盤の目があります。隣り合う交差点間の距離は 1 です。つまり、交差点が合計で $N^2$ 個あり、それぞれ座標 $(1, 1), (1, 2), ..., (1, N),$ $(2, 1), (2, 2), ..., (N, N-1), (N, N)$ に位置すると考えることもできます。 下の図は、$N = 4$ の場合の交差点の位置です。 あなたは、碁盤の目の交差点の位置は変えずに、道路の並びのみを変えることができます。上手く道路の並びを変えることで、できるだけ「便利」な道路網を建設してください。 「便利な道路網」って何？ 私は、以下の 2 つの条件を満たす道路
How to tackle hard combinatorial optimization problems arising in real applications?
実務に現れる多くの事例が組合せ最適化問題にモデル化できることが再認識されるようになりました． しかし，その多くはNP困難問題と呼ばれる計算困難な組合せ最適化問題であり，どのようにアプローチすれば良いか悩んでいる人は少なくないと思います． 本講演では，実務に現れる組合せ最適化問題に対する実践的なアプロ…
mrubyやKopiLuaにはなぜ文字連結用オペコードがあるの? ① (あるいはJavaの文字連結最適化について) - ほげほげにゃ
前置き 最近色々ありましてmrubyやKopiLua(C#によるLua実装)のソースコードを読んだりしております。 ちょうどVM部分を読んでいたら、面白い部分を見つけました。 mrubyのバイトコードにOP_STRCAT(文字連結)っていうのがあるのに驚いてたけど, LuaVM読んでたらOP_CONCATとかあったし文字連結系のオペコード用意するのって普通なんです…?— どみとり (@domitry) 2013, 12月 5 これまでx86のアセンブラしか読んだことがなかったので特殊かどうかよくわからない… そこでふとLL言語でない, 例えばJavaのVMはどうなってるんだろうなーと思い調べてみました。 昨日のお話、Javaのバイトコードを見てみたらstrcatやらconcatはなかった… キャストとかオブジェクト指向な要素(newとかclass method呼び出しとか)とかは含まれてた
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Faster than Rust and C++: the PERFECT hash table
Automatic Algorithms Optimization via Fast Matrix Exponentiation
