2025/12/14 3:56

Fast Sequence Iteration in Common Lisp

RSS: https://news.ycombinator.com/rss

要約▶

Japanese Translation:

要約

この記事では、Common Lisp の「シーケンス」がリンクリストまたはベクターのいずれかであり、本当のイテレータプロトコルを欠いているため、開発者は

elt+length+loop

や

reduce

といったアドホックなユーティリティに頼らざるを得ないと説明しています。
このギャップを埋めるために著者はマクロ do-sequence
を作成し、任意のシーケンスタイプを標準的なキーワード引数（

:start

、

:end

、

:key

）とオプションの

:with-index

および

:with-raw-elt

を使って反復処理します。マクロは

etypecase

によりリスト、シンプル配列、またはベクタータイプを分岐し、それぞれに効率的な

loop

フォームを生成します。

使用例として 2 つの関数が示されています：

```
max-elt-reduce
```
（
```
reduce
```
を使って実装）と
```
max-elt-do-seq
```
（新しいマクロを使用）。
次に、カスタムキュー構造で一致するすべての位置を収集するベンチマークとして
```
position-all-reduce
```
と
```
position-all-do‑seq
```
を比較し、類似した速度向上が得られることを示しています。

ベンチマークは AMD 5900X プロセッサと 64 GB DDR4 メモリ上で 6 種類の人気 Lisp 実装（SBCL、CCL、ECL、CLISP、および他の2つ）に対して実行されました。各テストは一貫した計測を確保するために完全なガベージコレクション (

measure

) で開始し、コードは

(speed 3) (safety 0) (debug 0)

の設定でコンパイルされました。

結果は

do-sequence

が常に

reduce

より高速であることを示しており、速度向上率は約 10 % から >100 % に及びます。特に SBCL 以外のシステムで顕著です。
著者はマクロが可読性と性能を改善する一方で、コードサイズとコンパイル時間を増加させる可能性があるため、インライン化はデッドコード除去（DCE）が未使用パスを削除しない限り避けるべきだと警告しています。

Lisp 開発者にとって

do-sequence

を採用するとシーケンス処理の速度と明確さが向上しますが、プロダクション環境ではマクロのオーバーヘッドを利益と比較検討する必要があります。

本文

はじめに & コード

Common Lisp のシーケンスに慣れていない方へ。
「シーケンス」とは、連結リストかベクターのどちらでもあるデータ構造で、
要素検索・比較・削除といった操作を 1 つのインタフェースで扱うことが目的です。

ANSI CL には実際にイテレータプロトコルがないため、シーケンスはその代替手段となります。
リストとベクターを同じコードで走査しつつ

:start

・

:end

・

:key

といった従来のキーワードをサポートすることは容易ではありません。
ANSI CL は次の 2 つの統一インタフェースを提供しています。

elt + length + loop
（または
```
do
```
）
```
iterate
```
の裏で動く、シンプルかつ直感的な手法。
reduce

キーワード全て（
```
:from-end
```
を含む）を自動的に処理し、実装が速いというメリットがあります。
ただし
```
reduce
```
はクロージャを何度も呼び出すオーバーヘッドがあるほか、
```
:key
```
を適用する前の「生要素」やインデックスへの直接アクセスができません。

アドベント・オブ・コードで最初に書いた単純な

max-elt

を

reduce

版に書き換える際、
繰り返し特殊化を避けるために次のようなマクロを作成しました。

(defmacro do-sequence ((var seq &key (start 0) end key with-index with-raw-elt)
                       &body body)
  "シーケンス上で通常のキーワード（:START, :END, :KEY）を利用して走査するマクロ。  
   :WITH-INDEX と :WITH-RAW-ELT は評価されないシンボルを受け取り、インデックスや生要素として使われます。  
   走査は `(LOOP ... :DO (LOCALLY ,@BODY))` を通じて行われるため、BODY 内では RETURN や宣言が使用できます。"
  (once-only (seq start end key)
    (macrolet ((impl (type has-key-p &optional has-end-p)
                 `(let ((ivar (or with-index (gensym "IDX")))
                        (rvar (cond (with-raw-elt     with-raw-elt)
                                    (,,(not has-key-p) var)
                                    (t                (gensym "RAW")))))
                    `(loop
                       ,@(ecase ,type
                           (list
                            `(:for ,ivar :of-type (integer 0 #.array-dimension-limit)
                              :from ,start ,@(when ,has-end-p `(:below ,end))
                              :for ,rvar :in (nthcdr ,start ,seq)))
                           (vector
                            `(:for ,ivar :of-type (integer 0 #.array-dimension-limit)
                              :from ,start :below (or ,end (length ,seq))
                              :for ,rvar := (aref ,seq ,ivar))))
                       ,@(cond (,has-key-p   `(:for ,var := (funcall ,key ,rvar)))
                               (with-raw-elt `(:for ,var := ,rvar)))
                       :do (locally ,@body)))))
      `(etypecase ,seq
         (list
          (cond ((and ,key ,end) ,(impl 'list t   t))
                (,key            ,(impl 'list t   nil))
                (,end            ,(impl 'list nil t))
                (t               ,(impl 'list nil nil))))
         ((simple-array * (*))           (if ,key
              ,(impl 'vector t)
              ,(impl 'vector nil)))
         (vector
          (if ,key
              ,(impl 'vector t)
              ,(impl 'vector nil)))))))```

ANSI CL には従っており、`once-only` は実質的に既定です。  
Zlib ライセンスの下でコピー可能です。

---

## ベンチマーク

以下は `max-elt` を `reduce` と `do-sequence` の両方で実装し、さまざまなシーケンス型（リスト・ベクター・配列）に対して大きいサイズで比較した結果です。  
インデックスと生要素が必要だったため、`:with-index` と `:with-raw-elt` を使用しています。

```lisp
(deftype index () `(integer 0 ,array-dimension-limit))
(deftype end   () '(or null index))
(deftype key   () '(or symbol (function (t) t) null))
(deftype test  () '(or symbol (function (t t) t)))

(declaim (ftype
          (function (sequence test &key (:start index) (:end end) (:key key))
                    (values t (or null index)))
          max-elt-reduce max-elt-do-seq))

(defun max-elt-reduce (seq pred &key (start 0) end key)
  (let ((i start) maxi max)
    (declare (type index i))
    (reduce
     (if key
         (lambda (kmax el)
           (incf i)
           (let ((kel (funcall key el)))
             (if (or (= i start) (funcall pred kel kmax))
                 (progn (setf maxi i max el) kel)
                 kmax)))
         (lambda (kmax el)
           (incf i)
           (if (or (= i start) (funcall pred el kmax))
               (progn (setf maxi i max el) el)
               kmax)))
     seq :start start :end end)
    (values max maxi)))

(defun max-elt-do-seq (seq pred &key (start 0) end key)
  (let (maxi rmax max)
    (do-sequence (el seq :start start :end end :key key
                     :with-index i :with-raw-elt r)
      (when (or (= i start) (funcall pred el max))
        (setf maxi i rmax r max el)))
    (values rmax maxi)))

(defconstant +len+ 5000000)

(let ((l   (make-sequence 'list   +len+ :initial-element 0))
      (sv  (make-sequence 'vector +len+ :initial-element 0))
      (fsv (make-array +len+ :element-type 'fixnum :initial-element 0))
      (fv  (make-array +len+ :element-type 'fixnum :initial-element 0
                       :adjustable t)))
  (format t "Test,~A~%" (lisp-implementation-type))
  (loop :for (args name) :in
        `(((,l   ,#'>) "LIST")
          ((,l   ,#'> :start 100 :end ,(- +len+ 100) :key ,#'1+) "LIST (fiddly)")
          ((,sv  ,#'>) "SIMPLE-VECTOR")
          ((,fsv ,#'>) "(SIMPLE-ARRAY FIXNUM)")
          ((,fv  ,#'>) "(VECTOR FIXNUM)"))
        :do (let ((tref (nth-value 1 (measure (apply #'max-elt-reduce args))))
                  (tnew (nth-value 1 (measure (apply #'max-elt-do-seq args)))))
              (format t "~A,~D → ~D (~@D%)~%"
                      name
                      (round (* tref 1000))
                      (round (* tnew 1000))
                      (round (* 100 (- (/ tref tnew) 1)))))))```

### 結果

| 実装 | LIST | LIST (fiddly) | SIMPLE‑VECTOR | SIMPLE‑ARRAY FIXNUM | VECTOR FIXNUM |
|------|------|---------------|--------------|---------------------|--------------|
| SBCL | 39 → 26 (+50%) | 124 → 64 (+93%) | 979 → 499 (+96%) | 372 → 251 (+48%) |
| CCL  | 46 → 39 (+18%) | 129 → 77 (+69%) | 1186 → 703 (+69%) | 450 → 408 (+10%) |
| ECL  | 44 → 32 (+38%) | 140 → 81 (+71%) | 966 → 600 (+61%) | 417 → 314 (+33%) |
| CLISP | 51 → 37 (+38%) | 177 → 121 (+46%) | 960 → 635 (+51%) | 422 → 331 (+27%) |

---

## 別のシンプルケース

マクロを別コンテキストで検証するため、`position-all` を実装します。  
これはシーケンス内にあるオブジェクトの **すべての位置** を収集します。

```lisp
(deftype queue () '(cons cons list))
(defun make-queue ()
  (let ((q (cons nil nil)))
    (setf (car q) q)
    q))

(declaim (ftype (function (t queue) queue) push-queue)
         (inline push-queue))
(defun push-queue (obj queue)
  (let ((new-tail (list obj)))
    (setf (cdar queue) new-tail
          (car queue)   new-tail))
  queue)

(declaim (ftype
          (function (t sequence &key (:start index) (:end end)
                       (:key key) (:test test))
                    list)
          position-all-reduce position-all-do-seq))

(defun position-all-reduce (obj seq &key (start 0) end key (test #'eql))
  (let ((i start))
    (declare (type index i))
    (cdr
     (reduce
      (if key
          (lambda (acc el)
            (incf i)
            (when (funcall test (funcall key el) obj)
              (push-queue i acc))
            acc)
          (lambda (acc el)
            (incf i)
            (when (funcall test el obj)
              (push-queue i acc))
            acc))
      seq :start start :end end
      :initial-value (make-queue)))))

(defun position-all-do-seq (obj seq &key (start 0) end key (test #'eql))
  (let ((acc (make-queue)))
    (do-sequence (el seq :start start :end end :key key :with-index i)
      (when (funcall test el obj)
        (push-queue i acc)))
    (cdr acc)))

(defconstant +len+ 5000000)

(let* ((sv  (let ((tmp (make-sequence 'vector +len+ :initial-element 0)))
              (loop :for i :from 0 :below +len+ :by 1000
                    :do (setf (aref tmp i) 42))
              tmp))
       (l   (coerce sv 'list))
       (fsv (make-array +len+ :element-type 'fixnum :initial-contents l))
       (fv  (make-array +len+ :element-type 'fixnum :initial-contents l
                       :adjustable t)))
  (format t "Test,~A~%" (lisp-implementation-type))
  (loop :for (args name) :in
        `(((42   ,l) "LIST")
          ((42   ,l :start 100 :end ,(- +len+ 100) :key ,#'1+) "LIST (fiddly)")
          ((42  ,sv) "SIMPLE-VECTOR")
          ((42 ,fsv) "(SIMPLE-ARRAY FIXNUM)")
          ((42  ,fv) "(VECTOR FIXNUM)"))
        :do (let ((tref (nth-value 1 (measure (apply #'position-all-reduce args))))
                  (tnew (nth-value 1 (measure (apply #'position-all-do-seq args)))))
              (format t "~A,~D → ~D (~@D%)~%"
                      name
                      (round (* tref 1000))
                      (round (* tnew 1000))
                      (round (* 100 (- (/ tref tnew) 1)))))))```

### 結果

| 実装 | LIST | LIST (fiddly) | SIMPLE‑VECTOR | SIMPLE‑ARRAY FIXNUM | VECTOR FIXNUM |
|------|------|---------------|--------------|---------------------|--------------|
| SBCL | 30 → 11 (+173%) | 58 → 18 (+224%) | 879 → 351 (+150%) | 291 → 147 (+98%) |
| CCL  | 33 → 21 (+57%) | 63 → 28 (+122%) | 907 → 538 (+69%) | 352 → 301 (+17%) |
| ECL  | 29 → 20 (+45%) | 70 → 33 (+110%) | 826 → 458 (+80%) | 310 → 220 (+41%) |
| CLISP | 40 → 26 (+54%) | 108 → 70 (+54%) | 835 → 468 (+78%) | 321 → 228 (+41%) |

---

## ベンチマークの詳細

* **実行環境**  
  * SBCL 2.5.11, CCL 1.13, ECL 24.5.10, CLISP 2.49.92（バイトコードコンパイラ）  
  * ハードウェア：AMD 5900X、64 GB DDR4  
  * OS：Gentoo Linux (カーネル 6.12)  
  * GCC 15.2 / glibc 2.41
* **最適化設定**  
  `(optimize (speed 3) (safety 0) (debug 0))`  
  `measure` はタイミングを取る前にフル GC を行います。

---

## 結論

マクロベースのアプローチは、特に SBCL が `reduce` の最適化を強力に実装している場合でも、**パフォーマンスと可読性**の両面で顕著な向上をもたらしました。  
ただし、コードサイズが増えたりコンパイル時間が長くなる可能性がありますので、**インライン化は慎重に行い**、コンパイラの死コード除去機能によって恩恵が得られる場合のみ利用してください。

同じ日のほかのニュース

一覧に戻る →

2025/12/18 1:42

Gemini 3 Flash: Frontier intelligence built for speed

## Japanese Translation: > **概要：** > Google は、低コストで高速な AI モデル Gemini 3 Flash をリリースしました。これは Flash レベルのレイテンシーでプロ級の推論性能を提供します。Gemini アプリと Search の AI Mode では既にデフォルトエンジンとなり、Gemini 2.5 Flash は世界中で追加料金なしで即座に置き換えられます（Gemini 3 Pro が公開された直後）。ベンチマーク結果では、GPQA Diamond で 90.4 %、Humanity’s Last Exam（ツール無し）で 33.7 %、MMMU Pro で 81.2 %、SWE‑bench Verified で 78 % を獲得し、より大きなフロンティアモデルを上回ります。Gemini 3 Flash は Gemini 2.5 Pro より約30 %少ないトークン数で同等以上の性能を発揮します。価格は入力トークンあたり 0.50 USD、出力トークンあたり 3 USD（音声入力は 1 USD/百万トークン）です。JetBrains、Bridgewater Associates、Figma など多くの企業がこのモデルを活用し、コーディング、データ分析、設計ワークフローの高速化に役立てています。開発者は Gemini API（Google AI Studio）、Antigravity、Gemini CLI、Android Studio、Vertex AI、および Gemini Enterprise を通じて Gemini 3 Flash にアクセスできます。このモデルは Gemini アプリと Search 経由で全ユーザーへ展開されるほか、プレビュー API でも利用可能です。

2025/12/18 6:13

I got hacked: My Hetzner server started mining Monero

## Japanese Translation: ヘツナー VPS 上で Coolify をホストし、Next.js ベースの Umami アナリティクスを含む複数コンテナを実行していた。12 月 7 日に、Umami コンテナ内に Monero マイニングボット（`javae`/`xmrig`）が出現し、CPU スパイクが約 15 倍に増大した。著者はマイナーをコンテナに追跡し、CVE‑2025‑66478 ― Next.js の React Server Components “Flight” プロトコルにおける不安全なデシリアライゼーション（Puppeteer を介さずリモートコード実行が可能）を特定した。HTTP リクエストを巧妙に作成することで RCE が発動し、マイナーがインストールされた。ホストファイルシステムのチェック（`/tmp/.XIN-unix/javae`）ではエスケープは確認できず、コンテナは非 root の `nextjs` ユーザーとして実行され、特権モードやボリュームマウントも無いため、すべての悪意あるプロセスは名前空間内に留まった。著者は侵害されたコンテナを停止・削除し、CPU 負荷を通常状態へ戻した。UFW をデフォルトで受信トラフィックを拒否するよう設定し、SSH、HTTP、および HTTPS のみ許可することで、オープンな PostgreSQL / RabbitMQ ポートを効果的に遮断した。ヘツナーは 2025‑12‑17 にネットワークスキャン検知後、アブズケース警告を送付し、著者が侵害と対策を説明するとともにチケットはクローズされた。重要な教訓として、十分に隔離されているコンテナでも基盤フレームワークに脆弱性がある場合は突破可能であり、「Next.js を使っていない」状態が第三者ツールの依存関係によって偽りになるケースがあることを指摘した。この事例は、ファイアウォールルール、非 root ユーザー設定、特権モード無し、監視・ fail2ban の導入、およびタイムリーなパッチ適用という防御層の重要性を強調した。 ## 行動計画 - Umami を廃止する - すべてのコンテナに対してユーザー権限とマウントを監査する - SSH アクセスを強化し、アラートを設定する - セキュリティパッチを定期的に適用し、将来のインシデントを防止する ---

2025/12/18 3:15

How SQLite is tested

## Japanese Translation: > **SQLiteのテストインフラは網羅的で、コードベース全体にわたって完全な分岐カバレッジを実現しています。** > プロジェクトには約155.8 KSLOCのCソースがありますが、テストコードは92 M KSLOC以上――約590倍の量――で、すべての行が実行されることを保証しています。4つの独立したハーネスがカバレッジを提供します： > • **TCL**（27.2 KSLOC、1,390個のスクリプトファイル）で51,445件の異なるケースと数百万回の実行があります； > • **TH3**（1,055.4 KSLOC、約76.9 MBのバイナリ）で50,362件の異なるケース、完全カバレッジに必要な2.4 Mインスタンス、および約248.5 Mテストを実行するソークテストがあります； > • **SQL Logic Test (SLT)** はSQLiteとPostgreSQL、MySQL、MS SQL Server、Oracle 10gを比較し、7.2 Mクエリと1.12 GBのデータで検証します； > • **dbsqlfuzz**（libFuzzerベース）はSQLとデータベースファイルの両方を変異させ、約336個のシードファイルから16コアで1日あたり約500 Mテストを提供します。 > 追加の軽量ハーネスには `speedtest1.c`、`mptester.c`、`threadtest3.c`、`fuzzershell.c`、およびJSONBファズラ `jfuzz` が含まれます。 > 異常テストではメモリ不足、I/O障害、クラッシュ／電源損失、およびカスタムmalloc/VFSフックを使用した複合故障をシミュレートし、各障害後に整合性チェックが実行されます。 > ファズリングの歴史はAFL（2014‑2019）からOSS Fuzz（2016年以降）、その後dbsqlfuzz（2018年末）とjfuzz（2024年1月）へ進化しました。`fuzzcheck` スクリプトは毎回ビルド時に興味深いケースを再実行し、新しいバグが自動的にリグレッションテストとして生成されることを保証します。 > リソースリーク検出はTCL/TH3ハーネスに組み込まれており、メモリリーク、ファイルディスクリプタ枯渇、および不要なスレッドが自動的に監視されます。 > カバレッジは `gcov` を使用して100 %の分岐カバレッジと変異テストで達成され、マクロ（`ALWAYS`、`NEVER`、`testcase`）がMC/DCを強制し、コメント（`/*OPTIMIZATION‑IF‑TRUE/FALSE*/`）は偽陽性を防ぎます。 > 結果として、継続的に拡張される高い信頼性のテストスイートが実現し、ユーザーにSQLiteの安定性への確信を提供し、セキュリティ脆弱性から保護し、オープンソースデータベース品質保証のベンチマークとなります。