読者です 読者をやめる 読者になる 読者になる

sbcl

RustとSBCLでのDAWG構築性能の比較メモ

Rustの勉強を兼ねて、cl-dawgというDAWGのCommon Lisp実装を移植して、rust-dawgというライブラリを作ってみた。 (DAWGは末尾部分を共有可能にしたトライの亜種。上記ライブラリでは、そのトライ木をDoubleArray形式で表現している。DAWGやDoubleArrayの構築…

ソート済みのリストに対する破壊的マージソートの改良

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

Lock-Free Queue

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: 成功…

エラトステネスの篩

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

簡易スタック型VM(JITコンパイラもどき)でのフィボナッチ数計算速度

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

CommonLispアセンブラ上にスタック型言語(っぽいもの)

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

マインスイーパー

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

=関数よりもeql関数の方が速かった(間接呼び出し時)

以下、sbcl-1.0.51-x86-64-linuxでの実行結果。 ;; 計時用関数 (defun compare-time (fn nums1 nums2) (declare (optimize (speed 3) (safety 0) (debug 0)) (function fn)) (time (loop FOR n1 fixnum IN nums1 FOR n2 fixnum IN nums2 WHEN (funcall fn n1…

Cの定数値や型のサイズを取得するための関数

sb-alienパッケージとかを使ってネイティブライブラリを使用していると、ちょくちょくCの定数の値や型の定義(型のサイズ)を知りたくなることがある。 毎回ヘッダファイルを調べるのも面倒なので、lisp上から取得出来るように関数を用意してみた。 (defun c-i…

再帰関数(ハノイの塔)にinline宣言をつけたら・・・

Forthでハノイの塔 - sileの日記でハノイの塔を解くcommon lispプログラムを載せたら「inline宣言を付けるともっと早くなりますよ」というコメントを頂いたので試してみた。 inline宣言付与結果 再帰関数をinline展開する際の深さはsb-ext:*inline-expansion…

簡易的なカウントダウンラッチ

後々使いたいので、簡単なカウントダウンラッチを作成してみた。 ウェイトは単純なスピンで実装しているのであまり実用的ではないけど、お試し用途であれば十分(だと思う)。 (defpackage countdown-latch (:use :common-lisp) (:export make countdown-and-a…

簡易スレッドID取得関数(+SBCLでのTLS)

実行中のスレッドがN個あるとして、そのそれぞれに0からN-1のID値を割り振る関数を作成した。 (defpackage thread-id (:use :common-lisp) (:shadow :common-lisp get) (:export get)) (in-package :thread-id) (define-symbol-macro *id* (tls:symbol-value…

SBCLの出力をパイプして使う場合の注意点

SBCLの出力をパイプして使う場合の注意点。 何も気にせずに書いていると大量のエラー情報が出力されて戸惑うことがある。 例として以下のSBCLスクリプトを用いる。 ;;;; ファイル名: loop.lisp ;;;; sbcl-1.0.48 (loop FOR n FROM 0 DO (format t "loop: ~a~…

SBCLのnon-blocking I/O

SBCLでnon-blocking I/Oを使いたくなったので少し調べてみた。serve-eventというものが利用可能らしい。 SBCL自体のマニュアルにはこれに関数詳しい説明はなく、CMUCLのドキュメント(CMUCL User's Manual: Event Dispatching with SERVE-EVENT)を参照する必…

SBCLで配列に対するsxhash関数呼び出しが常に同じ値を返す

sbcl(1.0.43)では、配列に対するsxhash関数は常に同じ値を返すようだ。 ;;;; sbcl-1.0.43 ;; 一次元配列 (sxhash #()) --> 518591303 (sxhash #(a 10 "sbcl")) --> 518591303 (sxhash (make-array 10 :adjustable t :fill-pointer 3)) --> 518591303 (sxhash…

DAWG2(3): cl-dawg

いろいろ途中経過を省いてDAWGシリーズ(?)の最後。 common lisp用のライブラリにまとめました、という話。 ・cl-dawg-0.1.0 概要 DAWGのcommon lisp実装 ただしSBCL依存 DAWG構築時に利用しているハッシューテーブルでSBCLの拡張機能を使っているため 静的に…

DAWG2(2.5): DAWG構築時のハッシュ値用の領域節約

前回にソート済みファイルからDAWGを構築する際には、個々のノードのハッシュ値をO(1)で(簡単に)算出可能にするために、ノードにハッシュ値用のフィールドを持たせていた。 ;;;; 再掲 ;; DAWGのノード用の構造体 (defstruct node (label 0 :type octet) (sib…

DAWG2(2): ソート済みファイルからのDAWG構築

前回はトライだったけど、今回はDAWGを構築。 Nをキーセットに含まれる文字の総数*1だとして、DAWGはトライと同様にO(N)で構築可能(多分間違っていないはず...)。 ただし、子ノード(サブトライ)が共有可能かどうかの判定が入るので、実際には一桁程度遅くな…

DAWG2(1): ソート済みファイルからのトライ構築

七月にやっていたDAWG(Direct Acyclic Word Graph)シリーズ(?)の続き。 結構長い間中断していて自分でも内容がうろ覚えなので、仕切り直してもう一度。 今回はDAWGの前段階として、ソート済み(かつ各行がユニーク)なファイルからトライを構築する。 DAWG 軽…

構造体のスタックへの割り当て

SBCLのマニュアル(ver 1.0.37)にも書いてあることだけど ... 。 通常は構造体のインスタンスを作成するとヒープ上にそのための領域が割り当てられる。 これには(おそらく)ヒープ割り当て+GC処理のコストが伴うので、構造体としてまとめるよりも、その各フィ…

行をバイト列として読み込む

テキストファイルの各行をバイト列として読み込むマクロを定義。 SBCL等のように文字列を内部的にユニコードとして表現している処理系では、テキストファイルを読み込む際、そのファイルが不正なバイト列を含んでいると読み込みに失敗することがあるので、そ…

UNF: Common Lisp版

しばらく(私的には)プログラミングから離れた生活が続いていたので、肩慣らしを兼ねてUNF(Unicode正規化ライブラリ)のcommon lisp版(cl-unf)を作成。いつものようにSBCLで作成し、SBCL向けに最適化されているが、UTF-32に対応しているなら、他の処理系でも一…

簡易外部リンククローラ

あるサイトからの外部リンク一覧を取得する簡単なクローラ(もどき)をsbclで作成。 ;;;; sbcl-1.0.37 (require :puri) ; ver1.5.1 (require :drakma) ; ver1.0.0: HTTPクライアント (require :cl-ppcre) ; ver2.0.1: 正規表現 (require :sb-queue) ; A thread…

引数の型チェックの有無を使用者に選択させる(sbcl)

関数を書いていると、引数の型チェックを有効にするかどうかで悩むことがたまにある。 ;;;; sbcl-1.0.37 ;; 足し算を行う関数 ;; 引数が適切な前提としている (defun plus-impl (x y) (declare ((integer 0 1000) x y) (optimize (speed 3) (safety 0))) (+ …

sbclで文字列を効率的に扱う場合の型

あまり話題に関連性がないが、一応前々回の続き。 sbcl(1.0.37)での文字列関連の型の階層は以下のようになっている*1。 僕は最近までsimple-string型*2が文字列関連型の最下層だと思い込んでいたので、文字列を扱う部分のプログラムを高速化したい場合、(dec…

コンパイルすると何故か異様にファイルサイズが大きくなる関数

表題の通り。 ;; sbcl-1.0.28, sbcl-1.0.37 ;; ファイル名: huge.lisp (defun decode-surrogate-pair (high low) (code-char (+ #x10000 (ash (ldb (byte 10 0) high) 10) (ash (ldb (byte 10 0) low) 00)))) $ sbcl * (compile-file "huge") * (quit) $ ls …

マルチバイト文字列→ユニコード文字列

DoubleArray(トライの一種)を利用して、マルチバイト文字列をユニコード文字列にある程度自動的に変換する、という試み(?)。 ちゃんとした形に整理するほどの気力はないので、一応動く程度のソースコードと覚え書きを残しておくことにする。 やること&概要 …

maphash-to-list

common lispではハッシュが使い難い(と思う)。 その理由の一つは、リストのようにマッピング関数がない*1せいだと思うので、そのための関数を定義。 ユーティリティ関数っぽくいろいろ装飾。 ※ 宣言はsbcl(1.0.37)用に特化 (declaim (inline maphash-to-list…

:a

;; sbcl-1.0.37, clisp-2.42, ClozureCL-1.4 > *print-case* > :UPCASE > :a > :A > :a > :A > 'abcdè > ABCDÈ さすがユニコード対応。

Igo : sbcl-1.0.28, sbcl-1.0.37

以前、計時を行った条件に合わせてcommon lisp版のIgo(0.2.3)をsbclのバージョン1.0.28で動かしてみたところ、処理を終えるまでに92.712秒かかった。 sbclのバージョンを1.0.37に替え、それ以外は同様の条件で試してみたところ、こちらは33.962秒で終了。 3…

make-sequenceとmake-array

sbcl-1.0.34での話。 make-sequence関数はmake-array関数よりも特殊化されているので、より高速なのかと思っていたら、そうではなかった。 ;; make-array関数 > (time (loop repeat 1000000 sum (length (make-array 1000 :initial-element 0)))) Evaluation…

errno文字列表現取得関数

sbclを使って、errnoの値に対応するメッセージを簡単に取得する方法。 sb-int:strerror関数を使う。 ;; errno=22の場合 > (sb-int:strerror 22) --> "Invalid argument" ;; errno=2の場合 > (sb-int:strerror 2) --> "No such file or directory"

llvm : tutorial : jit

チュートリアル第四章『4. Kaleidoscope: Adding JIT and Optimizer Support — LLVM 3.4 documentation』の2。タイトルにはJITとあるが、僕のこれまでの進め方ではチュートリアル通りのJITは実現できないので、似たような動作をする方法でごまかす。 実装 …

llvm : tutorial : optimize

チュートリアル第四章『4. Kaleidoscope: Adding JIT and Optimizer Support — LLVM 3.4 documentation』。 タイトルの通り、ここではJIT(を用いたRead-Eval-Print-Loop)とoptimizeがKaleidoscopeに加わっている。 前者は少しやっかいなので、分割して今回は…

一文字マクロ文字

パターンマッチがある関数型言語でよく見かける_変数*1をsbclでも使えないかと少し試してみた。 結局満足出来る結果は得られなかったが、作成したものの一部をメモして残しておく。 ;; 以下は、マクロ文字候補文字xが ;; シンボル名の一部として解釈できない…

sbcl, apache, cgi, エラー

sbclでCGIスクリプト(#!/usr/local/bin/sbcl --script)を作成して、Apacheのもとで動かしてみようとしたら、失敗した。 OSはCentOS 5。 rubyやperlで作成したCGIは普通に動く。 Apacheのエラーログには次のような出力がはかれていた。 [Wed Jan 20 03:30:01 …

ftype型宣言(sbcl) : 戻り値の型指定

前回と重複するところがあるが、ftype型宣言の有用な使い方について書いておく。 関数の戻り値の型指定 ftype型宣言を使うと、関数の戻り値の型を指定することができる。 これが何故有用かと云うと、sbclは関数の戻り値の型が指定されている場合、それに基づ…

BWT : bzip2 : 修正版

前回書いたBWT関数はかなり非効率だったので、その修正版を作成した。 修正点は主に以下の三つ。 対象を文字列からバイト列に変更 列のローテートは実際には行わない。代わりに、各列の先頭位置を保持する変数を用意し、その値をずらすことで循環列を表現す…

ftype型宣言(sbcl)

ftype型宣言。 あまり使われているのを見ない気がするが、これを使うと「型宣言なしでは遅いけど、宣言をつけるとコードが汚くなる」というような問題を解決できる時があるので、少し書いておく。以下はsbcl(1.0.34)での挙動。 準備 ;; 処理速度を最優先 (de…

sbclでのmkstr実装(or 文字列出力)注意点

『On Lisp』のmkstrの話。オリジナルの実装はこれ。 ;; 引用: http://www.komaba.utmc.or.jp/~flatline/onlispjhtml/utilityFunctions.html (defun mkstr (&rest args) (with-output-to-string (s) (dolist (a args) (princ a s)))) この実装は、sbcl(1.0.34…

文字列変換C++関数自動生成

仕事柄(かどうかは分からないが)switch分岐を多用したCやC++の文字列(群?)変換関数を書く機会がたまにある。 例えば最近では、Shift_JISの全角文字(カタカナ+記号)を半角文字に変換するCの関数を作成した(このRuby拡張ライブラリの中で使われている関数)。 …

バイト列→文字列変換ライブラリ(sbcl)

前回の知見(文字コード変換関数をC++で用意する云々)を反映して、FFIを利用した、バイト列を文字列に変換するsbclのライブラリを作成した。 ・unsafe-conv(0.0.1) 対応している文字コードは、UTF-8、Shift_JIS、EUC-JPの三つ。UTF-8以外のC++の変換関数につ…

UTF-8: バイト列→文字列変換(C++&FFI版)

昨日作成したutf8-octets-to-string関数をclispでも試してみた。 ;;;; データ準備 ;; ファイルをバイト列として読み込む (defun read-octets-file (path) (with-open-file (in path :element-type '(unsigned-byte 8)) (let ((as (make-array (file-length i…

UTF-8: バイト列→文字列変換

前々回に作成したURLデコード用の関数では、sb-ext:octets-to-string関数が処理のボトルネックとなっていた。 確かsbcl(1.0.28)はバイト列から文字列への変換には、UTF-8でもShift-JISでもEUC-JP(及びその他)でも出来るような汎用的な方法(枠組み?)*1を採用…

URLエンコード/デコード

URLのエンコード/デコード処理は、時々必要になって、その度に(適当に)自作しているものの一つなので、今回少し真面目に作成してパッケージにまとめてみた。 仕様は『URLEncoder (Java Platform SE 6)』を参考にさせてもらった。 (defpackage :url (:use :co…

HTTPリクエスト並列化のボトルネック

今日(昨日?)は、HTTPリクエストを並列化して大量のURLからのデータ取得を高速化する、というようなことを試していた。 並列化 初めは単純に、個々のHTTPリクエスト(URL)を別々のスレッドで処理すれば、(イメージ的には)総処理時間もO(1)*1に近いものになるの…

リストのユニーク

sbcl(1.0.28)で文字列のリストのユニークな要素を取ろうとすると、やけに遅い。 リストの要素数は30万くらいなのだが、しばらく待ってもレスポンスがない。 > (length *word-list*) ; *word-list*は文字列のリスト --> 320000 ; この数は適当 > (time (remov…

リストのコピー(末尾に追加 vs push&nreverse)

sbclのソースを読んでいたら、次のようなコードを目にした。 ;;; sbcl-1.0.29/src/code/seq.lispのlist-remove-duplicates*関数からの抜粋 (let* ((result (list '())) (splice result) (current list)) ; listは引数で渡されたリスト #|...|# (do (#|...|#)…

Shift-JIS追加

sbcl(1.0.28)は、文字コード(external-format)に:shift-jisを指定することができない。 > (string-to-octets "あいうえお" :external-format :shift-jis) debugger invoked on a SIMPLE-ERROR in thread #<THREAD "initial thread" RUNNING {AB6E569}>: Unknown external-format :SHIFT-JIS ;; :shift_ji</thread>…

実行可能ファイル作成補助マクロ(sbcl)

sbcl(1.0.28)では、実行可能ファイルを作成することができる。 > (sb-ext:save-lisp-and-die "実行可能ファイル名" :toplevel #'エントリ関数 :executable t) エントリ関数には(必須引数の数が0個なら?)どのような関数でも指定可能なのだが、いろいろクセが…