TrieBenchmark.cs

//#define run

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;

namespace SwitchGenerator
{
    internal class Program
    {
        public static readonly string[] Top1000 = Resource.Top1000;
        public static readonly string[] Top100 = Resource.Top100;

        private const bool generate = false;

        private static void Main(string[] args)
        {
#if run
            Test();
            BenchmarkSwitches();
#else
            GenerateSwitches();
#endif
        }

#if run
        private static void Test()
        {
            foreach (var val in Top1000)
            {
                Debug.Assert(HashSwitch.Switch(val) == TrieSwitch.SafeSwitch(val));
                Debug.Assert(HashSwitch.Switch(val) == TrieSwitch.UnsafeSwitch(val));
            }

        }

        private static void BenchmarkSwitches()
        {
            var summary = BenchmarkRunner.Run<Benchmarks>();
        }
#endif

        private static void GenerateSwitches()
        {
            GenerateHashSwitch();
            GenerateTrieSwitch();
        }

        private static void GenerateTrieSwitch()
        {
            var sb = new StringBuilder();
            sb.AppendLine("public class TrieSwitch");
            sb.AppendLine("{");

            sb.AppendLine("  public unsafe static int UnsafeSwitch(string val)");
            sb.AppendLine("  {");
            GenerateTrieSwitch(sb, unzafe: true);
            sb.AppendLine("  }");
            sb.AppendLine();
            sb.AppendLine("  public static int SafeSwitch(string val)");
            sb.AppendLine("  {");
            GenerateTrieSwitch(sb, unzafe: false);
            sb.AppendLine("  }");

            sb.AppendLine("}");

            var result = sb.ToString();

            File.WriteAllText(@"../../../TrieSwitch.cs", sb.ToString());
        }

        private static void GenerateTrieSwitch(StringBuilder sb, bool unzafe)
        {
            var minLength = Top100.Min(t => t.Length);
            var maxLength = Top100.Max(t => t.Length);
            var caseToLookup = new Dictionary<string, int>();
            for (var i = 0; i < Top100.Length; i++)
            {
                caseToLookup[Top100[i]] = i + 1;
            }

            sb.AppendLine("    var length = val.Length;");
            if (unzafe)
            {
                sb.AppendLine($"    fixed (char* chars = val)");
            }

            sb.AppendLine("    switch (length)");
            sb.AppendLine("    {");

            var orderedGroups = Top100.GroupBy(t => t.Length).OrderBy(t => t.Key);
            foreach (var group in orderedGroups)
            {
                sb.AppendLine($"    case {group.Key}:");
                GenerateTrie(sb, unzafe, group.ToArray(), caseToLookup, charIndex: 0, indent: 3);
                sb.AppendLine("      return 0;");
            }

            sb.AppendLine("    }");

            sb.AppendLine("    return 0;");
        }

        private static void GenerateTrie(
            StringBuilder sb, bool unzafe, string[] cases,
            Dictionary<string, int> caseToRetVal,
            int charIndex, int indent)
        {
            var lookup = cases.ToLookup(t => t[charIndex]);
            var variable = unzafe ? "chars" : "val";

            Debug.Assert(lookup.Count > 0);

            if (lookup.Count == 1)
            {
                var grouping = lookup.First();
                var childCases = grouping.ToArray();

                if (childCases.Length == 1)
                {
                    var singleCase = childCases[0];
                    WriteIndented(sb, indent, $"if ({variable}[{charIndex}] == '{grouping.Key}'");
                    for (var i = charIndex + 1; i < singleCase.Length; i++)
                    {
                        sb.Append($" && {variable}[{i}] == '{singleCase[i]}'");
                    }
                    sb.AppendLine(")");
                    Recurse(sb, unzafe, caseToRetVal, singleCase.Length - 1, indent, childCases);
                }
                else
                {
                    WriteIndentedLine(sb, indent, $"if ({variable}[{charIndex}] == '{grouping.Key}')");
                    Recurse(sb, unzafe, caseToRetVal, charIndex, indent, childCases);
                }

                return;
            }

            WriteIndentedLine(sb, indent, $"switch ({variable}[{charIndex}])");
            WriteIndentedLine(sb, indent, "{");

            var atEnd = charIndex == cases[0].Length - 1;

            foreach (var grouping in lookup)
            {
                if (atEnd)
                {
                    WriteIndentedLine(sb, indent, $"case '{grouping.Key}':");
                    Recurse(sb, unzafe, caseToRetVal, charIndex, indent, grouping.ToArray());
                }
                else
                {
                    WriteIndentedLine(sb, indent, $"case '{grouping.Key}':");
                    Recurse(sb, unzafe, caseToRetVal, charIndex, indent, grouping.ToArray());
                    WriteIndentedLine(sb, indent + 1, "return 0;");
                }
            }

            WriteIndentedLine(sb, indent, "}");
        }

        private static void Recurse(
            StringBuilder sb, bool unzafe,
            Dictionary<string, int> caseToRetVal,
            int charIndex, int indent, string[] cases)
        {
            var match = cases.SingleOrDefault(t => t.Length == charIndex + 1);
            var rest = cases.Where(t => t != match).ToArray();
            if (match != null)
            {
                Debug.Assert(rest.Length == 0);
                WriteIndentedLine(sb, indent + 1, $"return {caseToRetVal[match]};");
            }

            if (rest.Length > 0)
            {
                GenerateTrie(sb, unzafe, rest, caseToRetVal, charIndex + 1, indent + 1);
            }
        }

        private static void WriteIndentedLine(StringBuilder sb, int indent, string v)
        {
            WriteIndented(sb, indent, v);
            sb.AppendLine();
        }

        private static void WriteIndented(StringBuilder sb, int indent, string v)
        {
            sb.Append(WriteIndent(indent));
            sb.Append(v);
        }

        private static string WriteIndent(int indent)
        {
            return string.Join("", Enumerable.Repeat("  ", indent));
        }

        private static void GenerateHashSwitch()
        {
            var sb = new StringBuilder();
            sb.AppendLine("public class HashSwitch");
            sb.AppendLine("{");
            sb.AppendLine("  public static int Switch(string val)");
            sb.AppendLine("  {");
            sb.AppendLine("    switch (val)");
            sb.AppendLine("    {");
            sb.AppendLine("      default: return 0;");

            for (var i = 0; i < Top100.Length; i++)
            {
                sb.AppendLine($"      case \"{Top100[i]}\": return {i + 1};");
            }

            sb.AppendLine("    }");
            sb.AppendLine("  }");
            sb.AppendLine("}");

            File.WriteAllText(@"../../../HashSwitch.cs", sb.ToString());
        }
    }

#if run
    public class Benchmarks
    {
        [Benchmark]
        public void HashSwitch()
        {
            foreach (var value in Program.Top1000)
            {
                global::HashSwitch.Switch(value);
            }
        }

        [Benchmark]
        public void SafeTrieSwitch()
        {
            foreach (var value in Program.Top1000)
            {
                TrieSwitch.SafeSwitch(value);
            }
        }

        [Benchmark]
        public void UnsafeTrieSwitch()
        {
            foreach (var value in Program.Top1000)
            {
                TrieSwitch.UnsafeSwitch(value);
            }

        }
    }
#endif
}

internal static class Resource
{
    public static string[] Top1000 = {
"as",
"I",
"his",
"that",
"he",
"was",
"for",
"on",
"are",
"with",
"they",
"be",
"at",
"one",
"have",
"this",
"from",
"by",
"hot",
"word",
"but",
"what",
"some",
"is",
"it",
"you",
"or",
"had",
"the",
"of",
"to",
"and",
"a",
"in",
"we",
"can",
"out",
"other",
"were",
"which",
"do",
"their",
"time",
"if",
"will",
"how",
"said",
"an",
"each",
"tell",
"does",
"set",
"three",
"want",
"air",
"well",
"also",
"play",
"small",
"end",
"put",
"home",
"read",
"hand",
"port",
"large",
"spell",
"add",
"even",
"land",
"here",
"must",
"big",
"high",
"such",
"follow",
"act",
"why",
"ask",
"men",
"change",
"went",
"light",
"kind",
"off",
"need",
"house",
"picture",
"try",
"us",
"again",
"animal",
"point",
"mother",
"world",
"near",
"build",
"self",
"earth",
"father",
"any",
"new",
"work",
"part",
"take",
"get",
"place",
"made",
"live",
"where",
"after",
"back",
"little",
"only",
"round",
"man",
"year",
"came",
"show",
"every",
"good",
"me",
"give",
"our",
"under",
"name",
"very",
"through",
"just",
"form",
"sentence",
"great",
"think",
"say",
"help",
"low",
"line",
"differ",
"turn",
"cause",
"much",
"mean",
"before",
"move",
"right",
"boy",
"old",
"too",
"same",
"she",
"all",
"there",
"when",
"up",
"use",
"your",
"way",
"about",
"many",
"then",
"them",
"write",
"would",
"like",
"so",
"these",
"her",
"long",
"make",
"thing",
"see",
"him",
"two",
"has",
"look",
"more",
"day",
"could",
"go",
"come",
"did",
"number",
"sound",
"no",
"most",
"people",
"my",
"over",
"know",
"water",
"than",
"call",
"first",
"who",
"may",
"down",
"side",
"been",
"now",
"find",
"head",
"stand",
"own",
"page",
"should",
"country",
"found",
"answer",
"school",
"grow",
"study",
"still",
"learn",
"plant",
"cover",
"food",
"sun",
"four",
"between",
"state",
"keep",
"eye",
"never",
"last",
"let",
"thought",
"city",
"tree",
"cross",
"farm",
"hard",
"start",
"might",
"story",
"saw",
"far",
"sea",
"draw",
"left",
"late",
"run",
"don’t",
"while",
"press",
"close",
"night",
"real",
"life",
"few",
"north",
"book",
"carry",
"took",
"science",
"eat",
"room",
"friend",
"began",
"idea",
"fish",
"mountain",
"stop",
"once",
"base",
"hear",
"horse",
"cut",
"sure",
"watch",
"color",
"face",
"wood",
"main",
"open",
"seem",
"together",
"next",
"white",
"children",
"begin",
"got",
"walk",
"example",
"ease",
"paper",
"group",
"always",
"music",
"those",
"both",
"mark",
"often",
"letter",
"until",
"mile",
"river",
"car",
"feet",
"care",
"second",
"enough",
"plain",
"girl",
"usual",
"young",
"ready",
"above",
"ever",
"red",
"list",
"though",
"feel",
"talk",
"bird",
"soon",
"body",
"dog",
"family",
"direct",
"pose",
"leave",
"song",
"measure",
"door",
"product",
"black",
"short",
"numeral",
"class",
"wind",
"question",
"happen",
"complete",
"ship",
"area",
"half",
"rock",
"order",
"fire",
"south",
"problem",
"piece",
"told",
"knew",
"pass",
"since",
"top",
"whole",
"king",
"street",
"inch",
"multiply",
"nothing",
"course",
"stay",
"wheel",
"full",
"force",
"blue",
"object",
"decide",
"surface",
"deep",
"moon",
"island",
"foot",
"system",
"busy",
"test",
"record",
"boat",
"common",
"gold",
"possible",
"plane",
"stead",
"dry",
"wonder",
"laugh",
"thousand",
"ago",
"ran",
"check",
"game",
"shape",
"equate",
"hot",
"miss",
"brought",
"heat",
"snow",
"tire",
"bring",
"yes",
"distant",
"fill",
"east",
"paint",
"language",
"among",
"unit",
"power",
"town",
"fine",
"certain",
"fly",
"fall",
"lead",
"cry",
"dark",
"machine",
"note",
"wait",
"plan",
"figure",
"star",
"box",
"noun",
"field",
"rest",
"correct",
"able",
"pound",
"done",
"beauty",
"drive",
"stood",
"contain",
"front",
"teach",
"week",
"final",
"gave",
"green",
"oh",
"quick",
"develop",
"ocean",
"warm",
"free",
"minute",
"strong",
"special",
"mind",
"behind",
"clear",
"tail",
"produce",
"fact",
"space",
"heard",
"best",
"hour",
"better",
"true",
"during",
"hundred",
"five",
"remember",
"step",
"early",
"hold",
"west",
"ground",
"interest",
"reach",
"fast",
"verb",
"sing",
"listen",
"six",
"table",
"travel",
"less",
"morning",
"ten",
"simple",
"several",
"vowel",
"toward",
"war",
"lay",
"against",
"pattern",
"slow",
"center",
"love",
"person",
"money",
"serve",
"appear",
"road",
"map",
"rain",
"rule",
"govern",
"pull",
"cold",
"notice",
"voice",
"energy",
"hunt",
"probable",
"bed",
"brother",
"egg",
"ride",
"cell",
"believe",
"perhaps",
"pick",
"sudden",
"count",
"square",
"reason",
"length",
"represent",
"art",
"subject",
"region",
"size",
"vary",
"settle",
"speak",
"weight",
"general",
"ice",
"matter",
"circle",
"pair",
"include",
"divide",
"syllable",
"felt",
"grand",
"ball",
"yet",
"wave",
"drop",
"heart",
"am",
"present",
"heavy",
"dance",
"engine",
"position",
"arm",
"wide",
"sail",
"material",
"fraction",
"forest",
"sit",
"race",
"window",
"store",
"summer",
"train",
"sleep",
"prove",
"lone",
"leg",
"exercise",
"wall",
"catch",
"mount",
"wish",
"sky",
"board",
"joy",
"winter",
"sat",
"written",
"wild",
"instrument",
"kept",
"glass",
"grass",
"cow",
"job",
"edge",
"sign",
"visit",
"past",
"soft",
"fun",
"bright",
"gas",
"weather",
"month",
"million",
"bear",
"finish",
"happy",
"hope",
"flower",
"clothe",
"strange",
"gone",
"trade",
"melody",
"trip",
"office",
"receive",
"row",
"mouth",
"exact",
"symbol",
"die",
"least",
"trouble",
"shout",
"except",
"wrote",
"seed",
"tone",
"join",
"suggest",
"clean",
"break",
"lady",
"yard",
"rise",
"bad",
"blow",
"oil",
"blood",
"touch",
"grew",
"cent",
"mix",
"team",
"wire",
"cost",
"lost",
"brown",
"wear",
"garden",
"equal",
"sent",
"choose",
"fell",
"fit",
"flow",
"fair",
"bank",
"collect",
"save",
"control",
"decimal",
"ear",
"else",
"quite",
"broke",
"case",
"middle",
"kill",
"son",
"lake",
"moment",
"scale",
"loud",
"spring",
"observe",
"child",
"straight",
"consonant",
"nation",
"dictionary",
"milk",
"speed",
"method",
"organ",
"pay",
"age",
"section",
"dress",
"cloud",
"surprise",
"quiet",
"stone",
"tiny",
"climb",
"cool",
"design",
"poor",
"lot",
"experiment",
"bottom",
"key",
"iron",
"single",
"stick",
"flat",
"twenty",
"skin",
"smile",
"crease",
"hole",
"jump",
"baby",
"eight",
"village",
"meet",
"root",
"buy",
"raise",
"solve",
"metal",
"whether",
"push",
"seven",
"paragraph",
"third",
"shall",
"held",
"hair",
"describe",
"cook",
"floor",
"either",
"result",
"burn",
"hill",
"safe",
"cat",
"century",
"consider",
"type",
"law",
"bit",
"coast",
"copy",
"phrase",
"silent",
"tall",
"sand",
"soil",
"roll",
"temperature",
"finger",
"industry",
"value",
"fight",
"lie",
"beat",
"excite",
"natural",
"view",
"sense",
"capital",
"won’t",
"chair",
"danger",
"fruit",
"rich",
"thick",
"soldier",
"process",
"operate",
"practice",
"separate",
"difficult",
"doctor",
"please",
"protect",
"noon",
"crop",
"modern",
"element",
"hit",
"student",
"corner",
"party",
"supply",
"whose",
"locate",
"ring",
"character",
"insect",
"caught",
"period",
"indicate",
"radio",
"spoke",
"atom",
"human",
"history",
"effect",
"electric",
"expect",
"bone",
"rail",
"imagine",
"provide",
"agree",
"thus",
"gentle",
"woman",
"captain",
"guess",
"necessary",
"sharp",
"wing",
"create",
"neighbor",
"wash",
"bat",
"rather",
"crowd",
"corn",
"compare",
"poem",
"string",
"bell",
"depend",
"meat",
"rub",
"tube",
"famous",
"dollar",
"stream",
"fear",
"sight",
"thin",
"triangle",
"planet",
"hurry",
"chief",
"colony",
"clock",
"mine",
"tie",
"enter",
"major",
"fresh",
"search",
"send",
"yellow",
"gun",
"allow",
"print",
"dead",
"spot",
"desert",
"suit",
"current",
"lift",
"rose",
"arrive",
"master",
"track",
"parent",
"shore",
"division",
"sheet",
"substance",
"favor",
"connect",
"post",
"spend",
"chord",
"fat",
"glad",
"original",
"share",
"station",
"dad",
"bread",
"charge",
"proper",
"bar",
"offer",
"segment",
"slave",
"duck",
"instant",
"market",
"degree",
"populate",
"chick",
"dear",
"enemy",
"reply",
"drink",
"occur",
"support",
"speech",
"nature",
"range",
"steam",
"motion",
"path",
"liquid",
"log",
"meant",
"quotient",
"teeth",
"shell",
"neck",
"oxygen",
"sugar",
"death",
"pretty",
"skill",
"women",
"season",
"solution",
"magnet",
"silver",
"thank",
"branch",
"match",
"suffix",
"especially",
"fig",
"afraid",
"huge",
"sister",
"steel",
"discuss",
"forward",
"similar",
"guide",
"experience",
"score",
"apple",
"bought",
"led",
"pitch",
"coat",
"mass",
"card",
"band",
"rope",
"slip",
"win",
"dream",
"evening",
"condition",
"feed",
"tool",
"total",
"basic",
"smell",
"valley",
"nor",
"double",
"seat",
"continue",
"block",
"chart",
"hat",
"sell",
"success",
"company",
"subtract",
"event",
"particular",
"deal",
"swim",
"term",
"opposite",
"wife",
"shoe",
"shoulder",
"spread",
"arrange",
"camp",
"invent",
"cotton",
"born",
"determine",
"quart",
"nine",
"truck",
"noise",
"level",
"chance",
"gather",
"shop",
"stretch",
"throw",
"shine",
"property",
"column",
"molecule",
"select",
"wrong",
"gray",
"repeat",
"require",
"broad",
"prepare",
"salt",
"nose",
"plural",
"anger",
"claim",
"continent",
};

    public static string[] Top100 = Top1000.Take(100).ToArray();
}

Have you ever built an Emit-based version of this?