自作ライブラリの紹介

最近(といっても半年スパンぐらいですが)私が実装したライブラリをまとめつつ簡単に紹介しておきます。 shinnya/binpack バイナリと Scala の型を相互変換するためのライ

Survey: Linux New I/O Scheduler

https://lwn.net/Articles/720675/ Linux kernel 4.12 で入った新しい IO Scheduler について。 IO リクエストを発行する際に内部的に multiple queue(multiqueue API) を使う点が従来の scheduler と異なる。 記事にはベンチマークがないが、調べた

Reading: Impossibility of Distributed Consensu with One Faulty Process

主要な結論は、”No consensus protocol is totally correct in spite of one fault.” という有名なものです。 まず、用語を整理しておくと、 configuration consensus protocol を実行するシステムの内部状態。 run

Reading: AlphaSort

AlphaSort 概要 CPU cache-sensitive なソート方法について論じた論文。 内部的には (key-prefix, the pointer to a record) のタプルをキーにした QuickSort を使う。 何が新しいか cache locality を考慮に入れてソート方法を選択

東洋経済のGAFA特集を読んだ

社で論文の印刷をしている間ヒマだったから東洋経済のGAFAの特集の回を読んでいたが存外面白かった。 印象的だったのが日本企業へのインタビューで

DB Weekly 230

DB Weekly Issue 230: November 16, 2018 おもしろそうな記事が1つもありませんでした。終わり。

Reading: Rust RFC 2535

2535-or-patterns - のメモ。 Summary パターンマッチ内で任意にネストした形式で |(or pattern) を使えるようにする。 記法は Some(A(0) | B(1 | 2)) のようになる。 以前は Some(A(0)) | Some(B(1)) | Some(B(2)) のように書かなけ

Purely Functional Data Structures の遅延評価の記法

Purely Functional Data Structures の遅延評価の記法を紹介し、それと等価な OCaml のコードを説明します。 遅延評価 遅延評価(ここではメモ化付きの遅延評価を指します)は必要になる

DB Weekly 220-225

DB Weekly の 220 〜 225 で面白かった記事を紹介します。 Introducing HaloDB, a fast, embedded key-value… | Yahoo Engineering インデックス情報はメモリ上に持ち、データファイルには追記のみしていく系の embedded KVS da

Reading: Epidemic Broadcast Trees

1. Introduction tree-based and gossip based primitives. メッセージの伝送に unreliable IP multicast を使う。欠点として IP-multicast に依存していること、2 つの異なる protocol が必要で複雑であること。 この論文で説明するのは、

Reading: Ceph: A Scalable, High-Performance Distributed File System

1. Introduction Ceph は peta-byte スケールに対応するための file system(と Object Storage) Object Storage Device(OSD), Metadata Server(MDS)があって、クライアントは中央集権的な MDS とやり取りした後

Reading: HyParView: A Membership Protocol for Reliable Gossip-Based Broadcast

HyParView を読んだのでメモ。 前提 transport protocol は信頼できるものが必要。 failure detector には TCP を使う。 well known server から contact node を教えてもらえる必要がある。 well known server の詳細はこの論文では説

Reading: In Search of an Understandable Consensus Algorithm(Raft)

In Search of an Understandable Consensus Algorithm を読んだのでざっくりとメモ。 Paxos のよくなかった点 アルゴリズムに曖昧な部分がある。 Lamport が論文で説明しているのは single-decree なアルゴリズムで、m

A note on Lamport Logical Clock

Lamport の論理クロックのメモ。 プロセス P1, P2 において、イベントを a, b として C(a), C(b) をプロセスのローカルな論理時間を, X -> Y と X < Y をイベントの順序を表現

MPSC Queue in C

Non-intrusive MPSC node-based queue 上記 URL は multi producers and single consumer 向けの queue の実装で、akka の actor の実装でもこのアルゴリズムが利用されています1。この queue の良い点は記事内で説明されてい

Day-Stout-Warren algorithm

Day-Stout-Warren algorithm このアルゴリズムを使うと木を balance させるタイミングを制御できるので、何か特殊用途に使えるんじゃないかと思って実装してみることに。C++ だと以

私がいかにして履歴書・職務経歴書を書いているか

MS Word なんて持ってねーよという Linux Desktop ユーザーのために、私が履歴書と職務経歴書を作成している方法をざっくり説明します。私の git リポジトリを公開できれ

lualatex の Number too big エラーを解決する

この記事を書いている時点の Arch Linux 上で pandoc + lualatex で markdown から pdf を生成する時にエラーが出て pdf の生成に失敗します。 問題の詳細は下記ブログで説明されているので

GitHub 上に elpa の package archive を立てる

SATySFi 用の major mode である satysfi.el のパッケージを作成するのを例にして手順を説明します。上から順に実行していってください。 GitHub にリポジトリを作成する 名前は何でも

union と Placement new で ADT を定義する

C++ には Placement new という機能があって、簡単に言えば、事前に確保されているメモリ領域に新たに生成されたオブジェクトを埋め込む機能です。私は Placement New の使い道

RITUEL(リチュエル) でおすすめのパン

表参道に RITUEL 青山 というパン屋があって、本店がフランスにある店の日本支店です。クロワッサンとエスカルゴというクロワッサンの一種が大変有名です。2

Windows Safe fsync in Java

Java fsync Directory の続き。 FileChannel.force は API としてぶっ壊れており、Windows ではディレクトリに対して force を呼ぶと例外が投げられるため(厳密に言えば、この挙動は implementation defined

Quicksort Revisited

転職活動のコーディングインタビューに備えてクイックソートを勉強し直していました。 それで、クイックソートなんて実装することはまずないだろうと思

Invariant Functor Pattern

圏論に Invariant Functor という概念があります。 ざっくりとプログラミングの概念で表現すると、Invariant Functor は、型コンストラクタ F、任意の型 A, B があった

libstfl.so.0 exists in filesystem on upgrading Arch Linux

When you upgrade your arch linux using pacman, you might see the following error: $ sudo pacman -Syu (Abbreviated) stfl: /usr/lib/libstfl.so.0 exists in filesystem` The message means that /usr/lib/libstfl.so.0 was created by some reason and it isn’t managed by pacman. Ok…, but how can we confirm that? Run the following command: $ sudo pacman -Qo /usr/lib/libstfl.so.0 The result of the above command should be like this if libstfl.so.0 is owned by pacman:

Create a new file if and only if not exists in Java

今まで Java で「ファイルがなかった時だけ作成する」をやる正しい方法がイマイチよく分かっていなかったのですが、 File.createNewFile() Files.createFile() で FileAlreadyExistsException をキャッチし無視する のいずれ

Java fsync Directory

ファイルに対して書き込みをした際に durability を保証するために fsync を呼ぶわけですが、fsync は基本的には(少なくとも ext4 をファイルシステムに使っている場

Reading: Space/Time Trade-offs in Hash Coding with Allowable Errors

Space/time trade-offs in hash coding with allowable errors 概要 新しい hash conding の手法(つまり Bloom Filter のこと)は以下に特徴がある。 reject time and space (判定速度とメモリ空間効率が高い) 誤りを許容する (第一種

Modulo Multiplication

たまに大きな数同士のかけ算をオーバーフローさせずに計算し、その modulo が取りたい時があります。 多倍長演算を実装すればいいわけですが、大変面倒なので

Knuth's multiplicative Hashing Method

Knuth 先生の The Art of Computer Programming の Volume 3 に、multiplicative hashing method が説明されています。C++ で書くと以下のコードになります。 #include <cstdio>#include <cinttypes>#include <unordered_map> std::uint32_t hashOf(std::uint32_t x) { // 2654435769 is

CRC32 Implementation

CRC32 値の計算で除数に 0x4C11DB7、生成多項式に $$ x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1 $$ を使うのが性能が良いらしい。

Reading: A Fast, Minimal Memory, Consistent Hash Algorithm

pdf Consistent Hashing の嬉しくない点 storage 用途で使う場合は各 bucket がデータの shared を表しているので、任意の bucket の追加と削除で shard が消えると困る。 Consistent Hashing と比べて嬉しい点 各 hash bucket に

個人で ACM Membership を得ることについて

論文を読む人はそれだけで入る価値がありますが、それ以外の特典は微妙です。 良い点 いちいち論文を DL できるかどうか探さなくて済むようになるので楽。

Type inference algorithm described in Modern Compiler Implementation in ML

Modern Compiler Implementation in ML で説明されている algorithm を実装したので、参考にしてください。 ocaml-typeinference

Reading: Stanford CS166 van Emde Boas Trees

CS166: DataStructures の van Emde Boas Trees を読みました。 Ordered Dictionaries(以下 OD = Ordered Dictionary) insert(x), is-empty(), lookup(x), delete(x), max(), min(), successor(x), predecessor(x) をサポートするデータ構造 BST は上記の操作をすべてサポートし

Reading: Stanford CS166 Cuckoo Hashing

CS166: DataStructures の Cuckoo Hashing を読みました。 Cuckoo Hashing lookup は worst-case で O(1) delete は worst-case で O(1) insert は amortized, expected で O(1) (高確率で実現可能) hash table の cuckoo graph が complex(後述) になる場合は hashing に失敗する。

Reading: Stanford CS166 Disjoint Set Forest

CS166: DataStructures を読んだのでメモ。 Disjoint Set Forest というのは、いわゆる Union Find の話です。 dynamic connectivity にどう対処するか? Euler tour trees は forests で解決した。 今回は incremental に connectivity が追加される問題につい

Computational Theory Definitions

Computational theory の記号とその定義をよく忘れてしまうのでメモ。 用語 Ω 関数の下界を表す。 ある関数 T(n) と関数 f(n) に対して $T(n) = Ω(f(n)) \iff ある定数 c, n_0$ が存在して

Reading: Performance in Practice of String Hashing Functions

Performance in Practice of String Hashing Functions は boost の hash function を決める際の根拠となっている論文みたいなので読んでみました。 Conclusions shift-add-xor string hashing functions の class から hashing function をランダムに選ぶと、analyti

Reading Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems

TL;DR Event-Driven から coroutine ベースの実装にするとメモリーオーバーヘッドが下がって、コードも短かく書ける。 以下論文の内容です。 Abstract Event-Driven programming でメモリオーバーヘッドは下が

ocaml-text-rope has been published!

OCaml で実装した Rope を公開しました。 フィードバックなどあればよろしくお願いします。 ocaml-text-rope 後で opam にも publish します。 今回実装した Rope は Ropes: an Alternative to Strings で説明されている

Hash function of std::vector<std::string> for std::unordered_map

C++ で std::unordered_map のキーに自作クラスを与えるには std::hash 関数の特殊化をする必要があります。 本稿では std::vector<std::string> を内部で保持しているクラスの hash function の作り方について説明します

Using ulex and menhir with OMake

OMake で ulex と menhir を使う方法についてメモ。 ocamllex ではなく ulex を使うモチベーションですが、ocamllex では utf8 なファイルを扱えないので他の lexer が必要だからで

Getting Started with PolyML

PolyML でコンパイルする方法が結構ややこしいのでメモを残しておきます。 (いきなり複数ディレクトリが存在する複雑な例で説明しますが、現実的には 1 つの

scala.io.Source.fromURI is broken

Scala で雑にファイルを読みたい時にたまに scala.io.Source を使いたくなる時があるかと思いますが、scala.io.Source.fromURI の使い方には注意が

Write a file correctly with ext4

ext4 で atomicity を保証してファイルに正しく書き込む方法について説明します。 だいたい Don’t fear the fsync! を読めば理解できるので英語を読みたい人はこっちを読ん

特異値分解の別形式

Wikipedia には載っていない特異値分解の別形式について以下にまとめておく。 $R$ を実数体として、行列 $A\in Mm,n®$ のランクを $r$ とすると、$A$ の SVD は以下のように定義

Debugging PostgreSQL with GDB

PostgreSQL の install から gdb での debug をできる環境の作り方までを紹介します。 まずは PostgreSQL を git から clone してきます。 git clone git://github.com/postgres/postgres.git 次に configure から make install までします。この時に debug 用のオプショ

jumplist for ctrlp.vim

https://github.com/shinnya/ctrlp-jumplist I was sick of the frequent upgrade of vimfiler and unite.vim, so I switched to ctrlp.vim and nerdtree a while ago. Then I wrote the new plugin for ctrlp.vim, which provides the functionality to open jumplist in ctrlp.vim. Let’s try it if you have an interest.

The abstraction layer of I/O in PostgreSQL

PostgreSQL の Stable Storage への IO は VFS と似たような手法で struct f_smgr として抽象化されていて、見たところ magnetic disk への実装しか登録されていませんが複数の実装を登録できるようにな

A performance benchmark of Couchbase on EC2

Environment benchmark01 - benchmark07, c4.large(client), m4.xlarge(couchbase), 8GB gp2 24 IOPS benchmark08 - benchmark22, c4.4xlarge(client), m4.xlarge(couchbase), 8GB gp2 24 IOPS + 100GB gp2 300 IOPS(for data storage) How to setup couchbase servers sudo su - echo 0 > /proc/sys/vm/swappiness cp -p /etc/sysctl.conf /etc/sysctl.conf.`date +%Y%m%d-%H:%M` echo '' >> /etc/sysctl.conf echo '#Set swappiness to 0 to avoid swapping' >> /etc/sysctl.conf echo 'vm.swappiness = 0' >> /etc/sysctl.conf echo never > /sys/kernel/mm/transparent_hugepage/enabled echo never > /sys/kernel/mm/transparent_hugepage/defrag cp -p /etc/rc.

Recommended resources for learning Haskell

Haskell の基本的な文法は知っている前提です。 http://book.realworldhaskell.org/ 今さら紹介の必要もないでしょうが…。この本で基本的なプログラミングスキルを学べます。Web 上に溢れる

Installing a set of packages of development tools with yum

yum groupinstall 'Development Tools' yum provides the functionality to install a group of packages. To install packages for developing software tools by yum, give ‘Development Tools’ to yum groupinstall, which includes many packages like make, git, subversion, and so on.

RE: PHP のトレイトに気を付ける

PHP のトレイトに気を付ける というエントリを読みました。Scala では self-type annotation により依存関係を明示できるが、PHP ではそれができないので暗黙の依存関

Build ICU for iOS using cmake

ICU を iOS 向けにビルドする方法について説明します。 https://github.com/zhm/icu-ios というリポジトリに armv7 や x86_64 向けの universal binary を生成するスクリプトと icu のソースコードが付属しているので、

An algorithm of pattern match compiler

main :: IO () main = print $ match 0 us qs Error where us = [makeVar 2, makeVar 3] qs = [ ([PCon "Nil" [], PVar "ys"], (App (App (Var "A") (Var "u1")) (Var "ys"))) , ([PVar "xs", PCon "Nil" [] ], (App (App (Var "B") (Var "u1")) (Var "xs"))) , ( [ PCon "Cons" [ PVar "x", PVar "xs" ], PCon "Cons" [ PVar "y", PVar "ys"] ], (App (App (App (App (App (Var "C") (Var "u1")) (Var "x")) (Var "xs")) (Var "y")) (Var "ys")) ) ] type Name = String type Constructor = String data Expr = Var Name | App Expr Expr | Case Name [Clause] | Fatbar Expr Expr | Error deriving (Show) data Clause = Clause Constructor [Name] Expr deriving (Show) data Pattern = PVar Name | PCon Name [Pattern] deriving (Show) type Equation = ([Pattern], Expr) arity :: Constructor -> Int arity c = case c of "Cons" -> 2 "Nil" -> 0 _ -> 0 constructors :: Constructor -> [Constructor] constructors c = case c of "Cons" -> ["Cons", "Nil"] "Nil" -> ["Cons", "Nil"] _ -> [] subst :: Expr -> Name -> Name -> Expr subst e@(Var n) before after = if n == before then Var after else Var n subst (App e1 e2) before after = App (subst e1 before after) (subst e2 before after) subst (Fatbar e1 e2) before after = Fatbar (subst e1 before after) (subst e2 before after) subst (Case var clauses) before after = Case var (map (\c -> substClause c before after) clauses) substClause :: Clause -> Name -> Name -> Clause substClause (Clause c us e) before after = Clause c us (subst e before after) isPVar :: Equation -> Bool isPVar (PVar _: _, _) = True isPVar _ = False isPCon :: Equation -> Bool isPCon q = not $ isPVar q getCon :: Equation -> Constructor getCon (PCon c _ : _, _) = c getCon _ = "" makeVar :: Int -> Name makeVar i = "_u" ++ show i partition :: Eq b => (a -> b) -> [a] -> [[a]] partition _ [] = [] partition _ [x] = [[x]] partition f (x:x':xs) | f x == f x' = tack x (partition f (x':xs)) | otherwise = [x] : partition f (x':xs) tack :: a -> [[a]] -> [[a]] tack x xss = (x : head xss) : tail xss match :: Int -> [Name] -> [Equation] -> Expr -> Expr match _ [] qs def = foldr Fatbar def [e | ([], e) <- qs] match k (u:us) qs def = foldr (matchVarCon k (u:us)) def (partition isPVar qs) matchVarCon :: Int -> [Name] -> [Equation] -> Expr -> Expr matchVarCon k us qs def | isPVar (head qs) = matchVar k us qs def | isPCon (head qs) = matchCon k us qs def matchVar :: Int -> [Name] -> [Equation] -> Expr -> Expr matchVar k (u:us) qs def = match k us [(ps, subst e v u) | (PVar v : ps, e) <- qs ] def matchCon :: Int -> [Name] -> [Equation] -> Expr -> Expr matchCon k (u:us) qs def = Case u [matchClause c k (u:us) (choose c qs) def | c <- cs ] where cs = constructors (getCon (head qs)) matchClause :: Constructor -> Int -> [Name] -> [Equation] -> Expr -> Clause matchClause c k (u:us) qs def = Clause c us' (match (k' + k) (us' ++ us) [(ps' ++ ps, e) | (PCon c ps' : ps, e) <- qs ] def) where k' = arity c us' = [makeVar (i + k) | i <- [1.

Convert a nullable value to Option

あまり知られていないようですが、Scala では null を Option を使うことで上手く扱うことができます。 Option(maybeNull) match { case Some(value) => // when the value is not null case None => // when the value is null } 上記

about

Hi, I’m Shinya Yamaoka. I’m an software engineer and currently live in Tokyo. I was born and grew up in Japan and have learned computer programming from 2009. I’m interested in database, distributed systems, compiler and functional programming. For recruiters, you can find my resume on LinkedIn.