Anders Hesselbom

DOD är bättre OOD för tidskritiska system

2020-08-29

Objektorienterad design (OOD) är ofta ett bra val för att det är relativt enkelt att använda med robusta mönster att följa. Men när man programmerar tidskritiskt, som t.ex. i när man gör spel, kan det vara värt att titta på dataorienterad design (DOD).

DOD handlar om att utnyttja processorns cache. Normalt när man läser och skriver data ber man processorn att läsa och skriva från RAM-minnet. Men när så sker, antar processorn att fler läs- och skrivoperationer kommer att ske med närliggande minneadresser, och cachar således närliggande data. Man kan alltså öka prestandan i sitt program, genom att se till att data som uppdateras ofta ligger nära varandra i minnet.

Jag har en väldigt enkel dator, en liten NUC från ASUS. Jag har skrivit ett litet testprogram i C#/.NET Core 3.1 som skapar 500 rymdskepp och flyttar dessa en halv miljon enheter i sidled, både enligt OOD och DOD.

Den objektorienterade lösningen

Denna kod definierar ett rymdskepp enligt traditionell OOD:

public class Spaceship
{
    public int X { get; set; }
    public int Y { get; set; }
}

Följande lilla kodsnutt skapar 500 rymdskepp i en array (givet att konstanten Ships är satt till 500):

var spaceshipsOop = new Spaceship[Ships];

for (var i = 0; i < Ships; i++)
    spaceshipsOop[i] = new Spaceship
    {
        X = 0,
        Y = i
    };

Och denna kod förflyttar alla 500 skepp en halv miljon enheter åt vänster (eftersom konstanten travelDistance är satt till 500 000):

for (var x = 0; x < travelDistance; x++)
    for (var i = 0; i < Ships; i++)
        spaceshipsOop[i].X++;

Hela kalaset kostar 194 millisekunder (3,124 sekunder i debugläge) för min lilla processor att utföra.

Den dataorienterade lösningen

I den dataorienterade lösningen vill vi försäkra oss om att data som kommer uppdateras samtidigt också finns lagrat tillsammans. Därför skulle definitionen av ett rymdskepp kunna bytas ut mot en definition av samtliga rymdskepp:

public class Spaceships
{
    public int[] X { get; set; }
    public int[] Y { get; set; }
}

Det innebär att koden som skapar 500 rymdskepp istället ser ut så här:

var spaceshipsDoa = new Spaceships
{
    X = new int[Ships], Y = new int[Ships]
};
for (var i = 0; i < Ships; i++)
{
    spaceshipsDoa.X[i] = 0;
    spaceshipsDoa.Y[i] = i;
}

Och slutligen, koden som förflyttar skeppen en halv miljon enheter åt vänster, ser nu ut så här:

for (var x = 0; x < travelDistance; x++)
    for (var i = 0; i < Ships; i++)
        spaceshipsDoa.X[i]++;

På min enhet har processorn fått jobba i 334 millisekunder (1,419 sekunder i debug-läge) för att åstadkomma detta, vilket är en rejäl försämring, men en förbättring på mer än 50 procent i debug-läge.

Vi kan alltså konstatera att man inte har någon automatisk vinst innan man kommer upp i lite tyngre arbeten, och det är därför fördelen med DOD var så tydligt i debug-läge. I release-läge ligger break-even för min del när 500 skepp gör en resa på två miljoner enheter (ungefär 1,2 sekunder oavsett strategi), och vid fem miljoner enheter kostar OOD-lösningen 3,2 sekunder och DOD-lösningen 2,5 sekunder.

Fördelen med DOD minskar ytterligare om antalet rymdskepp som ska förflyttas minskar, men ökar om antalet rymdskepp som ska förflyttas ökar. Med 2000 rymdskepp som ska som ska förflyttas fem miljoner enheter kostar OOD-lösningen 100 sekunder och DOD-lösningen 65 sekunder, vilket är en klart märkbar förbättring. Om en skälig mängd data ska användas väldigt intensivt och prestanda är kritiskt så är DOD att föredra, men i övrigt spelar det ingen större roll

Hela källkoden (C# version 8.0, .NET Core version 3.1):

using System;
using System.Diagnostics;

namespace ConsoleApp2
{
    public class Program
    {
        public const int Ships = 2000;

        private static void Main()
        {
            const int travelDistance = 5000000;

            var spaceshipsOop = new Spaceship[Ships];

            for (var i = 0; i < Ships; i++)
                spaceshipsOop[i] = new Spaceship
                {
                    X = 0,
                    Y = i
                };

            var stopwatch = new Stopwatch();
            stopwatch.Start();
            
            for (var x = 0; x < travelDistance; x++)
                for (var i = 0; i < Ships; i++)
                    spaceshipsOop[i].X++;

            stopwatch.Stop();

            Console.WriteLine($"Object oriented approach: {stopwatch.ElapsedMilliseconds}");

            stopwatch.Reset();

            var spaceshipsDoa = new Spaceships
            {
                X = new int[Ships], Y = new int[Ships]
            };
            for (var i = 0; i < Ships; i++)
            {
                spaceshipsDoa.X[i] = 0;
                spaceshipsDoa.Y[i] = i;
            }

            stopwatch.Start();

            for (var x = 0; x < travelDistance; x++)
                for (var i = 0; i < Ships; i++)
                    spaceshipsDoa.X[i]++;

            stopwatch.Stop();

            Console.WriteLine($"Data oriented approach: {stopwatch.ElapsedMilliseconds}");
        }
    }

    public class Spaceship
    {
        public int X { get; set; }
        public int Y { get; set; }
    }

    public class Spaceships
    {
        public int[] X { get; set; }
        public int[] Y { get; set; }
    }
}

Categories: C#, General