mixi Engineers’ Blog » Inside Tokyo Cabinet その五
先日、MySQL Conferenceという催しに行ってきました。そこでMySQLの開発者のBrian Aker氏およびMichael Widenius氏と話をする機会があったのですが、やっぱしトップランナー達と議論するのは刺激になるなぁと思ったmikioです（その時の資料）。さて、一連の連載も今回が感動の最終回で、TCの性能上の蘊蓄をお届けいたします。 なぜdynamic hashingを使わないか Brianさん達とTCの実装についても少し議論したのですが、その際にdynamic hashingをなぜ使わないのかと問われました。その背景として、TCやQDBMではハッシュのバケット数（＝格納するレコード数を予測してその数倍に設定すべき値）をデータベース作成時に指定しなければならないという問題があります。バケット数が大きすぎると空間効率が劣化し、小さすぎると時間効率が劣化するというトレード
mixi Engineers’ Blog » Inside Tokyo Cabinet その四
涼しさに夏の終わりを感じてなんだか寂しくなるも、新しいオフィスから見えるパノラマの空の高さに癒されているmikioです。秋は気が変わりやすいこともあり、今回は唐突にDBMの並列性についての考察を記してみます。 並列性って何? 最近はマルチコアのプロセッサが当り前になってきて、そのパワーを100%引き出すために、並列性をできるだけ高めることが求められるようになってきました。それについて考える前に、まずは用語の整理をしておきましょうか。 並行性 : 二つ以上のタスクを一緒に進めること。必ずしも同時に処理を行うとは限らず、Aを少しやってからBを少しやって、それからまたAを少しやって、またBをやって...といった、いわゆるタイムシェアリングで実現してもよい雰囲気。 並列性 : 二つ以上のタスクを同時に進めること。タスクを複数のマシンに割り当てたり、複数のCPUに割り当てたり、CPU内の複数のコアに
Inside Tokyo Cabinet その参 - mixi engineer blog
この連載のように小難しい記事が続くと、読者の皆さんだけでなく執筆陣まで引いてしまうのではないかと心配しているmikioです。いやいや、いいんです。ハッキングから夜のオカズまでバラエティに富んだブログを目指すべく、私は私なりの記事を、たとえマイノリティ向けだとしても臆さず書いてゆくのです。今回はTCの実装の詳細についてお届けします。 QDBMとどう違うの? QDBMもTCと同様にDBMの一実装で、小さくて速くて使いやすいをモットーに作りはじめて、それなりに目標を達成できたと自負しているプロダクトです。しかし、今思えばいろいろと気に入らない点がいくつかありました。TCはそれを克服すべく一から書き直したものです。具体的には以下の点が違います。 空間効率の向上 : データベースファイルのサイズがもっと小さい 時間効率の向上 : 読み書きにかかる時間がもっと短い 耐障害性の向上 : データベースファ
Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー
,. -‐'''''""¨¨¨ヽ (.＿＿_,,,... -ｧァﾌ| あ…ありのまま 今日 起こった事を話すぜ！ |i i| }! }} /／| |l､{ j} /,,ｨ//｜ 『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ､_ﾉ／ u {:}//ﾍ |ﾘ u' } ,ﾉ _,!V,ﾊ | ／´fト､_{ﾙ{,ィ'ｅﾗ , ﾀ人 な… 何を言ってるのか わからねーと思うが /' ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ おれも何をされたのかわからなかった… ,ﾞ ／ )ヽ iLﾚ u' | | ヾｌﾄﾊ〉 |／_／ ﾊ !ニ⊇ '／:} V:::::ヽ 頭がどうにかなりそうだった… /／ 二二二7'T'' ／u' __ /:::::::/｀ヽ /'
mixi Engineers’ Blog » Inside Tokyo Cabinet その弐
予定を立てた途端にやりたくなくなる症候群に堪えて連載を続けるmikioです（こんな私でもエアーマンくらいは倒せます）。前回はDBMの基本について説明しましたが、それを忠実に実装しても実際には使いものにはならないことにも触れました。今回は、実用的なDBMに進化すべく、Tokyo Cabinet（およびその前身のQDBM）で考えた工夫についてお話します。 ハッシュ関数についてもう少し 前回の記事に関して、「ハッシュ関数はビットシフト使って実装した方が早いよ」という旨のお便りをいただきました（ありがとうございます）。まさにその通りで、乗算命令（ここではimull）より左シフト命令（ここではsall）の方が速いみたいです（Intelの資料によると、mulが15から18で、salが4とのこと）。しかし、DBMの場合はファイルI/Oにかかる時間が支配的になるというのが重要な点です。したがって、ハッシュ
Inside Tokyo Cabinet その壱 - mixi engineer blog
約半年間の沈黙を破ってOSSの世界に戻ってきつつあるmikioです。先日、Tokyo Cabinet（以下「TC」と呼びます）というデータベースライブラリをリリースしました。今回から数回に分けて、TCの設計と苦労話について連載してみます。 DBMとは TCは、いわゆるDBMの系譜のデータベースライブラリで、単純なハッシュテーブルをファイル上で永続化するだけの機能を提供します。DBMはAT&Tの古代UNIXの時代から受け継がれる伝統芸能なのですが、私はそういう枯れた技術が大好きなのです。 プログラマの皆さんは、PerlやRubyではハッシュ（連想配列）と呼ばれ、JavaやC++ではmapと呼ばれるような、何らかのキーに関連づけてなんらかの値を記録するデータ構造って実によく使いますよね。例えばmixiでは、ユーザアカウントに関連する情報（名前とかニックネームとか）は、ユーザIDをキーにしたハッ
講義資料 配列解析アルゴリズム特論I 情報生命科学基礎/演習 他 -渋谷哲朗
平成20年度 東京大学大学院 情報理工学系研究科・コンピュータ科学専攻 配列解析アルゴリズム特論I 4/10 4/17 4/24 5/1 5/8 5/15 5/22 5/29 (The problem to be reported - in English) 6/5 6/12 6/19 7/3 7/10 7/17 東京大学 理学部・情報科学科 情報科学特別講義３ （情報科学とバイオインフォマティクス） 6/10 7/15 7/22 東京大学大学院 新領域創成科学研究科・情報生命科学専攻 情報生命科学基礎/演習 5/27 6/17 京都大学大学院 薬学研究科・医薬創成情報科学専攻 情報科学概論 6/3 中央大学大学院 理工学系研究科・物理学専攻 物理学特別講義第二 TBA 創価大学工学部 生命情報工学科 TBA TBA 戻る Copyright (c) 2004- Tetsuo
テスト自動化 - Wikipedia
この自動化には通常、以下のような手順が含まれる。 テストケースの設計 テストケース[2]はプログラムがどのように動作すべきかを理解していないと作れない。JTest等のように、プログラムの構造に基づいて自動的にテストケースを作成するツールも存在するが、プログラムの実行結果がどうなるべきかは基本的に人間が決定する。 テストの実行と結果の確認 テストケースが実行可能なプログラムで記述されていれば、テストの実行と結果の確認は自動化できる。単体テストの自動実行フレームワークとしてxUnitがある。xUnitには、各種言語向けの実装が公開されており、通常のプログラムと同じ形式でテストケースを記述することができる。 テスト進捗の管理 カバレッジ(網羅率)分析 信頼度成長曲線 レポートの作成
ソフトウェアテスト - Wikipedia
ソフトウェアテスト (英: software testing) は、コンピュータのプログラムから仕様にない振舞または欠陥（バグ）を見つけ出す作業のことである。ソフトウェアテストで見つかったプログラム中の欠陥を修正する作業をデバッグという。ソフトウェアテストに成功するとは、テストで欠陥が発見されるか、規定した試験項目にすべて合格するか、規定した品質目標に到達することである。目標とした品質には、規定した試験項目にすべて合格することもある。例えば、OS, プログラミング言語では、仕様を満たしているかどうかの適合試験を規定している。ソフトウェアテストでは、欠陥が存在することを示すことはできるが、欠陥が存在しないことは証明できない。ソフトウェアに仕様にない振舞がないことを保証する作業を証明といい、証明用のシステム、証明しやすい言語も多数存在している。本項では動的なソフトウェアテストを中心に扱う。 ソ
テスト自動化とは - ソフトウェアテスト自動化まとめサイト なんでも自動化サイト
1.V字開発プロセスモデルによる分類 1.1.要件定義 VDM 形式手法(Formal Methods)により仕様の自動検証などを行う。 1.2.システム設計 モデル検査 Spin モデル検査により状態遷移図の状態で自動検証を行う。 LTSA モデル検査により状態遷移図の状態で自動検証を行う。 NuSMV モデル検査により状態遷移図の状態で自動検証を行う。 モデル駆動 ZIPC(商用:キャッツ株式会社) 状態遷移図による検証が可能 MDA モデルを実際に動かして動作検証する。Executable Umlなどを使用して仕様を記述。 IAR visualSTATE(商用:IAR SYSTEMS) ステートマシンを設計、検証、実装できるツール。20ステートまでの無料の評価版あり 1.3.詳細設計 Enterprise Architect(商用:SPARX SYSTEMS) テストツールではないが
安藤のためのC言語テスティングフレームワークCUnit
安藤のためのC言語テスティングフレームワークCUnit 『CUnit for Mr.Ando』は CppUnit-x をベースにしたC言語テスティングフレームワークです。 これは、C言語のソースコードを単体テストのために供給します。 "CUnit for Mr.Ando" is CppUnit-x based C langage testing framework for Mr.Ando. It provide the C source code for unit testing. イントロダクション Introduction. JUnit は非常に強力なJava単体テストツールです。 しかしながら、多くのC言語技術者はJava言語を理解することができません。 JUnit is a very powerful Java simple unit test tool. However, man
Google Code Blog: Mercurial support for Project Hosting on Google Code
Interested in learning about the latest advancements in Android, App Engine, Chrome, Google Web Toolkit, OpenSocial, and more? Register to attend Google I/O, May 27-28 at Moscone West in San Francisco. We are happy to announce that Project Hosting on Google Code now supports the Mercurial version control system in addition to Subversion. This is being initially rolled out as a preview release to a
NAKAMURA Minoru's Diary (2006年2月)
2002 | 10 | 11 | 12 2003 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 2004 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 2005 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 2006 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 2007 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 2008 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 2009 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1
Technical Note TN2123:CrashReporter
CrashReporterはクラッシュしているすべてのプログラムに関する情報を記録する、Mac OS Xのデバッグ機能です。このテクニカルノートではCrashReporterについて詳しく説明します。CrashReporterが生成するクラッシュログと、そのログを利用してプログラムをデバッグする方法について説明します。このテクニカルノートは、Mac OS Xユーザ空間のソフトウェアを開発する方なら誰にでも役に立ちます。 はじめにMac OS XのCrashReporterは、アプリケーションが現場で直面する問題を把握するための便利な機能です。CrashReporterは3つの有用なアクションを実行します。プログラムがクラッシュすると、CrashReporter はクラッシュログ（一般的に、~/Library/Logs/CrashReporter/<プログラム名>.crash.log）を記録
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://tut-framework.sourceforge.net/
Google Code Archive - Long-term storage for Google Code Project Hosting.
Sign in - Google Accounts