SearchValues i FrozenCollections w .NET 8 do optymalizacji

Optymalizacja wyszukiwania w .NET 8: SearchValues i FrozenCollections dla gorących ścieżek

W .NET 8 pojawiły się SearchValues<T> i kolekcje FrozenSet<T>/FrozenDictionary<TKey, TValue>, które minimalizują narzuty w gorących ścieżkach. Te struktury wykonują ciężką optymalizację przy tworzeniu, zapewniając stałą prędkość wyszukiwania bez powtórnych analiz. Nadają się dla wysokonakładanych aplikacji z milionami operacji.

Optymalizacja wyszukiwania symboli z SearchValues

Standardowy string.IndexOfAny analizuje zbiór symboli przy każdym wywołaniu, co akumuluje narzuty w pętlach. SearchValues<char> jest tworzony raz i buforuje optymalną strategię wyszukiwania.

Przy inicjalizacji .NET wykonuje:

• Analizę wejściowego zbioru (pojedynczy symbol, zakres, zbiór).
• Wybór algorytmu z uwzględnieniem SIMD (AVX2, SSE2).
• Budowę struktur danych (maski bitowe, tablice haszujące).

SearchValues<char> separators = SearchValues.Create(".,;!?");
ReadOnlySpan<char> input = "Hello, world!";
int index = input.IndexOfAny(separators);

Strategie wyszukiwania zależą od danych:

• Pojedynczy symbol — weryfikacja wektorowa.
• Zakres (0-9A-Z) — maska bitowa O(1).
• Mały zbiór (≤4 symbole) — SIMD.
• Duży zbiór — zoptymalizowana tablica haszująca.

Benchmarki demonstrują przyspieszenie:

| Scenariusz | IndexOfAny | SearchValues | Przyspieszenie |

|----------|------------|--------------|----------------|

| Krótki ciąg znaków | ~5 ns | ~5 ns | 1x |

| Długi ciąg znaków (2000 symboli) | ~52 ns | ~4 ns | ~13x |

Korzyść jest maksymalna dla ciągów >100 symboli dzięki wykluczeniu powtórnej analizy.

FrozenCollections: niezmienne tablice haszujące

HashSet<T> i Dictionary<TKey, TValue> niosą narzuty z powodu wsparcia mutacji: przehaszowanie, kontrole granic. FrozenSet<T> i FrozenDictionary<TKey, TValue> są zoptymalizowane dla scenariuszy tylko do odczytu.

Przy tworzeniu:

• Analiza kluczy dla funkcji doskonałego haszowania bez kolizji.
• Przyjazne dla cache rozmieszczenie danych.
• Usunięcie runtime-sprawdzeń niezmienności.

Dla małych kolekcji stosuje się maskę bitową zamiast hasza.

var dict = Enumerable.Range(0, 100000)
    .ToFrozenDictionary(x => x, x => $"Value {{x}}");

if (dict.TryGetValue(42, out string? value))
{
    Console.WriteLine(value);
}

Benchmarki (100 000 elementów):

| Operacja | Dictionary | HashSet | FrozenDictionary | FrozenSet |

|----------|------------|---------|------------------|-----------|

| TryGetValue/Contains | 3.78 ns | 4.47 ns | 1.87 ns | 3.37 ns |

FrozenDictionary jest 2 razy szybszy niż standardowy Dictionary.

Scenariusze zastosowania

SearchValues:

• Miliony wyszukiwań w stałym zbiorze.
• Parsowanie logów, tokenizacja, walidacja.
• Długie ciągi znaków (>100 symboli).

FrozenCollections:

• Statyczne konfiguracje przy starcie.
• Tablice odsyłaczy (kody błędów, statusy).
• Obciążenia read-heavy z tysiącami odczytów.

Unikaj przy częstych mutacjach lub rzadkich wywołaniach — narzuty na stworzenie przewyższą korzyść.

Praktyczna implementacja

Buforuj na poziomie aplikacji:

public static class AppCache
{
    public static readonly SearchValues<char> UrlSafeChars = 
        SearchValues.Create("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-._~");
    
    public static readonly FrozenSet<string> ValidCurrencies = 
        new[] { "USD", "EUR", "GBP", "JPY", "CNY" }.ToFrozenSet();
}

Przykład walidacji:

• Email: SearchValues<char> invalidEmailChars = SearchValues.Create("()<>[]:;@\\,?\"");
• TLD: FrozenSet<string> validTlds = LoadTldsFromConfig().ToFrozenSet();

Zawsze sprawdzaj profilowaniem przez BenchmarkDotNet: opłacalność zależy od ilości operacji.

Co jest ważne

• SearchValues przyspiesza wyszukiwanie w 13x na długich ciągach znaków dzięki jednorazowej optymalizacji.
• FrozenDictionary daje 2x wzrost w TryGetValue w porównaniu z Dictionary.
• Oba narzędzia nadają się dla niezmiennych zbiorów w gorących ścieżkach.
• Wymagają profilowania: nieefektywne dla rzadkich wywołań.
• Wspierają SIMD i doskonałe haszowanie dla programistów middle/senior.

— Editorial Team