FastSearch 1.1.0

FastSearch

Lightning-fast, low-memory substring search for .NET

FastSearch is an open-source C# library for case-insensitive substring search ("contains" search) over in-memory collections of objects: autocomplete, type-ahead, filtering, and lookups across millions of items.

✨ Features

• Effortless searching: case-insensitive substring matches across large lists of objects through one interface, ISearch<T>.
• Multiple search algorithms:
  • NGramSearch (new in 1.1, recommended): compressed n-gram posting lists. At 1M items it indexes in about 1 s with 47 MiB of memory, and answers a typical random query in about 5 µs. That is 30× less memory than the trie and 20× faster than the suffix array on cold queries.
  • SuffixArraySearch (new in 1.1): generalized suffix array with a 1/2/3-character prefix table. Fastest at enumerating very broad results; memoizes broad queries.
  • CharSequenceSearch: suffix trie with a precomputed result list at every node. Fastest for narrow queries, but memory grows as O(N·L²) (1.5 GiB at 1M items).
  • HashSearch: precomputed hash of every substring. Speed is similar to the trie, and it uses the most memory.
  • LinqSearch: parallel LINQ scan over lowercased copies of the strings, with no index.
  • StringSearch: single-threaded Contains scan, with no index. Used as the baseline the other algorithms are checked against.
• Customizable object representation: override ToString() or pass a custom index function that returns the strings to index for each item.

🚀 Quick Start

1. Install the FastSearch package from NuGet: dotnet add package FastSearch.
2. Override ToString() on your objects, or pass an index function.
3. Create an NGramSearch with your IEnumerable<T>, then call Search.

var search = new NGramSearch<Customer>(customers, c => new[] { c.Name, c.Email });
ICollection<Customer> hits = search.Search("phoe"); // case-insensitive substring match, input order, no duplicates

Targets: net10.0 (.NET 10 LTS). Version 1.1 drops netstandard2.1, because every .NET runtime it served (.NET Core 3.x through .NET 9) is out of support or reaches end of support in November 2026. Stay on FastSearch 1.0.16 if you need an older runtime. The tests, benchmarks and the WPF sample also target .NET 10.

Which algorithm should I use?

NGramSearch, SuffixArraySearch, CharSequenceSearch, HashSearch, and LinqSearch capture indexed text at construction. Rebuild them when the source collection or indexed fields change. LinqSearch still allocates lowercased string copies; its lack of a substring index does not mean zero memory.

Algorithm specifications

• NGramSearch: compressed posting lists and candidate verification.
• SuffixArraySearch: sorted suffixes, prefix tables, and bounded result caching.
• CharSequenceSearch: suffix trie and optional exact matching.
• HashSearch: substring hashes with collision checking.
• LinqSearch: parallel scan over lowercased text snapshots.
• StringSearch: direct scan and correctness baseline.

How NGramSearch works

• Index: every distinct 1-, 2- and 3-character substring of an item, plus every 4-character substring shared by 16 or more items, maps to the sorted list of item ids that contain it. Each list is delta + varint encoded (about 1–2 bytes per entry), or stored as a bitmap when that's smaller.
• Short queries (1–3 characters, and common 4-character ones): answered exactly from a single list. There's no sorting, no de-duplication and no cache. The result is a lazy read-only view; its Count is known up front and items are decoded as you enumerate them.
• Longer queries: intersect the rarest gram lists, then verify the few remaining candidates against a compact lowercased copy of the text (1 byte per character for Latin-1 text).
• Guarantees: results come back in input order with no duplicates, the index never grows after it's built, and concurrent searches are safe.
• Full details: NGramSearch-Spec.md. The suffix trie is described in CharSequenceSearch-Spec.md.

Performance & Memory (v1.1, .NET 10)

All numbers are apples-to-apples. Every algorithm indexes the same items (the first N entries of the bundled 1M-password list, 7.5 characters on average) on the same machine with the same method, and each measurement runs in its own process.

• Index heap: GC.GetTotalMemory(true) after the build minus before it, with the input strings already loaded so they aren't counted for any algorithm.
• Heap after queries: the same measurement taken after the 1,000 random queries and the warm named-query workload. It includes SuffixArraySearch's bounded result cache. NGramSearch has no cache, so it doesn't retain query results.
• Latency: the named queries are averaged over 2,000 warm calls (20 for the scans) and include enumerating every result. The random mix is 1,000 cold queries of 1–8 characters and times the Search call only.
• JIT: all runs use DOTNET_TieredCompilation=0, so every algorithm runs fully optimized code from the first call.

Memory vs. items stored

Search latency (sequential query calls; LinqSearch uses parallel workers)

How to read this

• Memory: NGramSearch needs about 7 bytes per indexed character on 100k items and above (more on small lists, where fixed overhead dominates), and it doesn't grow with queries. At 1M items that's 47 MiB, versus 83 MiB (121 MiB after queries) for SuffixArraySearch and 1.5–1.8 GiB for the trie and hash indexes.
• Build time: NGramSearch builds 1M items in about 1.2 s and SuffixArraySearch in about 0.6 s, versus 12–20 s for the trie and hash indexes.
• Typical queries: on the random mix, NGramSearch averages about 5 µs, which is close to the trie and hash indexes (1.5–2.2 µs) and 20× faster than SuffixArraySearch (103 µs). The suffix array has to collect and sort broad results before it can cache them.
• Narrow, long queries: the trie and hash indexes are still fastest (about 0.1–0.3 µs), because they store every possible answer ahead of time. NGramSearch takes about 1 µs.
• Very broad queries: enumerating hundreds of thousands of results dominates. SuffixArraySearch is fastest because it hands back a cached array; NGramSearch decodes its compressed list as you enumerate, which makes it slightly slower than the trie (1.6 ms versus 1.5 ms for a at 1M items).
• No index: LinqSearch and StringSearch use no index memory but scan everything on every query, taking milliseconds at 100k items and above.

Fixes to existing algorithms in 1.1

• Faster indexing: CharSequenceSearch and HashSearch checked for duplicates by scanning a List on every insert, which made indexing quadratic in the number of items. They now use an O(1) per-item visited set.
• Exact-match case bug: CharSequenceSearch exact-match mode compared mixed-case source strings to the lowercased query and missed matches. The comparison is now case-insensitive.
• Read-only results: CharSequenceSearch and HashSearch used to return their internal mutable lists, so a caller could corrupt the index. They now return read-only views.
• Consistent empty queries: all six algorithms return no results for null or empty queries.
• Protected empty results: the trie, hash, and LINQ implementations use fixed empty arrays, so callers cannot corrupt later searches by adding to a shared empty result.
• Concurrent cache updates: SuffixArraySearch synchronizes cache eviction and insertion to keep retained item references within its budget.
• Sample selection: the WPF sample times the selected algorithm and checks its result count against StringSearch outside the timed loop.

Test machine: Apple-silicon Mac, .NET 10.0, workstation GC. These are the recorded v1.1 results, not a new benchmark run. Absolute times and relative performance depend on hardware, data, query distribution, and cache state.

Reproduce

cd PasswordSearch.Benchmark
export DOTNET_TieredCompilation=0
dotnet run -c Release -- heap ngram 1000000   # string | linq | hash | charseq | suffixarray | ngram
dotnet run -c Release                         # BenchmarkDotNet suite (10k items, with MemoryDiagnoser)

Regenerate documentation charts from the README benchmark tables:

uv run scripts/generate_benchmark_charts.py

The generator updates the root benchmark PNGs and matching images in docs/images/. Update the README tables first when recording new measurements, then keep the website, specifications, and spreadsheets in sync.

Excel workbooks: FastSearch.xlsx and Search Results.xlsx include current benchmarks for all six algorithms at 10k, 100k, and 999,998 items, algorithm guidance, and measurement notes. Their original sheets retain historical results separately.

Why Choose FastSearch?

• User-Friendly: Designed with developers in mind, enabling you to integrate powerful search functionality with ease.
• Future-Proof: Regular updates and improvements ensure you have access to the latest searching techniques.

Enjoy the power of efficient searching with FastSearch!

Contributing

We welcome contributions! Please feel free to submit issues or pull requests.

• Branches: work on a release/* branch, open a pull request into develop, and develop reaches main only through a pull request.
• Checks: CI builds the solution with warnings as errors and runs the tests on every pull request.
• Releases: pushing a vX.Y.Z tag on main publishes the package to NuGet.

License

This project is licensed under the Apache License 2.0. See the LICENSE file for more details.

Credits

Created by Richard Crane — Microsoft MVP and founder of MILL5.

• MILL5: mill5.com
• Microsoft MVP profile: mvp.microsoft.com/…/Richard-Crane
• Podcast — Inventing Fire with AI: inventingfirewith.ai
• Support: rich@mill5.com

Powered by MILL5 Explore Richard Crane on Microsoft MVP Listen to the Inventing Fire with AI podcast for insights on technology and innovation. For support, contact: rich@mill5.com

_{Powered by RepoBeacon}