← 2026-06-05 の一覧へ戻るホーム
CおよびC++ APIを実装したブランチレスクイックソートが、std::sortやpdqsortよりも高速

2026/06/03 5:00

CおよびC++ APIを実装したブランチレスクイックソートが、std::sortやpdqsortよりも高速

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

元のHacker News記事へ ↗
要約▶

Japanese Translation:

blqsort は、高度な分岐なし（branchless）手法を用いて分岐誤予測によって引き起こされるハードウェアの遅延を最小化することにより、標準的な C++ 

std::sort
を大幅に上回る高性能な単一ヘッダーソートライブラリです。Apple M1 システムでのベンチマーク結果（Clang -O3 でコンパイル）では、blqsort は 5,000 万個の二重精度数値を 0.97 秒でソートし、これに対し 
std::sort
および 
pdqsort
では 1.33 秒かかりました。また、独自に定義した構造体エントリ 5,000 万個のソートには blqsort で 0.96 秒、一方 
std::sort
では 3.46 秒かかりました。本ライブラリは C および C++ の両方をサポートし、単スレッドおよびマルチスレッドモードを選択可能となるよう、4 つの独立したヘッダーファイル（blqs.h、blqs_thr.h、blqsort.h、blqsort_thr.h）として提供されています。GCC もしくは Clang でコンパイル可能です。信頼性と速度を確保するため、blqsort は 1024 要素スタック配列を補助バッファとして使用し、大規模な分割区間に対して median-of-medians を用いたピボットとループアンローリングを適用し、小さなサブセットに対してカスタムソートネットワークを採用するとともに、悪い入力に対してはヒープソートへ、コピーコストが高いデータ型に対しては BlockQuicksort へ知的にフォールバックします。Google Highway のような外部依存関係を必要とする複雑な解決策と異なり、blqsort は適切なヘッダーを含めるのみで動作し、SIMD ライブラリを必要とせず、現代のハードウェア上でパフォーマンスクリティカルなアプリケーションへの堅牢かつ移植性の高いドロップイン代替手段として機能します。

本文

ブランチレスクイックソートの概要と実装ガイド

1. パフォーマンスベンチマーク

5,000 万件の 

double
タイプデータをソートした際の比較結果（すべてシングルスレッド版を使用）です。

メトロロジーApple M1AMD Ryzen
std::sort
1.33 秒5.56 秒
pdqsort
1.33 秒2.81 秒
blqsort
0.97 秒2.06 秒

補足事項

  • Apple M1: マルチスレッド版はさらに 3〜4 倍 の高速化が可能です。
  • ランタイム: C++ バージョンと C バージョンでは性能差が極めて僅かです。
  • 環境: Clang (M1) および GCC (Ryzen) を 
    -O3
    最適化でコンパイル。

2. 技術的アプローチ

ブランチレスプログラミングの概念

現代のプロセッサにおいて、**分岐誤予測（branch misprediction）**を回避することが高速化の鍵です。

コード比較例：ブランチレス vs 通常

【非推奨】条件分岐を含む書き方（遅い）

for (int i = 0; i < 1000; i++) {
    if (numbers[i] < 500) {
        small_numbers[smlen] = numbers[i];
        smlen += 1;
    }
}

【推奨】ブランチレスアプローチ（高速）

for (int i = 0; i < 1000; i++) {
    small_numbers[smlen] = numbers[i];
    smlen += (numbers[i] < 500); // 真偽値を直接足算する
}

ソートネットワークの活用

小規模なサブセット（2〜12 要素）では、カスタムソートネットワークを採用します。

  • メリット: ブランチレスな 
    sort-2
    素関数を使用し、極めて少ないスワップでソート可能。
  • 戦略: 各サイズごとに専用コードパスを定義します。

ピボット選択と悪性入力への対処

  • 不良入力回避: 同じ種の要素をグループ化し、バランスが崩れる部分をヒープソートに切り替えます。
  • ソート済み判定: パーティションが既にソート済みかのチェックを行います。
  • ピボット選択: 大規模領域では **Median-of-Medians（中央値の中位）**戦略を採用。
  • 最適化: 重要なパーティションループについては明示的に**アンロール（展開）**しています。

補助バッファ戦略

fluxsort
に由来する手法で、スタック上の 1024 要素分の領域（ヒープとは異なる）を「補助バッファ」として使用します。

  • 片方の領域から 1024 要素をコピーしスペース確保。
  • ブランチレス手法で左右交互に 1024 要素分をコピー。

注釈: コピー回数は本来必要な倍近く増えますが、軽量データ型においては「誤予測回避の利点」の方が圧倒的に効率的です。

データ型による実装の違い

  • 軽量データ型: ブランチレス・バッファベース（
    blqs.h
    等）を使用。
  • 重量級データ型 (文字列など): 
    std::is_trivially_copyable
    でない場合はコピーコストが高くなるため、ブロック移動を削減した BlockQuicksort を使用します。

3. システム別使用方法

C++ インターフェース

単一ヘッダーファイルのみで利用可能。

シングルスレッド版 (
blqs.h
)

#include "blqs.h"

double data[SIZE];

blqs::sort(data, data + SIZE);

マルチスレッド版 (
blqs_thr.h
)

C++ std::thread
を使用した並列処理です。

// blqs.h の代わりに blqs_thr.h をインクルードしてください
#include "blqs_thr.h"

double data[SIZE];
blqs::sort(data, data + SIZE); // 関数呼び出し形式は同一

C インターフェース

#define
メカニズムを用いてデータ型ごとに特殊化されたコードを生成します。

シングルスレッド版 (
blqsort.h
)

#define BLQS_CMP(a, b) ((a) < (b))
#define BLQS_TYPE double
#include "blqsort.h"

double data[SIZE];

blqsort(data, SIZE);

マルチスレッド版 (
blqsort_thr.h
)

POSIX threads を使用します。

// blqsort.h の代わりに blqsort_thr.h をインクルードしてください
#include "blqsort_thr.h"

double data[SIZE];
blqsort(data, SIZE); // 関数呼び出し形式は同一

4. カスタムデータ構造体のソート

Google Highway などの SIMD ライブラリは数値向けですが、複雑な構造体には適用しづらいため、柔軟性を確保したい場合は以下の方法を使用します。

C++ での例（コンパイル済み関数オブジェクト対応）

独自の比較ロジックを 

operator<
で定義可能。

#include "blqs.h"

struct entry {
    int id;
    int value;

    bool operator<(const entry& other) const {
        return id < other.id;
    }
};

struct entry data[SIZE];

blqs::sort(data, data + SIZE);

C での例（マクロによる比較関数定義）

マクロでカスタムフィールドを指定可能。

struct entry {
    int id;
    int value;
};

#define BLQS_CMP(a, b) (((a).id) < ((b).id))
#define BLQS_TYPE struct entry
#include "blqsort.h"

struct entry data[SIZE];

blqsort(data, SIZE);

5. カスタム構造体パフォーマンス比較

独自の構造体（フィールドが重い場合）をソートした場合のベンチマーク結果です。

実装Apple M1AMD Ryzen
std::sort
3.46 秒4.75 秒
pdqsort
3.46 秒4.72 秒
blqsort
0.96 秒2.20 秒

6. リンク・参考資料

  • 'if' がパフォーマンスを下げる場合は回避しましょう (詳細解説)
  • インタラクティブなソートデモ
  • お問い合わせ: christof.kaser@gmail.com

同じ日のほかのニュース

一覧に戻る →

2026/06/05 5:11

Anthropic の AI 駆動型脆弱性情報発見のためのオープンソースフレームワーク

## Japanese Translation: サマリーは全体的には良好ですが、キーポイント（コマンド、特定のスキル、パイプラインの段階）に見られる具体的な実行可能な詳細が不足しています。構造とコマンドを取り入れたやや詳細なバージョンであれば、推論を加えずに完全性を向上させることができます。 ## サマリー（改善版） Anthropic は、「Claude Security」というソフトウェアの脆弱性発見および修正のためのマネージドサービスを紹介しており、オープンソースのリファレンスハルネス `github.com/anthropics/defending-code-reference-harness` が提供されています。このリポジトリは、セキュリティチームとのパートナーシップから得られた知見を活用し、自律的な C/C++ 脆弱性発見および修正のためのガイド役を担っていますが、外部からのコントリビューションを受け入れるメンテナンスされた製品ではありません。アクセスには Bedrock や Vertex、Azure などの特定の API が要求されます。 コア技術は、脅威モデリング、静的スキャン、実行検証、パッチ適用を含む厳格な多段階パイプラインを使用しています。主要なスキルには `/threat-model`、`/vuln-scan`、`/triage`、`/patch`、および `/customize` があります。特に重要なのは、自律エージェントがシステムへの損傷を防ぐために **gVisor** サンドボックス内で対象コードを実行すること（Claude API へのエGRESSは制限されている）であり、パイプラインを `bin/vp-sandboxed` を通じて呼び出す前にユーザーが `./scripts/setup_sandbox.sh` を実行する必要があります。`/quickstart` スキルはサンドボックスなしで **Claude Code** で安全に確認できるのに対し、自律ループにはそれを必要とします。 ユーザーは段階的なアプローチに従うよう推奨されます：ステップ 1（Day 1）では、対象コードに対して静的スキャンと脅威モデリングを行い、`/patch` を通じてパッチを生成し、カスタマイズをスモークランで検証してからステップ 2（Day 2）へ進む。ステップ 2 では C/C++ ライブラリ向けの完全な自律ループを展開します。生产用途では、組織は複数の並列パイプラインウェーブ（ステップ 4）を実行し、結果に対して自動タリアジを行うべきです（`/triage` で投票を使用）。本システムは SDLC に連続的検証を統合しており、毎日スキャンや CI パイプラインを通じて運用され、ゼロから構築される完璧なプラットフォームを要求せずに多様な依存関係の露出に対処するのを支援します。サンドボックス化、カスタマイズ、およびパッチに関するドキュメントは `docs/security.md`、`docs/agent-sandbox.md` および関連ガイドで利用可能です。

2026/06/05 6:42

URL の IPv6 ゾーンは間違いです

## Japanese Translation: - 現在稼働中の Anubis ウェブサイトはバージョン v1.25.1-0.20260604200537-44d5fa3ce047 を使用しています。マスコットのデザインは CELPHASE によって作成されました。サイトには Techaro に帰属する著作権表示が表示され、コンテンツは「❤️（愛）と🇨🇦（カナダ）で作成」であるとしてクレジットされています。

2026/06/04 22:00

Cloudflare に参加する VoidZero が決定

## Japanese Translation: VoidZero（Vite、Vitest、Rolldown、Oxc、および Vite+ の開発者）が、その全チームを Cloudflare に統合し、エコシステムを完全にオープンソース化し、MIT ライセンスに基づき、ベンダー非依存な状態を維持することを約束しています。100 万ドルの資金を Vite エコシステムファンドに供与することで、コミュニティ主導の開発を優先し、ツールをプロプライエタリなスタックに合わせるのではなく、強化されたエンジニアリングリソースを直接ツール維持に向けるとして、この戦略的移行を進めています。Evan とコアチームは引き続き開発をリードし続けます。Vite（週 1.29 億回のダウンロード）や新しい Cloudflare プラグイン（週 1,400 万回のダウンロード）の高い採用率は、特に AI 開発者がこの統一されたワークフローによって支えられる高速フィードバックループを必要としていることで、強固な市場の信頼を示しています。現在、Vite は React、Next.js（vinext 経由）、Vue、SvelteKit、Nuxt、Astro、Solid、Qwik、Angular など主要なフレームワークの基盤となるビルドツールとして機能しています。新たに導入された統一 CLI（`cf`）はネイティブデプロイとバインディングを統合しており、標準的な Vite 操作と完全に互換性を保ちつつ、「cf dev」コマンドにより「vite dev」の超集合体として動作します。将来の計画には、Void プラットフォームを完全にオープンソース化して公衆との協力を促進することや、Cloudflare の Environment API を通じて非 Node ランタイムをサポートするツールへの進化が含まれています。結局のところ、開発者は強力なリソースと統一された環境にアクセスでき、業界はベンダーロックインなしで長期的なポータビリティを確保する強化された標準から恩恵を受け、Cloudflare のツールは Vite を Cloudflare 用に特別に適応させるのではなく、Vite スタンドダードの方へ移行しています。

CおよびC++ APIを実装したブランチレスクイックソートが、std::sortやpdqsortよりも高速 | そっか～ニュース