From e3db01cd487c5b666366885367c8bfff4a6a09da Mon Sep 17 00:00:00 2001 From: tanaka takashi Date: Tue, 30 Jun 2026 23:55:29 +0900 Subject: 検索インデックスのhash table化 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- docs/implementation-status.md | 16 ++++++++++++---- 1 file changed, 12 insertions(+), 4 deletions(-) (limited to 'docs') diff --git a/docs/implementation-status.md b/docs/implementation-status.md index 71bd226..52c037b 100644 --- a/docs/implementation-status.md +++ b/docs/implementation-status.md @@ -22,14 +22,19 @@ | 構成 | ビルド | CTest | 実施日 | 結果 | |---|---|---|---|---| -| Windows x64 / MSVC / Debug | ✅ 実施済 | ✅ 実施済 | 2026-06-30 | 14/14成功 | -| Windows x64 / MSVC / Release | ✅ 実施済 | ✅ 実施済 | 2026-06-30 | 14/14成功 | -| Windows x64 / MSVC / ASan | ✅ 実施済 | ✅ 実施済 | 2026-06-30 | 14/14成功 | +| Windows x64 / MSVC / Debug | ✅ 実施済 | ✅ 実施済 | 2026-06-30 | 15/15成功 | +| Windows x64 / MSVC / Release | ✅ 実施済 | ✅ 実施済 | 2026-06-30 | 15/15成功 | +| Windows x64 / MSVC / ASan | ✅ 実施済 | ✅ 実施済 | 2026-06-30 | 15/15成功 | | Windows以外 | ⬜ 未実施 | ⬜ 未実施 | ― | v1対象外 | Python MCP SDK 1.28.1によるglobal/scoped検索1000回交互呼出しも、Debug・Release・ASanの 各構成で成功し、接続切断・異常終了・ASan診断がないことを確認しました。 +P1のgram bucket hash table化後、Releaseの32KiB write p50は128.242msから5.907msへ +約21.7倍高速化しました。1MiB write p50は90.093ms、domain単体のindex構築平均は +1KiB 0.217ms、8KiB 1.299ms、32KiB 3.948ms、1MiB 34.988msで、payload増加に対する +二次的悪化がないことを確認しました。 + 実行コマンド: ```powershell @@ -121,9 +126,11 @@ ctest --preset windows-vs2026-asan | 設計項目 | 実装 | テスト作成 | テスト実施 | 補足・残作業 | |---|---|---|---|---| | Unicode codepoint 2/3-gram逆引き索引 | ✅ 実装済 | ✅ 作成済 | ✅ Debug/Release | contentとtagsを索引化 | +| gram bucket hash table | ✅ 実装済 | ✅ 作成済 | ✅ Debug/Release/ASan | open addressing、最大load factor 70%、完全key照合 | | ASCII case folding | ✅ 実装済 | ✅ 作成済 | ✅ Debug/Release | `CURRY`/`curry` を確認 | | 日本語検索 | ✅ 実装済 | ✅ 作成済 | ✅ Debug/Release | `設計` tagを確認 | -| hash衝突時の実codepoint照合 | ✅ 実装済 | 🟡 実装経路のみ | 🟡 間接実施 | 意図的なhash collision fixtureは未作成 | +| hash衝突時の実codepoint照合 | ✅ 実装済 | ✅ 作成済 | ✅ Debug/Release/ASan | test hashを8-bit化し、300個の異なるgramで衝突を強制 | +| index追加のallocation failure atomicity | ✅ 実装済 | ✅ 作成済 | ✅ Debug/Release/ASan | 全allocation位置を掃引し、部分登録・leakなしを確認 | | 1 codepoint query fallback | ✅ 実装済 | ⬜ 未作成 | ⬜ 未実施 | 全候補からscore計算する経路が未確認 | | 起動時索引構築 | ✅ 実装済 | 🟡 再起動で間接確認 | ✅ Debug/Release | 大量データ時の時間/メモリ試験なし | | write時索引更新 | ✅ 実装済 | ✅ MCP検索で確認 | ✅ Debug/Release | index allocation失敗のfault injectionなし | @@ -200,6 +207,7 @@ ctest --preset windows-vs2026-asan |---|---|---|---|---|---| | `tiny-convmem-mcp.smoke` | MCP E2E | ✅ 作成済 | ✅ 成功 | ✅ 成功 | initialize、6 tool schema、write/read/search/rebuild/health、検証エラー | | `tiny-convmem-mcp.domain` | Unit | ✅ 作成済 | ✅ 成功 | ✅ 成功 | role/tier、UTF-8、ULID、deep copy、ASCII/日本語n-gram | +| `tiny-convmem-mcp.search-index` | Unit | ✅ 作成済 | ✅ 成功 | ✅ 成功 | hash衝突、rehash、Unicode、allocation failure atomicity | | `tiny-convmem-mcp.mcpc` | Unit | ✅ 作成済 | ✅ 成功 | ✅ 成功 | required属性、NULL callback拒否、fork API | | `tiny-convmem-mcp.protocol` | MCP E2E | ✅ 作成済 | ✅ 成功 | ✅ 成功 | JSON-RPC異常系、schema/default、1000回交互検索、終了診断 | | `tiny-convmem-mcp.storage` | Unit/Integration | ✅ 作成済 | ✅ 成功 | ✅ 成功 | lock、write/reopen、ULID順、temp失敗、CRC破損拒否 | -- cgit v1.2.3