Last active
August 17, 2023 12:20
-
-
Save mgravell/bbbb83c1e13b1f05328064f41400436f to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Diagnostics; | |
using System.Text; | |
using System.Threading; | |
static class P { | |
static int remainingKeys = Crc16.RedisClusterSlotCount; | |
static readonly string[] keys = new string[remainingKeys]; | |
const byte CharsStart = 33, // ignore space | |
CharsEnd = 126; // ignore DEL | |
static void Main() | |
{ | |
Span<byte> three = stackalloc byte[3], two = three.Slice(0, 2), one = three.Slice(0, 1); | |
var watch = Stopwatch.StartNew(); | |
try | |
{ | |
for (byte i = CharsStart; i <= CharsEnd; i++) | |
{ | |
one[0] = i; | |
SetSlot(one); | |
} | |
// repeat the loops because we want to prefer shorter keys | |
for (byte i = CharsStart; i <= CharsEnd; i++) | |
{ | |
two[0] = i; | |
for (byte j = CharsStart; j <= CharsEnd; j++) | |
{ | |
two[1] = j; | |
SetSlot(two); | |
} | |
} | |
for (byte i = CharsStart; i <= CharsEnd; i++) | |
{ | |
three[0] = i; | |
for (byte j = CharsStart; j <= CharsEnd; j++) | |
{ | |
three[1] = j; | |
for (byte k = CharsStart; k <= CharsEnd; k++) | |
{ | |
three[2] = k; | |
SetSlot(three); | |
} | |
} | |
} | |
} catch (AllDoneException) | |
{ | |
} | |
watch.Stop(); | |
Console.WriteLine($"{Volatile.Read(ref remainingKeys)} remaining after {watch.Elapsed.TotalSeconds} seconds"); | |
Console.WriteLine("Press any key to show results..."); | |
Console.ReadKey(); | |
for (int i = 0; i < keys.Length; i++) | |
{ | |
Console.WriteLine($"{i}:\t{keys[i]}"); | |
} | |
static void SetSlot(ReadOnlySpan<byte> key) | |
{ | |
var slot = Crc16.GetClusterSlot(key); | |
// written with parallelism in mind, so: handles thread safety; for single-thread, | |
// this can be simpler and probably faster as just: | |
// if (keys[slot] is null) | |
// { | |
// keys[slot] = Encoding.ASCII.GetString(key); | |
// if (--remainingKeys <= 0) ThrowAllDone(); | |
// } | |
if (Volatile.Read(ref keys[slot]) is null | |
&& Interlocked.CompareExchange(ref keys[slot], Encoding.ASCII.GetString(key), null) is null) | |
{ | |
var rem = Interlocked.Decrement(ref remainingKeys); | |
if (rem <= 0) ThrowAllDone(); | |
} | |
static void ThrowAllDone() => throw new AllDoneException(); | |
} | |
} | |
sealed class AllDoneException : Exception { }// bite me | |
static class Crc16 | |
{ | |
public const int RedisClusterSlotCount = 16384; | |
public static unsafe int GetClusterSlot(ReadOnlySpan<byte> blob) | |
{ | |
unchecked | |
{ | |
fixed (byte* ptr = blob) | |
{ | |
fixed (ushort* crc16tab = s_crc16tab) | |
{ | |
int offset = 0, count = blob.Length, start, end; | |
if ((start = IndexOf(ptr, (byte)'{', 0, count - 1)) >= 0 | |
&& (end = IndexOf(ptr, (byte)'}', start + 1, count)) >= 0 | |
&& --end != start) | |
{ | |
offset = start + 1; | |
count = end - start; // note we already subtracted one via --end | |
} | |
uint crc = 0; | |
for (int i = 0; i < count; i++) | |
crc = ((crc << 8) ^ crc16tab[((crc >> 8) ^ ptr[offset++]) & 0x00FF]) & 0x0000FFFF; | |
return (int)(crc % RedisClusterSlotCount); | |
} | |
} | |
} | |
} | |
private static unsafe int IndexOf(byte* ptr, byte value, int start, int end) | |
{ | |
for (int offset = start; offset < end; offset++) | |
if (ptr[offset] == value) return offset; | |
return -1; | |
} | |
private static readonly ushort[] s_crc16tab = new ushort[] | |
{ | |
0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7, | |
0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef, | |
0x1231,0x0210,0x3273,0x2252,0x52b5,0x4294,0x72f7,0x62d6, | |
0x9339,0x8318,0xb37b,0xa35a,0xd3bd,0xc39c,0xf3ff,0xe3de, | |
0x2462,0x3443,0x0420,0x1401,0x64e6,0x74c7,0x44a4,0x5485, | |
0xa56a,0xb54b,0x8528,0x9509,0xe5ee,0xf5cf,0xc5ac,0xd58d, | |
0x3653,0x2672,0x1611,0x0630,0x76d7,0x66f6,0x5695,0x46b4, | |
0xb75b,0xa77a,0x9719,0x8738,0xf7df,0xe7fe,0xd79d,0xc7bc, | |
0x48c4,0x58e5,0x6886,0x78a7,0x0840,0x1861,0x2802,0x3823, | |
0xc9cc,0xd9ed,0xe98e,0xf9af,0x8948,0x9969,0xa90a,0xb92b, | |
0x5af5,0x4ad4,0x7ab7,0x6a96,0x1a71,0x0a50,0x3a33,0x2a12, | |
0xdbfd,0xcbdc,0xfbbf,0xeb9e,0x9b79,0x8b58,0xbb3b,0xab1a, | |
0x6ca6,0x7c87,0x4ce4,0x5cc5,0x2c22,0x3c03,0x0c60,0x1c41, | |
0xedae,0xfd8f,0xcdec,0xddcd,0xad2a,0xbd0b,0x8d68,0x9d49, | |
0x7e97,0x6eb6,0x5ed5,0x4ef4,0x3e13,0x2e32,0x1e51,0x0e70, | |
0xff9f,0xefbe,0xdfdd,0xcffc,0xbf1b,0xaf3a,0x9f59,0x8f78, | |
0x9188,0x81a9,0xb1ca,0xa1eb,0xd10c,0xc12d,0xf14e,0xe16f, | |
0x1080,0x00a1,0x30c2,0x20e3,0x5004,0x4025,0x7046,0x6067, | |
0x83b9,0x9398,0xa3fb,0xb3da,0xc33d,0xd31c,0xe37f,0xf35e, | |
0x02b1,0x1290,0x22f3,0x32d2,0x4235,0x5214,0x6277,0x7256, | |
0xb5ea,0xa5cb,0x95a8,0x8589,0xf56e,0xe54f,0xd52c,0xc50d, | |
0x34e2,0x24c3,0x14a0,0x0481,0x7466,0x6447,0x5424,0x4405, | |
0xa7db,0xb7fa,0x8799,0x97b8,0xe75f,0xf77e,0xc71d,0xd73c, | |
0x26d3,0x36f2,0x0691,0x16b0,0x6657,0x7676,0x4615,0x5634, | |
0xd94c,0xc96d,0xf90e,0xe92f,0x99c8,0x89e9,0xb98a,0xa9ab, | |
0x5844,0x4865,0x7806,0x6827,0x18c0,0x08e1,0x3882,0x28a3, | |
0xcb7d,0xdb5c,0xeb3f,0xfb1e,0x8bf9,0x9bd8,0xabbb,0xbb9a, | |
0x4a75,0x5a54,0x6a37,0x7a16,0x0af1,0x1ad0,0x2ab3,0x3a92, | |
0xfd2e,0xed0f,0xdd6c,0xcd4d,0xbdaa,0xad8b,0x9de8,0x8dc9, | |
0x7c26,0x6c07,0x5c64,0x4c45,0x3ca2,0x2c83,0x1ce0,0x0cc1, | |
0xef1f,0xff3e,0xcf5d,0xdf7c,0xaf9b,0xbfba,0x8fd9,0x9ff8, | |
0x6e17,0x7e36,0x4e55,0x5e74,0x2e93,0x3eb2,0x0ed1,0x1ef0 | |
}; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment