userspace RCU(QSBR)の使い方と解説 - くまメモ
http://lttng.org/urcu|Userspace RCU という大変クールなプロジェクトがあります。 「RCU（リードコピーアップデート）をユーザースペースで行うもの」という事で、そこだけ聞くとなんのこっちゃという感じ。 リードコピーアップデートって何よ リードコピーアップデートそのものの正しい説明はWikipedia*1 でも読んでもらうとして、Wikipediaを読むのすら面倒な人の為に説明すると「みんなで共有してるデータをfree()しても良いタイミングを見極める技術」です。 特定の構造体をみんなで共有して書き換えたりしたいな → Lockとればよくね？ すごく頻繁にアクセスするし読み出しの方が多いからLockはやだな → Read-Write Lockでよくね？ Read-Write LockだとAtomic命令多すぎてパフォーマンスでないな → Lock無くしてデー
Stackを使ってQueueを作る - くまメモ
有名な話かと思ったら意外と知られていなかったのでメモ。 FILOを使ってFIFOを作るとも言います。StackでQueue作れてもQueueでStackを作る方法が思いつかないので誰か教えて下さい。もしくはこういう学問があったら紹介して頂けると嬉しいです。 簡単な説明としては、2つのStackを用意して、enqueueするときには1つ目にpush()し、dequeueするときには2つ目からpop()するだけ。 ただし2つ目のStackが空の場合は1つ目のスタックが空になるまで2つ目のスタックに移し替える。 template<typename T> class MyQueue { std::stack<T> in, out; MyQueue(){} void enqueue(const T& v) { in.push(v); } T dequeue() { if (out.empty())
max_queue 最大値をいち早く返すデータ構造 - くまメモ
ちょっとマニアックなデータ構造を紹介 その名もmax queue、使い勝手はほとんどFIFOなqueueと一緒で、enqueue()もdequeue()もO(1)だけどそれに加えて「入ってるデータのうち最大の値」もO(1)の計算量で算出するという代物。 兄弟分で最小の物を返すmin queueや、両方の機能を備えたmin-max queueもあるけどmax queueが判れば自明なので割愛。 最大の値を覚えておけば良いだけに思えるけど、最大の値がdequeueされてしまった場合にO(n)の時間を掛けて再び探索してたら条件を満たせない。 max-queueでは最大の値を覚えておくため専用のqueue（以後最大値queueと呼ぶ）を内部でもう一本持つ。 この青い線がqueueに入ってるデータ列で高さがデータの大きさを表す、下に書かれている薄い線の入ったデータ列が最大値queue。 こちらの最大
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
