| | 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 | | { |
| 17 | 35 | | var compiledItems = specification.GetCompiledItems(); |
| 18 | 36 | | if (compiledItems.Length == 0) return source; |
| | 37 | |
|
| 44 | 38 | | var startIndexLikeItems = Array.FindIndex(compiledItems, item => item.Type == ItemType.Like); |
| 23 | 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. |
| 9 | 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 | |
|
| 10 | 53 | | public SpecLikeIterator(IEnumerable<TSource> source, SpecItem[] compiledItems, int startIndex) |
| | 54 | | { |
| | 55 | | Debug.Assert(source != null); |
| | 56 | | Debug.Assert(compiledItems != null); |
| 10 | 57 | | _source = source; |
| 10 | 58 | | _compiledItems = compiledItems; |
| 10 | 59 | | _startIndex = startIndex; |
| 10 | 60 | | } |
| | 61 | |
|
| | 62 | | public override Iterator<TSource> Clone() |
| 1 | 63 | | => new SpecLikeIterator<TSource>(_source, _compiledItems, _startIndex); |
| | 64 | |
|
| | 65 | | public override void Dispose() |
| | 66 | | { |
| 20 | 67 | | if (_enumerator is not null) |
| | 68 | | { |
| 10 | 69 | | _enumerator.Dispose(); |
| 10 | 70 | | _enumerator = null; |
| | 71 | | } |
| 20 | 72 | | base.Dispose(); |
| 20 | 73 | | } |
| | 74 | |
|
| | 75 | | public override bool MoveNext() |
| | 76 | | { |
| 35 | 77 | | switch (_state) |
| | 78 | | { |
| | 79 | | case 1: |
| 10 | 80 | | _enumerator = _source.GetEnumerator(); |
| 10 | 81 | | _state = 2; |
| | 82 | | goto case 2; |
| | 83 | | case 2: |
| | 84 | | Debug.Assert(_enumerator is not null); |
| 35 | 85 | | var likeItems = _compiledItems.AsSpan()[_startIndex.._compiledItems.Length]; |
| 45 | 86 | | while (_enumerator.MoveNext()) |
| | 87 | | { |
| 35 | 88 | | TSource sourceItem = _enumerator.Current; |
| 35 | 89 | | if (IsValid(sourceItem, likeItems)) |
| | 90 | | { |
| 25 | 91 | | _current = sourceItem; |
| 25 | 92 | | return true; |
| | 93 | | } |
| | 94 | | } |
| | 95 | |
|
| 10 | 96 | | Dispose(); |
| | 97 | | break; |
| | 98 | | } |
| | 99 | |
|
| 10 | 100 | | return false; |
| | 101 | | } |
| | 102 | |
|
| | 103 | | private static bool IsValid<T>(T sourceItem, ReadOnlySpan<SpecItem> span) |
| | 104 | | { |
| 35 | 105 | | var valid = true; |
| 35 | 106 | | var groupStart = 0; |
| | 107 | |
|
| 150 | 108 | | for (var i = 1; i <= span.Length; i++) |
| | 109 | | { |
| | 110 | | // If we reached the end of the span or the group has changed, we slice and process the group. |
| 50 | 111 | | if (i == span.Length || span[i].Bag != span[groupStart].Bag) |
| | 112 | | { |
| 39 | 113 | | var validOrGroup = IsValidInOrGroup(sourceItem, span[groupStart..i]); |
| 39 | 114 | | if ((valid = valid && validOrGroup) is false) |
| | 115 | | { |
| | 116 | | break; |
| | 117 | | } |
| 29 | 118 | | groupStart = i; |
| | 119 | | } |
| | 120 | | } |
| | 121 | |
|
| 35 | 122 | | return valid; |
| | 123 | |
|
| | 124 | | static bool IsValidInOrGroup(T sourceItem, ReadOnlySpan<SpecItem> span) |
| | 125 | | { |
| 39 | 126 | | var validOrGroup = false; |
| 143 | 127 | | foreach (var specItem in span) |
| | 128 | | { |
| 47 | 129 | | if (specItem.Reference is not SpecLikeCompiled<T> specLike) continue; |
| | 130 | |
|
| 47 | 131 | | if (specLike.KeySelector(sourceItem)?.Like(specLike.Pattern) ?? false) |
| | 132 | | { |
| 29 | 133 | | validOrGroup = true; |
| 29 | 134 | | break; |
| | 135 | | } |
| | 136 | | } |
| 39 | 137 | | return validOrGroup; |
| | 138 | | } |
| | 139 | | } |
| | 140 | | } |
| | 141 | | } |