- Notifications
You must be signed in to change notification settings - Fork3.2k
[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
Uh oh!
There was an error while loading.Please reload this page.
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
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.
CollaboratorAuthor
SamMorrowDrums commentedDec 18, 2025
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
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
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:
What's included
bitmap.go-ToolBitmaptype (256-bit, 4×uint64) with Set/And/Or/Iteratetool_index.go- Pre-computed index withQuery()andMaterialize()tool_variants.go- Simple override mechanism for tools with variant definitionsBenchmarks
Key design decisions
ApplyToTools- no allocs when no overrides matchOpen questions
ToolIndexpublicly or keep it internal?