リスタート可能シーケンス（rseq）によるスレッドセーフなデータ構造の構築と性能向上

2026 年 5 月 31 日現在、システムプログラミングにおいて「最も保守されている秘密」と呼べるのは、Linux カーネルバージョン 4.18（約 2018 年）以降に導入された リスタート可能シーケンス（Restartable Sequences, rseq） です。

この技術により、ロックや原子操作を使用せずにスレッドセーフなデータ構造を作成し、マルチコアマイクロプロセッサにおいても極めて効率的に拡張性を持たせることが可能になります。

• 現状の課題: 現在 rseq を利用するには手書きのアセンブリコードが必要ですが、将来的には全ての OS がサポートを強化し、言語やライブラリがこれを用いるようになるでしょう。
• 採用実績: tcmalloc、jemalloc、glibc、および Cosmopolitan が先行して採用しています。
• 背景: 128 コアあるいは 192 コアのマイクロプロセッサが登場し、価格も手頃になってきた現在、rseq の重要性が高まっています。

事例：malloc() 実装の劇的な高速化

• Raspberry Pi 5 ($160, 4 コア): rseq を採用することで従来の方法より約 3 倍高速化。多くの開発者にとっては「受け入れるかそうでないか」レベルの改善です。
• System76 Thelio Astra ($4,834, Ampere 128 コア・3GHz Altra CPU): rseq を採用することで従来の方法と比較して約 34 倍高速化。
• AMD Threadripper Pro 7995WX ($17,628.55, 96 コア): sched_getcpu() ベースのミューテックスによる超分割技術と比べて、

  malloc()

  が約 43 倍高速化。

高機能ワークステーションを持たないシステムプログラマーは、10 倍もの性能向上という「低く伸びる果実」を逃すことになり、「恐竜」として後塵拝する可能性があります。昨行列積算速度の最適化で成果が得られたのは、Splurge 級の高額投資ではなく、より廉価な Ampere ワークステーションへの投資と生活苦を我慢した結果でした。その報いはメディア取材、AI コミュニティでの知名度向上、プロジェクト採用率の 32% 上昇、そして Google の Gradient Canopy（Gemini TPU）へのオファーといった成果をもたらしました。

マイクロプロセッサをお持ちであれば、rseq はその能力を最大限に活かすための最重要テクニックです。本記事では動作原理と、すぐに役立つ具体的な例（プッシュ・ポップ操作）を提供します。

リスタート可能シーケンスが解決する問題

Cosmopolitan C ランタイムは Linux システム上でスレッドを作成する際、

rseq()

効果と機能

1. 極端な速度向上:

   sched_getcpu()

   の実装が改善されました。以前はマイクロ秒単位で待機していたのが、わずか 1 ナノ秒の relaxed mov インストラクションですべて済みます。
2. 情報返信機能: rseq TLS メモリの第 2 のフィールド（

   rseq_cs

   ）により、スレッドがカーネルに情報を返信できます。

   • rseq_cs

     にプログラム内のアセンブリ命令列のポインタを設定します。
   • カーネルがスレッドをプリエンプして別の CPU へ移動させた際、プログラムカウンタ（%rip）が指定された区間内にあるか確認します。
   • もしその場合、カーネルは指定した abort ハンドラにスレッドを強制的にジャンプさせます（関数の先頭への戻り操作など）。

解決すべき課題：GIL ロックの排除

従来の GIL（Global Interpreter Lock）やpthread_mutex を使用すると、数十のコアを持つシステムでは動作が極端に遅くなります。それはどの瞬間も単一のスレッドしかロックを保持できないからです。そのため「原子操作を使用したロックレスなリスト」を作ろうとする試みがよく行われますが、以下の問題があります。

static struct List {
  struct List *next;
};

_Atomic(struct List *) list;

// ... 単純な push/pop は ABA プロブレムやキャッシュライン競合の問題に直面する ...

単に複数のコアが同一の 64 バイト領域（キャッシュライン）を共有しているため、CPU は内部で基本的にはミューテックスとして振る舞うようになります。また、ユーザスペースの実装ロックよりも CPU 内部ミューテックスの方が優れているとは限りません。

シャード化されたリストの実装

より賢明なアプローチは、データ構造自体を シャード（分割） し、各 CPU に独自の領域を持たせることです。

static struct {
  alignas(64) struct List *list;
} lists[CPU_SETSIZE];

ここですべて行うべきことは

sched_getcpu()

static struct {
  alignas(64) pthread_mutex_t lock;
  struct List *list;
} gil[CPU_SETSIZE];

これで競合は角ケースのみで保証されますが、「暗闇と昼」ほどの差（競合時：200 ナノ秒以上、非競合時：約 15 ナノ秒）があり、単なるプッシュ・ポップ操作（約 1 ナノ秒）にとってはコストが高すぎます。

ミューテックスを排除する

OS スケジューラ制御（

sched_setaffinity()

rseq()

• 仕組み: プログラムが中断させたくないクリティカルセクションに入るとカーネルに通知します（アセンブリ命令で約 10 程度）。
• 構成: 最初の命令は

  rseq_cs

  フィールドを設定し、最後の命令はグローバルデータ構造への修正を行います。これは非常に小さなデータベーストランザクションのように動作します。
• 高速化の秘訣: カーネルとの双方向通信が共有メモリを経由することにあります。

例 No.1：最速なヒットカウンターを構築する

数字を増やすだけの極めて単純なプログラムを作成し、5 つの手法と比較しました（ブログのアクセス回数を追跡するマルチスレッド Web サーバーシナリオ）。

96 コア搭載の AMD Ryzen Threadripper Pro 7995WX (x86-64) のベンチマーク結果

• glibc ミューテックスと比較し、CPU 時間の消費を見ただけでも rseq は実際のところ 100 万倍もの高速化を実現しています。
• 検討価値があるのは主に以下の 3 つです：
  • シャード化（Sharding）: 全ての OS での互換性が求められる場合に最適。

    cosmo_shard()

    を使用。
  • アフィニティ（Affinity）: 最も速かったが、スレッドの微細管理を要求するためライブラリ開発には不向き。

    alignas(64) volatile long x

    などの工夫で rseq と同等の速度を出せます。
  • リスタート可能シーケンス: 優れたトレードオフ。現代の Linux でのみ動作しますが、将来のエレガントな言語実装が期待されます。

128 コア搭載の System76 Thelio Astra w/ Ampere の 3GHz Altra CPU (ARM64) のベンチマーク結果

• Ampere の ARM Altra CPU:非常に高速な原子操作とメモリアバリア管理を必要としない

  ldadd

  インストラクション（

  memory_order_relaxed

  ）を利用可能。
• x86 に対して「Hyper-Threading」の影響などがあり、Altra CPU は Threadripper よりも著しく高速です。
• rseq を使用することで 3GHz の CPU が事実上 33GHz の CPUになりました（ミューテックス使用時：219MHz へ劣化）。

RISC vs x86 の視点 Ampere が RISC の夢をようやく実現しました。私が現在最も多くのコアを持つ CPU を所有している ARM チップが、ベンチマーク結果から x86 チップよりも高い性能を発揮することが判明し、驚かされました。

例 No.2: リンクリストのプッシュ・ポップ操作

グローバルにオブジェクトインスタンスを追跡したい場合、rseq を使用するとシャード化されたリンクリストに対する

push()

pop()

#include <assert.h>
#include <cosmo.h>
#include <linux/rseq.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#define ITERATIONS 10000000l

struct List {
  struct List *next;
};

struct {
  alignas(64) struct List *freelist;
} heaps[CPU_SETSIZE];

ここですべてのロックと原子操作を取り除きました。

alignas(64)

アセンブリコード解説

Richard Stallman の Math 55 スタイルのアセンブリ表記を使用しています。これは C/C++ との制約系を組み合わせた最も強力な形式です。

static inline void push(struct List *chunk) {
#ifdef __x86_64__
  // x86-64 アセンブリ実装
  asm volatile(".pushsection .rodata.rseq,\"a\",@progbits\n"
               "	.balign	32\n"
               "300:	.long	0                      // rseq_cs::version\n"
               "	.long	0                      // rseq_cs::flags\n"
               "	.quad	301f                   // rseq_cs::start_ip\n"
               "	.quad	302f-301f              // rseq_cs::post_commit_offset\n"
               "	.quad	303f                   // rseq_cs::abort_ip\n"
               "	.popsection\n"                //
               "301:	lea	300b(%%rip),%%rcx\n"  // relative address calculation\n"
               "	mov	%%rcx,8(%1)\n"        // rseq->rseq_cs = &300b\n"
               "	mov	(%1),%%ecx\n"         // rseq->cpu_id_start\n"
               "	shl	$6,%%ecx\n"           // Multiply by 64 (cache line offset)\n"
               "	mov	(%2,%%rcx),%%rdx\n"   // rdx = freelist\n"
               "	mov	%%rdx,(%0)\n"         // chunk->next = rdx\n"
               "	mov	%0,(%2,%%rcx)\n"      // freelist = chunk\n"
               "302:	.pushsection .text.unlikely,\"ax\",@progbits\n"
               "	.byte	0x0f,0xb9,0x4d\n"  // Atomic compare and swap logic\n"
               "	.long	0x53053053\n"       // Magic number for rseq\n"
               "303:	jmp	301b               // restart on abort\n"
               "	.popsection"\n"
               : /* no outputs */
               : "r"(chunk), "r"(__get_rseq()), "r"(heaps)
               : "rcx", "rdx", "memory");
#endif
}

仕組みの詳細:

1. .pushsection .rodata.rseq

   : ファイル内の異なる領域にコンテンツを「テレポート」させます。標準の GNU リンカースクリプトは、起動時に

   PROT_READ

   マークを付与する ELF プログラムヘッダーセグメントにこれを認識します。
2. 静的な

   struct rseq_cs

   : System V スタイルの数値ラベル（正方向 f、逆方向 b）を使用し、コンパイラによる関数インライン化に対しても壊れないように設計されています。
3. カーネルとの通信: カーネルがスレッドをプリエンプしたとき、作成した

   rodata

   ストラクチャを読み取り、プログラムカウンタ (%rip) が指定された区間内にあるか確認します。そこにあれば、カーネルは abort_ip（ラベル 303）に変更して処理を再開させます。
4. トランザクション性: シーケンス全体はトランザクションのように動作し、最後の命令が変更をコミットするものとして機能します。

abort ハンドラコードは、GNU スタンドなセクション名

.text.unlikely

rseq()

RSEQ_SIG

malloc()

テストコード

プッシュとポップ関数のテスト用のコードです。

void *worker(void *arg) {
  struct List *elem;
  for (long i = 0; i < ITERATIONS; ++i) {
    switch (i % (ITERATIONS / 10000)) {
      case 0:
        push(malloc(sizeof(struct List)));
        break;
      default:
        if ((elem = pop()))
          push(elem);
        break;
    }
  }
  return 0;
}

void cleanup(void) {
  for (int i = 0; i < CPU_SETSIZE; ++i) {
    struct List *chunk;
    while ((chunk = heaps[i].freelist)) {
      heaps[i].freelist = chunk->next;
      free(chunk);
    }
  }
}

int main(void) {
  if (__get_rseq()->cpu_id < 0) {
    fprintf(stderr, "rseq is not supported on this system\n");
    return 1;
  }
  int threads = cosmo_cpu_count();
  pthread_t th[threads];
  for (long i = 0; i < threads; ++i)
    pthread_create(&th[i], 0, worker, 0);
  for (long i = 0; i < threads; ++i)
    pthread_join(th[i], 0);
  cleanup();
}

メソドロジーと測定方法

Cosmopolitan はデフォルトで x86-64 と ARMv8.0-a をターゲットにコンパイルされます。Altra 専用の ARM コードを構築することでさらに 10% のパフォーマンスを得ることも可能です。

malloc パフォーマンスを測定するためのコード（各 CPU でスレッドを生成し、小さなメモリ領域を割り当てと解放）：

#include <cosmo.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#define NUM_THREADS    cosmo_cpu_count()
#define NUM_ITERATIONS 10000000

void *identity(void *arg) {
  return arg;
}

void *(*pIdentity)(void *) = identity;

void *thread_func(void *arg) {
  for (unsigned long i = 0; i < NUM_ITERATIONS; i++)
    free(pIdentity(malloc(i % 256)));
  return NULL;
}

int main() {
  pthread_t threads[NUM_THREADS];
  for (int i = 0; i < NUM_THREADS; i++)
    if (pthread_create(&threads[i], NULL, thread_func, NULL))
      return 1;
  for (int i = 0; i < NUM_THREADS; i++)
    if (pthread_join(threads[i], NULL))
      return 1;
}

rseq の使用量を制限し、他の OS でも動作可能なポータブルな実行可能ファイルを作成するには、環境変数

COSMOPOLITAN_M_RSEQ_MAX

cosmocc -O -o bench bench.c
time ./bench
export COSMOPOLITAN_M_RSEQ_MAX=0
time ./bench

高度な読書資料

• tcmalloc のドキュメント: rseq を malloc 実装で使用した方法や、リンクリストではなく配列を使用し、未コミット領域に対する整数を示す方法を説明しています。

• MEMBARRIER_CMD_PRIVATE_EXPEDITED_RSEQ

  : Linux v5.10 の membarrier() システムコールに導入され、tcmalloc が rseq データ構造へのクロス-CPU 変更を促進するために使用されます。

クレジット

• Gentoo Linux ペンギンのグラフィック：ChatGPT と協力して作成。
• コードフォント：Fabrizio Schiavi（イタリア）が設計した PragmataPro Variable (€299)。

• rseq()

  システムコールの開発者：Paul Turner、Andrew Hunter（Google）、Mathieu Desnoyers（EfficiOS）。

赤い豆（redbean）の Discord サーバーにご参加いただき、私と Cosmopolitan の開発者たちとお過ごしください。

お供え金（資金提供）

System76 と Ampere は、llamafile などのオープンソースプロジェクトで私の活動をサポートするためにワークステーションを割引価格で購入することを快諾してくれました。過去 5 年間にわたるブログ運営とオープンソース活動が可能になったのは GitHub スポンサーおよび Patreon サブスクリプションのおかげです。本記事には Amazon アソシエイトリンクを含んでいますので、推奨製品を購入することも支援の手段の一つになります。最後に、私が今のような活動を可能にした功績に最も感謝すべき企業は Google と Mozilla です。