徐々に高度になるリングバッファの話 - Software Transactional Memo
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
文字列から浮動小数点数に変換する、なるべく速く - toge's diary
TL;DR 文字列から浮動小数点数に変換するならfastfloat使いましょう。 私が試せる環境で比較する限り、とても速いです。 細かいことが気になります C++でちょっとしたプログラムを書くときにいつも気になるのが 「文字列データから指定データ型への変換処理をどうやって効率的に書くか」 です。私だけかもしれませんが。 特に悩んでしまうのが「文字列→浮動小数点」です。 std::scanf, std::stringstreamを使うものは大抵すごく遅い std::strtodstd::stodはstd::stringへの変換が入るので避けたい std::from_charsは(libstdc++が)浮動小数点型に対応していない boost::sprit::qiが何故か速いのだけれどこのためにboost::sprit使うのは重い と色々制約が多いのです。どうにかならないものか。 fast_f
Halide事始め - プログラミングの実験場
MIT Halide(http://halide-lang.org/)というC++の高速画像処理ライブラリが去年リリースされた。C++内のDSLを使っていて、画像処理を、 計算のアルゴリズム アルゴリズム自体は副作用がなく、純粋関数的に定義される。 実装の詳細（「スケジュール」） スケジュールは、計算の並列化と、複数の計算ステップの融合を最適化する方法を指定する。 を分離した形で簡潔に書ける。 凄いのは、抽象的に書いたアルゴリズムからライブラリによって低レベルコードを出力させたほうが、手書きでチューニングしたコードよりも速いことすらあること（という作者の主張）。たとえば最近開発されたlocal Laplacian filterというの複雑なアルゴリズム（http://people.csail.mit.edu/sparis/publi/2011/siggraph/、pixelwise ope
Lock-Free Multi-Producer Multi-Consumer Queue on Ring Buffer | Linux Journal
Nowadays, high-performance server software (for example, the HTTP accelerator) in most cases runs on multicore machines. Modern hardware could provide 32, 64 or more CPU cores. In such highly concurrent environments, lock contention sometimes hurts overall system performance more than data copying, context switches and so on. Thus, moving the hottest data structures from a locked to a lock-free de
高速なハッシュテーブルを設計する | POSTD
(訳注：2016/9/28、頂きましたフィードバックを元に記事を修正いたしました。) はじめに 本稿では、高速で汎用的なハッシュテーブルを作るために行う、設計についての多くの意思決定事項を紹介します。最終的に、私の emilib::HashSet とC++11の std::unordered_set の間のベンチマークが出来上がりました。もし、ハッシュテーブルに興味があって、自分で設計したいなら（どのプログラミング言語かに関わらず）、本稿がヒントになるかもしれません。 ハッシュテーブル は、素晴らしい発明です。 ならし計算量O(1) ( O(√N)時間 )で、挿入、削除、検索を行うことができます。ならし計算量とは、ハッシュテーブルの計算に平均でO(1)の計算量がかかることを意味しますが、時々、これよりも多くの時間がかかる場合があります。具体的には、ハッシュテーブルに空きがない場合で、挿入の
C++でブルームフィルタを実装する方法 | POSTD
ブルームフィルタとは、「ある要素が集合のメンバである可能性があるか、それとも確実に集合のメンバではないか」を効果的に確認することのできるデータ構造です。この記事では、C++でブルームフィルタを実装する簡単な方法をご紹介します。 ブルームフィルタとは何なのか 、また、 その背後にある多くの数学的要素 については紹介していませんので、ご了承ください。これらのトピックに関しては、素晴らしいリソースがあるので、そちらを参考にしてください。 インターフェイス まずは、ブルームフィルタを定義していきましょう。ここでは、3つのパブリック関数を定義していきます。 コンストラクタ ブルームフィルタにアイテムを追加する関数 アイテムがブルームフィルタにある可能性を確認するためのクエリを行う関数 また、フィルタの状態を保持するビットの配列を含んだ、メンバ変数についても定義します。 #include <vecto
Boost.Lockfree ロックフリーキューの制限 - Faith and Brave - C++で遊ぼう
Boost 1.53.0時点のロックフリーキューは、要素型Tがtrivially copyable(memcpy可能な型)であることを要求します。そのため、ユーザー定義型の多くはロックフリーキューに格納できません。 #include <boost/lockfree/queue.hpp> int main() { boost::lockfree::queue<std::string> que(3); // エラー！ } In file included from main.cpp:3:0: boost_1_53_0/boost/lockfree/queue.hpp: In instantiation of 'class boost::lockfree::queue<std::basic_string<char> >': main.cpp:7:41: required from here bo
GoogleがB-tree実装のSTLコンテナを公開
C++ containers that save memory and time cpp-btree - C++ B-tree - Google Project Hosting Googleが、B-tree実装のSTLコンテナー(map, set, multimap, multiset)を発表した。 多くのSTLの実装では、map, set, multimap, multisetは、Red-Black treeで実装されている。Googleの発表によれば、B-tree実装のコンテナーは、赤黒木実装に比べて、速度が上がり、しかもメモリ消費量も削減できるとしている。 紹介まで。 B木は一つのノードに複数の要素を格納する。これにより、ポインターなどのオーバーヘッドを低減でき、メモリ消費量の削減につながる。また、複数の要素を一括してノードに詰め込むため、速度向上もあるのかもしれないが、そのへんはよ
unordered 系コンテナの max_load_factor 周りについて - melpon日記 - HaskellもC++もまともに扱えないへたれのページ
この記事は LL/ML Advent Calendar １９日目の記事です。 C++11 で追加された unordered 系のコンテナは、ハッシュを使って要素を管理するコンテナです。 そのハッシュを使ったアルゴリズムもいくつかありますが、C++11 では OpenHashing 方式を想定しているようです。 OpenHashing 方式は、同じバケットに対して複数の要素が入ってしまう場合、リンクリストなどでそれらの要素を繋いでやる方式です。 細かいことやその他の方式については SlideBoom closed down を見ましょう。 この記事では C++11 の unordered 系コンテナ特有の、バケットやリハッシュ関数について説明します。 バケット操作関数 バケットの数は bucket_count() で取得できます。また、n 番目のバケットに入っている要素数は bucket_s
Suffix Array を作る - SA-IS の実装
Suffix Array は今若者の間で人気のデータ構造です． マイ suffix array を実装することで，オシャレ度がアップしてモテ系になり，女子力も上がると言われています． その中でも今特に，手軽でクールな SA-IS (アルファベットサイズ固定の下で線形時間で省メモリで suffix array が作れる今最強のアルゴリズム) の実装がブームです． 僕もブームに便乗して，実装してみました． ところで，SA-IS は流行っているので，日本語でもすでに様々なところで記事が書かれています (日付順)． SAIS(Suffix Array - Induced Sorting) - EchizenBlog-Zwei SA-IS: SuffixArray線形構築 - sileの日記 SA-IS - (iwi) ｛ 反省します - TopCoder部 接尾辞配列(Suffix Array)の
STL風に使えるマップ型コンテナの紹介と性能比較 - Preferred Networks Research & Development
最近スマートフォンに乗り換えました。徳永です。 C++は世に数あるプログラミング言語の中では比較的メモリを食わない方ですが、それでもメモリ使用量が問題となる場合はあります。そのような場合の対処方法はいくつか有りますが、手軽に選択できる方法として、今日はSTLのmapやunordered_mapと同じ感じで使えるデータ構造をいくつか紹介したい思います。 以下、計算量の表記をする際には、要素数をnとします。 Loki::AssocVector LokiはModern C++ Designという本の作者であるAndrei Alexandrescuが開発したライブラリです。AssocVectorはその中の一つとして提供されているクラスで、vector<pair<key, value> >という型のベクターをkeyでソートした状態で持つ事により、二分探索による要素の探索を可能にしたデータ構造です。こ
dag_vector: ランダムアクセス可能な圧縮配列 - Preferred Networks Research & Development
こんにちは、この夏はシルキードライで乗り切りたい岡野原です。 今日は最近公開したC++のオープンソースであるdag vectorについて紹介します。 github: dag_vector ライセンスは修正BSDライセンスです。 dag vector (direct accessible gamma code vector) は値を圧縮して格納したまま任意の場所の値を高速に参照可能な配列ライブラリです。しかもデータ末尾への追記が可能です。 dag vectorはstd::vectorのように利用できます。下にいくつか例を見ていきましょう。 dag_vectorの例 #include "dag_vector.hpp" // dag_vectorは0以上の正整数の配列を扱う配列。 dag_vector dv; // 値はいつでも追加可能。追加された値は圧縮して格納される // 正整数xは2lg(
Story of Your Life » Blog Archive » Expression Templateの蛇足的な話
Preface 前にプリプロセサを駆使してシリアライザを書いたことがあったのですが、Expression Template(以下 式テンプレート)を使えば#define使わなくても近いようなことできるなーと思いついたので、実際に作ってみました。 で、そっちを説明しようと思ったんですが、やっぱり気が変わって、式テンプレート自体の自分なりの理解を簡単に説明したいと思います。 ちなみに式テンプレートのちゃんとした入門は、参考URLの方で錚々たる方々が素晴らしい記事を書いているので、そちらを参考にしてください。この記事はまぁ、蛇足的な、自己満足のためのものです。 Introduction 式テンプレートは、最初、行列やベクトルを使った科学計算の効率化のために考案されました。 例えば以下のようにVectorクラスの演算を行うとします。 Vector v_result, v1, v2, v3; v
ハザードポインタ版Lock-Free List - yamasaのネタ帳
前回の記事で時間切れのために書ききれなかった Lock-Free List について、サンプルコードをgithubに上げました。 GitHub - yamasa/lockfree: Experimental implementations of lock-free algorithms, using hazard pointers and tagged pointers. sortedlistmap.h がそれです。わかりやすくするため、Allocator対応などの細かい機能については省いています。決して手抜きではありません。;-) Lock-Free List のアルゴリズムについてはkumagiさんの解説記事が非常にわかりやすいので、そちらをご覧ください。
昆布じゃないのよ
目次 ホーム 連絡をする RSS Login Blog 利用状況 投稿数 - 1078 記事 - 2 コメント - 26137 トラックバック - 363 ニュース 著作とお薦めの品々は 著作とお薦めの品々は 東方熱帯林へ。 わんくま 東京勉強会#2 C++/CLI カクテル・レシピ 東京勉強会#3 template vs. generics 大阪勉強会#6 C++むかしばなし 東京勉強会#7 C++むかしばなし 東京勉強会#8 STL/CLRによるGeneric Programming TechEd 2007 @YOKOHAMA C++・C++/CLI・C# 適材適所 東京勉強会#14 Making of BOF 東京勉強会#15 状態遷移 名古屋勉強会#2 WinUnit - お気楽お手軽UnitTest CodeZine Cで実現する「ぷちオブジェクト指向」 CUnitによるテスト駆
正規表現しちへんげ！ 第二夜
09:25 10/12/31 年末まとめ 今年何やったっけ、と日記を読み返していました。何もやってないな…。 Polemy 作りました、くらい。 言語処理系作るのはやっぱり楽しいですね。 汎用言語として使う本格的なものを作ろうとすると懲りすぎて一歩も進まなくなってしまう自分が見えるので、 来年は、そうだなあ、TopCoder/ICPC風コンテストに特化した言語というかC++へのトランスレータ、 くらいに絞って作ってみようかなあ。 書いた記事だと 最短性チェックの話 が自分では割と気に入っています。 これのもっとバグを許容するバージョン作れないか。 読んだ論文で面白かったのは "A Pearl on SAT Solving in Prolog" と "When Simulation Meets Antichains" (PDF) など。 あとは、今年読んで面白かった本ベスト５（順不同）： 『
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Google Code Archive - Long-term storage for Google Code Project Hosting.
「なぜsetを使っちゃいけないの？」
https://sleepy-yoshi.hatenablog.com/entry/20111002/p1
「ソートも、サーチも、あるんだよ」 ～標準C++ライブラリにみるアルゴリズムの面白さ