C vs C#: de Gaussian blur van VLC versnellen

Update, 12 oktober: twee kleine wijzigingen in de broncode zorgen ervoor dat de regel-voor-regel C#-versie binnen 8% van de C-versie blijft. Details aan het einde van Ronde 1.

In mijn vorige bericht liet ik zien dat een native VLC 4-plugin volledig in C# geschreven kan worden, dankzij .NET Native AOT. De voor de hand liggende volgende vraag is niet hoe, maar hoe snel. VLC is geschreven in C, videofilters raken elke pixel van elk frame aan, en C# heeft een garbage collector. Dat moet toch iets kosten?

In plaats van te gissen, heb ik een echt VLC-filter gekozen, dit regel voor regel naar C# geport en beide versies binnen dezelfde VLC getest op dezelfde frames, met een byte-identiek resultaat. Daarna heb ik beide versies geoptimaliseerd en opnieuw getest. Twee keer.

Een blur met een historie

Een Gaussian blur vervangt elke pixel door een gewogen gemiddelde van de omliggende pixels: de dichtstbijzijnde tellen het zwaarst, en het gewicht neemt af volgens de klokcurve die Carl Friedrich Gauss in 1809 gebruikte om meetfouten te beschrijven. Die vloeiende overgang zorgt ervoor dat het resultaat lijkt op een lens die niet in focus is, in plaats van een blokkerige vlek. Eén getal bepaalt dit effect, de sigma: VLC kijkt naar buren tot 3 x sigma pixels afstand. Een sigma van 4 betekent dus een window van 25 pixels.

Het is een van de oudste effecten in digitale beeldverwerking: Photoshop 1.0 had het al in 1990, en GIMP, FFmpeg en GStreamer hebben er ook een. VLC heeft dit sinds 2007, te vinden onder Tools > Effects and Filters > Video Effects > Advanced als "Spatial blur".

Hoe VLC dit aanpakt

Een Gaussian blur is separabel: het blurren van elke rij en vervolgens elke kolom geeft exact hetzelfde resultaat als een volledig 2D-window. Een window van 25 x 25 (625 vermenigvuldigingen per pixel) wordt zo gereduceerd tot twee passes van 25. VLC's gaussianblur.c doet precies dat, met integers: een horizontale pass naar een buffer, een verticale pass over de buffer, en vervolgens een deling door de som van de gewichten. Hier is de horizontale pass:

for( int i_line = 0; i_line < i_visible_lines; i_line++ )
{
    for( int i_col = 0; i_col < i_visible_pitch; i_col++ )
    {
        type_t t_value = 0;
        const int c = i_line*i_in_pitch+i_col;
        for( int x = __MAX( -i_dim, -i_col*(x_factor+1) );
             x <= __MIN( i_dim, (i_visible_pitch - i_col)*(x_factor+1) + 1 );
             x++ )
        {
            t_value += pt_distribution[x+i_dim] *
                       p_in[c+(x>>x_factor)];
        }
        pt_buffer[c] = t_value;
    }
}

Dezelfde code, in C#

De C#-versie is een bewuste regel-voor-regel port: dezelfde loops, dezelfde grenzen, dezelfde integer-berekeningen en raw pointers waar de C-versie die ook gebruikt.

for (int line = 0; line < visibleLines; line++)
{
    for (int col = 0; col < visiblePitch; col++)
    {
        int value = 0;
        int c = line * inPitch + col;
        for (int x = Math.Max(-dim, -col * (xFactor + 1));
             x <= Math.Min(dim, (visiblePitch - col) * (xFactor + 1) + 1);
             x++)
        {
            value += distribution[x + dim] * input[c + (x >> xFactor)];
        }
        buffer[c] = value;
    }
}

Deze versie draait als een VLC-plugin via VLCLR, gecompileerd met Native AOT: een native DLL die VLC laadt als elke andere plugin. Het filter reserveert niets op de managed heap per frame, waardoor de garbage collector niets hoeft op te ruimen tijdens de uitvoering.

Om de vergelijking eerlijk te houden, is elke versie uitgevoerd in dezelfde VLC 4 release-build, tegen het eigen ongewijzigde filter, met byte-identieke frames als resultaat. Elke filter-aanroep is op dezelfde manier gemeten op een 1080p clip, op een laptop met een 11e-gen Intel Core i7 (Tiger Lake, 4 cores). De resultaten tonen milliseconden per frame op .NET 10 bij drie verschillende blur-sterktes, naast de frames per seconde (fps) bij sigma 4. .NET 8 en 11 scoren binnen enkele procenten hiervan.

Ronde 1: regel voor regel

Milliseconden per 1080p frame (C# op .NET 10), lager is beter.

Versie	sigma 2	sigma 4	sigma 8
Huidige VLC	62.0	125.9	252.9
C# port	78.9	155.2	298.1

C wint, zoals verwacht: de C#-port doet er ongeveer 23% langer over per frame. Geen ramp, maar een duidelijk gat.

De machinecode laat zien waarom. Voor de bovenstaande inner loop houdt clang de lopende som in een register en berekent de loop-grens één keer. De code-generator van .NET, RyuJIT, produceert ongeveer twee keer zoveel instructies: het berekent Math.Min(...) bij elke stap opnieuw en bewaart de som in het geheugen. Dezelfde rekenkunde, maar meer administratie eromheen.

Update, 12 oktober: Na publicatie heb ik onderzocht hoeveel van dit gat wordt veroorzaakt door de code-generator en hoeveel door de manier waarop de C# is geschreven. Twee kleine aanpassingen dichten het gat grotendeels: het berekenen van de loop-grenzen in lokale variabelen vóór de loop (zodat RyuJIT stopt met het herhaaldelijk evalueren van Math.Min(...)) en het gebruik van nint voor de indexen, zodat er geen 32- naar 64-bit conversie meer nodig is bij elke geheugenaccess. Clang doet dit automatisch. Dezelfde loops, dezelfde rekenkunde, byte-identieke output:

- int c = line * inPitch + col;
- for (int x = Math.Max(-dim, -col * (xFactor + 1));
-      x <= Math.Min(dim, (visiblePitch - col) * (xFactor + 1) + 1);
-      x++)
+ nint c = (nint)line * inPitch + col;
+ nint xStart = Math.Max(-dim, -col * (xFactor + 1));
+ nint xEnd = Math.Min(dim, (visiblePitch - col) * (xFactor + 1) + 1);
+ for (nint x = xStart; x <= xEnd; x++)

Milliseconden per 1080p frame (C# op .NET 10), lager is beter.

Versie	sigma 2	sigma 4	sigma 8
Huidige VLC	62.6	137.9	256.7
C# port	78.9	169.0	303.6
C# port, bounds hoisted	67.9	126.4	263.5

Met deze twee aanpassingen komt de regel-voor-regel C# binnen 8% van de C-versie en is hij bij sigma 4 zelfs sneller. Een deel van het gat zat in de compiler, en een deel in code waar de compiler wat hulp bij nodig had.

Ronde 2: hetzelfde algoritme, beide geoptimaliseerd

Voordat ik naar SIMD greep, was er veel te winnen met het algoritme zelf. Ik heb dezelfde vier wijzigingen op beide talen toegepast, nog steeds als eenvoudige scalaire code zonder SIMD of threads:

1. Vervang de deling door een vermenigvuldiging. Buiten de randen verandert de divisor nooit, dus een vooraf berekende "magische" reciproque en een shift geven exact hetzelfde resultaat, zonder de traagste instructie in de loop.
2. Lees geheugen in de volgorde waarin het is opgeslagen. De verticale pass liep in kolommen naar beneden en sprong bij elke stap een hele rij vooruit. Door volledige rijen te accumuleren wordt het geheugen sequentieel gelezen.
3. Gebruik de symmetrie van de klokcurve. wa + wb wordt w*(a+b): de helft minder vermenigvuldigingen.
4. Behandel de randen apart, zodat het binnenste gedeelte een simpelere loop kan draaien zonder dat er grenzen berekend hoeven te worden.

Milliseconden per 1080p frame (C# op .NET 10), lager is beter.

Versie	sigma 2	sigma 4	sigma 8
Huidige VLC	62.0	125.9	252.9
Geoptimaliseerde C	23.3	40.7	75.4
Geoptimaliseerde C#	28.1	50.6	98.9

De C#-versie, nog steeds scalaire code, is 2,5 keer sneller dan de huidige VLC-code. C blijft echter voorop lopen: C# doet er ongeveer 24% langer over, om dezelfde redenen als in ronde 1. Nog een voordeel voor C: clang zet deze simpelere loops automatisch om in SIMD-code. Ik heb dat uitgeschakeld om dezelfde code te vergelijken, maar met die functie aan behaalt de C-versie 34 fps zonder dat er één regel SIMD-code in de bron staat.

Ronde 3: tot het uiterste getuned

In de laatste ronde mogen beide zijden alles gebruiken wat ze in huis hebben: AVX2 SIMD, op één thread, met dezelfde byte-identieke output. C gebruikt intrinsics uit immintrin.h, C# gebruikt System.Runtime.Intrinsics. Het ontwerp is in beide talen hetzelfde: 16 pixels per instructie in de horizontale pass, samengevoegde taps voor de kleurvlakken, en een deling die exact in floating point wordt uitgevoerd.

De inner loop van de horizontale pass in C:

__m256i sum = _mm256_mullo_epi16(
    _mm256_cvtepu8_epi16( _mm_loadu_si128( (const __m128i *)p ) ), vw0 );
for( int i = 0; i < pair_count; i++ )
{
    const int o = pair_offsets[i];
    const __m256i both = _mm256_add_epi16(
        _mm256_cvtepu8_epi16( _mm_loadu_si128( (const __m128i *)(p - o) ) ),
        _mm256_cvtepu8_epi16( _mm_loadu_si128( (const __m128i *)(p + o) ) ) );
    sum = _mm256_add_epi16( sum,
        _mm256_mullo_epi16( both, _mm256_set1_epi16( (short)pair_weights[i] ) ) );
}

En in C#:

Vector256<ushort> sum = Avx2.MultiplyLow(
    Avx2.ConvertToVector256Int16(p).AsUInt16(), vw0);
for (int i = 0; i < pairCount; i++)
{
    int o = pairOffsets[i];
    Vector256<ushort> both = Avx2.Add(
        Avx2.ConvertToVector256Int16(p - o).AsUInt16(),
        Avx2.ConvertToVector256Int16(p + o).AsUInt16());
    sum = Avx2.Add(sum,
        Avx2.MultiplyLow(both, Vector256.Create((ushort)pairWeights[i])));
}

Indien mogelijk is de C#-versie zelfs leesbaarder: de types geven aan wat er in elk register zit, terwijl C voor alles één __m256i gebruikt.

In mijn eerste SIMD-versie deed C# er 14% langer over, en 30% langer bij de grootste blur. Dezelfde vector-instructies, maar clang unrolled de loops eromheen en hield de pointers in registers. Daarom ben ik aan beide kanten doorgegaan met bredere loops, twee taps per multiply (vpmaddwd), gevectoriseerde randen en geen scalaire staarten. Alleen aan de C#-kant heb ik de code hervormd totdat .NET produceerde wat clang standaard produceert: de hot loop in zijn eigen methode, en gewichten die direct vanuit het geheugen worden gebroadcast.

Milliseconden per 1080p frame (C# op .NET 10), lager is beter.

Versie	sigma 2	sigma 4	sigma 8
Huidige VLC	62.5	128.9	253.8
Getunede C	3.08	4.17	6.62
Getunede C#	3.05	4.23	7.22

Nu liggen ze dicht bij elkaar: bij sigma 2 en 4 zijn ze gelijkwaardig (binnen de meetfout), en bij de grootste blur doet C# er 9% langer over. Beiden zijn 30 keer sneller dan de huidige VLC-code.

Conclusies

Prestaties bij sigma 4, 1080p:

Methode	C	C#
Huidige VLC / regel-voor-regel port	8 fps	6 fps
Zelfde algoritme, geoptimaliseerd	25 fps	20 fps
Tot het uiterste getuned (SIMD)	240 fps	236 fps

Regel voor regel doet de C#-port er ongeveer 23% langer over. Niet vanwege de garbage collector, die hier niets te ruimen heeft, of bounds checks, die worden vermeden door raw pointers. Het ligt aan de code-generator: LLVM doet een beter werk met deze loops dan RyuJIT. (Update: twee kleine aanpassingen brengen dit terug naar binnen 8% van C).

Met extra werk is het gat bijna gedicht. Een deel daarvan was het herschrijven van C# zodat .NET produceert wat clang standaard produceert. Dat is de werkelijke kost van het kiezen voor C# in dit scenario: weten wat de compiler met je loops doet.

C# is een realistische keuze voor een VLC-plugin die werk op de CPU uitvoert. De C#-filter blurrt 1080p-video met ongeveer 140 frames per seconde, zelfs bij sigma 8, op één core.

Tijdens dit proces heb ik ook twee VLC-bugs gevonden die niets met snelheid te maken hebben: bij hardware-decodering kleurde elk CPU-filter de helft van het beeld groen, en de blur leest twee bytes voorbij de rechterrand van elke lijn. Ik heb hiervoor merge-requests ingediend.

Er zijn manieren om beide versies nog sneller te maken, zoals AVX-512 of het spreiden van het werk over meerdere cores, maar ik ben hier gestopt.

Ik ben ook benieuwd hoeveel van het gat bij de regel-voor-regel port echt door de code-generator komt. .NET heeft een experimentele NativeAOT-LLVM branch die C# compileert met LLVM, dezelfde backend die clang gebruikt. Dit is momenteel alleen beschikbaar voor WebAssembly, dus het kan een plugin bouwen voor de WebAssembly-versie van VLC, maar niet voor de desktopversie die hier is gebruikt.

Dit was een experiment om de twee talen op dezelfde CPU-code te vergelijken, niet de beste manier om video te blurren: een filter als dit hoort op de GPU. GPU-versies van enkele VLC-filters zijn momenteel in ontwikkeling.

Als die laatste 10% cruciaal is, blijft C het antwoord. Voor al het andere zal de taal waarin je het meest productief bent, gecombineerd met een goed algoritme, je verder brengen.

Probeer het zelf

De blur maakt nu deel uit van VLCLR, in een nieuwe VLCLR.Filters bibliotheek: GaussianBlur voert al deze versies uit op VLC-beelden. Het GaussianBlur voorbeeld verpakt dit in een volledige VLC-filterplugin van ongeveer 70 regels, van het uitlezen van de sigma-optie tot het alloceren van het uitvoerbeeld.

Net als bij het vorige bericht heb ik het experiment en de regels ontworpen, en heeft Claude het grootste deel van de code en de benchmark-omgeving geschreven.