タイトルの通り、マルチプロセスで使用可能なロックフリーのFIFOキューを実装したので、その簡単な紹介。 作成物 github: ipc-msgque (0.0.4) ロックフリーなFIFOキュー 再入可能 かつ SIGKILLに対して安全*1 C++ 共有メモリ(mmap)を使用 マルチプロセス(and…

以前に載せたマージソート(をベースとしたもの)をSBCL(1.0.58)にコミットしてくれたPaul Khuongさんが、こんな記事を書いていて、なるほどなー、と思ったので、表題に関係する部分を参考にさせて貰って変更前後での比較を行ったメモ。 オリジナルのマージソ…

compare-and-swap操作を用いたロックフリーなキューの実装。 SBCLでのみ動作*1。 (defpackage lock-free-queue (:use :common-lisp) (:export queue make enq deq empty-p element-count to-list)) (in-package :lock-free-queue) ;; compare-and-swap: 成功…

結論: デッドロックになってしまう 自動的にロックを解放してくれたりはしないみたい。 以下、試した内容のメモ書き。 環境 $ cat /proc/version Linux version 3.0.0-23-generic (buildd@komainu) (gcc version 4.6.1 (Ubuntu/Linaro 4.6.1-9ubuntu3) ) #38…

loop*1を使って、エラトステネスの篩を実装してみたメモ。 以下、処理系にはSBCLのver1.0.54(x86-64bit)を使用。 ;; 引数nまでの範囲の素数のシーケンス(ジェネレータ)を作成する (declaim (inline make-prime-sequence)) (defun make-prime-sequence (n) (l…

前回の続き。 githubにあるloopの簡易版を載せておく。 基本的な考え方 基本的なJava等のIteratorと似た*1インタフェースを通してループ処理を実現している。 異なるのは全ての関数をinline展開可能にすることで、同等のループを非関数型的に書いた場合と同…

今週は、common lispでループ処理を関数型っぽく、かつ効率良く実装できるかどうかを試していたので、その結果を載せておく。 結論から云えば、処理系の十分な最適化を期待できれば、関数型っぽく書いても、手続き型的に書いた場合と比肩しえる性能が得られ…

逆FizzBuzz問題 (Inverse FizzBuzz)というものがあるのを知ったので解いてみた。 結構力技。 あと、本当に合っているかは不明。 ;; 逆FizzBuzzを解く関数 ;; listは fizz,buzz,fizzbuzz のいずれかを要素に持つリスト ;; ;; 処理内容は、 ;; - 1: 開始数値を…

ここ数日はScalaのコップ本を読んでいて、何かまとまったプログラムをScalaで書いてみたくなったのでGomoku(Java形態素解析器。ver0.0.6)をScalaで実装してみた*1。 ・github: scala-gomoku(ver0.0.1)以下、使用例とJava版/Scala版の簡単な比較メモ。 使用例…

前々々回でスタック型言語をバイトコードにコンパイルする部分を、前々回でCommonLispアセンブラによるマシン語生成を、前回でそのアセンブラ上にスタック型言語のラップするところを扱った。 今回はそれらをまとめて、最初に作成したバイトコードインタプリ…

前回のCommonLispアセンブラを使って、アセンブラ上に簡単なスタック型言語(っぽいもの)を組み立てて、それを使ってフィボナッチ数を計算するプログラムを書くと、どのような感じになるかを試してみた。 cl-asmはバージョンを更新して0.0.2を使用*1。 0.0.1(…

前回は、C++で単純なVMを書いて、その上でのフィボナッチ数の計算時間を測定した。 そのVM部分をネイティブコードに置き換えたら、どの程度処理速度が改善するのかを測ってみたかったので、その前にまずネイティブコード(x86)の勉強も兼ねて、common lispで…

今年はlisp系のプログラミング言語(及びその処理系)を作ってみようと考えていて、かつ(少なくとも)当面の間はスタック型VMを基盤として実装していくことになると思われるので、まずは単純なスタックマシンのバイトコードインタプリタで、どの程度の処理速度…

CommonLispのfletとlabels的なものを(あらかじめ使えるものはlambdaしかない状況で)自分で実装する必要が出てきたので、その際のメモ。 なお、以下では煩雑になるためfuncall呼び出しの記述を省略している(実際にはScheme処理系で動作確認を行っていた)。 le…

端末上で動作するマインスイーパーをCommonLisp(SBCL)で実装してみた。 github: cl-mine-0.0.2 端末操作 端末操作部分のソースコードは以下のような感じ。 基本的には端末のエスケープシーケンスで(カーソル移動や画面クリア、文字色等の)制御を行っている。…

こちらの記事に刺激を受けて、以前に実装したN-Queenを高速化してみた(Common Lisp版のみ)。 (defvar *fastest* '(optimize (speed 3) (safety 0) (debug 0) (compilation-speed 0))) (deftype max-board-size () '(mod #x100)) (declaim (inline check)) ; …

少し必要になったのでErlangでユニコード文字列と各種エンコーディングのマルチバイト列(バイナリ)の相互変換を行うモジュールを作成した。 github: erl-creole-0.0.1 現状、対応しているエンコーディングは以下の通り*1: UTF-8, Shift_JIS, CP932, EUC-JP, …