| | | 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 | | public sealed class LikeMemoryEvaluator : IInMemoryEvaluator |
| | | 24 | | { |
| | | 25 | | /// <summary> |
| | | 26 | | /// Gets the singleton instance of the <see cref="LikeMemoryEvaluator"/> class. |
| | | 27 | | /// </summary> |
| | 1 | 28 | | public static LikeMemoryEvaluator Instance = new(); |
| | 2 | 29 | | private LikeMemoryEvaluator() { } |
| | | 30 | | |
| | | 31 | | /// <inheritdoc/> |
| | | 32 | | public IEnumerable<T> Evaluate<T>(IEnumerable<T> source, Specification<T> specification) |
| | | 33 | | { |
| | 17 | 34 | | var compiledItems = specification.GetCompiledItems(); |
| | 18 | 35 | | if (compiledItems.Length == 0) return source; |
| | | 36 | | |
| | 44 | 37 | | var startIndexLikeItems = Array.FindIndex(compiledItems, item => item.Type == ItemType.Like); |
| | 23 | 38 | | if (startIndexLikeItems == -1) return source; |
| | | 39 | | |
| | | 40 | | // The like items are contiguously placed as a last segment in the array and are already sorted by group. |
| | 9 | 41 | | return new SpecLikeIterator<T>(source, compiledItems, startIndexLikeItems); |
| | | 42 | | } |
| | | 43 | | |
| | | 44 | | private sealed class SpecLikeIterator<TSource> : Iterator<TSource> |
| | | 45 | | { |
| | | 46 | | private readonly IEnumerable<TSource> _source; |
| | | 47 | | private readonly SpecItem[] _compiledItems; |
| | | 48 | | private readonly int _startIndex; |
| | | 49 | | |
| | | 50 | | private IEnumerator<TSource>? _enumerator; |
| | | 51 | | |
| | 10 | 52 | | public SpecLikeIterator(IEnumerable<TSource> source, SpecItem[] compiledItems, int startIndex) |
| | | 53 | | { |
| | | 54 | | Debug.Assert(source != null); |
| | | 55 | | Debug.Assert(compiledItems != null); |
| | 10 | 56 | | _source = source; |
| | 10 | 57 | | _compiledItems = compiledItems; |
| | 10 | 58 | | _startIndex = startIndex; |
| | 10 | 59 | | } |
| | | 60 | | |
| | | 61 | | public override Iterator<TSource> Clone() |
| | 1 | 62 | | => new SpecLikeIterator<TSource>(_source, _compiledItems, _startIndex); |
| | | 63 | | |
| | | 64 | | public override void Dispose() |
| | | 65 | | { |
| | 14 | 66 | | if (_enumerator is not null) |
| | | 67 | | { |
| | 10 | 68 | | _enumerator.Dispose(); |
| | 10 | 69 | | _enumerator = null; |
| | | 70 | | } |
| | 14 | 71 | | base.Dispose(); |
| | 14 | 72 | | } |
| | | 73 | | |
| | | 74 | | public override bool MoveNext() |
| | | 75 | | { |
| | 25 | 76 | | switch (_state) |
| | | 77 | | { |
| | | 78 | | case 1: |
| | 10 | 79 | | _enumerator = _source.GetEnumerator(); |
| | 10 | 80 | | _state = 2; |
| | | 81 | | goto case 2; |
| | | 82 | | case 2: |
| | | 83 | | Debug.Assert(_enumerator is not null); |
| | 25 | 84 | | var likeItems = _compiledItems.AsSpan()[_startIndex.._compiledItems.Length]; |
| | 35 | 85 | | while (_enumerator.MoveNext()) |
| | | 86 | | { |
| | 31 | 87 | | TSource sourceItem = _enumerator.Current; |
| | 31 | 88 | | if (IsValid(sourceItem, likeItems)) |
| | | 89 | | { |
| | 21 | 90 | | _current = sourceItem; |
| | 21 | 91 | | return true; |
| | | 92 | | } |
| | | 93 | | } |
| | | 94 | | |
| | 4 | 95 | | Dispose(); |
| | | 96 | | break; |
| | | 97 | | } |
| | | 98 | | |
| | 4 | 99 | | return false; |
| | | 100 | | } |
| | | 101 | | |
| | | 102 | | private static bool IsValid<T>(T sourceItem, ReadOnlySpan<SpecItem> span) |
| | | 103 | | { |
| | 31 | 104 | | var valid = true; |
| | 31 | 105 | | var groupStart = 0; |
| | | 106 | | |
| | 134 | 107 | | for (var i = 1; i <= span.Length; i++) |
| | | 108 | | { |
| | | 109 | | // If we reached the end of the span or the group has changed, we slice and process the group. |
| | 46 | 110 | | if (i == span.Length || span[i].Bag != span[groupStart].Bag) |
| | | 111 | | { |
| | 35 | 112 | | var validOrGroup = IsValidInOrGroup(sourceItem, span[groupStart..i]); |
| | 35 | 113 | | if ((valid = valid && validOrGroup) is false) |
| | | 114 | | { |
| | | 115 | | break; |
| | | 116 | | } |
| | 25 | 117 | | groupStart = i; |
| | | 118 | | } |
| | | 119 | | } |
| | | 120 | | |
| | 31 | 121 | | return valid; |
| | | 122 | | |
| | | 123 | | static bool IsValidInOrGroup(T sourceItem, ReadOnlySpan<SpecItem> span) |
| | | 124 | | { |
| | 35 | 125 | | var validOrGroup = false; |
| | 131 | 126 | | foreach (var specItem in span) |
| | | 127 | | { |
| | 43 | 128 | | if (specItem.Reference is not SpecLikeCompiled<T> specLike) continue; |
| | | 129 | | |
| | 43 | 130 | | if (specLike.KeySelector(sourceItem)?.Like(specLike.Pattern) ?? false) |
| | | 131 | | { |
| | 25 | 132 | | validOrGroup = true; |
| | 25 | 133 | | break; |
| | | 134 | | } |
| | | 135 | | } |
| | 35 | 136 | | return validOrGroup; |
| | | 137 | | } |
| | | 138 | | } |
| | | 139 | | } |
| | | 140 | | } |