search

dotnet / maui

.NET MAUI is the .NET Multi-platform App UI, a framework for building native device applications spanning mobile, tablet, and desktop.
https://dot.net/maui
MIT License
22.22k stars 1.75k forks source link

Suggest a possible optimization for `static Color GetNamedColor(ReadOnlySpan<char> value)`. #11846

Open lsoft opened 1 year ago

lsoft commented 1 year ago

(a copy of https://github.com/dotnet/Microsoft.Maui.Graphics/issues/495)

I write this into issue, because I'm not sure we want such optimizations at all.

The discussed method: https://github.com/dotnet/maui/blob/main/src/Graphics/src/Graphics/Color.cs#L757

Now, the method looks like

        static Color GetNamedColor(ReadOnlySpan<char> value)
        {
            // the longest built-in Color's name is much lower than this check, so we should not allocate here in a typical usage
            Span<char> loweredValue = value.Length <= 128 ? stackalloc char[value.Length] : new char[value.Length];

            int charsWritten = value.ToLowerInvariant(loweredValue);
            Debug.Assert(charsWritten == value.Length);

            // this should use the C# feature https://github.com/dotnet/csharplang/issues/1881, when it is available
            // for now, we need to allocate the lowered string
            return loweredValue.ToString() switch
            {
                "default" => default,
                "aliceblue" => Colors.AliceBlue,

                                 //big switch

                "yellow" => Colors.Yellow,
                "yellowgreen" => Colors.YellowGreen,
                _ => null
            };
        }

I found that there is the room for optimization. On my machine the data looks like (PTAL on allocations too):

BenchmarkDotNet=v0.13.2, OS=Windows 10 (10.0.19044.1586/21H2/November2021Update)
Intel Core i7-8550U CPU 1.80GHz (Kaby Lake R), 1 CPU, 8 logical and 4 physical cores
.NET SDK=7.0.100
  [Host]     : .NET 7.0.0 (7.0.22.51805), X64 RyuJIT AVX2
  DefaultJob : .NET 7.0.0 (7.0.22.51805), X64 RyuJIT AVX2

|                  Method |     Mean |     Error |    StdDev |   Gen0 | Allocated |
|------------------------ |---------:|----------:|----------:|-------:|----------:|
|      GetNamedColor_Orig | 6.106 us | 0.1194 us | 0.1058 us | 1.5106 |    6320 B |
| GetNamedColor_Generated | 4.302 us | 0.0661 us | 0.1158 us |      - |         - |

The benchmark method looks like:

        [Benchmark]
        public void GetNamedColor_Orig()
        {
            _ = GetNamedColor_Orig("default");
            _ = GetNamedColor_Orig("aliceblue");

           ... //all existing colors

            _ = GetNamedColor_Orig("yellow");
            _ = GetNamedColor_Orig("yellowgreen");
        }

The optimized method:

        static Color GetNamedColor(ReadOnlySpan<char> value)
        {
            // the longest built-in Color's name is much lower than this check, so we should not allocate here in a typical usage
            Span<char> loweredValue = value.Length <= 128 ? stackalloc char[value.Length] : new char[value.Length];

            int charsWritten = value.ToLowerInvariant(loweredValue);
            Debug.Assert(charsWritten == value.Length);

            return GetNamedColor(loweredValue);
        }

        private static Color GetNamedColor(Span<char> color)
        {
            string candidatecolor = default;
            Color resultcolor = default;
            switch (color.Length)
            {
                case 3:
                    switch (color[0])
                    {
                        case 'r': candidatecolor = "red"; resultcolor = Colors.Red; break;
                        case 't': candidatecolor = "tan"; resultcolor = Colors.Tan; break;
                    }
                    break;
                case 4:
                    switch (color.Slice(2, 2))
                    {
                        case "ua": candidatecolor = "aqua"; resultcolor = Colors.Aqua; break;
                        case "ue": candidatecolor = "blue"; resultcolor = Colors.Blue; break;
                        case "an": candidatecolor = "cyan"; resultcolor = Colors.Cyan; break;
                        case "ld": candidatecolor = "gold"; resultcolor = Colors.Gold; break;
                        case "ay": candidatecolor = "gray"; resultcolor = Colors.Gray; break;
                        case "ey": candidatecolor = "grey"; resultcolor = Colors.Grey; break;
                        case "me": candidatecolor = "lime"; resultcolor = Colors.Lime; break;
                        case "vy": candidatecolor = "navy"; resultcolor = Colors.Navy; break;
                        case "ru": candidatecolor = "peru"; resultcolor = Colors.Peru; break;
                        case "nk": candidatecolor = "pink"; resultcolor = Colors.Pink; break;
                        case "um": candidatecolor = "plum"; resultcolor = Colors.Plum; break;
                        case "ow": candidatecolor = "snow"; resultcolor = Colors.Snow; break;
                        case "al": candidatecolor = "teal"; resultcolor = Colors.Teal; break;
                    }
                    break;
                case 5:
                    switch (color.Slice(1, 2))
                    {
                        case "zu": candidatecolor = "azure"; resultcolor = Colors.Azure; break;
                        case "ei": candidatecolor = "beige"; resultcolor = Colors.Beige; break;
                        case "la": candidatecolor = "black"; resultcolor = Colors.Black; break;
                        case "ro": candidatecolor = "brown"; resultcolor = Colors.Brown; break;
                        case "or": candidatecolor = "coral"; resultcolor = Colors.Coral; break;
                        case "re": candidatecolor = "green"; resultcolor = Colors.Green; break;
                        case "vo": candidatecolor = "ivory"; resultcolor = Colors.Ivory; break;
                        case "ha": candidatecolor = "khaki"; resultcolor = Colors.Khaki; break;
                        case "in": candidatecolor = "linen"; resultcolor = Colors.Linen; break;
                        case "li": candidatecolor = "olive"; resultcolor = Colors.Olive; break;
                        case "he": candidatecolor = "wheat"; resultcolor = Colors.Wheat; break;
                        case "hi": candidatecolor = "white"; resultcolor = Colors.White; break;
                    }
                    break;
                case 6:
                    switch (color.Slice(1, 2))
                    {
                        case "is": candidatecolor = "bisque"; resultcolor = Colors.Bisque; break;
                        case "nd": candidatecolor = "indigo"; resultcolor = Colors.Indigo; break;
                        case "ar": candidatecolor = "maroon"; resultcolor = Colors.Maroon; break;
                        case "ra": candidatecolor = "orange"; resultcolor = Colors.Orange; break;
                        case "rc": candidatecolor = "orchid"; resultcolor = Colors.Orchid; break;
                        case "ur": candidatecolor = "purple"; resultcolor = Colors.Purple; break;
                        case "al": candidatecolor = "salmon"; resultcolor = Colors.Salmon; break;
                        case "ie": candidatecolor = "sienna"; resultcolor = Colors.Sienna; break;
                        case "il": candidatecolor = "silver"; resultcolor = Colors.Silver; break;
                        case "om": candidatecolor = "tomato"; resultcolor = Colors.Tomato; break;
                        case "io": candidatecolor = "violet"; resultcolor = Colors.Violet; break;
                        case "el": candidatecolor = "yellow"; resultcolor = Colors.Yellow; break;
                    }
                    break;
                case 7:
                    switch (color.Slice(5, 2))
                    {
                        case "lt": candidatecolor = "default"; resultcolor = default; break;
                        case "on": candidatecolor = "crimson"; resultcolor = Colors.Crimson; break;
                        case "ed": candidatecolor = "darkred"; resultcolor = Colors.DarkRed; break;
                        case "ay": candidatecolor = "dimgray"; resultcolor = Colors.DimGray; break;
                        case "ey": candidatecolor = "dimgrey"; resultcolor = Colors.DimGrey; break;
                        case "ia": candidatecolor = "fuchsia"; resultcolor = Colors.Fuchsia; break;
                        case "nk": candidatecolor = "hotpink"; resultcolor = Colors.HotPink; break;
                        case "ta": candidatecolor = "magenta"; resultcolor = Colors.Magenta; break;
                        case "ce": candidatecolor = "oldlace"; resultcolor = Colors.OldLace; break;
                        case "ue": candidatecolor = "skyblue"; resultcolor = Colors.SkyBlue; break;
                        case "le": candidatecolor = "thistle"; resultcolor = Colors.Thistle; break;
                    }
                    break;
                case 8:
                    switch (color.Slice(6, 2))
                    {
                        case "lk": candidatecolor = "cornsilk"; resultcolor = Colors.Cornsilk; break;
                        case "ue": candidatecolor = "darkblue"; resultcolor = Colors.DarkBlue; break;
                        case "an": candidatecolor = "darkcyan"; resultcolor = Colors.DarkCyan; break;
                        case "ay": candidatecolor = "darkgray"; resultcolor = Colors.DarkGray; break;
                        case "ey": candidatecolor = "darkgrey"; resultcolor = Colors.DarkGrey; break;
                        case "nk": candidatecolor = "deeppink"; resultcolor = Colors.DeepPink; break;
                        case "ew": candidatecolor = "honeydew"; resultcolor = Colors.Honeydew; break;
                        case "er": candidatecolor = "lavender"; resultcolor = Colors.Lavender; break;
                        case "in": candidatecolor = "moccasin"; resultcolor = Colors.Moccasin; break;
                        case "en": candidatecolor = "seagreen"; resultcolor = Colors.SeaGreen; break;
                        case "ll": candidatecolor = "seashell"; resultcolor = Colors.SeaShell; break;
                    }
                    break;
                case 9:
                    switch ((color[0] << 0) + (color[1] << 1) + (color[6] << 2) + (color[7] << 3))
                    {
                        case ('a' << 0) + ('l' << 1) + ('l' << 2) + ('u' << 3): candidatecolor = "aliceblue"; resultcolor = Colors.AliceBlue; break;
                        case ('b' << 0) + ('u' << 1) + ('o' << 2) + ('o' << 3): candidatecolor = "burlywood"; resultcolor = Colors.BurlyWood; break;
                        case ('c' << 0) + ('a' << 1) + ('l' << 2) + ('u' << 3): candidatecolor = "cadetblue"; resultcolor = Colors.CadetBlue; break;
                        case ('c' << 0) + ('h' << 1) + ('a' << 2) + ('t' << 3): candidatecolor = "chocolate"; resultcolor = Colors.Chocolate; break;
                        case ('d' << 0) + ('a' << 1) + ('e' << 2) + ('e' << 3): candidatecolor = "darkgreen"; resultcolor = Colors.DarkGreen; break;
                        case ('d' << 0) + ('a' << 1) + ('a' << 2) + ('k' << 3): candidatecolor = "darkkhaki"; resultcolor = Colors.DarkKhaki; break;
                        case ('f' << 0) + ('i' << 1) + ('i' << 2) + ('c' << 3): candidatecolor = "firebrick"; resultcolor = Colors.Firebrick; break;
                        case ('g' << 0) + ('a' << 1) + ('o' << 2) + ('r' << 3): candidatecolor = "gainsboro"; resultcolor = Colors.Gainsboro; break;
                        case ('g' << 0) + ('o' << 1) + ('r' << 2) + ('o' << 3): candidatecolor = "goldenrod"; resultcolor = Colors.Goldenrod; break;
                        case ('i' << 0) + ('n' << 1) + ('r' << 2) + ('e' << 3): candidatecolor = "indianred"; resultcolor = Colors.IndianRed; break;
                        case ('l' << 0) + ('a' << 1) + ('e' << 2) + ('e' << 3): candidatecolor = "lawngreen"; resultcolor = Colors.LawnGreen; break;
                        case ('l' << 0) + ('i' << 1) + ('l' << 2) + ('u' << 3): candidatecolor = "lightblue"; resultcolor = Colors.LightBlue; break;
                        case ('l' << 0) + ('i' << 1) + ('y' << 2) + ('a' << 3): candidatecolor = "lightcyan"; resultcolor = Colors.LightCyan; break;
                        case ('l' << 0) + ('i' << 1) + ('r' << 2) + ('e' << 3): candidatecolor = "lightgrey"; resultcolor = Colors.LightGrey; break;
                        case ('l' << 0) + ('i' << 1) + ('r' << 2) + ('a' << 3): candidatecolor = "lightgray"; resultcolor = Colors.LightGray; break;
                        case ('l' << 0) + ('i' << 1) + ('i' << 2) + ('n' << 3): candidatecolor = "lightpink"; resultcolor = Colors.LightPink; break;
                        case ('l' << 0) + ('i' << 1) + ('e' << 2) + ('e' << 3): candidatecolor = "limegreen"; resultcolor = Colors.LimeGreen; break;
                        case ('m' << 0) + ('i' << 1) + ('e' << 2) + ('a' << 3): candidatecolor = "mintcream"; resultcolor = Colors.MintCream; break;
                        case ('m' << 0) + ('i' << 1) + ('o' << 2) + ('s' << 3): candidatecolor = "mistyrose"; resultcolor = Colors.MistyRose; break;
                        case ('o' << 0) + ('l' << 1) + ('r' << 2) + ('a' << 3): candidatecolor = "olivedrab"; resultcolor = Colors.OliveDrab; break;
                        case ('o' << 0) + ('r' << 1) + ('r' << 2) + ('e' << 3): candidatecolor = "orangered"; resultcolor = Colors.OrangeRed; break;
                        case ('p' << 0) + ('a' << 1) + ('e' << 2) + ('e' << 3): candidatecolor = "palegreen"; resultcolor = Colors.PaleGreen; break;
                        case ('p' << 0) + ('e' << 1) + ('u' << 2) + ('f' << 3): candidatecolor = "peachpuff"; resultcolor = Colors.PeachPuff; break;
                        case ('r' << 0) + ('o' << 1) + ('o' << 2) + ('w' << 3): candidatecolor = "rosybrown"; resultcolor = Colors.RosyBrown; break;
                        case ('r' << 0) + ('o' << 1) + ('l' << 2) + ('u' << 3): candidatecolor = "royalblue"; resultcolor = Colors.RoyalBlue; break;
                        case ('s' << 0) + ('l' << 1) + ('l' << 2) + ('u' << 3): candidatecolor = "slateblue"; resultcolor = Colors.SlateBlue; break;
                        case ('s' << 0) + ('l' << 1) + ('r' << 2) + ('a' << 3): candidatecolor = "slategray"; resultcolor = Colors.SlateGray; break;
                        case ('s' << 0) + ('l' << 1) + ('r' << 2) + ('e' << 3): candidatecolor = "slategrey"; resultcolor = Colors.SlateGrey; break;
                        case ('s' << 0) + ('t' << 1) + ('l' << 2) + ('u' << 3): candidatecolor = "steelblue"; resultcolor = Colors.SteelBlue; break;
                        case ('t' << 0) + ('u' << 1) + ('i' << 2) + ('s' << 3): candidatecolor = "turquoise"; resultcolor = Colors.Turquoise; break;
                    }
                    break;
                case 10:
                    switch (color.Slice(3, 4))
                    {
                        case "amar": candidatecolor = "aquamarine"; resultcolor = Colors.Aquamarine; break;
                        case "evio": candidatecolor = "blueviolet"; resultcolor = Colors.BlueViolet; break;
                        case "rtre": candidatecolor = "chartreuse"; resultcolor = Colors.Chartreuse; break;
                        case "kora": candidatecolor = "darkorange"; resultcolor = Colors.DarkOrange; break;
                        case "korc": candidatecolor = "darkorchid"; resultcolor = Colors.DarkOrchid; break;
                        case "ksal": candidatecolor = "darksalmon"; resultcolor = Colors.DarkSalmon; break;
                        case "kvio": candidatecolor = "darkviolet"; resultcolor = Colors.DarkViolet; break;
                        case "gerb": candidatecolor = "dodgerblue"; resultcolor = Colors.DodgerBlue; break;
                        case "stwh": candidatecolor = "ghostwhite"; resultcolor = Colors.GhostWhite; break;
                        case "htco": candidatecolor = "lightcoral"; resultcolor = Colors.LightCoral; break;
                        case "htgr": candidatecolor = "lightgreen"; resultcolor = Colors.LightGreen; break;
                        case "iumb": candidatecolor = "mediumblue"; resultcolor = Colors.MediumBlue; break;
                        case "ayaw": candidatecolor = "papayawhip"; resultcolor = Colors.PapayaWhip; break;
                        case "derb": candidatecolor = "powderblue"; resultcolor = Colors.PowderBlue; break;
                        case "dybr": candidatecolor = "sandybrown"; resultcolor = Colors.SandyBrown; break;
                        case "tesm": candidatecolor = "whitesmoke"; resultcolor = Colors.WhiteSmoke; break;
                    }
                    break;
                case 11:
                    switch (color.Slice(4, 2))
                    {
                        case "ma": candidatecolor = "darkmagenta"; resultcolor = Colors.DarkMagenta; break;
                        case "sk": candidatecolor = "deepskyblue"; resultcolor = Colors.DeepSkyBlue; break;
                        case "al": candidatecolor = "floralwhite"; resultcolor = Colors.FloralWhite; break;
                        case "st": candidatecolor = "forestgreen"; resultcolor = Colors.ForestGreen; break;
                        case "ny": candidatecolor = "greenyellow"; resultcolor = Colors.GreenYellow; break;
                        case "ts": candidatecolor = "lightsalmon"; resultcolor = Colors.LightSalmon; break;
                        case "ty": candidatecolor = "lightyellow"; resultcolor = Colors.LightYellow; break;
                        case "jo": candidatecolor = "navajowhite"; resultcolor = Colors.NavajoWhite; break;
                        case "le": candidatecolor = "saddlebrown"; resultcolor = Colors.SaddleBrown; break;
                        case "ng": candidatecolor = "springgreen"; resultcolor = Colors.SpringGreen; break;
                        case "sp": candidatecolor = "transparent"; resultcolor = Colors.Transparent; break;
                        case "ow": candidatecolor = "yellowgreen"; resultcolor = Colors.YellowGreen; break;
                    }
                    break;
                case 12:
                    switch (color[7])
                    {
                        case 'w': candidatecolor = "antiquewhite"; resultcolor = Colors.AntiqueWhite; break;
                        case 'g': candidatecolor = "darkseagreen"; resultcolor = Colors.DarkSeaGreen; break;
                        case 'i': candidatecolor = "lemonchiffon"; resultcolor = Colors.LemonChiffon; break;
                        case 'y': candidatecolor = "lightskyblue"; resultcolor = Colors.LightSkyBlue; break;
                        case 'r': candidatecolor = "mediumorchid"; resultcolor = Colors.MediumOrchid; break;
                        case 'u': candidatecolor = "mediumpurple"; resultcolor = Colors.MediumPurple; break;
                        case 't': candidatecolor = "midnightblue"; resultcolor = Colors.MidnightBlue; break;
                    }
                    break;
                case 13:
                    switch ((color[0] << 0) + (color[4] << 1) + (color[11] << 2))
                    {
                        case ('d' << 0) + ('g' << 1) + ('o' << 2): candidatecolor = "darkgoldenrod"; resultcolor = Colors.DarkGoldenrod; break;
                        case ('d' << 0) + ('s' << 1) + ('u' << 2): candidatecolor = "darkslateblue"; resultcolor = Colors.DarkSlateBlue; break;
                        case ('d' << 0) + ('s' << 1) + ('a' << 2): candidatecolor = "darkslategray"; resultcolor = Colors.DarkSlateGray; break;
                        case ('d' << 0) + ('s' << 1) + ('e' << 2): candidatecolor = "darkslategrey"; resultcolor = Colors.DarkSlateGrey; break;
                        case ('d' << 0) + ('t' << 1) + ('s' << 2): candidatecolor = "darkturquoise"; resultcolor = Colors.DarkTurquoise; break;
                        case ('l' << 0) + ('n' << 1) + ('s' << 2): candidatecolor = "lavenderblush"; resultcolor = Colors.LavenderBlush; break;
                        case ('l' << 0) + ('t' << 1) + ('e' << 2): candidatecolor = "lightseagreen"; resultcolor = Colors.LightSeaGreen; break;
                        case ('p' << 0) + ('g' << 1) + ('o' << 2): candidatecolor = "palegoldenrod"; resultcolor = Colors.PaleGoldenrod; break;
                        case ('p' << 0) + ('t' << 1) + ('s' << 2): candidatecolor = "paleturquoise"; resultcolor = Colors.PaleTurquoise; break;
                        case ('p' << 0) + ('v' << 1) + ('e' << 2): candidatecolor = "palevioletred"; resultcolor = Colors.PaleVioletRed; break;
                    }
                    break;
                case 14:
                    switch ((color[2] << 0) + (color[12] << 1))
                    {
                        case ('a' << 0) + ('n' << 1): candidatecolor = "blanchedalmond"; resultcolor = Colors.BlanchedAlmond; break;
                        case ('r' << 0) + ('u' << 1): candidatecolor = "cornflowerblue"; resultcolor = Colors.CornflowerBlue; break;
                        case ('r' << 0) + ('e' << 1): candidatecolor = "darkolivegreen"; resultcolor = Colors.DarkOliveGreen; break;
                        case ('g' << 0) + ('a' << 1): candidatecolor = "lightslategray"; resultcolor = Colors.LightSlateGray; break;
                        case ('g' << 0) + ('e' << 1): candidatecolor = "lightslategrey"; resultcolor = Colors.LightSlateGrey; break;
                        case ('g' << 0) + ('u' << 1): candidatecolor = "lightsteelblue"; resultcolor = Colors.LightSteelBlue; break;
                        case ('d' << 0) + ('e' << 1): candidatecolor = "mediumseagreen"; resultcolor = Colors.MediumSeaGreen; break;
                    }
                    break;
                case 15:
                    switch (color[6])
                    {
                        case 's': candidatecolor = "mediumslateblue"; resultcolor = Colors.MediumSlateBlue; break;
                        case 't': candidatecolor = "mediumturquoise"; resultcolor = Colors.MediumTurquoise; break;
                        case 'v': candidatecolor = "mediumvioletred"; resultcolor = Colors.MediumVioletRed; break;
                    }
                    break;
                case 16: candidatecolor = "mediumaquamarine"; resultcolor = Colors.MediumAquamarine; break;
                case 17: candidatecolor = "mediumspringgreen"; resultcolor = Colors.MediumSpringGreen; break;
                case 20: candidatecolor = "lightgoldenrodyellow"; resultcolor = Colors.LightGoldenrodYellow; break;
            }

            if(MemoryExtensions.SequenceEqual(candidatecolor.AsSpan(), color))
            //if(MemoryExtensions.Equals(candidatecolor.AsSpan(), color, StringComparison.Ordinal))
            {
                return resultcolor;
            }

            return null;
        }

(the idea taken from from https://github.com/dotnet/roslyn/issues/56374)

Few issues to mention:

  1. optimized version is bigger. it may be undesirable.
  2. optimized version is harder to understand and modify (for example for adding a new color).
  3. I do not check this code on a device because lack of possibility! I cheched only on PC.

If maintainers decides that this approach is fine, few additional points:

  1. I have an Incremental Source Generator that able to generate this body easily. Such generator can be included in this project and disable 2nd issue above.
  2. Also, other places with switch-over-strings can benefit from that source generator. I would like to play with them. Is there any?

Any thoughts? Thanks.

ghost commented 1 year ago

We've moved this issue to the Backlog milestone. This means that it is not going to be worked on for the coming release. We will reassess the backlog following the current release and consider this item at that time. To learn more about our issue management process and to have better expectation regarding different types of issues you can read our Triage Process.