zaterdag 29 mei 2021

Float datatype eenvoudig uitgelegd

Fabien Sanglard legt het veelgebruike type float goed uit. Float is een IEEE 754 standaard.

Kortgezegd heb je 1 sign bit, 8 exponent bits en 23 mantissa bits.

Het exponent gedeelte bepaalt in welk gebied het getal zit. Is de exponent 127, dan ligt het getal ergens tussen 1 en 2. Is de exponent 128 dan ligt het getal ergens tussen 2 en 4, etc.. Is de exponent kleiner dan 127, dan kom je in gebieden onder de 1 uit. Bij een exponent van 125 ligt het getal bijvoorbeeld ergens tussen 0.25 en 0.5.

Het mantissa gedeelte bepaalt waar precies in het gebied het getal is. De gradering is 2 tot de macht 23. Dat is bij kleine gebieden heel klein, maar dat loopt snel terug.

Bij exponent 150 (127+23) is iedere mantissa verhoging precies een verhoging van 1 in het float getal. Dus tot en met 2 tot de macht 24, dat is 16777216 kan ieder heel getal exact weergegeven worden. Daarna ga je sprongen krijgen. 16777217 kan bijvoorbeeld niet gemaakt worden, wel 16777218 bij een mantissa van 1 (mantissa van 0 is in dat geval 16777216).

Uitzonderingen:
Om het getal 0 weer te geven moet je sign 0 hebben, exponent 0 en mantissa 0.
Het getal infinity sign 0, exponent 255 en mantissa 0.
Het getal NaN (not a number) is sign 0, exponent 255 en mantissa ((2^23)-1) oftewel 8388607. Een mantissa van 1 is een Signaling NaN. Het verschil tussen een NaN en een SNaN is dat een SNaN een error veroorzaakt in de FPU module, al heb ik nog niet een SNaN error weten te genereren vanuit software.

Voor de C ontwikkelaars:
    union {
        float theFloat;
        struct {
            unsigned int mantissa : 23;
            unsigned int exponent : 8;
            unsigned int sign : 1;
        } parts;
        Uint32 theULong;
    } f;

    f.theFloat = 0.0f;
    int mantissa = f.parts.mantissa;
    int exponent = f.parts.exponent;
    int sign = f.parts.sign;

Als een float NaN is, dan is f.theFloat != f.theFloat. De float value is dan dus niet gelijk aan zichzelf.

Kleine oefening. Om een mantissa te krijgen die 1 groter is dan het begingetal, doe:

    int exponentVerhoging = 23;
    int beginGetal = 1 << exponentVerhoging;
    f.parts.exponent = 127 + exponentVerhoging;
    long mantissaGetalBeginPlus1 = (1 << 23) / (1 << exponentVerhoging);
    f.parts.mantissa = mantissaGetalBeginPlus1;

Toevoeging 2021-05-30: de "double" variant is soortgelijk. 1 sign bit, 11 exponent bits, 52 mantissa bits.
Daarmee kun je ieder getal tot en met 2 tot de macht 53 exact weergeven, dat is 9007199254740992. Het eerste getal dat niet weergegeven kan worden is dus 9007199254740993.
Het getal 1 is sign 0, exponent 1023, mantissa 0.
Het getal infinity is sign 0, Exponent 2047 en mantissa 0. Het getal 0 weer alles 0.

Opvallend: Wist je dat onder x64 in C/C++ het datatype long 4 bytes groot is? Net als een int, die ook 4 bytes groot is. Pas een "long long" is 8 bytes groot, maar dan gebruik ik liever de alias Sint64 om de duidelijkheid erin te houden. Eigenlijk is het duidelijker om overal Sint32 en Sint64 of Uint32/Uint64 te gebruiken als je met bits manipulatie bezig bent.

dinsdag 25 mei 2021

Waarom DOOM niet extreem soepel loopt op nieuwe CPU's

Een tijdje geleden had ik DOOM BFG edition aangeschaft en het viel mij op dat DOOM niet extreem soepel loopt, terwijl moderne CPU's toch veel sneller zijn dan die van 1993.

De reden hiervoor is de opbouw van het beeld bij DOOM. De muren worden namelijk verticaal getekend door de oorspronkelijke engine. Dus iedere keer een verticale rij van 1 pixel breed. Dat is echt killing voor je CPU cache. Daardoor heb je weinig aan de snelheid van je CPU, want de CPU is alleen maar aan het wachten op je memorybus.

Eerder had ik al geschreven over cachelines. Bij het tekenen van muren in SunRacer heb ik initieel ook geprobeerd om muren verticaal te tekenen, dus 1 pixel breed. Dat was zo langzaam dat het soms niet eens lukte om het hele scherm (1920x1080) te tekenen binnen 1 frame.

De CPU kan 64 bytes tegelijkertijd naar het geheugen wegschrijven, maar als de software vervolgens maar 4 bytes (1 pixel) verandert, dan gooi je een hoop performance weg.

Tegenwoordig houd ik in SunRacer meer rekening met de horizontale cachelines en bereken zoveel mogelijk pixels horizontaal. De CPU heeft dan wel meer werk, omdat er meer programmacode wordt doorlopen per pixel. Maar de CPU stond toch niets te doen. Dus is het uiteindelijke resultaat toch 2 keer sneller.

Waarom kost vermenigvuldigen minder clockcycles dan delen?

De oorspronkelijk Pentium CPU kon in 10 clockcycles een multiply doen, maar had voor een division 41 clockcycles nodig. Waarom is dat?

Als je kijkt naar onze schoolmethoden voor het vermenigvuldigen en delen, dan kun je het antwoord raden.

Vermenigvuldigen doen we namelijk door per cijfer een vermenigvuldiging te doen en de berekende getallen uiteindelijk op te tellen. De vermenigvuldigingsstappen zijn parallel uit te voeren. De CPU doet die stappen dus ook parallel.

Het delen doet de CPU op een soortgelijke methode als onze staartdeling. Die stappen kun je echter niet parallel uitvoeren, want de volgende stap is afhankelijk van de vorige. De CPU kan het probleem dus niet makkelijk parallel oplossen. Daarom duurt het langer.

Je ziet het terug in de logische diagrammen voor multiply en division. Op CPU's die geen float division kunnen doen kun je je wenden tot benaderingen.