Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

[Experiment] Bitmap-based tool index for O(1) filtering#1637

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Closed
SamMorrowDrums wants to merge5 commits intomainfromperf/bitmap-index

Conversation

@SamMorrowDrums
Copy link
Collaborator

⚠️ Experimental

This is anexperiment exploring bitmap-based indexing for efficient tool filtering. Not intended for immediate merge - just capturing the approach for discussion.

Problem

In stateless server patterns, we rebuild tool lists per-request. With ~130 tools and multiple filter dimensions (toolsets, read-only, feature flags), filtering becomes O(n × filters).

Approach

Pre-compute bitmaps at startup, then use bitwise operations for O(1) filtering:

// Build once at startupindex:=BuildToolIndex(allTools)// Per-request: ~78ns, 0 allocationsresult:=index.Query(QueryConfig{Toolsets: []string{"repos","issues"},ReadOnly:true,})// Materialize only when needed: ~1µs for 130 toolstools:=index.Materialize(ctx,result)

What's included

  1. bitmap.go -ToolBitmap type (256-bit, 4×uint64) with Set/And/Or/Iterate
  2. tool_index.go - Pre-computed index withQuery() andMaterialize()
  3. tool_variants.go - Simple override mechanism for tools with variant definitions

Benchmarks

Query (130 tools, 2 toolsets):     78ns    0 allocsMaterialize (full list):        1114ns    3 allocsToolOverrides.ApplyToTools:    ~18µs    ~130 allocs (condition funcs)

Key design decisions

  • 256-tool limit via fixed bitmap size (expandable if needed)
  • Lazy allocation inApplyToTools - no allocs when no overrides match
  • Pointer returns from Materialize to avoid struct copies
  • Simple ToolOverrides instead of full VariantIndex (only 2 tools need variants)

Open questions

  • Is this level of optimization needed for the local server?
  • How does this integrate with the remote server's caching?
  • Should we exposeToolIndex publicly or keep it internal?

This implements a high-performance bitmap index for tool filtering:- ToolBitmap: 256-bit bitmap (4 uint64s) with O(1) set operations- ToolIndex: Pre-computed index for toolset, read-only, and feature flag filtering- Query: Returns guaranteed tools + those needing dynamic checks- Materialize: Only runs dynamic Enabled() checks on survivorsPerformance benchmarks:- Query (2 toolsets): 78 ns/op, 0 allocs- Query (all toolsets): 44 ns/op, 0 allocs- Bitmap OR/AND: <0.3 ns/op- Full query + materialize (130 tools): 5.4 µs/op, 4 allocsKey insight: Static filters (toolset, read-only, feature flags) can bepre-computed as bitmaps. Dynamic Enabled() checks are only run on toolsthat survive static filtering, avoiding wasteful checks on tools thatwould be filtered out anyway.
Adds two new methods to ToolIndex:- UniqueFeatureFlags(): Returns all unique feature flags used by tools- QueryWithFeatureChecker(): Queries with automatic flag checkingKey optimization: Instead of checking the same feature flag N timesfor N tools that use it, each unique flag is checked exactly once.For example, if 50 tools use 3 unique flags, this reduces feature flagservice calls from O(50) to O(3).Test demonstrates: 50 tools using 3 flags results in exactly 3 checks.
Change Materialize() to return []*ServerTool instead of []ServerTool.This avoids copying the entire ServerTool struct (which includes theJSON schema) for each tool in the result.Benchmark improvement:- Materialize: 6199ns → 1114ns (5.6x faster)- Memory: 12584B → 472B (27x less)- Allocations: 4 → 3The returned pointers reference the cached tools in the index.Callers must not modify them.
Provides a lightweight mechanism for tools that have different definitionsbased on runtime conditions (e.g., feature flags, capabilities).Designed for the small number of tools (~2) that need variant handling:- ToolOverride: condition + replacement definition- ToolOverrides: map[string]ToolOverride with Apply() and ApplyToTools()- Lazy allocation: no allocs when no overrides matchThis is intentionally simple - only 60 lines - because most tools don'tneed variants and the full VariantIndex would be overkill.
@SamMorrowDrums
Copy link
CollaboratorAuthor

Superseded by a cleaner implementation that encapsulates bitmask complexity behind a composable EnableCondition API. See upcoming PR.

Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment

Reviewers

Copilot code reviewCopilotAwaiting requested review from CopilotCopilot will automatically review once the pull request is marked ready for review

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@SamMorrowDrums

[8]ページ先頭

©2009-2025 Movatter.jp