| | | 1 | | // Licensed to the .NET Foundation under one or more agreements. |
| | | 2 | | // The .NET Foundation licenses this file to you under the MIT license. |
| | | 3 | | |
| | | 4 | | using System.Collections.Generic; |
| | | 5 | | using System.Diagnostics; |
| | | 6 | | using System.Numerics; |
| | | 7 | | using System.Runtime.CompilerServices; |
| | | 8 | | using System.Runtime.Intrinsics; |
| | | 9 | | |
| | | 10 | | namespace System.Buffers |
| | | 11 | | { |
| | | 12 | | internal static class TeddyBucketizer |
| | | 13 | | { |
| | | 14 | | // This method is the same as GenerateBucketizedFingerprint below, but each bucket only contains 1 value. |
| | | 15 | | public static (Vector512<byte> Low, Vector512<byte> High) GenerateNonBucketizedFingerprint(ReadOnlySpan<string> |
| | | 16 | | { |
| | 0 | 17 | | Debug.Assert(values.Length <= 8); |
| | | 18 | | |
| | 0 | 19 | | Vector128<byte> low = default; |
| | 0 | 20 | | Vector128<byte> high = default; |
| | | 21 | | |
| | 0 | 22 | | for (int i = 0; i < values.Length; i++) |
| | | 23 | | { |
| | 0 | 24 | | string value = values[i]; |
| | | 25 | | |
| | 0 | 26 | | int bit = 1 << i; |
| | | 27 | | |
| | 0 | 28 | | char c = value[offset]; |
| | 0 | 29 | | Debug.Assert(char.IsAscii(c)); |
| | | 30 | | |
| | 0 | 31 | | int lowNibble = c & 0xF; |
| | 0 | 32 | | int highNibble = c >> 4; |
| | | 33 | | |
| | 0 | 34 | | low.SetElementUnsafe(lowNibble, (byte)(low.GetElementUnsafe(lowNibble) | bit)); |
| | 0 | 35 | | high.SetElementUnsafe(highNibble, (byte)(high.GetElementUnsafe(highNibble) | bit)); |
| | | 36 | | } |
| | | 37 | | |
| | 0 | 38 | | return (Vector512.Create(low), Vector512.Create(high)); |
| | | 39 | | } |
| | | 40 | | |
| | | 41 | | // We can have up to 8 buckets, and their positions are encoded by 1 bit each. |
| | | 42 | | // Every bitmap encodes a mapping of each of the possible 16 nibble values into an 8-bit bitmap. |
| | | 43 | | // For example if bucket 0 contains strings ["foo", "bar"], the bitmaps will have the first bit (0th bucket) set |
| | | 44 | | // 'f' is 0x66, 'b' is 0x62, so n0Low has the bit set at index 2 and 6, n0High has it set at index 6. |
| | | 45 | | // 'o' is 0x6F, 'a' is 0x61, so n1Low has the bit set at index 1 and 15, n1High has it set at index 6. |
| | | 46 | | // 'o' is 0x6F, 'r' is 0x72, so n2Low has the bit set at index 2 and 15, n2High has it set at index 6 and 7. |
| | | 47 | | // We repeat this for each bucket and then OR together the bitmaps (fingerprints) of each bucket to generate a s |
| | | 48 | | public static (Vector512<byte> Low, Vector512<byte> High) GenerateBucketizedFingerprint(string[][] valueBuckets, |
| | | 49 | | { |
| | 0 | 50 | | Debug.Assert(valueBuckets.Length <= 8); |
| | | 51 | | |
| | 0 | 52 | | Vector128<byte> low = default; |
| | 0 | 53 | | Vector128<byte> high = default; |
| | | 54 | | |
| | 0 | 55 | | for (int i = 0; i < valueBuckets.Length; i++) |
| | | 56 | | { |
| | 0 | 57 | | int bit = 1 << i; |
| | | 58 | | |
| | 0 | 59 | | foreach (string value in valueBuckets[i]) |
| | | 60 | | { |
| | 0 | 61 | | char c = value[offset]; |
| | 0 | 62 | | Debug.Assert(char.IsAscii(c)); |
| | | 63 | | |
| | 0 | 64 | | int lowNibble = c & 0xF; |
| | 0 | 65 | | int highNibble = c >> 4; |
| | | 66 | | |
| | 0 | 67 | | low.SetElementUnsafe(lowNibble, (byte)(low.GetElementUnsafe(lowNibble) | bit)); |
| | 0 | 68 | | high.SetElementUnsafe(highNibble, (byte)(high.GetElementUnsafe(highNibble) | bit)); |
| | | 69 | | } |
| | | 70 | | } |
| | | 71 | | |
| | 0 | 72 | | return (Vector512.Create(low), Vector512.Create(high)); |
| | | 73 | | } |
| | | 74 | | |
| | | 75 | | public static unsafe string[][] Bucketize(ReadOnlySpan<string> values, int bucketCount, int n) |
| | | 76 | | { |
| | 0 | 77 | | Debug.Assert(bucketCount == 8, "This may change if we end up supporting the 'fat Teddy' variant."); |
| | 0 | 78 | | Debug.Assert(values.Length > bucketCount, "Should be using a non-bucketized implementation."); |
| | 0 | 79 | | Debug.Assert(values.Length <= RabinKarp.MaxValues); |
| | | 80 | | |
| | | 81 | | // Stores the offset of the bucket each value should be assigned to. |
| | | 82 | | // This lets us avoid allocating temporary lists to build up each bucket. |
| | 0 | 83 | | Span<int> bucketIndexes = stackalloc int[RabinKarp.MaxValues].Slice(0, values.Length); |
| | | 84 | | |
| | | 85 | | // Group patterns with the same prefix into the same bucket to avoid wasting time during verification steps. |
| | 0 | 86 | | Dictionary<int, int> prefixToBucket = new(bucketCount); |
| | | 87 | | |
| | 0 | 88 | | int bucketCounter = 0; |
| | | 89 | | |
| | 0 | 90 | | for (int i = 0; i < values.Length; i++) |
| | | 91 | | { |
| | 0 | 92 | | string value = values[i]; |
| | | 93 | | |
| | 0 | 94 | | int prefix = 0; |
| | 0 | 95 | | for (int j = 0; j < n; j++) |
| | | 96 | | { |
| | 0 | 97 | | Debug.Assert(char.IsAscii(value[j])); |
| | 0 | 98 | | prefix = (prefix << 8) | value[j]; |
| | | 99 | | } |
| | | 100 | | |
| | 0 | 101 | | if (!prefixToBucket.TryGetValue(prefix, out int bucketIndex)) |
| | | 102 | | { |
| | | 103 | | // Potential optimization: We currently merge values with different prefixes into buckets randomly ( |
| | | 104 | | // We could employ a more sophisticated strategy here, e.g. by trying to minimize the number of |
| | | 105 | | // values in each bucket, or by minimizing the PopCount of final merged fingerprints. |
| | | 106 | | // Example of the latter: https://gist.github.com/MihaZupan/831324d1d646b69ae0ba4b54e3446a49 |
| | | 107 | | |
| | 0 | 108 | | bucketIndex = bucketCounter++ % bucketCount; |
| | 0 | 109 | | prefixToBucket.Add(prefix, bucketIndex); |
| | | 110 | | } |
| | | 111 | | |
| | 0 | 112 | | bucketIndexes[i] = bucketIndex; |
| | | 113 | | } |
| | | 114 | | |
| | 0 | 115 | | string[][] buckets = new string[bucketCount][]; |
| | | 116 | | |
| | 0 | 117 | | for (int bucketIndex = 0; bucketIndex < buckets.Length; bucketIndex++) |
| | | 118 | | { |
| | 0 | 119 | | string[] strings = buckets[bucketIndex] = new string[bucketIndexes.Count(bucketIndex)]; |
| | | 120 | | |
| | 0 | 121 | | int count = 0; |
| | 0 | 122 | | for (int i = 0; i < bucketIndexes.Length; i++) |
| | | 123 | | { |
| | 0 | 124 | | if (bucketIndexes[i] == bucketIndex) |
| | | 125 | | { |
| | 0 | 126 | | strings[count++] = values[i]; |
| | | 127 | | } |
| | | 128 | | } |
| | 0 | 129 | | Debug.Assert(count == strings.Length); |
| | | 130 | | } |
| | | 131 | | |
| | 0 | 132 | | return buckets; |
| | | 133 | | } |
| | | 134 | | } |
| | | 135 | | } |
| | | 136 | | |