徐々に高度になるリングバッファの話 - Software Transactional Memo

リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit

[t-tanaka]

複数スレッドから利用されるバッファ機構は，素人が実装すると高確率でバグるので，実務ではライブラリで提供されたものを使用するのをお勧め。もちろん学習用に自分で再実装するのはありだが。

[tattyu]

同時に同じメモリを触らない様にするだけで高速化するの面白いな。前にマルチスレッド高速化対応したら、クライアント様の推奨スペック以下の2コア2スレPCで処理落ちすると言われてクソムカついたの思い出した。。。

[naoya2k]

たいていの人が「ロックなしwait-freeで実装する方法」でメモリバリアの必要性がわからないところ(そしてテストは通るが実戦では低確率でバグるというダメなコードを作ってしまう)、ちゃんと書かれていてよかった。

[tettekete37564]

いちいちモジュロ計算するのは効率悪く無いか？と思ったら、“buffer_.size()が2の冪乗である限りにおいて、-1した値は最大値以下全部のビットが立った状態になっているのでそれを” < なるほどね

[rryu]

一見無駄な変数のコピーを使うようにするとマルチコアで実行する時に速くなるとか、知識がなかったらまるっきり謎なコードである。

[revert]

面白いけど自分とは無関係みたいに思ってる人が多そうだけど、何気なく使ってるロガーライブラリの中ではこの手のテクニックが使われてるし、意外と身近な代物ではあるんだよね

[napsucks]

多段キャッシュに支えられ超高速で疾走する全方位無双にも思える現代のCPUコアも、キャッシュラインを意識してプログラムしないとパフォーマンスが出ないことがあるのか

[chintaro3]

「0に戻さずに単調に増やし続けた場合、整数がオーバーフローする危険は一応あるが、毎秒40億回dequeueに成功し続けてもオーバーフローするのは126年後とかである。」うへぇ、割り切った実装だなぁ

[PrivateIntMain]

全くもってわからん領域がまた一つ増えた。職業プログラマなのになぁ。

[ken39arg]

キャッシュラインまで意識できる自信はない

[mattn]

リングバッファの絵かっこいい

[mas-higa]

"リングバッファのイメージ図" [これはひどい]

[blackphone9]

バッファサイズを2^n限定､AND演算つかって高速化はベアメタル組み込みでも良く使ってる｡UARTの通信バッファとか｡逆にマルチコア向けはぜんぜん触ったこと無いから新鮮｡

[igrep]

"傍目には無駄な変数2つと無駄な判定と代入を足したようにしか見えないのにこのような高速化が得られる。マルチコアプログラミングの醍醐味である。"

[JUN_NETWORKS]

CSの醍醐味って感じがしておもしれ〜

[yarumato]

“リング状にバッファを置いてReadとWriteのインデックスがグルグルと回る構造。容量上限と引き換えに高速な読み書き速度を得る。メモリ確保行わないので性能高い。実装自体は情報系の大学生の演習レベルの難度”

[kuhataku03]

ビジネスロジックの分離やシンプルなコードが崇拝される一方で、ハードウェアの環境/特性を活かしてプログラミングすると本来のロジックに関係のないコードを入れざる得ず、分離するのは難しい or 無理

[hirorinya]

へー学び

[y-kawaz]

良い。／最後の謎の絵は何か島本みを感じる。

[XYXY]

なるほど…

[halfrack]

マルチスレッド

[andonut146]

「オーバーフローするのは126年後とかである」素晴らしい。しかし、複数がPush()・Pop()するのは一人、みたいなQueueしか今まで見たことないな…。

[UhoNiceGuy]

現代的なCPUでもmod演算は時間がかかるのか//「どうせオーバーフローしないんだから0に巻き戻さなくていいよ」は勉強になった//キャッシュのラインとか凄い世界だ

[gurutakezawa]

理解はできるんだけどそれでも126年後が本当に126年後なのかとか実際に来ることは無いのかとか不安になるのはジジィだからなのかなぁ…

[nezuku]

バッファのサイズを超えたらインデックスを0に戻して…はバグなく書ききるのは難しい、それならばインデックスを符号なし64ビット整数と。オーバーフローする心配の前にシステムが限界になるだろうと。

[tomei10]

謎のイメージ図やめい

[rogertroutman]

記事もブコメも何ひとつとして理解できないブクマがホッテントリのトップに位置していることに強い不安を覚えて60分間ずっと我慢していたアルコールにとうとう手が伸びてしまった

[cocoasynn]

勉強になる

[rasterson]

16bit CPU時代にはインデックスはゼロに戻すものと教わったが、こういう高速化の割り切りもあるのですね。勉強になった。ところで、enque()の時はインデックスを進めてから値を書いた方が安全だと思う。セマフォ無いなら

[umai_bow]

リングバッファすき

[spark7]

サイズが2のn乗ならモジュロよりAND演算の方が早いというのが知れただけでもよかった。実際はそんなケースの方が少ないが。

[so-apps]

多くの場合、これがボトルネックになるようなら設計が間違っている。boost とかにあれば使いたいという程度かな。勉強にはなる。