Advent of Code bij Wolfpack: High Performance C#

NET en C# zijn de afgelopen jaren sterk geëvolueerd. .NET is volledig cross-platform geworden en heeft verbazingwekkende prestatieverbeteringen gekregen. Dit artikel laat nieuwe functies in .NET zien die gebruikt worden om zeer efficiënte en snelle C# code te schrijven.

Nu de feestdagen naderen, komen velen van ons bij Wolfpack in de feeststemming door deel te nemen aan de Advent of Code. Voor degenen die er niet mee bekend zijn: Advent of Code is een jaarlijkse online programmeer uitdaging die bestaat uit een reeks kleine codeer puzzels die elke dag van 1 tot 25 december worden uitgebracht (zoals een echte adventskalender).

Deelnemen aan Advent of Code is voor ons bij Wolfpack een geweldige manier om onze probleemoplossende-, codeer- en rekenvaardigheden te oefenen en tegelijkertijd wat plezier te hebben. We vergelijken onze aanpakken, bespreken oplossingen en motiveren elkaar om mee te doen. Sommige ontwikkelaars proberen te zien hoe ver ze kunnen komen door alleen Excel-spreadsheets te gebruiken, en we hebben ook elk jaar verschillende projectmanagers die mee doen!

Niet elke oplossing van een Advent of Code-puzzel hoeft gericht te zijn op efficiëntie en snelheid. Het doel is om plezier te hebben en er iets van te leren. Voor dag 6 dit jaar heb ik me wel gefocust op efficiëntie en snelheid. In deze blogpost wil ik drie manieren belichten om de puzzel te implementeren en verken ik hun performance.

Dag 06 van 2022

Dag 6 van Advent of Code dit jaar gaat over het vinden van een “marker” in een reeks tekens. Deze marker is een subreeks van een bepaalde lengte die unieke tekens bevat (dus geen duplicaten). In deel één van de puzzel moeten we een marker van vier karakters vinden. Deel twee vereist dat we een marker van veertien verschillende karakters vinden.

Bij voorbeeld, in het volgende “bericht”:

zccnvctfwqggmdngplrshbvqnoimdavb

De marker van deel één start op  index 3 (nvct) en de marker van deel twee start op index 15 (gpl…imd).

Wil je dit zelf oplossen, lees dan onderstaande oplossing nog niet!

De eerste ‘sliding window’ aanpak

De eenvoudige aanpak zou een ‘sliding window’ zijn. Je begint bij index 0 en maakt een ‘venster’ met de vereiste marker lengte die steeds een index opschuift. Voor ieder venster wordt gecontroleerd of deze duplicaten bevat.

Dit kan op de volgende manier worden bereikt met behulp van een HashSet:

public static int FindStartOfMarkerUsingHashSet(string input, int markerLength)
{
    for (int i = 0; i < input.Length - markerLength; i++)
        if (new HashSet<char>(input.Substring(i, markerLength)).Count == markerLength)
            return i;

    throw new InvalidOperationException("The input has no valid marker.");
}

Dit fragment is kort en klaart de klus, maar voor elke mogelijke marker die het controleert, wordt er een nieuwe string en HashSet gealloceerd op de heap, en is het vrij traag. Het uitvoeren van deze code met mijn daadwerkelijke invoer resulteert in 1,58 MB aan geheugengebruik en een gemiddelde totale tijd van 636,17 microseconden. (1 milliseconde is 1000 microseconden)

Span gebruiken allocaties tegen te gaan

We kunnen voorkomen dat er allocaties zijn op de heap voor elk venster dat we controleren door de Span<T> feature te gebruiken, die toegevoegd is in C#7.2 en .NET Core 2.1.

Een Span is niet veel meer dan een verwijzing naar een bepaald geheugenadres plus een lengte. In wezen is de Span ons venster. Het vertelt ons waar in de string we momenteel kijken.

Een snellere en allocatie vrije implementatie van deze puzzel zou zijn:

public static int FindStartOfMarkerUsingSpan(string input, int markerLength)
{
    ReadOnlySpan<char> span = input.AsSpan();
    for (int index = 0; index < input.Length - markerLength; index++)
    {
        ReadOnlySpan<char> subSpan = span[index..(index + markerLength)];

        if (!ContainsDuplicates(subSpan))
            return index;
    }

    throw new InvalidOperationException("The input has no valid marker.");

    static bool ContainsDuplicates(ReadOnlySpan<char> input)
    {
        for (int i = 0; i < input.Length; i++)
            for (int j = i + 1; j < input.Length; j++)
                if (input[i] == input[j])
                    return true;

        return false;
    }
}

 We kunnen deze aanpak ook benchmarken. De benchmark vertelt ons dat er inderdaad geen allocaties plaatsvinden in onze code. De tijd die nodig is voor mijn invoer van deel twee is nu 19,26 microseconden! Bijna 43 keer sneller! Als dit een zogenaamd “hot path” van een programma is (het wordt vaak uitgevoerd), kan de bespaarde tijd echt oplopen tot seconden of minuten voor processen.

Sprongen en stackalloc gebruiken voor ultieme performance

Een 43-voudige versnelling is indrukwekkend, maar het kan nog beter. De volgende oplossing heeft een andere aanpak van het venster. We houden bij wanneer elk uniek karakter voor het laatst voorkomt. Als we dit karakter opnieuw zien in ons venster, springen we direct naar de index na de eerste keer waar het karakter voorkomt.

Als we bijvoorbeeld eerder een h hebben gezien na 8 tekens en we zien nog een h na 11 tekens, kunnen we 9 karakters overslaan omdat de volgende 8 vensters allemaal een duplicaat h zullen bevatten. Deze informatie kan worden opgeslagen in een array van grootte 26. Elke index komt overeen met de plaats van een letter van het alfabet.

Om de methode allocatievrij te houden, gebruiken we het keyword stackalloc om een array op de stack toe te wijzen.

Hier is het volledige fragment voor de jump & stackalloc-implementatie:

public static int FindStartOfMarkerUsingSkipForward(string input, int payloadSize)
{
    ReadOnlySpan<char> span = input.AsSpan();
    Span<int> charOccurredAt = stackalloc int['z' - 'a' + 1];
    charOccurredAt.Fill(-1);

    int markerBase = 0;
    for (int i = payloadSize - 1; i >= 0; i--)
    {
        int currCharIndex = markerBase + i;
        char currChar = span[currCharIndex];
        int currCharAlreadyOccuredAt = charOccurredAt[currChar - 'a'];

        if (currCharAlreadyOccuredAt >= markerBase &&
            currCharIndex < currCharAlreadyOccuredAt)
        {
            markerBase = currCharIndex + 1;
            i = payloadSize;
            continue;
        }

        charOccurredAt[currChar - 'a'] = currCharIndex;
    }

    return markerBase;
}

Benchmarking van deze aanpak laat zien dat het gemiddeld 1,85 microseconden duurt, wat iets meer dan tien keer sneller is dan onze vorige geoptimaliseerde versie en in totaal 450 keer sneller dan de HashSet-aanpak! Ik zou zeggen dat we de Advent of Code-uitdaging van vandaag hebben overwonnen.

Benchmark

Er is een geweldige NuGet package om benchmarks voor C# code te maken: Benchmark.net. Dit leidt tot de volgende tabel:

Tbl 1. De resultaten van de benchmark

Deze tabel kan ook als grafiek worden weergegeven. Merk op dat de duur in microseconden logaritmisch is.

Fig 1. Een grafiek van de benchmark die de duur en het geheugengebruik weergeeft (gemaakt met behulp van ChartBenchmark.net)

Advent of Code bij Wolfpack

Samenvattend, deelnemen aan Advent of Code met collega’s bij Wolfpack is een leuke en lonende ervaring. Deze uitdagingen verbeteren niet alleen onze probleemoplossende-, codeer- en rekenvaardigheden, we leren ook collega’s beter kennen met die we normaal gesproken niet veel zien. We raden alle softwareontwikkelaars ten zeerste aan om deel te nemen aan dit jaarlijkse evenement en zelf de voordelen te ervaren. Veel codeer plezier!

Heb je interesse om volgend jaar met ons mee te doen aan Advent of Code? Zie onze vacatures.