sbcl
Rustの勉強を兼ねて、cl-dawgというDAWGのCommon Lisp実装を移植して、rust-dawgというライブラリを作ってみた。 (DAWGは末尾部分を共有可能にしたトライの亜種。上記ライブラリでは、そのトライ木をDoubleArray形式で表現している。DAWGやDoubleArrayの構築…
以前に載せたマージソート(をベースとしたもの)を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: 成功…
loop*1を使って、エラトステネスの篩を実装してみたメモ。 以下、処理系にはSBCLのver1.0.54(x86-64bit)を使用。 ;; 引数nまでの範囲の素数のシーケンス(ジェネレータ)を作成する (declaim (inline make-prime-sequence)) (defun make-prime-sequence (n) (l…
前々々回でスタック型言語をバイトコードにコンパイルする部分を、前々回でCommonLispアセンブラによるマシン語生成を、前回でそのアセンブラ上にスタック型言語のラップするところを扱った。 今回はそれらをまとめて、最初に作成したバイトコードインタプリ…
前回のCommonLispアセンブラを使って、アセンブラ上に簡単なスタック型言語(っぽいもの)を組み立てて、それを使ってフィボナッチ数を計算するプログラムを書くと、どのような感じになるかを試してみた。 cl-asmはバージョンを更新して0.0.2を使用*1。 0.0.1(…
端末上で動作するマインスイーパーをCommonLisp(SBCL)で実装してみた。 github: cl-mine-0.0.2 端末操作 端末操作部分のソースコードは以下のような感じ。 基本的には端末のエスケープシーケンスで(カーソル移動や画面クリア、文字色等の)制御を行っている。…
以下、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…
sb-alienパッケージとかを使ってネイティブライブラリを使用していると、ちょくちょくCの定数の値や型の定義(型のサイズ)を知りたくなることがある。 毎回ヘッダファイルを調べるのも面倒なので、lisp上から取得出来るように関数を用意してみた。 (defun c-i…
Forthでハノイの塔 - sileの日記でハノイの塔を解くcommon lispプログラムを載せたら「inline宣言を付けるともっと早くなりますよ」というコメントを頂いたので試してみた。 inline宣言付与結果 再帰関数をinline展開する際の深さはsb-ext:*inline-expansion…
後々使いたいので、簡単なカウントダウンラッチを作成してみた。 ウェイトは単純なスピンで実装しているのであまり実用的ではないけど、お試し用途であれば十分(だと思う)。 (defpackage countdown-latch (:use :common-lisp) (:export make countdown-and-a…
実行中のスレッドが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スクリプトを用いる。 ;;;; ファイル名: loop.lisp ;;;; sbcl-1.0.48 (loop FOR n FROM 0 DO (format t "loop: ~a~…
SBCLでnon-blocking I/Oを使いたくなったので少し調べてみた。serve-eventというものが利用可能らしい。 SBCL自体のマニュアルにはこれに関数詳しい説明はなく、CMUCLのドキュメント(CMUCL User's Manual: Event Dispatching with SERVE-EVENT)を参照する必…
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…
いろいろ途中経過を省いてDAWGシリーズ(?)の最後。 common lisp用のライブラリにまとめました、という話。 ・cl-dawg-0.1.0 概要 DAWGのcommon lisp実装 ただしSBCL依存 DAWG構築時に利用しているハッシューテーブルでSBCLの拡張機能を使っているため 静的に…
前回にソート済みファイルからDAWGを構築する際には、個々のノードのハッシュ値をO(1)で(簡単に)算出可能にするために、ノードにハッシュ値用のフィールドを持たせていた。 ;;;; 再掲 ;; DAWGのノード用の構造体 (defstruct node (label 0 :type octet) (sib…
前回はトライだったけど、今回はDAWGを構築。 Nをキーセットに含まれる文字の総数*1だとして、DAWGはトライと同様にO(N)で構築可能(多分間違っていないはず...)。 ただし、子ノード(サブトライ)が共有可能かどうかの判定が入るので、実際には一桁程度遅くな…
七月にやっていたDAWG(Direct Acyclic Word Graph)シリーズ(?)の続き。 結構長い間中断していて自分でも内容がうろ覚えなので、仕切り直してもう一度。 今回はDAWGの前段階として、ソート済み(かつ各行がユニーク)なファイルからトライを構築する。 DAWG 軽…
SBCLのマニュアル(ver 1.0.37)にも書いてあることだけど ... 。 通常は構造体のインスタンスを作成するとヒープ上にそのための領域が割り当てられる。 これには(おそらく)ヒープ割り当て＋GC処理のコストが伴うので、構造体としてまとめるよりも、その各フィ…
テキストファイルの各行をバイト列として読み込むマクロを定義。 SBCL等のように文字列を内部的にユニコードとして表現している処理系では、テキストファイルを読み込む際、そのファイルが不正なバイト列を含んでいると読み込みに失敗することがあるので、そ…
しばらく(私的には)プログラミングから離れた生活が続いていたので、肩慣らしを兼ねて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-1.0.37 ;; 足し算を行う関数 ;; 引数が適切な前提としている (defun plus-impl (x y) (declare ((integer 0 1000) x y) (optimize (speed 3) (safety 0))) (+ …
あまり話題に関連性がないが、一応前々回の続き。 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(トライの一種)を利用して、マルチバイト文字列をユニコード文字列にある程度自動的に変換する、という試み(?)。 ちゃんとした形に整理するほどの気力はないので、一応動く程度のソースコードと覚え書きを残しておくことにする。 やること＆概要 …
common lispではハッシュが使い難い(と思う)。 その理由の一つは、リストのようにマッピング関数がない*1せいだと思うので、そのための関数を定義。 ユーティリティ関数っぽくいろいろ装飾。 ※ 宣言はsbcl(1.0.37)用に特化 (declaim (inline maphash-to-list…
;; sbcl-1.0.37, clisp-2.42, ClozureCL-1.4 > *print-case* > :UPCASE > :a > :A > :ａ > :Ａ > 'ａbｃdè > ＡBＣDÈ さすがユニコード対応。
以前、計時を行った条件に合わせてcommon lisp版のIgo(0.2.3)をsbclのバージョン1.0.28で動かしてみたところ、処理を終えるまでに92.712秒かかった。 sbclのバージョンを1.0.37に替え、それ以外は同様の条件で試してみたところ、こちらは33.962秒で終了。 3…
