Optimizing String Searches in C# with SearchValues
Tags: dotnet, csharp, performance, programming
Published: 2024-04-18 18:13:22

Searching arrays for specific values is a common task in programming. In some cases, like searching paths (e.g., Owner.Name.Title), it's necessary to efficiently locate characters like the dot ('.'). In other situations, such as tokenization systems, you might need to search large amounts of text for markers that indicate where to replace values with tokens. In all these cases, a bit of preparation can significantly improve performance.


## Advantages of Vectorization
Modern CPUs often offer vector processing capabilities, which allow processing multiple values simultaneously with a single instruction. This feature can be used to speed up array searches. Although .NET provides a method called `IndexOfAny`, which can find the first occurrence of any of the specified characters, optimizing this method depends on the specifics of the search task. Let’s say we need to find the first occurrence of a dot in a string.

```
string path = "Owner.Name.Title";
int indexOfFirstDot = path.IndexOf('.');
```

## Complex Scenarios and SearchValues
For more complex searches, where you need to identify the first occurrence of any character from a wide range, we can use `SearchValues`. Here’s how we might use `SearchValues` for searching alphanumeric characters.

```
SearchValues<char> alphaNumeric = SearchValues.Create("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz");

int indexOfFirstAlphaNumeric = path.AsSpan().IndexOfAny(alphaNumeric);
```

NET analyzes the input to determine which of the available search techniques will work best, leading to a more optimal strategy for specific scenarios.

## Why is SearchValues Faster?
`SearchValues<T>` allows separating the work of choosing a search strategy from the search itself. When we define `SearchValues<char>` for alphanumeric characters, .NET uses an implementation optimized for that case, which includes vector processing where applicable.

## Benchmark Design and Results
Our benchmark was designed to demonstrate the efficiency of using `SearchValues<T>` with the BenchmarkDotNet library, a standard for measurable performance tests in the .NET community.

We tested three different search methods on strings of various lengths:

**IndexOfFirstAlphaNumericSimple**: Searching a simple string "Owner.Name.Title" for any alphanumeric character.

**IndexOfFirstAlphaNumericLong**: Searching a long string of 2062 characters for any alphanumeric character.

IndexOfSearchValuesLong: Searching the same long string using SearchValues for optimization.


![Benchmark Results](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uzjxcbub4b506k4i0y1w.png)


## Interpretation
In our benchmark test, we wanted to see how well the `SearchValues `method performs compared to other methods when searching within strings. We set up a test using three different methods on strings of different lengths. Here’s a straightforward interpretation of what the benchmark results show:

IndexOfFirstAlphaNumericSimple: This method was used to find any alphanumeric character in a short and straightforward string, "Owner.Name.Title". It performed quite quickly, taking on average about 4.715 nanoseconds. This quick result shows that for short strings, this method is very efficient.

**IndexOfFirstAlphaNumericLong**: Here, we tested the same search on a much longer string of 2062 characters. The average time it took was about 52.356 nanoseconds. This indicates that as the string length increases, finding a character towards the end becomes significantly slower using this standard method.

**IndexOfSearchValuesLong**: Using the SearchValues method on the same long string of 2062 characters, the time taken dropped significantly to an average of 4.076 nanoseconds. This shows a dramatic improvement and suggests that SearchValues is much more efficient, especially for longer strings.

## What This Means
The results clearly show that the SearchValues method outperforms the standard search when dealing with longer strings. It's particularly effective because it can handle large data efficiently by using modern CPU features like vector processing. This means that if you're working with large amounts of text, using SearchValues can greatly speed up how quickly you can find characters or sequences, making your applications faster and more responsive.

## Application in AI
The concepts discussed in optimizing string searches with SearchValues can be quite beneficial in the development and performance optimization of AI applications, especially those involving large-scale data processing or natural language processing tasks. Here's how these principles can be applied: Efficient

AI often requires the handling of large datasets, including textual data. Efficient searching and processing mechanisms like SearchValues can reduce the computational time for tasks such as tokenization, parsing, or searching within large corpora of text, which are common in natural language processing (NLP).

In another hand the use of vector processing (SIMD - Single Instruction, Multiple Data) capabilities in modern CPUs can be leveraged in AI to speed up operations that can be parallelized. This is similar to how deep learning frameworks optimize matrix operations, which are fundamental to neural network computations. Implementing vectorized operations for pre-processing steps can significantly enhance the overall performance of AI systems.

## For the end
`SearchValues<T>` represents a powerful tool within the .NET environment that uses advanced techniques such as vector processing to optimize string searches. With each new release, .NET continues to improve performance, providing developers with better tools for building more efficient and faster applications. In the realm of AI, these techniques can be crucial in achieving scalability and efficiency, particularly when dealing with complex and large datasets.

GitHub Link: https://github.com/admir-live/SearchValues-Benchmark