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 --- tests/CMakeLists.txt | 28 +++++++ tests/function-coverage.md | 1 + tests/mcp_protocol_test.py | 37 ++++++++++ tests/search_index_benchmark.c | 110 ++++++++++++++++++++++++++++ tests/search_index_test.c | 161 +++++++++++++++++++++++++++++++++++++++++ 5 files changed, 337 insertions(+) create mode 100644 tests/search_index_benchmark.c create mode 100644 tests/search_index_test.c (limited to 'tests') diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt index 9ce564e..9a02ee0 100644 --- a/tests/CMakeLists.txt +++ b/tests/CMakeLists.txt @@ -22,6 +22,33 @@ if(MSVC) endif() add_test(NAME tiny-convmem-mcp.domain COMMAND tiny-convmem-domain-test) +add_executable(tiny-convmem-search-index-test + search_index_test.c + "${PROJECT_SOURCE_DIR}/src/domain/message.c" + "${PROJECT_SOURCE_DIR}/src/domain/search.c" +) +target_include_directories(tiny-convmem-search-index-test PRIVATE "${PROJECT_SOURCE_DIR}/src") +target_compile_features(tiny-convmem-search-index-test PRIVATE c_std_17) +target_compile_definitions(tiny-convmem-search-index-test PRIVATE TINY_SEARCH_TEST_HASH_BITS=8) +target_link_libraries(tiny-convmem-search-index-test PRIVATE tiny-convmem-base) +if(MSVC) + target_compile_options(tiny-convmem-search-index-test PRIVATE /utf-8 /W4) +endif() +add_test(NAME tiny-convmem-mcp.search-index COMMAND tiny-convmem-search-index-test) + +add_executable(tiny-convmem-search-benchmark + search_index_benchmark.c + "${PROJECT_SOURCE_DIR}/src/domain/message.c" + "${PROJECT_SOURCE_DIR}/src/domain/search.c" +) +target_include_directories(tiny-convmem-search-benchmark PRIVATE "${PROJECT_SOURCE_DIR}/src") +target_compile_features(tiny-convmem-search-benchmark PRIVATE c_std_17) +target_link_libraries(tiny-convmem-search-benchmark PRIVATE tiny-convmem-base) +if(MSVC) + target_compile_options(tiny-convmem-search-benchmark PRIVATE /utf-8 /W4) + target_link_libraries(tiny-convmem-search-benchmark PRIVATE psapi) +endif() + add_executable(tiny-convmem-mcpc-test mcpc_test.c) target_include_directories(tiny-convmem-mcpc-test PRIVATE "${CMAKE_CURRENT_SOURCE_DIR}") target_compile_features(tiny-convmem-mcpc-test PRIVATE c_std_17) @@ -111,6 +138,7 @@ if(TINY_CONVMEM_ENABLE_ASAN AND MSVC) TEST tiny-convmem-mcp.smoke tiny-convmem-mcp.domain + tiny-convmem-mcp.search-index tiny-convmem-mcp.mcpc tiny-convmem-mcp.protocol tiny-convmem-mcp.boundaries diff --git a/tests/function-coverage.md b/tests/function-coverage.md index 66c2e4a..8787918 100644 --- a/tests/function-coverage.md +++ b/tests/function-coverage.md @@ -10,6 +10,7 @@ byte/encoding logic is exposed through internal headers and tested directly. | `storage/codec.c` | `tiny_codec_put_u32`, `tiny_codec_put_u64`, `tiny_codec_get_u32`, `tiny_codec_get_u64`, `tiny_codec_crc32` | `boundaries`: offsets 0–15, integer limits, empty/NULL and known CRC | | `sys/system.c` | test-hook helpers; UTF adapters; `native_file`; argument, path, directory, file, clock and random APIs | `boundaries`, `storage`, `smoke`: NULL/invalid handle, Unicode paths, short I/O, operation failure, cleanup | | `domain/message.c` | `duplicate_string`, `copy_failed`, all `tiny_message_*`, role/tier parse/name, `tiny_utf8_valid`, `tiny_message_id_valid` | `domain`: enum failure, UTF-8 invalidity, ULID alphabet/length, deep copy and ownership | +| `domain/search.c` | Unicode decode/score、open-addressing lookup/rehash、transactional delta merge、candidate union | `domain`, `search-index`: ASCII/日本語、8-bit hash衝突、複数rehash、allocation failure全位置、leak balance | | `domain/search.c` | `decode_codepoints`, `gram_hash`, `find_bucket`, `add_gram`, `index_text`, all `tiny_search_*` | `domain`: ASCII case folding, Unicode grams/tags, candidates, scoring and ownership | | `storage/store.c` | error/I/O helpers, ULID, entry growth/search, record codec, replay/snapshot/recovery, all `tiny_store_*` | `storage`, `lifecycle`: lock, append/reopen, corruption, rebuild rollback, Unicode path | | `mcp/json.c` | `reserve`, all `tiny_json_*` | `boundaries`: empty append, growth, control escaping, signed/unsigned integer limits, OOM | diff --git a/tests/mcp_protocol_test.py b/tests/mcp_protocol_test.py index 118043f..f739168 100644 --- a/tests/mcp_protocol_test.py +++ b/tests/mcp_protocol_test.py @@ -81,6 +81,15 @@ def tool_payload(response: Mapping[str, Any], expect_error: bool = False) -> dic return json.loads(result["content"][0]["text"]) +def assert_stable_recency_order(messages: list[dict[str, Any]]) -> None: + for left, right in zip(messages, messages[1:]): + left_time = int(left["timestamp"]) + right_time = int(right["timestamp"]) + assert left_time > right_time or ( + left_time == right_time and left["message_id"] <= right["message_id"] + ), (left, right) + + def main() -> None: parser = argparse.ArgumentParser() parser.add_argument("--server", type=Path, required=True) @@ -156,6 +165,22 @@ def main() -> None: next_id += 1 assert len(history) == 20 + ranked = tool_payload( + tool_call( + server, + next_id, + "search_messages", + {"query": "needle target", "limit": 100}, + ) + )["results"] + next_id += 1 + assert len(ranked) == 30 + assert all(item["session_id"] == "target" for item in ranked[:20]) + assert all(item["session_id"] == "other" for item in ranked[20:]) + assert_stable_recency_order(ranked[:20]) + assert_stable_recency_order(ranked[20:]) + ranked_ids_before = [item["message_id"] for item in ranked] + for index in range(args.iterations): arguments: dict[str, Any] = {"query": "needle"} if index % 2: @@ -192,6 +217,18 @@ def main() -> None: next_id += 1 tool_payload(tool_call(server, next_id, "rebuild_index", {})) next_id += 1 + ranked_after_rebuild = tool_payload( + tool_call( + server, + next_id, + "search_messages", + {"query": "needle target", "limit": 100}, + ) + )["results"] + next_id += 1 + assert [item["message_id"] for item in ranked_after_rebuild] == [ + message_id for message_id in ranked_ids_before if message_id != message_ids[0] + ] assert tool_payload(tool_call(server, next_id, "get_system_health", {}))["status"] == "OK" next_id += 1 diff --git a/tests/search_index_benchmark.c b/tests/search_index_benchmark.c new file mode 100644 index 0000000..f17335a --- /dev/null +++ b/tests/search_index_benchmark.c @@ -0,0 +1,110 @@ +#include "domain/message.h" +#include "domain/search.h" + +#include +#include +#include +#include + +#ifdef _WIN32 +#include +#include +#endif + +#include "base/allocator.h" + +static double +now_milliseconds(void) +{ + struct timespec value; + timespec_get(&value, TIME_UTC); + return (double)value.tv_sec * 1000.0 + (double)value.tv_nsec / 1000000.0; +} + +static uint64_t +peak_working_set(void) +{ +#ifdef _WIN32 + PROCESS_MEMORY_COUNTERS counters; + if (GetProcessMemoryInfo(GetCurrentProcess(), &counters, sizeof(counters))) + { + return (uint64_t)counters.PeakWorkingSetSize; + } +#endif + return 0; +} + +static char * +make_content(size_t size) +{ + static const char alphabet[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 "; + uint32_t state = UINT32_C(0x9e3779b9); + char *content; + size_t position; + if (size == SIZE_MAX) + { + return NULL; + } + content = malloc(size + 1); + if (!content) + { + return NULL; + } + for (position = 0; position < size; ++position) + { + state = state * UINT32_C(1664525) + UINT32_C(1013904223); + content[position] = alphabet[state % (sizeof(alphabet) - 1)]; + } + content[size] = '\0'; + return content; +} + +int +main(int argc, char **argv) +{ + tiny_message_t message; + size_t size, iterations, iteration; + char *content; + double started, elapsed; + if (argc != 3) + { + fprintf(stderr, "usage: %s SIZE_BYTES ITERATIONS\n", argv[0]); + return 2; + } + size = (size_t)strtoull(argv[1], NULL, 10); + iterations = (size_t)strtoull(argv[2], NULL, 10); + if (size == 0 || size > TINY_CONTENT_MAX || iterations == 0) + { + fprintf(stderr, "size or iterations is out of range\n"); + return 2; + } + content = make_content(size); + if (!content) + { + return 1; + } + tiny_message_init(&message); + message.content = content; + started = now_milliseconds(); + for (iteration = 0; iteration < iterations; ++iteration) + { + tiny_search_index_t *index = tiny_search_index_create(); + if (!index || !tiny_search_index_add(index, &message, 0)) + { + tiny_search_index_free(index); + free(content); + return 1; + } + tiny_search_index_free(index); + } + elapsed = now_milliseconds() - started; + printf("{\"size_bytes\":%zu,\"iterations\":%zu,\"total_ms\":%.3f," + "\"mean_ms\":%.3f,\"peak_working_set_bytes\":%llu}\n", + size, + iterations, + elapsed, + elapsed / (double)iterations, + (unsigned long long)peak_working_set()); + free(content); + return tiny_allocator_outstanding() == 0 ? 0 : 1; +} diff --git a/tests/search_index_test.c b/tests/search_index_test.c new file mode 100644 index 0000000..5a477ad --- /dev/null +++ b/tests/search_index_test.c @@ -0,0 +1,161 @@ +#include "domain/message.h" +#include "domain/search.h" + +#include +#include +#include +#include + +#include "base/allocator.h" + +static int failures; + +#define CHECK(value) \ + do \ + { \ + if (!(value)) \ + { \ + fprintf(stderr, "CHECK failed at line %d: %s\n", __LINE__, #value); \ + failures++; \ + } \ + } \ + while (0) + +static tiny_message_t +make_message(const char *content, char **tags, size_t tag_count) +{ + tiny_message_t message; + tiny_message_init(&message); + message.content = (char *)content; + message.metadata.tags = tags; + message.metadata.tag_count = tag_count; + return message; +} + +static bool +candidate_contains(tiny_search_index_t *index, const char *query, size_t expected) +{ + size_t *candidates = NULL; + size_t count = 0, position; + bool found = false; + if (!tiny_search_index_candidates(index, query, &candidates, &count)) + { + return false; + } + for (position = 0; position < count; ++position) + { + if (candidates[position] == expected) + { + found = true; + break; + } + } + free(candidates); + return found; +} + +static void +test_collision_rehash_and_unicode(void) +{ + tiny_search_index_t *index = tiny_search_index_create(); + char contents[300][4]; + size_t position; + char *tags[] = { "設計メモ" }; + tiny_message_t tagged = make_message("tagged content", tags, 1); + tiny_message_t duplicate = make_message("aaaaaa", NULL, 0); + size_t *candidates = NULL; + size_t count = 0; + + CHECK(index != NULL); + for (position = 0; index && position < 300; ++position) + { + tiny_message_t message; + contents[position][0] = (char)('a' + (position / (26 * 26)) % 26); + contents[position][1] = (char)('a' + (position / 26) % 26); + contents[position][2] = (char)('a' + position % 26); + contents[position][3] = '\0'; + message = make_message(contents[position], NULL, 0); + CHECK(tiny_search_index_add(index, &message, position)); + } + for (position = 0; index && position < 300; ++position) + { + CHECK(candidate_contains(index, contents[position], position)); + } + + CHECK(tiny_search_index_add(index, &tagged, 300)); + CHECK(candidate_contains(index, "設計", 300)); + CHECK(candidate_contains(index, "TAGGED", 300)); + CHECK(tiny_search_index_add(index, &duplicate, 301)); + CHECK(tiny_search_index_candidates(index, "aaa", &candidates, &count)); + { + size_t duplicate_hits = 0; + for (position = 0; position < count; ++position) + { + if (candidates[position] == 301) + { + duplicate_hits++; + } + } + CHECK(duplicate_hits == 1); + } + free(candidates); + candidates = NULL; + CHECK(tiny_search_index_candidates(index, "a", &candidates, &count)); + CHECK(count == 302); + free(candidates); + tiny_search_index_free(index); +} + +static void +test_transactional_allocation_failure(void) +{ + const tiny_message_t baseline = make_message("baseline-only", NULL, 0); + char *tags[] = { "transaction-tag", "日本語追加" }; + const tiny_message_t addition + = make_message("zyxwvutsrqponmlkjihgfedcba-transactional-new-token", tags, 2); + size_t failure_index; + bool reached_success = false; + + for (failure_index = 0; failure_index < 512; ++failure_index) + { + tiny_search_index_t *index; + size_t baseline_allocations = tiny_allocator_outstanding(); + tiny_allocator_reset(); + index = tiny_search_index_create(); + CHECK(index != NULL); + CHECK(tiny_search_index_add(index, &baseline, 0)); + + tiny_allocator_fail_after(failure_index); + if (tiny_search_index_add(index, &addition, 1)) + { + tiny_allocator_reset(); + CHECK(candidate_contains(index, "transactional-new-token", 1)); + reached_success = true; + tiny_search_index_free(index); + CHECK(tiny_allocator_outstanding() == baseline_allocations); + break; + } + + tiny_allocator_reset(); + CHECK(candidate_contains(index, "baseline-only", 0)); + CHECK(!candidate_contains(index, "transactional-new-token", 1)); + CHECK(tiny_search_index_add(index, &addition, 1)); + CHECK(candidate_contains(index, "transactional-new-token", 1)); + tiny_search_index_free(index); + CHECK(tiny_allocator_outstanding() == baseline_allocations); + } + CHECK(reached_success); +} + +int +main(void) +{ + tiny_allocator_reset(); + CHECK(tiny_allocator_outstanding() == 0); + test_collision_rehash_and_unicode(); + CHECK(tiny_allocator_outstanding() == 0); + test_transactional_allocation_failure(); + tiny_allocator_reset(); + CHECK(tiny_allocator_outstanding() == 0); + return failures == 0 ? 0 : 1; +} -- cgit v1.2.3