| | | 1 | | using System.Diagnostics; |
| | | 2 | | |
| | | 3 | | namespace Pozitron.QuerySpecification; |
| | | 4 | | |
| | | 5 | | /* |
| | | 6 | | public IEnumerable<T> Evaluate<T>(IEnumerable<T> source, Specification<T> specification) |
| | | 7 | | { |
| | | 8 | | foreach (var likeGroup in specification.LikeExpressions.GroupBy(x => x.Group)) |
| | | 9 | | { |
| | | 10 | | source = source.Where(x => likeGroup.Any(c => c.KeySelectorFunc(x)?.Like(c.Pattern) ?? false)); |
| | | 11 | | } |
| | | 12 | | return source; |
| | | 13 | | } |
| | | 14 | | This was the previous implementation. We're trying to avoid allocations of LikeExpressions, GroupBy and LINQ. |
| | | 15 | | The new implementation preserves the behavior and reduces allocations drastically. |
| | | 16 | | We've implemented a custom iterator. Also, instead of GroupBy, we have a single array sorted by group, and we slice |
| | | 17 | | For source of 1000 items, the allocations are reduced from 257.872 bytes to only 64 bytes (the cost of the iterator |
| | | 18 | | */ |
| | | 19 | | |
| | | 20 | | /// <summary> |
| | | 21 | | /// Represents an in-memory evaluator for "Like" expressions. |
| | | 22 | | /// </summary> |
| | | 23 | | [EvaluatorDiscovery(Order = 20)] |
| | | 24 | | public sealed class LikeMemoryEvaluator : IMemoryEvaluator |
| | | 25 | | { |
| | | 26 | | /// <summary> |
| | | 27 | | /// Gets the singleton instance of the <see cref="LikeMemoryEvaluator"/> class. |
| | | 28 | | /// </summary> |
| | 2 | 29 | | public static LikeMemoryEvaluator Instance = new(); |
| | 4 | 30 | | private LikeMemoryEvaluator() { } |
| | | 31 | | |
| | | 32 | | /// <inheritdoc/> |
| | | 33 | | public IEnumerable<T> Evaluate<T>(IEnumerable<T> source, Specification<T> specification) |
| | | 34 | | { |
| | 18 | 35 | | var compiledItems = specification.GetCompiledItems(); |
| | 19 | 36 | | if (compiledItems.Length == 0) return source; |
| | | 37 | | |
| | 46 | 38 | | var startIndexLikeItems = Array.FindIndex(compiledItems, item => item.Type == ItemType.Like); |
| | 24 | 39 | | if (startIndexLikeItems == -1) return source; |
| | | 40 | | |
| | | 41 | | // The like items are contiguously placed as a last segment in the array and are already sorted by group. |
| | 10 | 42 | | return new SpecLikeIterator<T>(source, compiledItems, startIndexLikeItems); |
| | | 43 | | } |
| | | 44 | | |
| | | 45 | | private sealed class SpecLikeIterator<TSource> : Iterator<TSource> |
| | | 46 | | { |
| | | 47 | | private readonly IEnumerable<TSource> _source; |
| | | 48 | | private readonly SpecItem[] _compiledItems; |
| | | 49 | | private readonly int _startIndex; |
| | | 50 | | |
| | | 51 | | private IEnumerator<TSource>? _enumerator; |
| | | 52 | | |
| | 12 | 53 | | public SpecLikeIterator(IEnumerable<TSource> source, SpecItem[] compiledItems, int startIndex) |
| | | 54 | | { |
| | | 55 | | Debug.Assert(source != null); |
| | | 56 | | Debug.Assert(compiledItems != null); |
| | 12 | 57 | | _source = source; |
| | 12 | 58 | | _compiledItems = compiledItems; |
| | 12 | 59 | | _startIndex = startIndex; |
| | 12 | 60 | | } |
| | | 61 | | |
| | | 62 | | public override Iterator<TSource> Clone() |
| | 2 | 63 | | => new SpecLikeIterator<TSource>(_source, _compiledItems, _startIndex); |
| | | 64 | | |
| | | 65 | | public override void Dispose() |
| | | 66 | | { |
| | 24 | 67 | | if (_enumerator is not null) |
| | | 68 | | { |
| | 12 | 69 | | _enumerator.Dispose(); |
| | 12 | 70 | | _enumerator = null; |
| | | 71 | | } |
| | 24 | 72 | | base.Dispose(); |
| | 24 | 73 | | } |
| | | 74 | | |
| | | 75 | | public override bool MoveNext() |
| | | 76 | | { |
| | 39 | 77 | | switch (_state) |
| | | 78 | | { |
| | | 79 | | case 1: |
| | 12 | 80 | | _enumerator = _source.GetEnumerator(); |
| | 12 | 81 | | _state = 2; |
| | | 82 | | goto case 2; |
| | | 83 | | case 2: |
| | | 84 | | Debug.Assert(_enumerator is not null); |
| | 39 | 85 | | var likeItems = _compiledItems.AsSpan()[_startIndex.._compiledItems.Length]; |
| | 55 | 86 | | while (_enumerator.MoveNext()) |
| | | 87 | | { |
| | 43 | 88 | | TSource sourceItem = _enumerator.Current; |
| | 43 | 89 | | if (IsValid(sourceItem, likeItems)) |
| | | 90 | | { |
| | 27 | 91 | | _current = sourceItem; |
| | 27 | 92 | | return true; |
| | | 93 | | } |
| | | 94 | | } |
| | | 95 | | |
| | 12 | 96 | | Dispose(); |
| | | 97 | | break; |
| | | 98 | | } |
| | | 99 | | |
| | 12 | 100 | | return false; |
| | | 101 | | } |
| | | 102 | | |
| | | 103 | | private static bool IsValid<T>(T sourceItem, ReadOnlySpan<SpecItem> span) |
| | | 104 | | { |
| | 43 | 105 | | var groupStart = 0; |
| | 170 | 106 | | for (var i = 1; i <= span.Length; i++) |
| | | 107 | | { |
| | | 108 | | // If we reached the end of the span or the group has changed, we slice and process the group. |
| | 58 | 109 | | if (i == span.Length || span[i].Bag != span[groupStart].Bag) |
| | | 110 | | { |
| | 47 | 111 | | if (IsValidInOrGroup(sourceItem, span[groupStart..i]) is false) |
| | | 112 | | { |
| | 16 | 113 | | return false; |
| | | 114 | | } |
| | 31 | 115 | | groupStart = i; |
| | | 116 | | } |
| | | 117 | | } |
| | 27 | 118 | | return true; |
| | | 119 | | |
| | | 120 | | static bool IsValidInOrGroup(T sourceItem, ReadOnlySpan<SpecItem> span) |
| | | 121 | | { |
| | 173 | 122 | | foreach (var specItem in span) |
| | | 123 | | { |
| | 55 | 124 | | if (specItem.Reference is not SpecLikeCompiled<T> specLike) continue; |
| | | 125 | | |
| | 55 | 126 | | if (specLike.KeySelector(sourceItem)?.Like(specLike.Pattern) ?? false) |
| | | 127 | | { |
| | 31 | 128 | | return true; |
| | | 129 | | } |
| | | 130 | | } |
| | 16 | 131 | | return false; |
| | | 132 | | } |
| | | 133 | | } |
| | | 134 | | } |
| | | 135 | | } |