[C++] Size specifieke implementatie voor templates

[Verwijderd]

Mijn vraag

Ik ben redelijk nieuw met het gebruik van templates in C++. Het leek me daarom een goed idee om wat meer ervaring met templates op te doen en dus wat bestaande code te herschrijven. Ik heb op dit moment meerdere helper functies om te controleren of de parity van een specifiek integer type even of oneven is. Om deze code aan te passen naar templates was ik geneigd om het volgende te doen:

code:

template <typename T>
bool IsEvenParity(T)
{
    switch (sizeof(T))
    {
        case 1:
            //implementation goes here for uint8_t
            break;

        case 2:
            //implementation goes here for uint16_t
            break;

        case 4:
            ////implementation goes here for uint32_t
            break;

        case 8:
            //implementation goes here for uint64_t
            break;

        default: // Incompatible
            static_assert(sizeof(T) <= 8, "Incompatible integer type T")
    }
}

De code hierboven is inefficiënt en hoogstwaarschijnlijk fout. Mijn vraag is dus: hoe kan ik een template gebruiken voor size specifieke types, zonder voor elke type een nieuwe template te schrijven ?

Relevante software en hardware die ik gebruik

Visual Studio 2019

Wat ik al gevonden of geprobeerd heb

Google zoeken heeft geen oplossing geboden.

[cosmo50]

Ik ben geen expert met C++, dus of het de efficiëntste oplossing is kan ik niet met zekerheid zeggen. Echter, lijkt dit mij een typisch geval van template specialization. Met de eerste hit op google voor deze term, https://en.cppreference.c...e/template_specialization, kom je er denk ik uit!

[Verwijderd]

Bedankt, ik had nog nooit van de term "template specialization" gehoord (ik ben maar een hobbyist C/C++ programmeur). Met deze info kan ik gerichter gaan zoeken.

[Daos]

Het idee van functie-templates is dat je 1 functie/algoritme schrijft dat direct met allerlei soorten data-typen kan werken. Als je een switch doet op de grootte en dan aparte algoritmes aanroept zoals jij doet, dan kan je net zo goed losse functies schrijven.

Voorbeeldje hoe het wel werkt. Parameter value en lokale variabele test zijn van type T (mijn algoritme gaat fout als de meest linkse bit gezet is of als value signed is; het is alleen ter illustratie):

C++:

#include <iostream>

template <typename T>
bool IsEvenParity(T value)
{
    T test = 1;
    
    bool isEvenParity = true;
    
    while (test < value)
    {
        if (value & test)
        {
            isEvenParity = !isEvenParity;
        }
        
        test <<= 1;
    }
    
    return isEvenParity;
}

int main() {
    uint8_t x1 = 0x35; // 2 + 2 = 4 ones = even
    uint16_t x2 = 0x1234; // 1 + 1 + 2 + 1 = 5 ones = odd 
    uint32_t x3 = 0x12345678; // 1 + 1 + 2 + 1 + 2 + 2 + 3 + 1 = 13 ones = odd
    uint64_t x4 = 0x1234567812345678; // 2 x 13 = 26 ones = even

    std::cout << (IsEvenParity(x1) ? "even" : "odd") << std::endl;
    std::cout << (IsEvenParity(x2) ? "even" : "odd") << std::endl;
    std::cout << (IsEvenParity(x3) ? "even" : "odd") << std::endl;
    std::cout << (IsEvenParity(x4) ? "even" : "odd") << std::endl;

    return 0;
}

Je kan natuurlijk wel de grootte gebruiken voor een loopje. In dit geval kan je een lookup-table voor een byte maken en dan via een loopje over de bytes in je parameter lopen om de totale parity te bepalen.

[.oisyn]

@Daos En toen riep je je code aan met de most significant bit op 1

@Verwijderd Je voorbeeld is een beetje ongelukkig gekozen. De code van Daos werkt op zich wel (met een kleine aanpassing om de potentiele oneindige lus te voorkomen), maar echt generiek is hij uiteindelijk niet; het werkt alleen met (unsigned) integers. Het gebruik van een template is hier simpelweg niet echt de juiste keuze. Je zou dan ook gewoon louter een implementatie kunnen maken voor uint64_t en impliciete conversies van andere ints het werk verder laten doen.

[ Voor 15% gewijzigd door .oisyn op 13-09-2021 22:44 ]

[zzattack]

I.p.v. een switch op sizeof(T) kun je tegenwoordig een constexpr-if statement gebruiken. If-branches waarvan compile-time al bepaald kan worden dat ze nooit uitgevoerd worden zullen ook niet meegecompileerd worden.

code:

template <typename T>
bool IsEvenParity(T value) {
  if constexpr (std::is_same_v<T, uint8_t>) { /* code die value als uint8_t behandelt */ }
  else if constexpr (std::is_same_v<T, uint16_t>) { /* code die value als uint16_t behandelt */ }
  ...
}

Helpt je verder niet aangezien templates hier niet echt het juiste gereedschap is.

[ Voor 18% gewijzigd door zzattack op 13-09-2021 23:16 . Reden: .oisyn heeft gelijk ]

[.oisyn]

@zzattack En toen was T een signed integer en deed de compiler aan sign extension bij een shift-right op signed ints

Mijn duit dan:

C++:

#include <climits>
#include <concepts> // C++20

template<std::integral T>
constexpr bool IsEvenParity(T value)
{
    using uint = std::make_unsigned_t<T>;
    uint uvalue(value);

    constexpr uint numbits = static_cast<uint>(CHAR_BIT * sizeof(T));
    uint shift = 1;
    while(shift < numbits)
    {
        uvalue ^= static_cast<uint>(uvalue >> shift);
        shift <<= 1;
    }

    return (uvalue & 1) == 0;
}

(Zonder C++20 concepts zou je het nog zo kunnen doen:

code:

#include <type_traits>

template<class T>
constexpr std::enable_if_t<bool, std::is_integral_v<T>> IsEvenParity(T value)
// ...

Of gewoon niet met integral check, maar dan gaat std::make_unsigned_t<> klagen als je 't aanroept met non-integral types)

[ Voor 87% gewijzigd door .oisyn op 14-09-2021 00:07 ]

[Verwijderd]

.oisyn schreef op maandag 13 september 2021 @ 22:32:
@Verwijderd Je voorbeeld is een beetje ongelukkig gekozen. De code van Daos werkt op zich wel (met een kleine aanpassing om de potentiele oneindige lus te voorkomen), maar echt generiek is hij uiteindelijk niet; het werkt alleen met (unsigned) integers. Het gebruik van een template is hier simpelweg niet echt de juiste keuze. Je zou dan ook gewoon louter een implementatie kunnen maken voor uint64_t en impliciete conversies van andere ints het werk verder laten doen.

Na het lezen van de reacties denk inderdaad dat mijn huidige code niet echt geschikt is om door een template te vervangen. De code wordt o.a. gebruik in CPU emulators en moet dus zo snel mogelijk zijn. Dat is tevens ook de reden waarom er een specifieke implementatie nodig is voor verschillende unsigned types.

Hierbij een voorbeeld van de huidige code voor de uint8_t en uint32_t versies:

code:

inline bool IsEvenParity8(uint8_t x)
{
#ifdef  CORE_ALLOW_INTRINSICS
    return (~(__popcnt(x)) & 1);
#else
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return (~x) & 1;
#endif
}

code:

inline bool IsEvenParity32(uint32_t x)
{
#ifdef  CORE_ALLOW_INTRINSICS
    return (~(__popcnt(x)) & 1);
#else
    x ^= x >> 16;
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return (~x) & 1;
#endif
}

Zoals je kunt zien maak ik dus gebruik van compiler intrinsics (indien mogelijk) met een fallback. Voor uint64_t types is het zelfs nog iets complexer omdat er geen 64-bit popcnt instructie beschikbaar is (enkel de 32-bit versie) als we voor x86 compileren. Dit moet ik dus specifiek afvangen d.m.v. preprocessor directives.

Iedereen bedankt voor het meedenken!

[.oisyn]

Heh, die code is precies wat mijn template implementatie doet . Er zijn ²log(B) operaties met B het aantal bits van het getal. Zie hier hoe de loop gewoon wordt geunrolled.

[ Voor 6% gewijzigd door .oisyn op 14-09-2021 00:09 ]

[Verwijderd]

Ha inderdaad! Dit geeft dus maar aan dat ik nog veel te leren heb m.b.t. C++. Heb met regelmaat nog moeite om de overstap te maken vanaf C, maar al doende leert men

[ThomasG]

.oisyn schreef op dinsdag 14 september 2021 @ 00:06:
Heh, die code is precies wat mijn template implementatie doet . Er zijn ²log(B) operaties met B het aantal bits van het getal. Zie hier hoe de loop gewoon wordt geunrolled.

Het is nog verder te verbeteren