ソート済の整数列を圧縮する件
圧縮されたソート済の整数列ってのは汎用的なデータ構造で、たとえば検索エンジンの転置インデックスとか、いろんなところで使うわけです。で、検索エンジンの場合は速度重要なので、PForDeltaとか様々なデータ構造が研究されてる。 一方、H2O には、ブラウザキャッシュに載ってない js や css をサーバプッシュする仕組み「cache-aware server push」があって、何がキャッシュされているか判定するためにブルームフィルタを全ての HTTP リクエストに含める必要がある。 で、ブルームフィルタを圧縮しようと思うと、ブルームフィルタってのはソート済の整数列として表現できるので、これを圧縮しようって話になる。 検索エンジン等で使う場合は速度重要だけど、HTTPリクエストに載せる場合は空間効率のほうが重要になる。ってことで、空間効率が理論限界に近いゴロム符号（の特殊系であるライス符号
雑なツイートをしてしまったばかりにrubyを高速化するはめになった俺たちは！
逆に言うと、Rubyの文字列型の内部実装がropeになれば、freezeしてもしなくても変わらない速度が出るようになって、結局freezeする必要なんてなかったんやーで丸く収まるんじゃないの？と思いました #雑な感想 — Kazuho Oku (@kazuho) October 6, 2015とツイートしたところ、処理系の中の人から @kazuho 文字列を弄る話じゃなくて、文字列の identity の話なので、ちょっと関係ないかなぁ、と — _ko1 (@_ko1) October 6, 2015みたいなツッコミをもらって、うっすみません…ってなってRuby VMのコードを読むことになったわけです。 で、まあ、いくつか気になる点があったので手をつけてしまいました。 1. オブジェクト生成のホットパスの最適化 ホットスポットだとされていたところのコードを読んでると、オブジェクト生成の際に
前方秘匿性 (forward secrecy) をもつウェブサイトの正しい設定方法
前方秘匿性（forward secrecy）とは、以下のような性質を指します。 公開鍵暗号の秘密鍵のように、比較的長期に渡って使われる鍵が漏えいしたときでも、それまで通信していた暗号文が解読されないという性質 鍵が漏れることも想定せよ――クラウド時代における「楕円曲線暗号」の必然性 - @IT 鍵が攻撃者や諜報機関など第三者の知るところとなった場合でも、それまで通信していた暗号文が解読されないようにしないといけない、という考え方とともに、最近 HTTPS を利用するウェブサイトにおいても導入が求められるようになってきた概念です。 前方秘匿性を満たすウェブサイトの設定方法については、TLSの暗号化方式をECDH_RSAあるいはECDHE_RSAに設定すれば良い、と述べている文献が多いです。 ですが、ほとんどのウェブサーバにおいて、それは誤りです。 なぜか。 通信を暗号化する鍵（セッション鍵）
C言語で「1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に」の5問目を解いてみた
「Java8で「ソフトウェアエンジニアならば1時間以内に解けなければいけない5つの問題」の5問目を解いてみた」と「Perl6で「ソフトウェアエンジニアならば1時間以内に解けなければいけない5つの問題」の5問目を解いてみた」経由。 以下のような問題ですね。 1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる とてもいい問題だと思うし、一方で上の回答例がeval的な手法を使っていたので、そういうズルをせずに解いたらどうなるだろう、ということでCで書いてみた。 正解が出るようになるまでの所要時間、約30分。なんとかプログラマ合格のようです。 #include <stdio.h> #define MAX_POS 9 #define EXPE
論理削除はなぜ「筋が悪い」か
「論理削除が云々について - mike-neckのブログ」を読んで。 データベース設計において、「テーブルの書き換えをするな、immutableなマスタと更新ログによって全てを構成しろ」というこの記事の主張はモデリング論として全く正しい。 だが、残念なことに、ディスクやメモリが貴重な資源だった時代の技術であるRDBは、そのようなモデリングに基づいて設計されたデータベースには必ずしも適していない。 第一の問題は、RDBに対してなされる様々な「更新」（トランザクション）は不定形（どのテーブルをどのように修正するかはアプリケーション依存）だという点。不定形な「更新」を時系列にそってRDBに記録していくのは、設計と並走性の点において困難あるいは煩雑なコーディングが必要になる（というか、そのような「イベント」による「変化」はREDOログに書き、その更新された「状態」をテーブルに反映していくというのが
Kazuho's Weblog: 「技術的負債」は避けるべき？ - 割引率を使って考えてみた
「技術的負債」をコントロールする定量評価手法への期待 からの続きです。 ソフトウェアサービス企業における技術責任者の最も重要な仕事のひとつが、エンジニアリングの効率化です。そのためには、サービスの初期開発コストだけでなく、運用コストを織り込んだ上で正しい技術的判断を行っていく必要があります。 「技術的負債」という言葉は、この運用コスト最適化の重要性を指摘する上で、とてもキャッチーなフレーズだと考えられます。しかし、「技術的負債」を産まないように、あるいは負債を早めに返していこうとすると、開発工数が大きくなってしまうという問題もあります。 初期開発コストと運用コストのバランス注1を、どのようにとっていけば良いのでしょう？ 同等の機能を提供する「ソフトA」と「ソフトB」を考えてみます。ソフトAは、初期開発工数が6だが、２年目以降の維持工数が毎年4かかるとします注2。ソフトBは、初期開発工数が1
なぜHTTPSはHTTPより速いのか
先週、httpvshttps.com というウェブサイトが公開されました。このウェブサイトでは、HTTP と HTTPS を用いてアクセスした場合のウェブページのダウンロード完了までにかかる時間の比較ができるのですが、多くの環境で HTTPS の方が HTTP よりも高速なことに驚きの声が上がっていました。 HTTP が TCP 上で平文を送受信するのに対し、HTTPS は TCP 上で TLS (SSL) という暗号化技術を用いて通信を行います。ならば、TLS のオーバーヘッドのぶん HTTPS のほうが遅いはずだ、という予測に反する結果になったのですから、驚くのも無理はありません。 実は、この結果にはからくりがありました。 Google Chrome、Mozilla Firefox、最近のSafari注1は、Google が開発した通信プロトコル「SPDY」に対応しており、HTTPS
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
