[C++] Dynamische variant array (rfc)

[Zoijar]

Ik zit al een tijdje met het volgende probleem en vroeg me af wat men hier van mijn voorlopige oplossing denkt:

Men leest ruwe data uit een file, een sequence bytes, en daarbij staan twee descriptors:het data type, en de dimensie van het type (formaat). Dit is goed te vergelijken met een image bestand. Dat kan 1x 8bit grayscale zijn, 3x 8bit RGB-kleur, 1x 32bit float, etc.

Nu wil ik dynamisch, at run-time, deze data uit kunnen lezen in een gewenst formaat. Vergelijkbaar met OpenGL texture reads. Als je een texture read doet krijg je een vector met 4 floats, ongeacht het onderliggende type en formaat. Zonodig treed er conversie op van bijvoorbeeld int[0,255] naar float[0,1].

Hiervoor heb ik deze C++11 code geschreven (sorry voor de lengte... maar het spreekt wel voor zich denk ik)

C++:

namespace FS {

class VC {
public:
    typedef unsigned char base_type;

    VC() {}
    virtual ~VC() {}

    virtual float floatAt(int i) = 0;
    virtual vec2<float> vec2fAt(int i) = 0;
    virtual vec3<float> vec3fAt(int i) = 0;
    virtual vec4<float> vec4fAt(int i) = 0;

    virtual int intAt(int i) = 0;
    virtual vec2<int> vec2iAt(int i) = 0;
    virtual vec3<int> vec3iAt(int i) = 0;
    virtual vec4<int> vec4iAt(int i) = 0;

    virtual unsigned int size() const = 0;

    void loadRawData(const unsigned char* data, size_t size) {
        m_data.resize(size);
        memcpy(m_data.data(), data, size);
    }

    static std::shared_ptr<VC> create(GLenum type, GLenum format) {
        auto it = registry.find(std::make_pair(type, format));
        if (it == registry.end()) {
            return std::shared_ptr<VC>();
        } else {
            return std::shared_ptr<VC>(it->second());
        }
    }

    static void reg(GLenum type, GLenum format, std::function<VC*()> func) {
        registry[std::make_pair(type, format)] = func;
    }

protected:
    std::vector<base_type> m_data;

private:
    static std::map<std::pair<GLenum, GLenum>, std::function<VC*()> > registry;
};

template <typename F, typename T>
T convert(const F& v) {
    return std::is_integral<F>::value ?
                (std::is_integral<T>::value ? static_cast<T>(v) : static_cast<T>(v) / std::numeric_limits<F>::max())
              :
                (static_cast<T>(v))
    ;
}

constexpr int const_min(int a, int b) {
    return a < b ? a : b;
}

template <typename U, int C>
class ConcreteVC : public VC {
public:
    typedef U value_type;
    const static int components = C;

    ConcreteVC() {
    }

    virtual ~ConcreteVC() {}

    virtual unsigned int size() const {
        return m_data.size() / (sizeof(U) * C);
    }

    inline U& itemAt(int i, int offset) {
        return reinterpret_cast<U*>(m_data.data())[i * components + offset];
    }

    template <typename T>
    inline T itemAtAs(int i, int offset) {
        return convert<U, T>(itemAt(i, offset));
    }

    virtual float floatAt(int i) {
        return itemAtAs<float>(i, 0);
    }

    virtual vec2<float> vec2fAt(int i) {
        return vec2<float>(itemAtAs<float>(i, 0), itemAtAs<float>(i, const_min(1, components-1)));
    }

    virtual vec3<float> vec3fAt(int i) {
        return vec3<float>(itemAtAs<float>(i, 0), itemAtAs<float>(i, const_min(1, components-1)), itemAtAs<float>(i, const_min(2, components-1)));
    }

    virtual vec4<float> vec4fAt(int i) {
        return vec4<float>(itemAtAs<float>(i, 0), itemAtAs<float>(i, const_min(1, components-1)), itemAtAs<float>(i, const_min(2, components-1)), itemAtAs<float>(i, const_min(3, components-1)));
    }

    virtual int intAt(int i) {
        return itemAtAs<int>(i, 0);
    }

    virtual vec2<int> vec2iAt(int i) {
        return vec2<int>(itemAtAs<int>(i, 0), itemAtAs<int>(i, const_min(1, components-1)));
    }

    virtual vec3<int> vec3iAt(int i) {
        return vec3<int>(itemAtAs<int>(i, 0), itemAtAs<int>(i, const_min(1, components-1)), itemAtAs<int>(i, const_min(2, components-1)));
    }

    virtual vec4<int> vec4iAt(int i) {
        return vec4<int>(itemAtAs<int>(i, 0), itemAtAs<int>(i, const_min(1, components-1)), itemAtAs<int>(i, const_min(2, components-1)), itemAtAs<int>(i, const_min(3, components-1)));
    }
};

} // namespace

int main() {
    FS::VC::reg(GL_UNSIGNED_BYTE, GL_RED, [](){return new FS::ConcreteVC<unsigned char, 1>();});
    FS::VC::reg(GL_UNSIGNED_BYTE, GL_RGB, [](){return new FS::ConcreteVC<unsigned char, 3>();});

    std::vector<unsigned char> data = {42,127,128,255,0,1};
    GLenum dataFormat = GL_RED;
    GLenum dataType = GL_UNSIGNED_BYTE;

    auto vc = FS::VC::create(dataType, dataFormat);
    vc->loadRawData(data.data(), data.size());

    for (unsigned int i=0; i<vc->size(); ++i) {
        qDebug() << toQString(vc->intAt(i)) << "\t" << toQString(vc->vec3fAt(i));
    }

    return 0;
}

// Output:
// "42"      "[0.164706, 0.164706, 0.164706]" 
// "127"     "[0.498039, 0.498039, 0.498039]" 
// "128"     "[0.501961, 0.501961, 0.501961]" 
// "255"     "[1, 1, 1]" 
// "0"   "[0, 0, 0]" 
// "1"   "[0.00392157, 0.00392157, 0.00392157]" 

Vector classes werken zoals je zou denken. Code kan iets uitgebreid worden; dit is een simpel voorbeeld.

Aangezien het dynamisch moet gebeuren zie ik geen snellere algemene oplossing dan 1 indirecte call (virtual in dit geval) per gelezen pixel. Kan dat sneller als je over vele pixels itereert? Wat vindt men van deze oplossing? Zit ik op het goede spoor? Zie ik iets over het hoofd dat het simpeler/beter maakt?

Waar ik me ook aan stoor zijn die 8 virtual functions. In principe kan dat als template, maar virtual templates kunnen niet (vrij logisch als je de grootte van je vtable niet kan bepalen)...

Comments?

[Soultaker]

Zoijar schreef op maandag 26 november 2012 @ 15:13:
Aangezien het dynamisch moet gebeuren zie ik geen snellere algemene oplossing dan 1 indirecte call (virtual in dit geval) per gelezen pixel.

't Probleem lijkt me hier niet zozeer dat de call indirect is (als je over veel pixels loopt kan de compiler die vtable lookup meestal wel buiten de lus halen, lijkt me) maar dat 'ie daardoor niet te inlinen is. Dat is het grootste verschil met een statische/inline/template functie.

Is dat erg? Geen idee. Ik denk dat als performance belangrijk is je de bitmap class beter een functie kan geven om (een region van) de image data naar een vast formaat te converteren. (À la glReadPixels().) Zo'n functie kun je wel efficiënt implementeren. Maar of dat in jouw situatie de moeite waard is kan ik natuurlijk niet inschatten...

[.oisyn]

Met Soultaker, ik zou gewoon hele (deel)gebieden in een keer converteren naar een algemeen formaat.

[MLM]

Afhankelijk van wat je wilt bereiken, als je slechts een paar bewerkingen doet/ondersteunt, haal dan je hele bewerking naar de virtual kant.

Anders gewoon omzetting naar een vast "intermediate" formaat (4 x float is prima meestal, tenzij je 32bit ints zonder precisie-verlies wilt kunnen gebruiken).

[.oisyn]

Of 4 doubles, heb je het precisieprobleem ook opgelost

[Zoijar]

Maar hoe traag zou het zijn denken jullie? Een goed voorspelbare functie call kost toch bijna niks? Alles in cache met prediction etc.

Voor integers zou ik ook bv nog zoiets kunnen bedenken:

C++:

unsigned int x[3] = {0,0,0};
char* xx = (char*)x;

for pixels n:
      for typeBytes i: 
          xx[i    ] = data[n+i];
          xx[4+i] = data[n+(min(typeComponents, 1)*typeBytes+i];
          xx[8+i] = data[n+(min(typeComponents, 2)*typeBytes+i];

           // inline call om iets te doen met x[3]

Maar zou dat uitmaken? Loopje sneller dan een indirecte call bv?

Verder was het een beetje een brain-storm; ik weet nog niet precies hoe ik het wil gebruiken of waar. Data kopieren is misschien geen optie als ik bijvoorbeeld een OpenGL hardware buffer memory map.


(ik gebruik nu gewoon een byte buffer en ga uit van een paar standaard layouts indien data op de client nodig is (bv 3x float), anders vertel ik opengl het formaat en die handelt het dan intern wel af)

---
Stel bv je kan een 3d model inladen met een miljoen vertices. Formaat kan verschillen. Als de posities tussen [0,1] liggen kan het bv in 16 bit fixed point op disk/geheugen/gpu staan, anders 32 bit floats, of misschien 16bit floats, etc. Dan wil je een boundig box berekenen (en wie weet wat nog meer). Die berekeningen doe je in principe in floats. Ga je dan al je data kopieren en twee keer in geheugen houden (tientallen MBs?) Lijkt me ook zonde. Dan is dit op zich wel een OK ontwerp, toch?

Kwam hierop omdat ik dit soort code zie staan wat ik erg lelijk vind:

C++:

char* data;
double sum = 0.0;

if (type == FLOAT) {
   for (items i) sum += (float*)(data)[i];
} else if (type == INT) {
   for (items i) sum += (int*)(data)[i];
}

maar wel efficient

Of zoiets?

C++:

template <typename F>
void iterate(char* data, int n, int type, F func) {
    switch (type) {
       case FLOAT: for (i [0,n)) func(((float*)data)[i]); break;
       case INT: etc...
   };
}
double sum = 0.0;
iterate(data, n, dataType, [&sum](double x) {sum += x;}

Wat is nou een goede afweging tussen efficientie en algemeenheid? Die laatste is volgens mij precies even efficient als dat hele gedoe met de virtual calls (welke meer uitbreidbaar is) vanwege het toch aanmoeten roepen van een lambda -- kan een compiler die efficient inlinen als je ze als template passed?

[ Voor 53% gewijzigd door Zoijar op 28-11-2012 19:57 ]

[MLM]

Een virtual call kan niet inlined worden, dat kan performance kosten als de functie erg kort is, en miljoenen keren gecalled word (best mogelijk voor een 1kx1k image). Desondanks heb je goeie kansen dat de code in de cache zit, en performance zou best wel eens mee kunnen vallen (de enige manier om er zeker van te zijn is om het te benchmarken).

De vuistregel blijft echter: "premature optimization is the root of all evil". Ik zou gewoon eerst implementeren wat je leuk vind/het minste tijd kost, en mocht performance non-optimaal zijn, kan je altijd nog verder kijken

[.oisyn]

Je kunt die eerste oplossing ook abstraheren met templates. Het vereist wel dat je alle implementaties kent, want template overloading kan natuurlijk niet door een virtual call.